加权共享近邻优化的密度峰值聚类算法

doi:10.3778/j.issn.1673-9418.2405064

摘要/Abstract

摘要： 密度峰值聚类算法DPC的样本局部密度定义随数据集规模大小不同而不同，样本局部密度受到截断距离[dc]影响，且其一步分配策略会带来样本分配的“多米诺骨牌效应”，严重影响聚类结果。提出基于加权共享近邻优化的密度峰值聚类算法（WSN-DPC）。该算法利用基于标准差加权的距离代替传统欧氏距离，强化样本不同特征对距离的贡献；利用共享近邻信息定义样本相似度，进而定义样本局部密度和相对距离，以尽可能体现数据集中样本的真实分布信息。同时，采用不同分配策略对离群点和非离群点依次进行分配，使得每个样本能够尽可能地分配到正确类簇。多个数据集的实验测试和统计性检验结果表明，WSN-DPC算法优于DPC及其改进算法，有效地解决了DPC算法的缺陷。

关键词: 共享近邻, 局部密度, 加权距离, 类簇中心, 聚类

Abstract: DPC (clustering by fast search and find of density peaks) algorithm??s local density definition varies with the size of a dataset, the local density of a point is sensitive to the cutoff distance dc, and its single-step assignment strategy for the remaining points can cause the “domino effect”, resulting in its incapability in finding the genuine clustering in a dataset. To address the limitations, this paper proposes a density peak clustering algorithm based on weighted shared neighbors (WSN-DPC). This algorithm utilizes standard deviation weighted distance to enhance the Euclidean distance, thereby highlighting the contributions of different features to the distances between points. Additionally, shared neighbor information is used to define the similarities between points, and the local density and relative distance of a point are defined, so as to reflect the true distribution of points within a dataset as far as possible. Furthermore, distinct assignment strategies are employed in turn for outliers and non-outliers in the dataset, so as to guarantee that each point is to be assigned to its most appropriate cluster. Extensive experiments across multiple datasets and the statistically significant test demonstrate that the proposed WSN-DPC is superior to DPC and its variants, while addressing the limitations of DPC.

Key words: shared neighbor, local density, weighted distance, cluster center, clustering

张文杰, 谢娟英. 加权共享近邻优化的密度峰值聚类算法[J]. 计算机科学与探索, 2025, 19(4): 929-944.

ZHANG Wenjie, XIE Juanying. Density Peak Clustering Algorithm Optimized by Weighted Shared Neighbors[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(4): 929-944.

参考文献

[1] 陈磊, 吴润秀, 李沛武, 等. 加权K近邻和多簇合并的密度峰值聚类算法[J]. 计算机科学与探索, 2022, 16(9): 2163-2176.
CHEN L, WU R X, LI P W, et al. Weighted K-nearest neighbors and multi-cluster merge density peaks clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(9): 2163-2176.
[2] 刘娟, 万静. 自然反向最近邻优化的密度峰值聚类算法[J]. 计算机科学与探索, 2021, 15(10): 1888-1899.
LIU J, WAN J. Optimized density peak clustering algorithm by natural reverse nearest neighbor[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(10): 1888-1899.
[3] JAIN A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666.
[4] GUHA S, RASTOGI R, SHIM K. Cure: an efficient clustering algorithm for large databases[J]. Information Systems, 2001, 26(1): 35-58.
[5] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: an efficient data clustering method for very large databases[C]//Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1996: 103-114.
[6] SHEIKHOLESLAMI G, CHATTERJEE S, ZHANG A D. WaveCluster: a wavelet-based clustering approach for spatial data in very large databases[J]. The VLDB Journal, 2000, 8(3): 289-304.
[7] WANG W, YANG J, MUNTZ R R. STING: a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd Very Large Data Bases Conference, 1997: 186-195.
[8] 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. New York: ACM, 1996: 226-231.
[9] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[10] 谢娟英, 张文杰. 局部标准差优化的密度峰值聚类算法[J]. 陕西师范大学学报(自然科学版), 2024, 52(3): 47-62.
XIE J Y, ZHANG W J. Density peak clustering algorithm optimized with local standard deviation[J]. Journal of Shaanxi Normal University (Natural Science Edition), 2024, 52(3): 47-62.
[11] ZELNIK-MANOR L, PERONA P, ZELNIK-MANOR L, et al. Self-tuning spectral clustering[C]//Proceedings of the 18th International Conference on Neural Information Processing Systems, 2004: 1601-1608.
[12] 谢娟英, 高红超, 谢维信. 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.
[13] XIE J Y, GAO H C, XIE W X, et al. Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J]. Information Sciences, 2016, 354: 19-40.
[14] BIAN Z K, CHUNG F L, WANG S T. Fuzzy density peaks clustering[J]. IEEE Transactions on Fuzzy Systems, 2021, 29(7): 1725-1738.
[15] REN C H, SUN L F, YU Y, et al. Effective density peaks clustering algorithm based on the layered K-nearest neighbors and subcluster merging[J]. IEEE Access, 2020, 8: 123449-123468.
[16] XIE J Y, LIU X L, WANG M Z, et al. SDW-DPC: an advanced clustering algorithm by searching density peaks using standard deviation weighted distance[C]//Proceedings of the 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems. Piscataway: IEEE, 2022: 131-137.
[17] WANG S L, LI Q, ZHAO C F, et al. Extreme clustering-a clustering method via density extreme points[J]. Information Sciences, 2021, 542: 24-39.
[18] LIU R, WANG H, YU X M. Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J]. Information Sciences, 2018, 450: 200-226.
[19] CHEN J G, YU P S. A domain adaptive density clustering algorithm for data with varying density distribution[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(6): 2310-2321.
[20] SUN L, QIN X Y, DING W P, et al. Density peaks clustering based on k-nearest neighbors and self-recommendation[J]. International Journal of Machine Learning and Cybernetics, 2021, 12(7): 1913-1938.
[21] ZHANG Q H, DAI Y Y, WANG G Y. Density peaks clustering based on balance density and connectivity[J]. Pattern Recognition, 2023, 134: 109052.
[22] SEYEDI S A, LOTFI A, MORADI P, et al. Dynamic graph-based label propagation for density peaks clustering[J]. Expert Systems with Applications, 2019, 115: 314-328.
[23] GUO W J, WANG W H, ZHAO S P, et al. Density peak clustering with connectivity estimation[J]. Knowledge-Based Systems, 2022, 243: 108501.
[24] KELLY M, LONGJOHN R, NOTTINGHAN K. The UCI machine learning repository[EB/OL]. [2024-02-16]. https://archive.ics.uci.edu.
[25] 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.
[26] CHANG H, YEUNG D Y. Robust path-based spectral clustering[J]. Pattern Recognition, 2008, 41(1): 191-203.
[27] VEENMAN C J, REINDERS M J T, BACKER E. A maximum variance cluster algorithm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(9): 1273-1280.
[28] XIE J Y, JIANG W L. An adaptive clustering algorithm by finding density peaks[C]//Proceedings of the 15th Pacific Rim International Conference on Artificial Intelligence. Cham: Springer, 2018: 317-325.
[29] HANDL J, KNOWLES J. Multi-objective clustering and cluster validation[M]//Multi-objective machine learning. Berlin, Heidelberg: Springer, 2006: 21-47.