k-means

Supervised learning had labels to grade every prediction. Unsupervised learning begins by admitting it has none — and must therefore define what structure means before finding it. k-means makes the oldest, simplest definition: a cluster is a set of points that are close to a shared center. That single sentence, made mathematical, produces the most-used clustering algorithm in existence, a beautiful convergence argument, and — because the definition is so specific — a precise catalog of when the algorithm is the wrong tool.

The objective, and why it is hard

Given points $x_1, \ldots, x_n \in \mathbb{R}^d$ and a target of $k$ clusters, k-means seeks centers $\mu_1, \ldots, \mu_k$ and an assignment $c: \{1..n\} \to \{1..k\}$ minimizing the within-cluster sum of squares (inertia):

Exact minimization is NP-hard even for $k = 2$ — the assignment space is combinatorial. What is easy is optimizing each block of variables with the other held fixed, and that observation is the whole algorithm.

Lloyd’s algorithm = alternating minimization

• Assignment step (fix $\mu$, minimize over $c$): each point picks its nearest center — separately per point, trivially optimal.
• Update step (fix $c$, minimize over $\mu$): each center moves to the mean of its assigned points, because the mean is the minimizer of summed squared distance ($\nabla_\mu \sum \lVert x_i - \mu \rVert^2 = 0 \Rightarrow \mu = \bar x$ — the same two-line calculus as least squares).

Each step can only lower $J$ (or leave it fixed), $J \ge 0$, and there are finitely many assignments — so Lloyd’s algorithm must converge in finitely many steps. That is a genuine proof, and you can watch every clause of it hold:

Initialization is half the algorithm

Because only the local optimum is guaranteed, where you start matters. k-means++ (Arthur & Vassilvitskii, 2007) seeds centers one at a time, choosing each new center with probability proportional to its squared distance from the nearest already-chosen center — spreading seeds across the data’s extent. The payoff is not just empirical: k-means++ guarantees expected inertia within $O(\log k)$ of optimal, which random initialization cannot promise at all. In practice: k-means++ plus a few restarts (keep the lowest $J$) is the standard recipe, and it is what the widget’s default does.

Choosing k, honestly

The objective cannot choose $k$ for you — $J$ decreases monotonically in $k$ (more centers never hurt), hitting zero at $k = n$. The working tools:

• Elbow heuristic: plot $J$ vs $k$, look for the bend where returns diminish. Honest status: a heuristic, often ambiguous, frequently overruled by domain knowledge.
• Silhouette score: for each point, compare mean distance to its own cluster ($a$) vs the nearest other cluster ($b$): $s = (b - a)/\max(a, b) \in [-1, 1]$. Averages near 1 mean tight, separated clusters; near 0 means the “clusters” are a partition of a continuum.
• The uncomfortable truth: k-means will happily carve a single Gaussian into $k$ pieces with a respectable-looking result. Clustering algorithms find structure only in the sense that they impose it; validation must come from outside the objective.

The assumptions in the objective

Squared Euclidean distance to a mean encodes three bets, each a failure mode when false: clusters are convex and roughly spherical (moons/rings break this — the widget shows it), similarly sized in radius (a big cluster bleeds into a small one’s territory, since boundaries are equidistant hyperplanes), and features are commensurately scaled (a feature in grams dominates one in kilograms 10⁶-fold — standardize first, the same lecture as regularization and PCA). And because the mean itself is not robust, single outliers drag centroids; k-medoids swaps in medians at higher cost. The next two lessons relax the geometry: mixtures make cluster shape learnable (k-means turns out to be a degenerate special case), and DBSCAN abandons centers entirely.

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs, make_moons

X, _ = make_blobs(n_samples=300, centers=3, random_state=0)
km = KMeans(n_clusters=3, init="k-means++", n_init=10, random_state=0).fit(X)
print(km.inertia_)                    # the J this lesson defined

Xm, _ = make_moons(n_samples=300, noise=0.06, random_state=0)
km2 = KMeans(n_clusters=2, n_init=10, random_state=0).fit(Xm)
# converged fine; the assignment is still geometrically wrong — plot it

Exercises