聚类分析实例

k-means 聚类”数据分析、数据挖掘一、概要分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并 且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满 足，尤其是在处理海量数据的时候，如果通过预处理使得数据满足分类算法的要 求，则代价非常大，这时候可以考虑使用聚类算法。聚类属于无监督学习，相比 于分类，聚类不依赖预定义的类和类标号的训练实例。本文介绍一种常见的聚类 算法一一k均值和k中心点聚类，最后会举一个实例：应用聚类方法试图解决 一个在体育界大家颇具争议的问题中国男足近几年在亚洲到底处于几流水 平。二、聚类问题所谓聚类问题，就是给定一个元素集合D,其中每个元素具有n个可观 察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相 异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个 元素映射到一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给 定类别数量，是无监督学习的一种。目前聚类广泛应用于统计学、生物学、数据 库技术和市场营销等领域，相应的算法也非常的多。本文仅介绍一种最简单的聚 类算法k均值（k-means）算法。三、概念介绍区分两个概念： hard clustering： 文档要么属于类w，要么不属于类w，即文档对确定的类 w是二值的1或0。soft clustering：文档可以属于类w1，同时也可以属于w2，而且文档属于一个类的值不是0或1,可以是这样的小数。K-Mea ns就是一种hard clusteri ng,所谓K-mea ns里的K就是我们要事先指定 分类的个数，即K个。k-means算法的流程如下：1）从N个文档随机选取K个文档作为初始质心2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类3）重新计算已经得到的各个类的质心 4）迭代23步直至满足既定的条件，算法结束 在Kmeans算法里所有的文档都必须向量化，n个文档的质心可以认为是这n 个向量的中心，计算方法如下：这里加入一个方差RSS的概念：RSS严二兄巩啖严KRSS -匸 RSSk=lRSSk的值是类k中每个文档到质心的距离，RSS是所有k个类的RSS值的和。 算法结束条件： 1）给定一个迭代次数，达到这个次数就停止，这好像不是一个好建议。2) k个质心应该达到收敛，即第n次计算出的n个质心在第n + 1次迭代时候位 置不变。3) n个文档达到收敛，即第n次计算出的n个文档分类和在第n + 1次迭代时候 文档分类结果相同。4) RSS值小于一个阀值，实际中往往把这个条件结合条件1使用回过头用RSS讨论质心的计算方法是否合理RSSk 何=M=E 口加-订dRSS把佰）为了取得RSS的极小值，RSS对质心求偏导数应该为0所以得到质心可见，这个质心的选择是合乎数学原理的。K-means方法的缺点是聚类结果依赖于初始选择的几个质点位置，看下面这个例 子：j L一XdiXd3X-X右X 川5gX f/点1E-10 11211N34如果使用2mea ns方法，初始选择d2和d5那么得到的聚类结果就是di, d2, d3d4, d5, d6，这不是一个合理的聚类结果解决这种初始种子问题的方案：1）去处一些游离在外层的文档后再选择2）多选一些种子，取结果好的（RSS小）的K个类继续算法3）用层次聚类的方法选择种子。我认为这不是一个合适的方法，因为对初始N 个文档进行层次聚类代价非常高。以上的讨论都是基于K是已知的，但是我们怎么能从随机的文档集合中选择这个 k值呢 我们可以对k去1N分别执行k-means，得到RSS关于K的函数下图:当RSS由显著下降到不是那么显著下降的K值就可以作为最终的K,如图可以选 择4或9。四、算法及示例k均值算法的计算过程非常直观：1、从D中随机取k个元素，作为k个簇的各自的中心。2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算 术平均数。4、将D中全部元素按照新的中心重新聚类。5、重复第4步，直到聚类结果不再变化。6、将结果输出。由于算法比较直观，没有什么可以过多讲解的。下面，我们来看看k-means算法一个有趣 的应用示例：中国男足近几年到底在亚洲处于几流水平今年中国男足可算是杯具到家了，几乎到了过街老鼠人人喊打的地步。对于目前中国男足在 亚洲的地位，各方也是各执一词，有人说中国男足亚洲二流，有人说三流，还有人说根本不 入流，更有人说其实不比日韩差多少，是亚洲一流。既然争论不能解决问题，我们就让数据 告诉我们结果吧。下图是采集的亚洲15只球队在2005年-2010年间大型杯赛的战绩（由于澳大利亚是后来 加入亚足联的，所以这里没有收录）。E2QQ丘年世界杯502S1725285050C2010年世界杯D2007年亚钿杯153105丸250140994324 5 6 I Tfi J -50504040EricZrisr505050409S217Tech Blog h阳:寤“庐其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理：对于世界杯，进入决赛 圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40,预选赛小组未出线的 赋予50。对于亚洲杯，前四名取其排名，八强赋予5,十六强赋予9,预选赛没出现的赋予 17。这样做是为了使得所有数据变为标量，便于后续聚类。下面先对数据进行0,1规格化，下面是规格化后的数据：Z3宅5G7S910111213141516坦断克克尔苗别国本国萌特&塔麻兹国南林鳞尼中日韩伊沙伊卡阿乌S越阿巴朝印110.50.300.1900150,130. 240. 7S0_250.30. 7&0.0611010. 76C. 51S 7&0.50.7760. 2511Q.5110.25110. 50.70. 760.50.70. 6312QQ6年世齐杯2010年世界杯氏叩年亚汕杯CD其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理：对于世界杯，进入决赛 圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40,预选赛小组未出线的 赋予50。对于亚洲杯，前四名取其排名，八强赋予5,十六强赋予9,预选赛没出现的赋予 17。这样做是为了使得所有数据变为标量，便于后续聚类。下面先对数据进行0,1规格化，下面是规格化后的数据：1-2L24360.51961$e1.21243GB.51961S1.212436.1039231.3163590.692S21.2124361.2124366.5196151.2124366.5196151.2124360_51?61S0B.6928208.5196151.21243&e.51%150卜.212436回.51961501.2124365196150B.692fi208.519615；IB.6928291-212436B_51?615tncZhangfsi Tech Blog (httpJ/blD)从做到右依次表示各支球队到当前中心点的欧氏距离，将每支球队分到最近的簇，可对各支 球队做如下聚类：中国C,日本A,韩国A,伊朗A,沙特A,伊拉克C,卡塔尔C,阿联酋C,乌兹别克斯坦B, 泰国C,越南C,阿曼C,巴林B，朝鲜B，印尼C。第一次聚类结果：A：日本，韩国，伊朗，沙特；B：乌兹别克斯坦，巴林，朝鲜；C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼。下面根据第一次聚类结果，调整各个簇的中心点。A 簇的新中心点为：+0+/4二，（0+/4二,+/4二二, , 用同样的方法计算得到B和C簇的新中心点分别为, , ,1, ,。用调整后的中心点再次进行聚类，得到：rI fi 血*/E# 个人交拽/Itm n/kfn ean/bin丿氏bug/km色白 ns. EX E1.366320.1558850-3637310-0519620-1S58851-3GB321-368321-36832 0-848705 1-368321-3G8321.36B320848705 0-848705 1_3&8326.5196150.692821.21243G0.7967430.G92B2e.519&160.5i?fil50.51961500-5196150-S19&1E0.519610G0.519&151-2124361-7320511-3163S91-21243&回.5196150-519615第二次迭代后的结果为：中国C,日本A,韩国A,伊朗A,沙特A,伊拉克C,卡塔尔C，阿联酋C，乌兹别克斯坦B, 泰国C,越南C,阿曼C,巴林B，朝鲜B，印尼C。结果无变化，说明结果已收敛，于是给出最终聚类结果：亚洲一流：日本，韩国，伊朗，沙特亚洲二流：乌兹别克斯坦，巴林，朝鲜亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼看来数据告诉我们，说国足近几年处在亚洲三流水平真的是没有冤枉他们，至少从国际杯赛 战绩是这样的。其实上面的分析数据不仅告诉了我们聚类信息，还提供了一些其它有趣的信息，例如从中可 以定量分析出各个球队之间的差距，例如，在亚洲一流队伍中，日本与沙特水平最接近，而 伊朗则相距他们较远，这也和近几年伊朗没落的实际相符。另外，乌兹别克斯坦和巴林虽然 没有打进近两届世界杯，不过凭借预算赛和亚洲杯上的出色表现占据B组一席之地，而朝 鲜由于打入了 2010世界杯决赛圈而有幸进入B组，可是同样奇迹般夺得2007年亚洲杯的 伊拉克却被分在三流，看来亚洲杯冠军的分量还不如打进世界杯决赛圈重啊。其它有趣的信 息，有兴趣的朋友可以进一步挖掘。