二阶K近邻和多簇合并的密度峰值聚类算法

doi:10.13229/j.cnki.jdxbgxb.20220779

摘要/Abstract

摘要：

针对流形数据中密度峰值聚类（DPC）算法的局部密度易找到错误的类簇中心，且分配策略易导致远离类簇中心的剩余样本被错误分配的问题，本文提出二阶K近邻和多簇合并的密度峰值聚类（DPC-SKMM）算法。首先，利用最小二阶K近邻定义局部密度，凸显类簇中心与非类簇中心间的密度差异，从而找到正确的类簇中心；其次，利用K近邻找出样本局部代表点并依此确定核心点，用核心点指导微簇划分；最后，利用最小二阶K近邻及共享近邻定义的微簇间吸引度合并微簇，避免远离类簇中心的样本被错误分配，且微簇合并过程无须迭代。本文将DPC-SKMM算法与IDPC-FA、DPCSA、FNDPC、FKNN-DPC、DPC算法进行对比，实验结果表明，DPC-SKMM算法能有效聚类流形及UCI数据集。

关键词: 密度峰值聚类, 流形数据, 二阶K近邻, K近邻, 吸引度, 多簇合并策略

Abstract:

In the face of manifold data， the local density of density peaks clustering （DPC） algorithm is easy to find the wrong cluster center and the allocation strategy is easy to cause the residual samples far from the cluster center to be misallocation. In view of the above problems， this paper proposes density peaks clustering with second-order K-nearest neighbors and multi-cluster merging. Firstly， the minimum second-order K-nearest neighbor is used to define the local density， highlighting the density difference between the cluster center and the non-cluster center， so as to find the correct cluster center； Secondly， the K-nearest neighbor is used to find the local representative points of the sample and determine the core points， and the core points are used to guide the micro-cluster division； Finally， the inter-cluster attraction defined by the minimum second-order K-nearest neighbor and shared nearest neighbor is used to merge the micro-clusters， which avoids the misallocation of samples away from the cluster center， and the micro-cluster merging process does not require iteration. In this paper， DPC-SKMM algorithm is compared with IDPC-FA， DPCSA， FNDPC， FKNN-DPC， DPC algorithm. Experimental results show that DPC-SKMM algorithm can cluster manifolds and UCI data sets effectively.

Key words: density peaks clustering, manifold data, second-order K-nearest neighbors, K-nearest neighbor, attractiveness, multi-cluster merging strategy

中图分类号:

TP301.6

吕莉,朱梅子,康平,韩龙哲. 二阶K近邻和多簇合并的密度峰值聚类算法[J]. 吉林大学学报(工学版), 2024, 54(5): 1417-1425.

Li LYU,Mei-zi ZHU,Ping KANG,Long-zhe HAN. Density peaks clustering with second-order K-nearest neighbors and multi-cluster merging[J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(5): 1417-1425.

图/表 5

表1

表2

图1

表3

表4

参考文献 23

1	Djenouri Y, Belhadi A, Fournier-Viger P, et al. Fast and effective cluster-based information retrieval using frequent closed itemsets[J]. Information Sciences, 2018, 453: 154-167.
2	Zhao H, He C. Objective cluster analysis in value-based customer segmentation method[C]∥Proceedings of the 2nd International Workshop on Knowledge Discovery and Data Mining. Piscataway NJ: IEEE, 2009: 484-487.
3	刘仲民, 李战明, 李博皓, 等. 基于稀疏矩阵的谱聚类图像分割算法[J]. 吉林大学学报: 工学版, 2017, 47(4): 1308-1313.
	Liu Zhong-min, Li Zhan-ming, Li Bo-hao, et al. Spectral clustering image segmentation based on sparse matrix[J]. Journal of Jilin University (Engineering and Technology Edition), 2017, 47(4): 1308- 1313.
4	赵嘉, 姚占峰, 吕莉, 等.基于相互邻近度的密度峰值聚类算法[J]. 控制与决策, 2021, 36(3): 543-552.
	Zhao Jia, Yao Zhan-feng, Li Lyu, et al. Density peaks clustering based on mutual neighbor degree[J]. Control and Decision, 2021, 36(3): 543-552.
5	曲福恒, 潘曰涛, 杨勇,等. 基于加权空间划分的高效全局k-means聚类算法[J/OL]. 吉林大学学报: 工学版,[2024-02-28].
	Qu Fu-heng, Pan Yue-tao, Yang Yong, et al. An efficient global k-means clustering algorithm based on weighted space partitioning[J/OL]. Journal of Jilin University (Engineering and Technology Edition), [2024-02-28].
6	Liew A W C, Yan H, Yang M. Pattern recognition techniques for the emerging field of bioinformatics: a review[J]. Pattern Recognition, 2005, 38(11): 2055-2073.
7	Rodriguez A, Lsio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
8	Wang Y, Yang Y. Relative density-based clustering algorithm for identifying diverse density clusters effectively[J]. Neural Computing and Applications, 2021, 33(16): 10141-10157.
9	Li C, Zhang Y. Density peak clustering based on relative density optimization[J]. Mathematical Problems in Engineering, 2020, 2020: No2816102.
10	赵嘉, 王刚, 吕莉, 等. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730-2737.
	Zhao Jia, Wang Gang, Li Lyu, et al. Density peaks clustering algorithm based on geodesic distance and cosine mutual reverse nearest neighbor for manifold datasets[J]. Acta Electronica Sinica, 2022, 50(11): 2730-2737.
11	Yuan X, Yu H, Liang J, et al. A novel density peaks clustering algorithm based on K nearest neighbors with adaptive merging strategy[J]. International Journal of Machine Learning and Cybernetics, 2021, 12(10): 2825-2841.
12	吴润秀, 尹士豪, 赵嘉, 等. 基于相对密度估计和多簇合并的密度峰值聚类算法[J]. 控制与决策, 2023, 38(4): 1047-1055.
	Wu Run-xiu, Yin Shi-hao, Zhao Jia, et al. Density peaks clustering based on relative density estimating and multi cluster merging[J]. Journal of Control and Decision, 2023, 38(4): 1047-1055.
13	赵嘉, 陈磊, 吴润秀, 等. K近邻和加权相似性的密度峰值聚类算法[J]. 控制理论与应用, 2022, 39(12): 2349-2357.
	Zhao Jia, Chen Lei, Wu Run-xiu, et al. Density peaks clustering based on K-nearest neighbors and weighted similarity[J]. Control Theory & Applications, 2022, 39(12): 2349-2357.
14	Du M, Ding S, Xu X, et al. Density peaks clustering using geodesic distances[J]. International Journal of Machine Learning and Cybernetics, 2018, 9(8): 1335-1349.
15	王大刚, 丁世飞, 钟锦. 基于二阶 k 近邻的密度峰值聚类算法研究[J]. 计算机科学与探索, 2021, 15(8): 1490-1500.
	Wang Da-gang, Ding Shi-fei, 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.
16	Cheng D, Zhang S, Huang J. Dense members of local cores-based density peaks clustering algorithm[J]. Knowledge-Based Systems, 2020, 193: 105454
17	陈蔚昌, 赵嘉, 肖人彬, 等.面向密度分布不均数据的近邻优化密度峰值聚类算法[J].控制与决策, 2024, 39(3): 919-928.
	Chen Wei-chang, Zhao Jia, Xiao Ren-bin, et al. Density peaks clustering algorithm with nearest neighbor optimization for data with uneven density distribution[J]. Control and Decision, 2024, 39(3): 919-928.
18	Zhao J, Tang J, Shi A, et al. Improved density peaks clustering based on firefly algorithm[J]. International Journal of Bio-Inspired Computation, 2020, 15(1): 24-42.
19	Sun L, Liu R, Xu J, et al. An adaptive density peaks clustering method with Fisher linear discriminant[J]. IEEE Access, 2019, 7: 72936-72955.
20	Du M, Ding S, Xue Y. A robust density peaks clustering algorithm using fuzzy neighborhood[J]. International Journal of Machine Learning and Cybernetics, 2018, 9(7): 1131-1140.
21	Cheng D, Zhu Q, Huang J, et al. Natural neighbor-based clustering algorithm with density peeks[C]∥2016 International Joint Conference on Neural Networks, 2016: 92-98.
22	Vinh N X, Epps J, BAILEY J. Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance[J]. The Journal of Machine Learning Research, 2010, 11: 2837-2854.
23	Fowlkes E B, Mallows C L. A method for comparing two hierarchical clusterings[J]. Journal of the American Statistical Association, 1983, 78(383): 553-569.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

算法	AMI	ARI	FMI	Arg-	AMI	ARI	FMI	Arg-
	Db				Circle
DPC-SKMM	1	1	1	17	1	1	1	26
IDPC-FA	0.652 6	0.503 3	0.699 9	-	0.462 9	0.438 5	0.765 2	-
DPCSA	0.413 6	0.109 6	0.468 9	-	0.295 0	0.083 3	0.524 2	-
FNDPC	0.509 8	0.271 4	0.580 3	0.09	0.423 6	0.273 2	0.586 3	0.29
FKNN-DPC	0.510 7	0.271 8	0.579 3	19	0.706 3	0.613 9	0.779 0	32
DPC	0.518 5	0.279 4	0.585 3	4.0	0.359 6	0.301 5	0.604 8	0.3
	Jain				Cmc
DPC-SKMM	1	1	1	6	1	1	1	11
IDPC-FA	1	1	1	-	0.809 3	0.842 1	0.902 7	-
DPCSA	0.216 7	0.216 7	0.216 7	-	0.665 6	0.576 1	0.745 4	-
FNDPC	0.596 1	0.596 1	0.596 1	0.47	0.809 3	0.842 1	0.902 7	0.28
FKNN-DPC	0.709 2	0.709 2	0.709 2	43	1	1	1	49
DPC	0.618 3	0.618 3	0.618 3	0.8	0.385 7	0.266 1	0.537 7	5
	Compound				LineBlobs
DPC-SKMM	0.880 2	0.892 9	0.921 5	8	1	1	1	5
IDPC-FA	0.792 2	0.832 7	0.881 5	-	1	1	1	-
DPCSA	0.839 2	0.828 4	0.870 7	-	1	1	1	-
FNDPC	0.723 9	0.533 7	0.644 0	0.09	0.638 6	0.638 6	0.638 6	0.21
FKNN-DPC	0.838 1	0.841 8	0.887 7	7	1	1	1	7
DPC	0.775 4	0.591 0	0.687 6	4.0	0.837 5	0.837 5	0.837 5	4.2
	Sticks				Spiral
DPC-SKMM	1	1	1	5	1	1	1	4
IDPC-FA	1	1	1	-	1	1	1	-
DPCSA	0.763 4	0.763 4	0.763 4	-	1	1	1	-
FNDPC	1	1	1	0.22	1	1	1	0.07
FKNN-DPC	1	1	1	7	1	1	1	5
DPC	0.809 4	0.809 4	0.809 4	2	1	1	1	1.8

算法	秩均值
算法	AMI	ARI	FMI
DPC-SKMM	5.19	5.19	5.19
IDPC-FA	4.19	4.31	4.31
DPCSA	2.38	2.13	2.13
FNDPC	2.56	2.44	2.56
FKNN-DPC	4.25	4.38	4.25
DPC	2.44	2.56	2.56

算法	AMI	ARI	FMI	Arg-	AMI	ARI	FMI	Arg-
	Iris				Wine
DPC-SKMM	0.878 6	0.903 8	0.935 5	16	0.859 9	0.896 2	0.931 2	7
IDPC-FA	0.862 3	0.885 7	0.923 3	-	0.767 5	0.771 3	0.847 8	-
DPCSA	0.883 1	0.903 8	0.935 5	-	0.748 0	0.741 4	0.828 3	-
FNDPC	0.883 1	0.903 8	0.935 5	0.11	0.789 8	0.802 5	0.868 6	0.26
FKNN-DPC	0.883 1	0.903 8	0.935 5	22	0.848 1	0.883 9	0.922 9	8
DPC	0.860 6	0.885 7	0.923 3	0.2	0.706 5	0.672 4	0.783 5	2
	Seeds				Ecoli
DPC-SKMM	0.789 5	0.835 4	0.889 8	5	0.656 4	0.743 3	0.814 0	2
IDPC-FA	0.729 9	0.767 0	0.844 4	-	0.663 8	0.756 1	0.828 4	-
DPCSA	0.660 9	0.687 3	0.791 8	-	0.440 6	0.459 3	0.646 7	-
FNDPC	0.713 6	0.754 5	0.836 1	0.07	0.483 3	0.561 8	0.717 8	0.35
FKNN-DPC	0.775 7	0.802 4	0.868 2	9	0.587 8	0.589 4	0.702 7	2
DPC	0.729 9	0.767 0	0.844 4	0.7	0.497 8	0.446 5	0.577 5	0.4
	waveform				Libras
DPC-SKMM	0.394 2	0.380 3	0.588 6	23	0.556 4	0.358 8	0.423 7	5
IDPC-FA	0.353 7	0.291 4	0.530 0	-	0.573 3	0.381 6	0.424 7	-
DPCSA	0.251 0	0.223 6	0.532 7	-	0.538 8	0.309 5	0.379 1	-
FNDPC	0.352 1	0.282 6	0.530 6	0.21	0.549 4	0.329 0	0.386 9	0.17
FKNN-DPC	0.323 9	0.267 1	0.524 4	2	0.555 4	0.345 9	0.404 4	10
DPC	0.340 0	0.275 9	0.533 6	3.1	0.535 8	0.319 3	0.371 7	0.3
	Parkinsons				Wdbc
DPC-SKMM	0.243 0	0.413 5	0.820 3	20	0.703 2	0.811 7	0.912 2	26
IDPC-FA	0.215 1	0.363 2	0.819 0	-	0.623 7	0.742 3	0.882 9	-
DPCSA	0.072 8	0.160 1	0.658 2	-	0.336 1	0.377 1	0.759 5	-
FNDPC	0.177 2	0.268 6	0.814 0	7	0.607 6	0.364 5	0.875 8	0.05
FKNN-DPC	0.215 1	0.363 2	0.819 0	0.04	0.642 3	0.761 3	0.889 4	2
DPC	0.247 8	0.125 6	0.618 7	1.2	0.436 6	0.496 4	0.794 1	0.5

算法		秩均值
算法	AMI	ARI	FMI
DPC-SKMM	5.25	5.56	5.56
IDPC-FA	4.13	4.19	3.81
DPCSA	1.75	1.94	2.31
FNDPC	3.13	3.06	3.31
FKNN-DPC	4.19	4.25	4.00
DPC	2.56	2.00	2.00

[1]	翁剑成,魏瑞聪,何寒梅,徐海辉,王晶晶. 基于关联路链组的城市路网短时交通流预测模型[J]. 吉林大学学报(工学版), 2023, 53(11): 3104-3112.
[2]	曹倩,李志慧,陶鹏飞,马永建,杨晨曦. 考虑风险异质特性的路网交通事故风险评估方法[J]. 吉林大学学报(工学版), 2023, 53(10): 2817-2825.
[3]	魏路,高磊,李晋宏,杨建,田玉林. 基于密度峰值聚类的交通控制子区划分方法[J]. 吉林大学学报(工学版), 2023, 53(1): 124-131.
[4]	刘富, 权美静, 王柯, 刘云, 康冰, 韩志武, 侯涛. 仿蝎子振源定位机理的位置指纹室内定位方法[J]. 吉林大学学报(工学版), 2019, 49(6): 2076-2082.
[5]	黄岚, 李玉, 王贵参, 王岩. 基于点距离和密度峰值聚类的社区发现方法[J]. 吉林大学学报(工学版), 2016, 46(6): 2042-2051.