k-Means — Saed Sayad

k-means partitions $n$ objects into $k$ clusters, each object belonging to the cluster whose mean (centroid) is nearest. It is the default clustering algorithm: fast, simple, and good enough often enough that every alternative is benchmarked against it.

The objective

k-means minimizes the within-cluster sum of squares (WCSS) — the total squared distance from every point to its own centroid $\mu_i$ :

$V = \sum_{i=1}^{k} \sum_{x_j \in S_i} (x_j - \mu_i)^2$

Exactly minimizing WCSS is NP-hard, so k-means uses Lloyd’s heuristic: an assign-and-update loop that never increases $V$ and stops when it stops moving.

The algorithm

Choose $k$ in advance and pick $k$ initial centroids (traditionally at random; k-means++ seeds them spread out).
Assign each object to its closest centroid by Euclidean distance.
Update each centroid to the mean of the objects assigned to it.
Repeat steps 2–3 until the assignments stop changing between rounds.

Two clusters of points in Age–Income space, each circled with its centroid marked — A converged k-means run with k = 2: every point belongs to the cluster whose centroid is nearest, and each centroid sits at its cluster's mean.

The loop is efficient — each iteration is $O(nk)$ — but it has two structural weaknesses: you must fix $k$ ahead of time, and the result is sensitive to initialization, often converging to a local optimum. The practical remedies are multiple restarts with different seeds and comparing several values of $k$ on a quality curve. A larger $k$ always lowers WCSS but eventually overfits, splitting real clusters into meaningless shards.

Worked example: grouping website visitors by age

Group $n = 19$ visitors by age alone, with $k = 2$ and random initial centroids $c_1 = 16$ , $c_2 = 22$ :

15, 15, 16, 19, 19, 20, 20, 21, 22, 28, 35, 40, 41, 42, 43, 44, 60, 61, 65

Iteration 1. Compute each age’s distance to both centroids and assign to the nearer one (ties go to cluster 2):

$x_i$	$d_1$	$d_2$	Cluster
15	1	7	1
15	1	7	1
16	0	6	1
19	3	3	2
19	3	3	2
20	4	2	2
20	4	2	2
21	5	1	2
22	6	0	2
28	12	6	2
35–65	…	…	2

Updating: cluster 1 = {15, 15, 16} → $c_1 = 15.33$ ; cluster 2 = the remaining 16 ages → $c_2 = 36.25$ .

Iterations 2–4. The centroids keep sliding as borderline points switch clusters:

Iteration	$c_1$	$c_2$	Change
0 (init)	16.00	22.00	—
1	15.33	36.25	yes
2	18.56	45.90	yes
3	19.50	47.89	yes
4	19.50	47.89	none — converged

Between iterations 3 and 4 no assignment changes, so the loop halts. Two groups emerge: ages 15–28 (centroid 19.50) and ages 35–65 (centroid 47.89). Different initial centroids can converge elsewhere — run the algorithm several times and keep the best WCSS to see the clusters fairly.

Try it: k-means stepper

Step the assign–update loop yourself on a 2-D point set and watch the centroids converge:

In practice

sklearn.cluster.KMeans defaults to kmeans++ seeding and n_init restarts — leave both on; they cost little and fix most of the local-optimum problem. Choose $k$ with the elbow of the WCSS curve, the silhouette score, or the gap statistic, and always scale features first (StandardScaler). For very large data, MiniBatchKMeans approximates the loop on random batches. Remember the geometry: k-means assumes roughly spherical, similar-size clusters — for elongated or interleaved shapes, use hierarchical clustering or a density-based method instead.

Common pitfalls

Unscaled features — one large-unit variable will own the Euclidean geometry.
A single run with random init — unlucky seeds land in bad local optima; always restart.
Reading the WCSS drop as proof of structure — WCSS falls for every larger $k$ , even on noise; validate with silhouette or stability.
Assuming the clusters are spherical and equal-size; k-means carves Voronoi cells and will happily split an elongated cluster in two.
Feeding it categorical or ordinal codes as if they were continuous coordinates.

Summary

k-means alternates assigning points to the nearest centroid and updating centroids to cluster means, driving the within-cluster sum of squares downhill until convergence. On the visitor ages, two restarts-free iterations settle on {15–28} and {35–65} with centroids 19.50 and 47.89. Seed well, restart often, scale first, and choose $k$ with a quality curve rather than a guess.