一、项目背景详细介绍
在前面的聚类算法实现中,我们已经系统地介绍并实现了 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; }


