C++ 实现 K-means 聚类算法详解

K-means 聚类算法是一种常用的无监督学习算法，用于将一组数据分成 K 个类别。以下是一个简单的 C++ 实现。

定义数据结构

首先需要定义一个数据结构来表示每个数据点。这里我们使用一个简单的结构体来存储数据点的坐标。

struct Point {
  double x, y;
  int cluster;
};

其中，x 和 y 表示数据点的坐标，cluster 表示该点所属的簇。

初始化数据

接下来需要从输入数据中读取数据点并初始化。

int k = 3; // 要分成的簇的数量
vector<Point> points; // 存储所有数据点的数组

// 从文件中读取数据点
ifstream input("data.txt");
while (!input.eof()) {
  Point p;
  input >> p.x >> p.y;
  p.cluster = -1;
  points.push_back(p);
}
input.close();

// 随机初始化簇的中心点
vector<Point> centroids;
for (int i = 0; i < k; i++) {
  int index = rand() % points.size();
  centroids.push_back(points[index]);
}

这里我们从文件中读取数据点，然后随机初始化簇的中心点。

迭代计算

接下来需要进行迭代计算，直到簇的中心点不再发生变化为止。

bool changed = true;
while (changed) {
  // 将所有数据点分配到最近的簇
  for (int i = 0; i < points.size(); i++) {
    double min_distance = numeric_limits<double>::max();
    int min_index = -1;
    for (int j = 0; j < centroids.size(); j++) {
      double distance = calculate_distance(points[i], centroids[j]);
      if (distance < min_distance) {
        min_distance = distance;
        min_index = j;
      }
    }
    points[i].cluster = min_index;
  }

  // 计算每个簇的中心点
  vector<Point> new_centroids(k);
  vector<int> count(k);
  for (int i = 0; i < points.size(); i++) {
    new_centroids[points[i].cluster].x += points[i].x;
    new_centroids[points[i].cluster].y += points[i].y;
    count[points[i].cluster]++;
  }
  for (int i = 0; i < k; i++) {
    if (count[i] > 0) {
      new_centroids[i].x /= count[i];
      new_centroids[i].y /= count[i];
    }
  }

  // 判断簇的中心点是否发生变化
  changed = false;
  for (int i = 0; i < k; i++) {
    if (new_centroids[i].x != centroids[i].x || new_centroids[i].y != centroids[i].y) {
      centroids[i] = new_centroids[i];
      changed = true;
    }
  }
}

在每一次迭代中，首先需要将所有数据点分配到最近的簇。然后计算每个簇的中心点，判断簇的中心点是否发生变化。如果发生了变化，则更新簇的中心点并继续迭代，直到簇的中心点不再发生变化为止。

计算距离

最后，需要定义一个计算两个数据点之间距离的函数。

double calculate_distance(const Point& p1, const Point& p2) {
  double dx = p1.x - p2.x;
  double dy = p1.y - p2.y;
  return sqrt(dx * dx + dy * dy);
}

这个函数使用欧几里得距离计算两个数据点之间的距离。

完整的代码如下：

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

using namespace std;

struct Point {
  double x, y;
  int cluster;
};

double calculate_distance(const Point& p1, const Point& p2) {
  double dx = p1.x - p2.x;
  double dy = p1.y - p2.y;
  return sqrt(dx * dx + dy * dy);
}

int main() {
  int k = 3; // 要分成的簇的数量
  vector<Point> points; // 存储所有数据点的数组

  // 从文件中读取数据点
  ifstream input("data.txt");
  while (!input.eof()) {
    Point p;
    input >> p.x >> p.y;
    p.cluster = -1;
    points.push_back(p);
  }
  input.close();

  // 随机初始化簇的中心点
  vector<Point> centroids;
  for (int i = 0; i < k; i++) {
    int index = rand() % points.size();
    centroids.push_back(points[index]);
  }

  bool changed = true;
  while (changed) {
    // 将所有数据点分配到最近的簇
    for (int i = 0; i < points.size(); i++) {
      double min_distance = numeric_limits<double>::max();
      int min_index = -1;
      for (int j = 0; j < centroids.size(); j++) {
        double distance = calculate_distance(points[i], centroids[j]);
        if (distance < min_distance) {
          min_distance = distance;
          min_index = j;
        }
      }
      points[i].cluster = min_index;
    }

    // 计算每个簇的中心点
    vector<Point> new_centroids(k);
    vector<int> count(k);
    for (int i = 0; i < points.size(); i++) {
      new_centroids[points[i].cluster].x += points[i].x;
      new_centroids[points[i].cluster].y += points[i].y;
      count[points[i].cluster]++;
    }
    for (int i = 0; i < k; i++) {
      if (count[i] > 0) {
        new_centroids[i].x /= count[i];
        new_centroids[i].y /= count[i];
      }
    }

    // 判断簇的中心点是否发生变化
    changed = false;
    for (int i = 0; i < k; i++) {
      if (new_centroids[i].x != centroids[i].x || new_centroids[i].y != centroids[i].y) {
        centroids[i] = new_centroids[i];
        changed = true;
      }
    }
  }

  // 输出结果
  for (int i = 0; i < k; i++) {
    cout << "Cluster " << i << ":" << endl;
    for (int j = 0; j < points.size(); j++) {
      if (points[j].cluster == i) {
        cout << "(" << points[j].x << ", " << points[j].y << ")" << endl;
      }
    }
  }

  return 0;
}