一、K-means算法概述

Zdi28資訊網——每日最新資訊28at.com

K-means算法是一種非常經典的聚類算法，其主要目的是將數據點劃分為K個集群，以使得每個數據點與其所屬集群的中心點（質心）的平方距離之和最小。這種算法在數據挖掘、圖像處理、模式識別等領域有著廣泛的應用。Zdi28資訊網——每日最新資訊28at.com

二、K-means算法的基本原理

K-means算法的基本原理相對簡單直觀。算法接受兩個輸入參數：一是數據集，二是用戶指定的集群數量K。算法的輸出是K個集群，每個集群都有其中心點以及屬于該集群的數據點。Zdi28資訊網——每日最新資訊28at.com

K-means算法的執行過程如下：Zdi28資訊網——每日最新資訊28at.com

1. 初始化：隨機選擇K個點作為初始集群中心（質心）。
2. 分配數據點到最近的集群：對于數據集中的每個點，計算其與各個質心的距離，并將其分配到距離最近的質心所對應的集群中。
3. 重新計算質心：對于每個集群，計算其內所有數據點的平均值，并將該平均值設為新的質心。
4. 迭代優化：重復步驟2和3，直到滿足某個終止條件（如質心的變化小于某個閾值，或者達到最大迭代次數）。

圖解說明：

Zdi28資訊網——每日最新資訊28at.com

2.聚類中心

Zdi28資訊網——每日最新資訊28at.com

3.目標函數

Zdi28資訊網——每日最新資訊28at.com

4.迭代更新

Zdi28資訊網——每日最新資訊28at.com

5.算法終止條件

迭代進行分配步驟和更新步驟，直到聚類中心不再發生顯著變化，或者達到預設的最大迭代次數。Zdi28資訊網——每日最新資訊28at.com

四、K-means算法的C++實現

首先是頭文件：Zdi28資訊網——每日最新資訊28at.com

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

第一步: 數據結構定義

我們定義了一個Point結構體來表示二維空間中的點。Zdi28資訊網——每日最新資訊28at.com

struct Point {    double x, y;    Point(double x = 0, double y = 0) : x(x), y(y) {}};

這個結構體很簡單，只有兩個成員變量x和y，分別表示點在二維空間中的橫坐標和縱坐標。還有一個構造函數，用于創建點對象時初始化坐標。Zdi28資訊網——每日最新資訊28at.com

第二步: 輔助函數

距離計算函數

double distance(const Point& a, const Point& b) {    return std::hypot(a.x - b.x, a.y - b.y);}

這個函數計算兩個點之間的距離，使用了<cmath>庫中的std::hypot函數，它接受兩個參數（橫坐標和縱坐標的差值），并返回這兩點之間的歐幾里得距離。Zdi28資訊網——每日最新資訊28at.com

質心計算函數

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坐標，然后分別除以點的數量，得到質心的坐標。Zdi28資訊網——每日最新資訊28at.com

第三步: K-means算法主體

K-means算法的主體部分可以進一步拆分為幾個小的步驟：初始化、分配點、重新計算質心和檢查收斂性。Zdi28資訊網——每日最新資訊28at.com

初始化

在K-means算法中，我們需要首先選擇K個初始質心。在這個簡單的實現中，我們隨機選擇數據集中的K個點作為初始質心。Zdi28資訊網——每日最新資訊28at.com

std::vector<Point> centroids(k);for (int i = 0; i < k; ++i) {    centroids[i] = data[rand() % data.size()];}

分配點

對于數據集中的每個點，我們需要找到最近的質心，并將其分配給該質心對應的集群。Zdi28資訊網——每日最新資訊28at.com

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);}

重新計算質心

分配完點后，我們需要重新計算每個集群的質心。Zdi28資訊網——每日最新資訊28at.com

std::vector<Point> new_centroids(k);for (int i = 0; i < k; ++i) {    new_centroids[i] = centroid(clusters[i]);}

檢查收斂性

如果新舊質心之間的變化很小（在一個很小的閾值以內），則算法收斂，可以停止迭代。Zdi28資訊網——每日最新資訊28at.com

bool converged = true;for (int i = 0; i < k; ++i) {    if (distance(centroids[i], new_centroids[i]) > 1e-6) {        converged = false;        break;    }}

如果算法未收斂，則更新質心并繼續迭代。Zdi28資訊網——每日最新資訊28at.com

第四步: 主函數和數據準備

在主函數中，我們準備了一個簡單的數據集（整體代碼見最后），并設置了K值和最大迭代次數。然后調用kmeans函數進行聚類。Zdi28資訊網——每日最新資訊28at.com

這就是K-means算法的一個基本實現。在實際應用中，可能還需要考慮更多的優化和異常情況處理，比如處理空集群、改進初始質心的選擇方法、添加對異常值的魯棒性等。Zdi28資訊網——每日最新資訊28at.com

結果輸出：

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算法的優缺點

優點：

• 算法簡單直觀，易于理解和實現。
• 對于大數據集，K-means算法是相對高效的，因為它的復雜度是線性的，即O(n)。
• 當集群之間的區別明顯且數據分布緊湊時，K-means算法表現良好。

缺點：

• 需要預先指定集群數量K，這在實際應用中可能是一個挑戰。
• 對初始質心的選擇敏感，不同的初始質心可能導致完全不同的結果。
• 只能發現球形的集群，對于非球形或復雜形狀的集群效果不佳。
• 對噪聲和異常值敏感，因為它們會影響質心的計算。

六、源代碼如下

#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;  }

Zdi28資訊網——每日最新資訊28at.com

本文鏈接：http://www.tebozhan.com/showinfo-26-83992-0.html詳解 C++ 實現 K-means 算法

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 面試官：限流的常見算法有哪些？

下一篇： C++中提升性能相關的十大特性