k-means算法.docx

K-Means算法

K-means聚类算法
     K-means也是聚类算法中最简单的一种了，但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中，那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。
     聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集。聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。
     在聚类问题中，给我们的训练样本是，每个，没有了y。
     K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：
1、 随机选取k个聚类质心点（cluster centroids）为。
2、 重复下面过程直到收敛 {
               对于每一个样例i，计算其应该属于的类

               对于每一个类j，重新计算该类的质心

}
     K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。
     下图展示了对n个样本点进行K-means聚类的效果，这里k取2。

     K-means面对的第一个问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下：

     J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值，那么首先可以固定每个类的质心，调整每个样例的所属的类别来让J函数减少，同样，固定，调整每个类的质心也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，和c也同时收敛。（在理论上，可以有多组不同的和c值能够使得J取得最小值，但这种现象实际上很少见）。
     由于畸变函数J是非凸函数，意味着我们不能保证取得的最小值是全局最小值，也就是说k-means对质心初始位置的选取比较感冒，但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优，那么可以选取不同的初始值跑多遍k-means，然后取其中最小的J对应的和c输出。
     下面累述一下K-means与EM的关系，首先回到初始问题，我们目的是将样本分成k个类，其实说白了就是求每个样例x的隐含类别y，然后利用隐含类别将x归类。由于我们事先不知道类别y，那么我们首先可以对每个样例假定一个y吧，但是怎么知道假定的对不对呢？怎么评价假定的好不好呢？我们使用样本的极大似然估计来度量，这里是就是x和y的联合分布P(x,y)了。如果找到的y能够使P(x,y)最大，那么我们找到的y就是样例x的最佳类别了，x顺手就聚类了。但是我们第一次指定的y不一定会让P(x,y)最大，而且P(x,y)还依赖于其他未知参数，当然在给定y的情况下，我们可以调整其他参数让P(x,y)最大。但是调整完参数后，我们发现有更好的y可以指定，那么我们重新指定y，然后再计算P(x,y)最大时的参数，反复迭代直至没有更好的y可以指定。
     这个过程有几个难点，第一怎么假定y？是每个样例硬指派一个y还是不同的y有不同的概率，概率如何度量。第二如何估计P(x,y)，P(x,y)还可能依赖很多其他参数，如何调整里面的参数让P(x,y)最大。这些问题在以后的篇章里回答。
     这里只是指出EM的思想，E步就是估计隐含类别y的期望值，M步调整其他参数使得在给定类别y的情况下，极大似然估计P(x,y)能够达到极大值。然后在其他参数确定的情况下，重新估计y，周而复始，直至收敛。
     上面的阐述有点费解，对应于K-means来说就是我们一开始不知道每个样例对应隐含变量也就是最佳类别。最开始可以随便指定一个给它，然后为了让P(x,y)最大（这里是要让J最小），我们求出在给定c情况下，J最小时的（前面提到的其他未知参数），然而此时发现，可以有更好的（质心与样例距离最小的类别）指定给样例，那么得到重新调整，上述过程就开始重复了，直到没有更好的指定。这样从K-means里我们可以看出它其实就是EM的体现，E步是确定隐含类别变量，M步更新其他参数来使J最小化。这里的隐含类别变量指定方法比较特殊，属于硬指定，从k个类别中硬选出一个给样例，而不是对每个类别赋予不同的概率。总体思想还是一个迭代优化过程，有目标函数，也有参数变量，只是多了个隐含变量，确定其他参数估计隐含变量，再确定隐含变量估计其他参数，直至目标函数最优。

原理
K-Means聚类算法是最为经典的，同时也是使用最为广泛的一种基于划分的聚类算法，它属于基于距离的聚类算法。所谓的基于距离的聚类算法指采用距离作为相似性度量的评价指标，也就是说当两个对象离的近，二者之间的距离比较小，那么它们之间的相似性就比较大。这类算法通常是由距离比较相近的对象组成簇，把得到紧凑而且独立的簇作为最终目标，因此，将这类算法称为基于距离的聚类算法。 K-Means聚类算法就是其中比较经典的一种算法。K-Means聚类是数据挖掘的重要分支，同时也是实际应用中最常用的聚类算法之一。本章重点是对K-Means聚类算法中的初始中心随机选取进行了分析与研究，给出了K-Means算法的思想和原理，优缺点的介绍以及现有的关于初始聚类中心选取的改进措施。
1967年，J.B, Mac Queen提出的K-Means算法是目前为止在工业和科学应用中一种极有影响的聚类技术。K-Means聚类算法是一种常用的基于划分的聚类分析方法，该聚类算法的最终目标就是根据输入参数k(这里的k表示需要将数据对象聚成几簇)，然后把数据对象分成k个簇。该算法的基本思想：首先指定需要划分的簇的个数k值;然后随机地选择k个初始数据对象点作为初始的聚类中心;第三，计算其余的各个数据对象到这k个初始聚类中心的距离(这里一般采用距离作为相似性度量)，把数据对象划归到距离它最近的那个中心所处在的簇类中;最后，调整新类并且重新计算出新类的中心，如果两次计算出来的聚类中心未曾发生任何的变化，那么就可以说明数据对象的调整己经结束，也就是说聚类采用的准则函数是收敛的，表示算法结束(这里采用的是误差平方和的准则函数)。
K-Means聚类算法属于一种动态聚类算法，也称作逐步聚类法，该算法的一个比较显著的特点就是迭代过程，每次都要考察对每个样本数据的分类正确与否，如果不正确，就要进行调整。当调整完全部的数据对象之后，再来修改中心，最后进入下一次迭代的过程中。若在一个迭代中，所有的数据对象都己经被正确的分类，那么就不会有调整，聚类中心也不会改变，聚类准则函数也表明已经收敛，那么该算法就成功结束。
传统的K-Means算法的基本工作过程:首先随机选择k个数据作为初始中心，计算各个数据到所选出来的各个中心的距离，将数据对象指派到最近的簇中;然后计算每个簇的均值，循环往复执行，直到满足聚类准则函数收敛为止。通常采用的是平方误差准则函数(式2-17 )，这个准则函数试图使生成的k个结果簇尽可能的紧凑和独立。其具体的工作步骤如下:
输入:初始数据集DATA和簇的数目k
输出:k个簇，满足平方误差准则函数收敛
1)任意选择k个数据对象作为初始聚类中心
2)Repeat
3)根据簇中对象的平均值，将每个对象赋给最类似的簇
4)更新簇的平均值，即计算每个对象簇中对象的平均值
5)计算聚类准则函数E
6 ) Until准则函数E值不再进行变化
图3-1显示了K-Means算法对于包含10个数据对象的数据集的聚类过程。

K-Means算法的工作框架如下：

从该算法的框架能够得出:K-Means算法的特点就是调整一个数据样本后就修改一次聚类中心以及聚类准则函数Jc的值，当n个数据样本完全被调整完后表示一次迭代完成，这样就会得到新的Jc。和聚类中心的值。若在一次迭代完成之后，Jc的值没有发生变化，那么表明该算法已经收敛，在迭代过程中Jc值逐渐缩小，直到达到最小值为止。该算法的本质是把每一个样本点划分到离它最近的聚类中心所在的类。
K-Means聚类算法的其实本质是一个最优化求解的问题，目标函数虽然有很多局部最小值点，但是只有一个全局最小值点。之所以只有一个全局最小值点是由于目标函数总是按照误差平方准则函数变小的轨迹来进行查找的。
K-Means算法对聚类中心采取的是迭代更新的方法，根据k个聚类中心，将周围的点划分成k个簇;在每一次的迭代中将重新计算的每个簇的质心，即簇中所有点的均值，作为下一次迭代的参照点。也就是说，每一次的迭代都会使选取的参照点越来越接近簇的几何中心也就是说簇心，所以目标函数如果越来越小，那么聚类的效果也会越来越好。

优缺点
K-Means算法是一种基于划分的聚类算法，尝试找出使得平方误差函数值最小的k个划分，当簇与簇之间的特征区别比较明显的时候，并且结果簇是密集的，K-Means聚类结果的效果较好。K-Means聚类算法的优点主要集中在:算法快速、简单;对大数据集有较高的效率并且是可伸缩性的;时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(nkt) ,其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目。但是，目一前为止，K-Means算法也存在着许多缺点，在应用中面临着许多问题，有待于进一步的优化.
( I ) K-Means聚类算法中需要用户事先指定聚类的个数k值
很多时候，在对数据集进行聚类的时候，用户起初并不清楚该数据集应该分多少类才合适，即聚类个数k值难以估计。有些算法如ISODATA算法是通过类的自动分裂和合并来得到较为理想的k的簇的个数。文献[13]中提出了一种基于半监督K-Means的k值全局寻优算法，它的思想是将k值从原始类别数递增，在完整的数据集{U,L}上进行constrained-K-Means聚类，当聚类后得到的空簇(空簇指的是某一簇中不包含任何标记的数据)的频率大于设定值时，算法结束，计算k取不同值时的被错误标记的数据总数N，找出最优参数k。文献HIS]采用了一种RLC算法，结合全协方差矩阵，逐步删除只含少量数据的类。文献「16]采用了一种竞争学习规则:次胜者受罚机制，来自动地生成适当数量的类，其思想就是:针对输入的聚类个数k值，一方面用修正竞争方法来获胜单元权值的方法来适应输入的k值，另一方面针对次胜单元采取惩罚的方法，使它与输入的k值尽可能的远离。
(2)对初始聚类中心的选取具有极大的依赖性使算法常陷入局部最小解
K-Means聚类算法利用迭代的重定位技术，通过随机选取出初始中心来进行寻找最优的聚类中心从而使准则函数达到收敛的效果。因此，这种随机选取初始中心的做法会导致算法的不稳定性。另外，由于K-Means选择的聚类准则函数是常用的误差平方和准则函数，它是一个非凸函数，存在多个局部极小值，只有一个是全局最小的。加上K-Means聚类算法随机选取的初始中心往往会落入到非凸函数曲面的位置，从而导致与全局最优解的搜索范围存在着一定偏离，因此，通过迭代技术往往使聚类准则函数达到局部最优而非全局最优。所以，初始聚类中心的选择会对聚类结果产生较大的影响，容易使聚类结果陷入局部最优解，造成聚类结果不稳定和不准确性。文献[as]提出了多中心聚类算法，首先运用两阶段的最大最小距离方法搜索出最佳的初始中心，再用合并算法将最初的已经划分成小类的数据集合并形成终类，也就是说利用多个中心来共同代表一个较大形状的簇。韩凌波等人在文献[33]中提出通过求解每个数据点的密度参数，而后选取k个高密度点作为初始聚类中心，有效的解决了算法随机选取初始聚类中心造成的聚类结果的不稳定性和不准确性。
(3)对噪声和孤立点数据敏感
K-Means算法将簇的质心看成聚类中心加入到下一轮的计算当中，从而导致聚类中心远离真正的数据密集区，趋向噪声孤立点数据，导致聚类结果的不准确性。因此，如果需要聚类的数据中含有大量的噪声点，那么将会很大程度上受到影响，导致结果的不稳定甚至错误。如何消除K-Means算法对噪声点的敏感性? K-medoid算法基于最小化所有对象与其参照点(不使用簇中对象的均值，选用簇中位置最中心的对象即中心点作为参照点)之间的相异度之和的原则来执行的。PAM算法是一种K-medoid算法，提出的比较早，它的主要思想是:将n个对象划分为k个子集，然后随机的选出k个中心，PAM算法便是为了找到更好的聚类中心，就反复的进行迭代，然后分析所有可能的数据，将每个数据对中的其中的一个看成中心点(而另一个对象不是)。对这些所有可能的组合，计算估计聚类的质量。文献[17]提出，将簇的中心点和簇的均值点进行相分离的思想，也就是说，在进行第k轮迭代的时候，在簇中找出与第k-1轮聚类中心点相似度较大的点的均值，把它用来作为第k轮的聚类中心点，这样的操作就可以消除孤立点的负面影响。文献中提出了一种新的基于参考点和密度的改进算法，算法思想是首先通过参考点来准确反映数据对象的空间特征，而后对数据基于参考点进行分析与处理(前提是需要参考点能够准确的反应数据特征)。
(4)针对大的数据量，算法的开销大
K-Means算法需要不断的进行迭代调整，计算调整后的新得到的中心，所以，如果遇到的数据量多的时候，算法的开销是相当可观的。因此，需要分析算法的时间复杂度并对以加之改进，从而针对算法的应用范围来进行提高。文献[19]中，通过一定的相似性准则来去掉聚类中心的候选集进行改进算法的时间复杂度。文献[20]中，K-Means算法对样本数据进行聚类的时候，将选择初始中心和一次迭代完成对数据的调整建立在随机选择样本数据的基础上，这样就可以提高算法的收敛的速度。
(5)无法发现任意的簇，一般只能发现球状簇
K-Means算法多采用欧氏距离函数度量数据对象之间的相似度，并且采用误差平方和作为准则函数。采用欧氏距离作为相似性度量的聚类算法，通常只能发现数据对象分布较均匀的球状簇。采用误差平方和准则函数的聚类算法，当类簇大小差别较大且形状较不规则时，容易造成对较大的类簇进行分割来达到目标函数取极小值的目的，从而造成聚类结果的不准确性。文献[18]针对非球状簇，采用多中心代表思想，将多个中心点都分配给同一个类，用huffman树来体现非球状簇的伸长方向，这种算法被称为多种子的非层次聚类。
混合高斯模型（Mixtures of Gaussians）和EM算法
      这篇讨论使用期望最大化算法（Expectation-Maximization）来进行密度估计（density estimation）。
      与k-means一样，给定的训练样本是，我们将隐含类别标签用表示。与k-means的硬指定不同，我们首先认为是满足一定的概率分布的，这里我们认为满足多项式分布，其中，有k个值{1,…,k}可以选取。而且我们认为在给定后，满足多值高斯分布，即。由此可以得到联合分布。
      整个模型简单描述为对于每个样例，我们先从k个类别中按多项式分布抽取一个，然后根据所对应的k个多值高斯分布中的一个生成样例，。整个过程称作混合高斯模型。注意的是这里的仍然是隐含随机变量。模型中还有三个变量和。最大似然估计为。对数化后如下：

      这个式子的最大值是不能通过前面使用的求导数为0的方法解决的，因为求的结果不是close form。但是假设我们知道了每个样例的，那么上式可以简化为：

       这时候我们再来对和进行求导得到：

      就是样本类别中的比率。是类别为j的样本特征均值，是类别为j的样例的特征的协方差矩阵。
实际上，当知道后，最大似然估计就近似于高斯判别分析模型（Gaussian discriminant analysis model）了。所不同的是GDA中类别y是伯努利分布，而这里的z是多项式分布，还有这里的每个样例都有不同的协方差矩阵，而GDA中认为只有一个。
      之前我们是假设给定了，实际上是不知道的。那么怎么办呢？考虑之前提到的EM的思想，第一步是猜测隐含类别变量z，第二步是更新其他参数，以获得最大的最大似然估计。用到这里就是：
循环下面步骤，直到收敛： {
      （E步）对于每一个i和j，计算

      （M步），更新参数：

}
      在E步中，我们将其他参数看作常量，计算的后验概率，也就是估计隐含类别变量。估计好后，利用上面的公式重新计算其他参数，计算好后发现最大化最大似然估计时，值又不对了，需要重新计算，周而复始，直至收敛。
      的具体计算公式如下：

      这个式子利用了贝叶斯公式。
      这里我们使用代替了前面的，由简单的0/1值变成了概率值。
      对比K-means可以发现，这里使用了“软”指定，为每个样例分配的类别是有一定的概率的，同时计算量也变大了，每个样例i都要计算属于每一个类别j的概率。与K-means相同的是，结果仍然是局部最优解。对其他参数取不同的初始值进行多次计算不失为一种好方法。
      虽然之前再K-means中定性描述了EM的收敛性，仍然没有定量地给出，还有一般化EM的推导过程仍然没有给出。下一篇着重介绍这些内容。