K-Means

Clustering中文翻译作“聚类”，简单地说就是把相似的东西分到一组，同Classification(分类)不同，对于一个classifier，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，一个classifier会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做supervisedlearning(监督学习)，而在聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，因此，一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此clustering通常并不需要使用训练数据进行学习，这在MachineLearning中被称作unsupervisedlearning(无监督学习)。举一个简单的例子：现在有一群小学生，你要把他们分成几组，让组内的成员之间尽量相似一些，而组之间则差别大一些。最后分出怎样的结果，就取决于你对于“相似”的定义了，比如，你决定男生和男生是相似的，女生和女生也是相似的，而男生和女生之间则差别很大”，这样，你实际上是用一个可能取两个值“男”和“女”的离散变量来代表了原来的一个小学生，我们通常把这样的变量叫做“特征”。实际上，在这种情况下，所有的小学生都被映射到了两个点的其中一个上，已经很自然地形成了两个组，不需要专门再做聚类了。另一种可能是使用“身高”这个特征。我在读小学候，每周五在操场开会训话的时候会按照大家住的地方的地域和距离远近来列队，这样结束之后就可以结队回家了。除了让事物映射到一个单独的特征之外，一种常见的做法是同时提取N种特征，将它们放在一起组成一个N维向量，从而得到一个从原始数据集合到N维向量空间的映射——你总是需要显式地或者隐式地完成这样一个过程，因为许多机器学习的算法都需要工作在一个向量空间中。那么让我们再回到clustering的问题上，暂且抛开原始数据是什么形式，假设我们已经将其映射到了一个欧几里德空间上，为了方便展示，就使用二维空间吧，如下图所示：从数据点的大致形状可以看出它们大致聚为三个cluster，其中两个紧凑一些，剩下那个松散一些。我们的目的是为这些数据分组，以便能区分出属于不同的簇的数据，如果按照分组给它们标上不同的颜色，就是这个样子：那么计算机要如何来完成这个任务呢？当然，计算机还没有高级到能够“通过形状大致看出来”，不过，对于这样的N维欧氏空间中的点进行聚类，有一个非常简单的经典算法，也就是本文标题中提到的k-means(k-均值)。在介绍k-means的具体步骤之前，让我们先来看看它对于需要进行聚类的数据的一个基本假设吧：对于每一个cluster，我们可以选出一个中心点(center)，使得该cluster中的所有的点到该中心点的距离小于到其他cluster的中心的距离。虽然实际情况中得到的数据并不能保证总是满足这样的约束，但这通常已经是我们所能达到的最好的结果，而那些误差通常是固有存在的或者问题本身的不可分性造成的。例如下图所示的两个高斯分布，从两个分布中随机地抽取一些数据点出来，混杂到一起，现在要让你将这些混杂在一起的数据点按照它们被生成的那个分布分开来：由于这两个分布本身有很大一部分重叠在一起了，例如，对于数据点2.5来说，它由两个分布产生的概率都是相等的，你所做的只能是一个猜测；稍微好一点的情况是2，通常我们会将它归类为左边的那个分布，因为概率大一些，然而此时它由右边的分布生成的概率仍然是比较大的，我们仍然有不小的几率会猜错。而整个阴影部分是我们所能达到的最小的猜错的概率，这来自于问题本身的不可分性，无法避免。因此，我们将k-means所依赖的这个假设看作是合理的。基于这样一个假设，我们再来导出k-means所要优化的目标函数：设我们一共有N个数据点需要分为K个cluster，k-means要做的就是最小化NnKkknnkxrJ11/21,NnCpnncpdistJ这个函数，其中nkr在数据点n被归类到clusterk的时候为1，否则为0。直接寻找nkr和k来最小化J并不容易，不过我们可以采取迭代的办法：先固定k，选择最优的nkr，很容易看出，只要将数据点归类到离他最近的那个中心就能保证J最小。下一步则固定nkr，再求最优的k。将J对k求导并令导数等于零，很容易得到J最小的时候k应该满足：nnknnnkkrxr亦即k的值应当是所有clusterk中的数据点的平均值。由于每一次迭代都是取到的J最小值，因此J只会不断地减小（或者不变），而不会增加，这保证了k-means最终会到达一个极小值。虽然k-means并不能保证总是能得到全局最优解，但是对于这样的问题，像k-means这种复杂度的算法，这样的结果已经是很不错的了。下面我们来总结一下k-means算法的具体步骤：1.选定K个中心k的初值。这个过程通常是针对具体的问题有一些启发式的选取方法，或者大多数情况下采用随机选取的办法。因为前面说过k-means并不能保证全局最优，而是否能收敛到全局最优解其实和初值的选取有很大的关系，所以有时候我们会多次选取初值跑k-means，并取其中最好的一次结果。2.将每个数据点归类到离它最近的那个中心点所代表的cluster中。3.用公式kclusterjjkkxN1计算出每个cluster的新的中心点。4.重复第二步，一直到迭代了最大的步数或者前后的J的值相差小于一个阈值为止。按照这个步骤写一个k-means实现其实相当容易了，在SciPy或者Matlab中都已经包含了内置的k-means实现，不过为了看看k-means每次迭代的具体效果，我们不妨自己来实现一下，代码如下（需要安装SciPy和matplotlib）。首先3个中心点被随机初始化，所有的数据点都还没有进行聚类，默认全部都标记为红色，如下图所示：然后进入第一次迭代：按照初始的中心点位置为每个数据点着上颜色，这是代码中第41到43行所做的工作，然后45到47行重新计算3个中心点，结果如下图所示：可以看到，由于初始的中心点是随机选的，这样得出来的结果并不是很好，接下来是下一次迭代的结果：可以看到大致形状已经出来了。再经过两次迭代之后，基本上就收敛了，最终结果如下：不过正如前面所说的那样k-means也并不是万能的，虽然许多时候都能收敛到一个比较好的结果，但是也有运气不好的时候会收敛到一个让人不满意的局部最优解，例如选用下面这几个初始中心点：最终会收敛到这样的结果：不得不承认这并不是很好的结果。不过其实大多数情况下k-means给出的结果都还是很令人满意的，算是一种简单高效应用广泛的clustering方法。K-means算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tKmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。K如何确定kmenas算法首先选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。这样做的前提是我们已经知道数据集中包含多少个簇，但很多情况下，我们并不知道数据的分布情况，实际上聚类就是我们发现数据分布的一种手段，这就陷入了鸡和蛋的矛盾。如何有效的确定K值，这里大致提供几种方法。1.与层次聚类结合经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。2.稳定性方法稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有k个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明k个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个k，找到合适的k值。3.系统演化方法系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为K个聚类时称系统处于状态K。系统由初始状态K=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态Ki，其所对应的聚类结构决定了最优类数Ki。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。4.使用canopy算法进行初始划分[4]基于CanopyMethod的聚类算法将聚类过程分为两个阶段Stage1、聚类最耗费计算的地方是计算对象相似性的时候，CanopyMethod在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；Stage2、在各个Canopy内使用传统的聚类方法(如K-means)，不属于同一Canopy的对象之间不进行相似性计算。从这个方法起码可以看出两点好处：首先，Canopy不要太大且Canopy之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于K-means这样的聚类方法是需要人为指出K的值的，通过Stage1得到的Canopy个数完全可以作为这个K值，一定程度上减少了选择K的盲目性。