K-Means Clustering

Lloyd's algorithm, k-means++ init, silhouette, failure modes

You have 100,000 user embeddings and want 5 segments. K-means: randomly initialize 5 centroids. Step 1 (assignment) — assign each user to the nearest centroid by Euclidean distance. Step 2 (update) — move each centroid to the mean of all users assigned to it. Repeat until assignments stop changing. This is Lloyd's algorithm. It is guaranteed to converge. It is not guaranteed to find the global optimum.

K-means minimizes the within-cluster sum of squared distances (inertia): Σₖ Σᵢ ∈ cluster k ‖xᵢ - μₖ‖². This is NP-hard in general — K-means finds a local minimum. The result depends on initialization. K-means++ fixes this: choose the first centroid uniformly at random, then each subsequent centroid with probability proportional to the squared distance from the nearest existing centroid. This produces better local optima with fewer restarts. sklearn uses k-means++ by default; note that sklearn's default n_init changed in v1.4 to 'auto', which resolves to a single run when init='k-means++' (versions before 1.4 defaulted to n_init=10).

Elbow method: plot inertia vs K. Inertia always decreases as K increases — more clusters always fit tighter. Look for the elbow where marginal gain of adding a cluster drops off. This is approximate and often there is no clear elbow in real data.

Silhouette score is a per-point diagnostic: it compares each point's average distance to points in its own cluster (cohesion) against its average distance to points in the nearest other cluster (separation), and ranges from -1 to 1 — near 1 means well-clustered, near 0 means the point sits on a cluster boundary, and negative means it was probably assigned to the wrong cluster. Averaged across all points, scores below roughly 0.25 signal weak or absent structure (e.g., curse-of-dimensionality noise) — so a uniformly low average like 0.08-0.12 across every K tested is a structural warning that no choice of K will fix, not a sign you have not found the right K yet.

Three structural limitations to know. First: K-means assumes spherical clusters (Euclidean distance to centroid). If your data has non-spherical or unequal-density clusters, K-means draws the wrong boundaries regardless of K. Second: sensitive to outliers — one outlier pulls a centroid far from the cluster. (K-medoids addresses this directly by using an actual data point, the medoid, as the cluster center instead of the mean — more robust to outliers and more interpretable, at higher compute cost; choose k-medoids over k-means when outliers or interpretability matter more than speed.) Third: requires specifying K in advance, and an incorrect K produces confident but wrong assignments.

K-means also has a probabilistic reading, covered in full in the GMM module: a Gaussian Mixture Model fits several Gaussian "components" (bell-curve clusters, each with its own center and spread) to the data using Expectation-Maximization (EM), a soft version of K-means that assigns each point a probability of belonging to each component instead of one hard label. K-means is exactly the hard-assignment limit of that EM process when every component is forced to share the same isotropic covariance σ²I (the same, direction-independent spread) and σ→0: as σ shrinks toward 0, each point's soft, probabilistic membership collapses into an all-or-nothing 1-or-0 vote for whichever component is nearest — precisely K-means' nearest-centroid assignment step. That equivalence is also where K-means' spherical, equal-radius cluster assumption comes from; see the GMM module for the full derivation.

NOT-this: "K-means finds the natural clusters." K-means partitions space into Voronoi cells — every point gets assigned to the nearest centroid. Try DBSCAN or GMM when clusters are not spherical or equal in size.

Key points

• Always run K-means with K-means++ initialization and n_init=10 — a single random initialization frequently gets trapped in a poor local minimum. Running 10 times and taking the best result (lowest inertia) adds 10× compute but significantly improves cluster quality. As of sklearn 1.4, this is no longer the default (n_init now defaults to 'auto', which runs only once with k-means++ init) — so set n_init=10 explicitly rather than relying on the default.
• Trap: using K-means on high-dimensional data without dimensionality reduction. In high dimensions, Euclidean distance concentrates — all points become approximately equidistant, making centroid-based assignment meaningless. Apply PCA to 20–50 dimensions first. This is not optional at 100+ features; it is the difference between signal and noise.
• Diagnostic: after clustering, compute the per-cluster variance of key business metrics (revenue, engagement). If all clusters have similar metric distributions, the clustering is not capturing meaningful signal. Try different features or a different algorithm. Clusters that look geometrically clean but collapse to the same business profile have not solved the segmentation problem.

Recap

• Lloyd's algorithm: assign to nearest centroid → move centroid to mean → repeat.
• Converges always, global optimum never — minimizes inertia $\Sigma\|x_i-\mu_k\|^2$, NP-hard, local min.
• K-means++ + n_init=10: distance-weighted init beats random restarts (sklearn default).
• Elbow method: inertia always drops with K — look for the knee.
• Three limits: assumes spherical clusters, outlier-sensitive, K fixed in advance.
• High-D first reduce: distances concentrate → PCA to 20–50 dims before clustering.
• Hard-assignment limit of EM on GMM with shared isotropic $\sigma^2 I$, $\sigma\to0$.

Check your understanding