Clustering Lab · Lecture 13

k-means by hand, one step at a time

Slide 5: points 1, 2, 3, 10, 11, 12 with k = 2 and a poor start at 1 and 2. Predict each step, then press the button. Change the numbers to try your own example.

Points

Start centres

Rounds so far

Each round has two steps: assign every point to its nearest centre, then move each centre to the mean of its points. Stop when nothing changes.

What to notice

A poor start still ends well here, but it needs more rounds.
The centres are means, so they can sit where no point is (7.6).
k-means always stops: each step can only lower the total squared distance.

Try this

Start the centres at 1 and 12. How many rounds now? Homework 13.1: do it on paper first, then check each round here.

Watch k-means find groups

The 200 unlabelled points from slide 3. Pick k, choose a start (random, or click the plot to move the nearest centre), then step through assign and move.

round

inertia (total squared distance)

–

Crosses: centres. Thin lines: the path each centre has travelled. Click the plot to move the nearest centre there (before or between steps).

What to notice

Inertia falls at every step and stops falling when nothing changes.
"A bad start" ends in a poor answer: two centres share one group and one centre covers two. k-means only finds a local best.
That is why scikit-learn runs n_init=10 starts and keeps the one with the lowest inertia.

Try this

Press "New random start" and "Run to the end" five times. Do you always get the same inertia? Set k = 2. Which two groups get merged?

Choose k: the elbow

scikit-learn's result for each k (n_init=10, random_state=0). Inertia always falls as k grows; look for the bend.

k =

Slide 7 in Python

Why n_init=10? Ten single random starts

What to notice

From k = 1 to 3 inertia drops steeply; after 3 it hardly moves. The bend says 3.
With more clusters than real groups, k-means still splits the data. It never says "there is no group here".
Some single starts stop at a much worse answer. Ten starts make that unlikely.

Try this

At k = 4, which real group gets split in two? Homework 13.2: draw the elbow for blobs with 4 centres. Does the bend appear at 4?

Limits of k-means

Five invented data sets where we know the true groups. Compare the groups k-means finds with the true ones.

Data

colour by k-means colour by true group

points put in the right group

Iris without labels (slide 10)

What to notice

k-means draws straight borders halfway between centres, so it likes round groups of similar size.
Curved, stretched or very uneven groups are cut in the wrong places.
Distances mix units. Scale first, exactly as for k-NN in Lecture 12.

Try this

Compare "not scaled" with "scaled first". Which feature decides the groups when you do not scale? In the iris plot, find the flowers k-means put in the wrong group.

Works offline: no internet needed. The data and the trained models are built into this page. Every number was calculated with scikit-learn and checked, so it matches what you will see in Jupyter or Colab.