K-means聚类算法.docVIP

K-means聚类算法 K-means也是聚类算法中最简单的一种了，但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中，那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。 聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集clip_image002[10]。聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。 在聚类问题中，给我们的训练样本是clip_image004，每个clip_image006，没有了y。 K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下： 1、 随机选取k个聚类质心点（cluster centroids）为clip_image008[6]。 2、 重复下面过程直到收敛 { 对于每一个样例i，计算其应该属于的类 clip_image009 对于每一个类j，重新计算该类的质心 clip_image010[6] } K是我们事先给定的聚类数，clip_image012[6]代表样例i与k个类中距离最近的那个类，clip_image012[7]的值是1到k中的一个。质心clip_image014[6]代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为clip_image012[8]，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心clip_image014[7]（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。 下图展示了对n个样本点进行K-means聚类的效果，这里k取2。 clip_image015 K-means面对的第一个问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下： clip_image016[6] J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值，那么首先可以固定每个类的质心clip_image014[8]，调整每个样例的所属的类别clip_image012[9]来让J函数减少，同样，固定clip_image012[10]，调整每个类的质心clip_image014[9]也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，clip_image018[6]和c也同时收敛。（在理论上，可以有多组不同的clip_image018[7]和c值能够使得J取得最小值，但这种现象实际上很少见）。 由于畸变函数J是非凸函数，意味着我们不能保证取得的最小值是全局最小值，也就是说k-means对质心初始位置的选取比较感冒，但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优，那么可以选取不同的初始值跑多遍k-means，然后取其中最小的J对应的clip_image018[8]和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