> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/ji-qi-xue-xi/ju-lei-suan-fa/based-on-hierarchy/ji-chu-de-ceng-ci-ju-lei-suan-fa.md).

# 基础的层次聚类算法

## 引入

层次聚类算法分为两种:

* **凝聚方法, agglomerative**, 即自下而上法(bottom-up)
  * 从点作为个体簇开始, 每一步合并两个**最近距离的簇**. 需要定义**簇的邻近性**概念
* **分裂算法, divisive**, 即自上而下法(top-down)
  * 从一个簇包含所有点开始, 每一步分裂一个簇, 直到只剩下单点簇. 在每一步, 需要确定分裂那个簇, 以及如何分裂

两种方法本质上没有优劣之分, 只是在实际应用的时候要根据数据特点以及想要的类的数量, 来考虑是自上而下更快还是自下而上更快, 然后进行选择.

因此以下只关注**凝聚方法**的层次聚类. 使用凝聚方法, 首先需要计算两个簇之间的邻近度.

## 簇的邻近度

**MIN/单链(single link)**

MIN/单链将簇的邻近度定义为两个簇的最近点之间的邻近度, 以点的邻近度, 作为簇的邻近度. 关于点的邻近度的定义可以参考两点之间的相似性度量方法.

单链擅长:

* 处理**非凸集**/**非椭圆**形状的簇

但缺点也很显著:

* 对**噪声**和**离群点**很敏感

**MAX/全链(complete link)**

MAX/全链去两个簇中两个最远的点之间的邻近度作为簇的邻近度.

全链擅长:

* 对**噪声**和**离群点**不敏感

但也有以下的缺点:

* 偏好形成球形, 对非凸集样本集不友好
* 可能使得很大的簇破裂

**组平均(group average)**

对两个簇中的所有点之间组成**点对**, 对所有点对的邻近度(距离)取平均值, 因此需要遍历所有点.

**Ward**

Ward将两个簇的邻近度定义为**两个簇合并时导致的平方误差的增量**. 即首先分别计算两个簇的平方误差, 然后再假设这两个簇聚合在一起, 计算聚合后的新簇的平方误差. 再将合并后平方误差减去合并前的, 就得到了合并后的平方误差的增量. 这个值肯定的大于0的, 在聚类算法中, 应选择平方误差增加最小的两个簇进行合并.

至于**平方误差**, 公式为:

$$\sum\limits\_{i=1}^{n}x\_i^2-\frac{1}{n}(\sum\limits\_{i=1}^{n}x\_i)^2$$

本质相当于方差$$\times n$$. 当然Ward属于一种思想, 任何可以衡量簇内部离散程度的指标都可以使用.

在使用平方误差的Ward方法时, 层次聚类算法可以从数学上证明, 与K-Means算法十分相似. 因此具有K-Means聚类算法的性质.

**质心方法**

计算每个簇的质心, 使用质心点之间的邻近度作为两个簇之间的邻近度.

质心方法有个独特的缺点: 本次迭代合并的两个簇, 可能比上一次迭代合并的两个簇更为相似, 从而出现**倒置**的可能性. 使用其他簇的邻近度评价方法不会出现这个现象, 簇之间的距离随着层次聚类的进行而单调增加.

**Lance-Williams公式**

上面的所有计算簇的邻近度的方法, 都能够用Lance-Williams公式的形式表示, 不同方法之间, 只是公式中参数值设定的不同.

Lance-Williams公式是一种衡量簇之间邻近度的通用且重要的公式.

确定好要使用的簇的邻近度之后, 开始对簇进行合并, 这一步被称为**linkage**. 如使用ward方法的这个过程就被称为ward linkage method.

linkage过程中会记录每次合并的两个簇的序号, 并给定这个新生成的簇一个新的独特序号(序号递增), 然后会记录这两个被合并簇之间的邻近度.

**scipy.cluster.hirarchy.linkage**函数中可以选择上述的任意一种方法, 进行linkage, 记录并返回整个合并过程. 使用返回的**linkage matrix**可以画**树状图**(dendrogram)进行可视化, 而包装好的聚类方法中, 也使用到了这个函数, 对函数的返回结果进行解析和组装, 返回聚类结果.

## 使用方法

对于层次聚类, 在**sklearn**和**scipy**中都有对应的模型类或函数进行实践.

`sklearn`中有一个专门做凝聚方式的聚类的类: [AgglomerativeClustering](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html#sklearn.cluster.AgglomerativeClustering), 具体的使用方法可以参考对应的文档. 需要注意的是层次聚类因为是从完全单点的簇聚合成一个簇, 所以需要指定簇的数量, 才能返回对应的结果. 重要的参数如下:

* **n\_clusters**: int, default=2
  * 要发现的簇的数量
* **affinity**: string or callable, default: “euclidean”
  * 计算点之间的相似度的方法, 可以快捷的使用字符串指定, 接受“euclidean”, “l1”, “l2”, “manhattan”, “cosine”, or “precomputed”, 对于`ward`方法, 只接受`euclidean`
* **linkage**: {“ward”, “complete”, “average”, “single”}, optional (default=”ward”)
  * 簇之间合并的方法, 如上面介绍

`scipy`中, 可以使用[scipy.cluster.hierarchy.fclusterdata](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.fclusterdata.html#scipy.cluster.hierarchy.fclusterdata)函数进行聚类. 具体的使用方法可以参考对应的文档. 原理可参考[Hierarchical clustering (scipy.cluster.hierarchy)](https://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html).

## 层次聚类特性

**优点**:

* 层次聚类的算法往往能够得到**高质量**的聚类
* 不同的linkage方法的选择, 可以适用于多种数据集情况

**缺点**:

* **计算量**以及**存储量**十分复杂, 层次聚类算法是很昂贵的
* 对于**高维数据**或**噪声**的存在也可能产生问题

一种解决方案是, 在使用层次聚类之前, 使用如K-Means之类的其他聚类算法进行初步聚类(即使用其他算法聚出来很多类, 其他算法在使用时指定较多的簇数量), 然后再使用层次聚类算法, 即层次聚类算法的起点是从小簇开始的, 不再是从单个点开始. 使用这种方法, 上面的两个缺点, 在一定程度上都能得到解决(速度等).