KMeans的应用

聚类是数据挖掘领域中重要的技术之一，用于发现数据中未知的分类。聚类分析已经有了很长的研究历史，其重要性已经越来越受到人们的肯定。聚类算法是机器学习、数据挖掘和模式识别等研究方向的重要研究内容之一，在识别数据对象的内在关系方面，具有极其重要的作用。聚类主要应用于模式识别中的语音识别、字符识别等，机器学习中的聚类算法应用于图像分割，图像处理中，主要用于数据压缩、信息检索。聚类的另一个主要应用是数据挖掘、时空数据库应用、序列和异常数据分析等。此外，聚类还应用于统计科学，同时，在生物学、地质学、地理学以及市场营销、银行客户等级划分等方面也有着重要的作用。

优点

1.算法快速、简单;
2.当聚类是密集的，且类与类之间区别明显时，效果较好。
3.对大数据集有较高的效率并且是可伸缩性的;
4.时间复杂度近于线性，而且适合挖掘大规模数据集。
K-Means聚类算法的时间复杂度是O(nkt) ,其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目。

缺点

1.在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。

2.在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法，例如文献 中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。

3.从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。

应用案例

k-means算法一个有趣的应用示例：中国男足近几年到底在亚洲处于几流水平？

  今年中国男足可算是杯具到家了，几乎到了过街老鼠人人喊打的地步。对于目前中国男足在亚洲的地位，各方也是各执一词，有人说中国男足亚洲二流，有人说三流，还有人说根本不入流，更有人说其实不比日韩差多少，是亚洲一流。既然争论不能解决问题，我们就让数据告诉我们结果吧。

  下图是我采集的亚洲15只球队在2005年-2010年间大型杯赛的战绩（由于澳大利亚是后来加入亚足联的，所以这里没有收录）。

第十一章 K-Means(K均值)算法模型实现（下）

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

  下面先对数据进行[0,1]规格化，下面是规格化后的数据：

第十一章 K-Means(K均值)算法模型实现（下）

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

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

第十一章 K-Means(K均值)算法模型实现（下）

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

  中国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.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}。

  用调整后的中心点再次进行聚类，得到：

第十一章 K-Means(K均值)算法模型实现（下）

第二次迭代后的结果为：

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

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

  亚洲一流：日本，韩国，伊朗，沙特

  亚洲二流：乌兹别克斯坦，巴林，朝鲜

  亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼

  看来数据告诉我们，说国足近几年处在亚洲三流水平真的是没有冤枉他们，至少从国际杯赛战绩是这样的。

  其实上面的分析数据不仅告诉了我们聚类信息，还提供了一些其它有趣的信息，例如从中可以定量分析出各个球队之间的差距，例如，在亚洲一流队伍中，日本与沙特水平最接近，而伊朗则相距他们较远，这也和近几年伊朗没落的实际相符。另外，乌兹别克斯坦和巴林虽然没有打进近两届世界杯，不过凭借预算赛和亚洲杯上的出色表现占据B组一席之地，而朝鲜由于打入了2010世界杯决赛圈而有幸进入B组，可是同样奇迹般夺得2007年亚洲杯的伊拉克却被分在三流，看来亚洲杯冠军的分量还不如打进世界杯决赛圈重啊。其它有趣的信息，有兴趣的朋友可以进一步挖掘。

上面的应用案例取自参考文献3，资料有点久远，只供学习算法运用。Kmeans算法目前就写这么多，之后有应用与新的自己的改进或想法会继续补充的。

参考文献

1、《机器学习实战》（书）
2、《k-means聚类算法的研究》（硕士论文）
3、算法杂货铺——KMeans均值聚类（博客）
4、 K均值聚类（kmeans）算法及应用（博客）
5、其他各种网站（略）