聚类算法---以K-means算法为例

安英博2013.12.26分类是指将数据归于一系列已知类别之中的某个类的分类过程。分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足，尤其是在处理海量数据的时候。聚类是根据客体属性对一系列未分类的客体进行类别的识别，把一组个体按照相似性归成若干类。聚类属于无监督学习。分类和聚类在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具来发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上做进一步的分析。聚类分析的算法可以分为划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法。其中，最广泛使用的聚类算法k-means算法属于划分法。聚类算法给定一个有N个元组或者纪录的数据集，划分法将构造K个分组，每一个分组就代表一个聚类，KN。而且这K个分组满足下列条件：（1）每一个分组至少包含一个数据纪录；（2）每一个数据纪录属于且仅属于一个分组（某些模糊聚类算法中该条件可以放宽）；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。划分法k-means算法，也被称为k-均值或k-平均。该算法首先随机地选择k个对象作为初始的k个簇的质心；然后对剩余的每个对象，根据其与各个质心的距离，将它赋给最近的簇，然后重新计算每个簇的质心；这个过程不断重复，直到准则函数收敛。通常采用的准则函数为平方误差和准则函数，即SSE(sumofthesquarederror)，其定义如下:SSE是数据库中所有对象的平方误差总和，p为数据对象，mi是簇Ci的平均值。这个准则函数使生成的结果尽可能的紧凑和独立。k-means算法下面给出k-means算法的具体步骤:(l)给定大小为n的数据集，令I=1，选取k个初始聚类中心Zj(I)，j=1，2，3，…，k；(2)计算每个数据对象与聚类中心的距离D(xi，Zj(I))，i=1，2，3…n，j=l，2，3，…，k，如果满足D(xi，Zk(I))=min{D(xi，Zj(I))，i=l，2，3，…n}则xi∈Ck；(3)计算k个新的聚类中心：即取聚类中所有元素各自维度的算术平均数；(4)判断：若Zj(I+1)≠Zj(I)，j=l，2，3，…，k，则I=I+1，返回(2)；否则算法结束。k-means算法描述距离D的计算方法1.欧几里得距离：其意义就是两个元素在欧氏空间中的集合距离，因为其直观易懂且可解释性强，被广泛用于标识两个标量元素的相异度。2.曼哈顿距离：3.闵可夫斯基距离：k-means算法描述K-Means的算法如下：①随机在图中取k（这里k=2）个种子点。②对图中的所有点求到这k个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A、B属于上面的种子点，C、D、E属于下面中部的种子点）③移动种子点到属于他的“点群”的中心。（见图上的第三步）④然后重复第2）和第3）步，直到种子点不再移动（图中的第四步上面的种子点聚合了A,B,C，下面的种子点聚合了D，E）。从图中可以看到，A,B,C,D,E是五个在图中点。而灰色的点是种子点，也就是我们用来找点群的点。有两个种子点，所以k=2。举例概述应用实例——中国男足近几年在亚洲处于几流水平？下图是采集的亚洲15只球队在2006年-2010年间大型比赛的战绩（澳大利亚未收录）。数据做了如下预处理：对于世界杯，进入决赛圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40，预选赛小组未出线的赋予50。对于亚洲杯，前四名取其排名，八强赋予5，十六强赋予9，预选赛没出现的赋予17。应用实例1.规格化数据由于取值范围大的属性对距离的影响高于取值范围小的属性，这样不利于反映真实的相异度，因此聚类前，一般先对属性值进行规格化。所谓规格化就是将各个属性值按比例映射到相同的取值区间，来平衡各个属性对距离的影响。通常将各个属性均映射到[0,1]区间，映射公式为：其中max(ai)和min(ai)表示所有元素项中第i个属性的最大值和最小值。𝟐𝟖−𝟏𝟕𝟓𝟎−𝟏𝟕=𝟏𝟏𝟑𝟑≈0.32.选取k个初始聚类中心设k=3，即将这15支球队分成三个集团。抽取日本、巴林和泰国的值作为三个簇的种子，即初始化三个簇的中心为A：{0.3,0,0.19}，B：{0.7,0.76,0.5}和C：{1,1,0.5}。应用实例3.计算每个数据对象到聚类中心的距离D(xi，Zj(I))计算所有球队分别对三个中心点的相异度，以欧氏距离度量。例：中国{1,1,0.5}，A：{0.3,0,0.19}d(X,Y)=(1−0.3)2+12+(0.5−0.19)2≈1.2594应用实例图中从左到右依次表示各支球队到当前中心点的欧氏距离，将每支球队分到最近的簇，可对各支球队做如下聚类：中国C，日本A，韩国A，伊朗B，沙特B，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。第一次聚类结果：A：日本，韩国；B：伊朗，沙特，乌兹别克斯坦，巴林，朝鲜；C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼。4.根据第一次聚类结果，调整3个簇的中心点A簇的新中心点为：{(0.3+0)/2=0.15,(0+0.15)/2=0.075,(0.19+0.13)/2=0.16}={0.15,0.075,0.16}B簇的新中心点为：{(0.24+0.3+0.7*3)/5=0.528,(0.76*4+0.68)/5=0.744,(0.25+0.06+0.25+0.5+1)/5=0.412}={0.528,0.744,0.412}C簇的新中心点={1,0.94,0.40625}。应用实例5.由于Zj(2)≠Zj(1)，所以用调整后的中心点再次计算距离D所有球队分别到三个新中心点的距离D如图所示，所以，第二次迭代后的结果为：中国C，日本A，韩国A，伊朗B，沙特B，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。结果无变化，说明结果已收敛，最终聚类结果为：亚洲一流：日本，韩国；亚洲二流：乌兹别克斯坦，巴林，朝鲜，伊朗，沙特；应用实例亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼。中国{1,1,0.5}，A：{0.15,0.075,0.16}d(X,Y)=(1−0.15)2+（1−0.075）2+(0.5−0.16)2≈1.3014其实分析数据不仅告诉我们聚类信息，还提供了一些其它有趣的信息，例如从中可以定量分析出各个球队之间的差距。例如，在亚洲二流队伍中，伊朗与沙特水平最接近，另外，乌兹别克斯坦和巴林虽然没有打进近两届世界杯，不过凭借预选赛和亚洲杯上的出色表现占据B组一席之地，而朝鲜由于打入了2010世界杯决赛圈而有幸进入B组。其它有趣的信息还可以进一步挖掘。应用实例主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是O(nkt)，其中，n是所有对象的数目，k是簇的数目，t是迭代的次数。通常kn且tn。当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。主要缺点：必须事先给出k值，但很多时候并不知道数据集应该分成多少个类别才最合适。聚类结果对初值敏感，对于不同的初始值，可能会导致不同结果。初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。可以多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定来解决这一问题，但比较耗时、浪费资源。在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。k-means算法的性能分析