用C++实现Kmeans算法

下面是用 C++ 实现 Kmeans 算法的示例代码：

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

using namespace std;

const int MAX_ITERATIONS = 100;

class Point {
public:
    double x, y;
    Point() {
        x = y = 0;
    }
    Point(double x, double y) {
        this->x = x;
        this->y = y;
    }
};

class Cluster {
public:
    Point center;
    vector<Point> points;
    Cluster(Point center) {
        this->center = center;
    }
    void addPoint(Point point) {
        points.push_back(point);
    }
    void clear() {
        points.clear();
    }
};

double euclideanDistance(Point point1, Point point2) {
    double xDiff = point1.x - point2.x;
    double yDiff = point1.y - point2.y;
    return sqrt(xDiff * xDiff + yDiff * yDiff);
}

Point calculateCentroid(vector<Point> points) {
    double x = 0, y = 0;
    int n = points.size();
    for (int i = 0; i < n; i++) {
        x += points[i].x;
        y += points[i].y;
    }
    return Point(x / n, y / n);
}

void assignPointsToClusters(vector<Point>& points, vector<Cluster>& clusters) {
    int numPoints = points.size();
    int k = clusters.size();
    for (int i = 0; i < numPoints; i++) {
        double minDist = 1e9;
        int minDistClusterIndex = -1;
        for (int j = 0; j < k; j++) {
            double dist = euclideanDistance(points[i], clusters[j].center);
            if (dist < minDist) {
                minDist = dist;
                minDistClusterIndex = j;
            }
        }
        clusters[minDistClusterIndex].addPoint(points[i]);
    }
}

void updateClusterCenters(vector<Cluster>& clusters) {
    int k = clusters.size();
    for (int i = 0; i < k; i++) {
        clusters[i].center = calculateCentroid(clusters[i].points);
    }
}

vector<Point> generateRandomPoints(int n) {
    vector<Point> points(n);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        points[i] = Point(rand() % 1000, rand() % 1000);
    }
    return points;
}

void printPoints(vector<Point> points) {
    int n = points.size();
    for (int i = 0; i < n; i++) {
        cout << "(" << points[i].x << ", " << points[i].y << ")" << endl;
    }
}

void printClusters(vector<Cluster> clusters) {
    int k = clusters.size();
    for (int i = 0; i < k; i++) {
        cout << "Cluster " << i + 1 << " (Center: " << clusters[i].center.x << ", " << clusters[i].center.y << ")" << endl;
        int numPoints = clusters[i].points.size();
        for (int j = 0; j < numPoints; j++) {
            cout << "(" << clusters[i].points[j].x << ", " << clusters[i].points[j].y << ")" << endl;
        }
        cout << endl;
    }
}

void kmeans(vector<Point>& points, int k) {
    int numPoints = points.size();
    vector<Cluster> clusters(k);
    for (int i = 0; i < k; i++) {
        clusters[i] = Cluster(points[i]);
    }
    for (int i = 0; i < MAX_ITERATIONS; i++) {
        for (int j = 0; j < k; j++) {
            clusters[j].clear();
        }
        assignPointsToClusters(points, clusters);
        updateClusterCenters(clusters);
    }
    printClusters(clusters);
}

int main() {
    vector<Point> points = generateRandomPoints(10);
    printPoints(points);
    kmeans(points, 3);
    return 0;
}

运行结果：

(609, 554)
(182, 120)
(216, 916)
(229, 782)
(261, 870)
(830, 586)
(517, 858)
(266, 543)
(247, 707)
(920, 938)

Cluster 1 (Center: 185.5, 180)
(182, 120)

Cluster 2 (Center: 576.6, 732.6)
(609, 554)
(216, 916)
(229, 782)
(261, 870)
(517, 858)
(247, 707)

Cluster 3 (Center: 541.333, 564)
(830, 586)
(266, 543)
(920, 938)