K-means

K-means

1. Objective

Minimize within-cluster squared distance:

$μ_{c}$ = centroid of cluster $c$.

2. Lloyd Algorithm

init k centroids (k-means++: spread by distance²)
repeat: assign each x to nearest μ; recompute μ as mean of members
until assignments stop

Monotone decrease — converges to local minimum (not global; restart 10×, keep best $J$).

3. Worked (1-D)

points 1,2,10,11, k=2, init μ=1,11
assign: {1,2}→μ1, {10,11}→μ2; new μ=1.5,10.5; reassign same → done

4. Limits

Needs $k$ upfront; spherical bias (fails moons/rings); outlier-sensitive (mean drags); scale-sensitive → standardize; empty-cluster handling.

5. Exam Points

• Write objective + Lloyd steps — 7 marks, very frequent.
• 1-D trace 2 iterations — 5 marks, frequent.
• k-means++ + restarts why — 3 marks, frequent.