Module 2 — k-means: principle, initialization and limits

k-means is to clustering what linear regression is to supervised learning: the mandatory starting point, simple, fast, and instructive right down to its flaws. Understanding it properly — including what it cannot do — prepares every algorithm that follows.

The algorithm: two alternating steps

You fix the number of clusters $k$ in advance. The algorithm then places $k$ centroids (the cluster centers) and repeats two steps until stabilization:

1. Assignment: each point joins the nearest centroid;
2. Update: each centroid moves to the mean of the points assigned to it.

And so on. Because the centroids move, the assignments change; because the assignments change, the centroids move. The process always converges, generally within a few dozen iterations.

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler

X_s = StandardScaler().fit_transform(X)     # imperative: see module 1
km = KMeans(n_clusters=4, n_init=10, random_state=42).fit(X_s)
km.labels_            # the cluster assigned to each point
km.cluster_centers_   # the k centroids, readable as typical profiles

A word on cluster_centers_: each centroid is a vector of means, hence a typical profile of the cluster. This is the main interpretation tool — "cluster 2 is the high-basket, low-frequency customers". Without that reading, a clustering remains a column of meaningless numbers.

What the algorithm minimizes: inertia

k-means does not grope at random: it minimizes within-cluster inertia, the sum of squared distances from each point to its centroid.

$$\text{inertia} = \sum_{j=1}^{k} \sum_{x \in C_j} \lVert x - \mu_j \rVert^2$$

In other words: clusters as compact as possible. This quantity, exposed as km.inertia_, decreases relentlessly as $k$ grows — reaching zero when every point is its own cluster. It therefore cannot, on its own, be used to choose $k$; that is the whole point of module 3.

Initialization: why k-means++ matters

The two steps converge to a local minimum, which depends on the initial position of the centroids. A poor starting draw produces a mediocre partition — two centroids stuck in the same cloud, an obvious cluster split in half.

Two guardrails, active by default in scikit-learn and never to be disabled without reason:

• k-means++ places the initial centroids far from one another, ruling out absurd configurations from the start;
• n_init restarts the algorithm several times with different draws and keeps the lowest-inertia solution.

Structural limits: what k-means cannot see

These limits are not bugs but direct consequences of the definition. Knowing them saves you from blaming the data.

Limit	Origin	Consequence
$k$ fixed in advance	the algorithm does not infer it	an external criterion is needed (module 3)
spherical clusters of comparable size	minimizing a distance to a center	fails on elongated or curved shapes
every point is assigned	no notion of noise	outliers drag the centroids
scale-sensitive	Euclidean distance	standardization mandatory

The second row carries the heaviest consequences. Two interlocking crescents, an obvious structure to the eye, are butchered by k-means: minimizing distance to a center amounts to cutting space into convex cells, and no such partition follows a curve. This is precisely the gap DBSCAN will fill in module 5.

Useful variants to know

MiniBatchKMeans handles very large volumes by working on successive samples, at barely degraded quality. k-medoids replaces the mean with an actual point from the dataset, which resists outliers better and allows non-Euclidean distances. And for categorical variables the mean no longer makes sense: you move to k-modes, or change representation.

Summary

• k-means alternates assignment to the nearest centroid and update of centroids to the mean, until convergence.
• It minimizes within-cluster inertia (compact clusters); this inertia always decreases with $k$ and therefore cannot choose it.
• Convergence is local: k-means++ and n_init protect against poor initializations.
• It assumes spherical clusters of comparable size, assigns every point including outliers, and requires prior standardization.

Next module: choosing the number of clusters with the elbow method and the silhouette score.