聚类算法 -- kmeans 算法


无法舍弃两个方中的任何一方,那不是温柔,那不过是软弱罢了 - 东京食尸鬼


算法流程

  1. 随机的取 k 个点作为 k 个初始质心
  2. 计算其他点到这个 k 个质心的距离
  3. 如果某个点 p 离第 n 个质心的距离更近,则该点属于 cluster n
  4. 计算同一 cluster 中,也就是相同 label 的点向量的平均值,作为新的质心
  5. 迭代至所有质心都不变化为止,即算法结束

K-means


算法过程演示

转载:http://www.cnblogs.com/leoo2sk/archive/2010/09/20/k-means.html

下图是亚洲15只球队在2005年-2010年间大型杯赛的战绩

其中包括两次世界杯和一次亚洲杯。对数据做了如下预处理:对于世界杯,进入决赛圈则取其最终排名,没有进入决赛圈的,打入预选赛十强赛赋予40,预选赛小组未出线的赋予50。对于亚洲杯,前四名取其排名,八强赋予5,十六强赋予9,预选赛没出现的赋予17。这样做是为了使得所有数据变为标量,便于后续聚类

对数据进行[0,1]归约化处理

接着用k-means算法进行聚类。设k=3,即将这15支球队分成三个集团

现抽取日本、巴林和泰国的值作为三个簇的种子,即初始化三个簇的中心为A:{0.3, 0, 0.19},B:{0.7, 0.76, 0.5}和C:{1, 1, 0.5}。下面,计算所有球队分别对三个中心点的相异度,这里以欧氏距离度量。下面是用程序求取的结果:

从做到右依次表示各支球队到当前中心点的欧氏距离,将每支球队分到最近的簇,可对各支球队做如下聚类:

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.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

结果无变化,说明结果已收敛,于是给出最终聚类结果:

A:日本,韩国,伊朗,沙特 B:乌兹别克斯坦,巴林,朝鲜 C:中国,伊拉克,卡塔尔,阿联酋,泰国,越南,阿曼,印尼


评价

k 均值适用于绝大多数的数据类型,并且简单有效。但其缺点就是需要知道准确的 k 值,并且不能处理异形簇,比如球形簇,不同尺寸及密度的簇,环形簇等等