面向流形数据的自然近邻图优化和微簇合并密度峰值聚类算法

doi:10.13229/j.cnki.jdxbgxb.20250043

Abstract

Abstract:

Density Peak Clustering algorithm faces challenges in detecting density peaks in manifold data， and its assignment strategy often misallocates samples far from density peaks. To address these issues， this paper proposes a Natural Neighbor Graph Optimization and Micro-Cluster Merging Density Peak Clustering algorithm for manifold data. First， based on the natural neighbor graph， a novel local density measurement method is designed using geodesic distances between vertices， which accurately characterizes the internal structure and distribution properties of manifold data. Second， by analyzing the connection relationships between vertices in the natural neighbor graph， the algorithm automatically identifies representative samples and determines local cores to guide micro-cluster partitioning. Finally， a new similarity measurement criterion for micro-clusters is defined based on geodesic distances between samples， which optimizes clustering performance throughmicro-cluster merging. The proposed algorithm is compared with four improved density peaks clustering algorithms and the original density peaks clustering algorithm. Experimental results show that the proposed algorithm can be effectively applied to clustering analysis of manifold data and real-world datasets.

Key words: density peak clustering, clustering algorithm, manifold data, natural neighbor graph, geodesic distance, micro-cluster merging

CLC Number:

TP311

Jia ZHAO,Chao-fan HE,Ren-bin XIAO,Tang-huai FAN,Zheng-xiang PAN. Density peaks clustering algorithm based on natural neighbor graph optimization and micro-cluster merging for manifold data[J].Journal of Jilin University(Engineering and Technology Edition), 2026, 56(8): 2219-2228.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Table 1

Table 2

Fig.4

Fig.5

Fig.6

Table 3

Table 4

References 28

[1]	Nan F, Tang Y, Yang P, et al. A novel sub-Kmeans based on co-training approach by transforming single-view into multi-view[J]. Future Generation Computer Systems, 2021, 125: 831-843.
[2]	Hou J, Lin H, Yuan H, et al. Flexible density peak clustering for real-world data[J]. Pattern Recognition, 2024, 156: 110772.
[3]	Gagniere S, Han Y, Chen Y, et al. A robust grid‐based meshing algorithm for embedding self‐intersecting surfaces[J]. Computer Graphics Forum, 2024, 43(1): e14986.
[4]	Wang F, Li L, Liu Z. Stratification-based semi-supervised clustering algorithm for arbitrary shaped datasets[J]. Information Sciences, 2023, 639: 119004.
[5]	谢坤,董宏辉,卢玲玉,等. 基于CFSFDP-BP的车辆出行群体分类及识别方法[J]. 吉林大学学报: 工学版, 2026, 56(3): 725-733.
	Xie Kun, Dong Hong-hui, Lu Ling-yu, et al. Classification and recognition method of vehicle travel groups based on CFSFDP-BP[J]. Journal of Jilin University (Engineering and Technology Edition),2026, 56(3): 725-733.
[6]	Kim B, Yuvaraj N, Tse K T, et al. Pressure pattern recognition in buildings using an unsupervised machine-learning algorithm[J]. Journal of Wind Engineering and Industrial Aerodynamics, 2021, 214: 104629.
[7]	Corneo E, Garbelotto R, Prestes G, et al. Coagulation biomarkers and coronavirus disease 2019 phenotyping: a prospective cohort study[J]. Thrombosis Journal, 2023, 21(1): 80.
[8]	Chang J Q, Yu F S. Design matrix factorization and knowledge-guided clustering for trust-aware cross-domain recommendation systems[C]∥7th International Conference on Software Engineering and Computer Science,Taicang, China, 2025: 1-6.
[9]	Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344: 1492-1496.
[10]	Xiong J, Zang W, Zhao Y, et al. Density peaks clustering algorithm with connected local density and punished relative distance[J]. The Journal of Supercomputing, 2024, 80(5): 6140-6168.
[11]	Wang Y. McDPC: multi-center density peak clustering[J]. Neural Computing and Applications, 2020, 32(17): 13465-13478.
[12]	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.
[13]	Xie J, Jiang W, Ding L. Clustering by searching density peaks via local standard deviation[C]∥International conference on Intelligent Data Engineering and Automated Learning, Guilin, China, 2017: 295-305.
[14]	吕莉, 朱梅子, 康平, 等. 面向分布不均数据的混合近邻密度峰值聚类算法[J]. 控制理论与应用, 2024, 41(10): 1821-1830.
	Lv Li, Zhu Mei-zi, Kang Ping, et al. Multiplex neighbor density peaks clustering for uneven density data sets[J]. Control Theory & Applications, 2024, 41(10): 1821-1830.
[15]	Chen J, Yu P S. A domain adaptive density clustering algorithm for data with varying density distribution[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(6): 2310-2321.
[16]	Zhang S, Li K. A novel density peaks clustering algorithm with isolation kernel and k-induction[J]. Applied Sciences, 2022, 13(1): 322.
[17]	Li Y, Sun L, Tang Y. DPC-DNG: Graph-based label propagation of k-nearest higher-density neighbors for density peaks clustering[J].Applied Soft Computing,2024,161: 111773.
[18]	赵嘉, 陈磊, 吴润秀, 等. K近邻和加权相似性的密度峰值聚类算法[J]. 控制理论与应用, 2022, 39(12): 2349-2357.
	Zhao Jia, Chen Lei, Wu Run-xiu, et al. Density peaks clustering algorithm with K-nearest neighbors and weighted similarity[J]. Control Theory & Applications, 2022, 39(12): 2349-2357.
[19]	Zang W, Liu X, Ma L, et al. DPC-MFP: an adaptive density peaks clustering algorithm with multiple feature points[J]. Neurocomputing, 2025, 618: 129060.
[20]	Du M. Density peaks clustering using geodesic distances[J]. International Journal of Machine Learning and Cybernetics, 2018, 9(8): 1335-1349.
[21]	Zhang D, Wang Y, Zhou L, et al. Multimodal classification of Alzheimer's disease and mild cognitive impairment[J]. NeuroImage, 2011, 55(3): 856-867.
[22]	Sahraeian R, Van Compernolle D. Crosslingual and multilingual speech recognition based on the speech manifold[J]. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2017, 25(12): 2301-2312.
[23]	Ding S, Li C, Xu X, et al. A sampling-based density peaks clustering algorithm for large-scale data[J]. Pattern Recognition, 2023, 136: 109238.
[24]	Guo W, Wang W, Zhao S, et al. Density peak clustering with connectivity estimation[J]. Knowledge-Based Systems, 2022, 243: 108501.
[25]	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.
[26]	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.
[27]	Vinh N X, Epps J, Bailey J. Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance[J]. Journal of Machine Learning Research, 2010, 11: 2837-2854.
[28]	Fowlkes E B, Mallows C L. A method for comparing two hierarchical clusterings[J]. Journal of the American Statistical Association, 1983, 78: 553-569.

Related Articles 15

[1]	Zhou-zhou LIU,Cong JIN,Guang-yi JIANG,Nan JIA,Chao LIU,Yang-mei ZHANG. Traffic anomaly detection in wireless sensor networks based on deep learning [J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(8): 2201-2209.
[2]	Qi-liang ZHU,Xue-ting YU. k⁃prototype clustering algorithm and privacy protection for sensitive data republishing under relative entropy [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(3): 1009-1014.
[3]	Xi-jun ZHANG,Guang-jie YU,Yong CUI,Ji-yang SHANG. Short-term traffic flow prediction based on clustering algorithm and graph neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(6): 1593-1600.
[4]	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]	Zhuang-zhuang LIU,Wen-qing ZHENG,Jian ZHENG,Yi-zheng LI,Peng-yu JI,Ai-min SHA. Pavement surface temperature monitoring method based on gridding approach [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(6): 1746-1755.
[6]	Yao-long KANG,Li-lu FENG,Jing-an ZHANG,Su-e CAO. Fast outlier mining algorithm in uncertain data set based on spectral clustering [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(4): 1181-1186.
[7]	Jian-cheng WENG,Rui-cong WEI,Han-mei HE,Hai-hui XU,Jing-jing WANG. Urban road network short-term traffic flow prediction model based on associated road chain group [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(11): 3104-3112.
[8]	Si-bao WANG,Zhong-zheng GUO,Chi MA,Shi-long WANG. Thermal-force deformation analysis and prediction modeling of CNC gear hobbing machine workbench [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(10): 2761-2772.
[9]	Lu WEI,Lei GAO,Jin-hong LI,Jian YANG,Yu-lin TIAN. Traffic sub⁃area division method based on density peak clustering [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(1): 124-131.
[10]	Yao-long KANG,Li-lu FENG,Jing-an ZHANG,Fu CHEN. Outlier mining algorithm for high dimensional categorical data streams based on spectral clustering [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(6): 1422-1427.
[11]	Meng-su ZHANG,Chun-tian LIU,Xi-jin LI,Yong-ping HUANG. Design of fuzzy comprehensive evaluation system for performance appraisal based on K⁃means clustering algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(5): 1851-1856.
[12]	SUN Zong-yuan, FANG Shou-en. Hierarchical clustering algorithm of moving vehicle trajectories in entrances and exits freeway [J]. 吉林大学学报(工学版), 2017, 47(6): 1696-1702.
[13]	LIU Li, LIU Ping-ping, WEI Jia. Semi-supervised dimensionality reduction algorithm applying in face data with side information [J]. 吉林大学学报(工学版), 2011, 41(增刊1): 189-193.
[14]	ZHANG Rui-Hua, CHENG He-You, JIA Zhi-Beng. Energyefficient clustering algorithm for wireless sensor networks [J]. 吉林大学学报(工学版), 2010, 40(06): 1663-1667.
[15]	LI Min, WANG Jian-Xin, CHEN Jian-Er. Distance measure based algorithm for identification of protein complexes [J]. 吉林大学学报(工学版), 2010, 40(05): 1318-1323.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

算法	LineBlobs				Pathbase
算法	ARI	AMI	FMI	Arg-	ARI		AMI	FMI	Arg-
DPC-NGMM	1	1	1	2	0.990 5		0.983 0	0.993 7	2
SDPC	0.541 9	0.623 0	0.699 9	0.1	0.484 3		0.522 1	0.666 6	0.1
DPC-CE	1	1	1	-	0.473 8		0.486 4	0.693 8	-
IDPC-FA	1	1	1	-	0.859 3		0.844 2	0.906 7	-
DPCSA	1	1	1	-	0.613 3		0.707 3	0.751 1	-
DPC	0.823 7	0.837 5	0.884 2	4.2	0.508 2		0.557 3	0.684 8	0.4
算法	Jain				Compound
算法	ARI	AMI	FMI	Arg-	ARI		AMI	FMI	Arg-
DPC-NGMM	1	1	1	4	0.905 6		0.882 2	0.930 2	10
SDPC	1	1	1	0.1	0.702 2		0.707 4	0.782 1	0.1
DPC-CE	1	1	1	-	0.808 2		0.614 1	0.706 0	-
IDPC-FA	1	1	1	-	0.832 7		0.792 2	0.881 5	-
DPCSA	0.044 2	0.216 7	0.592 4	-	0.828 4		0.839 2	0.870 7	-
DPC	0.714 6	0.618 3	0.881 9	0.8	0.636 2		0.825 0	0.723 6	4.6
算法	Db				Cmc
算法	ARI	AMI	FMI	Arg-	ARI	AMI		FMI	Arg-
DPC-NGMM	1	1	1	7	1		1	1	7
SDPC	0.396 1	0.544 1	0.641 4	0.1	0.638 5		0.563 2	0.785 8	0.1
DPC-CE	0.675 8	0.558 8	0.739 5	-	0.669 4		0.736 2	0.835 2	-
IDPC-FA	0.503 3	0.652 6	0.699 9	-	0.842 1		0.809 3	0.902 7	-
DPCSA	0.109 6	0.413 6	0.468 9	-	0.576 1		0.665 6	0.745 4	-
DPC	0.279 4	0.518 5	0.585 3	4	0.266 1		0.385 7	0.537 7	5
算法	Cth3				Ls
算法	ARI	AMI	FMI	Arg-	ARI	AMI		FMI	Arg-
DPC-NGMM	0.997 1	0.994 8	0.997 9	10	1		1	1	11
SDPC	0.471 5	0.652 8	0.620 4	0.1	0.589 2		0.669 7	0.702 3	0.1
DPC-CE	0.825 5	0.715 8	0.793 5	-	0.743 5		0.639 2	0.741 5	-
IDPC-FA	0.832 7	0.875 8	0.878 6	-	0.627 4		0.707 6	0.732 5	-
DPCSA	0.653 8	0.789 1	0.754 7	-	0.599 9		0.725 2	0.712 9	-
DPC	0.513 5	0.686 6	0.647 3	0.1	0.689 4		0.766 5	0.777 9	0.9
算法	Circle3				Complex9
算法	ARI	AMI	FMI	Arg-	ARI	AMI		FMI	Arg-
DPC-NGMM	1	1	1	16	1		1	1	16
SDPC	0.146 2	0.221 7	0.483 4	0.1	0.556 1		0.679 7	0.638 9	0.1
DPC-CE	0.529 0	0.255 5	0.627 9	-	0.461 5		0.695 8	0.552 7	-
IDPC-FA	0.438 5	0.462 9	0.765 2	-	0.957 7		0.951 3	0.965 8	-
DPCSA	0.083 3	0.295	0.524 2	-	0.422 1		0.682 1	0.518 8	-
DPC	0.301 5	0.359 6	0.604 8	0.3	0.609 4		0.740 2	0.683 9	2

算法	ARI	AMI	FMI
DPC-NGMM	5.70	5.70	5.70
SDPC	2.25	1.95	2.15
DPC-CE	3.80	2.80	3.60
IDPC-FA	4.50	4.50	4.60
DPCSA	2.35	3.15	2.45
DPC	2.40	2.90	2.50

算法	Iris					Seeds
算法	ARI	AMI		FMI	Arg-	ARI	AMI	FMI	Arg-
DPC-NGMM	0.883 1		0.852 5	0.921 6	3	0.775 5	0.732 4	0.849 8	35
SDPC	0.885 7		0.862 3	0.923 3	0.1	0.765 7	0.721 5	0.843 2	0.1
DPC-CE	0.663 4		0.727 7	0.782 4	-	0.744 8	0.714 4	0.829 7
IDPC-FA	0.885 7		0.862 3	0.923 3	-	0.767	0.729 9	0.844 4	-
DPCSA	0.903 8		0.883 1	0.935 5	-	0.687 3	0.660 9	0.791 8	-
DPC	0.903 8		0.883 1	0.935 5	3.2	0.767	0.729 8	0.844 4	0.7
算法	Wine					Ecoli
算法	ARI	AMI		FMI	Arg-	ARI	AMI	FMI	Arg-
DPC-NGMM	0.864 9		0.819 7	0.910 3	26	0.757 8	0.675 0	0.834 3	4
SDPC	0.870 8		0.855 0	0.914 0	0.1	0.679 9	0.574 22	0.762 26	0.1
DPC-CE	0.536 2		0.584 1	0.694 5	-	0.114 5	0.070 4	0.580 2	-
IDPC-FA	0.771 3		0.767 5	0.847 8	-	0.756 1	0.663 8	0.828 4	-
DPCSA	0.741 4		0.748 0	0.828 3	-	0.459 3	0.440 6	0.646 7	-
DPC	0.770 3		0.769 5	0.847 4	2.4	0.410 9	0.522 3	0.554 5	2.1
算法	Iononsphere					Libras
算法	ARI	AMI		FMI	Arg-	ARI	AMI	FMI	Arg-
DPC-NGMM	0.419 5		0.305 4	0.760 3	11	0.386 5	0.583 5	0.435 8	11
SDPC	0.217 6		0.150 4	0.627 7	0.1	0.255 7	0.451 0	0.308 4	0.1
DPC-CE	0.114 5		0.070 4	0.580 2	-	0.353 1	0.557 0	0.419 2	-
IDPC-FA	0.218 3		0.135 5	0.643 2	-	0.381 6	0.573 3	0.424 7	-
DPCSA	0.213 5		0.133 5	0.639 0	-	0.309 5	0.538 8	0.379 1	-
DPC	0.230 6		0.148 4	0.644 9	1.8	0.362 6	0.583 2	0.419 0	0.5
算法	WDBC					Waveform
算法	ARI	AMI		FMI	Arg-	ARI	AMI	FMI	Arg-
DPC-NGMM	0.811 4		0.704 3	0.913 0	6	0.319 6	0.367 3	0.574 4	55
SDPC	0.773 0		0.676 4	0.897 7	0.1	0.356 1	0.364 8	0.593 8	0.1
DPC-CE	0.435 5		0.374 2	0.774 3	-	0.283 6	0.327 4	0.545 6	-
IDPC-FA	0.773 0		0.676 4	0.897 7	-	0.311 4	0.295 6	0.533 1	-
DPCSA	0.377 1		0.336 1	0.759 5	-	0.223 6	0.251 0	0.532 7	-
DPC	0.754 8		0.637 5	0.887 6	0.7	0.269 8	0.326 1	0.529 2	0.1

算法	ARI	AMI	FMI
DPC-NGMM	5.25	5.38	5.25
SDPC	3.94	4.06	3.81
DPC-CE	2.06	2.25	2.44
IDPC-FA	3.81	3.19	3.69
DPCSA	2.19	2.06	2.44
DPC	3.75	4.06	3.38

Density peaks clustering algorithm based on natural neighbor graph optimization and micro-cluster merging for manifold data

RICH HTML

PDF (PC)