詳解 C++ 實(shí)現(xiàn) K-means 算法
一、K-means算法概述
K-means算法是一種非常經(jīng)典的聚類算法，其主要目的是將數(shù)據(jù)點(diǎn)劃分為K個(gè)集群，以使得每個(gè)數(shù)據(jù)點(diǎn)與其所屬集群的中心點(diǎn)（質(zhì)心）的平方距離之和最小。這種算法在數(shù)據(jù)挖掘、圖像處理、模式識(shí)別等領(lǐng)域有著廣泛的應(yīng)用。
二、K-means算法的基本原理
K-means算法的基本原理相對(duì)簡(jiǎn)單直觀。算法接受兩個(gè)輸入?yún)?shù)：一是數(shù)據(jù)集，二是用戶指定的集群數(shù)量K。算法的輸出是K個(gè)集群，每個(gè)集群都有其中心點(diǎn)以及屬于該集群的數(shù)據(jù)點(diǎn)。
K-means算法的執(zhí)行過程如下：
- 初始化：隨機(jī)選擇K個(gè)點(diǎn)作為初始集群中心（質(zhì)心）。
- 分配數(shù)據(jù)點(diǎn)到最近的集群：對(duì)于數(shù)據(jù)集中的每個(gè)點(diǎn)，計(jì)算其與各個(gè)質(zhì)心的距離，并將其分配到距離最近的質(zhì)心所對(duì)應(yīng)的集群中。
- 重新計(jì)算質(zhì)心：對(duì)于每個(gè)集群，計(jì)算其內(nèi)所有數(shù)據(jù)點(diǎn)的平均值，并將該平均值設(shè)為新的質(zhì)心。
- 迭代優(yōu)化：重復(fù)步驟2和3，直到滿足某個(gè)終止條件（如質(zhì)心的變化小于某個(gè)閾值，或者達(dá)到最大迭代次數(shù)）。
圖解說明：
圖a表示初始的數(shù)據(jù)集，在圖b中隨機(jī)找到兩個(gè)類別質(zhì)心，接著執(zhí)行上述的步驟二，得到圖c的兩個(gè)集群，但此時(shí)明顯不符合我們的要求，因此需要進(jìn)行步驟三，得到新的類別質(zhì)心（圖d），重復(fù)的進(jìn)行多次迭代（如圖e和f），直到達(dá)到不錯(cuò)的結(jié)果。
三、K-means算法的數(shù)學(xué)表達(dá)
K-means 算法是一種迭代求解的聚類分析算法，其目標(biāo)是將 個(gè)觀測(cè)值劃分為 （）個(gè)聚類，以使得每個(gè)觀測(cè)值屬于離它最近的均值（聚類中心或聚類質(zhì)心）對(duì)應(yīng)的聚類，以作為聚類的標(biāo)準(zhǔn)。
數(shù)學(xué)公式
1.數(shù)據(jù)表示
2.聚類中心
3.目標(biāo)函數(shù)
4.迭代更新
5.算法終止條件
迭代進(jìn)行分配步驟和更新步驟，直到聚類中心不再發(fā)生顯著變化，或者達(dá)到預(yù)設(shè)的最大迭代次數(shù)。
四、K-means算法的C++實(shí)現(xiàn)
首先是頭文件：
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <algorithm>第一步: 數(shù)據(jù)結(jié)構(gòu)定義
我們定義了一個(gè)Point結(jié)構(gòu)體來表示二維空間中的點(diǎn)。
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
};這個(gè)結(jié)構(gòu)體很簡(jiǎn)單，只有兩個(gè)成員變量x和y，分別表示點(diǎn)在二維空間中的橫坐標(biāo)和縱坐標(biāo)。還有一個(gè)構(gòu)造函數(shù)，用于創(chuàng)建點(diǎn)對(duì)象時(shí)初始化坐標(biāo)。
第二步: 輔助函數(shù)
距離計(jì)算函數(shù)
double distance(const Point& a, const Point& b) {
return std::hypot(a.x - b.x, a.y - b.y);
}這個(gè)函數(shù)計(jì)算兩個(gè)點(diǎn)之間的距離，使用了<cmath>庫中的std::hypot函數(shù)，它接受兩個(gè)參數(shù)（橫坐標(biāo)和縱坐標(biāo)的差值），并返回這兩點(diǎn)之間的歐幾里得距離。
質(zhì)心計(jì)算函數(shù)
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());
}這個(gè)函數(shù)計(jì)算一個(gè)點(diǎn)集的質(zhì)心。質(zhì)心是所有點(diǎn)的坐標(biāo)平均值。函數(shù)遍歷點(diǎn)集，累加所有點(diǎn)的x坐標(biāo)和y坐標(biāo)，然后分別除以點(diǎn)的數(shù)量，得到質(zhì)心的坐標(biāo)。
第三步: K-means算法主體
K-means算法的主體部分可以進(jìn)一步拆分為幾個(gè)小的步驟：初始化、分配點(diǎn)、重新計(jì)算質(zhì)心和檢查收斂性。
初始化
在K-means算法中，我們需要首先選擇K個(gè)初始質(zhì)心。在這個(gè)簡(jiǎn)單的實(shí)現(xiàn)中，我們隨機(jī)選擇數(shù)據(jù)集中的K個(gè)點(diǎn)作為初始質(zhì)心。
std::vector<Point> centroids(k);
for (int i = 0; i < k; ++i) {
centroids[i] = data[rand() % data.size()];
}分配點(diǎn)
對(duì)于數(shù)據(jù)集中的每個(gè)點(diǎn)，我們需要找到最近的質(zhì)心，并將其分配給該質(zhì)心對(duì)應(yīng)的集群。
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);
}重新計(jì)算質(zhì)心
分配完點(diǎn)后，我們需要重新計(jì)算每個(gè)集群的質(zhì)心。
std::vector<Point> new_centroids(k);
for (int i = 0; i < k; ++i) {
new_centroids[i] = centroid(clusters[i]);
}檢查收斂性
如果新舊質(zhì)心之間的變化很小（在一個(gè)很小的閾值以內(nèi)），則算法收斂，可以停止迭代。
bool converged = true;
for (int i = 0; i < k; ++i) {
if (distance(centroids[i], new_centroids[i]) > 1e-6) {
converged = false;
break;
}
}如果算法未收斂，則更新質(zhì)心并繼續(xù)迭代。
第四步: 主函數(shù)和數(shù)據(jù)準(zhǔn)備
在主函數(shù)中，我們準(zhǔn)備了一個(gè)簡(jiǎn)單的數(shù)據(jù)集（整體代碼見最后），并設(shè)置了K值和最大迭代次數(shù)。然后調(diào)用kmeans函數(shù)進(jìn)行聚類。
這就是K-means算法的一個(gè)基本實(shí)現(xiàn)。在實(shí)際應(yīng)用中，可能還需要考慮更多的優(yōu)化和異常情況處理，比如處理空集群、改進(jìn)初始質(zhì)心的選擇方法、添加對(duì)異常值的魯棒性等。
結(jié)果輸出：
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)五、K-means算法的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
- 算法簡(jiǎn)單直觀，易于理解和實(shí)現(xiàn)。
- 對(duì)于大數(shù)據(jù)集，K-means算法是相對(duì)高效的，因?yàn)樗膹?fù)雜度是線性的，即O(n)。
- 當(dāng)集群之間的區(qū)別明顯且數(shù)據(jù)分布緊湊時(shí)，K-means算法表現(xiàn)良好。
缺點(diǎn)：
- 需要預(yù)先指定集群數(shù)量K，這在實(shí)際應(yīng)用中可能是一個(gè)挑戰(zhàn)。
- 對(duì)初始質(zhì)心的選擇敏感，不同的初始質(zhì)心可能導(dǎo)致完全不同的結(jié)果。
- 只能發(fā)現(xiàn)球形的集群，對(duì)于非球形或復(fù)雜形狀的集群效果不佳。
- 對(duì)噪聲和異常值敏感，因?yàn)樗鼈儠?huì)影響質(zhì)心的計(jì)算。
六、源代碼如下
#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);
// 隨機(jī)化第一個(gè)質(zhì)點(diǎn)
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);
}
// 清除前一個(gè)的質(zhì)點(diǎn)
for (auto& cluster : clusters) {
cluster.clear();
}
// 重新計(jì)算質(zhì)點(diǎn)
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;
}
// 輸出結(jié)果
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)); // 隨機(jī)數(shù)種子，可以使用隨機(jī)數(shù)生成數(shù)據(jù)集
std::vector<Point> data = {
// 數(shù)據(jù)集
{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; // 集群數(shù)量
int max_iterations = 5; // 迭代次數(shù)
kmeans(data, k, max_iterations);
return 0;
}
