ML：层次聚类的基本原理与实现

在机器学习中，聚类（Clustering）是一类典型的无监督学习任务。它不依赖预先给定的类别标签，而是根据样本之间的相似性或距离，把数据自动划分为若干组。

K 均值聚类通常需要事先指定簇数 k，并通过更新簇中心得到最终划分。层次聚类采用另一种思路：它通过逐步合并或拆分样本，构建从局部到整体的层级结构。

层次聚类关注的不只是“最终分成几类”，还包括：

• 哪些样本最先合并

• 小簇如何逐步合并成大簇

• 不同簇之间的相似程度如何

• 在不同层级截断时会得到怎样的聚类结果

因此，层次聚类不仅是一种聚类算法，也是一种观察数据结构的方法，尤其适合样本量不太大、希望理解样本层级关系的探索性分析任务。

一、层次聚类的基本思想

层次聚类（Hierarchical Clustering）的核心思想是：根据样本之间的相似性，逐步构建树状聚类结构。

这种结构可以从两个方向生成：

• 凝聚式聚类：自底向上，先把每个样本看作一个簇，再逐步合并相近的簇。

• 分裂式聚类：自顶向下，先把所有样本看作一个整体，再逐步拆分成更小的簇。

在实际应用中，更常见的是凝聚式层次聚类（Agglomerative Hierarchical Clustering）。Scikit-learn 中的 AgglomerativeClustering 采用的就是这种自底向上的合并思路。

凝聚式层次聚类可以概括为：

• 输入：一组没有标签的样本

• 过程：根据距离和链接准则逐步合并样本或簇

• 输出：最终聚类标签，或一棵表示合并关系的树

• 目标：让相似样本更早合并，不相似样本更晚合并

图 1：凝聚式层次聚类的基本过程

与 K 均值聚类相比，层次聚类不只是给出某个 k 下的划分结果，还能展示样本从细粒度到粗粒度的组织关系。例如，同一批样本可以在较低层级分成多个小簇，也可以在较高层级合并为少数大簇。

二、凝聚式聚类与分裂式聚类

图 2：凝聚式聚类与分裂式聚类

1、凝聚式层次聚类

凝聚式层次聚类（Agglomerative Clustering）采用自底向上的策略：

• 初始时，每个样本都是一个独立簇

• 每一步找到最相近的两个簇

• 将这两个簇合并为一个新簇

• 重复合并，直到达到指定簇数或距离阈值

如果有 n 个样本，初始时有 n 个簇。每合并一次，簇的数量减少 1。完整执行后，可以得到从 n 个单样本簇到 1 个总簇的合并过程。

凝聚式聚类直观、稳定，适合构建层次结构；但它需要计算和更新大量簇间距离，样本量很大时计算成本较高。

2、分裂式层次聚类

分裂式层次聚类（Divisive Clustering）采用相反的自顶向下策略：

• 初始时，所有样本属于同一个大簇

• 每一步选择一个簇进行拆分

• 逐步把大簇分解为更小的簇

• 直到达到停止条件

分裂式聚类在概念上也很自然，但实际计算中通常更复杂，因为每一步如何选择最佳拆分方式并不容易。因此，常见工具库中更常用的是凝聚式层次聚类。

本文后续主要讨论凝聚式层次聚类。

三、距离度量：如何判断样本是否相似

层次聚类要不断合并“最相近”的样本或簇，因此首先需要定义样本之间的距离。

在数值特征空间中，距离越小，通常表示样本越相似；距离越大，通常表示样本差异越明显。

图 3：三种距离度量对比

设两个样本为：

其中，n 表示特征数量。

1、欧氏距离

欧氏距离（Euclidean Distance）衡量两个点在几何空间中的直线距离：

其中：

• xᵢ 表示样本 x 的第 i 个特征值

• zᵢ 表示样本 z 的第 i 个特征值

• d(x,z) 表示两个样本之间的距离

欧氏距离适合连续数值特征，但对特征尺度敏感。如果某个特征的数值范围远大于其他特征，它可能主导距离计算。因此，使用基于距离的聚类方法前，通常需要考虑标准化或归一化。

2、曼哈顿距离

曼哈顿距离（Manhattan Distance）又称城市街区距离，它计算两个样本在各个维度上的绝对差之和：

曼哈顿距离在某些高维或稀疏特征场景中可能更稳健，例如文本向量或稀疏特征空间。

3、余弦距离

余弦相似度关注两个向量方向是否接近，而不是长度是否接近：

常见余弦距离可以写成：

余弦距离常用于文本向量、TF-IDF 特征、词袋特征等高维向量场景。不同距离度量可能显著改变层次聚类结果，尤其在高维数据中更明显。

四、链接准则：如何计算簇与簇之间的距离

样本之间的距离容易计算，但当多个样本合并成簇之后，还需要定义“簇与簇之间的距离”。这就是链接准则（Linkage Criterion）要解决的问题。

Scikit-learn 的 AgglomerativeClustering 支持 ward、single、average、complete 等链接准则。它们决定了算法每一步如何衡量两个簇之间的距离，以及应该合并哪两个簇。

图 4：四种链接准则对比

1、单链接：最近点距离

单链接（Single Linkage）使用两个簇中最近两个样本之间的距离作为簇间距离：

其中：

• A、B 表示两个簇

• x 表示簇 A 中的样本

• z 表示簇 B 中的样本

单链接容易发现链状结构或非球形结构，但也容易受到噪声和离群点影响。两个簇只要有一对样本很近，就可能被合并，这种现象通常称为链式效应。

2、全链接：最远点距离

全链接（Complete Linkage）使用两个簇中最远两个样本之间的距离作为簇间距离：

全链接更关注簇整体是否紧凑。只有当两个簇中最远样本之间的距离也不大时，它们才容易被合并。因此，全链接倾向于形成较紧凑的簇，但也可能对离群点较敏感。

3、平均链接：平均距离

平均链接（Average Linkage）使用两个簇中所有样本两两距离的平均值作为簇间距离：

其中：

• |A| 表示簇 A 中的样本数量

• |B| 表示簇 B 中的样本数量

平均链接在单链接和全链接之间取得折中。它既不只看最近点，也不只看最远点，而是考虑两个簇之间的整体距离。

4、Ward 链接：最小化簇内方差增加

Ward 链接不直接使用最近点、最远点或平均距离，而是选择合并后使簇内平方误差增加最小的两个簇。

它的目标可以理解为：

其中：

• SSE(A) 表示簇 A 内样本到簇中心的残差平方和

• SSE(B) 表示簇 B 内样本到簇中心的残差平方和

• SSE(A∪B) 表示合并后新簇的残差平方和

• Δ(A,B) 表示合并 A 与 B 带来的簇内平方误差增加量

Ward 方法每一步选择 Δ(A,B) 最小的两个簇合并。它通常倾向于得到较紧凑、较规则的簇。需要注意的是，在 Scikit-learn 中，linkage="ward" 只能配合欧氏距离相关度量使用。

五、树状图：层次结构的可视化

层次聚类的一个重要特点，是可以用树状图（Dendrogram）展示样本或簇的合并过程。

在树状图中：

• 底部通常表示单个样本

• 越早合并，表示越相似

• 合并高度越低，表示距离越近

• 合并高度越高，表示差异越大

图 5：层次聚类与树状图分析

层次聚类得到的是一棵合并树。如果需要得到具体聚类标签，可以在树的某个高度进行截断：

• 截得较低：得到更多、更细的簇

• 截得较高：得到更少、更粗的簇

• 指定簇数：保留指定数量的簇

• 指定距离阈值：超过某个距离后停止合并

图 6：不同截断高度对应不同聚类结果

在 Scikit-learn 中，可以通过 n_clusters 指定最终簇数，也可以通过 distance_threshold 指定距离阈值。若 distance_threshold 不为 None，则 n_clusters 必须设为 None。

树状图的主要价值不是提高预测能力，而是帮助观察数据结构，例如：

• 哪些样本最相似

• 哪些簇之间差异较大

• 是否存在自然分组层次

• 选择几个簇较为合理

需要注意的是，普通结构图只能表达合并关系，真正的 dendrogram 还需要表达每次合并的距离高度，通常可借助 SciPy 和 Matplotlib 绘制。

六、层次聚类的基本流程

以凝聚式层次聚类为例，其基本流程如下：

（1）把每个样本看作一个独立簇。

（2）计算所有簇之间的距离。

（3）找到距离最近的两个簇。

（4）根据链接准则将它们合并成新簇。

（5）更新新簇与其他簇之间的距离。

（6）重复合并，直到满足停止条件。

停止条件可以是：

• 达到指定簇数

• 合并距离超过指定阈值

• 所有样本合并成一个簇

• 根据树状图人工选择截断位置

例如，有 5 个样本 A、B、C、D、E。若 A 与 B 很近，C 与 D 很近，E 与其他样本都较远，凝聚式层次聚类可能先合并 A 和 B，再合并 C 和 D。若最终指定分成 3 类，可能得到：

• 簇 1：A、B

• 簇 2：C、D

• 簇 3：E

如果指定分成 2 类，则会继续在已有簇之间进行合并，得到更粗粒度的结果。

这说明，层次聚类不仅给出一个最终划分，还保留了样本从近到远逐步组织起来的过程。

七、Scikit-learn 中的 AgglomerativeClustering

在 Scikit-learn 中，层次聚类主要通过 AgglomerativeClustering 实现。它的基本特点是：

• 属于无监督聚类算法

• 采用自底向上的凝聚式合并

• 支持指定最终簇数

• 支持不同链接准则

• 支持不同距离度量

• 可以配合距离阈值构建层次结构

常用参数包括：

• n_clusters：指定最终聚类数量

• metric：指定样本之间的距离度量

• linkage：指定簇间距离的链接准则

• distance_threshold：指定停止合并的距离阈值

• compute_distances：是否计算合并距离，常用于绘制树状图

• connectivity：指定样本之间的连接约束，可用于加入局部邻域结构

其中，linkage 常见取值包括：

• "ward"：最小化簇内方差增加

• "complete"：使用簇间最远点距离

• "average"：使用簇间平均距离

• "single"：使用簇间最近点距离

如果 linkage="ward"，通常使用 metric="euclidean"；如果要使用 "manhattan"、"cosine" 等非欧氏距离，通常应选择 "average"、"complete" 或 "single"。

参数选择可以从以下思路出发：

• 连续数值特征、希望得到较紧凑簇：可先尝试 linkage="ward"

• 希望使用曼哈顿距离或余弦距离：可考虑 average 或 complete

• 数据可能存在链状结构：可尝试 single，但需注意噪声影响

• 样本量较小、希望观察层次结构：可结合树状图分析

• 只需要最终聚类标签：可直接设置 n_clusters

由于层次聚类依赖距离，数值特征量纲差异较大时，通常应先进行标准化。

八、Python 实现：二维数据聚类示例

下面使用合成二维数据演示层次聚类的基本流程。

这段代码体现了层次聚类的基本工作流：

• 生成或加载数据

• 对数值特征进行标准化

• 创建 AgglomerativeClustering

• 使用 fit_predict() 得到簇标签

• 使用轮廓系数进行简单评估

• 可视化聚类结果

这里使用 linkage="ward" 和 metric="euclidean"，是连续数值数据中较常见的组合。需要注意的是，聚类标签中的 0、1、2 只是算法生成的簇编号，不代表类别大小、优劣或顺序。

九、Python 实现：比较不同链接准则

不同链接准则会影响层次聚类结果。下面比较 ward、complete、average 和 single 四种策略。

一般来说：

• ward 倾向于形成较紧凑、较规则的簇

• complete 更关注簇整体是否紧凑

• average 更关注簇间整体平均距离

• single 容易形成链状合并，对噪声较敏感

因此，层次聚类通常不能只运行一次就结束，而应结合数据分布、距离度量、树状图和评价指标综合判断。

十、Python 实现：绘制树状图

AgglomerativeClustering 可以保存合并关系，但绘制标准树状图通常需要借助 SciPy 的 dendrogram。

这段代码中有几个关键点：

• distance_threshold=0 表示构建完整层次合并树

• n_clusters=None 是使用距离阈值时的配套设置

• compute_distances=True 用于保存合并距离

• children_ 记录每次合并的两个子节点

• distances_ 记录每次合并发生时的距离

compute_distances=True 适合后续绘制树状图，但会增加计算和内存开销。对于小样本数据，树状图很适合观察样本从单独个体逐步合并成大簇的过程。

十一、层次聚类适用场景、优势与局限

1、适用场景

层次聚类适合以下情况：

• 数据没有标签，需要探索自然分组

• 样本量不太大

• 希望观察样本之间的层级关系

• 不确定应该分成几个簇，希望先观察合并结构

• 数据可能存在从细粒度到粗粒度的多层组织

典型应用包括：

• 客户分群

• 文档聚类

• 生物样本聚类

• 图像或特征向量聚类

• 小规模探索性数据分析

层次聚类的优势在于，它不仅能给出最终标签，还能展示样本之间的合并顺序，适合解释相似关系。

2、主要优势

层次聚类的主要优势包括：

• 可通过树状图观察多层级结构

• 结果直观，适合解释样本相似关系

• 可使用不同距离度量与链接准则

• 对小样本探索性分析很有帮助

• 凝聚式过程通常不依赖随机初始化

与 K 均值聚类相比，层次聚类更适合“先理解结构，再决定簇数”的任务。

3、主要局限

层次聚类也有明显局限：

• 计算成本较高，不适合特别大的数据集

• 对距离度量和特征尺度敏感

• 不同 linkage 可能得到不同结果

• 一旦某一步合并完成，后续不能撤销

• single linkage 容易产生链式效应

• 树状图在样本很多时难以阅读

• 通常不像 K 均值那样自然给出簇中心

因此，在需要快速处理大规模数据、需要明确簇中心或需要高效预测新样本归属时，K 均值等方法可能更合适。

十二、与 K 均值聚类和 DBSCAN 的关系

层次聚类、和 都是常见聚类方法，但适用思路不同。

图 7：层次聚类与 K 均值、DBSCAN 的区别

的核心是：

• 事先指定 k

• 通过簇中心组织样本

• 适合较大规模数值数据

• 更适合近似球形簇

层次聚类的核心是：

• 构建样本之间的层次结构

• 可通过不同高度截断得到不同簇数

• 适合小到中等规模数据

• 适合结构探索和可视化分析

的核心是：

• 基于密度寻找簇

• 可以发现任意形状簇

• 可以识别噪声点

• 对 eps 和 min_samples 较敏感

因此，如果目标是快速处理较大规模、近似球形的数据，可以优先考虑 K 均值；如果目标是发现密度结构和噪声点，可以考虑 DBSCAN；如果目标是理解样本之间的层级关系，层次聚类更合适。

小结

层次聚类通过距离度量和链接准则逐步合并样本或簇，形成从细到粗的树状结构。它适合探索样本之间的层级关系，并可通过树状图辅助判断簇数；但它计算成本较高，对距离、尺度和链接准则较敏感。

“点赞有美意，赞赏是鼓励”