层次聚类（Hierarchical Clustering）
字数 2862 2025-12-16 00:48:15

好的，我注意到你的已讲题目列表中尚未涵盖层次聚类（Hierarchical Clustering）中的一种经典且重要的算法——凝聚层次聚类（Agglomerative Hierarchical Clustering）的距离度量、链接准则与树状图（Dendrogram）生成过程。这是一个基础且关键的算法，对于理解层次聚类的全貌非常重要。

凝聚层次聚类（Agglomerative Hierarchical Clustering）的距离度量、链接准则与树状图生成过程

题目描述：
想象我们有一组数据点，没有预先设定要分成多少类，但我们想看到数据从“每个点一个类”到“所有点归为一类”的整个聚合过程，并能根据这个聚合过程决定最终的聚类数目。这就是凝聚层次聚类要解决的问题。我们需要一个清晰的算法，它不仅定义了如何计算两个数据点之间的距离，更重要的是，定义了如何计算两个簇（Cluster）之间的距离（链接准则），并一步步合并最近的簇，最终形成一颗能够可视化聚类过程的树状图。

解题过程详解：

步骤一：问题初始化与基本概念

  1. 输入：给定一个包含 n 个数据点的数据集 \(D = \{x_1, x_2, ..., x_n\}\)，以及一个计算两个数据点间距离的函数（如欧氏距离）。
  2. 初始状态：开始时，将每个数据点视为一个独立的簇。此时我们有 n 个簇。
  3. 核心输出：一个树状图（Dendrogram）。这是一个树形结构，展示了簇从底部（n个叶子节点）到顶部（1个根节点）的合并顺序和合并时的距离。
  4. 最终聚类：通过在树状图的某个“高度”进行水平切割，我们可以得到任意数量的聚类结果（从1到n类）。

步骤二：距离矩阵初始化

这是算法的起点。我们计算所有数据点两两之间的距离，形成一个 n x n 的对称距离矩阵 \(M\)。

  • \(M_{ij} = dist(x_i， x_j)\)，其中 \(dist\) 可以是欧氏距离、曼哈顿距离等。
  • 对角线上的元素为0（自己与自己的距离）。
  • 此时，这个距离矩阵也代表了簇间距离矩阵，因为每个簇只有一个点。

步骤三：迭代合并过程（算法的核心循环）

这是算法的主体，会重复 n-1 次，直到所有点合并为一个簇。

循环的每一步包含以下子步骤：

  1. 寻找最近的两个簇：在当前的距离矩阵 \(M\) 中，找到值最小的那个元素（对角线除外）。假设这个最小距离是 \(d_{min}\)，它对应于簇 \(C_a\) 和簇 \(C_b\)。

  2. 合并这两个簇：将簇 \(C_a\) 和 \(C_b\) 合并成一个新的簇 \(C_{new} = C_a \cup C_b\)。

  3. 更新距离矩阵（最关键的一步）：删除与 \(C_a\) 和 \(C_b\) 相关的行和列，并新增一行一列对应于新簇 \(C_{new}\)。新簇 \(C_{new}\) 与其它任意簇 \(C_k\) 的距离，需要根据我们选择的链接准则（Linkage Criterion）来计算。这是层次聚类的精髓所在。

    常见的链接准则详解：

    • 单链接（Single Linkage）：取两个簇中最近的两个点之间的距离。
      \(dist_{single}(C_{new}, C_k) = min(dist(x_i， x_j))\)，其中 \(x_i \in C_{new}\)， \(x_j \in C_k\)。
      • 特点：容易产生“链式效应”，擅长发现非球形、拉长的簇，但对噪声敏感。
    • 全链接（Complete Linkage）：取两个簇中最远的两个点之间的距离。
      \(dist_{complete}(C_{new}, C_k) = max(dist(x_i， x_j))\)，其中 \(x_i \in C_{new}\)， \(x_j \in C_k\)。
      • 特点：倾向于产生紧凑的、大小相近的球形簇，对噪声相对鲁棒。
    • 平均链接（Average Linkage）：取两个簇中所有点对之间的平均距离。
      \(dist_{average}(C_{new}, C_k) = \frac{1}{|C_{new}| \cdot |C_k|} \sum_{x_i \in C_{new}} \sum_{x_j \in C_k} dist(x_i, x_j)\)。
      • 特点：介于单链接和全链接之间，是一种常用的折中方法。
    • 沃德法（Ward‘s Method）：衡量的是合并两个簇导致的总方差增加。它试图在每一步合并中，最小化所有簇内误差平方和（SSE）的增加量。
      \(dist_{ward}(C_a, C_b) = \frac{|C_a| \cdot |C_b|}{|C_a| + |C_b|} \cdot ||\mu_a - \mu_b||^2\)，其中 \(\mu\) 是簇的质心。
      • 特点：倾向于生成大小均匀的簇，是许多场景下的默认选择，因为它基于方差，与K-Means的目标函数有内在联系。

  4. 记录合并信息：记录下这一步合并的簇对 \((C_a， C_b)\) 以及它们之间的距离 \(d_{min}\)。这个信息将用于绘制树状图。

步骤四：构建树状图

树状图是算法过程的直观可视化。

  1. 叶子节点：最底部的 n 个点代表初始的 n 个数据点。
  2. 内部节点与高度：每次合并产生一个新的内部节点。这个节点的高度（即在Y轴上的位置）被设置为这次合并时的距离 \(d_{min}\)。这个高度代表了这两个子簇之间的“相异性”。
  3. 连接：将这个新节点用两条线段分别连接到它合并的两个子簇（可能是叶子节点或已有的内部节点）上。
  4. 重复这个过程，直到画出最顶部的根节点，其高度是最后一次合并的距离。

步骤五：获取最终聚类结果

树状图本身并不直接给出聚类结果，它展示了所有可能性。要得到具体的 k 个簇，你需要：

  1. 在树状图的Y轴上选择一个“距离阈值”或“切割高度”。
  2. 画一条水平线穿过树状图。
  3. 这条水平线与树状图垂直线的交点数量，就是得到的簇的数量。每个交点以下的子树构成一个簇。

如何选择 k：通常观察树状图，寻找“腿”比较长的部分（即合并距离突然增大的地方），在这个高度进行切割，意味着合并的两个簇差异很大，不应再合并，从而得到有意义的聚类数目。

总结与串联

整个凝聚层次聚类算法的流程可以总结为：

  1. 初始化：计算所有点对距离，每个点自成一簇。
  2. 循环：
    • 找当前距离最近的簇对 \((A, B)\)。
    • 合并 \(A\) 和 \(B\) 为 \(C_{new}\)。
    • 用链接准则更新 \(C_{new}\) 与其他所有簇的距离。
    • 记录合并事件。
  3. 构建：利用记录信息，绘制树状图。
  4. 切割：根据树状图和分析目标，选择合适的切割点，得到最终聚类。

这个过程的核心在于链接准则的选择，它决定了算法对簇“形状”和“大小”的偏好，从而直接影响到最终的聚类效果和树状图的形态。

好的，我注意到你的已讲题目列表中尚未涵盖 层次聚类（Hierarchical Clustering） 中的一种经典且重要的算法—— 凝聚层次聚类（Agglomerative Hierarchical Clustering） 的 距离度量、链接准则与树状图（Dendrogram）生成过程 。这是一个基础且关键的算法，对于理解层次聚类的全貌非常重要。 凝聚层次聚类（Agglomerative Hierarchical Clustering）的距离度量、链接准则与树状图生成过程 题目描述 ： 想象我们有一组数据点，没有预先设定要分成多少类，但我们想看到数据从“每个点一个类”到“所有点归为一类”的整个聚合过程，并能根据这个聚合过程决定最终的聚类数目。这就是凝聚层次聚类要解决的问题。我们需要一个清晰的算法，它不仅定义了如何计算两个数据点之间的距离，更重要的是，定义了如何计算两个 簇（Cluster） 之间的距离（链接准则），并一步步合并最近的簇，最终形成一颗能够可视化聚类过程的树状图。 解题过程详解 ： 步骤一：问题初始化与基本概念 输入 ：给定一个包含 n 个数据点的数据集 $D = \{x_ 1, x_ 2, ..., x_ n\}$，以及一个计算两个数据点间距离的函数（如欧氏距离）。 初始状态 ：开始时，将每个数据点视为一个独立的簇。此时我们有 n 个簇。 核心输出 ：一个 树状图（Dendrogram） 。这是一个树形结构，展示了簇从底部（ n 个叶子节点）到顶部（1个根节点）的合并顺序和合并时的距离。 最终聚类 ：通过在树状图的某个“高度”进行水平切割，我们可以得到任意数量的聚类结果（从1到 n 类）。 步骤二：距离矩阵初始化 这是算法的起点。我们计算所有数据点两两之间的距离，形成一个 n x n 的对称距离矩阵 $M$。 $M_ {ij} = dist(x_ i， x_ j)$，其中 $dist$ 可以是欧氏距离、曼哈顿距离等。 对角线上的元素为0（自己与自己的距离）。 此时，这个距离矩阵也代表了 簇间距离矩阵 ，因为每个簇只有一个点。 步骤三：迭代合并过程（算法的核心循环） 这是算法的主体，会重复 n-1 次，直到所有点合并为一个簇。 循环的每一步包含以下子步骤 ： 寻找最近的两个簇 ：在当前的距离矩阵 $M$ 中，找到值最小的那个元素（对角线除外）。假设这个最小距离是 $d_ {min}$，它对应于簇 $C_ a$ 和簇 $C_ b$。 合并这两个簇 ：将簇 $C_ a$ 和 $C_ b$ 合并成一个新的簇 $C_ {new} = C_ a \cup C_ b$。 更新距离矩阵 （最关键的一步）：删除与 $C_ a$ 和 $C_ b$ 相关的行和列，并新增一行一列对应于新簇 $C_ {new}$。新簇 $C_ {new}$ 与其它任意簇 $C_ k$ 的距离，需要根据我们选择的 链接准则（Linkage Criterion） 来计算。这是层次聚类的精髓所在。 常见的链接准则详解 ： 单链接（Single Linkage） ：取两个簇中 最近 的两个点之间的距离。 $dist_ {single}(C_ {new}, C_ k) = min(dist(x_ i， x_ j))$，其中 $x_ i \in C_ {new}$， $x_ j \in C_ k$。 特点 ：容易产生“链式效应”，擅长发现非球形、拉长的簇，但对噪声敏感。 全链接（Complete Linkage） ：取两个簇中 最远 的两个点之间的距离。 $dist_ {complete}(C_ {new}, C_ k) = max(dist(x_ i， x_ j))$，其中 $x_ i \in C_ {new}$， $x_ j \in C_ k$。 特点 ：倾向于产生紧凑的、大小相近的球形簇，对噪声相对鲁棒。 平均链接（Average Linkage） ：取两个簇中所有点对之间的 平均 距离。 $dist_ {average}(C_ {new}, C_ k) = \frac{1}{|C_ {new}| \cdot |C_ k|} \sum_ {x_ i \in C_ {new}} \sum_ {x_ j \in C_ k} dist(x_ i, x_ j)$。 特点 ：介于单链接和全链接之间，是一种常用的折中方法。 沃德法（Ward‘s Method） ：衡量的是合并两个簇导致的 总方差增加 。它试图在每一步合并中，最小化所有簇内误差平方和（SSE）的增加量。 $dist_ {ward}(C_ a, C_ b) = \frac{|C_ a| \cdot |C_ b|}{|C_ a| + |C_ b|} \cdot ||\mu_ a - \mu_ b||^2$，其中 $\mu$ 是簇的质心。 特点 ：倾向于生成大小均匀的簇，是许多场景下的默认选择，因为它基于方差，与K-Means的目标函数有内在联系。 记录合并信息 ：记录下这一步合并的簇对 $(C_ a， C_ b)$ 以及它们之间的距离 $d_ {min}$。这个信息将用于绘制树状图。 步骤四：构建树状图 树状图是算法过程的直观可视化。 叶子节点 ：最底部的 n 个点代表初始的 n 个数据点。 内部节点与高度 ：每次合并产生一个新的内部节点。这个节点的 高度 （即在Y轴上的位置）被设置为这次合并时的距离 $d_ {min}$。这个高度代表了这两个子簇之间的“相异性”。 连接 ：将这个新节点用两条线段分别连接到它合并的两个子簇（可能是叶子节点或已有的内部节点）上。 重复这个过程，直到画出最顶部的根节点，其高度是最后一次合并的距离。 步骤五：获取最终聚类结果 树状图本身并不直接给出聚类结果，它展示了所有可能性。要得到具体的 k 个簇，你需要： 在树状图的Y轴上选择一个“距离阈值”或“切割高度”。 画一条水平线穿过树状图。 这条水平线与树状图垂直线的交点数量，就是得到的簇的数量。每个交点以下的子树构成一个簇。 如何选择 k ：通常观察树状图，寻找“腿”比较长的部分（即合并距离突然增大的地方），在这个高度进行切割，意味着合并的两个簇差异很大，不应再合并，从而得到有意义的聚类数目。 总结与串联 整个凝聚层次聚类算法的流程可以总结为： 初始化 ：计算所有点对距离，每个点自成一簇。 循环 ： 找当前距离最近的簇对 $(A, B)$。 合并 $A$ 和 $B$ 为 $C_ {new}$。 用 链接准则 更新 $C_ {new}$ 与其他所有簇的距离。 记录合并事件。 构建 ：利用记录信息，绘制树状图。 切割 ：根据树状图和分析目标，选择合适的切割点，得到最终聚类。 这个过程的核心在于 链接准则 的选择，它决定了算法对簇“形状”和“大小”的偏好，从而直接影响到最终的聚类效果和树状图的形态。