title: Hierarchical Clustering With Prototypes via Minimax Linkage.
abstract: Agglomerative hierarchical clustering is a popular class of methods for understanding the structure of a dataset. The nature of the clustering depends on the choice of linkage-that is, on how one measures the distance between clusters. In this article we investigateminimax linkage, a recently introduced but little-studied linkage. Minimax linkage is unique in naturally associating a prototype chosen from the original dataset with every interior node of the dendrogram. These prototypes can be used to greatly enhance the interpretability of a hierarchical clustering. Furthermore, we prove that minimax linkage has a number of desirable theoretical properties; for example, minimax-linkage dendrograms cannot have inversions (unlike centroid linkage) and is robust against certain perturbations of a dataset. We provide an efficient implementation and illustrate minimax linkage's strengths as a data analysis and visualization tool on a study of words from encyclopedia articles and on a dataset of images of human faces.
authors.affiliation: Department of Statistics, Stanford University, Stanford, CA 94305.
authors.forename: Jacob
authors.initials: J
authors.lastname: Bien
authors.affiliation: Department of Health Research and Policy and Department of Statistics, Stanford University, Stanford, CA 94305.
authors.forename: Robert
authors.initials: R
authors.lastname: Tibshirani
keywords: Agglomerative; Dendrogram; Unsupervised learning