Hierarchical assignment-based adaptive density peak clustering

Abstract

The density peak clustering (DPC) algorithm is sensitive to the selection of the truncation distance and prone to chaining effects during point assignment. To address these issues, a hierarchical assignment-based adaptive density peak clustering (HADPC) algorithm was proposed in this paper. This algorithm first introduces the concept of natural neighbors to adaptively compute local density, thereby reducing reliance on global parameters. Next, it reveals potential cluster structures by distinguishing between core points and boundary points, forming core clusters within a localized scope based on data distribution. Finally, boundary points are assigned through a weighted voting mechanism, resulting in complete clusters. To evaluate the effectiveness of the HADPC algorithm, comparative experiments are conducted against five baseline algorithms on the synthetic and University of California, Irvine (UCI) datasets. Experimental results indicate that the HADPC algorithm can achieve higher clustering accuracy than the comparison algorithms.

Keywords

density peak clustering (DPC) / natural neighbors / adaptive density / hierarchical allocation

References

[1] WEI X X, PENG M S, HUANG H J, et al. An overview on density peaks clustering. Neurocomputing, 2023, 554: Article 126633.

[2] LI T S, YANG L J, YANG J T, et al. Non-parameter clustering algorithm based on chain propagation and natural neighbor. Information Sciences, 2024, 672: Article 120663.

[3] BUCZAK A L, GUVEN E . A survey of data mining and machine learning methods for cyber security intrusion detection. IEEE Communications Surveys & Tutorials, 2016, 18(2): 1153-1176.

[4] LIEW A W C, YAN H, YANG M S . Pattern recognition techniques for the emerging field of bioinformatics: a review. Pattern Recognition, 2005, 38(11): 2055-2073.

[5] IKOTUN A M, EZUGWU A E, ABUALIGAH L, et al. K-means clustering algorithms: a comprehensive review, variants analysis, and advances in the era of big data. Information Sciences, 2023, 622: 178-210.

[6] RAN X C, XI Y, LU Y G, et al. Comprehensive survey on hierarchical clustering algorithms and the recent developments. Artificial Intelligence Review, 2023, 56(8): 8219-8264.

[7] KULKARNI O S, BURHANPURWALA A . A survey of advancements in DBSCAN clustering algorithms for big data. Proceedings of the 3rd International Conference on Power Electronics and IoT Applications in Renewable Energy and its Control (PARC'24), 2024, Feb 23-24, Mathura, India. Piscataway, NJ, USA: IEEE, 2024: 106-111.

[8] HEIDARI J, DANESHPOUR N, ZANGENEH A . A novel K-means and K-medoids algorithms for clustering non-spherical-shape clusters non-sensitive to outliers. Pattern Recognition, 2024, 155: Article 110639.

[9] GUO W J, CHEN W, LIU X G . Density peak clustering by local centers and improved connectivity kernel. Information Sciences, 2024, 666: Article 120439.

[10] CHOWDHURY S, HELIAN N, De AMORIM R C. Feature weighting in DBSCAN using reverse nearest neighbours. Pattern Recognition, 2023, 137: Article 109314.

[11] RODRIGUEZ A, LAIO A . Clustering by fast search and find of density peaks. Science, 2014, 344(6191): 1492-1496.

[12] YANG Y Q, CAI J H, YANG H F, et al. Density clustering with divergence distance and automatic center selection. Information Sciences, 2022, 596: 414-438.

[13] GUAN J Y, LI S, HE X X, et al. Clustering by fast detection of main density peaks within a peak digraph. Information Sciences, 2023, 628: 504-521.

[14] DU M J, DING S F, JIA H J . Study on density peaks clustering based on k-nearest neighbors and principal component analysis. Knowledge-Based Systems, 2016, 99: 135-145.

[15] LIU R, WANG H, YU X M . Shared-nearest-neighbor-based clustering by fast search and find of density peaks. Information Sciences, 2018, 450: 200-226.

[16] LI Y, ZHOU W J, WANG H K . F-DPC: fuzzy neighborhood-based density peak algorithm. IEEE Access, 2020, 8: 165963-165972.

[17] ZHAO J, TANG J J, SHI A Y, et al. Improved density peaks clustering based on firefly algorithm. International Journal of Bio-Inspired Computation, 2020, 15(1): 24-42.

[18] JIANG D, ZANG W K, SUN R, et al. Adaptive density peaks clustering based on K-nearest neighbor and Gini coefficient. IEEE Access, 2020, 8: 113900-113917.

[19] YU H, CHEN L Y, YAO J T . A three-way density peak clustering method based on evidence theory. Knowledge-Based Systems, 2021, 211: Article 106532.

[20] GUO W J, WANG W H, ZHAO S P, et al. Density peak clustering with connectivity estimation. Knowledge-Based Systems, 2022, 243: Article 108501.

[21] ABBAS M, EL-ZOGHABI A, SHOUKRY A . DenMune: density peak based clustering using mutual nearest neighbors. Pattern Recognition, 2021, 109: Article 107589.

[22] GUO L M, QIN W J, CAI Z, et al. Hybrid clustering algorithm based on improved density peak clustering. Applied Sciences, 2024, 14(2): Article 715.

[23] SHI Z C, GUO R Z, ZHAO Z G . An improved hierarchical clustering method based on the k-NN and density peak clustering. Transactions in GIS, 2023, 27: 2197-2212.

[24] HAN M, LEE J S . Graph-based density peak merging for identifying multi-peak clusters. Applied Soft Computing, 2023, 146: Article 110657.

[25] DING S F, DU W, XU X, et al. An improved density peaks clustering algorithm based on natural neighbor with a merging strategy. Information Sciences, 2023, 624: 252-276.

[26] CHENG D D, ZHU Q S, HUANG J L, et al. A local cores-based hierarchical clustering algorithm for data sets with complex structures. Neural Computing and Applications, 2019, 31(11): 8051-8068.

[27] YU D H, LIU G J, GUO M Z, et al. Density peaks clustering based on weighted local density sequence and nearest neighbor assignment. IEEE Access, 2019, 7: 34301-34317.