Paper deep dive
Density-aware Hierarchical Clustering Based on Element-Categorized Connection Subgraphs
Yuning Yu, José Rodríguez-Piñeiro, Xuefeng Yin, Bin Feng
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/10/2026, 3:52:38 AM
Summary
The paper proposes DHC-ECS, a density-aware hierarchical clustering method that integrates hierarchical, density-based, and graph clustering techniques. It introduces a novel inter-cluster similarity metric based on element-categorized connection subgraphs (ECS) within KNN graphs, considering local density, structural connectivity, and intrinsic thresholds to improve clustering accuracy and robustness over baseline methods like Chameleon and DBSCAN.
Entities (10)
Relation Signals (10)
DHC-ECS → integrates → Hierarchical Clustering
confidence 95% · effectively integrates the hierarchical clustering, density-based clustering, and graph clustering
DHC-ECS → integrates → graph clustering
confidence 95% · effectively integrates the hierarchical clustering, density-based clustering, and graph clustering
DHC-ECS → integrates → density-based clustering
confidence 95% · effectively integrates the hierarchical clustering, density-based clustering, and graph clustering
DHC-ECS → proposes → inter-cluster similarity metric
confidence 95% · we propose a density-aware hierarchical clustering method... Particularly, a novel inter-cluster similarity metric is introduced
DHC-ECS → utilizes → KNN connection subgraph
confidence 92% · based on element-categorized connection subgraphs (DHC-ECS)... element categorization in the KNN connection subgraphs
Chameleon → isbaselinefor → DHC-ECS
confidence 90% · compared with the baseline methods (including AChameleon...)
DHC-ECS → outperforms → G-RMS
confidence 90% · DHC-ECS exhibits superior overall performance... compared with the baseline methods (including... G-RMS)
DHC-ECS → outperforms → McDPC
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Clustering is a fundamental data mining technique for pattern recognition through unsupervised learning. Among various clustering methods, hierarchical clustering, density-based clustering, and graph clustering stand out as representative approaches. For hierarchical clustering, it can be categorized into agglomerative and divisive modes to construct clusters in a recursive manner. The key aspect of both modes is the calculation of inter-cluster similarity, which determines whether to merge the sub-clusters into one cluster or divide a current cluster into sub-clusters. Traditionally, the similarity is derived from pairwise distances, often overlooking density variations and structural connectivity in graphs. To address this, we propose a density-aware hierarchical clustering method based on element-categorized connection subgraphs (DHC-ECS), which effectively integrates the hierarchical clustering, density-based clustering, and graph clustering. Particularly, a novel inter-cluster similarity metric is introduced that considers not only distances but also the element categorization in the KNN connection subgraphs, kernel density estimation, and local connectivity within sub-clusters. Extensive evaluations on heterogeneous benchmark datasets demonstrate that DHC-ECS exhibits superior overall performance in terms of clustering accuracy and parameter robustness compared with the baseline methods (including AChameleon, RNN-DBSCAN, McDPC, and G-RMS). The work indicates the great potential of the proposed clustering algorithm for low-dimensional datasets by leveraging local density and graph-structured connectivity (i.e., the duality of vertices and edges), as well as the possibility to determine an intrinsic threshold, reducing the reliance on manual parameter tuning.
Tags
Links
- Source: https://arxiv.org/abs/2608.06990v1
- Canonical: https://arxiv.org/abs/2608.06990v1
Trouble viewing inline? Open PDF directly →
Full Text
59,880 characters extracted from source content.
Expand or collapse full text
Density-aware Hierarchical Clustering Based on Element-Categorized Connection Subgraphs Yuning Yu yuning˙yu@tongji.com 0000-0003-4797-8674 Tongji UniversityCao’an road 4800ShanghaiChina201804 , José Rodríguez-Piñeiro Tongji UniversityCao’an road 4800ShanghaiChina j.rpineiro@tongji.edu.cn , Xuefeng Yin Tongji UniversityCao’an road 4800ShanghaiChina yinxuefeng@tongji.edu.cn and Bin Feng RadioSky (Shanghai) Communication Technology Co., LtdCao’an road 4800ShanghaiChina fengbin@srtc.org.cn Abstract. Clustering is a fundamental data mining technique for pattern recognition through unsupervised learning. Among various clustering methods, hierarchical clustering, density-based clustering, and graph clustering stand out as representative approaches. For hierarchical clustering, it can be categorized into agglomerative and divisive modes to construct clusters in a recursive manner. The key aspect of both modes is the calculation of inter-cluster similarity, which determines whether to merge the sub-clusters into one cluster or divide a current cluster into sub-clusters. Traditionally, the similarity is derived from pairwise distances, often overlooking density variations and structural connectivity in graphs. To address this, we propose a density-aware hierarchical clustering method based on element-categorized connection subgraphs (DHC-ECS)111The source code is publicly available at https://github.com/yuning-yu/DHC-ECS-clustering-algorithm., which effectively integrates the hierarchical clustering, density-based clustering, and graph clustering. Particularly, a novel inter-cluster similarity metric is introduced that considers not only distances but also the element categorization in the KNN connection subgraphs, kernel density estimation, and local connectivity within sub-clusters. Extensive evaluations on heterogeneous benchmark datasets demonstrate that DHC-ECS exhibits superior overall performance in terms of clustering accuracy and parameter robustness compared with the baseline methods (including AChameleon, RNN-DBSCAN, McDPC, and G-RMS). The work indicates the great potential of the proposed clustering algorithm for low-dimensional datasets by leveraging local density and graph-structured connectivity (i.e., the duality of vertices and edges), as well as the possibility to determine an intrinsic threshold, reducing the reliance on manual parameter tuning. Hierarchical clustering, Density-based clustering, Graph clustering, Inter-cluster similarity, K-nearest neighbors †copyright: acmcopyright†doi: X.X 1. Introduction A cluster is defined as a group of observations that are similar to each other, i.e. close to each other in coordinates, parameter, or attributes. The aim of clustering is to find clusters of data points with high intra-cluster similarity and low inter-cluster similarity. As a kind of unsupervised learning tool, clustering is useful for recognizing underlying patterns from large datasets, which has wide applications in Geographic Information System (GIS), image segmentation, text analysis, bioinformatics, etc (Bryant and Cios, 2018; Khan et al., 2014). 1.1. Background of Hierarchical Clustering Clustering methods can be traditionally categorized into several main types, including partitioning-based clustering, hierarchical clustering, density-based clustering, graph-based clustering, grid-based clustering, and model-based clustering. Among them, hierarchical clustering is a very common clustering method, which forms clusters recursively in an agglomerative or divisive mode. Specifically, for the agglomerative hierarchical clustering methods, initially each observation is regarded as a cluster, or sub-clusters are first generated, and then the most similar sub-clusters are merged based on the predefined and calculated similarity metric. After each agglomeration, similarity between each pair of sub-cluster is recalculated before the next agglomeration. The algorithm will finish when a certain break condition is achieved, e.g, the predefined number of clusters, or the threshold of similarity. On the contrary, the divisive hierarchical clustering method regards all observations as a cluster initially and then find the most appropriate division position according to the similarity metric. After each partition, similarity is recalculated before the next partition until the break condition is satisfied. Traditionally, the similarity can be calculated by the minimum distance, maximum distance, average distance, centroid distance (Guha et al., 1998). These simple similarity definitions have some drawbacks and cannot cope with the datasets close to each other, or without hyperspherical shapes and nonuniform sizes (Guha et al., 1998). For minimum distance and maximum distance, they are easily affected by the outlier and do not consider the internal structure of the clusters. For average distance and centroid distance, the effect of outliers also exists. To make the clustering process more robust and able to identify clusters of non-spherical shapes and wide variances in size, Cure algorithm (Guha et al., 1998) represents clusters with multiple well-scattered points and shrink them toward the center of clusters, but it ignores the information of aggregate interconnectivity. Rock algorithm (Guha et al., 2000) considers the interconnectivity but it ignores the closeness of two clusters as defined by the similarity of the closest items across two clusters. Considering the unreasonable inter-cluster similarity and static model assumption, Chameleon algorithm (Karypis et al., 1999) was proposed in 1999, which considers the relative interconnectivity and relative closeness. Afterwards, diverse similarity metrics are proposed including utilizing intersection points, i.e. shared nearest neighbors (Nazari et al., 2015; Nazari and Kang, 2018), similarity metric based on the modified relative interconnectivity and relative closeness considering the internal expected value for connection (Guo et al., 2019a), similarity metric based on adaptive neighbor graph (Cao et al., 2018). 1.2. Limitations of Existing Hierarchical Clustering From the above investigation, the existing definitions of inter-cluster similarity for hierarchical clustering predominantly consider the distance between sub-clusters while neglecting the density of points. For a given observation, density is defined as a measure quantifying the degree of closeness between this observation and its neighboring points. Over the years, density-based clustering algorithms have been extensively explored and have gained significant attention, leading to the development of well-known methods such as density-based spatial clustering of applications with noise (DBSCAN) (Ester et al., 1996), density peak clustering (DPC) (Rodriguez and Laio, 2014; Guo et al., 2024), and mean-shift (MS) algorithm (Comaniciu and Meer, 1999; Guo et al., 2024). These algorithms have demonstrated their effectiveness across diverse datasets. As illustrated in Fig. 1(a), the duality between vertices and edges is an intrinsic property of the fully connected graph of the original data. Vertices and edges provide complementary characterizations of the underlying data structure, analogous to the concept of “yin” and “yang” in traditional Chinese philosophy. Leveraging this duality, a comprehensive clustering algorithm incorporating local structure and density is expected to yield superior clustering performance compared with independent hierarchical or density-based clustering methods, as shown in Fig. 1(b). In other words, the consistency in both local density and structures should be maintained within each cluster, and their variations across different clusters can be exploited for effective cluster discrimination. Meanwhile, the closeness and interconnectivity in traditional hierarchical clustering methods are also a manifestation of the duality. Existing approaches that integrate density-based and hierarchical clustering methods predominantly focus on constructing density-driven hierarchical structures (Campello et al., 2015; Xu et al., 2016; Neto et al., 2019; Zhu et al., 2022; Wang and Li, 2025), e.g., employing density information to generate sub-clusters, and subsequently organize them into hierarchical representations, or directly exploring the evolution of clusters across different density levels to obtain multi-scale clustering hierarchies. Although these methods effectively capture clusters with arbitrary shapes and varying densities, they mainly characterize clusters from the perspective of density distribution, and graph or tree structures primarily serve as computational substrates for density-based hierarchy construction. Recent graph-based extensions (Shao et al., 2018; Du et al., 2024) further combine topological properties of graphs together with hierarchical or density cluster features, providing additional information for cluster identification. Nevertheless, how to jointly exploit density consistency, structural consistency, adaptive cluster merging, and automatic hierarchy selection within a unified framework remains an open challenge. Figure 1. Utilizable intrinsic features of clusters. Furthermore, existing graph-based hierarchical clustering algorithms relying on graph cut criteria, such as minimum-cut and expected-cut based methods (Karypis et al., 1999; Shao et al., 2018), primarily evaluate inter-cluster similarity according to global graph cut criteria, while the structural characteristics of the connection region between adjacent sub-clusters are only implicitly considered. Here, the connection region is defined as the set of vertices and edges linking two adjacent sub-clusters in the k-nearest neighbor (KNN) graph. Consequently, the estimated similarity between sub-clusters may become unreliable, particularly when they exhibit substantially different local densities. Inspired by the concepts of core, boundary, and outlier points in density-based clustering, explicitly categorizing the vertices and edges within the connection region according to their structural and density characteristics can provide a more discriminative representation of inter-cluster relationships, thereby improving clustering accuracy and robustness. This observation motivates the proposed element-categorized connection subgraph (ECS). 1.3. Intrinsic Thresholds for Clustering Apart from the integration of hierarchical and density-based methodologies, and the refinement of vertex and edge categorization, another critical challenge in clustering lies in the selection of appropriate threshold parameters, which determines the stopping condition and the resultant clustering performance. Although some parameter-free clustering methods have been proposed (Hou et al., 2016; Li et al., 2020; Mahon and Lapata, 2025), their effectiveness has not yet been widely validated, and their applicability to diverse clustering scenarios remains limited. Furthermore, the authors posit the existence of intrinsic and dataset-independent thresholds under a specified clustering evaluation criterion. As illustrated in Fig. 1(d), although the orange points can be clearly regarded as belonging to the same cluster as the black points, the cluster affiliation of the green points becomes ambiguous as they approach the black points. However, for a given clustering evaluation criterion, the continuous increase of the distance between green points and black points eventually results in a discrimination beyond a certain distance threshold. This suggests the potential existence of an inherent distance threshold determining cluster membership, which is analogous to the marginal affiliation value in fuzzy clustering theory (Ruspini et al., 2019). In practice, the relationships among sub-clusters are usually more explicit than the ambiguous case in Fig. 1(d), facilitating the setting of an intermediate threshold. Therefore, instead of relying on manually specified parameters or parameter-free strategies that implicitly search for optimal configurations, an alternative direction is to identify and explicitly exploit the intrinsic threshold induced by the underlying data structure, thereby enhancing generalizability of clustering methods across datasets without explicitly defined parameters. This work provides a preliminary exploration of this idea to identify the intrinsic threshold. 1.4. Contributions of This Work Based on the above investigations and discussions, we propose a novel similarity metric that jointly considers both hierarchical and density characteristics of observations. The connectivity between sub-clusters is established through the ECS, where the vertices and edges within the connection regions are explicitly categorized according to their structural properties. Subsequently, the inter-cluster similarity is quantified by incorporating the structural and density information associated with these categorized connection elements. The proposed formulation comprehensively integrates link compactness (LC), link similarity (LS), density similarity (DS), and the coefficient of variation (CV) of linkage edge weights. Detailed definitions of these indices are provided in Section 3. The main contributions and novelties of this work include: (1) Hybrid clustering framework: A Density-aware Hierarchical Clustering (DHC) method based on element-categorized connection subgraphs (DHC-ECS) is proposed to combine the principles of hierarchical clustering, density-based clustering, and graph-based clustering. By designing a novel inter-cluster similarity metric that explicitly considers local structure and density, DHC-ECS effectively utilizes the duality of vertices and edges in the constructed graph, enhancing clustering robustness. (2) Element-categorized graph representation: To accommodate density variations and structural heterogeneity, we propose a novel KNN connection subgraph representation with explicit element categorization, namely the ECS framework, which accurately characterizes local structure within the dataset. This approach significantly improves clustering performance on datasets with inhomogeneous distributions. (3) Intrinsic threshold: Our experimental results provide empirical evidence for the potential existence of the intrinsic threshold in clustering. Although the thresholds still exhibit dataset-dependent variations, the discrepancy is relatively moderate, indicating the possibility of identifying the intrinsic threshold. This work extends the potential clustering paradigm beyond conventional parameter-driven and parameter-free approaches. The rest of the paper is structured as follows: Section 2 introduces the principle of hierarchical clustering and discusses the algorithm performance limitations. Section 3 introduces the methodology of the proposed clustering algorithm, including the algorithm flow, the concept of KNN connection subgraph, the categorization of vertices and edges of the connection regions of sub-clusters, and the proposed similarity metric. In Section 4, we present evaluation results on ten synthetic datasets and the comparison with some baseline hierarchical and density-based clustering methods. Finally, conclusions are drawn in Section 5. 2. The Basics of Chameleon-based Hierarchical Clustering In this section, the fundamental concepts of hierarchical clustering algorithms are introduced. Particularly, a representative algorithm named Chameleon (Karypis et al., 1999) is presented to facilitate a deep understanding of hierarchical clustering methods. Furthermore, the limitations of traditional Chameleon clustering methods are discussed. Several representative improvements of this algorithm are also introduced. 2.1. Principle of the Algorithm Chameleon is a well-known dynamic hierarchical clustering algorithm (Karypis et al., 1999) . It models the dataset as a sparse k-nearest-neighbor (KNN) graph Gknn(V,E)G_knn(V,E) based on a similarity matrix computed using a predefined similarity metric between each pair of observations. Here, V denotes the set of observations and E denotes the set of undirected edges, satisfying that (u,v)∈E(u,v)∈ E if and only if v∈Nk(u)v∈ N_k(u) or u∈Nk(v)u∈ N_k(v), where Nk(x)N_k(x) denotes the KNN of the observation x. Based on the KNN graph, the algorithm consists of two phases. During the first phase, the KNN graph is partitioned into a set of relatively small sub-clusters. During the second phase, the sub-clusters are dynamically merged using an inter-cluster similarity considering not only relative interconnectivity but also relative closeness. The pair of sub-clusters that has the highest inter-cluster similarity is merged into one cluster and then the inter-cluster similarity between this newly generated sub-cluster and all other sub-clusters is updated before the next agglomeration. The algorithm terminates when the user-specified thresholds for relative interconnectivity and relative closeness are reached. Particularly, the inter-cluster similarity is defined as follows. It takes relative interconnectivity RIRI and relative closeness RCRC into account comprehensively. For two sub-clusters CiC_i and CjC_j, RI(Ci,Cj)RI(C_i,C_j) is calculated as (1) RI(Ci,Cj)=2EC(Ci,Cj)EC(Ci)+EC(Cj),RI(C_i,C_j)= 2EC(C_i,C_j)EC(C_i)+EC(C_j), where EC(Ci,Cj)EC(C_i,C_j) is the sum of the weights of the edges that straddle the two clusters, which represents the absolute interconnectivity between the two sub-clusters. EC(Ci)EC(C_i) and EC(Cj)EC(C_j) are the sum of the weight of the edges crossing a min-cut bisection that splits the cluster into two roughly equal parts, which represents the internal interconnectivity of the corresponding sub-cluster. Through the normalization process, RI(Ci,Cj)RI(C_i,C_j) considers the relative interconnectivity. The relative closeness RC(Ci,Cj)RC(C_i,C_j) is calculated as (2) RC(Ci,Cj)=SEC¯(Ci,Cj)|Ci||Ci|+|Cj|SEC¯(Ci)+|Cj||Ci|+|Cj|SEC¯(Cj),RC(C_i,C_j)= SEC(C_i,C_j) |C_i | |C_i |+ |C_j | SEC(C_i)+ |C_j | |C_i |+ |C_j | SEC(C_j), where SEC¯(Ci,Cj) SEC(C_i,C_j) is the average weight of the edges that connect vertices in CiC_i and CjC_j, SEC¯(Ci) SEC(C_i) and SEC¯(Cj) SEC(C_j) are respectively the average weights of the edges that belong to the min-cut bisector of CiC_i and CjC_j. |Ci||C_i| and |Cj||C_j| denote the number of points in each cluster. Inter-cluster similarity can be defined as (3) RI(Ci,Cj)×RC(Ci,Cj)αRI(C_i,C_j)×RC(C_i,C_j)^α where α is a parameter giving different importance to RI(Ci,Cj)RI(C_i,C_j) and RC(Ci,Cj)RC(C_i,C_j). 2.2. Discussion on Algorithm Performance By dynamically updating the inter-cluster similarity considering both relative interconnectivity and relative closeness, Chameleon algorithm balances inter-cluster and intra-cluster characteristics without relying on static model assumptions. Therefore, it can obtain better clustering results on datasets of different shapes, sizes, and densities compared with traditional hierarchical methods (Karypis et al., 1999). However, some drawbacks of the Chameleon algorithm and other hierarchical clustering methods can be identified, as demonstrated in the introduction part, including: (1) insufficient consideration of local characteristics within and near the connection regions between sub-clusters; (2) lack of density and graph structural information for the similarity calculation; (3) threshold dependency. For the past few decades, several improvements to the Chameleon algorithm have been proposed. Existing studies mainly focus on refining the similarity measure (Guo et al., 2019b; Barton et al., 2019), incorporating local density and adaptive neighborhood graphs (Cao et al., 2018), improving the robustness of hierarchical merging and automatic cutoff selection (Jeong et al., 2013; Barton et al., 2019), and enhancing computational efficiency for large-scale datasets (Singh and Ahuja, 2025). Despite these improvements, the underlying graph representation remains largely unchanged. Consequently, the structural characteristics of the connection region between neighboring sub-clusters are still inadequately characterized, while both graph construction and hierarchical merging continue to rely heavily on manually specified thresholds. Furthermore, existing similarity measures mainly evaluate the overall interconnectivity or closeness between sub-clusters, without explicitly exploiting the structural properties of individual vertices and edges within the connection region. These limitations motivate the proposed DHC-ECS algorithm, which explicitly models both structural and density information for inter-cluster similarity estimation, based on the proposed element-categorized KNN connection subgraphs. 3. The Proposed Clustering Method The proposed DHC-ECS algorithm can be divided into two stages. In the first stage, a set of relatively small sub-clusters is generated, and preliminarily merged in a greedy way by iteratively agglomerating the pair of sub-clusters with the highest similarity. Since the sub-clusters in this stage are relatively small, their similarity is measured using the average distance between points. In the second stage, since the sub-clusters become larger and contain more points, the average similarity is not sufficient for characterizing inter-cluster similarities. Therefore, the proposed inter-cluster similarity metric is applied. The detailed algorithm flow is described below. (1) Greedy merging: In the first stage, each observation is initially regarded as a separate cluster, and the sub-clusters are then merged iteratively through a greedy method (Guo et al., 2019a), i.e., we find the pair of sub-clusters that has largest similarity and merge them into one cluster. Then the similarity between this new cluster and the other clusters is updated. In this stage, the similarity is calculated based on the average distance between points in different clusters as (4) di,j d_i,j =1|Ci||Cj|∑q∈Cj∑p∈Cidist(p,q), = 1 |C_i | |C_j |Σ _q∈C_jΣ _p∈C_i dist(p,q), (5) wi,j w_i,j =1di,j+1,Si,j=wi,j. = 1d_i,j+1, S_i,j=w_i,j. Here, di,jd_i,j denotes the distance between CiC_i and CjC_j, where CiC_i and CjC_j are the i-th and j-th cluster, respectively. dist(p,q) dist(p,q) represents the distance between point pair p and q, where p and q belong to CiC_i and CjC_j, respectively. This distance can be defined as needed, e.g., geodesic distance for non-convex clusters, standard Euclidean distance for data with inconsistent scales across dimensions, or Mahalanobis distance when correlation exists between dimensions. |.| |. | denotes the number of observations in a cluster. wi,jw_i,j denotes the edge weight, which also serves as the similarity si,js_i,j between CiC_i and CjC_j. For the synthetic datasets in Section 4, we adopt geodesic distance rather than Euclidean distance, because the dimensions are balanced and independent while manifold structures are present. This allows the distance measure to better reflect the actual distance on the manifold. The calculation process of geodesic distance is introduced below, where KNN is adopted for the calculation. (a) Calculate the Euclidean distance between all pairs of points and find the KNN set Nk(x)N_k(x) of each point x in the whole dataset X. (b) Initialize the geodesic distance. (6) dG(p,q)=d(p,q),ifq∈Nk(p)∞,otherwised_ G(p,q)= \ array[]ld(p,q), if\>q∈N_k(p)\\ ∞, otherwise array . (7) dG(p,q)=mindG(p,q),dG(q,p),d_ G(p,q)= min\d_ G(p,q),d_ G(q,p)\, Here, dG(p,q)d_G(p,q) represents the geodesic distance between p and q, and Nk(p)N_k(p) represents the KNN set of p. (c) Calculate the shortest distance between any pair of points p and q. (8) dG(p,q)=minh∈∖p,qdG(p,q),dG(p,h)+dG(h,q),d_ G(p,q)= min _h∈X \p,q\\d_ G(p,q),d_ G(p,h)+d_ G(h,q)\, where h is an intermediate point besides p and q. The shortest distance between any pair of point is obtained as the final geodesic distance. The stopping condition for the first stage is that the number of sub-clusters equals the threshold TnT_n, which is larger than the actual number of clusters. It is commonly set to N N in (Guo et al., 2019a), where N denotes the number of points in the entire dataset. (2) Refined merging: In the second stage, an agglomerative procedure is conducted to obtain the final clustering results, while the similarity calculation changes since the sub-clusters are larger in size than that in the first stage and the local characteristic becomes more important to determine whether to merge two clusters. For this reason, we construct a KNN graph for the entire dataset and determine the linkage between clusters. We use Nk(x)(x)N_k(x)(x) to denote the KNN set222It should be noted that if the total number of points in a sub-cluster is less than the preset K, the K value for this sub-cluster can be set to be the number of its points, and the KNN connection subgraph may become asymmetric for this sub-cluster and its connected sub-clusters. This processing ensures the balance of internal elements and linkage elements for small sub-clusters. of point x , and use Ek(x)(x)E_k(x)(x) to denote the set of edges between point x and its KNN. More generally, for any point set X, we define k(⋅)()=⋃x∈Nk(x)(x)N_k(·)(X)= _x N_k(x)(x), ℰk(⋅)()=⋃x∈Ek(x)(x)E_k(·)(X)= _x E_k(x)(x). Assuming that the index set of cluster pairs with connections is i1,j1,i2,j2,…,iNt,jNt\\i_1,j_1\,\i_2,j_2\,...,\i_N^t,j_N^t\\, where NtN^t denotes the number of cluster pairs in the t-th iteration, several key definitions for cluster pairs CiC_i and CjC_j are introduced as follows: • KNN graph First, based on the concept of KNN introduced above, we can construct a KNN graph for the original dataset. A clear definition is written as (9) GKNN=(V,EKNN),V=,G^KNN=(V,E^KNN),V=X, where (10) EKNN=u,v|u∈Nk(v)(v)orv∈Nk(u)(u).E^KNN= \\u,v\ |u∈ N_k(v)(v)\;\ or\;\ v∈ N_k(u)(u) \. • KNN connection subgraph Based on the definition of KNN graph, the KNN connection subgraph can be defined to describe the connection between a pair of clusters Ci,Cj\C_i,C_j\. Here, .,.\.,.\ denotes an unordered pair. CiC_i and CjC_j are both point sets, and Ci,Cj⊆VC_i,C_j V. The corresponding KNN connection subgraph is defined as a subgraph constructed from the vertices in Ci,Cj\C_i,C_j\ involved in inter-cluster KNN linkage and their KNN neighbors, denoted as (11) Gi,jKNN=(Vi,jKNN,Ei,jKNN),G_i,j^KNN=(V_i,j^KNN,E_i,j^KNN), To obtain Gi,jKNNG_i,j^KNN, the vertices that generate the linkage relationship are first picked out: (12) Vi,j∗=u|(u∈Ci∧∃v∈Nk(u)(u)∩Cj)∨(u∈Cj∧∃v∈Nk(u)(u)∩Ci), V_i,j^*= \u\, |\, (u∈ C_i ∃ v∈ N_k(u)(u)∩ C_j )\, \, (u∈ C_j ∃ v∈ N_k(u)(u)∩ C_i ) \, Then, the edges connected to these seed vertices form the edge set of Gi,jKNNG_i,j^KNN (13) Ei,jKNN=ℰk(⋅)(Vi,j∗).E_i,j^KNN=E_k(·)(V_i,j^*). Therefore, the vertex set of Gi,jKNNG_i,j^KNN can be determined including both seed vertices Vi,j∗V_i,j^* and their KNN, formulated as (14) Vi,jKNN=Vi,j∗∪k(⋅)(Vi,j∗).V_i,j^KNN=V_i,j^* _k(·)(V_i,j^*). For an intuitive presentation, an example of a KNN connection subgraph is shown in Fig. 2. Two neighboring sub-clusters are marked using green points as Sub-cluster 1 and blue points as Sub-cluster 2. For each point, the KNN set is determined according to the above definition, and the KNN connection subgraph is plotted as shown in Fig. 2. According to the linkage relationship, the KNN connection subgraph can be divided into different parts. For the vertex set, it can be divided into linkage points and internal points, which are marked respectively with circles and squares. For the edge set, it can be divided into linkage edges and internal edges, which are plotted using red and black lines respectively. The detailed definitions are introduced below. Figure 2. An example of KNN connection subgraph and categorization of vertices and edges (k=4). • Linkage points Linkage points denote the set of vertices connecting the two neighboring sub-clusters, defined as Vi,jlinkage=Vi∪VjV_i,j^linkage=V_i∪ V_j, satisfying 1) Vi⊆Ci,Vj⊆CjV_i C_i,V_j C_j, 2) ∀vi∈Vi∀ v_i∈ V_i, ∃v∈Cj∃\,v∈ C_j, s.t. v∈Nk(vi)(vi)v∈ N_k(v_i)(v_i) or vi∈Nk(v)(v)v_i∈ N_k(v)(v). This constraint also applies to VjV_j. In Fig. 2, linkage points refer to those points linked by red edges. • Linkage edges Linkage edges denote the set of edges Ei,jlinkageE_i,j^linkage connecting ViV_i and VjV_j in Vi,jlinkageV_i,j^linkage, satisfying 1) Ei,jlinkage⊆ℰk(⋅)(Vi)∪ℰk(⋅)(Vj)E_i,j^linkage _k(·)(V_i) _k(·)(V_j), 2) ∀e=v1,v2∀ e=\v_1,v_2\, s.t. (v1∈Vi∧v2∈Vj)∨(v1∈Vj∧v2∈Vi)(v_1∈ V_i v_2∈ V_j) (v_1∈ V_j v_2∈ V_i). The weight of each linkage edge is denoted as W(ei,jlinkage)W(e_i,j^linkage), which can be calculated as (4). In Fig. 2, linkage edges refer to the red edges. • Internal points connecting to linkage points Internal points denote the set of points connected to linkage points but not contributing to the KNN connection between the two sub-clusters, defined as Vi,jinternal=(k(⋅)(Vi)∪k(⋅)(Vj))∖Vi,jlinkageV_i,j^internal=(N_k(·)(V_i) _k(·)(V_j)) V_i,j^linkage, where ‘\ ’ denotes the set-difference operator. • Internal edges connecting to linkage points Internal edges denote the set of edges that connect the linkage points and internal points, defined as Ei,jinternal=(ℰk(Vi)∪ℰk(Vj))∖Ei,jlinkageE_i,j^internal=(E_k(V_i) _k(V_j)) E_i,j^linkage, i.e, the edges that belong to the linkage points and connect to the KNN set, but are not part of the linkage edge set. The weight of each internal edge is denoted as W(ei,jinternal)W(e_i,j^internal). In Fig. 2, internal edges connecting to linkage points refer to the black edges. • Point Density Point density is defined as the kernel density used to represent the concentration degree of neighboring points. For a specific observation x, its density is calculated as D(x)=∑y∈Nk(x)(x)exp(−|dist(x,y)|)D(x)=Σ _y∈ N_k(x)(x) (- |dist(x,y) |). Based on the element categorization of the KNN connection subgraphs, the similarity between two sub-clusters is defined as (15) Si,j=2LC1(|LS−1|+1)α1(|DS−1|+1)α,S_i,j=2LC 1 ( |LS-1 |+1 )^α 1 ( |DS-1 |+1 )^α, where Si,jS_i,j is the similarity metric between CiC_i and CjC_j. It considers the link compactness (LC), link similarity (LS), density similarity (DS), and the coefficient of variation (CV) of the linkage-edge weights for automatically adjusting the similarity according to the randomness in the distribution of linkage points. The definitions of LC, LS, DS, CV, and α are given as follows: (16) LC=∑ei,jlinkage∈Ei,jlinkageW(ei,jlinkage)∑ei,jinternal∈Ei,jinternalW(ei,jinternal),LC= Σ _e_i,j linkage∈ E_i,j linkageW(e_i,j linkage)Σ _e_i,j internal∈ E_i,j internalW(e_i,j internal), (17) LS=|Ei,jinternal|∑ei,jlinkage∈Ei,jlinkageW(ei,jlinkage)|Ei,jlinkage|∑ei,jinternal∈Ei,jinternalW(ei,jinternal),LS= |E_i,j internal |Σ _e_i,j linkage∈ E_i,j linkageW(e_i,j linkage) |E_i,j linkage |Σ _e_i,j internal∈ E_i,j internalW(e_i,j internal), (18) DS=|Vi,jinternal|∑vi,jlinkage∈Vi,jlinkageD(vi,jlinkage)|Vi,jlinkage|∑vi,jinternal∈Vi,jinternalD(vi,jinternal),DS= |V_i,j^internal |Σ _v_i,j^linkage∈V_i,j linkageD(v_i,j^linkage) |V_i,j^linkage |Σ _v_i,j^internal∈V_i,j internalD(v_i,j^internal), (19) CV=std(W(ei,jlinkage∪ei,jinternal))mean(W(ei,jlinkage∪ei,jinternal)),α=e−rCV.CV= std (W (e_i,j linkage∪ e_i,j internal ) )mean (W (e_i,j linkage∪ e_i,j internal ) ),\,α=e^-rCV. Here, std(.)std(.) and mean(.)mean(.) denote the standard deviation and mean value of the elements in the set, respectively. |⋅||·| denotes the cardinality of a set. r is an adjustable parameter to control the influence of the randomness of point distribution on the similarity calculation, which is fixed to 33 in this work. As shown in (16)–(19), LC represents the linkage compactness between two sub-clusters as the ratio between the sum of weights of linkage edges and internal edges, LS represents the linkage similarity between two sub-clusters as the ratio between the average weights of linkage edges and internal edges. DS represents the density similarity as the ratio between average density of linkage points and average density of internal points connecting to linkage points. α is a coefficient used to adapt to the randomness of point distribution. When the variation of edge weights and point density is large, corresponding to a large CV, the similarity decreases automatically as α approaches 0, and the terms (|LS−1|+1)α ( |LS-1 |+1 )^α and (|DS−1|+1)α ( |DS-1 |+1 )^α are driven to approach 1 because of the exponent α. In this case, the link compactness LC becomes more significant. Additionally, according to (15), a larger value of Si,jS_i,j indicates higher similarity between CiC_i and CjC_j. The break condition for this algorithm is that the similarity for any pair of clusters is lower than the predefined threshold TsT_s, or the number of clusters equals the predefined value. Algorithm 1 Density-aware hierarchical clustering based on element-categorized connection subgraphs 0: Data set: X, Predefined parameters: TnT_n, TsT_s (optional: Tn,finalT_n,final), K,rK,r. 0: Clustering results: L(x)L(x), Cluster number: NcN_c. 1: label=1,Nc=0label=1,N_c=0 2: for all x∈x do 3: L(x)←labelL(x) 4: label←label+1label +1 5: Nc←Nc+1N_c← N_c+1 6: end for 7: for i=0i=0 to Nc−1N_c-1 do 8: for j=ij=i to NcN_c do 9: calculate Si,jS_i,j 10: Sj,i←Si,jS_j,i← S_i,j 11: end for 12: end for 13: while Nc>TnN_c>T_n do 14: i,j←argmaxi,jSi,j,i<j\i,j\← _i,jS_i,j,i<j 15: L(xj)|L(xj)=j←iL(x_j) |_L(x_j)=j← i 16: L(xj)|L(xj)>j←L(xj)−1L(x_j) |_L(x_j)>j← L(x_j)-1 17: Update similarity matrix S 18: end while 19: Construct KNN connection subgraphs 20: Obtain D(x)D(x), Vi,jlinkageV_i,j^linkage, Ei,jlinkageE_i,j^linkage, Vi,jinternalV_i,j^internal, Ei,jinternalE_i,j^internal 21: Calculate inter-cluster similarity Si,jS_i,j for each pair of clusters 22: while ∃Si,j>Ts∃ S_i,j>T_s (optional: Nc>Tn,finalN_c>T_n,final) do 23: i,j←argmaxi,j,i≠jSi,j,i<j\i,j\← _i,j,i≠ jS_i,j,i<j 24: L(xj)|L(xj)=j←iL(x_j) |_L(x_j)=j← i 25: L(xj)|L(xj)>j←L(xj)−1L(x_j) |_L(x_j)>j← L(x_j)-1 26: Update similarity matrix Vi,jlinkage,Ei,jlinkage,V_i,j^linkage,E_i,j^linkage, S 27: end while Based on the interpretation above, the proposed algorithm differs from traditional methods in three key aspects: (1) providing a more detailed description of the KNN connection subgraph structure through element categorization to separate vertices and edges into internal and interconnected components, representing intra-cluster and inter-cluster similarity respectively; (2) incorporating density and randomness information into similarity estimation; and (3) focusing on boundary connection regions of sub-clusters to achieve a more refined characterization. Consequently, the proposed algorithm is expected to achieve enhanced robustness and adaptivity. 4. Experimental Results and Discussion 4.1. Clustering Performance on Synthetic Datasets For evaluation of the proposed clustering algorithm, ten synthetic datasets are used including 2circles, Halfkernel, Aggregation, Flame, Jain, Pathbased, R15, Spiral, Two circle noise, and Compound (Fränti and Sieranoja, 2018; Wang et al., 2020). The proposed DHC-ECS algorithm and the hierarchical algorithm with traditional similarity metrics (minimum distance, maximum distance, centroid distance, mean distance (Guha et al., 1998)), as well as several recently proposed and representative algorithms, including an improved Chameleon algorithm (ACHAMELEON) (Guo et al., 2019a), reverse-nearest-neighbor-based DBSCAN (RNN-DBSCAN)(Bryant and Cios, 2018), multi-center clustering by fast search and find of density peak (McDPC) (Wang et al., 2020), Gaussian kernel based robust mean-shift clustering (G-RMS)(Cariou et al., 2022), are tested on these datasets. The clustering results of our proposed method are illustrated in Fig. 3, where different colors represent distinct detected clusters, and misclassified points are marked by black circles. We can see that across all datasets, the majority of points are correctly clustered, except for a few points with ambiguous affiliation in the KNN connection regions of sub-clusters. Some external evaluation indices including Normalized Mutual Information (NMI) (Manning, 2009), Adjusted Rand Index (ARI) (Vinh et al., 2010), Fowlkes and Mallows index (FMI) (Powers, 2011) and Purity (Manning, 2009) are used to quantify the performance. To ensure a fair comparison, the Euclidean distance or the geodesic distance is adopted for all baseline algorithms other than G-RMS, depending on the dataset features and clustering performance. The evaluation results are listed in Table LABEL:table:evaluation_index, with corresponding parameters that are applied for each dataset being listed in Table 2. Figure 3. Clustering results on synthetic datasets (The points that are wrongly categorized are circled in black). (a) 2 circles. (b) Aggregation. (c) Halfkernel. (d) Flame. (e) Jain. (f) Pathbased. (g) R15. (h) Spiral. (i) Two circles noise. (j) Compound. From these evaluation indices and the applied parameters, we can conclude that (1) Hierarchical clustering method based on traditional similarity metrics (minimum distance, maximum distance, centroid distance, mean distance) performs quite unstably on these datasets, due to the different features of data distributions. (2) Apart from Spiral, Pathbased, and Compound, the ACHAMELEON algorithm performs well on most datasets with NMI larger than 0.97. (3) RNN-DBSCAN and McDPC perform well on most datasets except Halfkernel for RNN-DBSCAN, and Compound for McDPC. In addition, the parameter tuning for these two algorithms is heuristic (Bryant and Cios, 2018; Wang et al., 2020) and time-consuming to obtain optimal results. Moreover, since the McDPC algorithm relies on the decision graph defined by the local density and the δ distance (Wang et al., 2020), the experiments indicate that representative points belonging to different clusters but exhibiting similar decision features may be wrongly classified to the same clusters. Besides, the G-RMS algorithm is applicable to all datasets except single-center datasets (e.g., 2circles) or nested datasets (e.g., Compound). (4) Although the clustering results of the proposed DHC-ECS algorithm are not the best for all datasets, it exhibits better robustness and obtains good results for all these datasets (e.g, the NMI values for all the 10 datasets are larger than 0.95). Furthermore, although these datasets exhibit distinct features, the parameter applied to all the datasets are quite similar as shown in Table 2, except the threshold of similarity for stop condition (the mean value of TsT_s is around 0.38 and the variation is moderate). Meanwhile, TsT_s has an intuitive interpretation corresponding to the clustering granularity—a smaller threshold allows more sub-clusters to be merged, resulting in coarser clustering results, whereas a larger threshold produces finer partitions. This facilitates the parameter settings. To summarize, these results provide empirical evidence for the existence of intrinsic thresholds. In conclusion, the proposed DHC-ECS algorithm achieves more robust performance across these diverse synthetic datasets, compared with traditional and improved hierarchical clustering methods, as well as several recently proposed density-based clustering approaches. However, it is worth noting that due to the influence of the “curse of dimensionality”(Beyer et al., 1999), both distance and density estimations, as well as structural information should be re-evaluated in the high-dimensional spaces. Therefore, further investigation is required to evaluate the effectiveness of the DHC-ECS algorithm when applied to high-dimensional datasets in the future. Table 1. Performance Evaluation on Synthetic Datasets. Dataset Method NMI ARI FMI Purity min 1.000 1.000 1.000 1.000 max 1.000 1.000 1.000 1.000 cen 1.000 1.000 1.000 1.000 mean 1.000 1.000 1.000 1.000 2circles AChameleon 1.000 1.000 1.000 1.000 RNN-DBSCAN 1.000 1.000 1.000 1.000 McDPC 1.000 1.000 1.000 1.000 G-RMS 0.623 0.645 0.901 0.902 DHC-ECS 1.000 1.000 1.000 1.000 min 0.832 0.696 0.812 0.827 max 0.900 0.760 0.859 0.957 cen 0.993 0.994 0.998 0.998 mean 0.846 0.752 0.817 0.827 Aggregation AChameleon 0.990 0.994 0.996 0.996 RNN-DBSCAN 0.996 0.998 0.999 0.999 McDPC 1.000 1.000 1.000 1.000 G-RMS 0.988 0.993 0.996 0.996 DHC-ECS 0.990 0.994 0.996 0.996 min 1.000 1.000 1.000 1.000 max 1.000 1.000 1.000 1.000 cen 1.000 1.000 1.000 1.000 mean 1.000 1.000 1.000 1.000 Halfkernel AChameleon 1.000 1.000 1.000 1.000 RNN-DBSCAN 0.743 0.729 0.884 1.000 McDPC 1.000 1.000 1.000 1.000 G-RMS 0.756 0.739 0.891 0.821 DHC-ECS 1.000 1.000 1.000 1.000 min 0.073 -0.041 0.665 0.665 max 0.088 -0.045 0.659 0.638 cen 0.024 0.013 0.647 0.646 mean 0.161 0.163 0.671 0.725 Flame AChameleon 1.000 1.000 1.000 1.000 RNN-DBSCAN 0.935 0.972 0.992 0.996 McDPC 1.000 1.000 1.000 1.000 G-RMS 0.888 0.934 0.983 0.983 DHC-ECS 0.971 0.988 0.996 1.000 min 1.000 1.000 1.000 1.000 max 1.000 1.000 1.000 1.000 cen 1.000 1.000 1.000 1.000 mean 1.000 1.000 1.000 1.000 Jain AChameleon 1.000 1.000 1.000 1.000 RNN-DBSCAN 1.000 1.000 1.000 1.000 McDPC 1.000 1.000 1.000 1.000 G-RMS 0.884 0.945 0.960 0.260 DHC-ECS 1.000 1.000 1.000 1.000 min 0.253 0.080 0.550 0.510 max 0.113 0.088 0.518 0.513 cen 0.539 0.453 0.681 0.733 mean 0.297 0.117 0.569 0.570 Pathbased AChameleon 0.905 0.930 0.977 0.977 RNN-DBSCAN 0.876 0.916 0.971 0.973 McDPC 1.000 1.000 1.000 1.000 G-RMS 0.683 0.635 0.760 0.190 DHC-ECS 0.953 0.969 0.990 0.990 min 0.952 0.853 0.904 0.863 max 0.923 0.788 0.852 0.802 cen 0.989 0.987 0.993 0.993 mean 0.837 0.427 0.705 0.668 R15 AChameleon 0.992 0.989 0.995 0.995 RNN-DBSCAN 0.988 0.982 0.992 0.992 McDPC 0.977 0.923 0.952 0.930 G-RMS 0.993 0.991 0.996 0.930 DHC-ECS 0.984 0.979 0.990 0.995 min 0.259 0.069 0.529 0.529 max 0.259 0.069 0.509 0.529 cen 0.345 0.220 0.625 0.577 mean 0.102 0.009 0.492 0.397 Spiral AChameleon 1.000 1.000 1.000 1.000 RNN-DBSCAN 1.000 1.000 1.000 1.000 McDPC 1.000 1.000 1.000 1.000 G-RMS 1.000 1.000 1.000 1.000 DHC-ECS 1.000 1.000 1.000 1.000 min 0.568 0.473 0.831 0.836 max 0.342 0.131 0.651 0.620 cen 0.321 0.117 0.660 0.592 mean 0.316 0.112 0.661 0.661 Two circles AChameleon 1.000 1.000 1.000 1.000 noise RNN-DBSCAN 0.969 0.979 0.994 1.000 McDPC 1.000 1.000 1.000 1.000 G-RMS 0.734 0.683 0.808 0.871 DHC-ECS 1.000 1.000 1.000 1.000 min 0.762 0.548 0.721 0.777 max 0.810 0.661 0.813 0.847 cen 0.899 0.856 0.885 0.882 mean 0.789 0.682 0.774 0.777 Compound AChameleon 0.789 0.607 0.768 0.855 RNN-DBSCAN 0.878 0.879 0.883 0.917 McDPC 0.943 0.973 0.977 0.980 G-RMS 0.780 0.691 0.766 0.018 DHC-ECS 0.979 0.990 0.993 0.993 Table 2. Parameter Settings of the Proposed Method Applied for the Synthetic Datasets Dataset K TsT_s TnT_n r 2 circles 10 0.38 N N 3 Aggregation 10 0.55 N N 3 Halfkernel 10 0.23 N N 3 Flame 10 0.42 N N 3 Jain 10 0.14 N N 3 Pathbased 10 0.38 N N 3 R15 10 0.38 N N 3 Spiral 8 0.38 N N 3 Two circles noise 10 0.43 N N 3 Compound 7 0.51 0.95N N 3 4.2. Computational Complexity The computational complexity of the proposed DHC-ECS algorithm is mainly determined by the hierarchical agglomerative merging procedure. In the first stage, the pairwise distance matrix is first constructed, requiring O(N2)O(N^2) time for a dataset containing N observations. The similarity matrix is then initialized based on the average inter-cluster distance. During each agglomerative iteration, the pair of clusters with the highest similarity is merged, followed by updating the similarities between the newly generated cluster and the remaining clusters. Since there are initially N sub-clusters and approximately N−TnN-T_n merging operations are performed, where TnT_n denotes the predefined number of sub-clusters after the first stage, the overall computational complexity of the first stage is O(N3)O(N^3) under a straightforward implementation, which is consistent with the naive hierarchical clustering and can be reduced to O(N2logN)O(N^2 N) through a priority-queue implementation as discussed in (Schütze et al., 2008). In the second stage, the KNN connection subgraphs are first constructed, requiring O(Tn2)O(T_n^2) time using exhaustive nearest-neighbor search (or O(TnlogTn)O(T_n T_n) for low-dimensional datasets when efficient nearest-neighbor search algorithms are adopted). Subsequently, the KNN connection subgraph is extracted for each neighboring cluster pair, and the proposed similarity indices, including LC, LS, DS, and CV, are computed only for cluster pairs connected by the ECS. Assuming that the average number of neighboring clusters remains bounded, the number of candidate cluster pairs at the t-th merging iteration is approximately O(Nt)O(N^t), where NtN^t denotes the current number of clusters. Furthermore, since the number of preliminary sub-clusters has already been reduced to TnT_n (Tn≪NT_n N, typically Tn≈NT_n≈ N), and the second-stage merging terminates at a much smaller number of clusters L, the overall complexity of the second-stage merging procedure can be approximated as O(Tn2)O(T_n^2) given that L is typically much smaller than TnT_n. Therefore, the complexity of the second-stage agglomerative merging is significantly smaller than that of the first stage, thus the overall worst-case computational complexity of DHC-ECS is dominated by the first-stage hierarchical merging and is given by O(N3)+O(Tn2)≈O(N3)O(N^3)+O(T_n^2)≈ O(N^3). The space complexity is mainly determined by the storage of the pairwise distance, similarity matrix, and the KNN graph, resulting in an overall space complexity of O(N2)O(N^2). Compared with representative density-based clustering algorithms, such as RNN-DBSCAN, McDPC, and G-RMS, whose computational complexities are typically around O(N2)O(N^2)(Bryant and Cios, 2018; Wang et al., 2020; Cariou et al., 2022), the proposed DHC-ECS incurs a higher worst-case computational cost because of the iterative hierarchical merging procedure. Nevertheless, unlike conventional hierarchical clustering algorithms that evaluate all cluster pairs during each merging iteration, DHC-ECS computes the proposed similarity only for cluster pairs connected through the ECS. Consequently, the practical computational cost of the second-stage is usually much lower than that of exhaustive hierarchical merging, especially for sparse neighborhood graphs. In return for the additional computational cost, DHC-ECS provides a substantially richer characterization of inter-cluster relationships by jointly exploiting graph connectivity, local density, and structural information within KNN connection regions, leading to improved robustness on datasets with heterogeneous densities and complex cluster structures. 5. Conclusion In this paper, a novel two-stage density-aware hierarchical clustering algorithm based on element-categorized KNN connection subgraphs is proposed. In the first stage, we construct preliminary clusters using a greedy algorithm. In the second stage, the ECS is proposed to represent the connections between sub-clusters, and a new similarity metric is formulated, considering not only the point connectivity but also the density information. The proposed DHC-ECS algorithm is evaluated on ten widely-used synthetic datasets with heterogeneous distributions. Comparative analyses are conducted against hierarchical clustering methods based on traditional similarity metrics, as well as several representative baseline clustering algorithms, including an improved hierarchical clustering algorithm (ACHAMELEON), the density-based algorithms RNN-DBSCAN, McDPC, and a robust mean-shift algorithm (G-RMS). For quantitative comparisons, four external evaluation indices, including NMI, ARI, FMI and Purity, are calculated. Experimental results demonstrate that the proposed algorithm exhibits superior robustness and performs well across all these datasets compared to the aforementioned algorithms. This highlights the effectiveness and applicability of the DHC-ECS algorithm to obtain more refined clustering results across datasets with different features, including convex and non-convex shapes, uniform and non-uniform densities, balanced or unbalanced distributions, single-centered or multi-centered structures. Future work includes conducting extended experiments on high-dimensional datasets, and searching for improvements on computational complexity to accommodate to larger datasets. References Bryant and Cios [2018] Avory Bryant and Krzysztof Cios. RNN-DBSCAN: A density-based clustering algorithm using reverse nearest neighbor density estimates. IEEE Transactions on Knowledge and Data Engineering, 30(6):1109–1121, 2018. doi: 10.1109/TKDE.2017.2787640. Khan et al. [2014] Kamran Khan, Saif Ur Rehman, Kamran Aziz, Simon Fong, and S. Sarasvady. DBSCAN: Past, present and future. In The Fifth International Conference on the Applications of Digital Information and Web Technologies (ICADIWT 2014), pages 232–238, 2014. doi: 10.1109/ICADIWT.2014.6814687. Guha et al. [1998] Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim. CURE: An efficient clustering algorithm for large databases. ACM Sigmod record, 27(2):73–84, 1998. doi: 10.1145/276305.276312. Guha et al. [2000] Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim. ROCK: A robust clustering algorithm for categorical attributes. Information systems, 25(5):345–366, 2000. doi: 10.1109/ICDE.1999.754967. Karypis et al. [1999] George Karypis, Eui-Hong Han, and Vipin Kumar. Chameleon: Hierarchical clustering using dynamic modeling. computer, 32(8):68–75, 1999. doi: 10.1109/2.781637. Nazari et al. [2015] Zahra Nazari, Dongshik Kang, M. Reza Asharif, Yulwan Sung, and Seiji Ogawa. A new hierarchical clustering algorithm. In 2015 International Conference on Intelligent Informatics and Biomedical Sciences (ICIIBMS), pages 148–152, 2015. doi: 10.1109/ICIIBMS.2015.7439517. Nazari and Kang [2018] Zahra Nazari and Dongshik Kang. A new hierarchical clustering algorithm with intersection points. In 2018 5th IEEE Uttar Pradesh Section International Conference on Electrical, Electronics and Computer Engineering (UPCON), pages 1–5, 2018. doi: 10.1109/UPCON.2018.8596795. Guo et al. [2019a] Dongwei Guo, Jingjing Zhao, and Jici Liu. Research and application of improved CHAMELEON algorithm based on condensed hierarchical clustering method. In Proceedings of the 2019 8th international conference on networks, communication and computing, pages 14–18, 2019a. Cao et al. [2018] Xiaoxiao Cao, Tianyun Su, Pengyu Wang, Guoyu Wang, Zhihan Lv, and Xinfang Li. An optimized CHAMELEON algorithm based on local features. In Proceedings of the 2018 10th International Conference on Machine Learning and Computing, pages 184–192, 2018. Ester et al. [1996] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. Density-based spatial clustering of applications with noise. In Int. Conf. knowledge discovery and data mining, volume 240, 1996. Rodriguez and Laio [2014] Alex Rodriguez and Alessandro Laio. Clustering by fast search and find of density peaks. science, 344(6191):1492–1496, 2014. Guo et al. [2024] Limin Guo, Weijia Qin, Zhi Cai, and Xing Su. Hybrid clustering algorithm based on improved density peak clustering. Applied Sciences, 14(2):715, 2024. Comaniciu and Meer [1999] Dorin Comaniciu and Peter Meer. Mean shift analysis and applications. In Proceedings of the seventh IEEE international conference on computer vision, volume 2, pages 1197–1203. IEEE, 1999. Campello et al. [2015] Ricardo JGB Campello, Davoud Moulavi, Arthur Zimek, and Jörg Sander. Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data (TKDD), 10(1):1–51, 2015. Xu et al. [2016] Ji Xu, Guoyin Wang, and Weihui Deng. DenPEHC: Density peak based efficient hierarchical clustering. Information Sciences, 373:200–218, 2016. Neto et al. [2019] Antonio Cavalcante Araujo Neto, Jörg Sander, Ricardo JGB Campello, and Mario A Nascimento. Efficient computation and visualization of multiple density-based clustering hierarchies. IEEE Transactions on Knowledge and Data Engineering, 33(8):3075–3089, 2019. Zhu et al. [2022] Ye Zhu, Kai Ming Ting, Yuan Jin, and Maia Angelova. Hierarchical clustering that takes advantage of both density-peak and density-connectivity. Information Systems, 103:101871, 2022. Wang and Li [2025] Renmin Wang and Jie Li. Fast sparse representative tree splitting via local density for large-scale clustering. Scientific Reports, 15(1):29398, 2025. Shao et al. [2018] Junming Shao, Qinli Yang, Zhong Zhang, Jinhu Liu, and Stefan Kramer. Graph clustering with local density-cut. In International Conference on Database Systems for Advanced Applications, pages 187–202. Springer, 2018. Du et al. [2024] Xinyu Du, Fangfang Li, Xiaohua Li, and Ge Yu. ADPSCAN: Structural graph clustering with adaptive density peak selection and noise re-clustering. Applied Sciences, 14(15):6660, 2024. Hou et al. [2016] Jian Hou, Huijun Gao, and Xuelong Li. DSets-DBSCAN: A parameter-free clustering algorithm. IEEE Transactions on Image Processing, 25(7):3182–3193, 2016. Li et al. [2020] Xuelong Li, Han Zhang, Rong Wang, and Feiping Nie. Multiview clustering: A scalable and parameter-free bipartite graph fusion method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(1):330–344, 2020. Mahon and Lapata [2025] Louis Mahon and Mirella Lapata. K*-means: A parameter-free clustering algorithm. arXiv preprint arXiv:2505.11904, 2025. Ruspini et al. [2019] Enrique H. Ruspini, James C. Bezdek, and James M. Keller. Fuzzy clustering: A historical perspective. IEEE Computational Intelligence Magazine, 14(1):45–55, 2019. doi: 10.1109/MCI.2018.2881643. Guo et al. [2019b] Dongwei Guo, Jingjing Zhao, and Jici Liu. Research and application of improved CHAMELEON algorithm based on condensed hierarchical clustering method. In Proceedings of the 2019 8th international conference on networks, communication and computing, pages 14–18, 2019b. Barton et al. [2019] Tomas Barton, Tomas Bruna, and Pavel Kordik. Chameleon 2: an improved graph-based clustering algorithm. ACM Transactions on Knowledge Discovery from Data (TKDD), 13(1):1–27, 2019. Jeong et al. [2013] Kyo-Sung Jeong, Seok-Ho Yoon, Suk-Soon Song, Sang-Chul Lee, Minsoo Ryu, Sang-Wook Kim, and Byung-Soo Jeong. Data partitioning in hierarchical clustering: A parameter-insensitive approach. International Information Institute (Tokyo). Information, 16(10):7699, 2013. Singh and Ahuja [2025] Priyanshu Singh and Kapil Ahuja. Chameleon2++: An efficient and scalable variant of chameleon clustering. arXiv preprint arXiv:2501.02612, 2025. Fränti and Sieranoja [2018] Pasi Fränti and Sami Sieranoja. K-means properties on six clustering benchmark datasets, 2018. URL http://cs.uef.fi/sipu/datasets/. Wang et al. [2020] Yizhang Wang, Di Wang, Xiaofeng Zhang, Wei Pang, and You Zhou. McDPC: multi-center density peak clustering. Neural Computing and Applications, 32(17), 2020. doi: 10.1007/s00521-020-04754-5. Cariou et al. [2022] Claude Cariou, Steven Le Moan, and Kacem Chehdi. A novel mean-shift algorithm for data clustering. IEEE Access, 10:14575–14585, 2022. doi: 10.1109/ACCESS.2022.3147951. Manning [2009] Christopher D Manning. An introduction to information retrieval. 2009. Vinh et al. [2010] Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11:2837–2854, 2010. Powers [2011] David MW Powers. Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation. Jonunal of Machine Learning Technologies, 2:2229–3981, 2011. Beyer et al. [1999] Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. When is “nearest neighbor” meaningful? In Database Theory—ICDT’99: 7th International Conference Jerusalem, Israel, January 10–12, 1999 Proceedings 7, pages 217–235. Springer, 1999. Schütze et al. [2008] Hinrich Schütze, Christopher D Manning, and Prabhakar Raghavan. Introduction to information retrieval, volume 39. Cambridge University Press Cambridge, 2008.