聚类系列-层次聚类（Hierarchical Clustering）

上篇k-means算法却是一种方便好用的聚类算法，但是始终有K值选择和初始聚类中心点选择的问题，而这些问题也会影响聚类的效果。为了避免这些问题，我们可以选择另外一种比较实用的聚类算法-层次聚类算法。顾名思义，层次聚类就是一层一层的进行聚类，可以由上向下把大的类别（cluster）分割，叫作分裂法；也可以由下向上对小的类别进行聚合，叫作凝聚法；但是一般用的比较多的是由下向上的凝聚方法。本文会对分裂法略作简介和举个例子说明，重点介绍凝聚法，并且附上代码。

分裂法：

分裂法指的是初始时将所有的样本归为一个类簇，然后依据某种准则进行逐渐的分裂，直到达到某种条件或者达到设定的分类数目。用算法描述：

输入：样本集合D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）

1.将样本集中的所有的样本归为一个类簇；

repeat：

2.在同一个类簇（计为c）中计算两两样本之间的距离，找出距离最远的两个样本a,b；

3.将样本a，b分配到不同的类簇c1和c2中；

4.计算原类簇（c）中剩余的其他样本点和a，b的距离，若是dis(a)

util：达到聚类的数目或者达到设定的条件

举个例子来说明问题：

在平面上有6个点：p0(1,1), p1(1,2), p2(2,2), p3(4,4), p4(4,5), p5(5,6)，我现在需要对这6个点进行聚类，对应着上边的步骤我可以这样做：

1.将所有的点归为一个类簇c（p0,p1,p2,p3,p4,p5）

repeat:

2.在类簇c中计算他们的距离（简单的欧式距离）我们可以得到：

dis	p0	p1	p2	p3	p4	p5
po	0	1	sqrt(2)	sqrt(18)	5	sqrt(41)
p1	1	0	1	sqrt(13)	sqrt(18)	sqrt(32)
p2	sqrt(2)	1	0	sqrt(8)	sqrt(13)	5
p3	sqrt(18)	sqrt(13)	sqrt(8)	0	1	sqrt(5)
p4	5	sqrt(18)	sqrt(13)	1	0	sqrt(2)
p5	sqrt(41)	sqrt(32)	5	sqrt(5)	sqrt(2)	0

由上边的表格可以看出距离最远的两个点为p0和p5

3.将p0分配到类簇c1，将p5分配到类簇c2；

4.查表可以看出，剩余的点中p1和p2与p0的距离小，所以将它们两个归到类簇c1中；p3和p4与p5的距离小，所以将它们两个归到类簇c2中。这样我们得到了一次新的聚类结果c1=（p1,p2,p3）,c2=(p3,p4,p5);

util: 若是我要求就聚类成两个，则这个聚类到此结束，最终我们的聚类结果是（p1,p2,p3）和(p3,p4,p5)。若是我要求同一个类中，最大样本距离不大于sqrt(2),那么上述的分类结果没有到达要求，则需要返回到repeat处继续聚类，因为c1中的样本的距离都不大于sqrt（2），所以不需要再分了；而类簇c2中的dis(p3,p5)=sqrt(5)>sqrt(2),还需要继续分，c2最后分聚类成两个类（p3,p4）和(p5),这样我们最终得到了三个类簇（p1,p2,p3）、(p3,p4)和（P5）。

简单的介绍完分裂法以后，我们开始我们的重头戏，凝聚层次聚类的介绍。

凝聚法：

凝聚法指的是初始时将每个样本点当做一个类簇，所以原始类簇的大小等于样本点的个数，然后依据某种准则合并这些初始的类簇，直到达到某种条件或者达到设定的分类数目。用算法描述：

输入：样本集合D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）

1.将样本集中的所有的样本点都当做一个独立的类簇；

repeat：

util：达到聚类的数目或者达到设定的条件

还是拿分裂法的例子来说具体的讲解凝聚法。

1.首先经所有的样本看作是一个类簇，这样我可以得到初始的类簇有6个，分别为c1(p0),c2(p1),c3(p2),c4(p3),c5(p4),c6(p5)

repeat：

2.由上边的表可以得到两两类簇间的最小距离（并不是唯一，其他两个类簇间距离也可能等于最小值，但是先选取一个）是1，存在类簇c1和c2之间

注意：这个类簇间距离的计算方法有许多种。

(1).就是取两个类中距离最近的两个样本的距离作为这两个集合的距离，也就是说，最近两个样本之间的距离越小，这两个类之间的相似度就越大

(2).取两个集合中距离最远的两个点的距离作为两个集合的距离

(3).把两个集合中的点两两的距离全部放在一起求一个平均值，相对也能得到合适一点的结果。

(4).取两两距离的中值，与取均值相比更加能够解除个别偏离样本对结果的干扰。

(5).把两个集合中的点两两的距离全部放在一起求和然后除以两个集合中的元素个数

(6).求每个集合的中心点(就是将集合中的所有元素的对应维度相加然后再除以元素个数得到的一个向量)，然后用中心点代替集合再去就集合间的距离

前四种，在点击打开链接中有介绍，后边的两种在工业界也经常使用，当然，还会有其他的一些方法。

3.合并类簇c1和c2,得到新的聚类结果c1(p0，p1),c3(p2),c4(p3),c5(p4),c6(p5)。

util：若是我们要求聚成5个类别的话，我们这里就可以结束了。但是如果我们设定了一个阈值f，要求若存在距离小于阈值f的两个类簇时则将两个类簇合并并且继续迭代，我们又会回到repeat继续迭代从而得到新的聚类结果。

好了，多了不说了，开始上代码，代码中我都写好了注释

Cluster.java(用于存放类名和该类下的样本)

import java.util.ArrayList; import java.util.List; public class Cluster { private List 
  
    dataPoints = new ArrayList 
   
     (); // 类簇中的样本点 private String clusterName; public List 
    
      getDataPoints() { return dataPoints; } public void setDataPoints(List 
     
       dataPoints) { this.dataPoints = dataPoints; } public String getClusterName() { return clusterName; } public void setClusterName(String clusterName) { this.clusterName = clusterName; } }

DataPoint.java(存放样本点，包括样本点的名字、所属的类簇、向量空间的表示)

public class DataPoint { String dataPointName; // 样本点名 Cluster cluster; // 样本点所属类簇 private double dimensioin[]; // 样本点的维度 public DataPoint(){ } public DataPoint(double[] dimensioin,String dataPointName){ this.dataPointName=dataPointName; this.dimensioin=dimensioin; } public double[] getDimensioin() { return dimensioin; } public void setDimensioin(double[] dimensioin) { this.dimensioin = dimensioin; } public Cluster getCluster() { return cluster; } public void setCluster(Cluster cluster) { this.cluster = cluster; } public String getDataPointName() { return dataPointName; } public void setDataPointName(String dataPointName) { this.dataPointName = dataPointName; } }

HCluster.java(主函数，包括数据的读取整理，聚类的执行等等。。。)

/ * 我写这个程序的目的是对我的次有进行聚类 */ import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import Cluster; import DataPoint; public class HCluster { public static void main(String[] args) { HCluster hc = new HCluster(); // 使用链表存放样本点 ArrayList 
      
        dp = new ArrayList 
       
         (); // 读入样本文件 dp = hc.readData("E:/test_cc/vec.txt"); /* * freq代表了聚类的终止条件，判断还有没有距离小于freq的两个类簇，若有则合并后继续迭代，否则终止迭代 */ double freq = 0.5; List 
        
          clusters = hc.startCluster(dp, freq); // 输出聚类的结果，两个类簇中间使用----隔开 System.out.println(); System.out.println("结果输出---："); for (Cluster cl : clusters) { List 
         
           tempDps = cl.getDataPoints(); for (DataPoint tempdp : tempDps) { System.out.println(tempdp.getDataPointName()); } System.out.println("----"); } } // 聚类的主方法 private List 
          
            startCluster(ArrayList 
           
             dp, double freq) { // 声明cluster类，存放类名和类簇中含有的样本 List 
            
              finalClusters = new ArrayList 
             
               (); // 初始化类簇，开始时认为每一个样本都是一个类簇并将初始化类簇赋值给最终类簇 List 
              
                originalClusters = initialCluster(dp); finalClusters = originalClusters; // flag为判断标志 boolean flag = true; int it = 1; while (flag) { System.out.println("第" + it + "次迭代"); // 临时表量，存放类簇间余弦相似度的最大值 double max = -1; // mergeIndexA和mergeIndexB表示每一次迭代聚类最小的两个类簇，也就是每一次迭代要合并的两个类簇 int mergeIndexA = 0; int mergeIndexB = 0; /* * 迭代开始，分别去计算每个类簇之间的距离，将距离小的类簇合并 */ for (int i = 0; i < finalClusters.size() - 1; i++) { for (int j = i + 1; j < finalClusters.size(); j++) { // 得到任意的两个类簇 Cluster clusterA = finalClusters.get(i); Cluster clusterB = finalClusters.get(j); // 得到这两个类簇中的样本 List 
               
                 dataPointsA = clusterA.getDataPoints(); List 
                
                  dataPointsB = clusterB.getDataPoints(); /* * 定义临时变量tempDis存储两个类簇的大小，这里采用的计算两个类簇的距离的方法是 * 得到两个类簇中所有的样本的距离的和除以两个类簇中的样本数量的积，其中两个样本 之间的距离用的是余弦相似度。 * 注意：这个地方的类簇之间的距离可以 换成其他的计算方法 */ double tempDis = 0; /* * 此处计算距离可以优化，事先一次性将两两样本点之间的余弦距离计算好存放一个MAP中， * 这个地方使用的时候直接取出来，就不用每次再去计算了，可节省很多时间。 * 注意：若是类簇间的距离计算换成了别的方法，也就没有这种优化的说法了 */ for (int m = 0; m < dataPointsA.size(); m++) { for (int n = 0; n < dataPointsB.size(); n++) { tempDis = tempDis + getDistance(dataPointsA.get(m), dataPointsB.get(n)); } } tempDis = tempDis / (dataPointsA.size() * dataPointsB.size()); if (tempDis >= max) { max = tempDis; mergeIndexA = i; mergeIndexB = j; } } } /* * 若是余弦相似度的最大值都小于给定的阈值， 那说明当前的类簇没有再进一步合并的必要了， * 当前的聚类可以作为结果了，否则的话合并余弦相似度值最大的两个类簇，继续进行迭代 注意：这个地方你可以设定别的聚类迭代的结束条件 */ if (max < freq) { flag = false; } else { finalClusters = mergeCluster(finalClusters, mergeIndexA, mergeIndexB); } it++; } return finalClusters; } private List 
                 
                   mergeCluster(List 
                  
                    finalClusters, int mergeIndexA, int mergeIndexB) { if (mergeIndexA != mergeIndexB) { // 将cluster[mergeIndexB]中的DataPoint加入到 cluster[mergeIndexA] Cluster clusterA = finalClusters.get(mergeIndexA); Cluster clusterB = finalClusters.get(mergeIndexB); List 
                   
                     dpA = clusterA.getDataPoints(); List 
                    
                      dpB = clusterB.getDataPoints(); for (DataPoint dp : dpB) { DataPoint tempDp = new DataPoint(); tempDp.setDataPointName(dp.getDataPointName()); tempDp.setDimensioin(dp.getDimensioin()); tempDp.setCluster(clusterA); dpA.add(tempDp); } clusterA.setDataPoints(dpA); finalClusters.remove(mergeIndexB); } return finalClusters; } private double getDistance(DataPoint dataPoint, DataPoint dataPoint2) { double distance = 0; double[] dimA = dataPoint.getDimensioin(); double[] dimB = dataPoint2.getDimensioin(); if (dimA.length == dimB.length) { double mdimA = 0;// dimA的莫 double mdimB = 0;// dimB的莫 double proAB = 0;// dimA和dimB的向量积 for (int i = 0; i < dimA.length; i++) { proAB = proAB + dimA[i] * dimB[i]; mdimA = mdimA + dimA[i] * dimA[i]; mdimB = mdimB + dimB[i] * dimB[i]; } distance = proAB / (Math.sqrt(mdimA) * Math.sqrt(mdimB)); } return distance; } // 初始化类簇 private List 
                     
                       initialCluster(ArrayList 
                      
                        dpoints) { // 声明存放初始化类簇的链表 List 
                       
                         originalClusters = new ArrayList 
                        
                          (); for (int i = 0; i < dpoints.size(); i++) { // 得到每一个样本点 DataPoint tempDataPoint = dpoints.get(i); // 声明一个临时的用于存放样本点的链表 List 
                         
                           tempDataPoints = new ArrayList 
                          
                            (); // 链表中加入刚才得到的样本点 tempDataPoints.add(tempDataPoint); // 声明一个类簇，并且将给类簇设定名字、增加样本点 Cluster tempCluster = new Cluster(); tempCluster.setClusterName("Cluster " + String.valueOf(i)); tempCluster.setDataPoints(tempDataPoints); // 将样本点的类簇设置为tempCluster tempDataPoint.setCluster(tempCluster); // 将新的类簇加入到初始化类簇链表中 originalClusters.add(tempCluster); } return originalClusters; } private ArrayList 
                           
                             readData(String path) { ArrayList 
                            
                              dp = new ArrayList 
                             
                               (); File file = new File(path); if (!file.exists()) { System.out.println("输入文件不存在"); System.exit(1); } FileInputStream fis = null; InputStreamReader isr = null; BufferedReader br = null; try { fis = new FileInputStream(file); isr = new InputStreamReader(fis, "utf-8"); br = new BufferedReader(isr); String line = br.readLine(); String s[] = null; while (line != null) { /* * 说明一下我的数据格式为 word v1 v2 ....v200,word代表要聚类的词语， * v1-v200是word的词向量表示的每一个维度值，我实验的样本的维度为200， * 所有下边我声明了一个200的double数组 */ s = line.split(" "); double[] b = new double[200]; for (int i = 1; i < s.length; i++) { b[i - 1] = Double.parseDouble(s[i]); } dp.add(new DataPoint(b, s[0])); line = br.readLine(); } } catch (Exception ex) { ex.printStackTrace(); } finally { try { br.close(); isr.close(); fis.close(); } catch (IOException e) { e.printStackTrace(); } } System.out.println("加载数据完毕，数据大小为：" + dp.size()); return dp; } }