DPC algorithm based on K-reciprocal neighbors and kernel density estimation

ZHOU Yu; XIA Hao; LIU Hongyu; BAI Lei

doi:10.13700/j.bh.1001-5965.2023.0342

Volume 51 Issue 6

Jun. 2025

Turn off MathJax

Article Contents

Journal of Beijing University of Aeronautics and Astronautics > 2025 > 51(6): 1978-1990.

ZHOU Y，XIA H，LIU H Y，et al. DPC algorithm based on K-reciprocal neighbors and kernel density estimation[J]. Journal of Beijing University of Aeronautics and Astronautics，2025，51（6）：1978-1990 （in Chinese） doi: 10.13700/j.bh.1001-5965.2023.0342

Citation:

PDF( 7204 KB)

DPC algorithm based on K-reciprocal neighbors and kernel density estimation

doi: 10.13700/j.bh.1001-5965.2023.0342

School of Electrical Engineering，North China University of Water Resources and Electric Power，Zhengzhou 450045，China

Funds:

National Natural Science Foundation of China (U1504622,31671580); Henan Province Young Backbone Teachers Training Program (2018GGJS079)

More Information

Corresponding author: E-mail：zhouyu_beijing@126.com
Received Date: 12 Jun 2023
Accepted Date: 13 Oct 2023

Available Online: 27 Jun 2025

Publish Date: 20 Oct 2023

Abstract

Abstract

Clustering by fast search and find of density peaks (DPC) algorithm is a density-based clustering algorithm that does not require iteration or too many parameter settings. However, it fails to identify cluster centers with low cluster density because the local structure of data is not considered when computing local density. To solve this problem, a DPC algorithm based on K-reciprocal neighbors (KN) and kernel density estimation (KDE), called KKDPC was proposed. The number of KN and local kernel density of data points were obtained using the k-nearest neighbor and KDE methods. The number of KNs and local kernel density were weighted to obtain the new local density. The relative distance of data points was obtained based on their local density, and cluster centers and non-center points were selected based on the decision graph. Experiments were conducted on artificial and real datasets and compared with seven clustering algorithms including DPC, density-based spatial clustering of applications with noise (DBSCAN), K-means, fuzzy C-means clustering (FCM), DPC based on K nearest neighbors (DPC-KNN) algorithm, DPC with nearest neighbor optimization (DPC-NNO) algorithm, and DPC-FWSN algorithm. The performance of the KKDPC algorithm was verified by calculating the adjusted mutual information (AMI), adjusted Rand index (ARI), and normalized mutual information (NMI). The experimental results show that the proposed KKDPC algorithm can accurately identify cluster centers and improve clustering accuracy effectively.
- clustering algorithm,
- density peak,
- K-nearest neighbor,
- K-reciprocal neighbor,
- kernel density estimation

FullText(HTML)

References(34)

References

[1]	ZUO W D, HOU X M. An improved probability propagation algorithm for density peak clustering based on natural nearest neighborhood[J]. Array, 2022, 15: 100232. doi: 10.1016/j.array.2022.100232
[2]	KHATER I M, NABI I R, HAMARNEH G. A review of super-resolution single-molecule localization microscopy cluster analysis and quantification methods[J]. Patterns, 2020, 1(3): 100038. doi: 10.1016/j.patter.2020.100038
[3]	GRIFFIÉ J, BURN G L, WILLIAMSON D J, et al. Dynamic Bayesian cluster analysis of live-cell single molecule localization microscopy datasets[J]. Small Methods, 2018, 2(9): 1800008. doi: 10.1002/smtd.201800008
[4]	FANG U, LI J X, LU X Q, et al. Robust image clustering via context-aware contrastive graph learning[J]. Pattern Recognition, 2023, 138: 109340. doi: 10.1016/j.patcog.2023.109340
[5]	GUAN J Y, LI S, HE X X, et al. Peak-graph-based fast density peak clustering for image segmentation[J]. IEEE Signal Processing Letters, 2021, 28: 897-901. doi: 10.1109/LSP.2021.3072794
[6]	HU N, TIAN Z H, LU H, et al. A multiple-kernel clustering based intrusion detection scheme for 5G and IoT networks[J]. International Journal of Machine Learning and Cybernetics, 2021, 12(11): 3129-3144. doi: 10.1007/s13042-020-01253-w
[7]	张喜梅, 解滨, 徐童童, 等. 基于反向K近邻和密度峰值初始化的加权Kmeans聚类入侵检测算法[J]. 南京理工大学学报, 2023, 47(1): 56-65. ZHANG X M, XIE B, XU T T, et al. Intrusion detection algorithm based on weighted Kmeans clustering with reverse K-nearest neighbor and density peak initialization[J]. Journal of Nanjing University of Science and Technology, 2023, 47(1): 56-65(in Chinese).
[8]	MACQUEEN J. Some methods for classification and analysis of multivariate observations[J]. Berkeley Symposium on Mathematical Statistics and Probability, 1967, 1: 281-297.
[9]	PARK H S, JUN C H. A simple and fast algorithm for K-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2): 3336-3341. doi: 10.1016/j.eswa.2008.01.039
[10]	GUHA S, RASTOGI R, SHIM K. Cure: an efficient clustering algorithm for large databases[J]. Information Systems, 2001, 26(1): 35-58. doi: 10.1016/S0306-4379(01)00008-4
[11]	ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: an efficient data clustering method for very large databases[J]. ACM SIGMOD Record, 1996, 25(2): 103-114. doi: 10.1145/235968.233324
[12]	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 Second International Conference on Knowledge Discovery and Data Mining. Palo Alto: AAAI Press, 1996: 226-231.
[13]	ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS: ordering points to identify the clustering structure[J]. ACM SIGMOD Record, 1999, 28(2): 49-60. doi: 10.1145/304181.304187
[14]	SHEIKHOLESLAMI G, CHATTERJEE S, ZHANG A D. WaveCluster: a wavelet-based clustering approach for spatial data in very large databases[J]. The VLDB Journal, 2000, 8(3): 289-304.
[15]	WANG W, YANG J, MUNTZ R R. STING: a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd International Conference on Very Large Data Bases. New York: ACM, 1997: 186-195.
[16]	RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496. doi: 10.1126/science.1242072
[17]	DU M J, DING S F, JIA H J. Study on density peaks clustering based on K-nearest neighbors and principal component analysis[J]. Knowledge-Based Systems, 2016, 99: 135-145. doi: 10.1016/j.knosys.2016.02.001
[18]	JIANG D, ZANG W K, SUN R, et al. Adaptive density peaks clustering based on K-nearest neighbor and gini coefficient[J]. IEEE Access, 2020, 8: 113900-113917. doi: 10.1109/ACCESS.2020.3003057
[19]	YUAN X N, 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. doi: 10.1007/s13042-021-01369-7
[20]	XIE J Y, GAO H C, XIE W X, et al. Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J]. Information Sciences, 2016, 354: 19-40. doi: 10.1016/j.ins.2016.03.011
[21]	LIU R, WANG H, YU X M. Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J]. Information Sciences, 2018, 450: 200-226. doi: 10.1016/j.ins.2018.03.031
[22]	陈蔚昌, 赵嘉, 肖人彬, 等. 面向密度分布不均数据的近邻优化密度峰值聚类算法[J]. 控制与决策, 2024, 39(3): 919-928. CHEN W C, ZHAO J, XIAO R B, 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 (in Chinese).
[23]	ZHAO J, WANG G, PAN J S, et al. Density peaks clustering algorithm based on fuzzy and weighted shared neighbor for uneven density datasets[J]. Pattern Recognition, 2023, 139: 109406. doi: 10.1016/j.patcog.2023.109406
[24]	BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York : Plenum Press, 1981.
[25]	DING S F, LI C, XU X, et al. A sampling-based density peaks clustering algorithm for large-scale data[J]. Pattern Recognition, 2023, 136: 109238. doi: 10.1016/j.patcog.2022.109238
[26]	CHENG D D, ZHANG S L, HUANG J L. Dense members of local cores-based density peaks clustering algorithm[J]. Knowledge-Based Systems, 2020, 193: 105454. doi: 10.1016/j.knosys.2019.105454
[27]	KARKKAINEN I, FRANTI P. Dynamic local search algorithm for the clustering problem[M]. Joensuu: University of Joensuu, 2002.
[28]	GIONIS A, MANNILA H, TSAPARAS P. Clustering aggregation[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 4. doi: 10.1145/1217299.1217303
[29]	FU L M, MEDICO E. FLAME, a novel fuzzy clustering method for the analysis of DNA microarray data[J]. BMC Bioinformatics, 2007, 8(1): 3. doi: 10.1186/1471-2105-8-3
[30]	JAIN A K, LAW M H C. Data clustering: a user’s dilemma[M]// Pattern Recognition and Machine Intelligence. Berlin: Springer, 2005: 1-10.
[31]	XU X, DING S F, WANG L J, et al. A robust density peaks clustering algorithm with density-sensitive similarity[J]. Knowledge-Based Systems, 2020, 200: 106028. doi: 10.1016/j.knosys.2020.106028
[32]	CHANG H, YEUNG D Y. Robust path-based spectral clustering[J]. Pattern Recognition, 2008, 41(1): 191-203. doi: 10.1016/j.patcog.2007.04.010
[33]	BACHE K, LICHMAN M. UCI machine learning repository[EB/OL]. (2020-12-04)[2023-02-01]. http://archive.ics.uci.edu/ml.
[34]	SAMARIA F S, HARTER A C. Parameterisation of a stochastic model for human face identification[C]// Proceedings of The IEEE Workshop on Applications of Computer Vision. Piscataway: IEEE Press, 1994: 138-142.

Relative Articles

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(17) / Tables(4)

Get Citation

PDF

XML

Article Metrics

Article views(545) PDF downloads(42)

DPC algorithm based on K-reciprocal neighbors and kernel density estimation

doi: 10.13700/j.bh.1001-5965.2023.0342

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Proportional views

Related

DPC algorithm based on K-reciprocal neighbors and kernel density estimation

doi: 10.13700/j.bh.1001-5965.2023.0342

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Proportional views

Related

Export File

Citation

Format

Content