RECORD
New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering
Machine Learning · Submitted 2 May 2024
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Linkage methods are among the most popular algorithms for hierarchical clustering. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | Despite their relevance the current knowledge regarding the quality of the clustering produced by these methods is limited. | gap 0.99 | 0.05 | 0.02 | asserted 1.00 |
| s2 | Here, we improve the currently available bounds on the maximum diameter of the clustering obtained by complete-link for metric spaces. | contribution 0.97 | 0.95 | 0.50 | asserted 1.00 |
| s3 | 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. | interpretation 0.50 | 0.92 | 0.44 | asserted 0.85 |
| s4 | 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. | contribution 0.54 | 0.96 | 0.14 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
How the literature uses it
1 arXiv paper cite this in 15 sentences
Papers citing it · 10 sentences without a confident label
Builds on it 1 paper
-
Thus, to obtain our $(1+4lnn )k^1.59$ bound we combine the results of [ref] with Theorem [ref] while for the $k^1+1.59$ bound we add some new ideas/analysis on top of those from [ref] .
On the cohesion and separability of average-link for hierarchical agglomerative clustering · On the cohesion of average-link · 0.89
Uses its method or tool 1 paper
-
For a $k$-clustering $$, let $():=1/k ∑_i=i^k (C_i).$ As in [ref] , we use as the target clustering the one with minimum .
On the cohesion and separability of average-link for hierarchical agglomerative clustering · On the cohesion of average-link · 0.82
Compares with it 1 paper
-
[ref] shows that $()$ is $Ω( k )$ while [ref] shows that $()$ is $O( min{ k^1.30 , k^1.59 })$.
On the cohesion and separability of average-link for hierarchical agglomerative clustering · Related work · 0.81
Cites it as background 1 paper
-
There are works that present bounds on the approximation of regarding some criteria [ref] .
On the cohesion and separability of average-link for hierarchical agglomerative clustering · Related work · 1.00
What it cites
Cites as background 1 paper
-
Another relevant line aims to understand the theoretical properties (e.g. approximation guarantees) of algorithms widely used in practice, such as linkage methods [ref] .
Analysis of Agglomerative Clustering · Introduction · 0.93
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.