Hierarchical Clustering With Prototypes via Minimax Linkage
Hierarchical Clustering With Prototypes via Minimax Linkage
复制标题
DOI：
10.1198/jasa.2011.tm10183
复制
发表时间：
2011-09-01
影响因子：
3.7
通讯作者：
Tibshirani, Robert
中科院分区：
文献类型：
--
作者：
Bien, Jacob;Tibshirani, Robert
聚类分层聚类是理解数据集结构的一种流行方法。聚类的性质取决于连接的选择，也就是说，取决于如何测量聚类之间的距离。在本文中，我们研究极小极大连杆，这是一个最近被引入但研究很少的连杆。极大极小链接的独特之处在于将从原始数据集中选择的原型与树状图的每个内部节点自然地关联起来。这些原型可以用来极大地增强分层聚类的可解释性。进一步证明了极大极小连杆具有若干理想的理论性质；例如，极小极大连杆树形图不能有反转（不像质心连杆），并且对数据集的某些扰动具有鲁棒性。我们提供了一个有效的实现，并说明了极大极小链接作为一种数据分析和可视化工具的优势，用于研究百科全书文章中的单词和人脸图像数据集。
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 investigate minimax 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.