Lesson 19: Clustering — k-Means, GMMs, and DBSCAN¶

Every prior lesson in this part assumed some target — a threshold, a template, a known transform. Clustering asks a different kind of question, with no target at all: given a pile of points (or pixels), group them into a small number of sensible categories, using only how similar they are to each other. This is unsupervised learning's classical starting point — no labels, just a distance function and an assumption about what "a cluster" should look like. This lesson builds three clustering algorithms from scratch, each built on a different assumption about cluster shape, and shows concretely where each one wins and fails: k-means (round, similarly-sized clusters), Gaussian mixture models (elliptical clusters, soft assignment), and DBSCAN (arbitrary shape, defined by density rather than a center).

k-means on real color data¶

Lesson 18 built a perceptually meaningful color distance (L*a*b* Euclidean distance). Clustering is the natural next step: given a pile of pixel colors and no labels at all, group them into regions automatically. Build a synthetic 4-region color image (with noise, so it's not trivially separable by exact color match), convert to Lab*, and cluster the raw pixel colors.

K-means, also known as Lloyd's algorithm, is here unchanged from its textbook form: pick k random points as initial centers, assign every point to its nearest center, recompute each center as the mean of its assigned points, repeat until nothing moves. With compact, roughly equal-sized, roughly round clusters in Lab* space (exactly what this synthetic image has), it recovers the true regions almost perfectly. Two real caveats worth flagging even in this success case: k (the number of clusters) has to be chosen in advance — nothing in the algorithm discovers it — and different random initializations can converge to different, sometimes noticeably worse, local optima (try changing seed=3 to seed=0 above and rerun); k-means++ (Arthur & Vassilvitskii, 2007★) fixes this by seeding centers to be spread apart rather than purely at random.

Where k-means breaks: non-convex clusters¶

K-means' update rule — assign to the nearest center — can only carve space into convex regions. Build a dataset that isn't convex at all: two concentric rings. No placement of two centers can separate them correctly, no matter how many times the algorithm iterates.

K-means lands right at chance — it splits the two rings radially, half of each ring going to each cluster, because that's the only kind of boundary (a straight line, equidistant between two centers) the algorithm is capable of drawing. The clusters here aren't ambiguous to a human eye at all; the algorithm's assumption (round, center-based clusters) is simply the wrong tool for this shape.

Gaussian mixture models: soft, elliptical clusters¶

A Gaussian mixture model (GMM) generalizes k-means two ways: each cluster gets its own full covariance (so clusters can be elongated ellipses, not just circles), and assignment is soft — every point gets a probability of belonging to each cluster, not a hard label. Fit by expectation-maximization (EM) (Dempster, Laird, & Rubin, 1977★): the E-step computes each point's responsibility (probability) under the current Gaussians; the M-step re-fits each Gaussian's mean, covariance, and weight to its responsibility-weighted points.

GMM does no better than k-means here — also near chance. That's an important, easy-to-miss point: GMM fixes k-means' round-only assumption, but it's still a unimodal-per-cluster model — each cluster is described by one Gaussian bump. A ring isn't elliptical any more than it's circular; no single Gaussian, of any shape, fits an annulus well. GMM and k-means fail this dataset for the same underlying reason.

DBSCAN: clusters defined by density, not shape¶

DBSCAN (density-based spatial clustering, Ester et al., 1996★) never fits a parametric shape at all. A point is a core point if at least min_samples other points lie within distance eps of it. Clusters are formed by chaining together core points that are within eps of each other (and their neighbors), so a cluster can be any shape — including a ring — as long as it's a connected, sufficiently dense region of space. Points that end up in no core point's neighborhood are labeled noise, not forced into the nearest cluster.

DBSCAN separates the two rings perfectly — it never assumed a center or a shape, only that points within a ring are densely connected to their neighbors, while the gap between rings is not. This comes at a real cost: eps and min_samples have to be chosen by hand (a poor choice fragments each ring into dozens of tiny arcs — worth trying eps=0.15 above to see it happen), and DBSCAN struggles when different true clusters have very different densities, since one global eps can't be simultaneously right for a sparse cluster and a dense one.

Noise robustness: a real advantage of "no forced assignment"¶

Add clutter — points scattered uniformly across the whole region, belonging to neither ring — and compare how each algorithm handles them. k-means and GMM have no concept of "doesn't belong to any cluster": every point gets assigned somewhere, dragging cluster centers toward the clutter. DBSCAN can simply call clutter what it is.

k-means, by construction, flags exactly zero of the 60 clutter points as anything other than "definitely part of a ring" — the algorithm has no vocabulary for "doesn't belong anywhere." DBSCAN correctly isolates a minority of them; the rest happen to land within eps of a real ring point (or of each other, forming a small cluster of their own), which is a fair outcome, not a bug — density-based clustering only calls a point noise if it's genuinely isolated, and uniform random scatter still produces occasional clumps. The qualitative point stands regardless of the exact count: DBSCAN has a real, usable category for "this doesn't fit anywhere," whereas k-means structurally cannot.

Where this goes next¶

This is the end of Part 1. Many of the algorithms encountered so far operate directly on raw or hand-picked features — pixel color, (x, y) coordinates, texture — and rely on specific rules, such as the human-chosen distance functions used here. Future lessons revisit many of these problems using deep learning to automatically discover the features and the rules for combining them. For example, Lesson 43's instance segmentation uses a similar clustering idea, and Lesson 48's autoencoder learns the feature space itself, purely from reconstruction error, before any grouping is asked for at all. Where this lesson's methods assume a shape and fit it, the deep-learning methods later in this course learn a representation and let structure emerge from it.

Exercises¶

1. Rerun the color-segmentation k-means with k=3 and k=6 instead of the true 4. Since nothing in the algorithm can "know" the right number of clusters, how does the segmentation degrade in each direction, and can you tell purely from the output which k is likely wrong?
2. The GMM above was evaluated only on the ring dataset, where it fails for the same reason k-means does. Construct a two-cluster dataset where the clusters are genuinely elliptical (e.g. np.random.multivariate_normal with a non-diagonal covariance) and compare GMM against k-means there. Does GMM's extra flexibility (fitting the shape, not just the center) show a real accuracy advantage this time?
3. In the noisy-clutter DBSCAN demo, shrink eps from 0.6 to 0.3. Does DBSCAN start mislabeling real ring points as noise, real clutter points as belonging to a ring, or both — and does that match the earlier warning about eps being a hand-tuned, dataset-specific choice rather than something the algorithm discovers?