Project 38: K-Means Clustering from Scratch

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Intermediate
  • Time: 1-2 weeks
  • Language: Python with NumPy and Matplotlib
  • Prerequisites: Projects 16, 20, and 33
  • Source: ML-Found P15

What You Will Build

Build k-means clustering without a clustering library. Implement vectorized distances, assignment, centroid recomputation, within-cluster sum of squares (inertia), convergence detection, and multiple random restarts. Add k-means++ initialization and explicit handling for empty clusters. Animate assignments and centroid movement on 2D data, then apply the same engine to standardized customer features or image colors. Provide elbow and silhouette-style diagnostics while stressing that neither automatically discovers a uniquely correct k. Include deliberately difficult datasets—unequal density, non-spherical moons, outliers, and differently scaled features—to expose the geometric assumptions behind Euclidean centroid clustering.

Real World Outcome

For a dataset and k, the CLI logs inertia and centroid shift per iteration, saves an animation, and reports the best of several seeded restarts. A model-selection view plots inertia and silhouette summaries across k. Failure-gallery plots explain why k-means splits elongated or nonconvex clusters poorly.

Core Question

How can alternating between nearest-centroid assignments and mean updates reduce within-cluster variance, and what data geometry makes that objective meaningful or misleading?

Concepts You Must Understand First

  1. Euclidean distance and scale: large-scale features dominate squared distance unless standardized.
  2. Centroid as mean: the arithmetic mean minimizes squared distance within a fixed cluster.
  3. Alternating optimization: assignment and update steps each do not increase the k-means objective.
  4. Initialization: the objective is nonconvex, so different seeds reach different local solutions. See Arthur and Vassilvitskii, “k-means++.”
  5. Cluster validation: elbow and silhouette summarize geometry but do not supply ground truth. See Géron, Hands-On Machine Learning, ch. 9.

Build Milestones

  1. Implement and test distance, assignment, mean-update, and inertia calculations on tiny data.
  2. Add deterministic stopping by assignment stability or centroid shift plus an iteration cap.
  3. Implement random and k-means++ starts, empty-cluster repair, and best-of-n restarts.
  4. Animate 2D convergence and add elbow/silhouette comparisons across k.
  5. Apply the engine to real features and a documented failure gallery.

Hints in Layers

  1. Assert that inertia never materially increases after a full assignment/update cycle.
  2. For k-means++, sample new centers in proportion to squared distance from the nearest selected center.
  3. Repair empty clusters by reseeding to a far-away point or splitting a high-variance cluster, and log the event.

Common Pitfalls and Debugging

  • Symptom: one feature determines every cluster. Cause: inconsistent scales. Fix: fit standardization on the analysis data and explain transformed units.
  • Symptom: output changes wildly by run. Cause: single random initialization. Fix: seed, use k-means++, and compare multiple restarts.
  • Symptom: centroid contains NaN. Cause: empty cluster mean. Fix: detect and reseed before division.

Definition of Done

  • Core calculations match hand-computed fixtures.
  • Inertia history is nonincreasing within numerical tolerance.
  • Random and k-means++ initialization plus multiple restarts are supported.
  • Empty clusters, duplicates, and ties have deterministic policies.
  • Animation and k-selection diagnostics are exported.
  • Failure cases document scale, shape, density, and outlier limitations.

Previous: Project 37 · Complete learning path · Next: Project 39