[Clustering]
K-Means Clustering.
Partitions data into k clusters by minimizing within-cluster variance.
SPEC SHEET
FIG — THE MECHANISM, LIVE
Centroids (■) move to the mean of their assigned points until nothing changes - watch the territories settle.
C — How it actually works
Pick k centre points, assign every sample to its nearest centre, move each centre to the mean of its members, repeat until nothing moves. The data ends up carved into k compact, roughly spherical territories. It is fast, simple, and the default first look at unlabelled structure.
D — The math
Minimise within-cluster sum of squares: Σₖ Σ_{x∈Cₖ} ‖x − μₖ‖². Lloyd’s algorithm alternates assignment and mean-update; k-means++ seeding spreads initial centres to avoid bad local minima.
Training
O(n·k·d·iterations)
Inference
O(k·d)
E — When NOT to use it
- Clusters are elongated, nested, or vary widely in density - k-means only draws convex blobs
- You cannot even guess k and the structure matters more than a partition (try DBSCAN or hierarchical)
- Heavy categorical data - means of one-hots are not meaningful centres (use k-modes)
F — Tuning that matters
- Always use k-means++ init (default) with n_init=10+
- Choose k with the elbow on inertia AND silhouette score - never one alone
- Standardise features; a large-scale feature otherwise owns the distance
- MiniBatchKMeans handles millions of rows with minor quality loss
G — Production pitfalls
- Treating the output as truth: k-means ALWAYS returns k clusters, real or not
- Running once and keeping a bad local minimum
- Clustering raw high-dimensional sparse text - reduce with PCA/embeddings first
- Narrating clusters ("young urban savers") without validating them on held-out behaviour
H — Minimal starting point
PYTHONfrom sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
X = StandardScaler().fit_transform(X_raw)
km = KMeans(n_clusters=5, n_init=10, random_state=0).fit(X)
labels, centres = km.labels_, km.cluster_centers_I — The interview question
Why is k-means sensitive to initialisation, and what does k-means++ change?
The objective is non-convex; Lloyd’s algorithm only finds a local minimum, so bad seeds give bad partitions. k-means++ seeds centres with probability proportional to squared distance from existing ones, spreading them out and giving an O(log k) approximation guarantee in expectation.
J — In the wild
Telecom churn teams segment tens of millions of subscribers nightly with MiniBatch k-means on usage vectors - the segments feed pricing and campaign systems, and the "k=6" was chosen from silhouette curves plus what the marketing team could actually act on.
K — Consider instead
- DBSCAN— when cluster shapes are irregular or you need automatic outlier handling
- Hierarchical Clustering— when you want the full merge tree instead of one fixed k