Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search
Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search
复制标题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Benjamin Moseley;Joshua R. Wang
中科院分区：
文献类型：
--
作者：
Benjamin Moseley;Joshua R. Wang
层次聚类是一种已经使用了几十年的数据分析方法。尽管这种方法被广泛使用，但它的分析基础还不够发达。拥有一个很好理解的基础将既支持当前使用的方法，又有助于指导未来的改进。本文的目标是给出一个分析框架，以便更好地理解在实践中看到的观察结果。本文考虑了Dasgupta提出的层次聚类问题框架的对偶问题。主要结果是，在实际应用中最流行的算法之一，平均链接凝聚聚类，对这一目标有一个很小的恒定逼近比。此外，本文还证明了使用二等分k-均值分裂聚类对同一目标的逼近比有一个很差的下界。然而，我们通过给出两个恒定逼近算法，证明了有一些分裂算法在这一目标上执行得很好。本文是为自然目标函数的广泛使用的分层算法建立保证的首批工作之一。这一目标和分析让我们深入了解这些流行的算法正在优化哪些方面，以及它们何时会表现良好。
Hierarchical clustering is a data analysis method that has been used for decades. Despite its widespread use, the method has an underdeveloped analytical foundation. Having a well understood foundation would both support the currently used methods and help guide future improvements. The goal of this paper is to give an analytic framework to better understand observations seen in practice. This paper considers the dual of a problem framework for hierarchical clustering introduced by Dasgupta. The main result is that one of the most popular algorithms used in practice, average linkage agglomerative clustering, has a small constant approximation ratio for this objective. Furthermore, this paper establishes that using bisecting k-means divisive clustering has a very poor lower bound on its approximation ratio for the same objective. However, we show that there are divisive algorithms that perform well with respect to this objective by giving two constant approximation algorithms. This paper is some of the first work to establish guarantees on widely used hierarchical algorithms for a natural objective function. This objective and analysis give insight into what these popular algorithms are optimizing and when they will perform well.