结合密度比和系统演化的密度峰值聚类算法

doi:10.3778/j.issn.1002-8331.2105-0444

摘要/Abstract

摘要： 密度峰值聚类算法（DPC）能够有效地进行非球形数据的聚类，该算法需要输入截断距离，人工截取聚类中心，导致DPC算法的聚类效果有时较差。针对这些问题，提出一种结合密度比和系统演化的密度峰值聚类算法（DS-DPC）。利用自然最近邻搜索得出各样本点的邻居数目，根据密度比思想改进密度计算公式，使其能够反映周围样本的分布情况；对局部密度与相对距离的乘积进行降序排列，根据排序值选出聚类中心，将剩余样本按照DPC算法的分配策略进行聚类，避免了手动选择聚类中心的主观性；利用系统演化方法判断聚类结果是否需要合并或分离。通过在多个数据集上进行实验，并与其他聚类算法进行比较，实验结果表明，该算法具有较好的聚类效果。

关键词: 密度峰值聚类算法, 自然最近邻, 密度比, 系统演化方法, 聚类

Abstract: The density peak clustering（DPC） algorithm can effectively cluster non-spherical data. However, the algorithm needs to input the cutoff distance and manually intercept the clustering center, which causes the poor clustering effect of the DPC algorithm sometimes. To solve these problems, this paper proposes a density peak clustering algorithm combining density-ratio and system evolution（DS-DPC）. The natural nearest neighbor search is used to obtain the number of neighbors of each sample point, and the density calculation formula is improved according to the idea of density-ratio, so that it can reflect the distribution of surrounding samples. According to the ranking value, the product of the local density and the relative distance is sorted in descending order, the cluster centers, and clusters the remaining samples are selected, according to the allocation strategy of the DPC algorithm, avoiding the subjectivity of manually selecting the cluster centers. The system evolution method is used to determine whether the clustering results need to be merged or separated. Through experiments on multiple data sets and comparison with other clustering algorithms, the experimental results show that the proposed algorithm has a better clustering effect.

Key words: density peak clustering algorithm, natural nearest neighbor, density-ratio, system evolution method, clustering

曹俊茸, 张德生, 肖燕婷. 结合密度比和系统演化的密度峰值聚类算法[J]. 计算机工程与应用, 2022, 58(21): 75-82.

CAO Junrong, ZHANG Desheng, XIAO Yanting. Density Peak Clustering Algorithm Combining Density-Ratio and System Evolution[J]. Computer Engineering and Applications, 2022, 58(21): 75-82.

参考文献

[1] 何晓群.多元统计分析[M].北京：中国人民大学出版社，2015：41-45.
HE X Q.Multivariate statistical analysis[M].Beijing：China Renmin University Press，2015：41-45.
[2] TAN P N，STEINBACH M，KUMAR V.数据挖掘导论[M].范明，范宏建，译.北京：人民邮电出版社，2011：327-377.
TAN P N，STEINBACH M，KUMAR V.Introduction to data mining[M].FAN M，FAN H J.Beijing：Posts & Telecom Press，2011：327-377.
[3] SAMINA K，RASHID M，MUHAMMAD S I，et al.Density peaks based clustering for single-cell interpretation via multikernel learning-science direct[J].Procedia Computer Science，2019，147：71-76.
[4] RODRIGUEZ A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.
[5] 王洋，张桂珠.自动确定聚类中心的密度峰值算法[J].计算机工程与应用，2018，54（8）：137-142.
WANG Y，ZHANG G Z.Automatically determine density of cluster center of peak algorithm[J].Computer Engineering and Applications，2018，54（8）：137-142.
[6] 杜沛，程晓荣.一种基于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.
[7] LI C Z，ZHANG Y N.Density peak clustering based on relative density optimization[J].Mathematical Problems in Engineering，2020（9）：1-8.
[8] MILAN P，PANG W，HAOD H，et al.FREDPC：a feasible residual error-based density peak clustering algorithm with the fragment merging strategy[J].IEEE Access，2019（99）：1-17.
[9] JIANG J H，ZHOU W，WANG L M，et al.HaloDPC：an improved recognition method on halo node for density peak clustering algorithm[J].International Journal of Pattern Recognition and Artificial Intelligence，2019，33（8）：1-19.
[10] WANG Y Z，WANG D，ZHANG X F，et al.MATLAB code of McDPC：multi-center density peak clustering[J].Neural Computing and Applications，2020，32（17）：13465-13478.
[11] WANG L M，LI M Y，HAN X M，et al.Improved density peak clustering algorithm based on choosing strategy automatically for cut-off distance and cluster centre[J].Tehnicki Vjesnik，2018，25（2）：536-545.
[12] 高诗莹，周晓锋，李帅.基于密度比例的密度峰值聚类算法[J].计算机工程与应用，2017，53（16）：10-17.
GAO S Y，ZHOU X F，LI S.Clustering by fast search and find of density peaks based on density-raito[J].Computer Engineering and Applications，2017，53（16）：10-17.
[13] ZHU Q S，FENG J，HUANG J L.Natural neighbor：a self-adaptive neighborhood method without parameter K[J].Pattern Recognition Letters，2016，80（5）：30-36.
[14] HUANG J.Research on parameterless clustering algorithm based on natural nearest neighbor[D].Chongqing：Chongqing University，2014.
[15] WANG K J，ZHENG J，ZHANG J Y.Estimating the number of clusters via system evolution for cluster analysis of gene expression data[J].IEEE Transactions on Information Technology in Biomedicine，2009，13（5）：848-853.
[16] RASHID M，ZHANG G Z，BIE R F，et al.Clustering by fast search and find of density peaks via heat diffusion[J].Neurocomputing，2016，208：210-217.