k-means Clustering: Where You Start Decides What You Find

k-means is the first clustering algorithm anyone learns, and it has a property nobody mentions: it finds a different answer depending on where it happens to begin. Turn the dial below and watch the same points, cut the same number of ways, settle somewhere else.

Worked example — k-means Clustering: Where You Start Decides What You Find

Within-cluster sum of squares	1.0989
Iterations to converge	2
How far apart those are	430.8%
Different answers found	3 of 24
So this start is	the best found

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — k-means Clustering: Where You Start Decides What You Find

k-means looks for k groups by repeating two steps until nothing moves: put every point with the nearest centre, then move each centre to the mean of what it caught. What it is trying to minimise is the within-cluster sum of squares, the total squared distance from every point to its own centre, and each of the two steps can only lower it — which is the whole proof that the algorithm stops.

What each symbol means

k: how many clusters you asked for, which nothing in the data tells you
WCSS: the total squared distance from each point to its own centre

Assumes: That a cluster is a round blob of roughly equal size, because squared Euclidean distance to a mean cannot express anything else. Elongated, nested or very unequal groups are not found badly by k-means; they are not the kind of thing it is looking for.

Every one of those runs converged 🖖

Leave the three blobs and k = 3 alone and walk the starting-position dial from 1 to 24. Twenty-two of the starts settle at 1.0989. Numbers 17 and 21 settle at 5.8172 and 5.8331, which is 5.3 times worse: they merge two of the blobs and cut the third in half. Nothing went wrong in those two runs. Lloyd’s algorithm is guaranteed to converge — the within-cluster sum of squares falls at every step and cannot fall for ever, so it must stop, and in 1,536 runs swept across every set, every k and both initialisations, not one failed to. What it is not guaranteed to do is stop anywhere good. So "the algorithm converged" is a statement about arithmetic rather than about your data, and if you ran k-means once you have no way of telling which of these two answers you are holding.

k-means++ halves the damage and promises nothing 🖖

Switch How it starts to k-means++ and the spread on this set collapses to nothing: all twenty-four starts find 1.0989. That is the fix everyone reaches for, and it works by spreading the initial centres out instead of dropping them at random points. But the improvement is statistical, not a guarantee, and it is worth knowing by how much. Measured over 112 combinations of point set, sample size and k: k-means++ found a strictly better optimum than random starting in 38 of them, random did better in 17, and the two tied in 57. The average spread across twenty-four starts fell from 55.5% to 31.7%. So it roughly halves how wrong an unlucky run can be, and in one case out of six you would have done better throwing darts. Set the ring to 90 points and k = 5 for one of those: random reaches 0.9884 and k-means++ stops at 1.0213.

A stable, balanced, confident answer to a question with no answer 🖖

Load the last preset. The points are a regular lattice with no clusters in it whatsoever, and k-means divides them into four groups of exactly 25. Now look at what every diagnostic you have says about that result. It converged, in eleven iterations. It is stable: all twenty-four starting positions reach the same answer, so restarting tells you nothing is wrong. The clusters are perfectly balanced, which is what a good clustering usually looks like. Three separate signals point the same way, and there is nothing there. This is the part of clustering that has no technical fix: k-means answers the question "where would k centres go" and it always has an answer, whether or not the question "how many groups are in this data" has one at all.

Problem solved in full

You do not know how many clusters your data has, so you plan to read it off the elbow in the score curve. Try that reading on all four point sets and count how often it is right. The bottom panel gives you the best score at every k from 1 to 8, with the drop from the previous k drawn behind it.

Open this problem in the tool
1. First, why an elbow rather than a minimum. Set the point set to Three blobs and read the curve: 10.3978 at k = 1, then 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366. It never rises. It cannot: any clustering into k groups can be turned into one with k + 1 groups by splitting a group, and splitting can only move points closer to their own centre. Push k as far as the number of points and every point is its own cluster with the score exactly 0.
  
  $WCSS (k) = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}, WCSS (k + 1) \leq WCSS (k) three blobs : 10.3978, 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366$
2. So the curve has no minimum to find, and the reading has to be about the drops instead. On the blobs they go 46.0%, then 80.4%, then 15.9%, 12.9%, 14.6%, 11.6%, 11.7%. The drop after k = 3 is a fifth of the drop into it — a collapse by a factor of 5.06 — and k = 3 is exactly how the data was built. The method works here, and this is the case everybody is shown.
  
  $drop (k) = 1 - \frac{WCSS ( k + 1 )}{WCSS ( k )}, elbow = ar g max_{k} \frac{drop ( k - 1 )}{drop ( k )} three blobs : 46 . 0%, 80 . 4%, 15 . 9%, 12 . 9%, 14 . 6%, 11 . 6%, 11 . 7% \Rightarrow k = 3, \times 5.06$
3. Now the Lattice, which has no clusters at all. Its drops are 41.6%, 34.1%, 36.8%, 16.4%, 16.9%, 12.8%, 15.7%. There is a collapse by a factor of 2.25 after k = 4, which is exactly the shape you were told to look for. The elbow reading returns "four clusters" for a set with none.
  
  $lattice : 41 . 6%, 34 . 1%, 36 . 8%, 16 . 4%, 16 . 9%, 12 . 8%, 15 . 7% \Rightarrow k = 4, \times 2.25$
4. The Ring next, where there genuinely are two groups. Its drops run 37.2%, 32.8%, 38.5%, 33.4%, 43.1%, 25.3%, 15.3% — no trend at all, and then two falls at the end. The sharpest collapse is after k = 6. The reading says six; the answer is two.
  
  $ring : 37 . 2%, 32 . 8%, 38 . 5%, 33 . 4%, 43 . 1%, 25 . 3%, 15 . 3% \Rightarrow k = 6, \times 1.70$
5. And Uneven, three clusters of different sizes: 43.8%, 48.4%, 35.4%, 24.7%, 16.1%, 14.4%, 21.8%. A smooth decline with no collapse anywhere — the sharpest is a factor of 1.53, which is not a corner. The reading gives you nothing, on data that does have three clusters in it.
  
  $uneven : 43 . 8%, 48 . 4%, 35 . 4%, 24 . 7%, 16 . 1%, 14 . 4%, 21 . 8% \Rightarrow k = 5, \times 1.53$
Answer

One right out of four: correct on the blobs, four clusters invented on the lattice, six proposed for the ring’s two, and silence on the uneven set. The pattern is not random. The elbow is sharp exactly when the clusters are round, similarly sized and well separated — which is when you could have counted them by looking. It fades on every set where you actually needed the help. That is worth knowing before you use the curve to defend a number to somebody, and it is why the elbow sits beside the silhouette score, the gap statistic and information criteria rather than above them. None of those is on this page, and each of them is a different way of asking the same question the score curve cannot answer: not "where would k centres go", which always has an answer, but "are there groups here at all".

$set three blobs lattice ring uneven elbow says 3465 truth 3023 sharpness \times 5.06 \times 2.25 \times 1.70 \times 1.53$

Learning path

Fitting a line to data

References (3)

The algorithm itself. Written in 1957 for quantising a signal into levels, circulated as a Bell Labs memorandum, and not published for twenty-five years: S. P. Lloyd, “Least squares quantization in PCM.” IEEE Transactions on Information Theory 28(2), 129–137, 1982.
The initialisation the second insight block measures — and the source of the bound that makes it worth using, which is a guarantee about the EXPECTED score rather than about any single run: D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding.” In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’07), 1027–1035. SIAM, 2007.
Where the elbow reading comes from, and it was proposed with more caution than it is usually repeated with: R. L. Thorndike, “Who belongs in the family?” Psychometrika 18(4), 267–276, 1953.

By the 42Math team · Reviewed against published sources. Corrections welcome.