---
title: "Discerning Linkage-Based Algorithms among Hierarchical Clustering Methods"
authors:
  - "Margareta Ackerman"
  - "Shai Ben-David"
doi: "10.5591/978-1-57735-516-8/IJCAI11-195"
url: "https://ijcai.org/proceedings/2011/195"
pdf: "https://ijcai.org/proceedings/2011/0195.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "1140-1144"
track: ""
keywords:
---

# Discerning Linkage-Based Algorithms among Hierarchical Clustering Methods

Margareta Ackerman, Shai Ben-David

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 1140-1144. DOI: [10.5591/978-1-57735-516-8/IJCAI11-195](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-195)

## Abstract

Selecting a clustering algorithm is a perplexing task. Yet since different algorithms may yield dramatically different outputs on the same data, the choice of algorithm is crucial. When selecting a clustering algorithm, users tend to focus on cost-related considerations (software purchasing costs, running times, etc). Differences concerning the output of the algorithms are not usually considered. Recently, a formal approach for selecting a clustering algorithm has been proposed (Ackerman, Ben-David, and Loker, NIPS 2010). The approach involves distilling abstract properties of the input-output behavior of different clustering paradigms and classifying algorithms based on these properties. In this paper, we extend this approach into the hierarchical setting. 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 algorithms. 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.