66、C++项目实战：K-means聚类算法

K-means，说白了就是“物以类聚，人以群分”。

你有一堆数据点，想把它分成K个簇，让每个点离自己簇的中心最近。这就是K-means干的事。我当年第一次接触这个算法，是在做用户行为画像的时候——要把几万个用户按消费习惯分组，那时候手写了一个K-means，跑出来的效果还挺惊艳。

算法核心思想

K-means的流程其实很简单，就四步：

  1. 初始化：随机选K个点作为初始质心
  2. 分配：每个点归到最近的质心
  3. 更新：重新计算每个簇的质心
  4. 迭代：重复2和3，直到质心不再变化

嗯，这里要注意——初始质心的选择很关键。选不好，可能收敛到局部最优。我踩过这个坑，后面会讲怎么避。

C++实现：数据结构设计

先定义点、质心和簇的结构。我个人习惯用模板，方便以后扩展维度。

#include <vector>
#include <cmath>
#include <limits>
#include <random>

// 数据点，支持任意维度
template<typename T>
struct Point {
    std::vector<T> coords;
    
    Point() = default;
    Point(std::initializer_list<T> list) : coords(list) {}
    
    // 欧氏距离平方（省去开根号，提高性能）
    T squaredDistance(const Point& other) const {
        T sum = 0;
        for (size_t i = 0; i < coords.size(); ++i) {
            T diff = coords[i] - other.coords[i];
            sum += diff * diff;
        }
        return sum;
    }
};

// 质心：继承自Point，额外带一个ID
struct Centroid : public Point<double> {
    int id;
    Centroid(int id, std::initializer_list<double> list) 
        : Point(list), id(id) {}
};

// 簇：包含质心和归属点索引
struct Cluster {
    Centroid centroid;
    std::vector<int> pointIndices;
    
    Cluster(const Centroid& c) : centroid(c) {}
};

为什么用平方距离？因为开根号是计算密集型操作，而且比较距离大小不需要真实距离，平方就够了。我在项目中处理百万级点云时，这个优化能省下30%的时间。

核心算法实现

接下来是K-means的主循环。我习惯把逻辑拆成几个小函数，这样好调试。

class KMeans {
private:
    int k;
    int maxIter;
    double tolerance;  // 质心变化阈值
    std::vector<Point<double>> data;
    std::vector<Cluster> clusters;
    
public:
    KMeans(int k, int maxIter = 100, double tol = 1e-4)
        : k(k), maxIter(maxIter), tolerance(tol) {}
    
    void fit(const std::vector<Point<double>>& points) {
        data = points;
        initializeCentroids();
        
        for (int iter = 0; iter < maxIter; ++iter) {
            // 1. 分配每个点到最近的质心
            assignClusters();
            
            // 2. 更新质心
            bool converged = updateCentroids();
            
            if (converged) {
                std::cout << "收敛于第 " << iter + 1 << " 次迭代\n";
                break;
            }
        }
    }
    
private:
    void initializeCentroids() {
        // 随机选择K个点作为初始质心
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, data.size() - 1);
        
        for (int i = 0; i < k; ++i) {
            int idx = dis(gen);
            clusters.emplace_back(Centroid(i, {data[idx].coords[0], data[idx].coords[1]}));
        }
    }
    
    void assignClusters() {
        // 清空每个簇的点列表
        for (auto& cluster : clusters) {
            cluster.pointIndices.clear();
        }
        
        for (int i = 0; i < data.size(); ++i) {
            double minDist = std::numeric_limits<double>::max();
            int bestCluster = 0;
            
            for (int j = 0; j < clusters.size(); ++j) {
                double dist = data[i].squaredDistance(clusters[j].centroid);
                if (dist < minDist) {
                    minDist = dist;
                    bestCluster = j;
                }
            }
            
            clusters[bestCluster].pointIndices.push_back(i);
        }
    }
    
    bool updateCentroids() {
        bool converged = true;
        
        for (auto& cluster : clusters) {
            if (cluster.pointIndices.empty()) continue;
            
            // 计算新质心（均值）
            Centroid oldCentroid = cluster.centroid;
            Centroid newCentroid(oldCentroid.id, {0.0, 0.0});
            
            for (int idx : cluster.pointIndices) {
                newCentroid.coords[0] += data[idx].coords[0];
                newCentroid.coords[1] += data[idx].coords[1];
            }
            
            size_t n = cluster.pointIndices.size();
            newCentroid.coords[0] /= n;
            newCentroid.coords[1] /= n;
            
            // 检查是否收敛
            double shift = oldCentroid.squaredDistance(newCentroid);
            if (shift > tolerance) {
                converged = false;
            }
            
            cluster.centroid = newCentroid;
        }
        
        return converged;
    }
};

关键点：tolerance参数控制收敛精度。设得太小（比如1e-8）会导致迭代次数过多；设得太大（比如0.1）可能提前停止，聚类效果差。我一般用1e-4，效果不错。

K值怎么选？

这是K-means里最让人头疼的问题。K值选不对，聚类结果就是一团糟。

常用的方法是肘部法则：

  • 跑不同K值的K-means
  • 计算每个K下的总误差（SSE，即各点到质心距离的平方和）
  • 画一条K-SSE曲线
  • 找曲线“拐弯”的那个点

举个例子：

// 计算总误差（SSE）
double computeSSE(const std::vector<Point<double>>& data, 
                  const std::vector<Cluster>& clusters) {
    double sse = 0.0;
    for (const auto& cluster : clusters) {
        for (int idx : cluster.pointIndices) {
            sse += data[idx].squaredDistance(cluster.centroid);
        }
    }
    return sse;
}

// 尝试K从1到10
for (int k = 1; k <= 10; ++k) {
    KMeans km(k);
    km.fit(data);
    double sse = computeSSE(data, km.getClusters());
    std::cout << "K=" << k << " SSE=" << sse << "\n";
}

你想想看，如果K=1，SSE肯定最大。随着K增大，SSE会下降。但到某个点之后，下降速度会变慢——那个点就是“肘部”。

小技巧：如果肘部不明显，可以试试轮廓系数（Silhouette Score）。它同时考虑了簇内紧密度和簇间分离度，比单纯看SSE更可靠。

避坑指南：初始质心的选择

我曾经因为随机初始化，连续三次跑出不同的聚类结果。客户看了直摇头。

后来我改用K-means++初始化策略：

  1. 随机选第一个质心
  2. 对每个点，计算它到最近质心的距离D(x)
  3. 以概率正比于D(x)²选择下一个质心
  4. 重复直到选出K个质心

这样选出来的质心分布更均匀，收敛更快，结果也更稳定。

void initializeKMeansPlusPlus() {
    std::random_device rd;
    std::mt19937 gen(rd());
    
    // 随机选第一个质心
    std::uniform_int_distribution<> dis(0, data.size() - 1);
    int firstIdx = dis(gen);
    clusters.emplace_back(Centroid(0, {data[firstIdx].coords[0], data[firstIdx].coords[1]}));
    
    // 选剩下的K-1个
    for (int i = 1; i < k; ++i) {
        std::vector<double> weights(data.size());
        double totalWeight = 0.0;
        
        for (int j = 0; j < data.size(); ++j) {
            double minDist = std::numeric_limits<double>::max();
            for (const auto& cluster : clusters) {
                double dist = data[j].squaredDistance(cluster.centroid);
                minDist = std::min(minDist, dist);
            }
            weights[j] = minDist;
            totalWeight += minDist;
        }
        
        // 按权重随机选择
        std::uniform_real_distribution<> realDis(0.0, totalWeight);
        double threshold = realDis(gen);
        double cumulative = 0.0;
        int selectedIdx = 0;
        
        for (int j = 0; j < data.size(); ++j) {
            cumulative += weights[j];
            if (cumulative >= threshold) {
                selectedIdx = j;
                break;
            }
        }
        
        clusters.emplace_back(Centroid(i, {data[selectedIdx].coords[0], data[selectedIdx].coords[1]}));
    }
}

注意：K-means++虽然好，但计算权重的过程需要遍历所有点，如果数据量很大（比如上百万），这一步会有点慢。这时候可以考虑Mini-Batch K-means，每次只取一部分数据更新质心。

K-means的局限性

说实话，K-means不是万能的。它有这几个硬伤：

问题 原因 怎么办
只能处理球形簇 基于欧氏距离，假设簇是凸的 换DBSCAN或谱聚类
对异常点敏感 均值会被极端值拉偏 预处理时剔除异常点，或用K-medoids
需要指定K值 实际场景中K往往未知 肘部法则 + 业务经验
结果不稳定 依赖初始质心 多次运行取最优，或用K-means++

我在做图像分割时遇到过一个问题——K-means把天空和湖水分到了同一个簇，因为它们颜色相近。后来加了纹理特征才解决。所以特征工程也很重要。

完整示例：二维点聚类

最后给一个完整的main函数，跑起来就能看到效果。

int main() {
    // 生成测试数据：三个簇
    std::vector<Point<double>> points;
    
    // 簇1：中心(2, 2)
    for (int i = 0; i < 30; ++i) {
        points.emplace_back(Point<double>{2.0 + rand()%100/100.0, 2.0 + rand()%100/100.0});
    }
    // 簇2：中心(8, 3)
    for (int i = 0; i < 30; ++i) {
        points.emplace_back(Point<double>{8.0 + rand()%100/100.0, 3.0 + rand()%100/100.0});
    }
    // 簇3：中心(5, 8)
    for (int i = 0; i < 30; ++i) {
        points.emplace_back(Point<double>{5.0 + rand()%100/100.0, 8.0 + rand()%100/100.0});
    }
    
    KMeans km(3);
    km.fit(points);
    
    auto clusters = km.getClusters();
    for (const auto& cluster : clusters) {
        std::cout << "簇 " << cluster.centroid.id 
                  << " 质心: (" << cluster.centroid.coords[0] 
                  << ", " << cluster.centroid.coords[1] 
                  << ") 包含 " << cluster.pointIndices.size() 
                  << " 个点\n";
    }
    
    return 0;
}

K-means核心流程

下面这张图把整个流程串起来了，看一眼就明白。

K-means 聚类算法核心流程 输入数据 + K值 初始化K个质心（K-means++） 分配每个点到最近质心 更新质心（计算均值） 收敛？ 否 是 输出聚类结果

说白了，K-means就是“选中心、分点、再选中心”的循环。实现不难，但用好它需要经验。我建议你从二维数据开始练手，把可视化加上，看着点一点点聚成簇，那种感觉很有成就感。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →