A Density-Adaptive Hybrid Linkage Criterion for Agglomerative Hierarchical Clustering

Hierarchical clustering is a widely used unsupervised learning technique due to its ability to uncover nested data structures without requiring prior knowledge of the number of clusters. However, the effectiveness of agglomerative hierarchical clustering strongly depends on the selected linkage criterion. Conventional linkage methods exhibit inherent limitations: single linkage is susceptible to the chaining effect, often producing elongated and poorly separated clusters, whereas complete linkage tends to generate overly compact clusters and may fragment naturally connected data groups. To address these challenges, this paper proposes a novel Density-Adaptive Hybrid Linkage (DAHL) criterion for agglomerative hierarchical clustering. The proposed method dynamically integrates single-linkage and complete-linkage distances through a density-driven adaptive weighting mechanism, enabling the clustering process to balance connectivity and compactness according to local cluster characteristics. Unlike conventional fixed-linkage strategies, the proposed criterion automatically adjusts its behavior during cluster formation without requiring user-defined tuning parameters. A theoretical analysis demonstrates that the proposed linkage remains bounded between the corresponding single-linkage and complete-linkage distances, thereby preserving desirable properties of both methods. Furthermore, an efficient clustering algorithm based on the proposed linkage criterion is developed. Experimental evaluations conducted on multiple benchmark datasets from the UCI Machine Learning Repository demonstrate that the proposed approach consistently outperforms traditional single-linkage, complete-linkage, and average-linkage methods in terms of Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), Silhouette Score (SS), and Davies–Bouldin Index (DBI). The results confirm that the proposed density-adaptive hybrid linkage criterion provides a robust and effective framework for hierarchical clustering across datasets exhibiting diverse structuraland density characteristics.