A Characterization of Linkage-Based Hierarchical Clustering
Abstract
The class of linkage-based algorithms is perhaps the most popular class of hierarchical algorithms. We identify two properties of hierarchical algorithms, and prove that linkage- based algorithms are the only ones that satisfy both of these properties. Our characterization clearly delineates the difference between linkage-based algorithms and other hierarchical methods. We formulate an intuitive notion of locality of a hierarchical algorithm that distinguishes between linkage-based and global hierarchical algorithms like bisecting $k$-means, and prove that popular divisive hierarchical algorithms produce clusterings that cannot be produced by any linkage-based algorithm.
Cite
Text
Ackerman and Ben-David. "A Characterization of Linkage-Based Hierarchical Clustering." Journal of Machine Learning Research, 2016.Markdown
[Ackerman and Ben-David. "A Characterization of Linkage-Based Hierarchical Clustering." Journal of Machine Learning Research, 2016.](https://mlanthology.org/jmlr/2016/ackerman2016jmlr-characterization/)BibTeX
@article{ackerman2016jmlr-characterization,
title = {{A Characterization of Linkage-Based Hierarchical Clustering}},
author = {Ackerman, Margareta and Ben-David, Shai},
journal = {Journal of Machine Learning Research},
year = {2016},
pages = {1-17},
volume = {17},
url = {https://mlanthology.org/jmlr/2016/ackerman2016jmlr-characterization/}
}