聚类算法-k均值聚类（K-means）
⼀、简介
分类作为⼀种监督学习⽅法，要求必须事先明确知道各个类别的信息，并且断⾔所有待分类项都有⼀个类别与之对应。但是很多时候上述条件得不到满⾜，尤其是在处理海量数据的时候，如果通过预处理使得数据满⾜分类算法的要求，则代价⾮常⼤，这时候可以考虑使⽤聚类算法。聚类属于⽆监督学习，相⽐于分类，聚类不依赖预定义的类和类标号的训练实例。本⽂⾸先介绍聚类的基础——距离与相异度，然后介绍⼀种常见的聚类算法——k均值和k中⼼点聚类。
⼆、相异度计算
在正式讨论聚类前，我们要先弄清楚⼀个问题：如何定量计算两个可⽐较元素间的相异度。⽤通俗的话说，相异度就是两个东西差别有多⼤，例如⼈类与章鱼的相异度明显⼤于⼈类与⿊猩猩的相异度，这是能我们直观感受到的。但是，计算机没有这种直观感受能⼒，我们必须对相异度在数学上进⾏定量定义。
设，其中X，Y是两个元素项，各⾃具有n个可度量特征属性，那么X和Y的相异度定义为：，其中R为实数域。也就是说相异度是两个元素对实数域的⼀个映射，所映射的实数定量表⽰两个元素的相异度。
下⾯介绍不同类型变量相异度计算⽅法。
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。
2.2、⼆元变量
周杰伦 minemine所谓⼆元变量是只能取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系数，是⼀个⾮常重要的概念。
2.3、分类变量
分类变量是⼆元变量的推⼴，类似于程序中的枚举变量，但各个值没有数字或序数意义，如颜⾊、民族等等，对于分类变量，⽤“取值不同的同位属性数/单个元素的全部属性数”来标识其相异度。
2.4、序数变量
序数变量是具有序数意义的分类变量，通常可以按照⼀定顺序意义排列，如冠军、亚军和季军。对于序数变量，⼀般为每个值分配⼀个数，叫做这个值的秩，然后以秩代替原值当做标量属性计算相异度。
2.5、向量
对于向量，由于它不仅有⼤⼩⽽且有⽅向，所以闵可夫斯基距离不是度量其相异度的好办法，⼀种流⾏的做法是⽤两个向量的余弦度量，其度量公式为：
其中||X||表⽰X的欧⼏⾥得范数。要注意，余弦度量度量的不是两者的相异度，⽽是相似度！
三、聚类问题
在讨论完了相异度计算的问题，就可以正式定义聚类问题了。
所谓聚类问题，就是给定⼀个元素集合D，其中每个元素具有n个可观察属性，使⽤某种算法将D划分成k个⼦集，要求每个⼦集内部的元素之间相异度尽可能低，⽽不同⼦集的元素相异度尽可能⾼。其中每个⼦集叫做⼀个簇。
传奇站歌与分类不同，分类是⽰例式学习，要求分类前明确各个类别，并断⾔每个元素映射到⼀个类别，⽽聚类是观察式学习，在聚类前可以不知道类别甚⾄不给定类别数量，是⽆监督学习的⼀种。⽬前聚类⼴泛应⽤于统计学、⽣物学、数据库技术和市场营销等领域，相应的算法也⾮常的多。本⽂仅介绍⼀种最简单的聚类算法——k均值（k-means）算法。
四、K-means算法及其⽰例
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]规格化，下⾯是规格化后的数据：
接着⽤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年亚洲杯的伊拉克却被分在三流，看来亚洲杯冠军的分量还不如打进世界杯决赛圈重啊。其它有趣的信息，有兴趣的朋友可以进⼀步挖掘。
>有哪些