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
- Choose k and place k starting centres (k-means++ spreads them out sensibly).
- Assign step: every point joins the cluster of its nearest centre.
- Move step: every centre moves to the mean of the points assigned to it.
- Repeat assign and move until no point changes cluster.
- Each step can only lower the total squared distance from points to their centres, so it always stops.
- It may stop in a poor arrangement, depending on the start, so run it several times and keep the lowest total distance.
- Choose k with the "elbow" of total distance against k, or with a silhouette score.
Key points
- Objective: minimise the sum of squared distances from each point to its centre.
- Assign = nearest centre; move = mean of members. Alternate until stable.
- Assumes round clusters of similar size; struggles with long, curved or uneven clusters.
- Scale features first: k-means uses distances, so a feature with large numbers would decide the clusters.
- Results depend on the start: use k-means++ and several restarts.
- It is the "hard" version of a Gaussian mixture with EM (later in this unit).
Common mistakes
- Running it once from random starts and trusting the result.
- Forgetting to scale features, so the clusters are decided by whichever feature has the largest numbers.
- Using it on shapes like two interlocking moons.
- Treating the number of clusters k as known when it isn't. Try several values and compare the results.
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.