C++聚類算法中的類別劃分與合并

在C++中實現聚類算法時，類別劃分和合并是兩個關鍵步驟。這里，我們將討論K-means聚類算法，它是一種常見的聚類方法。K-means算法的目標是將數據點劃分為K個簇，使得每個數據點到其所屬簇的質心的距離之和最小。

以下是一個簡單的C++實現，展示了如何使用K-means算法進行類別劃分和合并：

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

struct Point {
    double x, y;
};

struct Centroid {
    double x, y;
};

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

std::vector<Point> kMeans(const std::vector<Point>& points, int k, int maxIterations = 100) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, points.size() - 1);

    std::vector<Centroid> centroids(k);
    std::vector<int> clusters(points.size(), -1);

    for (int i = 0; i < maxIterations; ++i) {
        std::vector<Point> clusters_points;

        for (int j = 0; j < points.size(); ++j) {
            double min_dist = std::numeric_limits<double>::max();
            int min_index = -1;

            for (int l = 0; l < k; ++l) {
                double dist = distance(points[j], centroids[l]);
                if (dist < min_dist) {
                    min_dist = dist;
                    min_index = l;
                }
            }

            clusters[j] = min_index;
            clusters_points.push_back(points[j]);
        }

        std::vector<Centroid> new_centroids(k);

        for (int j = 0; j < k; ++j) {
            if (clusters_points[j].size() == 0) {
                new_centroids[j] = centroids[j];
            } else {
                double sum_x = 0, sum_y = 0;
                for (const auto& point : clusters_points[j]) {
                    sum_x += point.x;
                    sum_y += point.y;
                }
                new_centroids[j] = {sum_x / clusters_points[j].size(), sum_y / clusters_points[j].size()};
            }
        }

        if (new_centroids == centroids) {
            break;
        }

        centroids = new_centroids;
    }

    return centroids;
}

int main() {
    std::vector<Point> points = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {3, 1}, {3, 2}};
    int k = 2;

    std::vector<Centroid> centroids = kMeans(points, k);

    std::cout << "Centroids:" << std::endl;
    for (const auto& centroid : centroids) {
        std::cout << "(" << centroid.x << ", " << centroid.y << ")" << std::endl;
    }

    return 0;
}

在這個示例中，我們首先定義了Point和Centroid結構體，分別表示數據點和質心。然后，我們實現了distance函數來計算兩點之間的距離。接下來，我們定義了kMeans函數，該函數接受一個點集、簇的數量（K）以及最大迭代次數作為參數。在kMeans函數中，我們使用K-means算法進行聚類，并返回最終的質心。

在main函數中，我們創建了一個包含6個二維點的點集，并將其劃分為2個簇。然后，我們調用kMeans函數并輸出結果。

請注意，這個實現僅用于演示目的，實際應用中可能需要根據具體需求進行調整。例如，可以使用更高效的距離計算方法、并行化算法以提高性能等。