C++聚類算法中的聚類邊界檢測

在C++中實現聚類邊界檢測，我們可以使用一種稱為DBSCAN（Density-Based Spatial Clustering of Applications with Noise）的算法。DBSCAN是一種基于密度的聚類算法，它可以有效地檢測出聚類邊界并識別噪聲點。

以下是使用C++實現DBSCAN算法的示例代碼：

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

struct Point {
    double x, y;
};

struct PointDistance {
    bool operator()(const Point& a, const Point& b) {
        return std::sqrt(std::pow(a.x - b.x, 2) + std::pow(a.y - b.y, 2)) > std::sqrt(std::pow(b.x - a.x, 2) + std::pow(b.y - a.y, 2));
    }
};

class DBSCAN {
public:
    DBSCAN(double eps, int minPts) : eps(eps), minPts(minPts) {}

    void run(const std::vector<Point>& points) {
        std::unordered_set<int> cluster_ids;
        std::vector<std::vector<Point>> clusters;

        for (int i = 0; i < points.size(); ++i) {
            if (visited[i]) continue;

            std::queue<int> q;
            q.push(i);
            visited[i] = true;
            int cluster_id = 0;

            while (!q.empty()) {
                int point_index = q.front();
                q.pop();

                if (cluster_ids.find(point_index) != cluster_ids.end()) continue;

                cluster_ids.insert(point_index);
                clusters.push_back({});
                clusters.back().push_back(points[point_index]);

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

        for (size_t i = 0; i < clusters.size(); ++i) {
            if (clusters[i].size() < minPts) {
                for (const auto& point : clusters[i]) {
                    visited[point] = false;
                }
                clusters.erase(clusters.begin() + i);
                --i;
            }
        }

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

private:
    double eps;
    int minPts;
    std::vector<bool> visited;

    std::vector<Point> getNeighbors(const std::vector<Point>& points, int point_index) {
        std::vector<Point> neighbors;
        for (int i = 0; i < points.size(); ++i) {
            if (i == point_index) continue;

            double distance = std::sqrt(std::pow(points[point_index].x - points[i].x, 2) + std::pow(points[point_index].y - points[i].y, 2));
            if (distance <= eps) {
                neighbors.push_back(points[i]);
            }
        }
        return neighbors;
    }
};

int main() {
    std::vector<Point> points = {{1, 2}, {2, 2}, {2, 3}, {8, 7}, {8, 8}, {25, 80}};
    DBSCAN dbscan(0.5, 2);
    dbscan.run(points);
    return 0;
}

在這個示例中，我們首先定義了一個Point結構體來表示二維空間中的點，然后定義了一個PointDistance結構體來比較兩點之間的距離。接下來，我們創建了一個DBSCAN類來實現DBSCAN算法。在run方法中，我們遍歷所有點，使用一個隊列來進行廣度優先搜索（BFS），將每個點的鄰居添加到隊列中，并將訪問過的點標記為已訪問。最后，我們根據點的數量判斷是否為噪聲點，并將聚類結果輸出到控制臺。

這個示例只是一個簡單的實現，實際應用中可能需要根據具體需求進行調整。