K-Means Initialization, K Selection, and Failure Modes

The labels alone hide several diagnostic patterns. Each of the following is visible in the output of a single fit, and none of them shows up in the inertia number that usually gets reported alongside it.

Run K-Means five times on the same matrix and you can get several different partitions at almost identical inertia. The usual reaction is to treat the spread as noise from the random number generator and keep the best-scoring run. That reading is wrong in an interesting way. The difficulty is in the objective itself, and it has been quantified.

Lloyd's iteration can require 2^Ω(n) iterations on a data set of n points lying in the plane. Andrea Vattani proved that in 2011. The earlier bound, from Arthur and Vassilvitskii, was 2^Ω(√n), and it needed d = Ω(√n) dimensions to construct; Vattani brought the exponential blow-up down into two dimensions. Tim Roughgarden and Joshua R. Wang summarised the position in 2016: “The worst-case running time of the method is exponential in the number of points. This was first proved by Arthur and Vassilvitskii [4], and extended to the plane by Vattani [18].”

The worst case is a construction, not the typical run. But it settles what the disagreement between seeds means. The landscape the procedure descends genuinely contains competing solutions. The partition you got is the one your initialization happened to reach, and the differences between restarts are evidence about the problem you are looking at.

Choosing the cluster count folds four different questions into one number. Only the first of them is about the optimizer at all.

Can the optimizer find a strong solution? In general, provably not. Finding the optimal k-means partition is NP-hard, and it stays NP-hard at both extremes of the problem. It is NP-hard for just two clusters in general dimension: Aloise and three colleagues published that short proof in 2009, written because an earlier proof, by Drineas and colleagues in 2004, was invalid. It is also NP-hard for points in the plane with general k, which Mahajan, Nimbhorkar and Varadarajan showed in 2012. Awasthi and three colleagues set both results out: “The work of Dasgupta [11] and Aloise et al. [1] showed that Euclidean k-means is NP-hard even for k = 2. Mahajan et al. [30] also show that the k-means problem is NP-hard for points in the plane.” Restarts buy better local solutions. They never convert the heuristic into a guarantee, and no count of them is a proof of optimality.

How much compression is acceptable? More clusters lower distortion and add complexity, and that tradeoff has no optimum inside the data. Does the partition persist? Seeds, resamples and preprocessing changes are the test. Can anyone act on the groups? Operational capacity and real domain distinctions constrain the useful range. That last constraint is about the organisation, not about the population.

Each method answers a narrower question than “How many real groups exist?”, and for three of them there is a measured track record to consult rather than an intuition.

The elbow curve plots inertia against K and looks for diminishing returns. It always trends downward. It may show no visible bend. It depends on feature geometry, and the scaling result above moves it. It is also conspicuously absent from the literature that benchmarked stopping rules. Glenn W. Milligan and Martha C. Cooper ran a Monte Carlo study in 1985, and its abstract opens: “A Monte Carlo evaluation of 30 procedures for determining the number of clusters was conducted on artificial data sets which contained either 2, 3, 4, or 5 distinct nonoverlapping clusters.” Arbelaitz and colleagues describe the same experiment from outside it: “They used 108 synthetic datasets with a varying number of non-overlapped clusters (2, 3, 4 or 5), dimensionality (4, 6 or 8) and cluster sizes.” Two rules came out on top, and neither reads a bend off a curve. StataCorp's manual reports the outcome and acts on it: “Milligan and Cooper (1985) evaluate 30 stopping rules, singling out the Caliński–Harabasz index and the Duda–Hart index as two of the best rules.” Stata ships exactly those two rules and no elbow rule.

Silhouette analysis measures cohesion relative to the nearest competing cluster. It can compare several K values, and it favors separated compact groups, which means it can penalize meaningful overlap. It also has the strongest measured record of the internal indices. Arbelaitz and four colleagues compared 30 internal cluster validity indices across 6,480 experimental configurations — 20 real UCI data sets plus synthetic ones, three clustering algorithms (k-means, Ward and average-linkage) and three partition-similarity measures — computing each index on 156,069 partitions. Their conclusion, published in 2013: “there is not a single CVI that showed clear advantage over the rest in every context, although Silhouette index obtained the best results in many of them”. The same study injected 10% random noise and watched the average success score fall to a third of its clean value. Best available is not the same as reliable.

The gap statistic replaces eyeballing with a comparison against a null. Robert Tibshirani and two colleagues described it in 2001, in an abstract that says what it does: “The technique uses the output of any clustering algorithm (e.g. K-means or hierarchical), comparing the change in within-cluster dispersion with that expected under an appropriate reference null distribution.” Better founded, and still not a verdict. In Schubert's 2023 evaluation it chose 30 clusters where the true k was 25, and 14 to 21 clusters on uniform noise whose true k was 1. Its answers also fluctuate with the random seed.

Stability analysis compares partitions across seeds, samples or perturbations. It reveals fragile boundaries. It needs label alignment or a partition metric, it can favor coarse solutions, and it does not prove usefulness. Domain and capacity constraints connect K to the actions available. They can cap complexity, they may encode existing organizational bias, and they should be tested rather than assumed.

Compare a bounded range of candidates, and preserve conflicting evidence. Bound K by domain limits, sample size and the smallest group anyone could act on. Run K-Means++ with enough independent initializations to expose local variation. Record inertia, silhouette distribution, cluster sizes and boundary margins. Repeat on resamples and on plausible preprocessing variants, then align the partitions. Check that each candidate supports distinct, feasible and ethical actions. Write down why the simpler and the more complex K values were rejected.

Two of those steps carry the anchored results. When collecting diagnostics, prefer a rule with a published track record. The Caliński–Harabasz variance-ratio index and the Duda–Hart Je(2)/Je(1) index have had one since the 1985 benchmark by Milligan and Cooper, and the gap statistic compares against a reference null distribution instead of against your eye. When testing perturbations, treat scaling as one of them: rescaling the data by α multiplies SSE by α² and moves the geometric optimum, so the scaling you fitted on belongs in the record. So does the seed. Schubert's own table marks the gap statistic's answers on several toy sets as results that fluctuate with random seeds, and an undocumented seed makes a K value unreproducible even when the pipeline is.

A dataset may support stable broad regimes and several plausible finer subdivisions. Forcing one count can hide that hierarchy or uncertainty. The final choice should reflect the level at which decisions remain stable and useful. When no candidate survives perturbation and review, report the absence of reliable partition evidence.

Stability is a narrower instrument than it looks. Idealized K-Means stays stable on asymmetric data even when K is wrong, and Ulrike von Luxburg's survey of the method puts it flatly: “Instability of the wrong number of clusters only occurs in symmetric data sets.” A stable K can therefore be a wrong K. That is one more reason to report the range that survived rather than the single number that scored best.