C++聚类算法中的软聚类与硬聚类

在C++中实现聚类算法时，软聚类和硬聚类是两种常见的方法，它们在处理数据点归属问题时有着不同的方式。

硬聚类

硬聚类是一种将数据点划分为固定数量的簇的方法，每个数据点只能属于一个簇，且簇的边界是明确的。在C++中，可以使用多种算法来实现硬聚类，如K-means算法。

K-means算法是一种迭代优化算法，旨在将n个观测值划分为k个（k≤n）聚类，使得每个观测值属于最近的均值（聚类中心）所代表的聚类，同时使得各聚类的内部观测值之间的平方距离（或欧氏距离）之和最小。

以下是一个简单的C++ K-means算法实现示例：

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

struct Point {
    double x, y;
};

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

std::vector<Point> kMeans(const std::vector<Point>& points, int k, int maxIterations = 100) {
    std::vector<Point> centroids(k);
    std::vector<int> assignments(points.size(), -1);
    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(0, k - 1);

    for (int i = 0; i < maxIterations; ++i) {
        // Assign points to the nearest centroid
        std::vector<int> counts(k, 0);
        for (size_t j = 0; j < points.size(); ++j) {
            double minDist = std::numeric_limits<double>::max();
            int closestCentroid = -1;
            for (int c = 0; c < k; ++c) {
                double dist = distance(points[j], centroids[c]);
                if (dist < minDist) {
                    minDist = dist;
                    closestCentroid = c;
                }
            }
            assignments[j] = closestCentroid;
            counts[closestCentroid]++;
        }

        // Update centroids
        for (int c = 0; c < k; ++c) {
            if (counts[c] > 0) {
                centroids[c] = {0, 0};
                for (size_t j = 0; j < points.size(); ++j) {
                    if (assignments[j] == c) {
                        centroids[c].x += points[j].x;
                        centroids[c].y += points[j].y;
                    }
                }
                centroids[c].x /= counts[c];
                centroids[c].y /= counts[c];
            }
        }
    }

    return centroids;
}

int main() {
    std::vector<Point> points = {{1, 2}, {1, 4}, {1, 0}, {10, 2}, {10, 4}, {10, 0}};
    int k = 2;
    std::vector<Point> centroids = kMeans(points, k);

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

    return 0;
}

软聚类

与硬聚类不同，软聚类允许数据点属于多个簇，每个数据点属于每个簇的概率是一个软决策。这种方法在处理数据时提供了更大的灵活性，因为它允许数据点部分地属于一个簇。

在C++中，K-means++是一种常用的软聚类算法，它是K-means算法的扩展，用于改进初始质心的选择，从而提高聚类的质量。K-means++通过选择距离现有质心较远的点作为新的质心，以避免初始质心选择的随机性导致的不稳定性。

以下是一个简单的C++ K-means++算法实现示例：

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

struct Point {
    double x, y;
};

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

std::vector<Point> kMeansPlusPlus(const std::vector<Point>& points, int k, int maxIterations = 100) {
    std::vector<Point> centroids(k);
    std::vector<int> assignments(points.size(), -1);
    std::default_random_engine generator;
    std::uniform_real_distribution<double> distribution(0.0, 1.0);

    // Choose the first centroid randomly
    centroids[0] = points[distribution(generator) * points.size()];

    for (int i = 1; i < k; ++i) {
        std::vector<double> distances(points.size());
        for (size_t j = 0; j < points.size(); ++j) {
            double dist = distance(points[j], centroids[i - 1]);
            distances[j] = dist * dist; // Square the distance for selection
        }

        // Select the next centroid with probability proportional to the squared distance
        double sumDistances = 0;
        for (size_t j = 0; j < points.size(); ++j) {
            sumDistances += distances[j];
            if (distribution(generator) < sumDistances / (i * points.size())) {
                centroids[i] = points[j];
                break;
            }
        }
    }

    // Assign points to the nearest centroid
    std::vector<int> counts(k, 0);
    for (size_t j = 0; j < points.size(); ++j) {
        double minDist = std::numeric_limits<double>::max();
        int closestCentroid = -1;
        for (int c = 0; c < k; ++c) {
            double dist = distance(points[j], centroids[c]);
            if (dist < minDist) {
                minDist = dist;
                closestCentroid = c;
            }
        }
        assignments[j] = closestCentroid;
        counts[closestCentroid]++;
    }

    return centroids;
}

int main() {
    std::vector<Point> points = {{1, 2}, {1, 4}, {1, 0}, {10, 2}, {10, 4}, {10, 0}};
    int k = 2;
    std::vector<Point> centroids = kMeansPlusPlus(points, k);

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

    return 0;
}

在这两个示例中，我们定义了一个Point结构体来表示二维空间中的点，并实现了计算两点之间距离的函数distance。kMeans函数实现了基本的K-means硬聚类算法，而kMeansPlusPlus函数实现了K-means++软聚类算法。在kMeansPlusPlus中，我们通过选择距离现有质心较远的点作为新的质心，来改进初始质心的选择。