C++: k-means clustering

Group unlabeled points by alternating between assigning points to centers and moving centers to the mean.

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";
}

Output

center 0: (1.25, 1.50)
center 1: (3.90, 5.10)
0011111

Explanation

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.

The algorithm stops when the assignments stop changing, and it always converges to a local optimum, but which one depends on the starting centers. Here the first two points start as centers. The points form two visible groups, and the final centers are the means of those groups.

Explore the dry run

Guided walkthroughReady

1#include <cmath>

2#include <iomanip>

3#include <iostream>

4#include <vector>

6struct Point {

7 double x, y;

8};

10int main() {

11 std::vector<Point> points = {{1, 1}, {1.5, 2}, {3, 4}, {5, 7}, {3.5, 5}, {4.5, 5}, {3.5, 4.5}};

12 std::vector<Point> centers = {points[0], points[3]};

13 std::vector<int> label(points.size(), 0);

15 for (int round = 0; round < 10; ++round) {

16 for (std::size_t i = 0; i < points.size(); ++i) {

17 double best = 1e18;

18 for (int c = 0; c < 2; ++c) {

19 double d = std::hypot(points[i].x - centers[c].x, points[i].y - centers[c].y);

20 if (d < best) {

21 best = d;

22 label[i] = c;

23 }

24 }

25 }

26 for (int c = 0; c < 2; ++c) {

27 double sx = 0, sy = 0;

28 int count = 0;

29 for (std::size_t i = 0; i < points.size(); ++i) {

30 if (label[i] == c) {

31 sx += points[i].x;

32 sy += points[i].y;

33 ++count;

34 }

35 }

36 if (count > 0) {

37 centers[c] = {sx / count, sy / count};

38 }

39 }

40 }

41 std::cout << std::fixed << std::setprecision(2);

42 for (int c = 0; c < 2; ++c) {

43 std::cout << "center " << c << ": (" << centers[c].x << ", " << centers[c].y << ")\n";

44 }

45 for (std::size_t i = 0; i < points.size(); ++i) {

46 std::cout << label[i];

47 }

48 std::cout << "\n";

49}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Choose two starting centers from the data.	`centers = (1,1) and (5,7)`	—
Assignment step: distance from the point to a center.	`centers = (1,1) and (5,7)`	—
Update step: each center moves to the mean of its points.	`centers → (1.25, 1.50) and (3.90, 5.10)`	—
After the rounds, the centers settle at the means of the two groups.	`centers → (1.25, 1.50) and (3.90, 5.10)`	center 0: (1.25, 1.50) center 1: (3.90, 5.10)
The labels put the first two points in cluster 0 and the other five, including (3, 4), in cluster 1.	`centers → (1.25, 1.50) and (3.90, 5.10)`	center 0: (1.25, 1.50) center 1: (3.90, 5.10) 0011111

Cost and common mistakes

O(rounds · n · k) time for n points and k clusters.

Different starting centers can give different clusters. Real implementations run several starts or use k-means++ initialization.
k must be chosen in advance. Methods such as the elbow method or silhouette score help.
k-means assumes roughly round clusters of similar size and is sensitive to feature scale.

Try it yourself

What happens if a cluster loses all of its points?

Reveal answer and reasoning

Its mean is undefined. The code above leaves that center unchanged; other implementations re-seed it from a random point.

C++: k-means clustering

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading