层次聚类

层次聚类是一种基于树形结构的聚类方法，常用的是自底向上的结合策略（AGNES算法）。假设有N个待聚类的样本，其基本步骤是：

1. 初始化—>把每个样本归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度；
2. 寻找各个类之间最近的两个类，把他们归为一类（这样类的总数就少了一个）；
3. 重新计算新生成的这个类与各个旧类之间的相似度；
4. 重复2和3直到所有样本点都归为一类，结束。

可以看出其中最关键的一步就是计算两个类簇的相似度，这里有多种度量方法：

• 单链接（single-linkage）: 取类间最小距离。
  最小距离：%20%3D%20%5Cunderset%7Bx%5Cin%20Ci%2Cz%20%5Cin%20C_j%7D%7Bmin%7Ddist(x%2Cz)#card=math&code=d%7Bmin%7D%28C_i%2CC_j%29%20%3D%20%5Cunderset%7Bx%5Cin%20C_i%2Cz%20%5Cin%20C_j%7D%7Bmin%7Ddist%28x%2Cz%29&id=edUD4)
• 全链接（complete-linkage）:取类间最大距离
  最大距离：%20%3D%20%5Cunderset%7Bx%5Cin%20Ci%2Cz%20%5Cin%20C_j%7D%7Bmax%7Ddist(x%2Cz)#card=math&code=d%7Bmax%7D%28C_i%2CC_j%29%20%3D%20%5Cunderset%7Bx%5Cin%20C_i%2Cz%20%5Cin%20C_j%7D%7Bmax%7Ddist%28x%2Cz%29&id=VqqCs)
• 均链接（average-linkage）:取类间两两的平均距离
  平均距离：

很容易看出：单链接的包容性极强，全链接则是坚持到底，只要存在缺点就坚决不合并，均连接则是从全局出发顾全大局。层次聚类法的算法流程如下所示：