熟悉算法 --k 均值聚类

1.1、摘要

在前面的文章中，介绍了三种常见的分类算法。分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足，尤其是在处理海量数据的时候，如果通过预处理使得数据满足分类算法的要求，则代价非常大，这时候可以考虑使用聚类算法。聚类属于无监督学习，相比于分类，聚类不依赖预定义的类和类标号的训练实例。本文首先介绍聚类的基础——距离与相异度，然后介绍一种常见的聚类算法——k 均值和 k 中心点聚类，最后会举一个实例：应用聚类方法试图解决一个在体育界大家颇具争议的问题——中国男足近几年在亚洲到底处于几流水平。

1.2、相异度计算

在正式讨论聚类前，我们要先弄清楚一个问题：如何定量计算两个可比较元素间的相异度。用通俗的话说，相异度就是两个东西差别有多大，例如人类与章鱼的相异度明显大于人类与黑猩猩的相异度，这是能我们直观感受到的。但是，计算机没有这种直观感受能力，我们必须对相异度在数学上进行定量定义。

**设，其中 X，Y 是两个元素项，各自具有 n 个可度量特征属性，那么 X 和 Y 的相异度定义为：，其中 R 为实数域。**也就是说相异度是两个元素对实数域的一个映射，所映射的实数定量表示两个元素的相异度。

下面介绍不同类型变量相异度计算方法。

1.2.1、标量

标量也就是无方向意义的数字，也叫标度变量。现在先考虑元素的所有特征属性都是标量的情况。例如，计算 X={2,1,102}和 Y={1,3,2}的相异度。一种很自然的想法是用两者的欧几里得距离来作为相异度，欧几里得距离的定义如下：

其意义就是两个元素在欧氏空间中的集合距离，因为其直观易懂且可解释性强，被广泛用于标识两个标量元素的相异度。将上面两个示例数据代入公式，可得两者的欧氏距离为：

除欧氏距离外，常用作度量标量相异度的还有曼哈顿距离和闵可夫斯基距离，两者定义如下：

曼哈顿距离：

闵可夫斯基距离：

欧氏距离和曼哈顿距离可以看做是闵可夫斯基距离在 p=2 和 p=1 下的特例。另外这三种距离都可以加权，这个很容易理解，不再赘述。

下面要说一下标量的规格化问题。上面这样计算相异度的方式有一点问题，就是取值范围大的属性对距离的影响高于取值范围小的属性。例如上述例子中第三个属性的取值跨度远大于前两个，这样不利于真实反映真实的相异度，为了解决这个问题，一般要对属性值进行规格化。所谓规格化就是将各个属性值按比例映射到相同的取值区间，这样是为了平衡各个属性对距离的影响。通常将各个属性均映射到[0,1]区间，映射公式为：

其中 max(ai)和 min(ai)表示所有元素项中第 i 个属性的最大值和最小值。例如，将示例中的元素规格化到[0,1]区间后，就变成了 X’={1,0,1}，Y’={0,1,0}，重新计算欧氏距离约为 1.732。

1.2.2、二元变量

所谓二元变量是只能取 0 和 1 两种值变量，有点类似布尔值，通常用来标识是或不是这种二值属性。对于二元变量，上一节提到的距离不能很好标识其相异度，我们需要一种更适合的标识。一种常用的方法是用元素相同序位同值属性的比例来标识其相异度。

设有 X={1,0,0,0,1,0,1,1}，Y={0,0,0,1,1,1,1,1}，可以看到，两个元素第 2、3、5、7 和 8 个属性取值相同，而第 1、4 和 6 个取值不同，那么相异度可以标识为 3/8=0.375。一般的，对于二元变量，相异度可用“取值不同的同位属性数/单个元素的属性位数”标识。

上面所说的相异度应该叫做对称二元相异度。现实中还有一种情况，就是我们只关心两者都取 1 的情况，而认为两者都取 0 的属性并不意味着两者更相似。例如在根据病情对病人聚类时，如果两个人都患有肺癌，我们认为两个人增强了相似度，但如果两个人都没患肺癌，并不觉得这加强了两人的相似性，在这种情况下，改用“取值不同的同位属性数/(单个元素的属性位数-同取 0 的位数)”来标识相异度，这叫做非对称二元相异度。如果用 1 减去非对称二元相异度，则得到非对称二元相似度，也叫 Jaccard 系数，是一个非常重要的概念。

1.2.3、分类变量

分类变量是二元变量的推广，类似于程序中的枚举变量，但各个值没有数字或序数意义，如颜色、民族等等，对于分类变量，用“取值不同的同位属性数/单个元素的全部属性数”来标识其相异度。

1.2.4、序数变量

序数变量是具有序数意义的分类变量，通常可以按照一定顺序意义排列，如冠军、亚军和季军。对于序数变量，一般为每个值分配一个数，叫做这个值的秩，然后以秩代替原值当做标量属性计算相异度。

1.2.5、向量

对于向量，由于它不仅有大小而且有方向，所以闵可夫斯基距离不是度量其相异度的好办法，一种流行的做法是用两个向量的余弦度量，其度量公式为：

其中 ||X|| 表示 X 的欧几里得范数。要注意，余弦度量度量的不是两者的相异度，而是相似度！

1.3、聚类问题

在讨论完了相异度计算的问题，就可以正式定义聚类问题了。

所谓聚类问题，就是给定一个元素集合 D，其中每个元素具有 n 个可观察属性，使用某种算法将 D 划分成 k 个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。

与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个元素映射到一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给定类别数量，是无监督学习的一种。目前聚类广泛应用于统计学、生物学、数据库技术和市场营销等领域，相应的算法也非常的多。本文仅介绍一种最简单的聚类算法——k 均值（k-means）算法。

1.4、K-means 算法及其示例

k 均值算法的计算过程非常直观：

1、从 D 中随机取 k 个元素，作为 k 个簇的各自的中心。

2、分别计算剩下的元素到 k 个簇中心的相异度，将这些元素分别划归到相异度最低的簇。

3、根据聚类结果，重新计算 k 个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。

4、将 D 中全部元素按照新的中心重新聚类。

5、重复第 4 步，直到聚类结果不再变化。

6、将结果输出。

伪代码如下

function K-Means(输入数据，中心点个数K)
    获取输入数据的维度Dim和个数N
    随机生成K个Dim维的点
    while(算法未收敛)
        对N个点：计算每个点属于哪一类。
        对于K个中心点：
            1，找出所有属于自己这一类的所有数据点
            2，把自己的坐标修改为这些数据点的中心点坐标
    end
    输出结果：
end

由于算法比较直观，没有什么可以过多讲解的。下面，我们来看看 k-means 算法一个有趣的应用示例：中国男足近几年到底在亚洲处于几流水平？

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

下图是我采集的亚洲 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}。下面，计算所有球队分别对三个中心点的相异度，这里以欧氏距离度量。下面是我用程序求取的结果：

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

中国 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 年亚洲杯的伊拉克却被分在三流，看来亚洲杯冠军的分量还不如打进世界杯决赛圈重啊。其它有趣的信息，有兴趣的朋友可以进一步挖掘。

参考文章

评：

除了普通的 kmeans，还有软聚类（可以得到多个 target 的聚类）kmeans，还有华而不实的 kmeans++，另外，还有一个很牛逼的聚类的框架-canopy，建议可以研究一下，不过 canopy 主要用于分布式环境下的聚类，也有一些缺陷。当时调研的时候也发现了某些地方不好整。
另外对于距离的计算其实也有很多学问的，比如说枚举型 feature 的计算，一般来说不是比较相似程度，而是通过在枚举的方向上对这个 feature 的展开。比如说颜色 {红、绿、蓝}就可以表示为 3 个维度的 0，1 值 feature，工业上一般这样处理。
另外算法的研究和工程上也有一些区别，比如说对于噪音的过滤，怎样合理、快速的归一化等等都是学问