K-Means Clustering

Partitioning data into k clusters by iteratively assigning points to the nearest centroid and re-computing centroids until convergence.

K-means clustering — assign each point to its nearest centroid, then update centroids

k =iteration 0

Restart replays the same initial positions. New init picks a different random start — results may vary.

Definition

K-means clustering partitions $n$ data points into $k$ groups (clusters) such that each point belongs to the cluster with the nearest centroid (cluster center).

The algorithm:

Initialize $k$ centroids randomly
Assign each point to its nearest centroid
Update each centroid to the mean of its assigned points
Repeat 2–3 until centroids stop moving

K-means minimizes the within-cluster sum of squares (WCSS, or inertia):

$\text{WCSS} = \sum_{j=1}^k \sum_{\mathbf{x} \in C_j} \|\mathbf{x} - \boldsymbol{\mu}_j\|^2$

Key properties

WCSS never increases at any step of the algorithm — both assignment and update steps can only improve or maintain it
Always converges in finitely many steps, since there are only finitely many possible partitions
Assumes roughly spherical, similarly-sized clusters — its geometric blind spot
Sensitive to the initial choice of centroids, which is why multiple random restarts are standard practice

Common mistakes

Forgetting to scale features before clustering: as with k-NN, unscaled features with large numeric ranges dominate the Euclidean distance
Picking $k$ without any diagnostic: always check an elbow plot or silhouette score rather than guessing $k$ arbitrarily
Applying k-means to non-convex or very differently-sized clusters: it will produce a confident but wrong partition rather than failing visibly

Customer segmentation

An online retailer clusters customers by (purchase frequency, average order value). K-means with $k=3$ finds: "bargain hunters" (high frequency, low value), "occasional splurgers" (low frequency, high value), and "loyal premium" (high frequency, high value). Marketing strategies can then be tailored per segment.

Try it

K-means is guaranteed to converge but not to find the global optimum. Why might it get stuck in a poor solution, and what's a simple remedy?

Solution

K-means can converge to a local minimum that depends on the initial centroids. Different initializations give different results.

The standard remedy is k-means++ initialization: instead of placing all centroids randomly, place each new centroid proportionally to its squared distance from the existing centroids. This tends to spread the initial centroids and significantly reduces the chance of poor solutions. Another approach is simply to run k-means multiple times with different random seeds and keep the best result.

Related concepts

Needs first

Mean Norms

DBSCAN Dimensionality Reduction Hierarchical Clustering K-Nearest Neighbors

View in full concept graph →