C++聚類算法中的聚類趨勢預測

在C++中實現聚類算法時，聚類趨勢預測是一個重要的任務。聚類趨勢預測可以幫助我們了解數據的分布和潛在結構，從而為后續的數據分析和決策提供依據。以下是一些常用的聚類和趨勢預測算法，以及如何在C++中實現它們的基本思路：

1. K-means聚類

K-means是一種廣泛使用的聚類算法，它將數據劃分為K個簇，每個簇的中心是該簇內所有數據點的均值。

基本步驟：

1. 初始化：隨機選擇K個數據點作為初始質心。
2. 分配數據點到簇：將每個數據點分配到距離最近的質心所在的簇。
3. 更新質心：計算每個簇內所有數據點的均值，更新質心的位置。
4. 迭代：重復步驟2和3，直到質心不再發生變化或達到最大迭代次數。

C++實現示例：

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

using namespace std;

struct Point {
    double x, y;
};

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

vector<Point> kmeans(const vector<Point>& points, int k, int max_iterations = 100) {
    vector<Point> centroids(k);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, points.size() - 1);

    // Initialize centroids
    for (int i = 0; i < k; ++i) {
        centroids[i] = points[dis(gen)];
    }

    for (int iter = 0; iter < max_iterations; ++iter) {
        vector<Point> clusters(k);
        vector<int> cluster_counts(k, 0);

        // Assign points to clusters
        for (const auto& point : points) {
            double min_dist = DBL_MAX;
            int min_cluster = -1;
            for (int i = 0; i < k; ++i) {
                double dist = distance(point, centroids[i]);
                if (dist < min_dist) {
                    min_dist = dist;
                    min_cluster = i;
                }
            }
            clusters[min_cluster].push_back(point);
            cluster_counts[min_cluster]++;
        }

        // Update centroids
        for (int i = 0; i < k; ++i) {
            if (cluster_counts[i] > 0) {
                Point centroid = {0, 0};
                for (const auto& point : clusters[i]) {
                    centroid.x += point.x;
                    centroid.y += point.y;
                }
                centroid.x /= cluster_counts[i];
                centroid.y /= cluster_counts[i];
                centroids[i] = centroid;
            }
        }

        // Check for convergence
        bool converged = true;
        for (int i = 0; i < k; ++i) {
            if (cluster_counts[i] > 0) {
                Point prev_centroid = centroids[i];
                for (const auto& point : clusters[i]) {
                    double dist = distance(point, prev_centroid);
                    if (dist > 1e-6) { // Arbitrary small threshold
                        converged = false;
                        break;
                    }
                }
                if (!converged) break;
                centroids[i] = prev_centroid; // Revert to previous centroid for this iteration
            }
        }

        if (converged) break;
    }

    return centroids;
}

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

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

    return 0;
}

2. DBSCAN聚類

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一種基于密度的聚類算法，它能夠發現任意形狀的簇，并識別噪聲點。

基本步驟：

1. 初始化：選擇一個點作為核心點，并設置一個鄰域半徑和最小點數。
2. 擴展簇：從核心點開始，不斷擴展簇，直到沒有更多的點可以加入。
3. 標記噪聲點：未被分配到任何簇的點被認為是噪聲點。

C++實現示例：

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

using namespace std;

struct Point {
    double x, y;
};

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

vector<Point> dbscan(const vector<Point>& points, double eps, int min_samples) {
    vector<Point> clusters;
    vector<bool> visited(points.size(), false);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, points.size() - 1);

    for (int i = 0; i < points.size(); ++i) {
        if (!visited[i]) {
            vector<Point> cluster;
            queue<int> q;
            q.push(i);
            visited[i] = true;

            while (!q.empty()) {
                int point_index = q.front();
                q.pop();
                cluster.push_back(points[point_index]);

                for (const auto& neighbor : points) {
                    if (!visited[neighbor.first] && distance(points[point_index], neighbor) <= eps) {
                        visited[neighbor.first] = true;
                        q.push(neighbor.first);
                    }
                }
            }

            if (cluster.size() >= min_samples) {
                clusters.push_back(cluster);
            }
        }
    }

    return clusters;
}

int main() {
    vector<Point> points = {{1, 2}, {1, 4}, {1, 0}, {10, 2}, {10, 4}, {10, 0}};
    double eps = 2;
    int min_samples = 2;
    vector<Point> clusters = dbscan(points, eps, min_samples);

    for (const auto& cluster : clusters) {
        cout << "Cluster:" << endl;
        for (const auto& point : cluster) {
            cout << "(" << point.x << ", " << point.y << ")" << endl;
        }
    }

    return 0;
}

3. 高斯混合模型（GMM）

高斯混合模型是一種基于概率的聚類方法，它假設數據是由多個高斯分布生成的。

基本步驟：

1. 估計參數：通過EM算法（Expectation Maximization）估計每個高斯分布的參數（均值、協方差和混合系數）。
2. 聚類：根據每個數據點屬于各個高斯分布的概率進行聚類。

C++實現示例：

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

using namespace std;

struct Point {
    double x, y;
};

double multivariate_normal_pdf(const Point& x, const vector<Point>& mean, const vector<vector<double>>& covariance) {
    double exponent = 0.0;
    for (size_t i = 0; i < x.size(); ++i) {
        exponent += pow(x[i] - mean[i], 2) / covariance[i][i];
    }
    return exp(-0.5 * exponent) / sqrt((2 * M_PI) * pow(covariance[0][0], covariance.size()));
}

vector<vector<Point>> gmm(const vector<Point>& points, int num_components, double max_iterations = 100) {
    vector<vector<Point>> clusters(num_components);
    vector<Point> means(num_components);
    vector<vector<double>> covariances(num_components);
    vector<double> weights(num_components, 1.0 / num_components);

    // Initialize means and covariances randomly
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, points.size() - 1);

    for (int i = 0; i < num_components; ++i) {
        int index = dis(gen);
        means[i] = points[index];
        covariances[i] = {{1, 0}, {0, 1}}; // Identity matrix
    }

    for (int iter = 0; iter < max_iterations; ++iter) {
        vector<double> log_likelihood(num_components, 0.0);

        // E-step: Compute posterior probabilities
        for (size_t i = 0; i < points.size(); ++i) {
            double max_prob = -1.0;
            int max_cluster = -1;
            for (int j = 0; j < num_components; ++j) {
                double prob = multivariate_normal_pdf(points[i], means[j], covariances[j]) * weights[j];
                if (prob > max_prob) {
                    max_prob = prob;
                    max_cluster = j;
                }
            }
            log_likelihood[max_cluster] += log(max_prob);
        }

        // M-step: Update parameters
        double total_log_likelihood = accumulate(log_likelihood.begin(), log_likelihood.end(), 0.0);
        for (int j = 0; j < num_components; ++j) {
            weights[j] = exp(log_likelihood[j] - total_log_likelihood);
            weights[j] /= accumulate(weights.begin(), weights.end(), 0.0);

            Point sum = {0, 0};
            for (size_t i = 0; i < points.size(); ++i) {
                if (j == max_cluster) {
                    sum.x += points[i].x;
                    sum.y += points[i].y;
                }
            }
            means[j] = sum / points.size();

            vector<double> sum_cov(4, 0.0);
            for (size_t i = 0; i < points.size(); ++i) {
                if (j == max_cluster) {
                    sum_cov[0] += pow(points[i].x - means[j].x, 2);
                    sum_cov[1] += pow(points[i].y - means[j].y, 2);
                    sum_cov[2] += (points[i].x - means[j].x) * (points[i].y - means[j].y);
                    sum_cov[3] += pow(points[i].x - means[j].x, 2) * pow(points[i].y - means[j].y, 2);
                }
            }
            double n = points.size();
            covariances[j][0] = sum_cov[0] / n;
            covariances[j][1] = sum_cov[1] / n;
            covariances[j][2] = sum_cov[2] / n;
            covariances[j][3] = sum_cov[3] / n;
        }
    }

    // Assign points to clusters based on posterior probabilities
    for (size_t i = 0; i < points.size(); ++i) {
        double max_prob = -1.0;
        int max_cluster = -1;
        for (int j = 0; j < num_components; ++j) {
            double prob = multivariate_normal_pdf(points[i], means[j], covariances[j]) * weights[j];
            if (prob > max_prob) {
                max_prob = prob;
                max_cluster = j;
            }
        }
        clusters[max_cluster].push_back(points[i]);
    }

    return clusters;
}

int main() {
    vector<Point> points = {{1, 2}, {1, 4}, {1, 0}, {10, 2}, {10, 4}, {10, 0}};
    int num_components = 2;
    vector<vector<Point>> clusters = gmm(points, num_components);

    for (const auto& cluster : clusters) {
        cout << "Cluster:" << endl;
        for (const auto& point : cluster) {
            cout << "(" << point.x << ", " << point.y << ")" << endl;
        }
    }

    return 0;
}

這些算法只是聚類和趨勢預測的一部分方法，實際應用中可能需要根據具體需求選擇合適的算法并進行調整。希望這些示例能幫助你理解如何在C++中實現這些算法。