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函数并输出结果。

请注意，这个实现仅用于演示目的，实际应用中可能需要根据具体需求进行调整。例如，可以使用更高效的距离计算方法、并行化算法以提高性能等。