Cluster：Hierarchical Clustering

上次学习了K-Means算法之后，本次继续学习另外一种Clustering算法：Hierarchical Clustering算法。Hierarchical Clustering分簇技术在Clustering方法中也是很重要的，其历史比较久远，和K-means一样。尽管如此，这两种算法仍然广泛使用，算是Clustering算法的基本思路了。

按照Clustering形式的不同，Hierarchical Clustering有两种思路：

Agglomerative：聚合思路。就是将每个点都初始化为单个簇，然后在后续迭代过程中逐渐合并类似的簇，直到最后整体成为单簇。

Divisive：拆分思路。将整体数据点看做单簇，在后续迭代过程中每次选择某种标准去拆分其中选择出来的一个簇，知道所有的簇中都只有单个数据点为止。

这是两种截然不同的思路，前者是Down-Top，后者是Top-Down。后者拆分的思路在K-means中的Bisecting K-means算法类似，只是初始条件和收敛条件不一样，迭代过程时一致的。不过按照某种标准拆分簇这个做法可能难度比较大，也不好操作，导致拆分思路的Hierarchical Clustering算法研究不多(我不知道是不是这个原因，仅是猜想)。所以本文也只介绍聚合思路(Agglomerative)的方法讨论。

在Hierarchical Clustering算法开始之前，我们先介绍一个很重要的概念：Dendrogram。wiki地址见这里，http://en.wikipedia.org/wiki/Dendrogram，表示系统树图，实际上可以看做一棵树，能够很好的表示出Hierarchical Clustering算法的结果。

对于Agglomerative Hierarchical Clustering算法的思路在上面提到过，思路比较简单：

 中间提到的Proximity Matrix就是距离的一种度量，对于单个数据作为单个簇的数据度量没有问题。当簇中有很多个数据时，就需要一种距离的度量来衡量簇之间的Distance。注意簇之间的Distance这个概念，和数据点之间的Distance是有区别的。在Hierarchical Clustering使用的距离度量(称为Linkage)形式有以下这么几种：

Single：又被成为Nearest-Neighbour，是取两个集合中最近的两个点作为这两个集合的距离。

Complete：是Single的反面，取两个集合中距离最远的两个点作为两个集合的距离。

Group：将两个集合中的点两两距离加权求和取平均值，相对得到合适的结果。

 unweighted：在UPGMA(Unweighted Pair-Group Method with Arithmetic)中使用这个权重，这里有个算法详细解释了UPGMA的实现过程。http://www.southampton.ac.uk/~re1u06/teaching/upgma/，这个教程理解透彻，对于理解Hierarchical Clustering很关键。

centroid：和k-means类似，注意这个是集合之间的linkage。

ward：这个距离也可以看做是一种目标函数，在迭代过程中计算簇内的方差。wiki参考这里：http://en.wikipedia.org/wiki/Ward%27s_method，在wiki上提到了一种Lance-Williams算法度量簇见的相似性或者距离，将前面提到的各种度量标准全部统一起来，感兴趣的同学可以看下。 

对于上面提到的度量，Single会将结果扩散，如两个Cluster比较远，但是个别点比较接近就被合并，结果会比较松散。Complete则相反，由于个别点比较远，导致两个比较接近的簇会抗拒合并到底。Group是相对温和的做法，只是计算量相对比较大。

时间和空间分析：

在空间上，Agglomerative Hierarchical Clustering需要保存数据点之间的距离矩阵，所以需要m*m个存储空间，其中m表示数据点数量；由于距离矩阵是对称的，只需要保存m*m/2空间；所以总体的空间复杂度是O(m*m)。

在时间复杂度上，需要计算数据点之间的距离，需要O(m*m)的时间复杂度；并且每次迭代只能产生合并两个簇，所以需要m-1词迭代，所以总的时间复杂度是O(m*m*m)。根据这里http://www.southampton.ac.uk/~re1u06/teaching/upgma/的算法流程，实际上不需要每次迭代过程中更新全部的距离矩阵，只需要更新O(m-i+1)个数据，即只更新对应簇相对于其他簇的距离，对于没有距离变化的簇不用更新距离。所以计算后总体的时间复杂度为O(m*m*logm)。 

Hierarchical Clustering算法的复杂度和K-means相比要复杂许多，尽管其描述不麻烦。计算量大，并且是贪心运算，不能保证全局最优。所以其使用范围，或者说实际用途，并不如Flat Clustering算法广泛。

Hierarchical Clustering需要注意的有这么几个问题：

1：没有全局目标函数

在Hierarchical Clustering中，每次迭代的过程都是局部(Local)最优，对于最终分簇结果缺少目标函数度量。缺少目标函数能够避免解决组合优化问题，但是这并不是个优点。我们在分簇算法中，对于最终的分簇结果有个最终的衡量标准，确定我们的分簇结果是否正确，如K-Means算法的SSE标准。在Hierarchical Clustering算法中，就没有标准对最终的分簇结果进行衡量。

2：对于簇内数据量的处理能力

簇内数据量的不同也是一种分簇的内在隐含变量，常规的Hierarchical Clustering算法将数据点设定为权重相同。实际上应该将这个因素纳入考虑范围，前面提到的UPGMA算法就将簇内数据量考虑，实际上在Hierarchical Clustering中，如果没有特殊的考虑，将数据点纳入考虑的UPGMA算法总是比较受欢迎的。

3：簇合并问题

在每次簇合并过程中，都会从当前距离矩阵中选择距离最小的簇进行合并，该合并动作一旦进行，后面就不可逆转了。这种操作会阻止局部最优成为全局最优，这个实际上贪心算法的弊病。

对于簇合并使用的贪心算法，也有一些方法来解除这个限制：如将簇分支移位，跳出局部最优；对簇中的部分数据量使用其它Clustering技术，如K-Means算法等。这些方法都是改变局部数据特性，增加数据跳出局部最优的可能，以期望达到全局最优。

优点：

1：潜在的使用场景，如分类学、或者本身就需要这种按照层次进行分类的地方就有不错的效果。

2：这种层次聚类在某些场景下会有不错的效果，研究证明(这一点我也说不准是哪些研究)。

缺点：

1：计算量大

2：目标函数不明，不容易对分类效果量化比较

3：簇合并后不可逆转，将局部最优作为全局最优解。

这些缺点并不影响我们对这种层次聚类的使用，有时候还会有出其不意的效果，我们先看下Hierarchical Clustering算法的过程：

算法细节可以参考这里：http://harthur.github.com/clusterfck/demos/colors/

其实算法的难点不是计算过程，而是使用准确的数据结构，将分簇数据保存；然后再使用Dendrogram将结果绘制出来。

本文到此结束，大家可以自行揣摩进一步的学习。