自适应多密度峰值子簇融合聚类算法

doi:10.3778/j.issn.1002-8331.2212-0234

摘要/Abstract

摘要： 经典的密度峰值聚类算法在计算局部密度时过分依赖截断距离，在分配非中心点时易出现连锁效应，且人工选取聚类中心点的方式难以识别出密度不均匀簇的聚类中心。针对该问题，提出一种自适应多密度峰值子簇融合聚类算法。考虑样本的邻域信息，将自然邻居的思想引入密度峰值聚类中，实现了样本点局部密度的自适应计算；为发现稀疏密度簇的中心，提出一种簇中心自动选取策略用于确定初始子簇中心，并使用一种两阶段分配策略降低连锁效应发生的概率；提出一种基于K近邻相似度的度量准则，将相似度高的子簇进行融合，得到最终的聚类结果。在二维合成数据集以及UCI数据集上，相较经典的密度峰值聚类算法以及近年来对其改进的算法，该算法表现出更优异的性能。

关键词: 自然邻居, 密度峰值聚类, 多子簇融合, 分配策略

Abstract: The classical density peak clustering algorithm relies too much on the cutoff distance when calculating the local density, it is prone to chain effects when assigning non-central points, and it is difficult to identify the cluster centers with uneven density by manually selecting the cluster center points. To solve the above problems, an adaptive multi-density peak sub-cluster fusion clustering algorithm is proposed. Considering the neighborhood information of the samples, the idea of natural neighbors is introduced into the density peak clustering to realize the self-adaptive calculation of the local density of the sample points. In order to find the centers of the sparse clusters, an automatic cluster center selection strategy is proposed to determine the initial sub-cluster center, and a two-step allocation strategy is used to reduce the probability of the occurrence of chain effects. A K-nearest neighbor similarity measurement criterion is proposed, and the subclusters with high similarity are fused to obtain the final clustering result. Compared with the classical density peak clustering algorithm and its improved algorithms in recent years, the algorithm shows better performance on two-dimensional synthetic datasets and UCI datasets.

Key words: natural neighbors, density peak clustering, multi-sub cluster fusion, assignment strategy

陈迪, 杜韬, 周劲, 仵匀政, 王心耕. 自适应多密度峰值子簇融合聚类算法[J]. 计算机工程与应用, 2023, 59(23): 73-85.

CHEN Di, DU Tao, ZHOU Jin, WU Yunzheng, WANG Xingeng. Adaptive Multi-Density Peak Sub-Cluster Fusion Clustering Algorithm[J]. Computer Engineering and Applications, 2023, 59(23): 73-85.

参考文献

[1] 孙林，秦小营，徐久成，等.基于K近邻和优化分配策略的密度峰值聚类算法[J].软件学报，2022，33（4）：1390-1411.
SUN L，QIN X Y，XU J C，et al.Density peak clustering algorithm based on k-nearest neighbors and optimal assignment strategy[J].Journal of Software，2022，33（4）：1390-1411.
[2] YANG L，CHEUNG Y M，YUAN Y T.Self-adaptive multiprototype-based competitive learning approach：a k-means-type algorithm for imbalanced data clustering[J].IEEE Transactions on Cybernetics，2019，51（3）：1598-1612.
[3] AHMAD A，KHAN S S.initKmix-a novel initial partition generation algorithm for clustering mixed data using k-means-based clustering[J].Expert Systems with Applications，2020，167（2）：114149.
[4] 胡春安，王家欣，毛伊敏.基于分组和IGSA的并行密度聚类算法[J].计算机应用研究，2021，38（11）：3293-3299.
HU C A，WANG J X，MAO Y M.Density-based clustering algorithm based on groups and improve gravitational search[J].Application Research of Computers，2021，38（11）：3293-3299.
[5] GUO W J，WANG W H，ZHAO S P，et al.Density peak clustering with connectivity estimation[J].Knowledge-Based Systems，2022，243（5）：108501.
[6] 江婧婷，郑朝晖.面向大规模节点划分的网格密度峰值聚类[J].小型微型计算机系统，2022，43（3）：498-505.
JIANG J T，ZHENG C H.Density peak and grid based clustering for large-scale node partition[J].Journal of Chinese Mini-Micro Computer Systems，2022，43（3）：498-505.
[7] 孙璐，梁永全.融合网格划分和DBSCAN的改进聚类算法[J].计算机工程与应用，2022，58（14）：73-79.
SUN L，LIANG Y Q.Improved clustering algorithm fusing grid partition and DBSCAN[J].Computer Engineering and Applications，2022，58（14）：73-79.
[8] WANG R，ZHOU J，JIANG H，et al.A general transfer learning-based Gaussian mixture model for clustering[J].International Journal of Fuzzy Systems，2021，23（3）：776-793.
[9] 李凯，张可心.结构α-熵的加权高斯混合模型的子空间聚类[J].电子学报，2022，50（3）：718-725.
LI K，ZHANG K X.Structural α-entropy weighting Gaussian mixture model for subspace clustering[J].Chinese Journal of Electronics，2022，50（3）：718-725.
[10] 张熠玲，杨燕，周威，等.CMvSC：知识迁移下的深度一致性多视图谱聚类网络[J].软件学报，2022，33（4）：1373-1389.
ZHANG Y L，YANG Y，ZHOU W，et al.CMvSC：knowledge transferring based deep consensus network for multi-view spectral clustering[J].Journal of Software，2022，33（4）：1373-1389.
[11] TANG H，ZHU X，CHEN K，et al.Towards uncovering the intrinsic data structures for unsupervised domain adaptation using structurally regularized deep clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2021，44（10）：6517-6533.
[12] HARTIGAN J A，WONG M A.Algorithm AS 136：a k-means clustering algorithm[J].Journal of the Royal Statistical Society，1979，28（1）：100-108.
[13] 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 KDD，1996：226-231.
[14] RODRIGUEZ A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344：1492-1496.
[15] DU M H，DING S F，JIA H J.Study on density peaks clustering based on k-nearest neighbors and principal component analysis[J].Knowledge-Based Systems，2016，99（5）：135-145.
[16] JIANG J H，CHEN Y J，MENG X Q，et al.A novel density peaks clustering algorithm based on k-nearest neighbors for improving assignment process[J].Physica A：Statistical Mechanics and Its Applications，2019，523（1）：702-713.
[17] 刘娟，万静.自然反向最近邻优化的密度峰值聚类算法[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.
[18] 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（1）：19-40.
[19] ABDULRAHMAN L，MORADI P，BEIGY H.Density peaks clustering based on density backbone and fuzzy neighborhood[J].Pattern Recognition，2020，107（12）：107449.
[20] 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（6）：200-226.
[21] CHEN J，PHILIP S Y.A domain adaptive density clustering algorithm for data with varying density distribution[J].IEEE Transactions on Knowledge and Data Engineering，2019，33（6）：2310-2321.
[22] 赵力衡，王建，陈虹君.去中心化加权簇归并的密度峰值聚类算法[J].计算机科学与探索，2022，16（8）：1910-1922.
ZHAO L H，WANG J，CHEN H J.Density peak clustering algorithm for decentralized weighted cluster merge[J].Journal of Frontiers of Computer Science and Technology，2022，16（8）：1910-1922.
[23] CHEN D，DU T，ZHOU J，et al.A domain density peak clustering algorithm based on natural neighbor[J].Intelligent Data Analysis，2023，27（2）：443-462.
[24] ZHU Q，FENG J，HUANG J.Natural neighbor：a self-adaptive neighborhood method without parameter K[J].Pattern Recognition Letters，2016，80（9）：30-36.
[25] XU X，DING S，WANG Y，et al.A fast density peaks clustering algorithm with sparse search[J].Information Sciences，2021，554：61-83.
[26] GUO X，GAO L，LIU X，et al.Improved deep embedded clustering with local structure preservation[C]//Proceedings of the IJCAI，2017：1753-1759.