Interactive guide
Grouping points that were never labeled
K-means never gets told which point belongs to which group. It just repeats one rule (assign, then re-center) until nothing moves. Place your own starting centroids below and watch it happen.
One rule, repeated until it settles
Pick K centroids to start. Every point joins whichever centroid is closest to it; that's the only "decision" in the whole algorithm. Then each centroid moves to the average position of the points that just joined it. Assign, then re-center. That's the entire algorithm, run over and over.
What's being minimized is inertia: the total squared distance from every point to its own centroid. Each full round can only hold inertia steady or shrink it, never increase it, so it always settles somewhere. The question this page is really about is where it settles, and whether that's the best possible grouping, or just the nearest one to where you started.
60 points below were generated from 4 natural groups, but k-means is never told that. Choose K yourself and see what it finds, or press New random data to try a fresh layout with a different number of groups each time.
Lloyd's algorithm
-
1
Place K centroids
Anywhere, often just K random data points. K-means is sensitive to this choice, as you'll see below.
-
2
Assign every point to its nearest centroid
Straight-line distance. This splits the space into regions, one per centroid.
-
3
Move each centroid to its group's mean
The average x and average y of every point currently assigned to it.
-
4
Repeat until nothing moves
Once an assignment round changes no one's group, the centroids stop moving too: that's convergence.
Click to place up to K centroids
centroid dotted lines show which centroid each point is currently assigned to.
Inertia by iteration
Total squared distance from every point to its centroid; never increases, round over round.
Choosing K: the elbow curve
Best inertia found at each K, over several random restarts. The bend is where more clusters stop paying for themselves.
Try this: click Reset, place centroids badly on purpose (say, all three bunched in one corner) and run it. Then reset again and use Random init a few times in a row. K-means always converges, but not always to the same place, and never to a grouping better than the one closest to where it started. That's why real implementations run it many times from different starting points and keep the lowest-inertia result.
A smarter place to start: k-means++
Running from many random starts and keeping the best result works, but it's still gambling on luck. k-means++ fixes the actual problem instead: it changes how the starting centroids themselves get picked, so a bad start happens far less often in the first place.
The first centroid is still picked uniformly at random, same as before. Every centroid after that is picked randomly too, but weighted: a point's chance of being picked next is proportional to the square of its distance from the nearest centroid already chosen. Points sitting far from every centroid picked so far, exactly the points a still-unclaimed cluster is made of, become far more likely to get picked next.
60 points below, in 4 equally-sized clusters spaced just close enough that plain random init regularly puts two centroids in the same cluster and none in another. Step through k-means++'s own selection process and watch which points it favors.
How k-means++ picks K starting points
-
1
Pick the first centroid uniformly
Any data point, each with equal probability. No information used yet.
-
2
Measure every point's distance to its nearest chosen centroid
D(x)², recomputed after every pick. Points near an existing centroid score low.
-
3
Pick the next centroid weighted by D(x)²
Not the single farthest point, just far more likely to be picked. Still genuinely random.
-
4
Repeat until K centroids are chosen
Then hand off to ordinary Lloyd's algorithm exactly as above; only the start changes.
A tiny example, worked by hand: 5 points, A already chosen
A: already chosen bigger, darker point = bigger D(x)² = higher chance of getting picked next.
| Point | Distance from A | D(x)² | P(x) |
|---|
Pick the first centroid to begin
chosen centroid bigger, darker point = higher probability of being picked next.
Verified over 400 independent runs on this exact dataset: plain random init merges two true clusters together 38% of the time, against just 16% for k-means++, and its average final inertia (339.8) lands well above k-means++'s (256.5). Same Lloyd's algorithm from there on; the only difference is where it started.
The jargons
K-means is Lloyd’s algorithm chasing one number down — inertia — and most of the terms below describe the ways that chase can go wrong: settling into a local optimum, or never being told the right K to begin with.
The center of a cluster: literally the average position of every point currently assigned to it. Not necessarily an actual data point.
Within-cluster sum of squares: total squared distance from every point to its own centroid. The quantity k-means is minimizing.
The standard k-means procedure: alternate assigning points to the nearest centroid and moving centroids to their group's mean, until neither changes.
Reached once a full round reassigns no points. Guaranteed to happen eventually: inertia can't increase, and there are only finitely many ways to partition the points.
A stable grouping that's the best nearby (reachable from its starting centroids) but not necessarily the lowest-inertia grouping that exists. Exactly like a local minimum in gradient descent.
A smarter initialization that spreads starting centroids apart on purpose, instead of placing them uniformly at random. Makes a bad local optimum much less likely.
K-means never tells you the right K; you supply it. One common heuristic: plot inertia against K and look for the point where adding another cluster stops helping much.