聚类分析实例.docx

《聚类分析实例.docx》由会员分享，可在线阅读，更多相关《聚类分析实例.docx（8页珍藏版）》请在优知文库上搜索。

1、k-means聚类”数据分析、数据挖掘一、概要分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并且断言所为待分类项都有个类别与之对应。但是很多时候上述条件得不到满足,尤其是在处理海好数据的时候，如果通过预处理使得数据满足分类算法的要求，那么代价非常大，这时候可以考虑使用聚聚类属于无监督学习，相比于分类，聚类不依帙颈定义的类和类标号的训练实例本文介绍一种常见的聚类卯法k均值和k中心点聚类，最后会举一个实例：应用聚类方法试图解决个在体育界大家颇具争议的问题中国男足近儿年在亚洲到底处丁几流水平.二、聚类问题所谓聚类问题，就是给定一个元素集合D,其中每个元素具有n个可观察属性，使用某种算

2、法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高.其中每个子集叫做一个镇.与分类不同，分类是例如式学习,要求分类前明确各个类别,并断言每个元素映射到一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给定类别数量，是无监督学习的一种。I1.前聚类广泛应用于统计学、生物学、数据库技术和市场营销等领域，相应的郛法也非常的多。本文仅介绍一种最简雌的聚类算法一一k均值（k-means）驻法。三、概念介绍区分两个概念:hardc1.ustering：一个文档要么属于类w,要么不属F类w,即文档对确定的类W是二值的1或O.softc1.ustering：

3、一个文档可以屈于类w1,同时也可以屈于w2,而且文档屈于一个类的值不是。或1,可以是0.3这样的小数.K-Means就是一种hardc1.ustering,所谓K-means里的K就是我们要事先指定分类的个数，即K个。k-means算法的流程如下:1）从N个文档随机选取K个文档作为初始质心2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类3）Ui计算已经得到的各个类的质心4)迭代23步直至满足既定的条件，算法结束在K-means算法里所有的文档都必须向量化，n个文档的质心可以认为是这n个向量的中心，计算方法如下:R(3)=2Jf这里参加个方差RSS的概念：RSSk=E-M2我

4、必KRSS=ERSSkJt=IRSSk的值是类k中每个文档到质心的距离，RSS是所有k个类的RSS值的和。算法结束条件：1)给定一个迭代次数，到达这个次数就停止，这好似不是一个好建议.2) k个顺心应该到达收敛，即第n次计算出的n个质心在第n+1次迭代时候位置不变。3) n个文档到达收敛，即第n次计算出的n个文档分类和在第n+1次迭代时候文档分类结果相同.4；RSS值小F一个阀值，实际中往往把这个条件结合条件1使用回过头用RSS讨论质心的计算方法是否合理M=E-2=1.,(vm-xm)2f7W=I=E2(vm-xm)我4(RSSkHRSS-加，”为r取得RSS的极小值，RSS对质心求偏导数应该

5、为0,所以得到质心（3）=3平可见，这个质心的选择是符合数学原理的。K-mea11s方法的缺点是聚类结果依赖于初始选择的几个质点位也，看下面这个例子：3dd曲2-XI-X办5成0IF_II_01234如果使用2-means方法，初始选择d2和d5那么得到的聚类结果就是d1.,d2.d3d4.d5,d6,这不是一个合理的聚类结果解决这种初始种子问题的方案：D去处一些游离在外层的文档后再选择2）多项选择一些种子，取结果好的（RSS小）的K个类继续算法3）用以次聚类的方法选择种子。我认为这不是一个适宜的方法，因为对初始N个文档进行层次聚类代价非常高。以上的讨论都是基丁K是的，但是我们怎么能从随机的文

6、档集合中选择这个k呢？我们可以对k去1N分别执行k-means.得到RSS关于K的函数下列图:0966OS-Ocxn&g？IOUJn;*&当RSS由显著下降到不是那么显著下降的K值就可以作为最终的K,如图可以选择4或9四、算法及例如k均值算法的计算过程非常直观；1、从D中机取k个元素，作为k个兼的各自的中心.2、分别计算朝下的元*到k个焦中心的相鼻度，将这整元素分别划归到相鼻度量低的袋.3、根据聚类结果，皆计算k个各自的中心，计算方法是取修中所有元素各自罐度的算术平均数.4、将D中全部元素按照新的中心工新聚类.5、AM4步，直到聚类结果不再变化.6、将结果出.由于算法比拟R.观，没有什么可以过

7、多讲解的。卜面，我们来看看k-mcans算法一个有题的应用例如:中国男足近几年到底在亚洲处于几流水平？今年中国男足可算是杯具到家了，几乎到了过街老跳人人喊打的地步.时于目前中国男足在亚洲的地位,各方也是各执一词，有人说中国男足亚洲二流，有人说三流，还有人说根本不入流，更有人说其实不比日韩差多少，是亚洲一流.既然争论不能解决问遨，我的就让数据告诉我们结果吧.下列图是采集的亚洲15只球队在2005年-2010年间大型杯赛的战绩（由于澳大利亚足后来参加亚足联的，所以这电没有收录），克尔苔别505092894173255282501509404050505040325959917其中包括两次世界杯和次

8、亚洲杯,我提前对数据r如下预处理：对于世界杯，进入决赛圈那么取其显终排名，没有进入决赛圈的，打入预选赛十强赛赋予10,预选赛小组未出妓的赋予50,对于亚洲杯,前四名取其排名，八强赋予5,卜六强赋予9,预选赛没出现的赋予17.这样做是为了使得所有数据变为标及便于后续联类.卜面先对数据进行o,U规格化.卜面是规格化后的数据:BD2006年世界杯2010年世界杯2007年亚洲杯1x0.130650.6616661116777777坦斯克克尔苔别国本国朗特拉塔联兹国南曼林鲜尼中日韩伊沙伊卡阿乌泰越阿巴朝印2345678910111213141516其中包括两次世界杯和次亚洲杯，我提前对数据做了如下预处

9、理：对于世界杯，进入决赛圈就么取其最终排名，没有进入决看圈的，打入预选赛卜强赛赋予40,预选骞小加未出线的赋予50.对于亚洲杯,前四名取其排名,八强赋予5,十六强赋予9.预选赛没*现的欣子17.这样做是为了使得所有数据变为标盘.便于后续聚类.下而先对数据迸行0.U规格化下面是规格化后的数据：61.e：/E:/个人JteiAnans/kmeans/bin/Debug/kmeans.D(E1.2124360.5196150B0.692821.212436B.5196151.2124361.732051B.1039230.7967431.31635990.692821.2124361.2124360

10、.51961501.2124360.51961501.2124360.5196158B.6928200.5196151.2124360.51961501.2124360.51961501.2124360.519615HB.6928200.5196153.6928200.5196151.2124360.519615ncZhangsTeChBIog(http：/IeoO2skcnb1.ogs.8m)从做到右依次表示各支球队到当前中心点的欧氏距离，将每支球队分到最近的微，可对各支球队做如下聚类：中国11本A,韩国A,伊朗A,沙特A,伊拉克卡塔尔阿联酋a自兹别克斯坦B,泰国C,越南C阿曼C巴林B.朝鲜

11、B,印尼C第一次聚类结果：A；11本，帏国,伊朗,沙特；B；0兹别克斯坦，巴林，朝鲜：C：中国,伊拉克.卡塔尔,阿联酋，泰国,越南，阿曼,印尼.下而根据第一次聚类结果,谓整各个税的中心点。A05的新中心点为t(0.3*0*0.2440.3)/4-0.21.9+0.15*0.76+0.76)4=O.4175,(0.1940.1340.25+0.06)/4=0.1575)=0.21,0.4175.0.1575用同样的方法计算褥到B和C籁的新中心点分别为97,0.7333.0.1167).11.0.94.0.40625).用调整后的中心点再次进行聚类，得到：fikEAX1SAmeensAreans/

12、bin/Debug/kmedn$.EXEST368320.5196150B.1558850.692821.212436B.3637311.2124361.7320S1B.0519620.7967431.316359B.15S8850.692821.2124361.368320.51961S01.368320.51961501.368320.5196150B.84870500.5196151.36832.51961501.368320.51961501.36832.5196150B.84870500.519615B.84870500.5196151.368320.5196150EricZhang

13、tSTechB1.og(httoe2skcnb1.ogsm)第：次迭代后的结果为:中国C日本A,韩国A,伊朗A,沙特A,伊拉克C卡塔尔C.阿联酋C.乌兹别克斯坦B,泰ISC,越南C.阿曼C,巴林B,朝鲜B,印尼C.结果无变化，说明结果己收敛，干是给出以终聚类结果;.亚洲一流：F1.本，帏国，伊朗，沙特亚洲二流：乌兹别克斯坦，巴林，朝解亚洲三流：中国.伊拉克,卡塔尔,阿联酋.泰国.越南,阿曼,印足后未数据告诉我11,说国足近几年处在亚洲三流水平真的是没有冤枉他们.至少从国际杯赛战绩是这样的.其实上面的分析数据不仅告诉了我们聚类信息还提供了一些其它有趣的信息例如从中可以定盘分析出各个球队之间的差距，例如.在亚洲一流队伍中，日本与沙特水平最接近，而伊朗那么相距他们较远,这也和近几年伊朗没落的实际相符。出外，乌兹别克斯坦和巴林虽然没有打进近两届世界杯，不过凭借侦算赛和亚洲杯上的出色表现占据B组一席之地，而朝鲜由于打入了2010世界杯决看圈而有幸进入B组.可是同样奇迹般夺得2007年亚洲杯的伊拉克却被分在三流.柠来亚洲杯冠军的分金还不如打进世界杯决褰豳曳明,其它有趣的信息,有兴趣的朋友可以进一步挖掘.