Why can two k-means runs on the same data return different clusterings?

## The instability is structural, not a bug k-means minimises the within-cluster sum of squares, `WCSS = sum over clusters of sum over its points of ||x - centroid||^2`. Lloyd's algorithm attacks that objective by alternating an assignment step and a recentring step, and each step can only lower the objective. That is a descent guarantee, and descent guarantees deliver a **local** minimum: a configuration no single step can improve. It says nothing about whether some completely different configuration scores lower. Exact minimisation of WCSS is computationally intractable in general, which is why the field lives with a heuristic that has to be started somewhere. Where it is started decides which basin it falls into. Two runs on the same table, differing only in their random initial centroids, can produce genuinely different groupings with genuinely different objective values — one may merge two real groups and split a third, the other may not. ## Restarts: the blunt fix Run the whole fit several times from different random starts and keep the best result. "Best" here must mean **lowest within-cluster sum of squares**, not the one whose clusters look nicest, because WCSS is the only thing the algorithm claims to optimise and it is the only comparison that is fair between runs. A concrete shape for this: on a 40,000-row product-catalogue table you fit k = 8 ten times with different seeds, record the final WCSS of each, and keep the fit with the smallest value. Two things are worth reading off that experiment beyond the winning model: - **The spread of the ten WCSS values is diagnostic.** Ten values within a hair of each other means the structure is strong enough that any sensible start finds it. A wide spread means the objective surface is bumpy and your "clusters" are partly an artefact of initialisation. - **The stability of the assignments is also diagnostic.** If the winning run and the runner-up disagree about which products go together, no downstream team should be told these are stable segments. The comparison is only valid when k, the data and the feature scaling are identical across runs. WCSS falls automatically as k rises, so it can never be used to compare fits with different numbers of clusters. ## k-means++: the smarter fix Uniform random initialisation frequently drops two or more centres inside the same dense region, which is exactly the situation that produces a bad local optimum: one true group ends up split between two centres while another true group has none. k-means++ seeds with a distance-weighted rule instead: 1. Choose the first centre uniformly at random from the data points. 2. For every point x, compute `D(x)`, the distance from x to the nearest centre chosen so far. 3. Choose the next centre from the data points, with the probability of picking x proportional to `D(x)^2`. 4. Repeat step 2 and 3 until k centres are chosen, then run Lloyd's algorithm from those centres. The squared weighting makes far-away regions overwhelmingly likely to be picked next, so the initial centres are spread across the data rather than clumped. It is still randomised — that matters, because the purely deterministic alternative of always taking the furthest point walks straight into outliers, picking a lone extreme record as a cluster centre every time. The randomised D-squared rule makes an outlier likely but not certain to be chosen. k-means++ also carries a theoretical guarantee: the expected within-cluster sum of squares of the seeding alone is within a factor of order `log k` of the optimal value, before Lloyd's algorithm has even started refining it. In practice it both improves the average result and shrinks the variance between runs, so fewer restarts are needed to be confident. Note what k-means++ is and is not. It is a **seeding rule**, not a different clustering algorithm — after seeding, the same Lloyd iteration runs. ## What none of this fixes Restarts and better seeding attack one specific failure: landing in a poor local optimum of the objective. They do nothing about the objective itself being the wrong description of your data. If the true groups are not compact, roughly round blobs, the global optimum of WCSS would still be a clustering you do not want, and finding it more reliably just means reliably getting the wrong answer. Similarly, if features are on wildly different numeric scales, every restart optimises the same distorted distance. ## Reproducibility versus stability Fixing the random seed makes a pipeline reproducible: the same code on the same data gives the same clusters tomorrow. That is a good engineering practice and a bad statistical argument. A pinned seed hides variability rather than removing it, and a segmentation that changes character when the seed changes is a weak segmentation regardless of which single seed you froze. Measure the variability first, then pin the seed.