聚类分析及K均值算法讲解

吴裕雄

当今信息大爆炸时代，公司企业、教育科学、医疗卫生、社会民生等领域每天都在产生大量的结构多样的数据。产生数据的方式更是多种多样，如各类的：摄像头、传感器、报表、海量网络通信等等，面对这海量结构各式各样的数据，如果单是依靠人力来完成，是件非常不现实的事，但这些数据又包含着许多对我们有很高价值的信息。面对这样的矛盾，我们必须通过一些方法来科学、高效地分析、处理这些数据，最后输出能够让人或者机器作出无差别的行为判断。聚类分析——就是解决这类问题的一种典型方法，它是基于生活常识，运用数学抽象模型及科学度量的一种海量数据分析、处理的方法。借助这样的聚类分析方法，形成了三大经典的算法：K 均值、凝聚的层次聚类和DBSCAN。下面是具体的概念及K均值算法的介绍。

在现实客观自然界中，每一样事物都有其属性，世界上'' 没有一片完全相同的叶子''，最根本的原因是：每一样的事物本身的属性不是跟其它任何事物的完全相同。但是我们分析和描述客观自然事物的时候，往往是基于对某一事物重要的、突出的和具有普遍性的属性来进行归门别类。这就是：旨在理解的聚类。它体现的是一种由一般到特殊的科学逻辑思想方法。比如：竹叶、枫叶等树叶具有'' 叶子''这个类的全部属性，白猫、黑猫等不同品种的猫具有''猫''类的全部属性。通过这样的分类，我们可以把前两者叫做：叶子，把后两者叫做：猫。但并不是说它们之间完全没有相同的属性，比如：它们分化程度较低的细胞都可以进行有丝分裂，都有细胞的基本结构等等。只不过我们在日常生活中对于这些事物比较少提起、不明显的属性常常不拿来做分析和判断。因为根本就没有必要把每个事物的各个要素都'' 锱铢必较''，除非是对某一事物进行必要的详尽的调查和研究，否则全盘考虑每一事物的属性是很不现实、很不科学的。从这一方面来说：概念上有意义的具有公共特性的对象组，扮演着十分重要的角色。这样的对象组我们可以称之为：簇。簇也是一种潜在的类，而聚类分析研究的就是：自动发现这些类的技术。聚类分析早期的大部分工作都是在寻求创建可以自动发现分类结构的数学分类方法。

比如：在生物学方面，生物学家使用聚类分析大量的遗传信息，以此来发现具有功能类似的基因组；在信息检索方面，网络搜索引擎可能返回成百上千万的页面信息，可以使用聚类将搜索结果分成若干簇，每个簇捕获查询的某个特定方面，每个簇又可划分为若干的子簇，从而产生一个层次结构来帮助用户进一步查询结果；在气候方面，通过对大气层和海洋的气压进行聚类分析，以此发现对陆地气候有明显影响的极地和海洋压力模式；在心理学和医学方面，通过聚类分析来识别不同类型的癌症特征，也可以用来检测疾病的时间和空间分布模式；在商业方面，可以使用聚类将顾客划分成若干组，以便进一步分析和开展营销活动......

与上面旨在理解的聚类相对应的一种聚类是：旨在实用的聚类。聚类分析提供由个别数据对象到数据对象所指派的簇的抽象。它体现的是一种由特殊到一般的科学逻辑思想方法。（可以很明显看出：科学与哲学其实就是相互统一的一门简单易懂的学科）此外，一些聚类技术实用簇原型（即代表簇中其他对象的数据对象）来刻画簇特征。比如：现在需要描述鸟类，通过什么方法来将这么多品种的鸟描述刻画清楚，表述给人或者机器知道呢？通常都是通过描述刻画鸟的一些普遍而又能够与其它事物区别开来的属性，来解决的。那我们如何获取或者知道鸟这样的属性呢？一般是通过某些个别具有鸟本身代表性和普遍性的鸟来确定这样的属性的，那么以后人或者机器就通过这些属性来区别某一事物，它到底是不是鸟类。刚才得出来能够普遍性地刻画鸟类这样的属性的那些具体的鸟，也就是能够代表一般的数据对象，就是簇原型。这些簇原型可以用作大量数据分析和数据处理技术的基础。因此，就实用而言，聚类分析是研究发现最具有代表性的簇原型的技术。

比如：在汇总方面，许多数据分析技术，如回归和PCA，都具有O（）或更高的时间或者空间复杂度（其中m是对象的个数）。因此，对于大型数据集，这些技术不切实际。然而，可以将算法用于仅包含簇原型的数据集，而不是整个数据集。依赖分析类型、原型个数和原型代表数据的精度，汇总结果可以与使用所有数据得到的结果相媲美。在压缩方面，可以使用簇原型来进行数据压缩。例如，创建一个包含所有簇原型的表，即每个原型赋予一个整数值，作为它在表中的位置（索引）。每个对象用与它所在的簇相关联的原型的索引来表示。这类压缩称作向量量化。常常用于图像、声音和视频这类数据，此类数据的特点是：（1）许多数据对象之间高度相似，（2）某些信息的丢失是可以接受的，（3）希望能够大幅度地压缩数据。在有效地发现最近邻方面，找出最近邻可能需要计算所有点对点之间的距离。通常，可以更有效地发现簇和簇原型。如果对象相对地靠近簇的原型，则我们可以使用簇原型减少发现对象最邻近所需要计算的距离的数目。直观地说，如果两个簇原型相距很远，则对应簇中的对象也不可能互为邻近。这样，为了找出一个对象的最邻近，只需要计算到邻近簇中对象的距离，也就是说两个簇的邻近性用其原型之间的距离来进行度量。

基于大体上了解聚类能够为我们解决什么样的问题之后，接下来来对其经典的三大算法——K均值、凝聚的层次聚类和DBSCAN，本篇幅主要讨论K均值算法。

有许多技术是可以实现：基于原型的聚类技术创建数据对象的单层划分。在这许多这样的技术中，最突出的一个是K均值，一个是K中心点。那什么是：基于原型的聚类技术呢？我们都知道，簇是对象的集合，并且每个对象到定义该簇的原型的距离比到其他簇原型的距离更近，或者说更相似。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，例如当数据具有分类（标称）属性时，原型通常是中心点，即簇中最有代表性的点。对于许多数据类型，原型可以视为最靠近中心的点，在这种情况下，通常把基于原型的簇看作基于中心的簇（用一个具有代表性的数据来作为分类的依据，得到最后的各个类（对象最后的集合）就是基于原型的簇）。那什么是：创建数据对象的单层划分呢？划分聚类就是简单地将数据对象划分成不重叠的子集（簇），使得每个数据对象恰在一个子集中。总的来说：K均值和K中心点的核心思想都是通过一个能够起到代表性作用的特殊点，来将数据集中的数据来进行分类（划分）。下面了解区分K均值算法与K中心点算法的各自特点。

K均值用质心定义原型，其中质心是一组点的均值。通常K均值聚类用于n维连续空间中的对象。而K中心点使用中心点定义原型，其中中心点是一组点中最具有代表性的点。K中心点聚类可以用于广泛的数据，因为它只需要完成对数据对象之间的邻近性进行度量。尽管质心几乎从来不对应于实际的数据点，但是根据定义，中心点必须是一个实际数据点。下面针对K均值算法做一个全面的认识。

K均值算法的具体操作步骤：1、选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。每个点指派到最近的质心，而指派到一个质心的点集为一个簇。2、根据指派到簇的点，更新每个簇的质心。3、重复指派和更新步骤，直到簇不发生变化，或等价地，直到质心不发生变化。

K均值的伪算法如下：

1、选择K个点作为初始的质心

2、Repeat

3、   将每个点指派到最近的质心，形成K个簇。

4、   重新计算每个簇的质心

5、Until 质心不发生变化

对于邻近性函数和质心类型的某些组合，K均值总是收敛到一个解，即K均值到达一种状态，其中所有点都不会从一个簇转移到另一个，从而质心不再改变。然而，由于大部分收敛都发生在早期阶段，因此上面的伪代码最后一行通常使用较弱的条件来替换，比如：until 直到仅有1%的点改变簇。

下面我们将更加详细地考虑基本K均值算法的每一个步骤，并分析算法的时间和空间复杂度。

为了将点指派到最近的质心，需要邻近性度量来量化所考虑的数据的最近这个抽象的概念。通常，对于欧氏空间中的点使用欧几里得距离（），对于文档则使用余弦相似性。

K均值算法第4步一般可以陈述为：重新计算每个簇的质心，因为质心可能随数据邻近性度量和聚类的目标不同而改变。聚类的目标通常用一个目标函数表示，该函数依赖于点之间，或点到簇的质心的邻近性，如：最小化每个点到最近质心的距离的平方。

当考虑近邻度量为欧几里得距离的数据时，我们使用：误差的平方和（Sum of the Squared Error，SSE）作为度量聚类质量的目标函数。SSE也称为：散布（scatter）。换言之，我们需要计算每个点的误差，即它到最近质心的欧几里得距离，然后计算误差的平方和。如果给定由两次运行K均值产生的两个不同的簇集，我们更喜欢误差的平方和最小的那个，因为这说明：聚类的原型（质心）可以更好地代表簇中点。SSE形式地定义如下：

其中，dist是欧几里得空间中两个对象之间的标准欧几里得距离（）。给定的这些假设，使得簇的SSE最小的质心是均值。这个证明我们留到后面。那么，怎么计算第i个簇的质心呢？我们可以通过以下的公式来获得：

符号表

 

例如，3个二维点（1，1）、（2,3）和（6，2）的质心是（（1+2+6）/3，（1+3+2）/3）=（3，2）

K均值算法的步骤3和步骤4都试图直接最小化SSE（目标函数），步骤3通过将点指派到最近的质心形成簇，最小化关于给定质心集的SSE，而步骤4则是在簇内中的对象来重新计算质心，更进一步最小化SSE。在这里很明显了：K均值的步骤3和步骤4只能确保找到关于SSE的局部最优，因为它们是对选定的质心和簇，而不是对所有可能的选择来优化SSE。这将导致了：次最优聚类的产生。

上面是使用K均值算法来处理欧几里得空间的连续型数据，那对于具有分类的标称属性的文档数据，我们该如何使用K均值算法来进行拟合聚类分析呢？

对于文档数据，我们是通过余弦相似性度量，来对 最近 这个抽象的词进行量化的。文档类型数据我们一般使用：文档—词矩阵表示，如下图示：

上图就是典型的文档—词矩阵表。我们的目标是最大化簇中文档与簇的质心的相似性，该度量称为簇的：凝聚度（cohesion）。对于该度量，也可以证明，与欧几里得数据一样，簇的质心就是均值。与SSE的相似量是：总凝聚度（total cohesion），其计算公式如下：

以上讨论了两种常见的情况，下面看一下一般的情况。

一般情况，一些近邻性函数、质心和目标函数可以用基于K均值算法，并且确保收敛。需要注意的是：对于哈曼顿距离（）和最小化距离和的目标，合适的质心是簇中各点的中位数。下面表格列举了一些组合：

K均值：常见的邻近度、质心和目标函数组合

上表最后一项，Bregman散度实际上是一类近邻性度量，它包括了平方欧几里得距离，Mahalanobis距离和余弦相似度。Bregman散度函数的重要性在于：任意这类函数都可以用均值作为质心，并以此作为K均值聚类算法的基础。具体地说，如果我们使用Bregman散度作为邻近度函数，则聚类算法的收敛性、局部最小等性质，与通常的K均值相同。此外，对于所有可能的Bregman散度函数，都可以开发具有这样性质的聚类算法。事实上，我们使用的余弦相似度或平方欧几里得距离的K均值算法，都是基于Bregman散度的一般聚类算法的特例。

接下来通过使用二维数据来进一步讨论K均值算法及其性质。因为K均值是非常一般的聚类算法，所以它可以用于许多类型的数据，如文档、时间序列等。

从上面的讨论中，我们知道：K均值算法的第一步就是要选定一个初始质心，然后开始聚类（形成簇），接下来再改变质心（从簇中计算出），这个过程一直持续到until条件满足为止。所以如果选定的初始质心一样的话，运行相同的K均值算法，得到最后总SSE是不同的，所以如何选取这个初始质心是十分重要的（算法本身对这个初始质心依赖性很大）。选择适当的初始质心是基本K均值过程的关键步骤。常见的方法是随机地选取初始质心，但是这样最后得到的簇的质量往往都是很差的。

上面这种随机地选取初始质心的属于：拙劣的初始质心的做法。还有一种是：随机初始化的局限做法，具体是这样的：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE的簇集。该策略虽然简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。只有两个初始质心，无论落在簇对的任何位置，都能得到最优聚类，因为质心将自己重新分布，每个簇一个。但不幸的是，随着簇的个数增加，至少一个簇对只有一个初始质心的可能性也逐步增大。在这种情况下，由于簇对相距较远，K均值算法不能在簇对之间重新分布质心，这样就只能得到局部最优了。

随机选择初始质心存在的问题，即使重复运行多次也不能克服，因此常常使用其他技术进行初始化。一种有效的方法是：取一样本，并使用层次聚类技术对它聚类。从层级聚类中提取K个簇，并使用这些簇的质心作为初始质心。这种方法通常很有效，但也仅对下列的情况有效：（1）样本相对较小，例如数百到数千（层次聚类开销较大）；（2）K相对于样本大小较小。下面来了解一下层次聚类是怎样的。

如果允许簇具有子簇，我们就可以得到一个层次聚类（hierarchical clustering）。层次聚类是嵌套簇的集族，组织成一棵树。除叶节点外，树中每一个节点（簇）都是其子女（子簇）的并，而树根是包含所有对象的簇。通常（并非总是），树叶是单个数据对象的单元素簇。层次聚类可以看做是划分聚类的序列，划分聚类可以通过取序列的任意成员得到，即通过在一个特定层剪断层次树得到。接下来了解一下什么是划分聚类。

划分聚类（partitional clustering）就是简单地将数据对象集划分成不重叠的子集（簇），并且使得每个数据对象恰在一个子集中。

我们下面还可以通过另外一种选择初始质心的方法——随机地选取第一个点，或取所有点的质心（均值）作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，我们得到初始质心的集合，确保不是随机的，而是散开的。然而，这种方法可能选中离群点，而不是稠密区域（簇）中的点。此外，求离当前初始质心集最远的点，开销也是非常大的。为了克服这些问题，通常将该方法用于点样本。由于离群点很少，它们多半不会在随机样本中出现。相比之下，除非是样本非常小，否则来自稠密区的点是很有可能包含在样本中的。此外，找出初始质心所需要的计算量也大幅度减少了，因为样本的大小通常远小于点的个数。

以上讨论的K均值算法，都对最初的初始质心有很大的依赖（对初始质心很敏感）了，稍后，我们将要讨论另外的两种产生较高质量（较低SSE）聚类的方法：（1）使用对初始化问题不太敏感的K均值的变种——二分K均值法；（2）使用后处理来修补所产生的簇集。下面来看一下K均值的时间复杂性和空间复杂性是怎样的。

K均值的空间需求是适度的，因为只需要存放数据点和质心。具体地说，所需要的存储量为O（（m+K）*n），其中m是点数，n是属性数。K均值算法的时间复杂度也是适度的。它基本上与数据点个数是线性相关的。具体地说，所需要的时间为O（I*K*m*n），其中I是收敛所需要迭代的次数。如前面所述，I通常很小，可以是有界的，因为大部分变化通常出现在前几次迭代。因此，只要簇的个数K显著小于m的话，那么K均值的计算时间与m线性相关，并且是有效的和简单的。

现在可以讨论一下有关K均值的一些附加问题以及对应的处理方法了。

前面介绍的基本K均值算法存在的问题之一是：如果所有的点在指派步骤都未分配都某个簇，就会得到一个空簇。如果这种情况发生，则需要某种策略来选择一个替补质点，否则的话，平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。另一种方法是从具有最大SSE的簇中，选择一个替补质心。这将分裂簇，并降低聚类的总SSE。如果有多个空簇，则该过程重复多次。这是处理空簇的问题，接下来是离群点问题的处理了。

使用平方误差标准时，离群点可能会过度影响所发现的簇。具体地说，当存在离群点时，结果簇的质心（原型）可能不如没有离群点时那样有代表性，并且SSE也比较高。正是因为如此，提前发现离群点并删除它们是有用的。然而，也应当意识到有一些聚类的应用，是不能删除离群点的。当聚类用来压缩数据时，必须对每个点聚类。在某些情况下（如财经分析），明显的离群点（如不寻常的有利可图的顾客）可能是最令人感兴趣的点。如果我们使用的方法在聚类前就删除离群点，则我们就避免了对不能很好聚类的点进行聚类。当然也可以在后处理时，识别离群点。例如，我们可以通过记录每个点对SSE的影响，删除那些具有异乎寻常的点（尤其是多次运行算法时）。此外，我们还可能需要删除那些很小的簇，因为它们常常代表离群点的组。

下面介绍如何使用：用后处理降低SSE

一种明显降低SSE的方法是找出更多簇，即使用较大的K值。然而，在许多情况下，我们希望降低SSE，但并不想增加簇的个数。这是有可能做到的，因为K均值常常收敛于局部极小。可以使用多种技术来修补结果簇，以便产生较小SSE的聚类。策略是关注每一个簇，因为总SSE只不过是每个簇的SSE之和。通过在簇上进行诸如分裂和合并等操作，我们可以改变总SSE。一种常用的方法是是交替地使用簇分裂和簇合并。在分裂阶段，将簇分开，而在合并阶段将簇合并。用这种方法，常常可以避开局部极小，并且仍能够得到具有期望个数簇的聚类。

通过增加簇个数来降低总SSE的两种策略：（1）分裂一个簇：通常选择具有最大SSE的簇，但是我们也可以分裂在特定属性上具有最大标准差得到簇。（2）引进一个新的质心：通常选择离所有簇质心最远的点。如果我们记录每个点对SSE的贡献，则可以很容易地确定最远的点。另一种方法是从所有的点或者具有最高SSE的点中随机地选择。

通过减少簇个数来最小化总SSE增长的两种策略：（1）拆散一个簇：删除簇的对应质心，并将簇中的点重新指派到其他簇。理想情况下，被拆散的簇应当是使总SSE增加最少的簇。（2）合并两个簇：通常选择质心最接近的两个簇，尽管另一种方法（合并两个导致总SSE增加最少的簇）或许会更好。这两种合并的策略与层次聚类使用的方法相同，分别称作：质心方法和Ward方法。

下面来看K均值的：增量地更新质心的方法。

我们可以在点到簇的每次指派之后，增量地更新质心，而不是在所有的点都指派到簇中之后才更新簇质心。注意，每步需要零次或两次簇质心更新，因为一个点或者转移到一个新的簇（两次更新），或者是留在它的当前簇（零次更新）。使用增量更新策略确保不会产生空簇，因为所有的簇都从单个点开始；并且如果一个簇只有单个点，则该点总是被重新指派到相同的簇。此外，如果使用增量更新，则可以调整点的相对权值；例如，点的权值通常随聚类的进行而减小。尽管这可能产生更好的准确率和更快的收敛性，但是在千变万化的情况下，选择好的相对权值可能是困难的。这些更新问题类似于人工神经网络的权值更新。

增量更新的另一个优点是使用不同于最小化SSE的目标。加上给定一个度量簇集的目标函数。当我们处理某个点时，我们可以对每个可能的簇指派计算目标函数的值，然后选择优化目标的簇指派。缺点方面，增量地更新质心可能导致算法对次序的依赖性。换言之，所产生的簇可能依赖于点的处理次序。尽管随机地选择点，次序问题可以解决，但是，基本K均值方法在把所有点指派到簇中之后才更新质心，就没有次序依赖性的问题。此外，增量更新的开销也稍微大一些。然而，K均值收敛相当快，因此切换簇的点数很快就会变小。

前面已经提到过了一种：能够产生大量较高质量（较低SSE）聚类的方法——二分K均值法，其实它就是K均值法的变种，它具有的特点是：对初始化问题不太敏感。下面重点讨论二分K均值法。

二分K均值算法是基本K均值算法的直接扩充，它基于一种简单的想法：为了得到K个簇，将所有点的集合分裂成两个簇，从两个簇中选取一个继续分裂，如此下去，直到产生K个簇。

二分K均值的细节算法如下：

1、初始化簇表，使之包含由所有的点组成的簇。

2、Repeat

3、从簇表中取出一个簇

4、{对选定的簇进行多次二分试验。}

5、For i=1 to 实验次数 do

6、    使用基本K均值，二分选定的簇。

7、End for

8、从二分试验中选择具有最小总SSE的两个簇

9、将这两个簇添加到簇表中

10、until 簇表中包含K个簇

待分裂的簇有许多不同的选择方法。可以选择最大的簇，选择具有最大SSE的簇，或者使用一个基于大小和SSE的标准进行选择。不同的选择导致不同的簇。

我们通常使用结果簇的质心作为基本K均值的初始质心，对结果簇逐步求精。这是必要的，因为尽管K均值算法可以确保找到使SSE局部最小的聚类，但是在二分K均值算法中，我们是通过局部地使用了K均值算法，即每次二分一个个体簇。因此，最终的簇集并不代表是SSE局部最小的聚类。

二分K均值不太受初始化的困扰，因为它执行了多次二分试验并选取具有最小SSE的试验结果，还因为每步只有两个质心。最后，通过记录K均值二分簇所产生的聚类序列，我们还可以使用二分K均值产生层次聚类。

最后讨论一下：K均值的优缺点问题。

K均值简单并且可以用于各种数据类型。它也相当有效，尽管常常多次运行。K均值的某些变种（包含二分均值）甚至更有效，并且不太受初始化问题的影响。然而，K均值并不适合所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇，尽管指定足够大的簇个数时，它通常能够发现纯子簇。对包含离群点的数据进行聚类时，K均值也有问题。在这种情况下，离群点检测和删除大有帮助。最后，K均值仅限于具有中心（质心）概念的数据。在之前提到过的另外一种聚类技术——K中心点聚类技术没有这种限制，但开销更大。