HC-C0NG: A Hierarchical Clustering Algorithm Based on Co-nearest Natural Graph for Complex Data Distributions

Clustering complex-structured datasets—characterized by clusters of varying shapes, densities, and scales—poses a significant challenge for traditional algorithms, particularly in noisy environments and when cluster boundaries are ambiguous. Existing natural neighbor-based clustering methods often struggle with such data due to sensitivity to density fluctuations and noise interference. In this paper, we propose a hierarchical clustering based on co-nearest natural graph (HC-C0NG) to address these challenges. First, we introduce a C0NG construction strategy that sparsifies neighbor relations, effectively reducing the impact of noise and outliers. Using the constructed C0NG, HC-C0NG partitions the dataset into multiple subgraphs. These subgraphs are then progressively merged based on a newly defined subgraph similarity metric, which enhances the accuracy of grouping similar substructures, even under varying densities. Additionally, we improve the construction of the natural neighborhood graph to better capture underlying structures in datasets with blurred cluster boundaries. Extensive experiments on synthetic and real-world datasets demonstrate that HC-C0NG achieves superior performance in identifying complex and noisy clusters compared to several state-of-the-art hierarchical and density-based clustering algorithms.