《聚类分析实例（6.29）.pdf》由会员分享，可在线阅读，更多相关《聚类分析实例（6.29）.pdf（9页珍藏版）》请在金锄头文库上搜索。
1、学 海 无 涯 k k- -meansmeans 聚类聚类”数据分析、数据挖掘数据分析、数据挖掘 一、概要 分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并 且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满 足， 尤其是在处理海量数据的时候，如果通过预处理使得数据满足分类算法的要 求，则代价非常大，这时候可以考虑使用聚类算法。聚类属于无监督学习，相比聚类属于无监督学习，相比 于分类， 聚类不依赖预定义的类和类标号的训练实例于分类， 聚类不依赖预定义的类和类标号的训练实例。 本文介绍一种常见的聚类 算法k 均值和 k 中心点聚类，最后会举一个实例：应用聚类方法
2、试图解决 一个在体育界大家颇具争议的问题中国男足近几年在亚洲到底处于几流水 平。 二、聚类问题 所谓聚类问题，就是给定一个元素集合所谓聚类问题，就是给定一个元素集合 D D，其中每个元素具有，其中每个元素具有 n n 个可观个可观 察属性，使用某种算法将察属性，使用某种算法将 D D 划分成划分成 k k 个子集，要求每个子集内部的元素之间相个子集，要求每个子集内部的元素之间相 异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。 与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个 元素映射到
3、一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给 定类别数量，是无监督学习的一种。目前聚类广泛应用于统计学、生物学、数据 库技术和市场营销等领域，相应的算法也非常的多。本文仅介绍一种最简单的聚 类算法k 均值（k-means）算法。 三、概念介绍 区分两个概念： hard clustering：一个文档要么属于类 w，要么不属于类 w，即文档对确定的类 w 是二值的 1 或 0。 soft clustering：一个文档可以属于类 w1，同时也可以属于 w2，而且文档属于 一个类的值不是 0 或 1，可以是 0.3 这样的小数。 K-Means 就是一种 hard clusteri
4、ng，所谓 K-means 里的 K 就是我们要事先指定 分类的个数，即 K 个。 k-means 算法的流程如下：算法的流程如下： 1）从）从 N 个文档随机选取个文档随机选取 K 个文档作为初始质心个文档作为初始质心 学 海 无 涯 2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类 3）重新计算已经得到的各个类的质心）重新计算已经得到的各个类的质心 4）迭代）迭代 23 步直至满足既定的条件，算法结束步直至满足既定的条件，算法结束 在 Kmeans 算法里所有的文档都必须向量化，n 个文档的质心可以认为是
5、这 n 个向量的中心，计算方法如下： 这里加入一个方差 RSS 的概念： RSSk 的值是类 k 中每个文档到质心的距离， RSS 是所有 k 个类的 RSS 值的和。 算法结束条件： 1）给定一个迭代次数，达到这个次数就停止，这好像不是一个好建议。 2） k 个质心应该达到收敛， 即第 n 次计算出的 n 个质心在第 n1 次迭代时候位 置不变。 3） n 个文档达到收敛， 即第 n 次计算出的 n 个文档分类和在第 n1 次迭代时候 文档分类结果相同。 4）RSS 值小于一个阀值，实际中往往把这个条件结合条件 1 使用 回过头用 RSS 讨论质心的计算方法是否合理 学 海 无 涯 为了取得
6、 RSS 的极小值，RSS 对质心求偏导数应该为 0，所以得到质心 可见，这个质心的选择是合乎数学原理的。 K-means 方法的缺点是聚类结果依赖于初始选择的几个质点位置，看下面这个 例子： 如果使用 2means 方法，初始选择 d2 和 d5 那么得到的聚类结果就是d1， d2，d3d4，d5，d6，这不是一个合理的聚类结果 解决这种初始种子问题的方案： 学 海 无 涯 1）去处一些游离在外层的文档后再选择 2）多选一些种子，取结果好的（RSS 小）的 K 个类继续算法 3）用层次聚类的方法选择种子。我认为这不是一个合适的方法，因为对初始 N 个文档进行层次聚类代价非常高。 以上的讨论都
7、是基于 K 是已知的，但是我们怎么能从随机的文档集合中选择这 个 k 值呢？ 我们可以对 k 去 1N 分别执行 k-means，得到 RSS 关于 K 的函数下图： 当 RSS 由显著下降到不是那么显著下降的 K 值就可以作为最终的 K，如图可以 选择 4 或 9。 四、算法及示例 学 海 无 涯 k k 均值算法的计算过程非常直观：均值算法的计算过程非常直观： 1 1、从、从 D D 中随机取中随机取 k k 个元素，作为个元素，作为 k k 个簇的各自的中心。个簇的各自的中心。 2 2、分别计算剩下的元素到、分别计算剩下的元素到 k k 个簇中心的相异度，将这些元素分别划归到相异度最低的
8、簇。个簇中心的相异度，将这些元素分别划归到相异度最低的簇。 3 3、根据聚类结果，重新计算、根据聚类结果，重新计算 k k 个簇各自的中心，计算方法是取簇中所有元素各自维度的算个簇各自的中心，计算方法是取簇中所有元素各自维度的算 术平均数。术平均数。 4 4、将、将 D D 中全部元素按照新的中心重新聚类。中全部元素按照新的中心重新聚类。 5 5、重复第、重复第 4 4 步，直到聚类结果不再变化。步，直到聚类结果不再变化。 6 6、将结果输出。、将结果输出。 由于算法比较直观，没有什么可以过多讲解的。下面，我们来看看 k-means 算法一个有趣 的应用示例：中国男足近几年到底在亚洲处于几流水
9、平？ 今年中国男足可算是杯具到家了， 几乎到了过街老鼠人人喊打的地步。 对于目前中国男足在 亚洲的地位，各方也是各执一词，有人说中国男足亚洲二流，有人说三流，还有人说根本不 入流，更有人说其实不比日韩差多少，是亚洲一流。既然争论不能解决问题，我们就让数据 告诉我们结果吧。 下图是采集的亚洲 15 只球队在 XXXX 年-XXXX 年间大型杯赛的战绩（由于澳大利亚是后来 加入亚足联的，所以这里没有收录）。 学 海 无 涯 其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理：对于世界杯，进入决赛 圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予 40，预选赛小组未出线的 赋予 50
10、。对于亚洲杯，前四名取其排名，八强赋予 5，十六强赋予 9，预选赛没出现的赋予 17。这样做是为了使得所有数据变为标量，便于后续聚类。 下面先对数据进行0,1规格化，下面是规格化后的数据： 学 海 无 涯 其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理：对于世界杯，进入决赛 圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予 40，预选赛小组未出线的 赋予 50。对于亚洲杯，前四名取其排名，八强赋予 5，十六强赋予 9，预选赛没出现的赋予 17。这样做是为了使得所有数据变为标量，便于后续聚类。 下面先对数据进行0,1规格化，下面是规格化后的数据： 从做到右依次表示各支球队到当
11、前中心点的欧氏距离， 将每支球队分到最近的簇， 可对各支 球队做如下聚类： 中国 C，日本 A，韩国 A，伊朗 A，沙特 A，伊拉克 C，卡塔尔 C，阿联酋 C，乌兹别克斯坦 B， 泰国 C，越南 C，阿曼 C，巴林 B，朝鲜 B，印尼 C。 第一次聚类结果： A：日本，韩国，伊朗，沙特； B：乌兹别克斯坦，巴林，朝鲜； C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼。 下面根据第一次聚类结果，调整各个簇的中心点。 学 海 无 涯 A 簇的新中心点为： (0.3+0+0.24+0.3)/4=0.21， (0+0.15+0.76+0.76)/4=0.4175,(0.19+0.13+0.
12、25+0.06)/4=0.1575 = 0.21, 0.4175, 0.1575 用同样的方法计算得到 B 和 C 簇的新中心点分别为0.7, 0.7333, 0.4167，1, 0.94,0.40625。 用调整后的中心点再次进行聚类，得到： 第二次迭代后的结果为： 中国 C，日本 A，韩国 A，伊朗 A，沙特 A，伊拉克 C，卡塔尔 C，阿联酋 C，乌兹别克斯坦 B， 泰国 C，越南 C，阿曼 C，巴林 B，朝鲜 B，印尼 C。 结果无变化，说明结果已收敛，于是给出最终聚类结果： 亚洲一流：日本，韩国，伊朗，沙特 亚洲二流：乌兹别克斯坦，巴林，朝鲜 亚洲三流：中国，伊拉克，卡塔尔，阿联酋，
13、泰国，越南，阿曼，印尼 看来数据告诉我们， 说国足近几年处在亚洲三流水平真的是没有冤枉他们， 至少从国际杯赛 战绩是这样的。 学 海 无 涯 其实上面的分析数据不仅告诉了我们聚类信息， 还提供了一些其它有趣的信息， 例如从中可 以定量分析出各个球队之间的差距，例如，在亚洲一流队伍中，日本与沙特水平最接近，而 伊朗则相距他们较远，这也和近几年伊朗没落的实际相符。另外，乌兹别克斯坦和巴林虽然 没有打进近两届世界杯，不过凭借预算赛和亚洲杯上的出色表现占据 B 组一席之地，而朝 鲜由于打入了 XXXX 世界杯决赛圈而有幸进入 B 组，可是同样奇迹般夺得 XXXX 年亚洲杯的 伊拉克却被分在三流， 看来亚洲杯冠军的分量还不如打进世界杯决赛圈重啊。 其它有趣的信 息，有兴趣的朋友可以进一步挖掘。
