基于互近邻相对距离的最小生成树聚类算法.docx

基于互近邻相对距离的最小生成树聚类算法
基于互近邻相对距离的最小生成树聚类算法
摘要：最小生成树（MinimumSpanningTree,MST）聚类是一种常用的划分数据集的方法，通过构建最小生成树来刻画数据集间的联系。然而，传统的MST聚类方法仅基于数据之间的绝对距离，无法准确地反映数据间的相对距离。为了解决这个问题，本文提出了一种基于互近邻相对距离的最小生成树聚类算法。该算法首先通过计算数据点之间的相对距离来构建一个相对距离矩阵，并利用Prim算法构建最小生成树。然后，引入互近邻相对距离，并将其作为权重添加到最小生成树的边上。最后，通过剪枝操作将最小生成树划分为多个子树，得到最终的聚类结果。实验结果表明，该算法在多个公开数据集上表现出了很好的聚类性能。
关键词：最小生成树聚类，相对距离，互近邻，剪枝操作
1.引言
随着大数据时代的到来，对于海量数据的聚类分析成为了一个重要的研究课题。最小生成树聚类是一种常用的聚类方法，它通过构建数据集的最小生成树，来描述数据点之间的联系。然而，传统的MST聚类方法仅基于数据之间的绝对距离，忽略了数据点之间的相对距离。而相对距离能够更准确地反映数据之间的远近关系，因此，基于相对距离的最小生成树聚类方法具有更好的聚类性能。
2.相关工作
在传统的最小生成树聚类方法中，一般采用欧氏距离或曼哈顿距离作为数据之间的距离度量。然而，这些方法都忽略了数据点之间的相对距离，导致最终的聚类结果不够准确。为了解决这个问题，一些研究者提出了基于互近邻相对距离的最小生成树聚类算法。这些算法通过计算数据点之间的相对距离，并将其作为权重添加到最小生成树的边上，从而更准确地刻画数据之间的联系。
3.方法
基于互近邻相对距离的最小生成树聚类算法主要包括以下几个步骤：
（1）计算相对距离矩阵：通过计算数据点之间的相对距离，构建一个相对距离矩阵。
（2）构建最小生成树：利用Prim算法根据相对距离矩阵构建最小生成树。
（3）添加权重：引入互近邻相对距离，并将其作为权重添加到最小生成树的边上。
（4）剪枝操作：通过剪枝操作将最小生成树划分为多个子树，得到最终的聚类结果。
4.实验结果
本文在多个公开数据集上对提出的算法进行了实验验证。实验结果表明，基于互近邻相对距离的最小生成树聚类算法相比传统的MST聚类方法具有更好的聚类性能。该算法能够更准确地刻画数据之间的联系，并得到更准确的聚类结果。
5.结论
本文提出了一种基于互近邻相对距离的最小生成树聚类算法，该算法能够更准确地刻画数据之间的联系，并得到更准确的聚类结果。实验结果表明，该算法在多个公开数据集上表现出了很好的聚类性能。然而，本文提出的算法还有一些局限性，例如对于高维数据的处理效果较差。因此，后续工作可以进一步改进算法，以提高其适用性和准确性。
参考文献：
[1]HanJ,KamberM.DataMining:ConceptsandTechniques[M].Elsevier,2011.
[2]PrimRC.Shortestconnectionnetworksandsomegeneralizations[J].BellSystemTechnicalJournal,1957,36(6):1389-1401.
[3]LiCT,ChenMS,YuPS.Adataclusteringalgorithmbasedonaminimumspanningtree[J].ExpertSystemswithApplications,2008,35(3):798-802.
[4]WangC,LiY,HuiP.Aneighbor-distance-basedclusteringalgorithm[J].PatternRecognitionLetters,2017,90:18-24.