文档介绍：聚类算法实践（一）一层次聚类、K-means聚类1
聚类算法实践（2）——谱聚类、Chameleon聚类6
聚类算法实践（3）——PCCA、SOM、AffinityPropagat13
聚类算法实践（一）一一层次聚类、K-means聚size不太敏感。
1D152D2530354045
如何确定应该取多少个cluster？这是聚类里面的一个非常重要的问题。对于层次聚类，可以根据聚类过程中，每次合并的两个cluster的距离来作大概判断，如下图。因为总共有2000个数据点，每次合并两个cluster，所以总共要做2000次合并。从图中可以看到在后期合并的两个cluster的距离会有一个陡增。假如数据的分类是十分显然的，就是应该被分为K个大的cluster，K个cluster之间有明显的间隙。那么如果合并的两个小cluster同属于一个目标cluster，那么它们的距离就不会太大。但当合并出来K个目标cluster后，再进行合并，就是在这K个cluster间进行合并了，这样合并的cluster的距离就会有一个非常明显的突变。当然，这是十分理想的情况，现实情况下突变没有这么明显，我们只能根据下图做个大致的估计。
Ian1300lift)UK®ITOismIffiOMB
聚类步数
对于测试样品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的中心，并且最小化函数
k
argmin工収j_他『
吕i=1jcjes；
其中就是第i个cluster的中心。上式就是要求每个数据点要与它们所属cluster的中心尽量接近。
为了得到每个cluster的中心，K-means迭代地进行两步操作。首先随机地给出k个中心的位置，然后把每个数据点归类到离它最近的中心，这样我们就构造了k个cluster。但是，这k个中心的位置显然是不正确的，所以要把中心转移到得到的cluster内部的数据点的平均位置。实际上也就是计算，在每个数据点的归类确定的情况下，上面函数取极值的位置，然后再次构造新的k个cluster。这个过程中，中心点的位置不断地改变，构造出来的cluster的也在变化（动画请看这里）。通过多次的迭代，这k个中心最终会收敛并不再移动。
K-means实际上是EM算法的一个特例（关于EM算法，请猛击这里和这里），根据中心点决定数据点归属是expectation，而根据构造出来的cluster更新中心则是maximizationo理解了K-means，也就顺带了解了基本的EM算法思路。
实际应用里，人们指出了很多K-means的不足。比如需要用户事先给出聚类数目k，而这个往往是很难判断的；又如K-means得到的是局域最优，跟初始给定的中心值有关，所以往往要尝试多个初始值；总是倾向于得到大小接近的凸型cluster等等。
r—LLLr—LLLr—LLLr—LLLr—LLL—LLLir—LLLir—LLLir—LLLir—LLLir—LLLir—LLLir
K-means算法相比起上面提到的层次聚类，还有一个很大的不同，那就是它需要数据点的坐标，因为它必须要求取平均，而层次聚类实际上并不需要坐标数据，只需要知道数据点之间的距离而已。这也就是说K-means只适用于使用欧氏距离来计算数据点相似性的情况，因为如果采用非欧距离，那么也不能通过简单的平均来得到cluster中心。
聚类结果
取k=3，K-means对样品组1聚类得到下面两张图。为什么是两张图呢？正如前面所说,K-means的聚类结果跟初始中心选择有关，而不是所以的初始值都能保证聚类成功的，下面第二张就是失败的例子。另外由于K-means总倾向于得到接近大小的cluster，所以可以看到两个小的cluster对大cluster的“入侵”。
对甜甜圈样品组，K-means也是完全没辙。
从上面的结果可以看出，K-means的聚类效果确实不是很好。用户如果选择了不正确的聚类数目，会使得本应同一个cluster的数据被判定为属于两个大的类别，这是我们不想看到的。因为需要数据点的坐标，这个