论文笔记13 -- （层次聚类）Performance guarantees for hierarchical clustering

《Performance guarantees for hierarchical clustering》 论文：http://cseweb.ucsd.edu/~dasgupta/papers/hier-jcss.pdf GitHub：https://github.com/jonfink/hcluster

Abstract

作者表示，对于任何度量空间中的任何数据集，都可以构建一个层次聚类，保证对于每个k，产生的k聚类的cost最多是最优k聚类的8倍。 这里，聚类的cost被认为是其聚类的最大半径。对于层次聚类，我们的算法在简单性和效率上和目前流行的聚集启发式算法相似，并且我们证明这些启发式算法具有无界逼近因子。

1.Introduction

n个数据点的层次聚类是将数据递归地划分为2、3、4、…n个类。通过划分其中一个类，可以使每个中间类更精细。图1显示了五点数据集的一种可能的层次聚类。

这种数据的等级表示长期以来一直是生物学家和社会科学家的主要内容，自60到70年代以来，它们一直是统计学家工具箱的标准组成部分。其受欢迎程度很容易理解。

在这里插入图片描述

它们不需要预先规定聚类的数量，允许在多个粒度级别上同时理解数据，并且可以使用一些简单、贪婪的启发式方法来构造它们。

能够以不同的细节级别查看数据是非常有用的，但是这些类相互嵌套的要求存在一些基本的困难。考虑图2的数据集，由欧几里得平面上的6个等距共线点组成。最常用的聚类cost function，如k-means，力求产生半径或直径较小的类。在这样的标准下，该数据的最佳2聚类（分成2组）是明确的，最佳的3聚类也是如此。 但是，它们在层次上是不兼容的。这就提出了一个令人不安的问题：通过要求层级结构，我们是否会陷入质量低劣的中间类？

在这里插入图片描述

为了更具建设性地重新阐述这一点，必须始终存在一个层次聚类，其中对于每个k，产生的k聚类（分组为k个类）在一些合理的成本函数下接近最优k聚类吗？ 正如我们已经看到的，很有可能通过合并最优k+1聚类的类不能获得最优的基于cost的k聚类。它们能被如此远的移除以至于它们甚至不能近似地协调成一个层次结构吗？尽管在层次聚类方面进行了大量理论研究（例如，参见[8]及其参考文献），但这一基本存在问题仍未得到解答。我们通过以下令人放心的结果解决它。

定理1 将聚类的cost作为其聚类的最大半径。然后，任何度量空间中的数据集都有一个分层的聚类，其中对于每个k，产生的k聚类的cost最多是最优k聚类的8倍。

注释 对我们的分析进行简单的修改表明，如果将聚类的cost视为其聚类的最大直径，则该结果也成立。

我们提出了一种构造这种层次结构的算法，其简单性和效率类似于层次聚类的标准启发式算法。它基于一组点的最远的第一次遍历，由Gonzalez[7]，用于密切相关的k中心问题的近似算法。他使用这种遍历进行聚类是巧妙的，事实上，对于他的结果，只需粗略检查其属性就可以了。对于层次聚类，我们会更详细地研究它，并需要在它的基础上进行构建。具体而言，n个数据点的最远的第一次遍历产生一系列“centers”μ1，…，μn使得对于任何k，这些中心的前k个定义了一个k-聚类，该聚类在最优因子2内。但是，以这种方式创建的n个类不是分层的。 我们的主要贡献是演示一种简单而优雅的方法，即使用遍历找到的信息来创建层次聚类。

我们的算法还有一个随机变量，具有更严格的近似常数。

定理2 在前一个定理的设置中，有一个随机算法，它产生一个分层的聚类，使得对于每个k，产生的k-聚类具有预期cost，最多是最优k-聚类的2e≈5.44倍。

与我们的算法不同，最常见的层次聚类启发式方法是自下而上的，从每个点的单独类开始，然后逐步合并两个“最近”的类，直到只剩下一个类为止。不同的方案以其亲密的概念来区分。在单链（single- linkage）聚类中，两个类之间的距离是它们最近的一对点之间的距离。在完全链（complete-linkage）聚类中，这是它们最远一对点之间的距离（因此，完全链明确地尝试最小化直径，这是我们的cost函数之一）。平均链（Average-linkage）有很多变种；在我们考虑的一个变种中，类之间的距离是它们平均值之间的距离[5]。

我们分析了这三种启发式的最坏情况，发现它们的近似比是无界的。

定理3 对于任何k，单链都能产生k-聚类，这是最优的乘法因子k，而平均和完全链可以通过乘法因子log2k来关闭。