Hierarchical Clustering with Prototypes: Minimax Linkage

• Activity Number: 479
• Type: Contributed
• Date/Time: Wednesday, August 4, 2010 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Jacob Bien*+ and Rob Tibshirani
• Companies: Stanford University and Stanford University
• Keywords: hierarchical clustering ; prototypes ; clustering ; dendrogram ; interpretability

Abstract

We investigate minimax linkage, a recently introduced but little-studied linkage for agglomerative hierarchical clustering. Minimax linkage associates with every interior node of the dendrogram a prototype chosen from the original dataset. Cutting a minimax linkage tree at any height induces a clustering of the data that is easily interpretable and has connections to set cover. We show that minimax linkage possesses a number of desirable theoretical properties, establishing its viability as a reliable method. Additionally, and more importantly, we demonstrate how it produces dendrograms that may be of greater use to scientists than those from standard linkages. We provide an efficient implementation, which is available as an R package, and illustrate the method on a study of words from encyclopedia articles.