Try first

Sixty points on a plot in two obvious blobs, and no labels at all.

You want the program to find the two groups. It cannot see the picture. Write down a procedure, in three steps, that would work. Try before reading on, because the answer is something you could have invented.

The procedure

Almost everyone converges on the same idea. Guess where the group centers are. Assign every point to the nearest center. Move each center to the middle of the points that chose it. Repeat.

That is k-means in full.

function kmeans(data, k, iterations = 50) {
  let centers = shuffled(data).slice(0, k).map(r => r.x.slice());
  let assign = new Array(data.length).fill(-1);

  for (let t = 0; t < iterations; t++) {
    let changed = false;
    data.forEach((r, i) => {
      let best = 0, bestD = Infinity;
      centers.forEach((c, j) => {
        const d = distance(r.x, c);
        if (d < bestD) { bestD = d; best = j; }
      });
      if (assign[i] !== best) { assign[i] = best; changed = true; }
    });

    centers = centers.map((c, j) => {
      const members = data.filter((_, i) => assign[i] === j).map(r => r.x);
      return members.length ? mean(members) : c;
    });

    if (!changed) { log("settled after", t + 1, "rounds"); break; }
  }
  return { centers, assign };
}

Start the centers at k randomly chosen data points. Assign, recompute, repeat until nothing changes.

The mean function is from lesson 3038 and the distance from lesson 3039. Nothing new was needed.

Watch it settle

function showClusters(data, result) {
  clear(); grid(1);
  data.forEach((r, i) => {
    dot(r.x[0], r.x[1], palette[result.assign[i] % palette.length], 4);
  });
  result.centers.forEach((c, j) => {
    dot(c[0], c[1], "#000", 9);
    dot(c[0], c[1], palette[j % palette.length], 6);
  });
}

view.xMin = 0; view.xMax = 10; view.yMin = 0; view.yMax = 10;
showClusters(points, kmeans(points, 2));

Run it a few times. Usually it settles in three or four rounds and finds the two blobs, and the centers land near where you would have put them.

Sometimes it does not. If both starting centers happen to fall inside the same blob, the split can end up cutting one blob in half and lumping the other together. It settles perfectly happily into that arrangement and reports no problem.

The fix is the same as lesson 3060’s: run it several times from different starts and keep the best. “Best” here means the one with the smallest total distance from points to their centers, which is the closest thing to a loss this method has.

Choosing k

This is the awkward part. You must state the number of groups before you begin, and if you knew that you would already know something important about your data.

The usual approach is to try several and look at the total distance.

function inertia(data, result) {
  let s = 0;
  data.forEach((r, i) => {
    const d = distance(r.x, result.centers[result.assign[i]]);
    s += d * d;
  });
  return s;
}

for (let k = 1; k <= 8; k++) {
  let best = Infinity;
  for (let t = 0; t < 10; t++) best = Math.min(best, inertia(points, kmeans(points, k)));
  log("k", k, " inertia", best.toFixed(1));
}

The number always falls as k rises, and at k equal to the number of points it reaches zero, because every point is its own center. So the smallest value is not the answer.

What you look for is the elbow: the point where the drop stops being dramatic. Going from 1 to 2 might halve it; going from 2 to 3 might shave a few percent. That suggests two real groups. It is a judgment call from a plot, and it is genuinely how this is done.

What it assumes without telling you

k-means finds groups that are roughly round, roughly equal in size, and separated by straight boundaries. That is what “nearest center” means geometrically.

Give it two long thin parallel bands and it will cut across them rather than along them. Give it a ring around a blob, as in lesson 3077, and it fails completely, for the same reason logistic regression did.

It is fast, simple, and it is a hypothesis about the shape of your data as much as an algorithm.

What to watch

Scale first. Again. Everything here is distance, so an unscaled column dominates the clustering and you get groups defined entirely by whichever feature has the widest range.

Exercises

  1. Run 20 times with k = 2 and count how often it splits the blobs correctly.
  2. Plot inertia against k for 1 to 8 and find the elbow. Does it match the data you generated?
  3. Build the ring dataset and cluster it with k = 2. Draw the result and explain the failure.
  4. Implement k-means++ initialization: pick the first center at random, then pick each next one with probability proportional to squared distance from the nearest existing center. Compare the success rate.
PreviousNext