C++: k-means clustering
k-means is an unsupervised algorithm that splits unlabeled points into k clusters. It repeats two steps. In the assignment step each point joins the cluster of its nearest center. In the update step each center moves to the mean of the points assigned to it.
C++
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
struct Point {
double x, y;
};
int main() {
std::vector<Point> points = {{1, 1}, {1.5, 2}, {3, 4}, {5, 7}, {3.5, 5}, {4.5, 5}, {3.5, 4.5}};
std::vector<Point> centers = {points[0], points[3]};
std::vector<int> label(points.size(), 0);
for (int round = 0; round < 10; ++round) {
for (std::size_t i = 0; i < points.size(); ++i) {
double best = 1e18;
for (int c = 0; c < 2; ++c) {
double d = std::hypot(points[i].x - centers[c].x, points[i].y - centers[c].y);
if (d < best) {
best = d;
label[i] = c;
}
}
}
for (int c = 0; c < 2; ++c) {
double sx = 0, sy = 0;
int count = 0;
for (std::size_t i = 0; i < points.size(); ++i) {
if (label[i] == c) {
sx += points[i].x;
sy += points[i].y;
++count;
}
}
if (count > 0) {
centers[c] = {sx / count, sy / count};
}
}
}
std::cout << std::fixed << std::setprecision(2);
for (int c = 0; c < 2; ++c) {
std::cout << "center " << c << ": (" << centers[c].x << ", " << centers[c].y << ")\n";
}
for (std::size_t i = 0; i < points.size(); ++i) {
std::cout << label[i];
}
std::cout << "\n";
}