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

doi:10.13229/j.cnki.jdxbgxb.20220779

Abstract

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

CLC Number:

TP301.6

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.

Figures/Tables 5

Table 1

Table 2

Fig.1

Table 3

Table 4

References 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

Comments

Recommended 0

No Suggested Reading articles found!

算法	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]	Qian CAO,Zhi-hui LI,Peng-fei TAO,Yong-jian MA,Chen-xi YANG. Traffic accident risk assessment method for road network considering risk heterogeneity [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(10): 2817-2825.
[2]	Kai LU,Wei WU,Guan-rong LIN,Xin TIAN,Jian-min XU. Combination forecasting model for number of assembling passengers at transportation terminal based on KNN regression algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1241-1250.
[3]	Fu LIU, Mei-jing QUAN, Ke WANG, Yun LIU, Bing KANG, Zhi-wu HAN, Tao HOU. Indoor positioning method based on location fingerprinting of imitating mechanism of scorpion vibration source [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(6): 2076-2082.
[4]	HUANG Lan, LI Yu, WANG Gui-shen, WANG Yan. Community detection method based on vertex distance and clustering of density peaks [J]. 吉林大学学报(工学版), 2016, 46(6): 2042-2051.

Density peaks clustering with second-order K-nearest neighbors and multi-cluster merging

RICH HTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 5

References 23

Related Articles 4

Metrics

Comments

Recommended 0