Cluster：Hierarchical Clustering

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算法的过程：

var HierarchicalClustering = function(distance, linkage, threshold) {
         this.distance = distance;
         this.linkage = linkage;
         this.threshold = threshold == undefined ? Infinity : threshold;
    }
    
    HierarchicalClustering.prototype = {
        cluster: function(items, snapshotPeriod, snapshotCb) {
            this.clusters = [];
            this.dists = []; // distances between each pair of clusters
            this.mins = []; // closest cluster for each cluster
            this.index = []; // keep a hash of all clusters by key
            
            for (var i = 0; i < items.length; i++) {
                var cluster = {
                    value: items[i],
                    key: i,
                    index: i,
                    size: 1
                };
                this.clusters[i] = cluster;
                this.index[i] = cluster;
                this.dists[i] = [];
                this.mins[i] = 0;
        }
        
        for (var i = 0; i < this.clusters.length; i++) {
            for (var j = 0; j <= i; j++) {
                var dist = (i == j) ? Infinity : 
                this.distance(this.clusters[i].value, this.clusters[j].value);
                this.dists[i][j] = dist;
                this.dists[j][i] = dist;
                
                if (dist < this.dists[i][this.mins[i]]) {
                    this.mins[i] = j;
                }
            }
        }
        
        var merged = this.mergeClosest();
        var i = 0;
        while (merged) {
            if (snapshotCb && (i++ % snapshotPeriod) == 0) {
                snapshotCb(this.clusters);
            }
            merged = this.mergeClosest();
        }
        
        this.clusters.forEach(function(cluster) {
            // clean up metadata used for clustering
            delete cluster.key;
            delete cluster.index;
        });
        
    return this.clusters;
    },
    
    mergeClosest: function() {
        // find two closest clusters from cached mins
        var minKey = 0, min = Infinity;
        for (var i = 0; i < this.clusters.length; i++) {
            var key = this.clusters[i].key, 
            dist = this.dists[key][this.mins[key]];
            if (dist < min) {
                minKey = key;
                min = dist;
            }
        }
        if (min >= this.threshold) {
            return false;
        }
        
        var c1 = this.index[minKey], 
        c2 = this.index[this.mins[minKey]];

        // merge two closest clusters
        var merged = {
            left: c1,
            right: c2,
                key: c1.key,
                size: c1.size + c2.size
            };
            
        this.clusters[c1.index] = merged;
        this.clusters.splice(c2.index, 1);
        this.index[c1.key] = merged;

         // update distances with new merged cluster
         for (var i = 0; i < this.clusters.length; i++) {
             var ci = this.clusters[i];
             var dist;
             if (c1.key == ci.key) {
                 dist = Infinity;
             } 
             else if (this.linkage == "single") {
                 dist = this.dists[c1.key][ci.key];
                 if (this.dists[c1.key][ci.key] > this.dists[c2.key][ci.key]) {
                     dist = this.dists[c2.key][ci.key];
                 }
             } 
             else if (this.linkage == "complete") {
                 dist = this.dists[c1.key][ci.key];
                 if (this.dists[c1.key][ci.key] < this.dists[c2.key][ci.key]) {
                     dist = this.dists[c2.key][ci.key];
                 }
             } 
             else if (this.linkage == "average") {
                 dist = (this.dists[c1.key][ci.key] * c1.size 
                 + this.dists[c2.key][ci.key] * c2.size) / (c1.size + c2.size);
             } 
             else {
                 dist = this.distance(ci.value, c1.value);
             }
             
             this.dists[c1.key][ci.key] = this.dists[ci.key][c1.key] = dist;
         }


         // update cached mins
         for (var i = 0; i < this.clusters.length; i++) {
             var key1 = this.clusters[i].key;
             if (this.mins[key1] == c1.key || this.mins[key1] == c2.key) {
                 var min = key1;
                 for (var j = 0; j < this.clusters.length; j++) {
                     var key2 = this.clusters[j].key;
                     if (this.dists[key1][key2] < this.dists[key1][min]) {
                         min = key2;
                     }
                 }
                 this.mins[key1] = min;
             }
             this.clusters[i].index = i;
         }

         // clean up metadata used for clustering
         delete c1.key;
         delete c2.key;
         delete c1.index;
         delete c2.index;
         
         return true;
     }

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

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

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