层次聚类
层次聚类分支
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个点进行聚类，对应着上边的步骤我可以这样做：
-
将所有的点归为一个类簇c（p0,p1,p2,p3,p4,p5）
-
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); -
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）将两个簇中两两点间的距离求和除以除以两个簇的样本总数
