K-means算法是一種非常經典的聚類算法,其主要目的是將數據點劃分為K個集群,以使得每個數據點與其所屬集群的中心點(質心)的平方距離之和最小。這種算法在數據挖掘、圖像處理、模式識別等領域有著廣泛的應用。
K-means算法的基本原理相對簡單直觀。算法接受兩個輸入參數:一是數據集,二是用戶指定的集群數量K。算法的輸出是K個集群,每個集群都有其中心點以及屬于該集群的數據點。
K-means算法的執行過程如下:
迭代進行分配步驟和更新步驟,直到聚類中心不再發生顯著變化,或者達到預設的最大迭代次數。
首先是頭文件:
#include <iostream> #include <vector> #include <cmath> #include <limits> #include <algorithm>
我們定義了一個Point結構體來表示二維空間中的點。
struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {}};
這個結構體很簡單,只有兩個成員變量x和y,分別表示點在二維空間中的橫坐標和縱坐標。還有一個構造函數,用于創建點對象時初始化坐標。
double distance(const Point& a, const Point& b) { return std::hypot(a.x - b.x, a.y - b.y);}
這個函數計算兩個點之間的距離,使用了<cmath>庫中的std::hypot函數,它接受兩個參數(橫坐標和縱坐標的差值),并返回這兩點之間的歐幾里得距離。
Point centroid(const std::vector<Point>& cluster) { double sum_x = 0, sum_y = 0; for (const auto& point : cluster) { sum_x += point.x; sum_y += point.y; } return Point(sum_x / cluster.size(), sum_y / cluster.size());}
這個函數計算一個點集的質心。質心是所有點的坐標平均值。函數遍歷點集,累加所有點的x坐標和y坐標,然后分別除以點的數量,得到質心的坐標。
K-means算法的主體部分可以進一步拆分為幾個小的步驟:初始化、分配點、重新計算質心和檢查收斂性。
在K-means算法中,我們需要首先選擇K個初始質心。在這個簡單的實現中,我們隨機選擇數據集中的K個點作為初始質心。
std::vector<Point> centroids(k);for (int i = 0; i < k; ++i) { centroids[i] = data[rand() % data.size()];}
對于數據集中的每個點,我們需要找到最近的質心,并將其分配給該質心對應的集群。
std::vector<std::vector<Point>> clusters(k);for (const auto& point : data) { double min_distance = std::numeric_limits<double>::max(); int cluster_index = 0; for (int i = 0; i < k; ++i) { double dist = distance(point, centroids[i]); if (dist < min_distance) { min_distance = dist; cluster_index = i; } } clusters[cluster_index].push_back(point);}
分配完點后,我們需要重新計算每個集群的質心。
std::vector<Point> new_centroids(k);for (int i = 0; i < k; ++i) { new_centroids[i] = centroid(clusters[i]);}
如果新舊質心之間的變化很小(在一個很小的閾值以內),則算法收斂,可以停止迭代。
bool converged = true;for (int i = 0; i < k; ++i) { if (distance(centroids[i], new_centroids[i]) > 1e-6) { converged = false; break; }}
如果算法未收斂,則更新質心并繼續迭代。
在主函數中,我們準備了一個簡單的數據集(整體代碼見最后),并設置了K值和最大迭代次數。然后調用kmeans函數進行聚類。
這就是K-means算法的一個基本實現。在實際應用中,可能還需要考慮更多的優化和異常情況處理,比如處理空集群、改進初始質心的選擇方法、添加對異常值的魯棒性等。
Cluster 1 centroid: (3.5, 3.9)(1, 0.6) (8, 5) (1, 4) (4, 6) Cluster 2 centroid: (5.41667, 9.06667)(2, 10) (2.5, 8.4) (5, 8) (8, 8) (9, 11) (6, 9)
#include <iostream> #include <vector> #include <cmath> #include <limits> #include <algorithm> struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }; double distance(const Point& a, const Point& b) { return std::hypot(a.x - b.x, a.y - b.y); } Point centroid(const std::vector<Point>& cluster) { double sum_x = 0, sum_y = 0; for (const auto& point : cluster) { sum_x += point.x; sum_y += point.y; } return Point(sum_x / cluster.size(), sum_y / cluster.size()); } void kmeans(std::vector<Point>& data, int k, int max_iterations) { std::vector<Point> centroids(k); std::vector<std::vector<Point>> clusters(k); // 隨機化第一個質點 for (int i = 0; i < k; ++i) { centroids[i] = data[rand() % data.size()]; } for (int iter = 0; iter < max_iterations; ++iter) { for (const auto& point : data) { double min_distance = std::numeric_limits<double>::max(); int cluster_index = 0; for (int i = 0; i < k; ++i) { double dist = distance(point, centroids[i]); if (dist < min_distance) { min_distance = dist; cluster_index = i; } } clusters[cluster_index].push_back(point); } // 清除前一個的質點 for (auto& cluster : clusters) { cluster.clear(); } // 重新計算質點 for (int i = 0; i < data.size(); ++i) { int cluster_index = 0; double min_distance = std::numeric_limits<double>::max(); for (int j = 0; j < k; ++j) { double dist = distance(data[i], centroids[j]); if (dist < min_distance) { min_distance = dist; cluster_index = j; } } clusters[cluster_index].push_back(data[i]); } std::vector<Point> new_centroids(k); for (int i = 0; i < k; ++i) { new_centroids[i] = centroid(clusters[i]); } bool converged = true; for (int i = 0; i < k; ++i) { if (distance(centroids[i], new_centroids[i]) > 1e-6) { converged = false; break; } } if (converged) { break; } centroids = new_centroids; } // 輸出結果 for (int i = 0; i < k; ++i) { std::cout << "Cluster " << i + 1 << " centroid: (" << centroids[i].x << ", " << centroids[i].y << ")" << std::endl; for (const auto& point : clusters[i]) { std::cout << "(" << point.x << ", " << point.y << ") "; } std::cout << std::endl; } } int main() { srand(time(nullptr)); // 隨機數種子,可以使用隨機數生成數據集 std::vector<Point> data = { // 數據集 {2.0, 10.0}, {2.5, 8.4}, {5.0, 8.0}, {8.0, 8.0}, {1.0, 0.6}, {9.0, 11.0}, {8.0, 5.0}, {1.0, 4.0}, {4.0, 6.0}, {6.0, 9.0} }; int k = 2; // 集群數量 int max_iterations = 5; // 迭代次數 kmeans(data, k, max_iterations); return 0; }
本文鏈接:http://www.tebozhan.com/showinfo-26-83992-0.html詳解 C++ 實現 K-means 算法
聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com
上一篇: 面試官:限流的常見算法有哪些?
下一篇: C++中提升性能相關的十大特性