欢迎您光临本小站。希望您在这里可以找到自己想要的信息。。。

K-means聚类算法

数据结构算法 water 113℃ 0评论

  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,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来说就是我们一开始不知道每个样例clip_image020[10]对应隐含变量也就是最佳类别clip_image022[6]。最开始可以随便指定一个clip_image022[7]给它,然后为了让P(x,y)最大(这里是要让J最小),我们求出在给定c情况下,J最小时的clip_image014[10](前面提到的其他未知参数),然而此时发现,可以有更好的clip_image022[8](质心与样例clip_image020[11]距离最小的类别)指定给样例clip_image020[12],那么clip_image022[9]得到重新调整,上述过程就开始重复了,直到没有更好的clip_image022[10]指定。这样从K-means里我们可以看出它其实就是EM的体现,E步是确定隐含类别变量clip_image024[6],M步更新其他参数clip_image018[9]来使J最小化。这里的隐含类别变量指定方法比较特殊,属于硬指定,从k个类别中硬选出一个给样例,而不是对每个类别赋予不同的概率。总体思想还是一个迭代优化过程,有目标函数,也有参数变量,只是多了个隐含变量,确定其他参数估计隐含变量,再确定隐含变量估计其他参数,直至目标函数最优。

================================================================================

在数据挖掘中,K-Means算法是一种cluster analysis的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。

问题

K-Means算法主要解决的问题如下图所示。我们可以看到,在图的左边有一些点,我们用肉眼可以看出来有四个点群,但是我们怎么通过计算机程序找出这几个点群来呢?于是就出现了我们的K-Means算法(Wikipedia链接

K-Means要解决的问题

算法概要

这个算法其实很简单,如下图所示: 

K-Means 算法概要

从上图中,我们可以看到,A,B,C,D,E是五个在图中点。而灰色的点是我们的种子点,也就是我们用来找点群的点。有两个种子点,所以K=2。

然后,K-Means的算法如下:

  1. 随机在图中取K(这里K=2)个种子点。

  2. 然后对图中的所有点求到这K个种子点的距离,假如点Pi离种子点Si最近,那么Pi属于Si点群。(上图中,我们可以看到A,B属于上面的种子点,C,D,E属于下面中部的种子点)

  3. 接下来,我们要移动种子点到属于他的“点群”的中心。(见图上的第三步)

  4. 然后重复第2)和第3)步,直到,种子点没有移动(我们可以看到图中的第四步上面的种子点聚合了A,B,C,下面的种子点聚合了D,E)。

这个算法很简单,但是有些细节我要提一下,求距离的公式我不说了,大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法”。

求点群中心的算法

一般来说,求点群中心点的算法你可以很简的使用各个点的X/Y坐标的平均值。不过,我这里想告诉大家另三个求中心点的的公式:

1)Minkowski Distance公式——λ可以随意取值,可以是负数,也可以是正数,或是无穷大。

2)Euclidean Distance公式——也就是第一个公式λ=2的情况

3)CityBlock Distance公式——也就是第一个公式λ=1的情况

这三个公式的求中心点有一些不一样的地方,我们看下图(对于第一个λ在0-1之间)。

(1)Minkowski Distance     (2)Euclidean Distance    (3) CityBlock Distance

上面这几个图的大意是他们是怎么个逼近中心的,第一个图以星形的方式,第二个图以同心圆的方式,第三个图以菱形的方式。

K-Means的演示

如果你以”K Means Demo“为关键字到Google里查你可以查到很多演示。这里推荐一个演示:http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html

操作是,鼠标左键是初始化点,右键初始化“种子点”,然后勾选“Show History”可以看到一步一步的迭代。

注:这个演示的链接也有一个不错的K Means Tutorial

K-Means++算法

K-Means主要有两个最重大的缺陷——都和初始值有关:

  • K是事先给定的,这个K值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。(ISODATA算法通过类的自动合并和分裂,得到较为合理的类型数目K)

  • K-Means算法需要用初始随机种子点来搞,这个随机种子点太重要,不同的随机种子点会有得到完全不同的结果。(K-Means++算法可以用来解决这个问题,其可以有效地选择初始点)

我在这里重点说一下K-Means++算法步骤:

  1. 先从我们的数据库随机挑个随机点当“种子点”。

  2. 对于每个点,我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里,然后把这些距离加起来得到Sum(D(x))。

  3. 然后,再取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先取一个能落在Sum(D(x))中的随机值Random,然后用Random -= D(x),直到其<=0,此时的点就是下一个“种子点”。

  4. 重复第(2)和第(3)步直到所有的K个种子点都被选出来。

  5. 进行K-Means算法。

相关的代码你可以在这里找到“implement the K-means++ algorithm”(墙)另,Apache的通用数据学库也实现了这一算法

K-Means算法应用

看到这里,你会说,K-Means算法看来很简单,而且好像就是在玩坐标点,没什么真实用处。而且,这个算法缺陷很多,还不如人工呢。是的,前面的例子只是玩二维坐标点,的确没什么意思。但是你想一下下面的几个问题:

1)如果不是二维的,是多维的,如5维的,那么,就只能用计算机来计算了。

2)二维坐标点的X,Y 坐标,其实是一种向量,是一种数学抽象。现实世界中很多属性是可以抽象成向量的,比如,我们的年龄,我们的喜好,我们的商品,等等,能抽象成向量的目的就是可以让计算机知道某两个属性间的距离。如:我们认为,18岁的人离24岁的人的距离要比离12岁的距离要近,鞋子这个商品离衣服这个商品的距离要比电脑要近,等等。

只要能把现实世界的物体的属性抽象成向量,就可以用K-Means算法来归类了

在《k均值聚类(K-means)》 这篇文章中举了一个很不错的应用例子,作者用亚洲15支足球队的2005年到1010年的战绩做了一个向量表,然后用K-Means把球队归类,得出了下面的结果,呵呵。

  • 亚洲一流:日本,韩国,伊朗,沙特

  • 亚洲二流:乌兹别克斯坦,巴林,朝鲜

  • 亚洲三流:中国,伊拉克,卡塔尔,阿联酋,泰国,越南,阿曼,印尼

其实,这样的业务例子还有很多,比如,分析一个公司的客户分类,这样可以对不同的客户使用不同的商业策略,或是电子商务中分析商品相似度,归类商品,从而可以使用一些不同的销售策略,等等。

转载请注明:学时网 » K-means聚类算法

喜欢 (0)or分享 (0)

您必须 登录 才能发表评论!

305889407