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 costrelated 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 [2]. The approach involves distilling abstract properties of the inputoutput behavior of different clustering paradigms and classifying algorithms based on these properties. In this paper, we extend the approach in [2] 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 linkagebased 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.