K-means initialisation and local minima
Where K-means drops its first guesses decides which answer it finds — a bad start gets stuck in a bad grouping, and k-means++ with restarts is the standard fix.
- 7 min read
- 3 reading levels
- Published
Read these first
On this page 5
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
K-means can settle into a bad answer and stay there, and where its first guesses land decides which answer you get.
Imagine a town council placing three water taps. Each house fetches water from its nearest tap. Every month, each tap is moved to the middle of the houses using it. Repeat this, and the taps settle into stable spots.
Here is the trap. If two taps start in the same colony, they split that colony between them. The third tap then serves the other two colonies alone. Nobody benefits from moving, so the arrangement freezes — stable, but wrong.
That frozen-but-wrong arrangement is called a local minimum: a solution no small change can improve, even though a better solution exists elsewhere.
Why this matters
K-means works exactly like those taps. It starts from guessed centre points and improves them step by step. It always stops at a stable answer. It does not promise the best answer.
Run it twice with different starting spots and you can get two different groupings of the same data. That surprises almost everyone the first time. It is not a bug — it is the algorithm's honest nature.
How it works
bad start: good start:
colony A x x <- two centres colony A x
colony B fight over A colony B x
colony C x colony C x
B and C share one centre one centre per colony
forever. Stable. Wrong. Stable. Right.Two defences are standard, and both are switched on by default in modern tools.
First, k-means++: instead of fully random starts, pick starting centres that are spread far apart from each other. Spread-out starts rarely gang up on one colony.
Second, restarts: run the whole thing several times from different starts, and keep the run whose houses walk the least total distance.
A real example you have seen
Photo apps group faces without names — that is clustering. When the app shows the same friend as two separate "people", a grouping settled badly. Rerunning the grouping often merges them, because a different start found a better arrangement.
Remember this
- K-means always stops at a stable answer, not always the best one.
- A bad start can split one true group and merge two others.
- k-means++ spreads the starts; restarts keep the best of many runs. Use both.
What to learn next
- How many clusters? — the other big K-means decision, and the tools for it.
- Gaussian mixture models — soft membership instead of hard walls.
- Clustering basics — the parent lesson, if you landed here early.
Developer — Code and libraries.
Setup
pip install scikit-learnOutputs verified with scikit-learn 1.7.2 and numpy 1.26.4 on CPU. Inertia values may differ in the last digit on other platforms.
Watching K-means get stuck
The score to watch is inertia: the summed squared distance from every point to its assigned centre. Lower is better. Same data, four different random starts:
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=150, centers=3, cluster_std=1.0, random_state=7)
# One random start, no retries. Each seed is a different roll of the dice.
for seed in range(4):
km = KMeans(n_clusters=3, init="random", n_init=1, random_state=seed)
km.fit(X)
print(f"seed {seed}: final inertia = {km.inertia_:.1f}")
# The default settings: smarter spread-out starts, kept if better.
best = KMeans(n_clusters=3, init="k-means++", n_init=10, random_state=0).fit(X)
print(f"k-means++ with n_init=10: inertia = {best.inertia_:.1f}")seed 0: final inertia = 271.5 seed 1: final inertia = 271.5 seed 2: final inertia = 271.5 seed 3: final inertia = 1472.6 k-means++ with n_init=10: inertia = 271.5
The walkthrough
Seed 3 landed in a local minimum. Its inertia is more than five times worse than the others. The algorithm ran to completion and reported success. Nothing warns you — 1472.6 looks like an ordinary number until you compare runs.
init="random", n_init=1 re-creates the fragile old behaviour on purpose. Three of four seeds got lucky here. On messier, higher-dimensional data, the failure rate climbs sharply.
init="k-means++" picks each new starting centre with probability tilted toward points far from the centres already chosen. Spread-out starts, dramatically fewer collapses.
n_init=10 runs everything ten times and keeps the lowest-inertia run. Since scikit-learn 1.4 the default is n_init="auto": one run for k-means++ starts, ten for random starts. The single k-means++ run is usually fine; raise it when clusters look unstable.
Common mistakes
Trusting one run on important data. Fit twice with different random_state values. If the two groupings disagree, believe neither yet — raise n_init or question n_clusters.
Comparing inertia across different k. Inertia always falls as n_clusters rises, so a lower inertia at higher k proves nothing. Only compare inertia between runs with the same k. Choosing k is its own problem — see How many clusters?.
Forgetting to scale features. A column measured in rupees swamps a column measured in years. Distances decide everything in K-means, so put StandardScaler in front.
Fixing random_state and calling the result stable. A fixed seed makes results repeatable — it does not make them good. Vary the seed when auditing stability; fix it when shipping.
Try it yourself
Set cluster_std=2.5 in make_blobs and rerun. Count how many of the four seeds now get stuck. Then find the smallest n_init that reliably reaches the best inertia with init="random".
What to learn next
- How many clusters? — the other big K-means decision, and the tools for it.
- Gaussian mixture models — soft membership instead of hard walls.
- Clustering basics — the parent lesson, if you landed here early.
Researcher — Mathematics and papers.
The objective and why it is hard
K-means minimises within-cluster sum of squares:
$$ J(C, \mu) = \sum_{i=1}^{n} \min_{j \in {1..k}} \lVert x_i - \mu_j \rVert^2 $$
Where:
- $x_i \in \mathbb{R}^d$ — the $i$-th data point, $n$ points total.
- $\mu_j \in \mathbb{R}^d$ — the centre of cluster $j$, $k$ clusters total.
- $C$ — the assignment of points to clusters; $J$ is the inertia scikit-learn reports.
Minimising $J$ exactly is NP-hard, even for $k=2$ (Aloise et al., 2009) and even in the plane for general $k$ (Mahajan et al., 2009). Every practical run is therefore a heuristic descent.
Lloyd's algorithm (Lloyd, 1957, published 1982) alternates two coordinate-wise minimisations: assign each point to its nearest centre (the $C$ step), then move each centre to the mean of its members (the $\mu$ step). Each step weakly decreases $J$, and the number of distinct partitions is finite, so the procedure terminates — at a stationary point of a non-convex objective. Cost per iteration is $O(nkd)$.
k-means++ and its guarantee
Arthur and Vassilvitskii (2007), k-means++: the advantages of careful seeding, choose the first centre uniformly, then each next centre with probability proportional to $D(x)^2$ — the squared distance from $x$ to its nearest already-chosen centre.
The guarantee: the expected cost of the seeding alone satisfies $\mathbb{E}[J] \le 8(\ln k + 2)\, J_{\text{OPT}}$, an $O(\log k)$ approximation before Lloyd descent even starts. Uniform seeding has unboundedly bad worst cases.
scikit-learn implements the greedy variant from the same paper: at each of the $k$ steps it samples $2 + \lfloor \log k \rfloor$ candidates and keeps the one that reduces cost most. Empirically stronger, though the clean bound is proved for the non-greedy version.
Variants worth knowing
- k-means‖ (Bahmani et al., 2012) — oversampling-based parallel seeding for distributed settings; a handful of passes replaces $k$ sequential ones.
- Mini-batch K-means (Sculley, 2010) — stochastic centre updates on small batches; slightly worse $J$, far faster at large $n$.
- Hartigan–Wong moves single points between clusters and escapes some Lloyd fixed points.
- Elkan acceleration uses the triangle inequality to skip distance computations — identical result, fewer FLOPs. scikit-learn selects it for dense data automatically.
Celebi et al. (2013), A comparative study of efficient initialization methods for the k-means clustering algorithm, is the useful empirical survey. Its blunt conclusion: seeding and restarts dominate every other tweak.
What to learn next
- How many clusters? — the other big K-means decision, and the tools for it.
- Gaussian mixture models — soft membership instead of hard walls.
- Clustering basics — the parent lesson, if you landed here early.