K-中心点聚类（K-medoids Clustering）原理与实现

题目/知识点描述

K-中心点聚类（K-medoids）是一种经典的聚类算法，旨在将数据集划分为K个簇。与K-均值（K-means）类似，但K-中心点选择数据集中实际存在的点（称为“中心点”）作为簇的代表，而不是簇中所有点的均值（质心）。这使得它对异常值（outliers）更为鲁棒，因为均值容易受极端值影响。典型算法是PAM（Partitioning Around Medoids）。

循序渐进讲解

1. 核心思想与动机

• 目标：将n个数据点分配到K个簇中，使得每个点分配到离它最近的中心点所在的簇，并且所有点与其所属簇的中心点之间的距离总和最小。
• 关键差异：K-均值使用“质心”（均值点），这个点可能不是数据集中的实际样本。K-中心点使用“中心点”，是真实的数据点。
• 动机：因为中心点是实际数据点，计算距离时总是基于数据集中实际存在的坐标，使得它对噪声和异常值不敏感。例如，在客户分群中，中心点代表一个典型的真实客户，而不是一个虚构的平均客户。

2. 算法核心概念定义

• 数据点集合：\(D = \{x_1, x_2, ..., x_n\}\)。
• 簇数量K：事先给定的参数。
• 中心点（Medoid）：每个簇中选出的那个代表点，是D中的一个真实点。
• 代价（Cost）：总绝对误差（Total Absolute Error, TA），定义为：
  \(TA = \sum_{i=1}^{n} d(x_i, m_{c_i})\)
  其中，\(d\) 是距离函数（如欧氏距离、曼哈顿距离），\(m_{c_i}\) 是点 \(x_i\) 所属簇的中心点。
• 目标：找到K个中心点，使得代价 \(TA\) 最小化。

3. 经典算法：PAM (Partitioning Around Medoids)

PAM 是最经典的K-中心点算法，分为两个主要阶段：构建阶段 和 交换阶段。

步骤1: 初始化（BUILD 阶段 - 构建阶段）
这个阶段的目标是找到K个初始中心点。

1. 选择一个初始中心点：
   a. 计算每个点 \(i\) 到所有其他点 \(j\) 的距离之和：\(S_i = \sum_{j=1}^{n} d(i, j)\)。
   b. 选择 \(S_i\) 最小的点作为第一个中心点（因为它到其他所有点的总距离最小，是“最中心”的点）。
2. 选择后续中心点（直到选出K个）：
   a. 对于每个非中心点 \(i\)：
   i. 对于每个非中心点 \(j\)：
   - 计算如果将点 \(j\) 与当前已选中心点组合，其代价的“增益”。一种常见方法是计算点 \(j\) 到其最近的中心点与到候选点 \(i\) 的距离差值，但标准PAM-BUILD更直接：
   - 我们想选下一个能最大程度减少总距离的点。简单但计算量大的方法是：将当前已选中心点集合M加上候选点i，然后计算所有非中心点分配到这个新集合后的总代价。但更高效的标准BUILD步骤如下：
   ii. 对于每个非中心点 \(j\)，找到它到当前已选中心点的最小距离 \(d_{j, current}\)。
   iii. 然后计算，如果让 \(j\) 被候选点 \(i\) 服务（即把 \(i\) 当作新中心点），距离变为 \(d(j, i)\)。对每个 \(j\)，比较 \(d_{j, current}\) 和 \(d(j, i)\)，取较小的那个距离，然后对所有 \(j\) 的这个最小距离求和，得到候选中心点 \(i\) 对应的“总代价”。
   b. 选择能使这个“总代价”最小的那个点 \(i\) 作为新的中心点加入集合。
   (注：BUILD阶段在PAM的某些描述中可以简化，比如随机选K个点，但标准PAM的BUILD旨在找到好的初始中心点)

步骤2: 迭代优化（SWAP 阶段 - 交换阶段）
这个阶段通过尝试交换中心点和非中心点来优化聚类结果。

1. 对于当前K个中心点的集合 \(M\)。
2. 对于每一对 \((m, t)\)，其中 \(m\) 是中心点，\(t\) 是非中心点。
3. 计算如果交换 \(m\) 和 \(t\)（即用 \(t\) 替换 \(m\) 作为中心点）会导致的总代价变化 \(\Delta C\)。
   • 计算 \(\Delta C\) 的方法：
     a. 对于每一个非中心点 \(j\)（\(j \neq t\)）：
     - 设 \(d_j\) 是 \(j\) 到其当前最近中心点的距离。
     - 设 \(d_{j}^{new}\) 是 \(j\) 到新的中心点集合（即用 \(t\) 替换了 \(m\) 之后的集合）中最近中心点的距离。
     - 这个点 \(j\) 带来的代价变化是 \(d_{j}^{new} - d_j\)。
     b. 对于点 \(m\) 自身（现在变成了非中心点）：
     - 设 \(d_m\) 是 \(m\) 到其他中心点（排除自身）的最小距离（即 \(m\) 在成为非中心点后归属的簇的距离）。
     - 设 \(d_{m}^{new}\) 是 \(m\) 到新中心点集合（包含 \(t\) 但不含 \(m\) ）的最近距离。
     - 注意，在计算总代价时，点 \(m\) 现在也需要被服务，所以它的代价是 \(d_{m}^{new}\)。
     c. 对于点 \(t\) （现在变成了中心点）：
     - 在代价中，中心点到自身的距离为0，所以它的贡献为0。
     d. 将所有这些变化求和，得到总代价变化 \(\Delta C\)。
4. 找到所有可能的交换对 \((m, t)\) 中，使得 \(\Delta C\) 最小的那一对。如果这个最小的 \(\Delta C\) 是负数（意味着总代价能降低），那么就执行这次交换：用 \(t\) 替换 \(m\) 作为中心点。
5. 重复步骤2-4，直到没有任何交换能够降低总代价（即 \(\Delta C\) 的最小值 >= 0），算法收敛。

4. 算法复杂度与优化

• 时间复杂度：PAM 的每次迭代（SWAP阶段）需要检查 O(K(n-K)) 对交换，对每一对需要评估所有 n-K 个非中心点，所以单次迭代复杂度是 O(K(n-K)²)。对于大数据集，这非常昂贵。
• 优化算法 CLARA 和 CLARANS：
  • CLARA (Clustering Large Applications)：不从整个数据集找中心点，而是采样多个子数据集，对每个子集应用PAM，然后选其中最好的结果。速度更快，但结果质量依赖于采样。
  • CLARANS (Clustering Large Applications based on RANdomized Search)：引入随机搜索。它不评估所有可能的交换对，而是随机选择一个中心点和一个非中心点尝试交换。如果交换能降低成本，就接受并继续；否则尝试一定次数后终止。它在效率和效果间取得更好平衡，是更常用的K-中心点算法。

5. 实现要点与示例

实现伪代码（PAM核心逻辑）：

输入：数据集D，簇数K
输出：K个中心点，聚类标签

1. 初始化：从D中选K个点作为初始中心点（可使用BUILD或随机选择）。
2. 为所有点分配簇：将每个点分配到离它最近的中心点所属的簇。
3. 计算当前总代价TA_current = 所有点到其中心点的距离之和。
4. 重复：
    best_delta = 0
    best_swap = None
    for 每个中心点m in M:
        for 每个非中心点t in (D - M):
            // 计算交换(m,t)产生的代价变化ΔC
            delta = 0
            for 每个点j in D:
                if j == t: continue // 中心点到自身距离为0
                d_old = j到当前所属簇中心点的距离
                d_new = j到用t替换m后所属新簇中心点的距离
                delta += (d_new - d_old)
            if delta < best_delta:
                best_delta = delta
                best_swap = (m, t)
    if best_delta < 0:
        执行交换：M = (M - {best_swap.m}) ∪ {best_swap.t}
        根据新中心点重新分配所有点的簇标签
        更新TA_current += best_delta
    else:
        break // 无法再优化，退出循环
5. 返回中心点集合M和每个点的簇标签。

示例（简化）：
假设有5个点坐标：[A(0,0), B(0,1), C(4,4), D(5,5), E(100,100)]，K=2。

• K-均值可能选出质心 ≈ (0, 0.5) 和 (36, 36)，受E点（异常值）严重影响。
• K-中心点（PAM）初始可能选A和C。计算交换，发现用B替换A可能更优。最终稳定后，中心点可能是B和D（或C），E点会被单独归到离它较近的簇（可能是D所在的簇），但中心点D是真实点，不会被E拉到(36,36)这样的虚构位置，从而对E这个异常值不敏感。

总结

K-中心点聚类通过选取真实数据点作为簇中心，相比K-均值对异常值更鲁棒。PAM算法通过交换中心点与非中心点来迭代优化，但计算成本高。其优化变种（如CLARANS）使其能应用于更大规模数据。核心权衡是：鲁棒性提高，但计算效率降低。