机器学习之聚类(层次聚类)

    层次聚类(Hierarchical Clustering)是聚类算法的一种，通过对给定的数据集进行层次的分解，直到某种条件满足为止，最终构建出一颗嵌套的树。

    说白了，层次聚类就是一层一层的进行聚类。可以采用自顶向下的聚类策略，也可以采用自下而上的策略。

凝聚聚类

    凝聚聚类采用自下而上的策略，初始时将每个样本都当做一簇，最开始样本的个数实际上等于簇的个数，依据某种准则合并簇，直到满足某种条件则停止聚类。

1. 算法描述
   (1) 计算两两簇之间的距离（簇间距计算方法在后面），找到距离最小的两个类簇cluster1和cluster2;
   (2)合并类簇cluster1和cluster2
   (3)重复上面两步，直到达到聚类的数目或者是满足某种条件停止。
2. 簇间距如何计算
   (1)SingleLinkage
   又叫做nearest-neughbor，就是取两个类中距离最近的两个样本作为两个类簇的距离。但是容易形成链状结构。
   (2)CompleteLinkage
   和SingleLinkage完全不同，取两个类中距离最远的两个样本作为两个类簇的距离。对异常点比较敏感。
   (3)Average-linkage
   取两个类中两两样本的距离的平均值作为类簇间距离。

分裂聚类

    凝聚聚类采用自顶向下的策略，首先将所有样本都当做一簇，然后依据某种准则分裂，将大簇编变成小簇，直到满足某种条件则停止分裂，在实际中，用凝聚聚类用的多。

1. 算法描述
   (1)在同一簇(cluster)里面计算两类样本之间的距离，找出距离最远的两个样本a,b;
   (2)将两个样本a,b分配到不同的类簇(cluster1和cluster2)中;
   (3)计算其余样本到两个类簇的距离，如果其余样本距离a近，则该样本归类于cluster1中，否则，归类于cluster2中;
   (4)重复第3步，直到满足特定的条件则停止分列。

   参考

   类簇间距离度量
   层次聚类介绍