Chamfer-Linkage for Hierarchical Agglomerative Clustering

• URL: http://arxiv.org/abs/2602.10444v1
• Date: Wed, 11 Feb 2026 02:36:14 GMT
• Title: Chamfer-Linkage for Hierarchical Agglomerative Clustering
• Abstract summary: We propose emphChamfer-linkage, a novel linkage function that measures the distance between clusters using the Chamfer distance.<n>We find that Chamfer-linkage consistently yields higher-quality clusterings than classical linkages.<n>Our results establish Chamfer-linkage as a practical drop-in replacement for classical linkage functions.
• Score: 9.30413560778001
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hierarchical Agglomerative Clustering (HAC) is a widely-used clustering method based on repeatedly merging the closest pair of clusters, where inter-cluster distances are determined by a linkage function. Unlike many clustering methods, HAC does not optimize a single explicit global objective; clustering quality is therefore primarily evaluated empirically, and the choice of linkage function plays a crucial role in practice. However, popular classical linkages, such as single-linkage, average-linkage and Ward's method show high variability across real-world datasets and do not consistently produce high-quality clusterings in practice. In this paper, we propose \emph{Chamfer-linkage}, a novel linkage function that measures the distance between clusters using the Chamfer distance, a popular notion of distance between point-clouds in machine learning and computer vision. We argue that Chamfer-linkage satisfies desirable concept representation properties that other popular measures struggle to satisfy. Theoretically, we show that Chamfer-linkage HAC can be implemented in $O(n^2)$ time, matching the efficiency of classical linkage functions. Experimentally, we find that Chamfer-linkage consistently yields higher-quality clusterings than classical linkages such as average-linkage and Ward's method across a diverse collection of datasets. Our results establish Chamfer-linkage as a practical drop-in replacement for classical linkage functions, broadening the toolkit for hierarchical clustering in both theory and practice.

Related papers

• Cluster-Aware Matching via Laplacian Optimal Transport [1.9890930069402575]
  We propose a novel approach for cluster-aware matching based on Laplacian Optimal Transport (LapOT)<n>We show that LapOT indeed produces cluster-aware matching that leads to more consistent and meaningful alignments between point clouds.
  arXiv  Detail & Related papers  (2026-07-17T17:56:51Z)
• A Generic Framework for Fair Consensus Clustering in Streams [1.6398837165722515]
  We introduce a new generic algorithmic framework that integrates closest fair clustering with cluster fitting.<n>We extend our methods to the more general k-median consensus clustering problem.
  arXiv  Detail & Related papers  (2026-02-12T02:52:07Z)
• You Can Trust Your Clustering Model: A Parameter-free Self-Boosting Plug-in for Deep Clustering [73.48306836608124]
  DCBoost is a parameter-free plug-in designed to enhance the global feature structures of current deep clustering models.<n>By harnessing reliable local structural cues, our method aims to elevate clustering performance effectively.
  arXiv  Detail & Related papers  (2025-11-26T09:16:36Z)
• Parameter-Free Clustering via Self-Supervised Consensus Maximization (Extended Version) [50.41628860536753]
  We propose a novel and fully parameter-free clustering framework via Self-supervised Consensus Maximization, named SCMax.<n>Our framework performs hierarchical agglomerative clustering and cluster evaluation in a single, integrated process.
  arXiv  Detail & Related papers  (2025-11-12T11:17:17Z)
• Graph Probability Aggregation Clustering [5.377020739388736]
  We propose a graph-based fuzzy clustering algorithm that unifies the global clustering objective function with a local clustering constraint.<n>The entire GPAC framework is formulated as a multi-constrained optimization problem, which can be solved using the Lagrangian method.<n>Experiments conducted on synthetic, real-world, and deep learning datasets demonstrate that GPAC not only exceeds existing state-of-the-art methods in clustering performance but also excels in computational efficiency.
  arXiv  Detail & Related papers  (2025-02-27T09:11:32Z)
• Anchor Learning with Potential Cluster Constraints for Multi-view Clustering [11.536710289572552]
  Anchor-based multi-view clustering (MVC) has received extensive attention due to its efficient performance.<n>We propose a noval method termed Anchor Learning with Potential Cluster Constraints for Multi-view Clustering (ALPC) method.
  arXiv  Detail & Related papers  (2024-12-21T07:43:05Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering [10.409652277630133]
  We improve the currently available bounds on the maximum diameter of the clustering obtained by complete-link for metric spaces. One of our new bounds, in contrast to the existing ones, allows us to separate complete-link from single-link in terms of approximation for the diameter.
  arXiv  Detail & Related papers  (2024-05-02T01:39:30Z)
• CCFC: Bridging Federated Clustering and Contrastive Learning [8.822947930471429]
  We propose a new federated clustering method named cluster-contrastive federated clustering (CCFC)<n>CCFC shows superior performance in handling device failures from a practical viewpoint.
  arXiv  Detail & Related papers  (2024-01-12T15:26:44Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Spatiotemporal k-means [39.98633724527769]
  We propose a twotemporal clustering method called k-means (STk) that is able to analyze multi-scale clusters. We show how STkM can be extended to more complex machine learning tasks, particularly unsupervised region of interest detection and tracking in videos.
  arXiv  Detail & Related papers  (2022-11-10T04:40:31Z)
• You Never Cluster Alone [150.94921340034688]
  We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation. We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one. By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
  arXiv  Detail & Related papers  (2021-06-03T14:59:59Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.