【模型】一篇入门之-层次聚类算法(HC)

层次聚类法(Hierarchical clustering)是最基础的聚类算法之一，学习聚类算法最好从它开始学起，因为它最有"聚类"的感觉，那么今天我们就一起来看看层次聚类法是个什么样的聚类算法，包括层次聚类的思想原理、算法流程、聚类效果、以及具体的代码实现方法和例子，等等。

一、层次聚类算法-原理与算法流程

聚类算法就是将整体样本聚为几类，属于一种无监督学习(也就是不需要y)，而层次聚类算法就是最基本的聚类算法之一，而层次聚类算法呢，又分为凝聚法和分裂法，较常用的凝聚法，很少用分裂法，所以我们不妨先看凝聚法，后面再顺带了解一下分裂法就好了。

1.1. 层次聚类-凝聚法

层次聚类算法(凝聚法Agglomerative)算法的核心思路就是，不断地把两个最近的聚在一起。

所以，层次聚类算法实际很简单，直接看下它的聚类流程，就知道它是怎么一回事了。

1.2. 层次聚类-凝聚法-算法流程

层次聚类(凝聚法)算法流程如下：

      1. 初始化：将每个样本都当作一类，也就是说，有多少个样本就有多少个类别。

      2. 计算类别两两之间的距离

      3. 将距离最近的两个类别合并为一类

      重复2，3，直到只剩1个类别(或k个类别)

总的来说，凝聚法就是不断地把最近的两类变为一类，就是这么简单。

1.3. 层次聚类-凝聚法-凝聚图

层次聚类(凝聚法)一般用下面这样的图来展示整个聚类过程：

凝聚法是一种自下而上的算法，这个图要从最底部开始往上看。

从图中最底部可以看到，一共有9个样本，最开始时，它们各自代表着一个类别，然后从底部往上，看最矮的合并线，可以看到，刚开始是将0、4合并为一类，类似地，继续按合并线高度往上看，可以看到接下来是将6、8合并、之后是1、2合并......如此逐层向上，直到最后所有的样本都合并为一类。

1.4. 层次聚类-分裂法

好了，搞清楚凝聚法就很容易理解分裂法了，分裂法与凝聚法是差不多的，只不过分裂法是一种自上而下的算法，我们下面直接看一下分裂法的算法流程，基本也就知道分裂法是怎么一回事了。

层次聚类算法(分裂法)的算法流程如下：

一、初始化

    将所有样本作为一个类别

二、分裂

    对每个样本>2的类别进行下述分裂，直到每个类别只有一个样本。

    每个类别分裂的流程如下：

    1. 计算样本两两之间的距离

    2. 将距离最远的两个样本作为两个类别中心

    3. 将其余样本划分到离它最近的类别中心

    4. 以两个类别上的样本均值作为两个类别的位置

这就是层次聚类算法的分裂法了，在实际中很少使用，一般都是用凝聚法，所以分裂法简单了解一下就好了。

二、层次聚类-距离计算

从上面层次聚类的流程中可以知道，层次聚类算法需要计算类别两两之间的距离。我们首先想到的肯定是欧氏距离 ，但实际中，有更多不同的距离计算方法，如下：

1. single：最近邻算法，NPA(Nearest Point Algorithm) 

2. complete：最远邻算法，FPA(Farthest Point Algorithm) 

3. average：等权均值法，UPGMA(Unweighted Pair-Group Methodusing the Average approach)

4. centroid：等权质心法，UPGMC(Unweighted Paire-Group Method using Centroid approach)

5. median： WPGMC，加权质心法(Weighted Pair-Group Method using Centroid approach)

6. weighted： 加权均值法(Weighted Pair Group Method with Arithmetic mean)      

7. ward ：ward方差法

上面说了各种类别距离的计算方法，但在一般情况下，层次聚类法都是使用ward方法，一般软件中实现的默认算法也是ward算法，其它的使用得相对较少，如果ward效果不好，也可以考虑single、complete、average等方法。

三、层次聚类算法-代码实现

在python中虽然用sklearn也能实现层次聚类算法，但它底层调用的其实是scipy的hierarchy.linkage函数，所以这里我们就直接使用scipy来实现层次聚类算法好了，下面是一个具体的实现例子，代码如下：

'''
本代码展示如何用SVD对图片进行降维
本代码来自《老饼讲解-机器学习》 www.bbblearn.com
'''
import matplotlib.pyplot as plt
from scipy.cluster import hierarchy
import numpy as np

X = np.array([[1 ,2],[3 ,4],[5 ,6],[1 ,8],[2 ,2]])           # 生成数据X
Z = hierarchy.linkage(X,method='ward', metric='euclidean')   # 使用层次聚类进行聚类
print('\n聚类过程Z:\n',Z)                                    # 打印聚类结果 
plt.figure(figsize=(8, 6))                                   # 初始化画布
hierarchy.dendrogram(Z)                                      # 绘制聚类过程
plt.show()                                                   # 展示聚类结果

代码运行结果如下：

其中，Z记录了合并过程，各列为：类别1，类别2，距离，合并后的样本数。以Z的第一行为例，它的意思是：类别0与类别4的距离为1，合并后样本个数为2。

总结

层次聚类分为凝聚法和分裂法，其中较常用的是凝聚法，它就是不断地将最近的两个类别进行合并，直到只剩一个类别，层次聚类算法中，类别的距离计算，一般都使用ward方法，在python中使用scipy的hierarchy.linkage函数来实现它就可以了。