K-中心点聚类（K-Medoids）算法的原理与迭代优化过程
字数 4372 2025-12-10 03:10:10

K-中心点聚类（K-Medoids）算法的原理与迭代优化过程

题目描述

K-中心点聚类（K-Medoids）是一种经典的划分聚类算法，与K-均值（K-Means）类似，其目标也是将n个数据点划分到k个簇中，使得同一簇内的点相似度较高，而不同簇的点相似度较低。然而，K-Means通过计算簇内点的均值（质心）作为簇的代表点，这种方法对离群点（Outliers）非常敏感。相反，K-Medoids则从每个簇的实际数据点中选取一个样本点作为簇的代表点（称为中心点，Medoid），其优化目标是最小化所有数据点到其所属簇的中心点的距离（或不相似度）之和。由于中心点是真实存在的数据点，相比K-Means的均值（可能不存在于数据集），K-Medoids对噪声和离群点的鲁棒性更强。最常见的K-Medoids实现是PAM算法（Partitioning Around Medoids，围绕中心点的划分）。

我将为你循序渐进地讲解K-Medoids（PAM）算法的核心思想、目标函数、详细的迭代优化步骤（PAM算法），包括初始化、分配、交换和评估，并简要介绍其变体，如CLARA和CLARANS。

解题过程（算法原理与步骤）

第一步：理解问题与设定

  1. 输入：
    • 数据集：\(D = \{ x_1, x_2, ..., x_n \}\)，包含n个数据点。
    • 聚类数量：k。
    • 不相似度/距离度量：\(d(x_i, x_j)\)，通常使用欧氏距离、曼哈顿距离等。
  2. 输出：
    • 划分结果：k个簇 \(C_1, C_2, ..., C_k\)。
    • 每个簇的中心点：\(m_1, m_2, ..., m_k\)，其中每个 \(m_t \in D\) 且属于其代表的簇 \(C_t\)。
  3. 核心目标：
    寻找k个中心点和对应的簇划分，使得以下目标函数（总代价）最小化：

\[ TC = \sum_{i=1}^{n} d(x_i, m_{c(i)}) \]

其中，$ c(i) $ 表示数据点 $ x_i $ 所属簇的索引，$ m_{c(i)} $ 是该簇的中心点。

第二步：核心算法——PAM（Partitioning Around Medoids）

PAM是解决K-Medoids问题的经典启发式算法，分为两个主要阶段：构建阶段 和 交换阶段。

阶段一：构建阶段（BUILD）
构建阶段旨在为交换阶段提供一个较好的初始中心点集合。

  1. 随机选择一个数据点作为第一个中心点。
  2. 重复以下步骤，直到选出k个中心点：
    • 对于每一个非中心点 \(x_j\)：
      计算如果选择 \(x_j\) 作为下一个中心点，能带来的总距离减少量。具体地，对于每个非中心点 \(x_i\) (i ≠ j)，比较其到当前已选中心点的最小距离 \(D_{current}(x_i)\)，和到候选点 \(x_j\) 的距离 \(d(x_i, x_j)\)。如果 \(d(x_i, x_j) < D_{current}(x_i)\)，则距离减少量为 \(D_{current}(x_i) - d(x_i, x_j)\)，否则为0。将所有非中心点的距离减少量求和，得到选择 \(x_j\) 的收益。
    • 选择能够带来最大总距离减少量的那个非中心点，将其加入中心点集合。
    • 这个阶段的目标是贪婪地选取能使总体不相似度下降最快的数据点作为中心点。

阶段二：交换阶段（SWAP）
交换阶段是PAM算法的核心迭代优化过程，旨在通过系统地尝试交换中心点与非中心点来改进聚类质量。

  1. 分配步骤：给定当前的中心点集合 \(M = \{ m_1, m_2, ..., m_k \}\)。
    • 对于数据集中的每一个点 \(x_i\)：
      • 计算 \(x_i\) 到所有k个中心点的距离 \(d(x_i, m_t)\)，其中 \(t = 1, 2, ..., k\)。
      • 将 \(x_i\) 分配到距离最近的那个中心点所在的簇。即，\(c(i) = \arg\min_{t} d(x_i, m_t)\)。
      • 记录下 \(x_i\) 到其最近中心点的距离，同时记录下到第二近中心点的距离（这在后续计算交换代价时会用到）。
  2. 尝试交换与评估步骤：这是PAM最精细的部分，目标是检查能否通过交换一个中心点和一个非中心点来降低总代价 \(TC\)。
    • 外层循环：遍历每一个当前的中心点 \(m_t\)。
    • 内层循环：遍历每一个非中心点 \(x_j\)（即 \(x_j \notin M\)）。
    • 核心计算：评估“用非中心点 \(x_j\) 替换中心点 \(m_t\)”这一交换所产生的总代价变化 \(\Delta TC\)。
      • 我们需要考虑交换对所有数据点的归属和距离成本的影响，而不仅仅是 \(m_t\) 所在簇的点。因为 \(m_t\) 被替换后，原来属于其他簇的点可能会被新的中心点 \(x_j\) 吸引过去。
      • 代价变化 \(\Delta TC\) 的计算：
        对于数据集中的每一个点 \(x_i\)：
        1. 情况A：如果 \(x_i\) 当前所属的中心点不是 \(m_t\)（即 \(c(i) \ne t\)），那么它可能有两种选择：
          • 保持原状：仍属于原来的簇，代价为 \(d(x_i, m_{c(i)})\)。
          • 被新中心点 \(x_j\) 吸引：代价变为 \(d(x_i, x_j)\)。
          • 它为总代价贡献的变化是：\(\max(d(x_i, x_j) - d(x_i, m_{c(i)}), 0)\)？ 等等，这里需要更精确的分析。实际上，对于这类点，交换后的代价是 \(\min( d(x_i, m_{c(i)}), d(x_i, x_j) )\)。而交换前的代价是 \(d(x_i, m_{c(i)})\)。所以变化量是 \(\min( d(x_i, m_{c(i)}), d(x_i, x_j) ) - d(x_i, m_{c(i)})\)。
            然而，PAM算法采用了一种更高效的分情况快速计算方法：
          • 如果 \(d(x_i, m_{c(i)}) \le d_2(x_i)\) （\(d_2(x_i)\) 是 \(x_i\) 到第二近中心点的距离），那么 \(x_i\) 的最优中心点就是当前的 \(m_{c(i)}\)。交换后，如果 \(m_{c(i)}\) 不变，则 \(x_i\) 的归属不变，代价不变。如果 \(m_{c(i)}\) 被换成了 \(x_j\)，则新代价是 \(\min( d(x_i, x_j), d_2(x_i) )\)。
          • 如果 \(d(x_i, m_{c(i)}) > d_2(x_i)\)，那么 \(x_i\) 本来就“不太满意”当前的中心点，交换可能带来改变。
            为了简化理解，我们可以记住核心公式：对于一次候选交换 (m_t, x_j)，总代价变化是交换后所有点的距离总和减去交换前的总和。PAM算法通过巧妙利用之前计算的最优和第二优距离，避免了为每次候选交换都重新计算所有点的归属，从而加速了计算。其核心是计算每个点 \(x_i\) 在这次交换下的“个人代价变化”。
      • 将所有点 \(x_i\) 的个人代价变化求和，就得到了这次交换 (m_t, x_j) 的总代价变化 \(\Delta TC_{t,j}\)。
    • 选择与执行：
      • 在所有候选交换对 \((m_t, x_j)\) 中，找到能使 \(\Delta TC\) 减少最多（即 \(\Delta TC\) 为负数且绝对值最大）的那一对。
      • 如果存在这样的交换对（即 \(\min_{t, j} \Delta TC_{t,j} < 0\)），则执行这次交换：将中心点 \(m_t\) 从中心点集合中移除，加入 \(x_j\)。
      • 如果不存在能使总代价降低的交换（即所有 \(\Delta TC_{t,j} \ge 0\)），则算法终止，当前的中心点集合和簇划分即为最终结果。
  3. 迭代：在每次成功执行交换后，重新执行分配步骤，更新所有点的簇归属和距离信息，然后再次进入尝试交换与评估步骤。如此循环，直到无法再通过任何交换降低总代价为止。

第三步：算法特点、复杂度与变体

  1. 算法特点：
    • 鲁棒性：对离群点不敏感，因为中心点是实际存在的数据点。
    • 适用性：可以处理任意不相似度矩阵，不要求数据点存在于欧氏空间（只需定义距离）。
    • 确定性：给定相同的初始中心点，PAM的结果是确定的。
  2. 时间复杂度：
    • 交换阶段每次迭代需要计算 \(O(k(n-k)^2)\) 次候选交换的代价。对于每个候选交换，评估所有n个点，因此每次迭代复杂度为 \(O(k(n-k)^2 * n)\)，当k远小于n时，近似为 \(O(kn^3)\)。这使得PAM不适用于大规模数据集。
  3. 常见变体：
    • CLARA（Clustering LARge Applications）：不直接在整个数据集上运行PAM，而是多次从数据集中抽取样本，在每个样本上运行PAM，然后选择在整个数据集上总代价最小的那组中心点。适用于大规模数据，但结果质量依赖于样本的代表性。
    • CLARANS（Clustering Large Applications based on RANdomized Search）：将聚类过程视为在图的节点（即所有可能的中-心点集合）上搜索最优解。它随机地进行邻居搜索（邻居节点指通过交换一个中心点得到的集合），并允许向上移动（接受暂时更差的解）以避免局部最优，类似于随机化搜索。通常比CLARA更有效。

总结

K-中心点聚类（K-Medoids）通过选择实际数据点作为簇代表，增强了聚类对噪声的鲁棒性。其经典实现PAM算法通过构建阶段初始化，并通过迭代的交换阶段（分配、评估所有可能的中心点-非中心点交换）来优化目标函数，直到收敛。尽管PAM的计算成本较高，但其思想清晰，且其变体CLARA和CLARANS使得该算法能应用于更大规模的数据集。理解PAM的关键在于掌握其基于交换的优化策略和代价变化的高效计算方法。

K-中心点聚类（K-Medoids）算法的原理与迭代优化过程 题目描述 K-中心点聚类（K-Medoids）是一种经典的划分聚类算法，与K-均值（K-Means）类似，其目标也是将n个数据点划分到k个簇中，使得同一簇内的点相似度较高，而不同簇的点相似度较低。然而，K-Means通过计算簇内点的均值（质心）作为簇的代表点，这种方法对离群点（Outliers）非常敏感。相反，K-Medoids则从每个簇的实际数据点中选取一个样本点作为簇的代表点（称为中心点，Medoid），其优化目标是 最小化所有数据点到其所属簇的中心点的距离（或不相似度）之和 。由于中心点是真实存在的数据点，相比K-Means的均值（可能不存在于数据集），K-Medoids对噪声和离群点的鲁棒性更强。最常见的K-Medoids实现是PAM算法（Partitioning Around Medoids，围绕中心点的划分）。 我将为你循序渐进地讲解K-Medoids（PAM）算法的核心思想、目标函数、详细的迭代优化步骤（PAM算法），包括初始化、分配、交换和评估，并简要介绍其变体，如CLARA和CLARANS。 解题过程（算法原理与步骤） 第一步：理解问题与设定 输入 ： 数据集：\( D = \{ x_ 1, x_ 2, ..., x_ n \} \)，包含n个数据点。 聚类数量：k。 不相似度/距离度量：\( d(x_ i, x_ j) \)，通常使用欧氏距离、曼哈顿距离等。 输出 ： 划分结果：k个簇 \( C_ 1, C_ 2, ..., C_ k \)。 每个簇的中心点：\( m_ 1, m_ 2, ..., m_ k \)，其中每个 \( m_ t \in D \) 且属于其代表的簇 \( C_ t \)。 核心目标 ： 寻找k个中心点和对应的簇划分，使得以下目标函数（总代价）最小化： \[ TC = \sum_ {i=1}^{n} d(x_ i, m_ {c(i)}) \] 其中，\( c(i) \) 表示数据点 \( x_ i \) 所属簇的索引，\( m_ {c(i)} \) 是该簇的中心点。 第二步：核心算法——PAM（Partitioning Around Medoids） PAM是解决K-Medoids问题的经典启发式算法，分为两个主要阶段： 构建阶段 和 交换阶段 。 阶段一：构建阶段（BUILD） 构建阶段旨在为交换阶段提供一个较好的初始中心点集合。 随机选择一个数据点作为第一个中心点。 重复以下步骤，直到选出k个中心点 ： 对于每一个 非中心点 \( x_ j \)： 计算如果选择 \( x_ j \) 作为下一个中心点，能带来的 总距离减少量 。具体地，对于每个非中心点 \( x_ i \) (i ≠ j)，比较其到当前已选中心点的最小距离 \( D_ {current}(x_ i) \)，和到候选点 \( x_ j \) 的距离 \( d(x_ i, x_ j) \)。如果 \( d(x_ i, x_ j) < D_ {current}(x_ i) \)，则距离减少量为 \( D_ {current}(x_ i) - d(x_ i, x_ j) \)，否则为0。将所有非中心点的距离减少量求和，得到选择 \( x_ j \) 的收益。 选择能够带来 最大总距离减少量 的那个非中心点，将其加入中心点集合。 这个阶段的目标是贪婪地选取能使总体不相似度下降最快的数据点作为中心点。 阶段二：交换阶段（SWAP） 交换阶段是PAM算法的核心迭代优化过程，旨在通过系统地尝试交换中心点与非中心点来改进聚类质量。 分配步骤 ：给定当前的中心点集合 \( M = \{ m_ 1, m_ 2, ..., m_ k \} \)。 对于数据集中的每一个点 \( x_ i \)： 计算 \( x_ i \) 到所有k个中心点的距离 \( d(x_ i, m_ t) \)，其中 \( t = 1, 2, ..., k \)。 将 \( x_ i \) 分配到 距离最近 的那个中心点所在的簇。即，\( c(i) = \arg\min_ {t} d(x_ i, m_ t) \)。 记录下 \( x_ i \) 到其最近中心点的距离，同时记录下到 第二近中心点 的距离（这在后续计算交换代价时会用到）。 尝试交换与评估步骤 ：这是PAM最精细的部分，目标是检查能否通过交换一个中心点和一个非中心点来降低总代价 \( TC \)。 外层循环 ：遍历每一个当前的中心点 \( m_ t \)。 内层循环 ：遍历每一个非中心点 \( x_ j \)（即 \( x_ j \notin M \)）。 核心计算 ：评估“用非中心点 \( x_ j \) 替换中心点 \( m_ t \)”这一交换所产生的 总代价变化 \( \Delta TC \)。 我们需要考虑交换对 所有数据点 的归属和距离成本的影响，而不仅仅是 \( m_ t \) 所在簇的点。因为 \( m_ t \) 被替换后，原来属于其他簇的点可能会被新的中心点 \( x_ j \) 吸引过去。 代价变化 \( \Delta TC \) 的计算 ： 对于数据集中的每一个点 \( x_ i \)： 情况A ：如果 \( x_ i \) 当前所属的中心点不是 \( m_ t \)（即 \( c(i) \ne t \)），那么它可能有两种选择： 保持原状 ：仍属于原来的簇，代价为 \( d(x_ i, m_ {c(i)}) \)。 被新中心点 \( x_ j \) 吸引 ：代价变为 \( d(x_ i, x_ j) \)。 它为总代价贡献的变化是：\( \max(d(x_ i, x_ j) - d(x_ i, m_ {c(i)}), 0) \)？ 等等，这里需要更精确的分析。实际上，对于这类点，交换后的代价是 \( \min( d(x_ i, m_ {c(i)}), d(x_ i, x_ j) ) \)。而交换前的代价是 \( d(x_ i, m_ {c(i)}) \)。所以变化量是 \( \min( d(x_ i, m_ {c(i)}), d(x_ i, x_ j) ) - d(x_ i, m_ {c(i)}) \)。 然而，PAM算法采用了一种更高效的 分情况快速计算 方法： 如果 \( d(x_ i, m_ {c(i)}) \le d_ 2(x_ i) \) （\( d_ 2(x_ i) \) 是 \( x_ i \) 到第二近中心点的距离），那么 \( x_ i \) 的最优中心点就是当前的 \( m_ {c(i)} \)。交换后，如果 \( m_ {c(i)} \) 不变，则 \( x_ i \) 的归属不变，代价不变。如果 \( m_ {c(i)} \) 被换成了 \( x_ j \)，则新代价是 \( \min( d(x_ i, x_ j), d_ 2(x_ i) ) \)。 如果 \( d(x_ i, m_ {c(i)}) > d_ 2(x_ i) \)，那么 \( x_ i \) 本来就“不太满意”当前的中心点，交换可能带来改变。 为了简化理解，我们可以记住核心公式： 对于一次候选交换 (m_ t, x_ j) ，总代价变化是交换后所有点的距离总和减去交换前的总和。PAM算法通过巧妙利用之前计算的最优和第二优距离，避免了为每次候选交换都重新计算所有点的归属，从而加速了计算。其核心是计算每个点 \( x_ i \) 在这次交换下的“个人代价变化”。 将所有点 \( x_ i \) 的个人代价变化求和，就得到了这次交换 (m_ t, x_ j) 的总代价变化 \( \Delta TC_ {t,j} \)。 选择与执行 ： 在所有候选交换对 \( (m_ t, x_ j) \) 中，找到能使 \( \Delta TC \) 减少最多 （即 \( \Delta TC \) 为负数且绝对值最大）的那一对。 如果存在这样的交换对（即 \( \min_ {t, j} \Delta TC_ {t,j} < 0 \)），则执行这次交换：将中心点 \( m_ t \) 从中心点集合中移除，加入 \( x_ j \)。 如果不存在能使总代价降低的交换（即所有 \( \Delta TC_ {t,j} \ge 0 \)），则算法终止，当前的中心点集合和簇划分即为最终结果。 迭代 ：在每次成功执行交换后，重新执行 分配步骤 ，更新所有点的簇归属和距离信息，然后再次进入 尝试交换与评估步骤 。如此循环，直到无法再通过任何交换降低总代价为止。 第三步：算法特点、复杂度与变体 算法特点 ： 鲁棒性 ：对离群点不敏感，因为中心点是实际存在的数据点。 适用性 ：可以处理任意不相似度矩阵，不要求数据点存在于欧氏空间（只需定义距离）。 确定性 ：给定相同的初始中心点，PAM的结果是确定的。 时间复杂度 ： 交换阶段每次迭代需要计算 \( O(k(n-k)^2) \) 次候选交换的代价。对于每个候选交换，评估所有n个点，因此每次迭代复杂度为 \( O(k(n-k)^2 * n) \)，当k远小于n时，近似为 \( O(kn^3) \)。这使得PAM不适用于大规模数据集。 常见变体 ： CLARA（Clustering LARge Applications） ：不直接在整个数据集上运行PAM，而是多次从数据集中抽取样本，在每个样本上运行PAM，然后选择在 整个数据集 上总代价最小的那组中心点。适用于大规模数据，但结果质量依赖于样本的代表性。 CLARANS（Clustering Large Applications based on RANdomized Search） ：将聚类过程视为在图的节点（即所有可能的中-心点集合）上搜索最优解。它随机地进行邻居搜索（邻居节点指通过交换一个中心点得到的集合），并允许向上移动（接受暂时更差的解）以避免局部最优，类似于随机化搜索。通常比CLARA更有效。 总结 K-中心点聚类（K-Medoids）通过选择实际数据点作为簇代表，增强了聚类对噪声的鲁棒性。其经典实现PAM算法通过构建阶段初始化，并通过迭代的交换阶段（分配、评估所有可能的中心点-非中心点交换）来优化目标函数，直到收敛。尽管PAM的计算成本较高，但其思想清晰，且其变体CLARA和CLARANS使得该算法能应用于更大规模的数据集。理解PAM的关键在于掌握其基于交换的优化策略和代价变化的高效计算方法。