文档介绍：聚类算法实践（1）
层次、K-means聚类
男人海洋发表于2013-08-2914:33来源：数据之城
所谓聚类，就是将相似的事物聚集在一起，而将不相似的事物划分到不同的类别的过
程，是数据分析之中十分重要的一种i i i
、 5 10 15 SO §5 30 35 40 45
如何确定应该取多少个cluster?这是聚类里面的一个非常重要的问题。对于层次聚类， 可以根据聚类过程中，每次合并的两个cluster的距离来作大概判断，如下图。因为总共有 2000个数据点，每次合并两个cluster，所以总共要做2000次合并。从图中可以看到在后 期合并的两个cluster的距离会有一个陡增。假如数据的分类是十分显然的，就是应该被分 为K个大的cluster，K个cluster之间有明显的间隙。那么如果合并的两个小cluster同属 于一个目标cluster，那么它们的距离就不会太大。但当合并出来K个目标cluster后，再 进行合并，就是在这K个cluster间进行合并了，这样合并的cluster的距离就会有一个非 常明显的突变。当然，这是十分理想的情况，现实情况下突变没有这么明显，我们只能根据 下图做个大致的估计。
一 一 一 一一 IbILI/ 口 CDouffi切Q
1200 1300 1400 1500 1E00
聚类步数
对于测试样品2 , average-linkage可谓完全失效，这是由于它对"相似性"的理解造
成的，所以只能得到凸型的cluster。
总体而言，像average-linkage这样的算法还是比较稳定的可以大致地判断聚类数目，
聚类效果也不错，在数据量比较小的时候可以使用。
3、K-means 算法
K-means 是最为常用的聚类方法之一，尽管它有着很多不足，但是它有着一个很关键
的优点：快！ K-means的计算复杂度只有O(tkn)，t是迭代次数，k是设定的聚类数目， 而n是数据量，相比起很多其它算法，K-means算是比较高效的。
K-means 的目标是要将数据点划分为k个cluster，找到这每个cluster的中心，并且
最小化函数
arg min £ I凶—％ K
' ?'=1 XjfzSi
其中山就是第i个cluster的中心。上式就是要求每个数据点要与它们所属cluster的中心 尽量接近。
为了得到每个cluster的中心，K-means迭代地进行两步操作。首先随机地给出k个中 心的位置，然后把每个数据点归类到离它最近的中心，这样我们就构造了 k个cluster。但 是，这k个中心的位置显然是不正确的，所以要把中心转移到得到的cluster内部的数据点 的平均位置。实际上也就是计算，在每个数据点的归类确定的情况下，上面函数取极值的位 置，然后再次构造新的k个cluster。这个过程中，中心点的位置不断地改变，构造出来的 cluster的也在变化（动画请看这里）。通过多次的迭代，这k个中心最终会收敛并不再移 动。
K-means 实际上是EM算法的一个特例（关于EM算法，请猛击这里和这里），根据
中心点决定数据点归属是expectation，而根据构造出来的cluster更新中心则是 maximization。理解了 K-means，也就顺带了解了基本的EM算法思路。
实际应用里，人们指出了很多K-means的不足。比如需要用户事先给出聚类数目k， 而这个往往是很难判断的；又如K-means得到的是局域最优，跟初始给定的中心值有关， 所以往往要尝试多个初始值；总是倾向于得到大小接近的凸型cluster等等。
K-means 算法相比起上面提到的层次聚类，还有一个很大的不同，那就是它需要数据 点的坐标，因为它必须要求取平均，而层次聚类实际上并不需要坐标数据，只需要知道数据 点之间的距离而已。这也就是说K-means只适用于使用欧氏距离来计算数据点相似性的情 况，因为如果采用非欧距离，那么也不能通过简单的平均来得到cluster中心。
聚类结果
取k=3 , K-means对样品组1聚类得到下面两张图。为什么是两张图呢？正如前面所 说，K-means的聚类结果跟初始中心选择有关而不是所以的初始值都能保证聚类成功的， 下面第二张就是失败的例子。另外由于K-means总倾向于得到接近大小的cluster，所以 可以看到两个小的cluster对大cluster的"入侵"。
36
30
即
15
10
§ I I I I I I I I
□ 5 10 15 '§0 躬 ^0 35 40