k-Means (Lloyd's Algorithm)
Interactive lab
Try it: k-Means (Lloyd's Algorithm)
How Lloyd's algorithm lowers the k-means objective (the sum of squared distances from each point to its cluster's centroid) by alternating nearest-centroid assignment and mean updates, and why a different start can end in a different local optimum.
How it works
- Place K initial centroids.
- Assignment: send every point to its nearest centroid (squared Euclidean distance; a tie goes to the lower-numbered centroid).
- Update: move every centroid to the mean of the points assigned to it (a centroid with no points stays where it is).
- Recompute the objective after each step — neither step can increase it.
- Stop when an assignment step changes nothing; the result is a local optimum that depends on the initial centroids.
Default run (8 steps): 12 points, K = 3. Initial centroids: c1 (1, 1), c2 (1.5, 2), c3 (9, 9). … Iteration 4, assignment: no point changes cluster, so the centroids would not move either. Lloyd's algorithm has converged with cost 7.9375.
Simplified: Toy 2-D data (3–16 points on a 0–10 board, K = 2–5). Lloyd's algorithm is a heuristic: it is not guaranteed to reach the minimum-cost clustering, and real data has many more points and dimensions.
Educational simulation
Loading the simulation…