K-means clustering

No labels this time. Just points on a plane.

Find the groups that are already there — without being told what a group is.

The first unsupervised chapter.

The whole algorithm

Guess k centers. Then repeat two moves until nothing changes:

Assign every point to its nearest center.
Move every center to the mean of the points that chose it.

The centers chase the density and park in the middle of each group.

The data

150 points, four blobs from make_blobs, no labels. Gray on purpose.

Your eye finds four groups instantly. Now make the algorithm find them.

What it minimizes

Inertia — the within-cluster sum of squares:

J = \sum_{i=1}^{N} \bigl\lVert x_i - \mu_{c_i} \bigr\rVert^{2}

Assign step picks the nearest centroid. Update step moves each centroid to its cluster's mean. Both only lower $J$ , so the loop has to stop — at a local minimum that depends on the seed.

Watch the centroids move

Diamonds are the centroids. Rings reach to each cluster's farthest point. Lower panel: inertia falling. Every frame is one real iteration.

Inertia craters from ~7,081 to 342 in six iterations. Most of it in step one.

Picking k: the elbow

Inertia always falls as k grows. Don't minimize it — find the bend.

Cliff to k=4 (342.2), then flat. The orange dot is the elbow.

Scratch vs. library

Our k-means++ vs sklearn.cluster.KMeans. Both hit inertia 342.2. Both score adjusted Rand index 1.0 against the hidden true blobs — perfect recovery.

Takeaways

First unsupervised chapter: no labels, no accuracy — inertia and judgment.
Fast, simple, gives a centroid per cluster. The default clustering.
You must pick k. It assumes round, equal-size clusters. Seed with k-means++.
Next: hierarchical clustering (no fixed k) and Gaussian mixtures (soft, tilted clusters) — k-means with an assumption relaxed.