层次聚类

层次聚类（Hierarchical Clustering）是一种不需要预先指定簇数量的聚类方法，通过构建一个层次嵌套的聚类树（树状图，dendrogram）来揭示数据在不同粒度上的结构。

聚类方向

层次聚类主要有两种方向：

从每个样本作为一个单独的簇开始，逐步合并最相似的簇，直到所有样本合并为一个簇或达到终止条件。这是最常用的层次聚类方法。

从所有样本作为一个簇开始，逐步将一个簇分裂为两个子簇，直到每个样本成为一个单独的簇。

在进行簇合并或分裂时，需要定义如何计算两个簇之间的距离。常用的方法包括：

计算两个簇中最近样本的距离，对非球形簇效果好，但易受噪声影响。

计算两个簇中最远样本的距离，对噪声较鲁棒，但偏好球形簇。

计算两个簇中所有样本对之间的平均距离，是单链接和全链接的折中方案。

合并时使簇内离差平方和的增量最小，倾向于生成大小相近的簇。

对于簇 $C_{i}$ 和 $C_{j}$ ，各种链接方法的距离定义如下：

单链接： $d (C_{i}, C_{j}) = min_{x \in C_{i}, y \in C_{j}} d (x, y)$
全链接： $d (C_{i}, C_{j}) = max_{x \in C_{i}, y \in C_{j}} d (x, y)$
平均链接： $d (C_{i}, C_{j}) = \frac{1}{∣ C _{i} ∣∣ C _{j} ∣} \sum_{x \in C_{i}} \sum_{y \in C_{j}} d (x, y)$