Home / Learn / Data & AI / ML foundations / Lesson 8.1
All lessons

Module 8: Finding patterns without labels · Lesson 8.1 · about 25 min

Clustering with k-means

With no labels at all, k-means finds k groups by repeating two steps: give each point to its nearest centre, then move each centre to the middle of its points. Run it by hand, see it settle, and learn its blind spots.

Key points, meanings and formulas on one page: choose "Save as PDF" in the print box.

Module 8 · about 25 minutes · read first: 1.4, 2.4. You’ll be able to run k-means by hand, explain inertia and why the algorithm always stops, and say when k-means is the wrong tool.

k-means finds groups in data nobody has labelled, by repeating two simple moves: join the nearest centre, then move each centre to the middle of its group.

1. Why this matters

Most data has no labels. A shop has purchase histories, but nobody has tagged customers as “bargain hunters” or “big weekly shoppers”. Clustering finds such groups for you, and k-means is the classic way. It is used for customer segments, grouping stores or products, shrinking the number of colours in an image, and as a first look at any new table.

2. Learning without labels

In supervised learning (Modules 3 to 7) every row had an answer to copy. In unsupervised learning there is no answer: the model looks for structure in the inputs alone. Clustering asks: which rows are like each other, and different from the rest?

Think of tipping a box of mixed buttons onto a table. Nobody tells you the categories, but you soon push them into piles of similar ones. k-means does that with numbers.

3. The algorithm

k-means needs one choice from you: k, the number of clusters (groups). Then:

  1. Start: place k centres. At random, or better with k-means++, which spreads them out.
  2. Assign: give every point to its nearest centre.
  3. Update: move each centre to the mean (average position) of the points assigned to it. The centre is also called the centroid.
  4. Repeat 2 and 3 until no point changes cluster.

Watch it happen

Six points on a line, k = 2, and a deliberately bad start.

Start. Points at 1, 2, 3, 10, 11, 12. The two centres start side by side at 1 and 2: a poor guess, to see k-means fix it.

Assign. The border is halfway between the centres, at 1.5. Only the point at 1 is nearer centre 1. The other five go to centre 2.

Update. Centre 1 stays at 1. Centre 2 moves to the average of its points: (2 + 3 + 10 + 11 + 12) ÷ 5 = 7.6.

Assign again. The border is now at (1 + 7.6) ÷ 2 = 4.3. Points 2 and 3 switch to centre 1.

Update again. Centre 1 = (1 + 2 + 3) ÷ 3 = 2. Centre 2 = (10 + 11 + 12) ÷ 3 = 11.

Stop. Assigning again changes nothing. Inertia (squared distances to the centres) = 1 + 0 + 1 + 1 + 0 + 1 = 4.

Try it: run k-means by hand
steps
inertia (sum of squared distances)

Made-up data: 150 customers by yearly visits and average spend, both scaled, with no labels. Step 1 colours each point by its nearest centre (the crosses). Step 2 moves each centre to the average of its points. Each step can only lower the inertia, so it always settles, but where it settles depends on the start: try a few. With a bad start two centres can share one group.

Both steps lower the inertia, the total squared distance from each point to its centre, so the algorithm always stops. But it only goes downhill from where it started, so different starts can end in different answers. Libraries run it several times (often 10) and keep the run with the lowest inertia.

k
how many groups you ask for
Sⱼ
cluster j: the set of points whose nearest centre is centre j
μⱼ (mu)
the centre of cluster j, the average position of its points
‖x − μⱼ‖²
squared distance from a point to its centre
J (inertia)
all those squared distances added up: small when every point is close to its centre
Physical meaning
Opening k shops in a town. Each resident uses the nearest shop; each shop then moves to the middle of its customers; repeat until nobody switches. The final shops sit in the hearts of the neighbourhoods, and inertia is the town's total walking.

4. Things to know

  • Scale first (Lesson 2.4). Distances mix the columns, so a column in dollars would swamp one in years.
  • Round, similar-sized clusters suit k-means best. It carves space into straight-edged cells round each centre, so long, curved or nested groups get cut badly. Density-based methods such as DBSCAN handle those.
  • Every point gets a cluster, outliers included, and they can drag a centre away.
  • You must choose k. Lesson 8.2 shows how.

“k-means finds the true groups in the data.” It finds the best k round blobs it can reach from its start, whether or not real groups exist. Give it random noise and k = 5 and it will happily return 5 clusters. Its answer depends on k, on the scaling and on the start. Clusters are a useful summary to check and name, not a discovery to trust blindly.

Maths and principle

Principle: find k centres so that each point is close to its own centre.

Objective (inertia): with clusters S1,…,Sk and centres 𝝁1,…,𝝁k,

J=∑j=1k∑𝐱∈Sj‖𝐱−𝝁j‖2

Why each step helps: with centres fixed, giving each point to its nearest centre can only shrink its term. With clusters fixed, the point that minimises the total squared distance to a set of points is their mean (the same fact as Lesson 5.4’s leaf mean). There are only finitely many ways to assign points, and J never rises, so the loop must end.

Analogy: opening k shops in a town. Each resident uses the nearest shop; each shop then moves to the middle of its customers; repeat until nobody switches.

Try it: points 1, 2, 3, 10, 11, 12 on a line, k=2, centres start at 1 and 2. Run it. (Assign: {1} and {2, 3, 10, 11, 12}. Update: 1 and 7.6. Assign: {1, 2, 3} and {10, 11, 12}. Update: 2 and 11. Assign: no change. Done.)

5. Worked example

Made-up numbers. Six customers by (visits per month, average spend in $10s): A (1, 9), B (2, 8), C (2, 10), D (8, 2), E (9, 3), F (10, 1). Start with centres at A and D.

  • Assign: A, B, C are nearest (1, 9); D, E, F nearest (8, 2).
  • Update: centre 1 = mean of A, B, C = (1.67, 9); centre 2 = mean of D, E, F = (9, 2).
  • Assign: no change. Done.

Inertia: cluster 1: (0.44 + 0) + (0.11 + 1) + (0.11 + 1) = 2.67; cluster 2: (1 + 0) + (0 + 1) + (1 + 1) = 4. Total 6.67. Two clear segments: occasional big spenders, and frequent small spenders.

6. Practice

  1. In the simulation, find a start where two centres share one group and another centre covers two. What does the inertia say?
  2. Why must the columns be scaled before k-means?
  3. A cluster ends up with no points. What would you do?
Answers
  1. The inertia stays higher than in a good run; keeping the lowest-inertia run of several avoids this.
  2. Distance adds up differences in every column, so a column with big numbers would decide the clusters on its own.
  3. Restart that centre somewhere else, for example at the point farthest from its centre (libraries do this automatically).

Try it on your own data: the small model trainer runs k-means on your CSV with k-means++ starts and the best of 10 runs.

New words: unsupervised learning, clustering, k-means, centroid, inertia, k-means++, local minimum.

  • Clustering finds groups in data with no labels; k-means is the classic method.
  • k-means repeats two steps: assign each point to its nearest centre, move each centre to the mean of its points, until nothing changes.
  • Inertia (total squared distance to the centres) falls at every step, so it always stops, but the result depends on the start: run it several times and keep the lowest inertia.
  • Scale the columns first; k-means suits round, similar-sized groups and puts every point, even outliers, in some cluster.

Check yourself

1The two steps of k-means are:
2Why run k-means several times from different starts?
3k-means struggles most with clusters that are

Sources

Your ticks stay in this browser. Save them as a file on the course home.

Updated 2026-11-22. Numbers in the examples are made up to show the idea unless a source is given. Simulations run in your browser; nothing you type is sent anywhere.