基于层次聚类（Hierarchical Clustering）的谱系图（Dendrogram）构建、链接准则与最优切割点选择
字数 3326 2025-12-23 17:37:33

基于层次聚类（Hierarchical Clustering）的谱系图（Dendrogram）构建、链接准则与最优切割点选择

题目描述：
层次聚类（Hierarchical Clustering）是一种常用的无监督聚类方法，它通过计算样本之间的相似度，构建一个树状的层次结构（称为谱系图或系统树图），来揭示数据内在的嵌套式聚类关系。本题目将详细讲解层次聚类的完整构建过程，包括距离矩阵计算、链接方法、谱系图生成，以及如何在谱系图上选择最优的聚类数量。层次聚类分为两种主要策略：凝聚（自底向上） 和分裂（自顶向下），这里我们将聚焦于应用更广泛的凝聚层次聚类。

解题过程：

第一步：理解核心目标与输入数据

  • 目标：给定一组数据样本（例如N个样本，每个样本是D维特征向量），我们希望将这些样本组织成一个树状结构，使得“相似”的样本在树中更早地合并在一起。这个树状结构（谱系图）展示了从每个样本作为一个单独的类（叶子节点），逐步合并，直到所有样本合并为一个大类（根节点）的完整过程。
  • 输入：N×D的数据矩阵（N个样本，D个特征）。
  • 输出：
    1. 一个谱系图（Dendrogram），它以树的形式可视化合并过程，其y轴通常表示合并时的距离（或不相似度）。
    2. 一个聚类划分。通过“切割”谱系图，可以获得任意数量的簇（从N个簇到1个簇）。

第二步：计算距离（相似度）矩阵
层次聚类的起点是样本间的距离矩阵（或相似度矩阵）。我们需要计算所有样本对之间的距离。

  • 常用距离度量（对于连续型特征）：
    • 欧氏距离：最常用，适用于各向同性（各向变化同等重要）的数据。
    • 曼哈顿距离：对异常值稍稳健。
    • 余弦距离：衡量向量方向的差异，常用于文本数据。
  • 假设有样本i和j，它们的特征向量为 \(\mathbf{x}_i\) 和 \(\mathbf{x}_j\)。
    • 欧氏距离：\(d(i, j) = \sqrt{\sum_{k=1}^{D} (x_{ik} - x_{jk})^2}\)。
  • 计算后得到一个 \(N \times N\) 的对称距离矩阵，记为 \(D\)，其中 \(D_{ij} = d(i, j)\)，且对角线元素 \(D_{ii} = 0\)。

第三步：选择链接准则（Linkage Criterion）
链接准则是层次聚类的核心决策规则，它定义了两个类簇之间的距离应如何基于其包含的样本点之间的距离来计算。不同的链接准则会产生不同形状的聚类结果。

  • 单链接：两个簇之间的距离定义为两个簇中最近样本对的距离。
    • 公式：\(d_{\text{single}}(C_A, C_B) = \min_{i \in C_A, j \in C_B} d(i, j)\)。
    • 特点：容易产生“链式效应”，倾向于生成细长、延展的簇，对噪声敏感。
  • 全链接：两个簇之间的距离定义为两个簇中最远样本对的距离。
    • 公式：\(d_{\text{complete}}(C_A, C_B) = \max_{i \in C_A, j \in C_B} d(i, j)\)。
    • 特点：倾向于生成紧凑、球形、大小相近的簇，对异常值敏感。
  • 平均链接：两个簇之间的距离定义为两个簇中所有样本对距离的平均值。
    • 公式：\(d_{\text{average}}(C_A, C_B) = \frac{1}{|C_A| |C_B|} \sum_{i \in C_A} \sum_{j \in C_B} d(i, j)\)。
    • 特点：介于单链接和全链接之间，是一种折中方案，相对常用。
  • 沃德链接：两个簇合并时，所有簇内方差（离差平方和）的增加量最小。
    • 公式：\(d_{\text{Ward}}(C_A, C_B) = \sqrt{\frac{|C_A||C_B|}{|C_A| + |C_B|}} \lVert \mathbf{c}_A - \mathbf{c}_B \rVert^2\)，其中 \(\mathbf{c}\) 是簇的质心。
    • 特点：倾向于生成大小相近、方差小的簇，是许多应用（如生态学、社会科学）的默认选择。

第四步：凝聚层次聚类的迭代合并算法
我们采用自底向上的策略，初始时每个样本自成一类，然后迭代地将最相似的两个类合并，直到所有样本合并为一类。

  1. 初始化：
    • 将每个样本视为一个单独的簇。此时我们有N个簇。
    • 创建一个簇间距离矩阵，初始时就是样本间距离矩阵 \(D\)。
    • 记录每次合并的信息（哪两个簇合并，合并时的距离）。
  2. 迭代合并（共进行N-1次合并）：
    a. 寻找最相似的两个簇：在当前簇间距离矩阵中，找到距离最小的两个簇 \(C_p\) 和 \(C_q\)。
    b. 合并这两个簇：创建一个新簇 \(C_r = C_p \cup C_q\)。
    c. 更新簇间距离矩阵：
    - 删除与 \(C_p\) 和 \(C_q\) 相关的行和列。
    - 计算新簇 \(C_r\) 与所有其他现有簇 \(C_k\) 的距离，使用第三步中选择的链接准则（例如，全链接则计算新簇中所有点到 \(C_k\) 中所有点的最大距离）。
    - 将新簇 \(C_r\) 对应的行和列加入距离矩阵。
    d. 记录合并：记录“簇 \(p\) 和簇 \(q\) 在距离 \(d\) 处合并”，这个信息用于后续绘制谱系图。
  3. 终止：当所有样本合并为一个簇时，算法停止。

第五步：构建谱系图
谱系图是上述合并过程的树形可视化。

  • 绘制方法：
    • 每个样本是谱系图最底部的叶子节点。
    • 每次合并操作对应谱系图中的一个内部节点。这个节点的y坐标是此次合并对应的簇间距离（即不相似度）。
    • 合并的两个簇（可能是叶子节点或内部节点）通过向上延伸的竖线与这个内部节点相连。两条竖线在y坐标等于合并距离的位置汇合成一条新的竖线，继续向上延伸，参与后续的合并。
  • 解读谱系图：
    • 垂直方向（y轴）表示距离或不相似度。y值越大，表示合并的两个簇差异越大。
    • 水平方向（x轴）表示样本，其顺序经过排列，使得合并的线条尽量不交叉，没有特殊的数值含义。
    • 在任意一个高度（距离）上，横向切割谱系图，可以得到该距离尺度下的聚类划分。切割线穿过的水平分支数，就是该划分下的簇数。

第六步：确定最优聚类数量（切割点选择）
从谱系图可以产生从1到N个簇的任意划分，如何选择“最优”的簇数K？常用的启发式方法是观察合并距离的跳跃幅度。

  1. 观察谱系图的“长腿”：在谱系图中，如果某些合并操作对应的y轴距离（合并距离）突然显著增大，说明这次合并将两个差异很大的簇组合到了一起。这暗示在合并之前，这两个簇是相对独立的。因此，最优的切割点通常设置在最后一次大跳跃之前。
  2. 计算合并距离的差值：我们可以列出每次合并对应的距离，记为 \(d_1, d_2, ..., d_{N-1}\)。
    • 计算相邻合并距离的差值：\(\Delta d_i = d_{i} - d_{i-1}\)（通常从第二次合并开始看）。
    • 找到差值最大的位置 \(i\)。那么，在合并 \(i\) 之前，有 \(N-i+1\) 个簇。这通常被认为是“自然”的簇数K。
  3. 结合先验知识：如果对数据的簇数有领域知识，也可以直接指定K，然后在谱系图上从y轴对应高度切割即可得到相应的聚类结果。

总结：
层次聚类的核心在于距离矩阵、链接准则、谱系图。其优势在于无需预先指定簇数，并且谱系图提供了数据层次结构的完整视图，有助于理解数据。其计算复杂度为 \(O(N^3)\) 到 \(O(N^2 \log N)\)（取决于实现），因此不适合非常大的数据集。在实际应用中，沃德链接和平均链接通常能产生更均衡的簇，是更常用、更稳健的选择。

基于层次聚类（Hierarchical Clustering）的谱系图（Dendrogram）构建、链接准则与最优切割点选择 题目描述 ： 层次聚类（Hierarchical Clustering）是一种常用的无监督聚类方法，它通过计算样本之间的相似度，构建一个树状的层次结构（称为谱系图或系统树图），来揭示数据内在的嵌套式聚类关系。本题目将详细讲解层次聚类的 完整构建过程 ，包括 距离矩阵计算、链接方法、谱系图生成 ，以及如何在谱系图上 选择最优的聚类数量 。层次聚类分为两种主要策略： 凝聚（自底向上） 和 分裂（自顶向下） ，这里我们将聚焦于应用更广泛的凝聚层次聚类。 解题过程 ： 第一步：理解核心目标与输入数据 目标 ：给定一组数据样本（例如N个样本，每个样本是D维特征向量），我们希望将这些样本组织成一个树状结构，使得“相似”的样本在树中更早地合并在一起。这个树状结构（谱系图）展示了从每个样本作为一个单独的类（叶子节点），逐步合并，直到所有样本合并为一个大类（根节点）的完整过程。 输入 ：N×D的数据矩阵（N个样本，D个特征）。 输出 ： 一个 谱系图 （Dendrogram），它以树的形式可视化合并过程，其y轴通常表示合并时的距离（或不相似度）。 一个 聚类划分 。通过“切割”谱系图，可以获得任意数量的簇（从N个簇到1个簇）。 第二步：计算距离（相似度）矩阵 层次聚类的起点是样本间的 距离矩阵 （或相似度矩阵）。我们需要计算 所有样本对 之间的距离。 常用 距离度量 （对于连续型特征）： 欧氏距离 ：最常用，适用于各向同性（各向变化同等重要）的数据。 曼哈顿距离 ：对异常值稍稳健。 余弦距离 ：衡量向量方向的差异，常用于文本数据。 假设有样本i和j，它们的特征向量为 \( \mathbf{x}_ i \) 和 \( \mathbf{x}_ j \)。 欧氏距离：\( d(i, j) = \sqrt{\sum_ {k=1}^{D} (x_ {ik} - x_ {jk})^2} \)。 计算后得到一个 \( N \times N \) 的 对称距离矩阵 ，记为 \( D \)，其中 \( D_ {ij} = d(i, j) \)，且对角线元素 \( D_ {ii} = 0 \)。 第三步：选择链接准则（Linkage Criterion） 链接准则是层次聚类的 核心决策规则 ，它定义了 两个类簇之间 的距离应如何基于其包含的样本点之间的距离来计算。不同的链接准则会产生不同形状的聚类结果。 单链接 ：两个簇之间的距离定义为 两个簇中最近样本对 的距离。 公式：\( d_ {\text{single}}(C_ A, C_ B) = \min_ {i \in C_ A, j \in C_ B} d(i, j) \)。 特点：容易产生“链式效应”，倾向于生成细长、延展的簇，对噪声敏感。 全链接 ：两个簇之间的距离定义为 两个簇中最远样本对 的距离。 公式：\( d_ {\text{complete}}(C_ A, C_ B) = \max_ {i \in C_ A, j \in C_ B} d(i, j) \)。 特点：倾向于生成紧凑、球形、大小相近的簇，对异常值敏感。 平均链接 ：两个簇之间的距离定义为 两个簇中所有样本对距离的平均值 。 公式：\( d_ {\text{average}}(C_ A, C_ B) = \frac{1}{|C_ A| |C_ B|} \sum_ {i \in C_ A} \sum_ {j \in C_ B} d(i, j) \)。 特点：介于单链接和全链接之间，是一种折中方案，相对常用。 沃德链接 ：两个簇合并时， 所有簇内方差（离差平方和）的增加量最小 。 公式：\( d_ {\text{Ward}}(C_ A, C_ B) = \sqrt{\frac{|C_ A||C_ B|}{|C_ A| + |C_ B|}} \lVert \mathbf{c}_ A - \mathbf{c}_ B \rVert^2 \)，其中 \( \mathbf{c} \) 是簇的质心。 特点：倾向于生成大小相近、方差小的簇，是许多应用（如生态学、社会科学）的默认选择。 第四步：凝聚层次聚类的迭代合并算法 我们采用 自底向上 的策略，初始时每个样本自成一类，然后 迭代地将最相似的两个类合并 ，直到所有样本合并为一类。 初始化 ： 将每个样本视为一个单独的簇。此时我们有N个簇。 创建一个 簇间距离矩阵 ，初始时就是 样本间距离矩阵 \( D \)。 记录每次合并的信息（哪两个簇合并，合并时的距离）。 迭代合并 （共进行N-1次合并）： a. 寻找最相似的两个簇 ：在当前簇间距离矩阵中，找到 距离最小 的两个簇 \( C_ p \) 和 \( C_ q \)。 b. 合并这两个簇 ：创建一个新簇 \( C_ r = C_ p \cup C_ q \)。 c. 更新簇间距离矩阵 ： - 删除与 \( C_ p \) 和 \( C_ q \) 相关的行和列。 - 计算 新簇 \( C_ r \) 与 所有其他现有簇 \( C_ k \) 的距离，使用第三步中选择的链接准则（例如，全链接则计算新簇中所有点到 \( C_ k \) 中所有点的最大距离）。 - 将新簇 \( C_ r \) 对应的行和列加入距离矩阵。 d. 记录合并 ：记录“簇 \( p \) 和簇 \( q \) 在距离 \( d \) 处合并”，这个信息用于后续绘制谱系图。 终止 ：当所有样本合并为一个簇时，算法停止。 第五步：构建谱系图 谱系图是上述合并过程的树形可视化。 绘制方法 ： 每个样本是谱系图最底部的叶子节点。 每次合并操作对应谱系图中的一个 内部节点 。这个节点的 y坐标 是此次合并对应的 簇间距离 （即不相似度）。 合并的两个簇（可能是叶子节点或内部节点）通过向上延伸的竖线与这个内部节点相连。两条竖线在y坐标等于合并距离的位置汇合成一条新的竖线，继续向上延伸，参与后续的合并。 解读谱系图 ： 垂直方向（y轴）表示 距离或不相似度 。y值越大，表示合并的两个簇差异越大。 水平方向（x轴）表示样本，其顺序经过排列，使得合并的线条尽量不交叉，没有特殊的数值含义。 在任意一个高度（距离）上， 横向切割 谱系图，可以得到该距离尺度下的聚类划分。切割线穿过的水平分支数，就是该划分下的簇数。 第六步：确定最优聚类数量（切割点选择） 从谱系图可以产生从1到N个簇的任意划分，如何选择“最优”的簇数K？常用的启发式方法是观察 合并距离的跳跃幅度 。 观察谱系图的“长腿” ：在谱系图中，如果某些合并操作对应的y轴距离（合并距离）突然显著增大，说明这次合并将两个差异很大的簇组合到了一起。这暗示 在合并之前，这两个簇是相对独立的 。因此，最优的切割点通常设置在 最后一次大跳跃之前 。 计算合并距离的差值 ：我们可以列出每次合并对应的距离，记为 \( d_ 1, d_ 2, ..., d_ {N-1} \)。 计算相邻合并距离的差值：\( \Delta d_ i = d_ {i} - d_ {i-1} \)（通常从第二次合并开始看）。 找到差值最大的位置 \( i \)。那么，在合并 \( i \) 之前，有 \( N-i+1 \) 个簇。这通常被认为是“自然”的簇数K。 结合先验知识 ：如果对数据的簇数有领域知识，也可以直接指定K，然后在谱系图上从y轴对应高度切割即可得到相应的聚类结果。 总结 ： 层次聚类的核心在于 距离矩阵、链接准则、谱系图 。其优势在于 无需预先指定簇数 ，并且 谱系图提供了数据层次结构的完整视图 ，有助于理解数据。其计算复杂度为 \( O(N^3) \) 到 \( O(N^2 \log N) \)（取决于实现），因此不适合非常大的数据集。在实际应用中， 沃德链接 和 平均链接 通常能产生更均衡的簇，是更常用、更稳健的选择。