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

doi:10.13229/j.cnki.jdxbgxb.20250043

吉林大学学报(工学版) ›› 2026, Vol. 56 ›› Issue (8): 2219-2228.doi: 10.13229/j.cnki.jdxbgxb.20250043

• 计算机科学与技术 • 上一篇

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

赵嘉^1,²(),何超凡^1,²,肖人彬³,樊棠怀^1,²,潘正祥⁴

^1.江西水利电力大学信息工程学院，南昌 330099
^2.江西省水利大数据智能处理与预警技术工程研究中心，南昌 330099
^3.华中科技大学人工智能与自动化学院，武汉 430074
^4.南京信息工程大学人工智能学院，南京 210044

收稿日期:2025-01-13 出版日期:2026-08-01 发布日期:2026-09-02
作者简介:赵嘉（1981-），男，教授，博士. 研究方向：智能计算与计算智能，模式识别，大数据挖掘.E-mail： zhaojia@juwp.edu.cn
基金资助:
国家自然科学基金项目(62466037);国家自然科学基金项目(62463021);国家自然科学基金项目(52069014)

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

Jia ZHAO^1,²(),Chao-fan HE^1,²,Ren-bin XIAO³,Tang-huai FAN^1,²,Zheng-xiang PAN⁴

^1.School of Information Engineering，Jiangxi University of Water Resources and Electric Power，Nanchang 330099，China
^2.Jiangxi Province Engineering Research Center for Intelligent Processing and Early Warning Technology of Water Conservancy Big Data，Nanchang 330099，China
^3.School of Artificial Intelligence and Automation，Huazhong University of Science and Technology，Wuhan 430074，China
^4.School of Artificial Intelligence，Nanjing University of Information Science and Technology，Nanjing 210044，China

Received:2025-01-13 Online:2026-08-01 Published:2026-09-02

摘要/Abstract

摘要：

针对密度峰值聚类算法难以发现流形数据的密度峰值；分配策略易将远离密度峰值的样本错误分配的问题，提出一种面向流形数据的自然近邻图优化和微簇合并密度峰值聚类算法。首先，基于自然近邻图，利用顶点间的测地距离设计了一种新的局部密度度量方法，精准刻画流形数据的内部结构与分布特性；其次，通过分析自然近邻图中顶点的连接关系，自动识别样本代表并确定局部核心，用以指导微簇划分；最后，利用样本间测地距离定义一种新的微簇间相似性度量准则，用以指导微簇合并，从而优化聚类效果。将该算法与4个改进密度峰值聚类算法以及密度峰值聚类算法进行对比，实验结果表明，本文算法能有效应用于流形数据和真实数据的聚类分析当中。

关键词: 密度峰值聚类, 聚类算法, 流形数据, 自然近邻图, 测地距离, 微簇合并

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

中图分类号:

TP311

赵嘉,何超凡,肖人彬,樊棠怀,潘正祥. 面向流形数据的自然近邻图优化和微簇合并密度峰值聚类算法[J]. 吉林大学学报(工学版), 2026, 56(8): 2219-2228.

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.

图/表 10

图 1

图 2

图 3

表1

表2

图4

图5

图6

表3

表4

参考文献 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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

算法	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)

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 28

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	刘洲洲,金聪,蒋光毅,贾楠,刘超,张杨梅. 基于深度学习的无线传感器网络流量异常检测[J]. 吉林大学学报(工学版), 2026, 56(8): 2201-2209.
[2]	谢坤,董宏辉,卢玲玉,耿庆桥,李鹏辉,董春娇. 基于CFSFDP-BP的车辆出行群体分类及识别方法[J]. 吉林大学学报(工学版), 2026, 56(3): 725-733.
[3]	朱齐亮,余雪婷. k-prototype聚类算法和相对熵下敏感数据重发布隐私安全保护[J]. 吉林大学学报(工学版), 2025, 55(3): 1009-1014.
[4]	张玺君,余光杰,崔勇,尚继洋. 基于聚类算法和图神经网络的短时交通流预测[J]. 吉林大学学报(工学版), 2024, 54(6): 1593-1600.
[5]	吕莉,朱梅子,康平,韩龙哲. 二阶K近邻和多簇合并的密度峰值聚类算法[J]. 吉林大学学报(工学版), 2024, 54(5): 1417-1425.
[6]	刘状壮,郑文清,郑健,李轶峥,季鹏宇,沙爱民. 基于网格化的路表温度感知技术[J]. 吉林大学学报(工学版), 2023, 53(6): 1746-1755.
[7]	康耀龙,冯丽露,张景安,曹素娥. 基于谱聚类的不确定数据集中快速离群点挖掘算法[J]. 吉林大学学报(工学版), 2023, 53(4): 1181-1186.
[8]	翁剑成,魏瑞聪,何寒梅,徐海辉,王晶晶. 基于关联路链组的城市路网短时交通流预测模型[J]. 吉林大学学报(工学版), 2023, 53(11): 3104-3112.
[9]	曹倩,李志慧,陶鹏飞,马永建,杨晨曦. 考虑风险异质特性的路网交通事故风险评估方法[J]. 吉林大学学报(工学版), 2023, 53(10): 2817-2825.
[10]	王四宝,郭忠政,马驰,王时龙. 数控滚齿机工作台热-力变形分析及预测建模[J]. 吉林大学学报(工学版), 2023, 53(10): 2761-2772.
[11]	毛伊敏,顾森晴. 基于MapReduce与优化布谷鸟算法的并行密度聚类算法[J]. 吉林大学学报(工学版), 2023, 53(10): 2909-2916.
[12]	魏路,高磊,李晋宏,杨建,田玉林. 基于密度峰值聚类的交通控制子区划分方法[J]. 吉林大学学报(工学版), 2023, 53(1): 124-131.
[13]	康耀龙,冯丽露,张景安,陈富. 基于谱聚类的高维类别属性数据流离群点挖掘算法[J]. 吉林大学学报(工学版), 2022, 52(6): 1422-1427.
[14]	张萌谡,刘春天,李希今,黄永平. 基于K⁃means聚类算法的绩效考核模糊综合评价系统设计[J]. 吉林大学学报(工学版), 2021, 51(5): 1851-1856.
[15]	孙宗元, 方守恩. 高速公路出入口运动车辆轨迹分层聚类算法[J]. 吉林大学学报(工学版), 2017, 47(6): 1696-1702.