A Framework for Parallelizing Hierarchical Clustering Methods
A Framework for Parallelizing Hierarchical Clustering Methods
复制标题
DOI：
10.1007/978-3-030-46150-8_5
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Silvio Lattanzi;Thomas Lavastida;Kefu Lu;Benjamin Moseley
中科院分区：
文献类型：
--
作者：
Silvio Lattanzi;Thomas Lavastida;Kefu Lu;Benjamin Moseley
层次聚类是数据挖掘、机器学习和统计中的基本工具。流行的层次聚类算法包括自上而下的分裂方法（例如二分k均值、k中值和k中心）和自下而上的凝聚方法（例如单链接、平均链接和质心链接）。不幸的是，只有少数可扩展的层次聚类算法是已知的，大多数基于单链接算法。因此，随着数据集的大小每天都在增加，迫切需要扩展其他流行的方法。我们引入了用于二等分 k 均值、k 中值、k 中心以及质心链接的高效分布式算法。特别是，我们首先形式化层次聚类算法的紧密度概念，然后使用这个概念来设计新的可扩展分布式方法，该方法在运行时间和解决方案的质量上具有强大的最坏情况界限。最后，我们通过实验证明所引入的算法是有效的并且接近其在实践中的顺序变体。
Hierarchical clustering is a fundamental tool in data mining, machine learning and statistics. Popular hierarchical clustering algorithms include top-down divisive approaches such as bisectingk-means,k-median, andk-center and bottom-up agglomerative approaches such as single-linkage, average-linkage, and centroid-linkage. Unfortunately, only a few scalable hierarchical clustering algorithms are known, mostly based on the single-linkage algorithm. So, as datasets increase in size every day, there is a pressing need to scale other popular methods.We introduce efficient distributed algorithms for bisectingk-means,k-median, andk-center as well as centroid-linkage. In particular, we first formalize a notion of closeness for a hierarchical clustering algorithm, and then we use this notion to design new scalable distributed methods with strong worst case bounds on the running time and the quality of the solutions. Finally, we show experimentally that the introduced algorithms are efficient and close to their sequential variants in practice.