层次聚类(Hierarchical Clustering)是聚类算法的一种，同时也是一种无监督的学习（即拿到的数据没有任何分类，不需要被告知要划分的类是哪些，从而完成分组），通过计算不同类别间的相似度来创建一棵有层次的嵌套聚类树。
在聚类数中，不同类别的原始数据是树的最低层，树的顶层是一个聚类的根节点。
创建聚类树有自下而上合并和自上而下分裂两种方法，分别为凝聚式聚类与分裂式聚类。
一.层次聚类与K_means的优缺点
1.K_means
优点
（1）算法快速、简单
（2）对大数据集有较高的效率
（3）适合处理大规模数据集，时间复杂度接近线性
（4）当结果簇是密集的，簇与簇区别明显时，效果较好
缺点
（1）K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的
（2）对离群点敏感
2.层次聚类
优点
（1）不需要预先定义所需要类的数目
（2）距离和相识度容易定义，限制少
（3）可以发现类的层次关系
缺点
（1）计算复杂度太高
（2）可能聚类成链状
二.分裂式聚类
1.原理
初始时将所有的样本归为一个类，然后依据某种准则进行逐渐的分裂，直到达到某种条件或者达到设定的分类数目。
2.类层次结构
自顶向下生成
3.分裂式聚类步骤
（1）将样本集中的所有的样本归为一个类；
（2）在同一个类（计为c）中计算两两样本之间的距离，找出距离最远的两个样本a , b；
（3）将样本a , b分配到不同的类c1和c2中；
（4）计算原类（c）中剩余的其他样本点和a，b的距离，若是dis(a) < dis(b)，则将样本点归到c1中，否则归到c2中；
Util： 达到聚类的数目或者达到设定的条件
4.示例
在平面上有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）在类c中计算他们的距离（欧式距离）我们可以得到：
（3）将p0分配到类c1，将p5分配到类c2；
（4）得到新的聚类c1=（p1,p2,p3）,c2=(p3,p4,p5);
Util.满足聚类要求
5.截止条件
假如要求最大样本距离不大于sqrt(2),那么上述的分类结果没有到达要求，则需要返回到（2）处继续聚类，因为c1中的样本的距离都不大于sqrt（2），所以不需要再分了；而类c2中的dis(p3,p5)=sqrt(5)>sqrt(2),还需要继续分(即到最后各自类的最远距离都小于规定的值sqrt(2)就截止聚类)，c2最后分聚类成两个类（p3,p4）和(p5),这样我们最终得到了三个类（p1,p2,p3）、(p3,p4)和（P5）。
如果要求达到聚类的数目为3，基于之前的每个聚类进行（2）步骤，计算各个聚类两两样本之间的距离，找出距离最远的两个样本的聚类进行分裂，从而达到聚类的数目。
