C++：使用传输和交换实现聚类算法（附带源码）
一、项目背景详细介绍
在前面的聚类算法实现中，我们已经系统地介绍并实现了 K-Means 聚类算法。K-Means 以其简单高效著称，但在真实工程与统计建模中，它存在一些先天局限性：
- 对异常值（Outliers）极其敏感
- 必须使用“均值”作为中心（不一定是实际样本）
- 仅适用于欧氏空间
- 对非凸分布表现较差
在许多实际应用场景中，我们更希望：
聚类中心一定是“真实样本点”，并且对异常值更鲁棒。
这正是 K-Medoids 聚类算法（也称 PAM，Partitioning Around Medoids）的出发点。
1.1 什么是“传输”和“交换”思想？
K-Medoids 并不是通过“求均值”来更新中心，而是通过：
- 传输（Relocation）：
将样本重新分配到最近的中心（medoid） - 交换（Swap）：
尝试用“非中心点”替换当前中心点，看是否能降低整体代价函数
📌 一句话概括：
K-Medoids = “分配（传输） + 中心交换（Swap）” 的组合优化算法。
1.2 K-Medoids 与 K-Means 的核心差异
| 维度 | K-Means | K-Medoids |
|---|---|---|
| 中心 | 均值（虚拟点） | 实际样本 |
| 距离 | 通常欧氏 | 任意距离 |
| 鲁棒性 | 差 | 强 |
| 计算量 | 较低 | 较高 |
| 工程适用性 | 连续数据 | 离散 / 非欧氏 |
1.3 工程与统计中的应用场景
- 异常值较多的数据
- 非欧氏距离（编辑距离、图距离）
- 小样本高可靠性聚类
- 生物信息学
- 社交网络分析
- 推荐系统中的代表点选择
二、项目需求详细介绍
2.1 功能性需求
本项目目标是：
👉 使用“传输 + 交换”策略，在 C++ 中从零实现 K-Medoids 聚类算法
需要支持：
- 任意维度的数值向量
- 指定聚类数 K
- 明确区分：
- 样本分配（Relocation）
- 中心交换（Swap）
- 输出：
- 每个样本的簇标签
- 每个簇的 medoid 索引
核心接口示例：
class KMedoids { public: KMedoids(int k, int maxIter); void fit(const std::vector<std::vector<double>>& data); const std::vector<int>& labels() const; const std::vector<int>& medoids() const; };
2.2 非功能性需求
- 不依赖第三方机器学习库
- 使用标准 C++ 数据结构
- 算法逻辑清晰、可教学
- 可控的时间复杂度
- 易于扩展（如任意距离度量）
2.3 适用规模
- 中小规模数据集（n ≤ 几千）
- 教学、科研、统计实验
- 需要高鲁棒性的工程场景
三、相关技术详细介绍
3.2 传输（Relocation）步骤
- 固定当前 medoids
- 将每个样本分配给最近的 medoid
- 这是一个“最近邻”问题
3.3 交换（Swap）步骤
- 尝试用任意一个非 medoid 点替换某个 medoid
- 重新计算总代价
- 若代价下降，则接受交换
📌 这是 K-Medoids 的核心，也是计算最昂贵的部分。
3.4 PAM（Partitioning Around Medoids）
经典 K-Medoids 实现即 PAM 算法：
- BUILD：初始化 medoids
- SWAP：迭代进行中心交换优化
本项目采用教学友好的简化 PAM 流程。
四、实现思路详细介绍
4.1 总体算法流程
随机选择 K 个样本作为初始 medoids repeat: 1. 传输（Relocation） - 将每个样本分配到最近的 medoid 2. 交换（Swap） - 对每个 medoid m: 对每个非 medoid 点 x: 尝试用 x 替换 m 若总代价下降，执行交换 until 无交换发生 或 达到最大迭代次数
4.2 距离度量设计
本项目使用欧氏距离，但代码结构允许轻松替换为：
- Manhattan 距离
- 编辑距离
- 自定义相似度
4.3 时间复杂度说明
- 传输步骤：O(nK)
- 交换步骤：O(K(n−K)n)
📌 因此不适合超大规模数据，但非常适合教学与中小规模工程。
五、完整实现代码
/****************************************************** * File: kmedoids.h ******************************************************/ #ifndef KMEDOIDS_H #define KMEDOIDS_H #include <vector> class KMedoids { public: KMedoids(int k, int maxIterations = 100); void fit(const std::vector<std::vector<double>>& data); const std::vector<int>& labels() const; const std::vector<int>& medoids() const; private: int K; int maxIter; std::vector<int> labelVec; // 每个样本的簇标签 std::vector<int> medoidIdx; // medoid 在数据中的索引 double distance(const std::vector<double>& a, const std::vector<double>& b); double totalCost(const std::vector<std::vector<double>>& data, const std::vector<int>& medoids); }; #endif /****************************************************** * File: kmedoids.cpp ******************************************************/ #include "kmedoids.h" #include <random> #include <limits> #include <stdexcept> #include <cmath> #include <algorithm> KMedoids::KMedoids(int k, int maxIterations) : K(k), maxIter(maxIterations) { if (K <= 0) throw std::invalid_argument("K must be positive"); } double KMedoids::distance(const std::vector<double>& a, const std::vector<double>& b) { double sum = 0.0; for (size_t i = 0; i < a.size(); ++i) { double d = a[i] - b[i]; sum += d * d; } return std::sqrt(sum); } double KMedoids::totalCost(const std::vector<std::vector<double>>& data, const std::vector<int>& medoids) { double cost = 0.0; for (size_t i = 0; i < data.size(); ++i) { double minDist = std::numeric_limits<double>::max(); for (int m : medoids) { double d = distance(data[i], data[m]); if (d < minDist) minDist = d; } cost += minDist; } return cost; } void KMedoids::fit(const std::vector<std::vector<double>>& data) { if (data.empty()) throw std::invalid_argument("Empty dataset"); int n = static_cast<int>(data.size()); labelVec.assign(n, 0); /* 随机初始化 medoids */ std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dist(0, n - 1); medoidIdx.clear(); while ((int)medoidIdx.size() < K) { int idx = dist(gen); if (std::find(medoidIdx.begin(), medoidIdx.end(), idx) == medoidIdx.end()) medoidIdx.push_back(idx); } /* 主迭代过程 */ for (int iter = 0; iter < maxIter; ++iter) { /* ---------- 传输（Relocation） ---------- */ for (int i = 0; i < n; ++i) { double minDist = std::numeric_limits<double>::max(); int best = 0; for (int k = 0; k < K; ++k) { double d = distance(data[i], data[medoidIdx[k]]); if (d < minDist) { minDist = d; best = k; } } labelVec[i] = best; } /* ---------- 交换（Swap） ---------- */ bool improved = false; double currentCost = totalCost(data, medoidIdx); for (int k = 0; k < K; ++k) { for (int i = 0; i < n; ++i) { if (std::find(medoidIdx.begin(), medoidIdx.end(), i) != medoidIdx.end()) continue; std::vector<int> candidate = medoidIdx; candidate[k] = i; double newCost = totalCost(data, candidate); if (newCost < currentCost) { medoidIdx = candidate; currentCost = newCost; improved = true; } } } if (!improved) break; } } const std::vector<int>& KMedoids::labels() const { return labelVec; } const std::vector<int>& KMedoids::medoids() const { return medoidIdx; } /****************************************************** * File: main.cpp ******************************************************/ #include <iostream> #include "kmedoids.h" int main() { std::vector<std::vector<double>> data = { {1.0, 2.0}, {1.2, 1.9}, {0.8, 2.1}, {8.0, 8.0}, {8.2, 7.9}, {7.9, 8.1} }; KMedoids model(2, 100); model.fit(data); std::cout << "Cluster labels:\n"; for (int l : model.labels()) std::cout << l << " "; std::cout << "\n"; std::cout << "Medoid indices:\n"; for (int m : model.medoids()) std::cout << m << " "; std::cout << "\n"; return 0; } 六、代码详细解读（仅解读方法作用）
6.1 fit
- 实现完整的 PAM 聚类流程
- 包含传输与交换两个核心阶段
- 支持提前收敛
6.2 totalCost
- 计算当前 medoids 下的总代价函数
- 是 Swap 判断是否接受的依据
6.3 distance
- 提供样本间距离计算
- 可替换为任意自定义距离
七、项目详细总结
通过本项目，我们：
- 系统实现了基于“传输 + 交换”的聚类算法
- 深刻理解了 K-Medoids 与 K-Means 的本质差异
- 构建了一个鲁棒、可解释的聚类模块
- 为复杂聚类与统计推断打下基础
该实现：
- 对异常值鲁棒
- 中心可解释
- 工程可控
- 教学价值极高
八、项目常见问题及解答
Q1：为什么 K-Medoids 比 K-Means 慢？
A：因为 Swap 阶段需要大量代价评估。
Q2：什么时候应该用 K-Medoids？
A：当你关心鲁棒性、中心可解释性或非欧氏距离时。
Q3：是否适合大规模数据？
A：不适合，需要 CLARA / CLARANS 等改进算法。
九、扩展方向与性能优化
- CLARA（基于采样的 K-Medoids）
- CLARANS（随机化 Swap）
- 支持任意距离矩阵输入
- 并行化 Swap 评估
- 与异常检测结合使用
