文档介绍：该【聚类分析实例 】是由【幸福人生】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【聚类分析实例 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。聚类分析实例
k-means聚类”——数据分析、数据挖掘
一、概要
  分类作为一种监督学****方法,要求必须事先明确知道各个类别的信息,并且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足,尤其是在处理海量数据的时候,如果通过预处理使得数据满足分类算法的要求,则代价非常大,这时候可以考虑使用聚类算法。聚类属于无监督学****相比于分类,聚类不依赖预定义的类和类标号的训练实例。本文介绍一种常见的聚类算法——k均值和k中心点聚类,最后会举一个实例:应用聚类方法试图解决一个在体育界大家颇具争议的问题——中国男足近几年在亚洲到底处于几流水平。
二、聚类问题
  所谓聚类问题,就是给定一个元素集合D,其中每个元素具有n个可观察属性,使用某种算法将D划分成k个子集,要求每个子集内部的元素之间相异度尽可能低,而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。
  与分类不同,分类是示例式学****要求分类前明确各个类别,并断言每个元素映射到一个类别,而聚类是观察式学****在聚类前可以不知道类别甚至不给定类别数量,是无监督学****的一种。目前聚类广泛应用于统计学、生物学、数据库技术和市场营销等领域,相应的算法也非常的多。本文仅介绍一种最简单的聚类算法——k均值(k-means)算法。
三、概念介绍
区分两个概念:
hardclustering:一个文档要么属于类w,要么不属于类w,即文档对确定的类w是二值的1或0。
softclustering:一个文档可以属于类w1,同时也可以属于w2,而且文档属于一个类的值不是0或1,。
K-Means就是一种hardclustering,所谓K-means里的K就是我们要事先指定分类的个数,即K个。
k-means算法的流程如下:
1)从N个文档随机选取K个文档作为初始质心
  
为了取得RSS的极小值,RSS对质心求偏导数应该为0,所以得到质心
      
可见,这个质心的选择是合乎数学原理的。
 
K-means方法的缺点是聚类结果依赖于初始选择的几个质点位置,看下面这个例子:
如果使用2-means方法,初始选择d2和d5那么得到的聚类结果就是{d1,d2,d3}{d4,d5,d6},这不是一个合理的聚类结果
解决这种初始种子问题的方案:
1)去处一些游离在外层的文档后再选择
2)多选一些种子,取结果好的(RSS小)的K个类继续算法
3)用层次聚类的方法选择种子。我认为这不是一个合适的方法,因为对初始N个文档进行层次聚类代价非常高。
以上的讨论都是基于K是已知的,但是我们怎么能从随机的文档集合中选择这个k值呢?
我们可以对k去1~N分别执行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年间大型杯赛的战绩(由于澳大利亚是后来加入亚足联的,所以这里没有收录)。
其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理:对于世界杯,进入决赛圈则取其最终排名,没有进入决赛圈的,打入预选赛十强赛赋予40,预选赛小组未出线的赋予50。对于亚洲杯,前四名取其排名,八强赋予5,十六强赋予9,预选赛没出现的赋予17。这样做是为了使得所有数据变为标量,便于后续聚类
。
下面先对数据进行[0,1]规格化,下面是规格化后的数据:
其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理:对于世界杯,进入决赛圈则取其最终排名,没有进入决赛圈的,打入预选赛十强赛赋予40,预选赛小组未出线的赋予50。对于亚洲杯,前四名取其排名,八强赋予5,十六强赋予9,预选赛没出现的赋予17。这样做是为了使得所有数据变为标量,便于后续聚类。
下面先对数据进行[0,1]规格化,下面是规格化后的数据:
从做到右依次表示各支球队到当前中心点的欧氏距离,将每支球队分到最近的簇,可对各支球队做如下聚类:
中国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,,}。
用调整后的中心点再次进行聚类,得到: