AVt天堂网 手机版,亚洲va久久久噜噜噜久久4399,天天综合亚洲色在线精品,亚洲一级Av无码毛片久久精品

當前位置:首頁 > 科技  > 軟件

詳解 C++ 實現 K-means 算法

來源: 責編: 時間:2024-04-19 09:22:26 126觀看
導讀一、K-means算法概述K-means算法是一種非常經典的聚類算法,其主要目的是將數據點劃分為K個集群,以使得每個數據點與其所屬集群的中心點(質心)的平方距離之和最小。這種算法在數據挖掘、圖像處理、模式識別等領域有著廣泛

一、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++中提升性能相關的十大特性

標簽:
  • 熱門焦點
Top