Characterization of Linkage-Based Clustering
March 13, 2013
Clustering is a central unsupervised learning task with a wide variety of applications. We discuss recent advances in clustering theory, including axiomatizing clustering and providing formal guidance for clustering algorithm selection, with an emphasis on a recent characterization of linkage-based algorithms.

Linkage-based clustering is one of the most commonly used and widely studied clustering paradigms. 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 clustering paradigms.

Joint work with Shai Ben-David and David Loker.