difficulty 2/5
K-means
Pick k centres, assign every point to the nearest, move each centre to the mean of what it caught, repeat. It always converges and it can converge somewhere arbitrarily bad.
Intuition
You have points and no labels, and a suspicion they fall into groups. K-means turns that suspicion into an objective: choose k centres so that the total squared distance from every point to its nearest centre is as small as possible [2, §2.3.2].
Then it solves that objective badly, on purpose, because solving it properly is intractable. The algorithm alternates two steps that each obviously improve the score — put every point with its nearest centre, then move every centre to the middle of its points — and stops when neither changes anything.
That guarantees it stops. It guarantees nothing about where. The whole character of k-means follows from that gap: it is fast, it is easy, it always returns an answer, and the answer can be ten times worse than the best one without anything in the output saying so.
Formal definition
How it works
Where it's used
Why & when
Worked example
Pitfalls
Check yourself
3 questions
The questions on this page come with access. They are graded on the server, so the answers stay there until you have given yours.
Sources
- Theoretical Analysis of the k-Means Algorithm — A Survey (2016)paperhttps://ar5iv.labs.arxiv.org/html/1602.08254
- scikit-learn User Guide — Clusteringdocs · retrieved 2026-09-06https://scikit-learn.org/stable/modules/clustering.html
- scikit-learn — KMeansdocs · retrieved 2026-10-07https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html