What you’ll learn

• the k-means objective, and why the two update steps fall out of it
• a proof that Lloyd’s algorithm terminates, and why that does not mean it finds the best answer
• a full iteration worked by hand on six points
• why n_initn_init exists, measured: inertia 302.46 versus 971.25 from one unlucky start
• the elbow and the silhouette, and which one actually answers “how many clusters?”
• three geometries where k-means fails, with adjusted Rand indices attached
• k-means++ , MiniBatchKMeans, and when each pays off

Intuition

k-means answers one question: if you had to replace every point with one of $k$ representative points, which $k$ would lose the least information?

Those representatives are the centroids. Once you have them, every point belongs to whichever is nearest. Once you have the assignment, the best possible representative for a group is its mean. Neither half can be solved without the other, so the algorithm alternates: fix the centroids and reassign, fix the assignment and recompute the centroids. Repeat until nothing moves.

That is the entire algorithm. Everything else on this page is consequences of it.

  flowchart TD
  A["Pick k initial centroids
(k-means++ by default)"] --> B["ASSIGN
each point to its nearest centroid"]
  B --> C["UPDATE
each centroid to the mean of its points"]
  C --> D{"Did any assignment change?"}
  D -->|"yes"| B
  D -->|"no"| E["Converged.
Record inertia."]
  E --> F{"Ran n_init times?"}
  F -->|"no"| A
  F -->|"yes"| G["Keep the run with the lowest inertia"]

The math

Let $C_1, \dots, C_k$ partition the $n$ points and let $\boldsymbol\mu_j$ be the centroid of $C_j$. k-means minimises the within-cluster sum of squares, which scikit-learn calls inertia:

Both update rules are the exact minimisers of $J$ with the other variable held fixed.

The assignment step. With the centroids fixed, $J$ is a sum of independent per-point terms. Each is minimised by choosing the nearest centroid:

The update step. With the assignment fixed, differentiate the contribution of one cluster with respect to its centroid:

Setting this to zero gives $\sum_{\mathbf{x}_i \in C_j} \mathbf{x}_i = |C_j| \boldsymbol\mu_j$, so

The centroid is the mean. Not an approximation — the exact minimiser. This is also why k-means is tied to squared Euclidean distance: swap in $L_1$ and the optimal representative becomes the median, which is a different algorithm (k-medians).

Why it always stops

Both steps are guaranteed not to increase $J$:

1. The assignment step moves points only to a centroid that is nearer or equally near, so every term in the sum weakly decreases.
2. The update step replaces each centroid with the exact minimiser for its cluster, so each cluster’s contribution weakly decreases.

So $J$ is non-increasing. There are only finitely many ways to partition $n$ points into $k$ groups, and $J$ is determined by the partition. A non-increasing sequence over a finite set of values that never revisits a partition must halt. Lloyd’s algorithm always terminates, typically in a handful of iterations.

It terminates at a local minimum. There is no guarantee it is the global one, and finding the global optimum of $J$ is NP-hard even for $k = 2$. That gap is what n_initn_init exists to paper over.

Worked example by hand

Six one-dimensional points: $1, 2, 3, 10, 11, 12$. Take $k = 2$ and the deliberately awkward initial centroids $\mu_1 = 2$, $\mu_2 = 4$.

Iteration 1 — assign. Compare $|x - 2|$ against $|x - 4|$:

Iteration 1 — update.

Iteration 2 — assign. With centroids at 2 and 11, points $1, 2, 3$ are all nearer 2 (distances 1, 0, 1 against 10, 9, 8) and $10, 11, 12$ are all nearer 11. No assignment changed, so the algorithm stops.

Final inertia:

Now watch what a bad start does. Initialise at $\mu_1 = 1$, $\mu_2 = 2$ instead:

• Assign: $1 \to C_1$; everything else is nearer 2, so $2, 3, 10, 11, 12 \to C_2$.
• Update: $\mu_1 = 1$, $\mu_2 = (2+3+10+11+12)/5 = 7.6$.
• Assign: is 3 nearer 1 or 7.6? $|3-1| = 2$ against $|3-7.6| = 4.6$ — nearer 1. So $1, 2, 3 \to C_1$ and $10, 11, 12 \to C_2$.
• Update: back to $\mu_1 = 2$, $\mu_2 = 11$. Same answer, one iteration later.

This particular bad start recovers. Many do not, which is the next section.

figureLloyd's algorithm from a deliberately bad startmatplotlib

See it move

Initialisation is not a detail

Run k-means on five well-separated blobs with a single random start and you get a different answer depending on nothing but the seed:

The seed-9 run is over three times worse. Look at what happened: two centroids landed inside the same blob and split it, leaving two genuine blobs merged into one cluster. Both steps of the algorithm behave perfectly; there is simply no single-point reassignment that escapes.

figureOne unlucky start, three times the inertiamatplotlib

k-means++

Rather than sampling initial centroids uniformly, k-means++ spreads them out:

1. Choose the first centroid uniformly at random from the data.
2. For each remaining point $\mathbf{x}$, compute $D(\mathbf{x})$, the distance to the nearest centroid already chosen.
3. Choose the next centroid from the data with probability proportional to $D(\mathbf{x})^2$.
4. Repeat until $k$ centroids are chosen.

The squared weighting makes far-away points overwhelmingly likely to be picked, so the seeds tend to land one per blob. The theoretical guarantee is that the expected inertia is within $O(\log k)$ of the global optimum — before a single Lloyd iteration runs.

This is scikit-learn’s default, and n_initn_init defaults to "auto""auto" (1 for k-means++k-means++, 10 for "random""random"). If you are doing anything that matters, set n_init=10n_init=10 explicitly.

Choosing k

Inertia cannot choose $k$ for you. It falls monotonically — with $k = n$ every point is its own centroid and $J = 0$. Here is that fall, on 400 points containing 4 genuine blobs:

The elbow method looks for the kink where the marginal improvement collapses. From $k = 3$ to $k = 4$ inertia drops by 1196; from 4 to 5 it drops by 63. That is the elbow, and it points at 4.

The silhouette has an actual maximum at 0.7475, also at $k = 4$. When the two agree, you are done. When they disagree, trust the silhouette — the elbow is a judgement call about the shape of a curve, while the silhouette is a number you can argmax.

figureInertia never rises; the silhouette peaksmatplotlib

Neither is authoritative. On real data the curve is often smooth with no elbow at all, and the silhouette peaks at $k = 2$ because two coarse groups always look cleanly separated. When that happens, the domain decides: how many customer segments can your marketing team actually operate?

Straight-edged cells

Because assignment compares squared distances to centroids, the boundary between two clusters is the set of points equidistant from both — a straight line, and in higher dimensions a hyperplane: the perpendicular bisector of the segment joining them. The partition of space is a Voronoi diagram.

figurek-means partitions the entire planematplotlib

This single geometric fact explains every k-means failure in the next section.

Where it fails

figureThree geometries, three failuresmatplotlib

The uniform-noise case deserves emphasis. Silhouette 0.378 is not obviously bad — you would plausibly ship that. The defence is to compare against a null: shuffle each column independently (destroying the joint structure but preserving the marginals), cluster the shuffled data, and check that your real silhouette is meaningfully higher.

In code

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
 
X, _ = make_blobs(n_samples=280, centers=3, cluster_std=0.95, random_state=4)
 
km = KMeans(n_clusters=3, n_init=10, random_state=0).fit(X)
 
print("inertia   ", round(km.inertia_, 4))
print("iterations", km.n_iter_)
print("centroids\n", km.cluster_centers_.round(3))
print("labels (first 10)", km.labels_[:10])
 
# The only clustering estimator in this phase that can label unseen points.
print("new point ->", km.predict([[0.0, 0.0]]))
 
# transform() returns distance to every centroid — often more useful than the label
print("distances ->", km.transform([[0.0, 0.0]]).round(3))

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
 
X, _ = make_blobs(n_samples=280, centers=3, cluster_std=0.95, random_state=4)
 
km = KMeans(n_clusters=3, n_init=10, random_state=0).fit(X)
 
print("inertia   ", round(km.inertia_, 4))
print("iterations", km.n_iter_)
print("centroids\n", km.cluster_centers_.round(3))
print("labels (first 10)", km.labels_[:10])
 
# The only clustering estimator in this phase that can label unseen points.
print("new point ->", km.predict([[0.0, 0.0]]))
 
# transform() returns distance to every centroid — often more useful than the label
print("distances ->", km.transform([[0.0, 0.0]]).round(3))

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
 
X, _ = make_blobs(n_samples=400, centers=4, cluster_std=0.9, random_state=11)
 
for k in range(1, 11):
    km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
    sil = silhouette_score(X, km.labels_) if k > 1 else float("nan")
    print(f"k={k:2d}  inertia {km.inertia_:9.2f}  silhouette {sil:.4f}")
 
# k= 1  inertia  16534.68  silhouette nan
# k= 2  inertia   6850.11  silhouette 0.5723
# k= 3  inertia   1842.91  silhouette 0.7329
# k= 4  inertia    646.92  silhouette 0.7475   <- both agree
# k= 5  inertia    584.31  silhouette 0.6277

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
 
X, _ = make_blobs(n_samples=400, centers=4, cluster_std=0.9, random_state=11)
 
for k in range(1, 11):
    km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
    sil = silhouette_score(X, km.labels_) if k > 1 else float("nan")
    print(f"k={k:2d}  inertia {km.inertia_:9.2f}  silhouette {sil:.4f}")
 
# k= 1  inertia  16534.68  silhouette nan
# k= 2  inertia   6850.11  silhouette 0.5723
# k= 3  inertia   1842.91  silhouette 0.7329
# k= 4  inertia    646.92  silhouette 0.7475   <- both agree
# k= 5  inertia    584.31  silhouette 0.6277

MiniBatchKMeans

Full k-means touches every point on every iteration. MiniBatchKMeansMiniBatchKMeans samples a small batch each step and nudges the affected centroids toward it, which turns the per-iteration cost from $O(n)$ into $O(b)$ for batch size $b$.

The price is a slightly worse optimum. On 100,000 points in 8 blobs, MiniBatch’s inertia came out 0.04% higher than full k-means; at 500,000 points, 0.01% higher. That is nothing. Use it whenever $n$ is large enough that full k-means is inconvenient.

from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.datasets import make_blobs
 
X, _ = make_blobs(n_samples=100_000, centers=8, cluster_std=1.0, random_state=0)
 
full = KMeans(n_clusters=8, n_init=3, random_state=0).fit(X)
mini = MiniBatchKMeans(n_clusters=8, n_init=3, batch_size=1024, random_state=0).fit(X)
 
print("full     ", round(full.inertia_, 1))            # 179598.7
print("minibatch", round(mini.inertia_, 1))            # 179671.3
print(f"penalty   {100 * (mini.inertia_ / full.inertia_ - 1):.2f}%")   # 0.04%

from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.datasets import make_blobs
 
X, _ = make_blobs(n_samples=100_000, centers=8, cluster_std=1.0, random_state=0)
 
full = KMeans(n_clusters=8, n_init=3, random_state=0).fit(X)
mini = MiniBatchKMeans(n_clusters=8, n_init=3, batch_size=1024, random_state=0).fit(X)
 
print("full     ", round(full.inertia_, 1))            # 179598.7
print("minibatch", round(mini.inertia_, 1))            # 179671.3
print(f"penalty   {100 * (mini.inertia_ / full.inertia_ - 1):.2f}%")   # 0.04%

Wall-clock timings vary far too much with thread count and BLAS build to quote a speedup you can rely on. The algorithmic claim is the durable one: each MiniBatch iteration reads batch_sizebatch_size rows instead of all $n$.

Pitfalls

Leaving n_initn_init at the default. Measured above: 971.25 against 302.46, on well-separated blobs. On messier data the gap is worse. n_init=10n_init=10 costs ten times the compute of a sub-second fit.

Arg-minimising inertia over k. Inertia is monotonically decreasing in $k$; the argmin is always $k = n$. Use it for the elbow’s shape, never for its minimum.

Not scaling. Covered on the previous page: one StandardScalerStandardScaler moved ARI from 0.035 to 0.891.

Trusting cluster indices across runs. Cluster 0 changes identity with random_staterandom_state. If you persist labels, persist the centroids and re-derive.

Applying k-means to one-hot encoded categoricals. The mean of a set of one-hot vectors is a vector of proportions, which is not a valid category. Use k-modes, or embed first.

Believing the clusters are real. k-means returns exactly $k$ groups from uniform noise, with a silhouette of 0.378. Always compare against a shuffled null.

Forgetting outliers move centroids. One point at distance 100 contributes 10,000 to the objective and will visibly drag its centroid. Handle outliers before clustering, or run a robust detector first.

Compare

🧪 Try It Yourself

Exercise 1 – One iteration by hand, in code

Exercise 2 – Prove the mean minimises the objective

Exercise 3 – What one bad seed costs

Exercise 4 – Confidently clustering pure noise

Exercise 5 – Sheared clusters break it

Recap

• k-means minimises the within-cluster sum of squares; assignment and mean-update are the exact minimisers of that objective with the other variable held fixed.
• It always terminates — non-increasing objective, finitely many partitions — but only at a local minimum.
• The worked example converged to centroids 2 and 11 with inertia 4 in two iterations.
• Initialisation matters enormously: 971.25 versus 302.46 from nothing but a different seed. Set n_init=10n_init=10.
• Inertia cannot pick $k$ (it is monotone in $k$). The silhouette can: it peaked at 0.7475 for $k = 4$.
• Boundaries are straight perpendicular bisectors, so sheared (ARI 0.587) and unequal-spread (ARI 0.803) geometries break it — and pure noise still yields three confident clusters.
• MiniBatchKMeans costs 0.04% inertia at 100k points and reads a fixed batch per iteration.

Exercise 6 – Measure the seed lottery

Next

Hierarchical Clustering (Dendrograms) — a method that does not need $k$ up front, builds the whole nesting of clusters at once, and lets you choose the cut afterwards.