What k-Means Actually Optimizes

Question

State the objective k-means minimizes, explain why Lloyd's algorithm always terminates yet routinely lands in local minima, the standard mitigations, and the shape assumption that makes k-means a poor fit for market-regime clustering.

Accepted Answer

Objective. Within-cluster sum of squares: min_C_k,mu_k sum_k=1^Ksum_i in C_k lVert x_i - mu_k rVert^2. Why Lloyd's terminates. Alternate: (1) assign each point to its nearest centroid, optimal assignments given centers; (2) update each centroid to its cluster mean, the mean is the unique minimizer of summed squared distance given assignments. Each step weakly decreases the objective; there are finitely many partitions; a decreasing function on a finite set must stop. It's coordinate descent on (assignments, centers). Why local minima anyway. The joint objective is non-convex (assignments are discrete; the centers' landscape is multimodal): monotone descent guarantees you stop, not where. Classic basin of doom: two initial centers land in one true cluster and split it while two other true clusters share a center, no single Lloyd step can fix this, since every move is locally worsening. Mitigations: many random restarts keeping the best objective; k-means++ seeding (choose initial centers with probability proportional to squared distance from those already chosen, spreads them out, with a provable expected-approximation guarantee); mini-batch variants for scale. Choosing K: elbow/sil

What k-Means Actually Optimizes

Problem

Your answer

Hints