Research of Density Peaks Clustering Algorithm Based on Second-Order k Neighbors

doi:10.3778/j.issn.1673-9418.2102053

Abstract

Abstract:

Clustering by fast search and find of density peaks (DPC) is a new density clustering algorithm proposed in recent years. The core of the algorithm is based on local density and relative distance. By drawing a decision diagram, the cluster center is selected manually, and the clustering is completed. The DPC algorithm uses the cutoff distance to calculate the local density, and essentially only considers the number of neighboring nodes around it, and the algorithm uses a single-step allocation strategy, which limits the accuracy and effectiveness of the algorithm for any data set to a certain extent. To solve the above problems, this paper proposes an optimized density peaks clus-tering algorithm based on second-order k neighbors (SODPC). The algorithm calculates direct density and indirect density by introducing second-order k neighbors of nodes, redefines the calculation method of local density, and on this basis, it defines the multi-step allocation strategy of non-central nodes to complete the clustering. Through manual and real data tests, it is proven that the algorithm in this paper has a good clustering effect on irregular and uneven density data sets.

Key words: density peaks clustering, decision graph, second-order k neighbor, local density

摘要：

密度峰值聚类（DPC）是近年来提出的一种新的密度聚类算法，算法的核心是基于局部密度和相对距离，通过画出决策图，人为选定聚类中心，进而完成聚类。DPC算法利用截断距离计算局部密度，本质上只考虑了周围近邻节点的数量，且算法采用单步分配策略，一定程度上限制了算法对任意数据集的计算精度和有效性。针对上述问题，提出基于二阶[k]近邻的密度峰值聚类算法（SODPC）。算法通过引入节点的二阶[k]近邻，计算直接密度和间接密度，重新定义局部密度的计算方式。在此基础上，定义非中心节点的多步骤分配策略完成聚类。通过人工和真实数据的测试，证明了该算法对不规则、密度不均匀的数据集具有较好的聚类效果。

关键词: 密度峰值聚类, 决策图, 二阶[k]近邻, 局部密度

WANG Dagang, DING Shifei, ZHONG Jin. Research of Density Peaks Clustering Algorithm Based on Second-Order k Neighbors[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(8): 1490-1500.

王大刚, 丁世飞, 钟锦. 基于二阶[k]近邻的密度峰值聚类算法研究[J]. 计算机科学与探索, 2021, 15(8): 1490-1500.

References

[1] JOHNSON S C. Hierarchical clustering schemes[J]. Psycho-metrika, 1967, 32(3): 241-254.
[2] JOHNSON A E, JOHNSON A S. K-means and temporal vari-ability in Kansas City Hopewell Ceramics[J]. American Antiquity, 1975, 40(3): 283-295.
[3] GUO S, WANG K, KANG H, et al. Bin loss for hard exudates segmentation in fundus images[J]. Neurocomputing, 2020, 392: 314-324.
[4] ZHOU A T, ZHOU S G, CAO J, et al. Approaches for scaling DBSCAN algorithm to large spatial databases[J]. Journal of Computer Science & Technology, 2000, 15(6): 509-526.
[5] CHEN Y W, SHEN L L, ZHONG C M, et al. A review of density peak clustering algorithms[J]. Journal of Computer Research and Development, 2020, 57(2): 378-394.
陈叶旺, 申莲莲, 钟才明, 等. 密度峰值聚类算法研究综述[J]. 计算机研究与发展, 2020, 57(2): 378-394.
[6] XIA S Y, PENG D W, MENG D Y, et al. A fast adaptive k-means with no bounds[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020: 1-13.
[7] BU F Y, ZHANG Q C, YANG L T, et al. An edge-cloud-aided high-order possibilistic c-means algorithm for big data clus-tering[J]. IEEE Transactions on Fuzzy Systems, 2020, 28(12): 3100-3109.
[8] ABE K, MINOURA K, MAEDA Y, et al. Model-based clus-tering for flow and mass cytometry data with clinical infor-mation[J]. BMC Bioinformatics, 2020, 21(13): 393.
[9] ISLAM M Z, ESTIVILL-CASTRO V, RAHMAN M A, et al. Combining K-means and a genetic algorithm through a novel arrangement of genetic operators for high quality clustering[J]. Expert Systems with Application, 2018, 91: 402-417.
[10] RODRIGUEZ A, LAIO A. Clustering by fast search and ?nd of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[11] DING S F, XU X, WANG Y R. Density peak clustering algorithm based on dissimilarity measure optimization[J]. Journal of Software, 2020, 31(11): 3321-3333.
丁世飞, 徐晓, 王艳茹. 基于不相似性度量优化的密度峰值聚类算法[J]. 软件学报, 2020, 31(11): 3321-3333.
[12] DU M J, DING S F, XU X, et al. Density peaks clustering using geodesic distances[J]. Machine Learning and Cyber-netics, 2018, 9(8): 1335-1349.
[13] LIU R, WANG H, YU X M. Shared-nearest-neighbor- based clustering by fast search and find of density peaks[J]. Infor-mation Sciences, 2018, 450: 200-226.
[14] 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.
[15] JIANG J H, CHEN Y J, HAO D H, et al. DPC-LG: density peaks clustering based on logistic distribution and gravita-tion[J]. Physica A: Statistical Mechanics and Its Applica-tions, 2018, 514: 25-35.
[16] SUN L P, TAO T, ZHENG X Y, et al. Combining density peaks clustering and gravitational search method to enhance data clustering[J]. Engineering Applications of Artifical Inte-lligence, 2019, 85: 865-873.
[17] WANG F Y, ZHANG D S, ZHANG X. Adaptive density peak clustering algorithm combined with whale optimization algorithm[J]. Computer Engineering and Applications, 2021, 57(3): 94-102.
王芙银, 张德生, 张晓. 结合鲸鱼优化算法的自适应密度峰值聚类算法[J]. 计算机工程与应用, 2021, 57(3): 94-102.
[18] JIA L, ZHANG D S, LV D D. Physics-optimized density peak clustering algorithm[J]. Computer Engineering and App-lications, 2020, 56(13): 47-53.
贾露, 张德生, 吕端端. 物理学优化的密度峰值聚类算法[J]. 计算机工程与应用, 2020, 56(13): 47-53.
[19] YANG X H, ZHU Q P, HUANG Y J, et al. Parameter-free Laplacian centrality peaks clustering[J]. Pattern Recogni-tion Letters, 2017, 100: 167-173.
[20] GAO S, MA J, CHEN Z M, et al. Ranking the spreading ability of nodes in complex networks based on local struc-ture[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 403: 130-147.
[21] QI X Q, FULLER E, LUO R, et al. A novel centrality method for weighted networks based on the Kirchhoff polynomial[J]. Pattern Recognition Letters, 2015, 58: 51-60.