k-means聚类算法c++

### 关于C++实现K-Means聚类算法 K-Means是一种常用的无监督学习算法，用于将数据划分为若干个簇。以下是基于C++实现K-Means的核心逻辑及其代码示例。 #### 初始化质心 在K-Means算法中，初始质心的选择至关重要。可以通过随机选取数据点作为初始质心或者采用更复杂的策略来优化收敛速度[^2]。 ```cpp // 随机初始化质心函数 std::vector<std::vector<double>> initializeCentroids(const std::vector<std::vector<double>>& X, int K) { std::vector<std::vector<double>> centroids(K); std::set<int> used_indices; while (used_indices.size() < K) { int rand_idx = rand() % X.size(); if (used_indices.find(rand_idx) == used_indices.end()) { centroids.push_back(X[rand_idx]); used_indices.insert(rand_idx); } } return centroids; } ``` #### 距离计算与分配最近质心 对于每个数据点，找到与其距离最近的质心，并将其分配到对应的簇中。通常使用欧几里得距离进行度量。 ```cpp double euclideanDistance(const std::vector<double>& a, const std::vector<double>& b) { double dist = 0.0; for (size_t i = 0; i < a.size(); ++i) { dist += pow(a[i] - b[i], 2); } return sqrt(dist); } std::vector<int> assignClosestCentroid(const std::vector<std::vector<double>>& X, const std::vector<std::vector<double>>& centroids) { std::vector<int> idx(X.size()); for (size_t i = 0; i < X.size(); ++i) { double min_dist = DBL_MAX; int closest_centroid = -1; for (size_t j = 0; j < centroids.size(); ++j) { double distance = euclideanDistance(X[i], centroids[j]); if (distance < min_dist) { min_dist = distance; closest_centroid = j; } } idx[i] = closest_centroid; } return idx; } ``` #### 更新质心位置 根据当前分配情况重新计算各簇的新质心位置[^2]。 ```cpp std::vector<std::vector<double>> updateCentroids(const std::vector<std::vector<double>>& X, const std::vector<int>& idx, int K) { std::vector<std::vector<double>> new_centroids(K, std::vector<double>(X[0].size(), 0)); std::vector<int> counts(K, 0); for (size_t i = 0; i < X.size(); ++i) { int cluster_index = idx[i]; for (size_t d = 0; d < X[0].size(); ++d) { new_centroids[cluster_index][d] += X[i][d]; } counts[cluster_index]++; } for (int k = 0; k < K; ++k) { if (counts[k] != 0) { for (size_t d = 0; d < X[0].size(); ++d) { new_centroids[k][d] /= counts[k]; } } } return new_centroids; } ``` #### 主循环结构 通过迭代完成整个K-Means过程，直到满足停止条件为止（如达到最大迭代次数或质心不再显著变化）[^2]。 ```cpp void runKMeans(std::vector<std::vector<double>>& X, int K, int max_iterations) { std::vector<std::vector<double>> centroids = initializeCentroids(X, K); for (int iteration = 0; iteration < max_iterations; ++iteration) { std::vector<int> idx = assignClosestCentroid(X, centroids); std::vector<std::vector<double>> updated_centroids = updateCentroids(X, idx, K); // 判断是否提前终止 bool converged = true; for (int k = 0; k < K; ++k) { if (euclideanDistance(centroids[k], updated_centroids[k]) > 1e-6) { converged = false; break; } } if (converged) { break; } centroids = updated_centroids; } } ``` ### 并行化处理 为了提高效率，在大规模数据场景下可以利用MPI或其他并行框架加速运算。例如，`MPI_Reduce`可用于汇总局部结果以更新全局质心[^3]。 --- ###