Clustering: k-Means & Friends

Groups without labels

You have 100,000 customers and no categories. Are there natural "types" hiding in the data — bargain hunters, premium loyalists, one-time gift buyers? Clustering finds groups such that members are similar to each other and different from other groups. No labels needed; the structure emerges from geometry (distance = similarity — the k-NN faith again).

Uses everywhere: customer segmentation, deduplicating records, grouping news articles, compressing color palettes, finding cell types in genomics, pre-labeling data cheaply.

k-Means: the classic

The most-used clustering algorithm is delightfully simple:

1. Pick $k$ (the number of clusters). Place $k$ centroids randomly.
2. Assign: each point joins its nearest centroid.
3. Update: move each centroid to the mean of its assigned points.
4. Repeat 2–3 until nothing moves.

The algorithm minimizes within-cluster squared distance (inertia). It always converges — though possibly to a mediocre local optimum, so implementations restart several times from different seeds (and use the smarter k-means++ initialization) and keep the best run.

Choosing k — the data won't tell you outright:

• Elbow method: plot inertia vs. $k$; the "elbow" where improvement slows marks a natural cluster count.
• Silhouette score (−1 to 1): how much closer each point is to its own cluster than to the next-best one; higher is better.
• Domain sense: 5 marketing personas may be actionable where 40 are useless — the business context legitimately influences $k$.

k-Means' blind spots: it assumes clusters are round-ish blobs of similar size. Crescent shapes, nested rings, or wildly different densities break it. And as always with distances — scale your features first.

Beyond k-Means

• Hierarchical clustering builds a tree (dendrogram) by repeatedly merging the closest clusters — no upfront $k$, and you can cut the tree at any level. Beautiful for taxonomy-like data.
• DBSCAN grows clusters from dense regions: finds arbitrary shapes, needs no $k$, and labels sparse points as noise/outliers — clustering and anomaly detection in one. Its knobs: neighborhood radius and minimum density.
• Gaussian mixture models fit overlapping bell curves (statistics path!) and give soft assignments — "this point is 70% cluster A, 30% cluster B".

Honest caveats

Clusters are hypotheses, not facts: different algorithms carve the same data differently, and clusters exist even in pure noise if you ask for them. Validate that discovered segments behave differently on external quantities (do the "personas" actually buy differently?) before acting on them.

Key takeaways

• Clustering = groups from geometry, no labels; k-means (assign/update loop) is the default.
• Choose k with elbow/silhouette + domain sense; scale features; know k-means' round-blob assumption.
• DBSCAN for weird shapes + outliers; hierarchical for tree structure; validate clusters externally.