C++ 基于传输与交换的 K-Medoids 聚类算法实现

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. 与异常检测结合使用