基于反向最近邻的密度估计聚类算法

doi:10.3778/j.issn.1002-8331.2403-0075

摘要/Abstract

摘要： 基于相互最近邻的密度峰聚类算法（DenMune）通过相互最近邻计算数据点的局部密度，是一种有效的聚类手段。但该算法存在构建聚类骨架不合理的问题，在分配弱点时采用硬投票策略，易产生错误。因此提出一种新的基于反向最近邻的密度估计聚类算法（RNN-DEC）。该算法引入反向最近邻来计算数据点的局部密度，将数据点分成强点、弱点和噪声点。使用强点构建聚类算法的骨架，通过软投票的方式将弱点分配到与其相似度最高的簇中去。提出了一种基于反向最近邻的簇融合算法，将相似度高的子簇融合，得到最终的聚类结果。实验结果表明，在一些合成数据集和UCI真实数据集上，相比较于其他经典算法，该算法具有更好的聚类效果。

关键词: 反向最近邻, 局部密度, 密度聚类算法, 子簇融合

Abstract: The density peak clustering algorithm based on mutual nearest neighbors (DenMune) is an effective clustering method that calculates the local density of data points through mutual nearest neighbors. However, this algorithm has the problem of unreasonable construction of clustering skeletons, and using a hard voting strategy when allocating weaknesses can easily lead to errors. Therefore, a new density estimation clustering algorithm based on reverse nearest neighbor (RNN-DEC) is proposed. This algorithm introduces reverse nearest neighbors to calculate the local density of data points, dividing them into strong points, weak points, and noisy points. It builds the skeleton of the clustering algorithm using strong points and assigns weaknesses to the cluster with the highest similarity through soft voting. Finally, a cluster fusion algorithm based on reverse nearest neighbor is proposed, which fuses high similarity sub clusters to obtain the final clustering result. The experimental results show that compared to other classical algorithms, this algorithm has better clustering performance on some synthetic datasets and UCI real datasets.

Key words: reverse nearest neighbor, local density, density clustering algorithm, subcluster fusion

许梅梅, 侯新民. 基于反向最近邻的密度估计聚类算法[J]. 计算机工程与应用, 2025, 61(1): 165-173.

XU Meimei, HOU Xinmin. Density Estimation Clustering Method Based on Reverse Nearest Neighbor[J]. Computer Engineering and Applications, 2025, 61(1): 165-173.

参考文献

[1] SHI Y, CHEN Z, QI Z, et al. A novel clustering-based image segmentation via density peaks algorithm with mid-level feature[J]. Neural Computing and Applications, 2017, 28(1): 29-39.
[2] GOMEZ-SANCHEZ G, DELGADO-SERRANO L, CARRERA D, et al. Clustering and graph mining techniques for classification of complex structural variations in cancer genomes[J]. Scientific Reports, 2022, 12(1): 3244.
[3] CARCILLO F, BORGNE Y L, CAELEN O, et al. Combining unsupervised and supervised learning in credit card fraud detection[J]. Information Sciences, 2021, 557(1): 317-331.
[4] ZHU E Z, MA R H. An effective partitional clustering algorithm based on new clustering validity index[J]. Applied Soft Computing, 2018, 71: 608-621.
[5] LU J C, KANG Z, WANG B Y, et al. Multi-view subspace clustering via partition fusion[J]. Information Sciences, 2021, 560: 410-423.
[6] CABEZAS L M C, IZBICKI R, STERN R B. Hierarchical clustering: visualization, feature importance and model selection[J]. Applied Soft Computing, 2023, 141: 110303.
[7] XU J, WANG G, DENG W. DenPEHC: density peak based efficient hierarchical clustering[J]. Information Sciences, 2016, 373: 200-218.
[8] HIRECHE C, DRIAS H, MOULAI H. Grid based clustering for satisfiability solving[J]. Applied Soft Computing, 2020, 88: 106069.
[9] CHATTERJEE A, MUKHERJEEJ, AIKAT S, et al. Semi-supervised classification of paddy fields from dual polarized synthetic aperture radar images using deep learning[J]. International Journal of Remote Sensing, 2021, 42(5): 1867-1892.
[10] EZUGWU A E, IKOTUN A M, OYELADE O, et al. A comprehensive survey of clustering algorithms: state-of-the-art machine learning applications, taxonomy, challenges, and future research prospects[J]. Engineering Applications of Artificial Intelligence, 2022, 110: 104743.
[11] ESTER M, KRIEGEL H P, SANDER J, et al. A density based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, Aug 2-4, 1996. Menlo Park: AAAI, 1996: 226-231.
[12] CAMPELLO R J G B, MOULAVI D, SANDER J. Density-based clustering based on hierarchical density estimates[C]//Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Gold Coast, Australia, 2013: 160-172.
[13] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[14] ZUO W D, HOU X M. An improved probability propagation algorithm for density peak clustering based on natural nearest neighborhood[J]. Array, 2022, 15: 100232.
[15] ABBAS M, EL-ZOGHABI A, SHOUKRY A. DenMune: density peak based clustering using mutual nearest neighbors[J]. Pattern Recognition, 2021, 109: 107589.
[16] ABBAS M, EL-ZOGHABI A, SHOUKRY A. PyMune: a Python package for complex clusters detection[J]. Software Impacts, 2023, 17: 100564.
[17] TAO Y, YIU M L, MAMOULIS N. Reverse nearest neighbor search in metric spaces[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(9): 1239-1252.
[18] BRITO M R, CHAVEZ E L, QUIROZ A J, et al. Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection[J]. Statistics & Probability Letters, 1997, 35(1): 33-42.
[19] HU Z, BHATNAGAR R. Clustering algorithm based on mutual K-nearest neighbor relationships[J]. Statistical Analysis and Data Mining, 2012, 5(2): 100-113.
[20] VINH N X, EPPS J, BAILEY J. Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance[J]. Journal of Machine Learning Research, 2010, 11: 2837-2854.
[21] HUBERT L, ARABIE P. Comparing partitions[J]. Journal of Classification, 1985, 2(1): 193-218.
[22] FOWLKES E, MALLOWS C. A method for comparing two hierarchical clusterings[J]. Journal of the American Statistical Association, 1983, 78(383): 553-569.
[23] QADDOURA R, FARIS H, ALJARAH I. An efficient clustering algorithm based on the k-nearest neighbors with an indexing ratio[J]. International Journal of Machine Learning and Cybernetics, 2020, 11(3): 675-714.
[24] FENG C, TAGUCHI Y, KAMAT V R. Fast plane extraction in organized point clouds using agglomerative hierarchical clustering[C]//Proceedings of the 2014 IEEE International Conference on Robotics and Automation, Hong Kong, China, May 31-Jun 7, 2014. Piscataway: IEEE, 2014: 6218-6225.
[25] LIU R, WANG H, YU X. Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J]. Information Sciences, 2018, 450: 200-226.
[26] LAURENS V D M. Accelerating t-SNE using tree-based algorithms[J]. Journal of Machine Learning Research, 2015, 15(1): 3221-3245.