Density Peak Clustering Algorithm Based on Ball-Tree

doi:10.3778/j.issn.1002-8331.2009-0284

Abstract

Abstract:

In order to overcome the deficiencies of clustering by fast search and find of density peaks（DPC） for its high time complexity and low accuracy, an optimized fast density peak clustering algorithm is proposed based on Ball-Tree in this paper（BT-DPC）. The algorithm defines local density of a point based on [k]-nearest neighbor, and constructs a ball tree to accelerate the calculation of the local density [ρ] and the distance [δ]. In the cluster allocation stage, the statistical learning allocation strategy is designed based on the [k]-nearest neighbors idea to classify the boundary points correctly. The experimental result shows that the BT-DPC algorithm can improve the time performance on the basis of increasing clustering quality compared with DPC algorithm and other popular clustering algorithms through the theory analysis and the experiments on several real-world datasets from the UCI machine learning repository.

Key words: clustering algorithm, ball-tree, clustering by fast search and find of density peaks（DPC）, allocation strategy

摘要：

针对密度峰值聚类算法DPC（clustering by fast search and find of density peaks）时间复杂度高、准确度低的缺陷，提出了一种基于Ball-Tree优化的快速密度峰值聚类算法BT-DPC。算法利用第[k]近邻度量样本局部密度，通过构建Ball-Tree加速密度[ρ]及距离[δ]的计算；在类簇分配阶段，结合[k]近邻思想设计统计学习分配策略，将边界点正确归类。通过在UCI数据集上的实验，将该算法与原密度峰值聚类算法及其改进算法进行了对比，实验结果表明，BT-DPC算法在降低时间复杂度的同时提高了聚类的准确度。

关键词: 聚类算法, ball-tree, 密度峰值聚类, 分配策略

DING Songyang, TIAN Qingyun. Density Peak Clustering Algorithm Based on Ball-Tree[J]. Computer Engineering and Applications, 2021, 57(20): 90-96.

丁松阳，田青云. Ball-Tree优化的密度峰值聚类算法[J]. 计算机工程与应用, 2021, 57(20): 90-96.

References

[1] XU R，WUNSCH D.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks，2005，16（3）：645-678.
[2] FREY B J，DUECK D.Clustering by passing messages between data points[J].Science，2007，315（5814）：972-976.
[3] DU M，DING S，JIA H，et al.Study on density peaks clustering based on k-nearest neighbors and principal component analysis[J].Knowledge Based Systems，2016：135-145.
[4] MOOSMANN F，NOWAK E，JURIE F，et al.Randomized clustering forests for image classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（9）：1632-1646.
[5] LI Z，LIU J，YANG Y，et al.Clustering-guided sparse structural learning for unsupervised feature selection[J].IEEE Transactions on Knowledge and Data Engineering，2014，26（9）：2138-2150.
[6] CHAIRA T.A novel intuitionistic fuzzy C means clustering algorithm and its application to medical images[J].Applied Soft Computing，2011，11（2）：1711-1717.
[7] MACQUEEN J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability，1967，1（14）：281-297.
[8] JAIN A K.Data clustering：50 years beyond K-means[C]//International Conference on Pattern Recognition，2010：651-666.
[9] ESTER M，KRIEGEL H，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with Noise[C]//Knowledge Discovery and Data Mining，1996：226-231.
[10] MURTAGH F，CONTRERAS P.Algorithms for hierarchical clustering：an overview[J].Wiley Interdisciplinary Reviews-Data Mining and Knowledge Discovery，2012，2（1）：86-97.
[11] DONG S，LIU J，LIU Y，et al.Clustering based on grid and local density with priority-based expansion for multi-density data[J].Information Sciences，2018：103-116.
[12] RODRIGUEZ A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.
[13] ZHANG W K，LI J.Extended fast search clustering algorithm：widely density clusters，no density peaks[J].Computer Science，2015：1-17.
[14] 谢娟英，高红超，谢维信.K近邻优化的密度峰值快速搜索聚类算法[J].中国科学：信息科学，2016，46（2）：258-280.
XIE J Y，GAO H C，XIE W X.K-nearest neighbors optimized clustering algorithm by fast search and finding the density peaks of a dataset[J].SCIENTIA SINICA Informationis，2016，46（2）：258-280.
[15] XIE J Y，GAO H，XIE W，et al.Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J].Information Sciences，2016：19-40.
[16] CHEN Y，HU X，FAN W，et al.Fast density peak clustering for large scale data based on KNN[J].Knowledge-Based Systems，2020，187：104824.
[17] 纪霞，姚晟，赵鹏.相对邻域与剪枝策略优化的密度峰值聚类算法[J].自动化学报，2020，46（3）：562-575.
JI X，YAO S，ZHAO P.Relative neighborhood and pruning strategy optimized density peaks clustering algorithm[J].Acta Automatica Sinica，2020，46（3）：562-575.
[18] 贾露，张德生，吕端端.物理学优化的密度峰值聚类算法[J].计算机工程与应用，2020，56（13）：47-53.
JIA L，ZHANG D S，LV D D.Optimized density peak clustering algorithm in physics[J].Computer Engineering and Applications，2020，56（13）：47-53.
[19] OMOHUNDRO S M.Five balltree construction algorithms[R].International Computer Science Institute，1989.
[20] LIU T，MOORE A W，GRAY A，et al.New algorithms for efficient high-dimensional nonparametric classification[J].Journal of Machine Learning Research，2006：1135-1158.
[21] MOORE A W.The anchors hierarchy：using the triangle inequality to survive high dimensional data[C]//Uncertainty in Artificial Intelligence，2000：397-405.
[22] 杜沛，程晓荣.一种基于[K]近邻的比较密度峰值聚类算法[J].计算机工程与应用，2019，55（10）：161-168.
DU P，CHENG X R.Comparative density peaks clustering based on [K]-nearest neighbors[J].Computer Engineering and Applications，2019，55（10）：161-168.