Interactive demo · Probabilistic Machine Learning · Chapter 21

K-means: Lloyd steps, local minima and K-means++

K-means alternates two exact minimisations of the distortion (21.15): assign every point to its nearest centre (21.13), then move every centre to the mean of its points (21.14). The distortion can only go down, so the algorithm stops, but only at a local minimum. Here 2000 points form five blobs (two wide ones and three small ones stacked on the left). Choose how the K centres are first placed, press Step to watch one assign-and-update round, and press 200 seeds to see how often each seeding ends in the best solution. K-means++ (21.18) picks each new centre with probability proportional to its squared distance to the centres already chosen.

Number of clusters K

Seeding

Random seed

Run

Try these

Data: 2000 simulated points (five Gaussian blobs, a stand-in for the book's blob data). Distortion is the sum of squared distances to the assigned centre, J in (21.15). The preset starts use fixed centres, so the same iterations can be reproduced in code. The 200-seed experiment starts every run from the chosen seeding (K centres) with seeds 1 to 200, for both rules, and runs Lloyd's algorithm to convergence.

In the lecture notes