聚类系列：
聚类(序)—-监督学习与无监督学习聚类(1)—-混合高斯模型 Gaussian Mixture Model 聚类(2)—-层次聚类 Hierarchical Clustering聚类(2*)—-k-means如何训练很大的码书聚类(3)—-谱聚类 Spectral Clustering
——————————–
假设有N个待聚类的样本，对于层次聚类来说，基本步骤就是：
1、（初始化）把每个样本归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度；
2、寻找各个类之间最近的两个类，把他们归为一类（这样类的总数就少了一个）；
3、重新计算新生成的这个类与各个旧类之间的相似度；
4、重复2和3直到所有样本点都归为一类，结束。
整个聚类过程其实是建立了一棵树，在建立的过程中，可以通过在第二步上设置一个阈值，当最近的两个类的距离大于这个阈值，则认为迭代可以终止。另外关键的一步就是第三步，如何判断两个类之间的相似度有不少种方法。这里介绍一下三种：
SingleLinkage：又叫做 nearest-neighbor ，就是取两个类中距离最近的两个样本的距离作为这两个集合的距离，也就是说，最近两个样本之间的距离越小，这两个类之间的相似度就越大。容易造成一种叫做 Chaining 的效果，两个 cluster 明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后 Chaining 效应会进一步扩大，最后会得到比较松散的 cluster 。
CompleteLinkage：这个则完全是 Single Linkage 的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，，限制非常大，两个 cluster 即使已经很接近了，但是只要有不配合的点存在，就顽固到底，老死不相合并，也是不太好的办法。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据，而没有考虑类内数据的整体特点。
Average-linkage：这种方法就是把两个集合中的点两两的距离全部放在一起求一个平均值，相对也能得到合适一点的结果。
average-linkage的一个变种就是取两两距离的中值，与取均值相比更加能够解除个别偏离样本对结果的干扰。
的方法对新闻进行分类。在已知一些新闻类别的特征的情况下，采用监督学习的方法是很OK的。但是在未知的情况下，就采用这种agglomerative hierarchical clustering进行自动分类。这种分类方法的动机很有意思。1998年雅让斯基是某个国际会议的程序委员会主席，需要把提交上来的几百篇论文发给各个专家去评审是否录用。虽然论文的作者自己给定了论文的方向，但方向还是太广，没有什么指导意义。雅让斯基就想到了这个将论文自动分类的方法，由他的学生费罗里安很快实现了。
另外有一种聚类方法叫做divisive hierarchical clustering（自顶而下），过程恰好是相反的，一开始把所有的样本都归为一类，然后逐步将他们划分为更小的单元，直到最后每个样本都成为一类。在这个迭代的过程中通过对划分过程中定义一个松散度，当松散度最小的那个类的结果都小于一个阈值，则认为划分可以终止。这种方法用的不普遍，原文也没有做更多介绍。
由于这种层次结构，普通的k-means也被称为一种flat clustering。
add@2013.9.11
层次聚类如何使用呢，借助matlab就可以实现了，十分简单。首先需要构造距离矩阵Y。这是一个对称矩阵，且对角线元素为0（自己与自己的距离为0）。假设所有样本保存为X，则通过：
Y=pdist(X);Y=squareform(Y);
就能够得到距离矩阵。注意pdist可以选择距离度量的方法，例如欧式距离，内积或者余弦夹角。在很多时候这个参数十分重要。
然后通过Z=linkage(Y)就能产生层次聚类的树结构了。
Z=linkage(Y)；
Z的结果描述起来需要借助实际的例子，大家可以通过matlab help查看，并结合实际结果领悟一下。这棵树可以通过以下指令可视化：
dendrogram(Z)
这样就完成了一次层次聚类了（虽然我们什么都没有做）
—————————
jiang1st2010
原文地址：
坚硬的城市里没有柔软的爱情，生活不是林黛玉，
