C++聚類算法中的局部搜索優化

在C++中實現聚類算法時，局部搜索優化是一種常用的方法，用于改進聚類結果。局部搜索優化通常與啟發式算法（如K-means、DBSCAN等）結合使用，以提高算法的性能和穩定性。

以下是一個簡單的C++示例，展示了如何使用局部搜索優化來改進K-means聚類算法的結果：

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

// 計算歐幾里得距離
double euclideanDistance(const vector<double>& point1, const vector<double>& point2) {
    double sum = 0;
    for (size_t i = 0; i < point1.size(); ++i) {
        sum += pow(point1[i] - point2[i], 2);
    }
    return sqrt(sum);
}

// K-means算法
vector<vector<double>> kMeans(const vector<vector<double>>& data, int k, int maxIterations = 100) {
    srand(time(0));

    // 隨機初始化質心
    vector<vector<double>> centroids(k);
    for (int i = 0; i < k; ++i) {
        centroids[i] = data[rand() % data.size()];
    }

    for (int iteration = 0; iteration < maxIterations; ++iteration) {
        vector<vector<double>> clusters(k);

        // 將數據點分配到最近的質心
        for (const auto& point : data) {
            double minDistance = DBL_MAX;
            int closestCentroid = -1;
            for (int i = 0; i < k; ++i) {
                double distance = euclideanDistance(point, centroids[i]);
                if (distance < minDistance) {
                    minDistance = distance;
                    closestCentroid = i;
                }
            }
            clusters[closestCentroid].push_back(point);
        }

        // 更新質心
        vector<vector<double>> newCentroids(k);
        for (int i = 0; i < k; ++i) {
            if (!clusters[i].empty()) {
                double sum = 0;
                for (const auto& point : clusters[i]) {
                    sum += point[0]; // 假設數據點只有一個特征
                }
                newCentroids[i] = {sum / clusters[i].size()};
            } else {
                // 如果某個質心沒有分配到任何點，隨機選擇一個數據點作為新的質心
                newCentroids[i] = data[rand() % data.size()];
            }
        }

        // 檢查質心是否收斂
        bool converged = true;
        for (int i = 0; i < k; ++i) {
            if (euclideanDistance(centroids[i], newCentroids[i]) > 1e-4) {
                converged = false;
                break;
            }
        }

        if (converged) {
            break;
        }

        centroids = newCentroids;
    }

    return centroids;
}

int main() {
    vector<vector<double>> data = {{1, 2}, {1, 4}, {1, 0}, {10, 2}, {10, 4}, {10, 0}};
    int k = 2;

    vector<vector<double>> centroids = kMeans(data, k);

    cout << "質心：" << endl;
    for (const auto& centroid : centroids) {
        cout << "[" << centroid[0] << ", " << centroid[1] << "]" << endl;
    }

    return 0;
}

在這個示例中，我們首先定義了一個計算歐幾里得距離的函數euclideanDistance。然后，我們實現了K-means算法，其中局部搜索優化通過在每次迭代中更新質心來實現。當質心的變化小于某個閾值（例如1e-4）時，我們認為算法已經收斂，停止迭代。

這個示例僅用于演示局部搜索優化在K-means算法中的應用。實際上，局部搜索優化可以與其他聚類算法結合使用，以提高算法的性能和穩定性。