Data clustering:50years beyond k-means翻译 - 图文

簇可以被定义为在特征空间中由低密度区域分开的高密度区域。算法根据这个簇的定义直接搜索特征空间中连通的稠密区域。不同的算法使用不同的连通性定义。Jarvis-Patrick算法定义一对点之间的相似度为它们共享的邻近点的数量，临近点是指出现在某一点的一定半径区域内的点（Frank 和 Todeschini，1994）。Ester et al.(1996)提出了和Jarvis-Patrick算法相似的DBSCAN聚类算法。它通过使用Parzen窗方法估计密度，直接搜索连通的稠密区域。Jarvis-Patrick算法和DBSCAN的性能依赖于两个参数：距离角度的邻域尺寸和一个簇的邻域内包含的点的最小数量。另外，许多概率模型被开发用于数据聚类，即通过混合概率模型模拟密度函数。这些方法假设数据由一个混合分布生成，即每个簇被一个或多个混合分布的组合来描述（McLachlan和Basford，1987）。EM算法（Dempster et al.,1977）经常被用来推断混合模型的参数。包括潜在狄利克雷分布（LDA）（Bleiet al.2003）、弹球分布模型（Li和McCallum，2006）和无指导数据聚类图形模型（Welling et al.2005）在内的几个贝叶斯方法已经被开发来改进用于数据聚类的混合模型。

虽然基于密度的方法，尤其是无参数的基于密度的方法因为可以处理任意形状的簇的内在性质而很有吸引力，但是它们在处理高维数据时却有局限性。当数据是高维的，特征空间往往是高维的，这使得从低密度区域中区分高密度区域变得很难。子空间聚类算法通过找到嵌入在低维子空间的给定高维数据的簇来克服这个局限性。CLIQUE（Agrawal et al.,1998）是一个可伸缩的聚类算法，设计用于寻找数据中有高密度簇的子空间。因为它只在低维度子空间进行估计，CLIQUE并不会遇到高维问题。

图论聚类，有时也被叫做谱聚类，用一个加权的图代表数据点。连接两个节点之间的边由对间相似度加权。主要思想是：划分节点为A和B两个子集使得剪裁尺寸，也就是被分配给连接节点集A和B的边的权值的和是最小的。最初用于解决这个问题的算法是最小剪切算法，它经常导致两个簇有不平衡的尺寸。后来比率剪切算法采用了一种簇尺寸（一个簇中的数据点的数量）约束（Hagen和Kahng，1992）。另一种叫做规范化剪切的带有簇尺寸（簇的数据量或者单个簇内的边的权值和）的近似基于图剪切的有效聚类算法是由Shi和Malik（2000）第一次提出的。它的多级版本由Yu和Shi（2003）提出。Meila和Shi（2001）

提出了谱聚类的一种马尔科夫随机漫步观点并提出了可以处理任意簇数目的修正规范化剪切（MNCut）算法。Ng et al.(2001)提出了另一种谱聚类算法的变体，它从核心矩阵的规范化特征向量中导出一个新数据表示方法。拉普拉斯特征映射（Belkin和Niyogi，2002）是另一种谱聚类方法，它基于图的拉普拉斯算子导出数据表示方法。Hofmann 和Buhmann（1997）为聚类提出了一种确定性退火算法，它利用数据对象间的邻近衡量来表示数据。Pavan和Pelillo（2007）通过将最大支配集（Motzkin和Straus，1965）和簇相联系明确的表达了对间聚类问题，它是一个图中簇的一种连续产生方法。

有些聚类算法有一个信息理论公式。比如，Roberts et al.(2001)提出的最小熵方法假设数据是由一个混合模型生成的并且每个簇是使用一个半参数概率密度模式化的。参数通过最大化簇中数据点的无条件密度和有条件密度之间的KL散度来进行估计。这使得有条件和无条件的密度之间的重叠最小化，因此将簇分隔开。换句话说，这个公式是利用最小化所观察数据的预期熵的方法的结果。信息瓶颈方法（Tishby et al.，1999）被提出来作为速率失真理论和应用有损耗数据压缩观点的一般化。简单的说，给定两个随机变量的联合分布，信息瓶颈在最大化保留两个变量间的相互信息的前提下，压缩其中一个变量。（Slonim和Tishby,2000）展示了这种方法在文档聚类中的应用，其中的两个随机变量是单词和文档。单词通过使得和文档之间的信息得以最大化的保留来聚类，使用聚类后的单词，文档通过使得聚类后单词和聚类后文档之间的相互关系得到最大化的保留来聚类。

3. 用户的困境

尽管有如此大量的聚类算法，而且这些算法也在许多不同的领域成功应用，聚类仍然是一个困难的问题。这可以归因于簇定义本身的模糊性以及定义一个合适的相似度尺度和目标函数。

（Jain和Dubes，1998）强调以下聚类的主要挑战，这即使到今天来看依然是中肯的。

（a）什么是一个簇？ （b）应该使用哪些特征？

（c）数据需要标准化吗？ （d）数据是否有异常值？ （e）怎样定义对间相似度？ （f）数据中有多少簇？ （g）应该使用哪个聚类方法？ （h）数据是否有聚类趋势？ （i）发现的簇和划分是否有效？

以下我们会强调和举例说明其中一些挑战。 3.1. 数据表示法

数据表示是影响聚类算法性能最重要的因素之一。如果表示法（特征的选择）很好，那么簇很有可能是紧凑而孤立的，即使是一个像K-means这样的简单聚类算法也能找到它们。可惜的是，没有通用的表示法，表示法的选择必须在领域知识的指导下进行。图5a表示的是一个K-means不能将其划分为两个自然簇的数据集。通过K-means得到的划分由图5a中的虚线表示。然而当a中同样的数据点利用数据计算得来的RBF相似度矩阵的顶层二维特征向量使其表示成图b。它们分离的非常好使得用K-means来聚类这些数据非常简单（Ng et al.,2001）。

图5. 一个好的表示法的重要性。图（a）表示K-means无法找出“自然”簇的“两环”数据集；虚线表示K-means在参数K = 2情况下获得的线性簇分离边界；图（b）是使用RBF核心计算基于数据的图拉普拉斯算子的顶层两个特征向量的图（a）的一种新的表示法；K-means现在可以简单的找到两个簇。

3.2. 分组的目的

数据的表示和分组的目的密切联系。表示法必须和用户最终的目的相配合。（Pampalk et al.,2003）中用13个布尔特征表示16种动物的例子证明表示法是怎样影响分组的。动物通过关于它们的外貌和活动的13个布尔特征表示。当更多的特征是外貌特征而不是活动特征时，动物被分成哺乳动物和鸟类。另一方面，当更多的特征是是活动特征时，数据集被分成食肉动物和非食肉动物。图6中的两个划分同样有效，它们都揭示了数据有意义的结构。要获得想要的聚类结果就要靠用户仔细的选择表示法。

图6. 数据特征的不同权重导致数据的不同划分。16种动物由与外形和活动相关的13个布尔特征值表示。图（a）表示当基于外形的特征获得较大权重时的划分结果；图（b）表示当基于活动的特征获得较大权重时的划分结果。图（a）和（b）引用自Pampalk et al.(2003),被称之为“热图”，其中颜色代表一个位置的样本密度；颜色越暖，密度越大。

3.3. 簇的数目

自动确定簇的数目是数据聚类中最困难的问题之一。大部分自动确定簇数目的方法是将其转化为模型选择问题。通常，聚类算法在不同的K值下运行，然后根据之前定义的准则选择最佳的K值。Figueiredo和Jain（2002）使用最小信