New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering

Sanjoy Dasgupta, Eduardo Sany Laber
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:10185-10205, 2024.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-dasgupta24a, title = {New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering}, author = {Dasgupta, Sanjoy and Laber, Eduardo Sany}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {10185--10205}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/dasgupta24a/dasgupta24a.pdf}, url = {https://proceedings.mlr.press/v235/dasgupta24a.html}, 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.} }
Endnote
%0 Conference Paper %T New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering %A Sanjoy Dasgupta %A Eduardo Sany Laber %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-dasgupta24a %I PMLR %P 10185--10205 %U https://proceedings.mlr.press/v235/dasgupta24a.html %V 235 %X 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.
APA
Dasgupta, S. & Laber, E.S.. (2024). New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:10185-10205 Available from https://proceedings.mlr.press/v235/dasgupta24a.html.

Related Material