k-means Local Minimum by Hand

1. Running Lloyd's algorithm from centroids (1, 2, 3):

Iteration 1 — assign: 1 → c1; 2 → c2; 3 → c3; every point from 10 upward is closest to c3 = 3. Update: c1 = 1, c2 = 2, c3 = mean(3, 10, 11, 12, 20, 21, 22) = 99/7 ≈ 14.14.

Iteration 2 — assign: 1 → c1; 2 → c2; 3 → c2 (distance 1 vs 11.14); 10 → c3 (|10 − 2| = 8 > |10 − 14.14| = 4.14); 11, 12, 20, 21, 22 → c3. Update: c1 = 1, c2 = mean(2, 3) = 2.5, c3 = mean(10, 11, 12, 20, 21, 22) = 96/6 = 16.

Iteration 3 — assign: 1 → c1; 2, 3 → c2; 10 → c3 (7.5 vs 6); rest → c3. Assignments unchanged → converged.

Final clusters: {1}, {2, 3}, {10, 11, 12, 20, 21, 22} with centroids 1, 2.5, 16. Inertia: cluster 1 contributes 0; cluster 2 contributes 0.25 + 0.25 = 0.5; cluster 3 contributes 36 + 25 + 16 + 16 + 25 + 36 = 154. J = 154.5.

2. The obvious clustering: Centroids 2, 11, 21; each cluster contributes 1 + 0 + 1 = 2, so J = 6. Lloyd's algorithm converged to a solution ~26× worse than the optimum. Each step of Lloyd's algorithm only decreases J, so it can never escape a basin once inside — it is a local search, and the quality of the answer depends heavily on initialisation. This is why scikit-learn runs n_init restarts and keeps the lowest inertia.

3. Why k-means++ avoids this: k-means++ picks the first centroid at random, then chooses each next centroid with probability proportional to D(x)^2, the squared distance to the nearest already-chosen centroid. After picking, say, 2, the points near 21 have D^2 \approx 361 while 1 and 3 have D^2 = 1 — the far cluster is overwhelmingly likely to receive the next centroid, and the middle cluster the third. Starting with one centroid per true group, Lloyd's algorithm converges directly to J = 6. The general guarantee is O(\log k)-competitive expected inertia; in practice it almost always removes pathological starts like this one.