Adaptive Density Peak Clustering Algorithm Based on Gaussian Distribution

doi:10.19678/j.issn.1000-3428.0068956

Abstract

Abstract:

The Density Peak Clustering (DPC) algorithm excels in diverse fields, is adept at identifying clusters of any shape, and is noise-resistant. However, the algorithm needs help with manual cluster center selection and underperforms on datasets with uneven densities. This paper introduces a novel Gaussian distribution-based adaptive DPC algorithm to overcome these challenges. This approach involves multiplying the local density by the relative distance θ_i and mapping this θ_i into a two-dimensional Gaussian space using Z-score standardization. Uniquely, the algorithm adaptively selects cluster centers based on the standard deviation of the Gaussian distribution and assigns data points to their nearest centers for initial clustering. This paper also introduces a suture factor model to facilitate the merging of similar sub-clusters. When the suture coefficient is greater than the threshold, merge the most similar clusters in the preliminary partition results and update the similarity matrix until the merging process is completed to obtain the final result. The experimental results on artificial and real datasets indicate that compared with DBSCAN algorithm, DPC algorithm, and ICKDC algorithm, the proposed algorithm has higher clustering accuracy and better clustering performance.

Key words: Density Peak Clustering (DPC) algorithm, Gaussian distribution, Z-score standardization, suture factor, inter-cluster similarity

摘要：

密度峰值聚类(DPC)算法可以发现任意形状的簇, 对噪声具有鲁棒性, 因此被广泛应用于各个领域。但DPC算法需要人工选取聚类中心, 对于密度不均匀型数据集表现较差。为此, 提出一种基于高斯分布的自适应密度峰值聚类算法。首先, 计算局部密度和相对距离的乘积θ_i, 通过Z-score标准化方法, 将θ_i映射到符合高斯分布的二维空间中, 利用高斯分布的标准偏差来自适应选取聚类中心, 得到聚类中心集合; 其次, 将其余数据点分配到离其最近的聚类中心所在的簇中, 得到初步划分结果; 最后, 设计缝合因子模型, 计算簇间缝合系数, 当缝合系数大于阈值时合并初步划分结果中最相似簇并更新相似度矩阵, 直至完成合并得到最终结果。在人工数据集和真实数据集上的实验结果表明, 与DBSCAN算法、DPC算法和ICKDC算法对比, 所提算法的聚类准确度更高, 聚类性能更佳。

关键词: 密度峰值聚类算法, 高斯分布, Z-score标准化, 缝合因子, 簇间相似度

LI Qiwen, WANG Zhihe, DU Hui, LU Depeng. Adaptive Density Peak Clustering Algorithm Based on Gaussian Distribution[J]. Computer Engineering, 2025, 51(4): 137-148.

李启文, 王治和, 杜辉, 鲁德鹏. 基于高斯分布的自适应密度峰值聚类算法[J]. 计算机工程, 2025, 51(4): 137-148.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0068956

https://www.ecice06.com/EN/Y2025/V51/I4/137

Figures/Tables 15

Fig.1 Decision diagram for the 2d-20c-no0 dataset

Fig.2 Clustering results of the 2d-20c-no0 dataset

Fig.3 Gaussian distribution fitting results of the flame2 dataset

Fig.4 Inter-cluster sature image of the Aggregation dataset

Fig.5 Inter-cluster stitching of the Twomoons dataset

Fig.6 Clustering result of the Twomoons dataset

Fig.7 Clustering results of different algorithms on datasets

Fig.8 The influence of parameter threshold on the evaluation indicators of GDPC algorithm

Fig.9 The influence of parameter σ on the evaluation indicators of GDPC algorithm

References 24

1	EZUGWU A E , IKOTUN A M , OYELADE O O , et al. A comprehensive survey of clustering algorithms: state-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Engineering Applications of Artificial Intelligence, 2022, 110, 104743. doi: 10.1016/j.engappai.2022.104743
2	张和平, 李俊武. 基于模糊c均值聚类算法的控制图模式识别. 工业工程, 2021, 24 (5): 108- 116.
	ZHANG H P , LI J W . Recognition of control chart patterns using fuzzy c-means algorithm. Industrial Engineering Journal, 2021, 24 (5): 108- 116.
3	MADEIRA S C , OLIVEIRA A L . Bi-clustering algorithms for biological data analysis: a survey. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004, 1 (1): 24- 45. doi: 10.1109/TCBB.2004.2
4	RAFAEL C G , RICHARD E W . Digital image processing. Upper Saddle River, USA: Prentice Hall, 2008.
5	LIU J , PHAM T D , YAN H , et al. Fuzzy mixed-prototype clustering algorithm for microarray data analysis. Neurocomputing, 2018, 276, 42- 54. doi: 10.1016/j.neucom.2017.06.083
6	XU R , WUNSCH D . Survey of clustering algorithms. IEEE Transactions on Neural Networks, 2005, 16 (3): 645- 678. doi: 10.1109/TNN.2005.845141
7	MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. [S. 1. ]: University of California Press, 1967: 281-297.
8	DEMPSTER A P , LAIRD N M , RUBIN D B . Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical, Society Series B: Statistical Methodology, 1977, 39 (1): 1- 22. doi: 10.1111/j.2517-6161.1977.tb01600.x
9	ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 1996: 226-231.
10	RODRIGUEZ A , LAIO A . Clustering by fast search and find of density peaks. Science, 2014, 344 (6191): 1492- 1496. doi: 10.1126/science.1242072
11	位雅, 张正军, 何凯琳, 等. 基于相对密度的密度峰值聚类算法. 计算机工程, 2023, 49 (6): 53- 61. doi: 10.19678/j.issn.1000-3428.0064368
	WEI Y , ZHANG Z J , HE K L , et al. Density peak clustering algorithm based on relative density. Computer Engineering, 2023, 49 (6): 53- 61. doi: 10.19678/j.issn.1000-3428.0064368
12	LI F X , ZHOU M , LI S , et al. A new density peak clustering algorithm based on cluster fusion strategy. IEEE Access, 2022, 10, 98034- 98047. doi: 10.1109/ACCESS.2022.3205742
13	王芙银, 张德生, 肖燕婷. 基于加权共享近邻与累加序列的密度峰值算法. 计算机工程, 2022, 48 (4): 61- 69. doi: 10.19678/j.issn.1000-3428.0060648
	WANG F Y , ZHANG D S , XIAO Y T . Density peak algorithm based on weighted shared nearest neighbor and accumulated sequence. Computer Engineering, 2022, 48 (4): 61- 69. doi: 10.19678/j.issn.1000-3428.0060648
14	XU T F , JIANG J H . A graph adaptive density peaks clustering algorithm for automatic centroid selection and effective aggregation. Expert Systems with Applications, 2022, 195, 116539. doi: 10.1016/j.eswa.2022.116539
15	CHEN D , DU T , ZHOU J , et al. A domain density peak clustering algorithm based on natural neighbor. Intelligent Data Analysis, 2023, 27 (2): 443- 462. doi: 10.3233/IDA-216541
16	ZHOU Z , SI G Q , SUN H D , et al. A robust clustering algorithm based on the identification of core points and KNN kernel density estimation. Expert Systems with Applications, 2022, 195, 116573. doi: 10.1016/j.eswa.2022.116573
17	HOU J, PELILLO M. A new density kernel in density peak based clustering[C]//Proceedings of the 23rd International Conference on Pattern Recognition (ICPR). Washington D.C., USA: IEEE Press, 2016: 468-473.
18	DU H , HAO Y T , WANG Z H . An improved density peaks clustering algorithm by automatic determination of cluster centres. Connection Science, 2022, 34 (1): 857- 873. doi: 10.1080/09540091.2021.2012422
19	张凤荔, 周洪川, 张俊娇, 等. 基于改进凝聚层次聚类的协议分类算法. 计算机工程与科学, 2017, 39 (4): 796- 803.
	ZHANG F L , ZHOU H C , ZHANG J J , et al. A protocol classification algorithm based on improved AGNES. Computer Engineering&Science, 2017, 39 (4): 796- 803.
20	MISHRA G , MOHANTY S K . A fast hybrid clustering technique based on local nearest neighbor using minimum spanning tree. Expert Systems with Application, 2019, 132, 28- 43. doi: 10.1016/j.eswa.2019.04.048
21	WANG Y Z , QIAN J X , HASSAN M , et al. Density peak clustering algorithms: a review on the decade 2014-2023. Expert Systems with Applications, 2023, 238, 121860.
22	VINH N X, EPPS J, BAILEY J. Information theoretic measures for clustering comparison[C]//Proceedings of International Conference on Machine Learning. New York, USA: ACM Press, 2010: 2837-2854.
23	NGUYEN T P Q , KUO R J . Partition-and-merge based fuzzy genetic clustering algorithm for categorical data. Applied Soft Computing, 2019, 75, 254- 264.
24	FOWLKES E B , MALLOWS C L . A method for comparing two hierarchical clusterings. Journal of the American Statistical Association, 1983, 78 (383): 553- 569.

[1]	LU Jiajia, DU Yusong. Constant-time Implementation Method for Discrete Gaussian Sampling on Integer [J]. Computer Engineering, 2020, 46(8): 119-123.
[2]	SONG Ruixia,WANG Meng,WANG Xiaochun. Image Fusion Algorithm Combining V-transform with Contourlet Transform [J]. Computer Engineering, 2017, 43(4): 263-268,276.
[3]	WANG Tiancheng,CAI Yunfei,TANG Zhenmin. SLAM Method Based on Region Particle Swarm Optimization and Partial Gaussian Resampling [J]. Computer Engineering, 2017, 43(11): 310-316.
[4]	LI Yanwei,WANG Xuerui. Improved Algorithm of Decorrelated Target Detection for Polarimetric SAR Images [J]. Computer Engineering, 2016, 42(9): 235-239.
[5]	JIANG Xiaoliang,LI Bailin,DONG Yang,CHEN Shaojie,HE Biao,WANG Qiong. A New Image Segmentation Model of Active Contour [J]. Computer Engineering, 2015, 41(6): 236-239,253.
[6]	ZHANG Mingjie,KANG Baosheng. A Moving Target Detection Method of Two-step Gaussian Mixture Model [J]. Computer Engineering, 2015, 41(10): 245-249.
[7]	LIU Bin, LUO Cong, WEI Meng-ran, HE Liang-hua. Motor Imagery EEG Signal Analysis Based on Bayesian Network [J]. Computer Engineering, 2014, 40(7): 128-132.
[8]	YIN Ming,WANG Zhi-cheng,YU Li-ping. Texture Image Retrieval Based on Nonsubsampled Shearlet Transform and Rotation Invariant Local Phase Quantization [J]. Computer Engineering, 2014, 40(10): 258-263,269.
[9]	MA Man-Fu, NI Wei. Trust Transfer of Cross-domains Mobile Node in Internet of Things [J]. Computer Engineering, 2013, 39(4): 100-104,108.
[10]	CHA Wei, HONG Rong-Gui, FU Jian-Feng, WANG Jing. Automatic Color Equalization Algorithm Based on Human Eye Lateral Inhibition Mechanism [J]. Computer Engineering, 2013, 39(1): 7-11.
[11]	LIU Jian-Wei, CHE Guang-Hui, LUO Xiong-Lin. Online Classification Algorithm Based on Confidence-weighted Learning [J]. Computer Engineering, 2012, 38(9): 180-182.
[12]	HE Tong. CLARANS Clustering Algorithm of Uncertainty Objects [J]. Computer Engineering, 2012, 38(11): 56-58.
[13]	LV Lin-Chao, HE Yu-Feng, YANG Yu-Xiang, HUANG Yuan. Iris Feature Extraction Algorithm Based on Energy Compensation and Feature Weighting [J]. Computer Engineering, 2012, 38(01): 165-167.
[14]	SU Xiao-Jiang, NI Hong, WANG Jin-Lin. Geographical Location-based Partitioning Method for Mobile User Group [J]. Computer Engineering, 2011, 37(20): 13-15.
[15]	ZHANG Jing, HU Li, XU Dao-Wei. Clustering Algorithm Based on Gauss Reputation Model in Sensor Network [J]. Computer Engineering, 2010, 36(17): 169-172.

Please choose a citation manager

Content to export