层次聚类

层次聚类分支

1）分裂法
从上到下对大类别进行分割
2）凝聚法
从下到上对小类别进行聚合

层次聚类优点

kmeans中需要人工确定聚类类别K基于初始化聚类中心，这将会很大程度上影响聚类效果。
而层次聚类避免了这一问题。

分裂法

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

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

输出：聚类结果

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

    repeat：

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

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

    4.计算原类簇（c）中剩余的其他样本点和a，b的距离，若是dis(a)<dis(b)，则将样本点归到c1中，否则归到c2中；

    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）

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

   
   
   

   2）确定最远的两个点：
   首轮计算得到距离最远的两个点为 p0 和 p5，
   3）确定簇：
   将 p0 分配到类簇 c1，将 p5 分配到类簇c2；
   4）为每个簇分配点：
   查表可以看出，剩余的点中p1和p2与p0的距离小，所以将它们两个归到类簇c1中；p3和p4与p5的距离小，所以将它们两个归到类簇c2中。这样我们得到了一次新的聚类 结果c1=（p1,p2,p3）,c2=(p3,p4,p5);

3. Util：
   若仅要求聚类为两个类别，则聚类结束。
   若要求一个簇中最大样本间距离不超过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，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）

 输出：聚类结果

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

       repeat：

            1）.计算两两类簇之间的距离，找到距离最小的两个类簇c1和c2；

            2）.合并类簇c1和c2为一个类簇；

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

上述算法流程中，对于计算两两簇之间的距离有较多的方法：
1）取两个簇中最近的两个样本点作为簇间距离
2）取两个簇中最远的两个样本点作为簇间距离
3）将两个簇中两两点间的距离均值作为簇间距离
4）将两个簇中两两点间的距离的中位数作为簇间距离
5）将两个簇中两两点间的距离求和除以除以两个簇的样本总数

转载注明：https://www.jianshu.com/p/cabab63f7a00