k-means clustering

Summary

K-means seeks low squared Euclidean distortion by alternating nearest-center assignment with fixed-membership mean updates:

μ_{1}, \dots, μ_{k}, C min i = 1 \sum n ∥ x_{i} - μ_{C (i)} ∥^{2} .

Each half-step minimizes the same objective while holding different variables fixed. This optimization definition does not require equal cluster sizes or establish that the resulting groups are natural classes.

The algorithm

Use finite points in meaningful Euclidean units, $1 \leq k \leq n$ , and an explicit initialization. Break distance ties by a fixed center order; retain an old center if its cluster is empty in this trace. Then repeat:

Assignment: $C (i) = ar g min_{j} ∥ x_{i} - μ_{j} ∥^{2}$ for each $i$ .
Update: $μ_{j} = \frac{1}{∣ C ^{- 1} ( j ) ∣} \sum_{i \in C^{- 1} (j)} x_{i}$ for each $j$ .

For a nonempty cluster, $\sum_{i} ∥ x_{i} - μ ∥^{2} = \sum_{i} ∥ x_{i} - \overset{x}{ˉ} ∥^{2} + m ∥ μ - \overset{x}{ˉ} ∥^{2}$ . The second term proves the mean minimizes fixed-membership squared distortion. An empty cluster has no defined mean, which is why an explicit policy is needed.

In the figure, initial centers are A0 $(110, 130)$ and B0 $(210, 120)$ . Points $(50, 80), (70, 110), (90, 80)$ choose A; $(230, 70), (250, 100), (270, 70)$ choose B. For $(90, 80)$ , squared distances are $2900$ versus $16000$ . Each group’s initial assigned SSE is $11000$ , giving total $22000$ . Updates produce A1 $(70, 90)$ and B1 $(250, 80)$ . Each group then contributes $500 + 400 + 500 = 1400$ , so total SSE drops to $2800$ .

Learning objective

Fix assignments before moving each centroid to its assigned mean

Derivation

assignment changes memberships while centers stay fixed. Updating then holds membership fixed and moves each center to its mean. The illustrated SSE decreases from 22,000 to 2,800. Original construction follows Lloyd's paper and the scikit-learn guide.

Check: What is held fixed while A moves to the mean of its three assigned samples?

Read it this way: Points 0 and 2 assigned to the left centroid give mean 1. Points 8 and 10 assigned right give mean 9.
During this centroid update, can a point silently change its assigned cluster?

Dense assignment costs $O (nk d)$ per iteration; mean updates add $O (n d)$ . Standard exact updates with stable tie/empty-cluster policies reach a fixed point on finite data, not a guaranteed global optimum. Floating-point tolerances and iteration limits add numerical stopping policies.

Give Observations Unequal Weight

New task: Double the weight of $(90, 80)$ in A’s fixed membership.

Picture and change: Minimize $\sum_{i} a_{i} ∥ x_{i} - μ ∥^{2}$ with positive weights, using $μ = \sum_{i} a_{i} x_{i} / \sum_{i} a_{i}$ . Positive per-observation weights leave fixed-center nearest assignment unchanged.

Check: A becomes $((50 + 70 + 180) /4, (80 + 110 + 160) /4) = (75, 87.5)$ .

Use when: Rows represent justified frequencies or importance in the distortion objective.

Update from an Arriving Point

New task: After the reference update, assign $(110, 70)$ to A, whose count is three.

Picture and change: Increment the count to four and use $μ_{n e w} = μ_{o l d} + (x - μ_{o l d}) /4$ .

Check: A moves from $(70, 90)$ to $(80, 85)$ while B remains unchanged.

Use when: A stream or mini-batch budget prevents full reassignment and mean recomputation. An incremental step does not inherit full-data Lloyd objective nonincrease.

Adding outlier $(1000, 80)$ to B’s fixed membership moves its mean to $(437.5, 80)$ . Squared distance strongly rewards accommodating outliers, even when the resulting center is not typical.

k-means++ initialization

Random initialization sometimes converges to bad local minima. k-means++ (Arthur & Vassilvitskii, 2007):

Pick $μ_{1}$ uniformly at random.
For $j = 2, \dots, k$ : pick $μ_{j}$ from data with probability proportional to $min_{j^{'} < j} ∥ x - μ_{j^{'}} ∥^{2}$ . Points far from existing centers are more likely to be picked.

The $O (lo g k)$ expected approximation guarantee concerns seeded distortion under the theorem’s conditions, not global-optimum recovery or runtime.

Choosing $k$

There is no universally right answer. Heuristics:

Elbow method: plot within-cluster SSE against k. Inspect diminishing returns; an elbow need not be distinct or objectively best.
Silhouette score: average similarity of each point to its own cluster vs. nearest other cluster; pick $k$ maximizing it.
Gap statistic: compare to clustering on uniform random data of the same shape.
Domain knowledge: often the right answer.

Choose geometry, downstream usefulness, and stability criteria before selecting among these heuristics.

Assumptions

Euclidean units and squared distortion define the task; standardizing features changes that task rather than automatically repairing it. Spherical mixture interpretations require additional probabilistic assumptions, not equal-size constraints in the objective. Replacing squared distance with absolute coordinate differences yields coordinate medians, not the same mean update.

Mini-batch k-means

Mini-batch updates trade full reassignment work for stochastic updates; evaluate quality, count policy, and workload-specific cost.

When k-means is and isn’t appropriate

Use it when squared-distance compression or grouping matches the task, including vector-quantization codebooks. Nonconvex shape discovery, categorical semantics, and alternative similarity objectives need separately justified methods.

Common pitfalls

Cluster IDs are permutation-invariant; compare partitions or aligned centers, not raw labels across runs. Alternating minimization alone does not make this algorithm an arbitrary mixture model’s EM procedure.