New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering

• URL: http://arxiv.org/abs/2405.00937v1
• Date: Thu, 2 May 2024 01:39:30 GMT
• Title: New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering
• Abstract summary: 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.
• Score: 10.409652277630133
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Linkage methods are among the most popular algorithms for hierarchical clustering. Despite their relevance the current knowledge regarding the quality of the clustering produced by these methods is limited. Here, 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, which corroborates the common perception that the former is more suitable than the latter when the goal is producing compact clusters. We also show that our techniques can be employed to derive upper bounds on the cohesion of a class of linkage methods that includes the quite popular average-link.

Related papers

• 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)
• Chamfer-Linkage for Hierarchical Agglomerative Clustering [9.30413560778001]
  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.
  arXiv  Detail & Related papers  (2026-02-11T02:36:14Z)
• 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)
• On the cohesion and separability of average-link for hierarchical agglomerative clustering [5.494111035517599]
  Average-link is widely recognized as one of the most popular and effective methods for building hierarchical agglomerative clustering. We present a study of the performance of average-link in metric spaces, regarding several natural criteria that capture separability and cohesion. We also present experimental results with real datasets that, together with our theoretical analyses, suggest that average-link is a better choice than other related methods when both cohesion and separability are important goals.
  arXiv  Detail & Related papers  (2024-11-07T19:31:00Z)
• Clustering Based on Density Propagation and Subcluster Merging [92.15924057172195]
  We propose a density-based node clustering approach that automatically determines the number of clusters and can be applied in both data space and graph space. Unlike traditional density-based clustering methods, which necessitate calculating the distance between any two nodes, our proposed technique determines density through a propagation process.
  arXiv  Detail & Related papers  (2024-11-04T04:09:36Z)
• 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)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Constrained Clustering and Multiple Kernel Learning without Pairwise Constraint Relaxation [15.232192645789485]
  We introduce a new constrained clustering algorithm that jointly clusters data and learns a kernel in accordance with the available pairwise constraints. We show that the proposed method outperforms existing approaches on a large number of diverse publicly available datasets.
  arXiv  Detail & Related papers  (2022-03-23T17:07:53Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  This paper explores the problem of clustering ensemble, which aims to combine multiple base clusterings to produce better performance than that of the individual one. We propose a novel low-rank tensor approximation-based method to solve the problem from a global perspective. Experimental results over 7 benchmark data sets show that the proposed model achieves a breakthrough in clustering performance, compared with 12 state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-12-16T13:01:37Z)
• 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)
• Hierarchical Correlation Clustering and Tree Preserving Embedding [3.821323038670061]
  We propose a hierarchical correlation clustering method that extends the well-known correlation clustering. In the following, we study unsupervised representation learning with such hierarchical correlation clustering.
  arXiv  Detail & Related papers  (2020-02-18T17:44:25Z)
• Toward Generalized Clustering through an One-Dimensional Approach [0.8122270502556374]
  An approach for detecting patches of separation between clusters is developed based on an agglomerative clustering, more specifically the single-linkage. The potential of this method is illustrated with respect to the analyses of clusterless uniform and normal distributions of points, as well as a one-dimensional clustering model characterized by two intervals with high density of points separated by a less dense interstice.
  arXiv  Detail & Related papers  (2020-01-01T16:52:05Z)

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.