区分两个概念：

hard clustering：一个文档要么属于类w，要么不属于类w，即文档对确定的类w是二值的1或0。

soft clustering：一个文档可以属于类w1，同时也可以属于w2，而且文档属于一个类的值不是0或1，可以是0.3这样的小数。

K-Means就是一种hard clustering，所谓K-means里的K就是我们要事先指定分类的个数，即K个。

k-means算法的流程如下：

1）从N个文档随机选取K个文档作为初始质心

2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类

3）重新计算已经得到的各个类的质心

4）迭代2～3步直至满足既定的条件，算法结束

在K－means算法里所有的文档都必须向量化，n个文档的质心可以认为是这n个向量的中心，计算方法如下：

这里加入一个方差RSS的概念：

RSSk的值是类k中每个文档到质心的距离，RSS是所有k个类的RSS值的和。

算法结束条件：

1）给定一个迭代次数，达到这个次数就停止，这好像不是一个好建议。

2）k个质心应该达到收敛，即第n次计算出的n个质心在第n＋1次迭代时候位置不变。

3）n个文档达到收敛，即第n次计算出的n个文档分类和在第n＋1次迭代时候文档分类结果相同。

4）RSS值小于一个阀值，实际中往往把这个条件结合条件1使用

回过头用RSS讨论质心的计算方法是否合理

为了取得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.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。

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

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

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

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

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

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