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 的核心差异

1.3 工程与统计中的应用场景

• 异常值较多的数据
• 非欧氏距离（编辑距离、图距离）
• 小样本高可靠性聚类
• 生物信息学
• 社交网络分析
• 推荐系统中的代表点选择

二、项目需求详细介绍

2.1 功能性需求

本项目目标是：

👉 使用“传输 + 交换”策略，在 C++ 中从零实现 K-Medoids 聚类算法

需要支持：

1. 任意维度的数值向量
2. 指定聚类数 K
3. 明确区分：
   • 样本分配（Relocation）
   • 中心交换（Swap）
4. 输出：
   • 每个样本的簇标签
   • 每个簇的 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 非功能性需求

1. 不依赖第三方机器学习库
2. 使用标准 C++ 数据结构
3. 算法逻辑清晰、可教学
4. 可控的时间复杂度
5. 易于扩展（如任意距离度量）

2.3 适用规模

• 中小规模数据集（n ≤ 几千）
• 教学、科研、统计实验
• 需要高鲁棒性的工程场景

三、相关技术详细介绍

3.2 传输（Relocation）步骤

• 固定当前 medoids
• 将每个样本分配给最近的 medoid
• 这是一个“最近邻”问题

3.3 交换（Swap）步骤

• 尝试用任意一个非 medoid 点替换某个 medoid
• 重新计算总代价
• 若代价下降，则接受交换

📌 这是 K-Medoids 的核心，也是计算最昂贵的部分。

3.4 PAM（Partitioning Around Medoids）

经典 K-Medoids 实现即 PAM 算法：

1. BUILD：初始化 medoids
2. 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

• 提供样本间距离计算
• 可替换为任意自定义距离

七、项目详细总结

通过本项目，我们：

1. 系统实现了基于“传输 + 交换”的聚类算法
2. 深刻理解了 K-Medoids 与 K-Means 的本质差异
3. 构建了一个鲁棒、可解释的聚类模块
4. 为复杂聚类与统计推断打下基础

该实现：

• 对异常值鲁棒
• 中心可解释
• 工程可控
• 教学价值极高

八、项目常见问题及解答

Q1：为什么 K-Medoids 比 K-Means 慢？

A：因为 Swap 阶段需要大量代价评估。

Q2：什么时候应该用 K-Medoids？

A：当你关心鲁棒性、中心可解释性或非欧氏距离时。

Q3：是否适合大规模数据？

A：不适合，需要 CLARA / CLARANS 等改进算法。

九、扩展方向与性能优化

1. CLARA（基于采样的 K-Medoids）
2. CLARANS（随机化 Swap）
3. 支持任意距离矩阵输入
4. 并行化 Swap 评估
5. 与异常检测结合使用