K-Means Clustering

K-means clustering splits n unlabeled points into k groups by alternating two steps: assign every point to the nearest centroid, then move every centroid to the mean of the points that chose it. It stops when an assignment changes nothing. The quantity it lowers is inertia: the total squared distance from each point to its own centroid.

Picture three flags planted somewhere on a field full of people. Everyone walks to the nearest flag. Each flag then slides to the middle of the crowd that gathered around it, which leaves some people closer to a different flag, so everyone walks again. Two rules, repeated until nobody moves. What makes this worth a lesson is not that it works. It is that it always stops — the proof takes two sentences — and that where it stops depends on both the data and where you planted the flags.

How K-Means Clustering Works

Start with what is missing. Nothing in the input says which group anything belongs to. The points are training data, but there are no supplied class labels or answer key. You hand the algorithm a pile of points and one number, k, and it hands back a partition. That is the whole contract, and it is why the points on the canvas open gray: an unlabeled point is the honest starting state.

The algorithm keeps k centroids, which are locations rather than data points. They can sit anywhere, including where no point lives. Two steps take turns:

• Assign. Every point looks at all k centroids and joins the nearest one. This step fits nothing and computes no gradient; for 15 points and 3 centroids it is 45 distance comparisons and the nearest one takes the point.
• Update. Every centroid moves to the mean of the points that just chose it. Not the median, not a random member. The mean, and that choice matters more than it looks.

The number that ties them together is inertia, the sum over all points of the squared distance to that point's own centroid. Note the squared: inertia lives in squared units, so it is not a distance and a value of 28.80 does not mean "28.80 apart from anything."

Now the argument that makes the loop finite. Assign sends each point to a centroid at least as close as its current one, so inertia cannot rise. Update sits each centroid at the mean of its members, and the mean is the unique location minimizing that set's summed squared distances, so inertia cannot rise there either. Better: if a centroid actually moves, the total strictly falls.

That much is not yet a proof. A quantity that never rises still leaves room for the loop to wander forever among labelings that all score the same. What closes the argument is one line of the code, the tie-break: ties go to the lowest-indexed centroid, so the labeling is a function of the centroids, and there are only finitely many labelings of n points into k groups. Some round therefore has to repeat one it already produced, and a repeat means no centroid moved, because a centroid that moved would have strictly lowered the total. Nothing moved is exactly what the break tests. No tolerance, no iteration budget, no convergence criterion to tune.

There is a geometric consequence worth staring at. Because a point joins whichever centroid is nearest, the partition of the plane is a Voronoi diagram of the k centroids: every boundary is a perpendicular bisector between two centroids, which is to say every boundary is a straight line. K-means cannot express a curved region, a ring, or a crescent. It can only ever hand you a plane cut into straight-edged cells. Remember that when you get to the rings.

That also settles when the algorithm applies, before you have looked at a single result. K-means wants numeric features where Euclidean distance means something, and groups that are roughly round, comparably sized, and measured on comparable scales. Categorical columns, nested or elongated shapes, and one column with a hundred times the variance of another are where it can go wrong in ways no amount of restarting will fix — well-separated groups may still come out right, so check the result against what the features mean.

K-Means Step by Step

The default run: fifteen points in three obvious blobs (five upper-left, five lower-left, and five stacked vertically on the right) with k = 3 and three starting centroids parked down the middle at (0, 2), (0, 0), and (0, −2). Those three starting positions belong to no blob. They are what a guess looks like when you have no idea.

1. Round 1, assign. Each point takes the nearest of the three. The middle-of-the-field start makes a mess of it: c₀ collects the whole upper-left blob plus (4, 3) and (4, 1) from the right blob, seven in all. c₁ gets just (5, 0) and (4, −1). c₂ gets the whole lower-left blob plus (4, −3), six in all. The right blob has been torn into three pieces. Inertia: 265.00.

2. Round 1, update. Each centroid moves to its crowd's mean. c₀ slides left and up to (−1.57, 3.00), dragged by five upper-left points against two stragglers from the right. c₁ jumps right to (4.50, −0.50), the mean of its two points. c₂ settles at (−2.50, −3.33). Nothing has been relabeled yet — only the centroids moved — and inertia drops to 151.55. This is the beat where the picture goes visibly stale: (4, 3) still belongs to c₀ even though c₁ is now closer to it.

3. Round 2, assign. Three points change hands: (4, 3), (4, 1), and (4, −3) all leave the left-hand centroids for c₁, which is now parked in the right blob. Each one moved to a closer centroid, so the total could only fall, to 64.60. The clusters are now 5 / 5 / 5, the split a human would have drawn.

4. Round 2, update. The centroids settle into their blobs: c₀ to (−3.80, 3.40), c₁ to (4.20, 0.00), c₂ to (−3.80, −3.40). Inertia: 28.80.

5. Round 3, assign. Nobody moves. Zero of fifteen points change cluster, the guard new == labels is true, and the loop breaks. Run the two steps ten more times and they would reproduce exactly this. It is a fixed point, not a pause.

Then the lesson does the thing a single run can never do: it restarts. Same fifteen points, same k = 3, same two steps, and a different guess: three of the data points, two of them inside the tall right blob, at (−4, −4), (4, 3) and (4, −3). Three rounds later it halts just as firmly, at inertia 133.10, with the two left blobs fused into one ten-point cluster, a cluster holding the single point (4, 3), and a third holding the rest of the right blob. Both results are fixed points. Both are what the algorithm does.

On the canvas: the inertia staircase in the left column can only ever step down, and the beat where it flattens is the halt. The colored wash on the plane is the Voronoi partition the current centroids induce. During an update beat it deliberately keeps the old geometry, so you can watch points end up on the wrong side of a boundary, which is precisely why another round is needed.

Why K-Means Always Stops, and Why That Isn't Enough

Convergence is guaranteed. The answer is not. Those are different claims, and conflating them is the single most expensive misreading of this algorithm.

Enumerate every way to start from three of these fifteen points, all 455 of them, and 332 land at 28.80, the split you would have drawn by hand. The other 123 stop somewhere worse, as high as 215.53. From inside a single run you cannot tell which happened. The loop halts, the inertia stops falling, and nothing on the screen distinguishes "this is the best partition" from "this is a partition I cannot escape." The stopping condition tests whether anything changed, and a bad answer changes nothing just as reliably as a good one.

This motivates running k-means from several starts and keeping the lowest inertia, and why the default initialization is now k-means++, which spreads the initial centroids by picking each new one with probability proportional to its squared distance from the nearest existing one. Neither trick makes the algorithm find the global optimum. Both make the bad basins less likely.

The working recipe that follows: scale the features, run the algorithm from many starts and keep the lowest inertia, check that the partition is stable across those starts instead of trusting one, and choose k with a silhouette score or domain knowledge rather than with inertia. sklearn defaults to k-means++ seeding, but with n_init="auto" that is a single run — set n_init explicitly if you want restarts, and compare the partitions across them yourself if you want evidence of stability. Nothing in the library does the last step for you either.

Time and Space Complexity of K-Means

The per-round time complexity is the part you can reason about: n points, k centroids, d dimensions, one distance each. The round count is the part you cannot. In practice it is small and people quote O(n · k · d · i) with i "the number of iterations," which quietly hides the only genuinely hard question.

One thing the table does not break out, because k-means does not either: this loop is the fitting. The centroids are learned parameters, which is why the library call is literally fit. Labeling a new point afterwards costs one pass over k centroids, so the expensive work is behind you. Compare kNN, where it is all still in front of you.

The animated version runs plain Lloyd's algorithm with a hand-placed start, capped at 12 rounds for the animation's sake. The algorithm itself has no such cap, and the status panel says so if a run ever reaches it. No configuration shipped here comes close.

Edge Cases

• An empty cluster. Place a centroid where it wins nothing and the mean of its members is undefined. The code shown guards it and leaves the centroid where it is, so it can sit out the entire run — ask for k = 4 on this data and 75 of the 1365 possible starts end with a centroid holding zero points, a cluster you asked for and did not get. Real libraries relocate it instead, usually to the point contributing most to inertia.
• An exact tie. A point equidistant from two centroids joins the lower-indexed one. That looks like a detail and is not: the tie-break has to be deterministic, or the assignment stops being a function of the centroids and the halting argument collapses.
• A start that is already a fixed point. Seed the centroids at the three blob means and the first update leaves them unchanged. Because the displayed code initializes labels as unknown, the following assignment check detects the fixed point.
• Fewer distinct points than k. Two centroids at the same location split the ties by index, so one of them wins every point and the other starves. The config panel refuses duplicate starting positions for exactly this reason.
• Shapes that are not blobs. Two concentric rings share a center, and no straight cut separates them. All 153 possible two-point starts on the rings preset end with both rings sliced through — not because they were unlucky, but because a partition into k Voronoi cells cannot produce a ring. When the answer is inexpressible, converging tells you nothing.

Common Mistakes

• Using inertia to choose k. The globally optimal inertia cannot increase as k increases, though it can stay equal; separate local runs need not follow that ordering: the best k = 4 partition of this data scores 15.33 against k = 3's 28.80, and k = n scores exactly 0. Minimizing the objective picks the degenerate answer every time. The elbow method, silhouette scores, and domain knowledge exist because the objective cannot do this job.
• Running it once and believing the result. A single converged run gives you no evidence about which basin you landed in. If your pipeline calls k-means once with a random start, it is sampling from a distribution of answers, one of them at a time.
• Swapping the mean for the median because the median resists outliers. The mean is what minimizes summed squared distance, which is the quantity the halting proof tracks. Use the median and inertia can rise. Paired with assignment by absolute (L1) distance it becomes a real algorithm, k-medians, which minimizes summed absolute distance instead: a different answer to a different question.
• Expecting balanced clusters. Nothing in the objective rewards equal sizes. On this data the second run happily produces clusters of 10, 4, and 1.
• Feeding it unscaled features. Distance treats every dimension alike, so a column measured in dollars will drown a column measured in years. Scaling is preprocessing, and skipping it is the most common way to get a clustering that reflects your units instead of your data.

A Note on Simplification

This is Lloyd's algorithm exactly as it runs: the two steps, the halting condition, and the guard on empty clusters are all real. What is left out is everything that wraps it in production: k-means++ seeding, multiple restarts keeping the best inertia, Elkan's and mini-batch variants that avoid recomputing every distance, and the feature scaling that has to happen before any of it. Two dimensions and fifteen points also flatter the algorithm; in high dimensions distances concentrate and "nearest centroid" becomes a much weaker signal. Treat this as an explainer for the mechanism and its failure modes, not as a substitute for reading how a real implementation is configured.