Document Type : Research Note

Authors

Department of Computer Engineering, Shahid Bahonar University of Kerman, Iran

Abstract

Clustering datasets with varying densities is challenging because classical Density Peak Clustering (DPC) may fail to identify valid centers in sparse regions and may incorrectly assign sparse samples to dense clusters. To address this issue, this paper proposes a Density Peak Clustering algorithm based on Fuzzy Shared Nearest Neighbors (DPC-FSNN). The proposed method combines k-nearest neighbors and fuzzy neighborhood information to construct a fuzzy nearest neighbor kernel for adaptive local density estimation. It also incorporates shared nearest neighbor information into the local distance computation and sample assignment process to improve center detection and assignment reliability. Experiments on varying-density datasets (e.g., Jain, Compound, and LineBlobs), complex-shape datasets, and real-world datasets are evaluated using AMI, ARI, and FMI. The results show that DPC-FSNN achieves competitive and often superior clustering performance compared with IDPC-FA, FKNN-DPC, DPC-FWSN, DPCSA, FNDPC, and the classical DPC algorithm. A computational complexity analysis is also provided, showing that the proposed method has overall complexity O(n^2) in the standard implementation.

Keywords

Main Subjects

[1] M. Ghazizadeh-Ahsaee, H. Sadoghi-Yazdi, and M. Naghibzadeh, "Curve fitting space for classification, " Neural Computing and Applications, vol. 20, no. 2, pp. 273–285, 2011.
[2] K. J. Cios, W. Pedrycz, R. W. Swiniarski, and L. A. Kurgan, Data Mining: A Knowledge Discovery Approach. New York, NY, USA: Springer, 2007.
[3] A. Rodriguez and A. Laio, "Clustering by fast search and find of density peaks, " Science, vol. 344, no. 6191, pp. 1492–1496, 2014.
[4] A. Lotfi, P. Moradi, and H. Beigy, "Density peaks clustering based on density backbone and fuzzy neighborhood, " Pattern Recognition, vol. 107, Art. no. 107449, 2020.
[5] K. Qiao, J. Chen, and S. Duan, "Self-adaptive two-stage density clustering method with fuzzy connectivity, " Applied Soft Computing, vol. 154, Art. no. 111355, 2024.
[6] J. Xie, X. Liu, and M. Wang, "SFKNN-DPC: Standard deviation weighted distance-based density peak clustering algorithm, " Information Sciences, vol. 653, Art. no. 119788, 2024.
[7] H. Ju, Y. Lu, W. Ding, J. Cao, and X. Yang, "Three-way evidence theory-based density peak clustering with the principle of justifiable granularity, " Applied Soft Computing, vol. 152, Art. no. 111217, 2024.
[8] X. Yuan, H. Yu, J. Liang, and B. Xu, "A novel density peaks clustering algorithm based on K nearest neighbors with adaptive merging strategy, " International Journal of Machine Learning and Cybernetics, vol. 12, pp. 2825–2841, 2021.
[9] D. Amagata and T. Hara, "Efficient density-peaks clustering algorithms on static and dynamic data in Euclidean space, " ACM Transactions on Knowledge Discovery from Data, vol. 18, no. 1, Art. no. 2, pp. 1–27, 2023.
[10] M. Li, X. Bi, L. Wang, and X. Han, "A method of two-stage clustering learning based on improved DBSCAN and density peak algorithm, " Computer Communications, vol. 167, pp. 75–84, 2021.
[11] Y. Wang, D. Wang, Y. Zhou, X. Zhang, and C. Quek, "VDPC: Variational density peak clustering algorithm, " Information Sciences, vol. 621, pp. 627–651, 2022.
[12] Y. Wang, W. Pang, and J. Zhou, "An improved density peak clustering algorithm guided by pseudo labels,” Knowledge-Based Systems, vol. 252, Art. no. 109374, 2022.
[13] J. Zhao, G. Wang, J.-S. Pan, T. Fan, and I. Lee, "Density peaks clustering algorithm based on fuzzy and weighted shared neighbor for uneven density datasets, " Pattern Recognition, vol. 139, Art. no. 109406, 2023.
[14] F. Ge and X. Liu, "Density peaks clustering algorithm based on a divergence distance and tissue-like P system, " Applied Sciences, vol. 13, no. 4, Art. no. 2293, 2023.
[15] P. Wang, T. Wu, and Y. Yao, "A three-way adaptive density peak clustering (3W-ADPC) method, " Applied Intelligence, vol. 53, no. 20, pp. 23966–23982, 2023.
[16] S. Ding, W. Du, C. Li, X. Xu, L. Wang, and L. Ding, "Density peaks clustering algorithm based on improved similarity and allocation strategy, " International Journal of Machine Learning and Cybernetics, vol. 14, no. 4, pp. 1527–1542, 2023.
[17] L. Guo, W. Qin, Z. Cai, and X. Su, "Hybrid clustering algorithm based on improved density peak clustering, " Applied Sciences, vol. 14, no. 2, Art. no. 715, 2024.
[18] S. Zhang and K. Li, "A novel density peaks clustering algorithm with isolation kernel and K-induction, " Applied Sciences, vol. 13, no. 1, Art. no. 322, 2023.
[19] R. Kharghanian and Z. Mohammadpoory, "K-means-CRBM: An efficient unsupervised tool for feature learning, " Journal of Advanced Data Mining and Applications, vol. 14, no. 1, pp. 61–69, Jan. 2026
[20] J. Zhao, J. Tang, A. Shi, T. Fan, and L. Xu, “Improved density peaks clustering based on firefly algorithm,” International Journal of Bio-Inspired Computation, vol. 15, no. 1, pp. 24–42, 2020.
[21] J. Xie, H. Gao, W. Xie, X. Liu, and P. W. Grant, "Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors, " Information Sciences, vol. 354, pp. 19–40, 2016.
[22] D. Yu, G. Liu, M. Guo, X. Liu, and S. Yao, "Density peaks clustering based on weighted local density sequence and nearest neighbor assignment, " IEEE Access, vol. 7, pp. 34301–34317, 2019.
[23] M. Du, S. Ding, and Y. Xue, "A robust density peaks clustering algorithm using fuzzy neighborhood, " International Journal of Machine Learning and Cybernetics, vol. 9, no. 7, pp. 1131–1140, 2018.
[24] N. X. Vinh, J. Epps, and J. Bailey, "Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance, " Journal of Machine Learning Research, vol. 11, pp. 2837–2854, 2010.
[25] L. Bai, X. Cheng, J. Liang, H. Shen, and Y. Guo, "Fast density clustering strategies based on the k-means algorithm, " Pattern Recognition, vol. 71, pp. 375–386, 2017.
[26] R. Liu, H. Wang, and X. Yu, "Shared-nearest-neighbor-based clustering by fast search and find of density peaks, " Information Sciences, vol. 450, pp. 200–226, 2018.