k-means clustering

k-means groups unlabelled points into k clusters by repeating two steps: assign every point to its nearest centre, then move each centre to the average of its points.

Why it matters

Often there are no labels at all: customers, documents or images that you want to group by similarity. k-means is the simplest and fastest clustering method, a standard first look at unlabelled data, and a building block elsewhere: compressing colours, initialising other models, and building the codebooks behind vector quantisation.

The idea

k-means groups points into k clusters by repeating two steps: assign each point to its nearest centre, then move each centre to the average of its points.

Placing k ice-cream vans on a beach. Each customer walks to the nearest van. Each van moves to the middle of its customers. Repeat until nobody moves.

Vans placed badly at the start can get stuck in a poor arrangement. k-means depends on its starting centres, so run it several times. It also assumes round clusters of similar size.

How it works

  1. Choose k and place k starting centres (k-means++ spreads them out sensibly).
  2. Assign step: every point joins the cluster of its nearest centre.
  3. Move step: every centre moves to the mean of the points assigned to it.
  4. Repeat assign and move until no point changes cluster.
  5. Each step can only lower the total squared distance from points to their centres, so it always stops.
  6. It may stop in a poor arrangement, depending on the start, so run it several times and keep the lowest total distance.
  7. Choose k with the "elbow" of total distance against k, or with a silhouette score.

Key points

Common mistakes

Not true: Starting centres: they do not affect the clusters k-means ends with.
In fact: The result depends on the starting centres and can be a poor one. Run it several times, or choose the start with k-means++.

Not true: Cluster shape: k-means handles long, curved shapes (two interlocking moons) as well as round ones.
In fact: k-means assumes round clusters of similar size. On long, curved or interlocking shapes it cuts straight across them.

Part of Unit 2: Classical ML, built by you in the free ML Foundations course.