一、引言

        K-Means聚类是机器学习中最经典的无监督学习算法之一，它以其简单性和高效性在数据挖掘、图像分割、客户分群等领域广泛应用。本文将详细介绍如何使用C++从零开始实现K-Means聚类算法。

        K-Means算法原理：

        K-Means算法的核心思想是将数据点划分为K个簇，使得每个数据点都属于离它最近的质心（簇中心）对应的簇，从而让簇内数据点尽可能相似，簇间数据点尽可能不同。

        算法步骤：

• 初始化：随机选择K个数据点作为初始质心
• 分配阶段：将每个数据点分配到距离最近的质心所在的簇
• 更新阶段：重新计算每个簇的质心（该簇所有点的均值）
• 迭代：重复步骤2-3，直到质心不再变化或达到最大迭代次数

二、C++实现核心代码

2.1 数据结构设计

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

class KMeans {
private:
    int k;                                  // 簇的数量
    int maxIterations;                      // 最大迭代次数
    double tolerance;                       // 收敛阈值
    std::vector<std::vector<double>> centroids; // 质心坐标
    
public:
    KMeans(int k, int maxIter = 100, double tol = 1e-4) 
        : k(k), maxIterations(maxIter), tolerance(tol) {}
    
    // 计算两点之间的欧氏距离
    double euclideanDistance(const std::vector<double>& a, 
                           const std::vector<double>& b) {
        double sum = 0.0;
        for (size_t i = 0; i < a.size(); ++i) {
            sum += std::pow(a[i] - b[i], 2);
        }
        return std::sqrt(sum);
    }

2.2 核心算法实现

    // 拟合数据并进行聚类
    std::vector<int> fit(const std::vector<std::vector<double>>& data) {
        if (data.empty()) return {};
        
        int n = data.size();
        int dim = data[0].size();
        
        // 1. 初始化质心 - 随机选择K个数据点
        initializeCentroids(data);
        
        std::vector<int> labels(n, -1);
        std::vector<std::vector<double>> oldCentroids;
        int iteration = 0;
        
        do {
            oldCentroids = centroids;
            
            // 2. 分配阶段：为每个数据点分配最近的簇
            for (int i = 0; i < n; ++i) {
                double minDist = std::numeric_limits<double>::max();
                int bestCluster = -1;
                
                // 寻找最近的质心
                for (int j = 0; j < k; ++j) {
                    double dist = euclideanDistance(data[i], centroids[j]);
                    if (dist < minDist) {
                        minDist = dist;
                        bestCluster = j;
                    }
                }
                labels[i] = bestCluster;
            }
            
            // 3. 更新阶段：重新计算质心
            updateCentroids(data, labels);
            
            iteration++;
            
        } while (!hasConverged(oldCentroids) && iteration < maxIterations);
        
        return labels;
    }

2.3 初始化质心

private:
    // 随机初始化质心
    void initializeCentroids(const std::vector<std::vector<double>>& data) {
        centroids.clear();
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, data.size() - 1);
        
        // 随机选择K个不重复的数据点作为初始质心
        std::vector<int> indices;
        while (centroids.size() < k) {
            int idx = dis(gen);
            // 避免重复选择
            if (std::find(indices.begin(), indices.end(), idx) == indices.end()) {
                indices.push_back(idx);
                centroids.push_back(data[idx]);
            }
        }
    }

2.4 质心更新和收敛判断

    // 更新质心坐标
    void updateCentroids(const std::vector<std::vector<double>>& data, 
                        const std::vector<int>& labels) {
        std::vector<std::vector<double>> newCentroids(k, 
            std::vector<double>(data[0].size(), 0.0));
        std::vector<int> clusterSizes(k, 0);
        
        // 计算每个簇的数据点总和
        for (size_t i = 0; i < data.size(); ++i) {
            int cluster = labels[i];
            for (size_t j = 0; j < data[i].size(); ++j) {
                newCentroids[cluster][j] += data[i][j];
            }
            clusterSizes[cluster]++;
        }
        
        // 计算均值得到新质心
        for (int i = 0; i < k; ++i) {
            if (clusterSizes[i] > 0) {
                for (size_t j = 0; j < newCentroids[i].size(); ++j) {
                    newCentroids[i][j] /= clusterSizes[i];
                }
            } else {
                // 如果簇为空，保持原质心
                newCentroids[i] = centroids[i];
            }
        }
        
        centroids = newCentroids;
    }
    
    // 判断算法是否收敛
    bool hasConverged(const std::vector<std::vector<double>>& oldCentroids) {
        for (int i = 0; i < k; ++i) {
            double dist = euclideanDistance(centroids[i], oldCentroids[i]);
            if (dist > tolerance) {
                return false;
            }
        }
        return true;
    }

2.5 使用示例

// 示例：使用K-Means对二维数据进行聚类
int main() {
    // 创建一些示例数据
    std::vector<std::vector<double>> data = {
        {1.0, 1.0}, {1.5, 2.0}, {3.0, 4.0}, 
        {5.0, 7.0}, {3.5, 5.0}, {4.5, 5.0},
        {1.5, 1.0}, {2.0, 1.5}, {5.0, 6.0}
    };
    
    // 创建K-Means聚类器，设置K=3
    KMeans kmeans(3);
    
    // 执行聚类
    std::vector<int> labels = kmeans.fit(data);
    
    // 输出聚类结果
    std::cout << "聚类结果:" << std::endl;
    for (size_t i = 0; i < data.size(); ++i) {
        std::cout << "数据点 (" << data[i][0] << ", " << data[i][1] 
                  << ") 属于簇 " << labels[i] << std::endl;
    }
    
    return 0;
}

三、注意事项

3.1 K值选择问题

        K-Means需要预先指定簇的数量K，选择合适的K值至关重要：

• 肘部法则：绘制不同K值对应的误差平方和（SSE），选择拐点
• 轮廓系数：衡量簇内紧密度和簇间分离度
• 业务理解：基于实际应用场景确定K值

3.2 空簇处理

        在更新质心时可能出现空簇，需要特殊处理：

• 重新初始化该簇的质心
• 选择距离当前质心最远的点作为新质心
• 选择SSE贡献最大的点作为新质心

3.3 局限性

• 对非球形簇效果不佳
• 对噪声和离群点敏感
• 初始质心选择影响最终结果

四、总结

        通过这个C++实现，我们完整地展示了K-Means聚类算法的核心思想和实现细节。K-Means虽然简单，但在实际应用中需要注意数据预处理、参数选择和算法优化等问题。

关键要点总结：

• 核心思想：通过迭代优化质心位置来最小化簇内距离
• 实现重点：质心初始化、数据点分配、质心更新

五、面试手撕

        考虑到面试手撕时可能只要写出核心代码体现思路就行，下面给出一个稍显粗糙的版本。

#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>

// 定义点的类型为double类型的向量（表示多维权重特征）
using Point = std::vector<double>;

/**
 * 计算两点之间的欧氏距离平方
 * （使用平方避免开方运算，不影响距离大小的相对比较，提升效率）
 * @param a 第一个点
 * @param b 第二个点
 * @return 距离的平方值
 */
double distSq(const Point& a, const Point& b) {
    double d = 0;
    // 累加每个维度上的差值平方
    for (size_t i = 0; i < a.size(); ++i) {
        d += (a[i] - b[i]) * (a[i] - b[i]);
    }
    return d;
}

/**
 * KMeans聚类核心函数
 * @param data 输入数据集（每个元素是一个多维权重特征向量）
 * @param k 目标聚类数量
 * @param maxIter 最大迭代次数（防止无限循环）
 * @return 每个样本对应的聚类标签（与输入数据顺序一致）
 */
std::vector<int> kmeans(const std::vector<Point>& data, int k, int maxIter = 50) {
    int n = data.size();       // 样本总数
    int dim = data[0].size();  // 每个样本的特征维度
    std::vector<int> labels(n, 0);  // 存储每个样本的聚类标签（初始都为0）
    std::vector<Point> centroids(k); // 存储k个聚类中心（质心）

    // 1. 初始化质心：从数据中随机选择k个点作为初始聚类中心
    std::srand(123);  // 固定随机种子，保证结果可复现（实际应用可去掉固定种子）
    for (int i = 0; i < k; ++i) {
        // 随机选择一个样本索引，将该样本作为初始质心
        centroids[i] = data[rand() % n];
    }

    // 2. 迭代优化聚类中心（核心循环）
    for (int iter = 0; iter < maxIter; ++iter) {
        bool changed = false;  // 标记本轮迭代中标签是否有变化（用于判断收敛）

        // 3. 分配阶段：将每个样本分配到最近的质心对应的聚类
        for (int i = 0; i < n; ++i) {
            int bestCluster = 0;  // 记录距离当前样本最近的聚类索引
            // 计算样本到第一个质心的距离
            double minDist = distSq(data[i], centroids[0]);

            // 遍历其他质心，找到最近的聚类
            for (int c = 1; c < k; ++c) {
                double currentDist = distSq(data[i], centroids[c]);
                if (currentDist < minDist) {
                    minDist = currentDist;
                    bestCluster = c;  // 更新最近聚类索引
                }
            }

            // 如果样本的聚类标签发生变化，更新标签并标记状态
            if (labels[i] != bestCluster) {
                labels[i] = bestCluster;
                changed = true;
            }
        }

        // 如果所有样本的标签都未变化，说明收敛，提前退出迭代
        if (!changed) {
            break;
        }

        // 4. 更新阶段：计算新的聚类中心（每个聚类的均值）
        std::vector<Point> newCentroids(k, Point(dim, 0.0));  // 新质心（初始化为0）
        std::vector<int> clusterCounts(k, 0);                 // 每个聚类的样本数量（初始化为0）

        // 累加每个聚类中所有样本的特征值
        for (int i = 0; i < n; ++i) {
            int cluster = labels[i];  // 当前样本所属的聚类
            // 累加该样本的每个维度特征到对应聚类的新质心
            for (int d = 0; d < dim; ++d) {
                newCentroids[cluster][d] += data[i][d];
            }
            clusterCounts[cluster]++;  // 对应聚类的样本数+1
        }

        // 计算均值：将累加的特征值除以样本数，得到新质心
        for (int c = 0; c < k; ++c) {
            // 每个维度都取均值
            for (int d = 0; d < dim; ++d) {
                newCentroids[c][d] /= clusterCounts[c];
            }
        }

        // 更新质心为新计算的质心
        centroids = newCentroids;
    }

    // 返回最终的聚类标签
    return labels;
}