Clustering & k-Means
Every model so far has learned from labeled examples — this is spam, that is not; this patient relapsed, that one didn't. Clustering throws the labels away and asks a harder, more exploratory question: are there natural groups in here at all? It's how you discover customer segments, species, or symptom profiles nobody told you to look for. k-means is the workhorse: beautifully simple, genuinely useful, and easy to fool.
Unsupervised: structure without answers
In unsupervised learning there is no outcome to predict and nothing to be "right" about. You hand the algorithm feature vectors and ask it to organize them. Clustering, the most common flavor, partitions the data into groups so that points in the same group are similar and points in different groups are not. The reward is a hypothesis about hidden structure — one you then have to interpret and validate, because the algorithm will happily invent groups whether or not any exist.
The k-means loop
k-means needs one thing from you up front: k, the number of clusters. Then it repeats two steps until nothing changes:
- Assign. Attach every point to the nearest cluster center (centroid), by straight-line distance.
- Update. Move each centroid to the mean position of the points now assigned to it.
Assign, update, assign, update. Each round can only lower the total within-cluster spread, so it always converges, usually in a handful of iterations. Step through it below and watch the centroids drift into place, dragging their colors with them. (You can also grab any point and move it, or reseed the starting centroids to see how much the result depends on where you began.)
🎯 Step through k-means
Step alternates assign / update (gray points are not yet assigned); centroid trails show their path. Build the elbow plot by sliding k. Then switch to Two moons — k-means will cluster it confidently, and confidently wrong. Drag any point to reshape the data.
Choosing k
Since you supply k, choosing it well is the whole game. Two diagnostics help. The elbow method plots the within-cluster sum of squares as k grows: it always falls, but it falls fast until you've captured the real groups, then flattens — the "elbow" marks a good k (three, for the blobs above). The silhouette score asks, for each point, how much closer it sits to its own cluster than to the next-nearest one; pick the k that maximizes the average. Neither is a verdict; the strongest input is theory. If you expected three segments, that's real evidence for k = 3.
Where k-means goes wrong
Because it assigns by straight-line distance to a center, k-means can only draw straight boundaries and only find convex, roughly spherical, similarly-sized clusters. Feed it two interlocking crescents and it slices them down the middle (geometrically sensible, structurally nonsense) because no pair of centers can wrap a curve. It's also sensitive to initialization: a bad set of starting centroids can converge to a poor local solution, which is why k-means++ (spreading the initial centers apart) and several random restarts are standard. Reseed the centroids on the moons and you'll see different wrong answers, each one delivered with total confidence.
That confidence is the real lesson. k-means always returns exactly k clusters, even from pure noise, so a clustering is never proof that groups exist. Clusters are hypotheses, not facts — validate them by stability, silhouette, and whether they mean anything and replicate.
Clustering without naming k first
Hierarchical clustering asks you for no k at all. It begins with every point as its own cluster, repeatedly merges the two closest clusters, and records the entire history as a tree called a dendrogram. Cut that tree low and you get many small groups; cut it high and you get a few large ones. You pick the number after seeing the structure instead of before, which is a genuinely different bargain from the one k-means offers.
What replaces k is linkage: the definition of "closest" between two clusters rather than two points. Complete linkage measures by the farthest pair, average by the mean over all pairs, and Ward merges whichever pair increases the within-cluster spread least. Single linkage measures by the closest pair, which lets a cluster grow along a chain of near neighbors.
That last one earns its keep on exactly the data k-means fails. Run all four on two interlocking moons of 100 points each and single linkage recovers both moons perfectly, putting 100% of points in the right group where k-means manages 73%. Complete, average, and Ward all land near 82%, barely an improvement. So the moral is not "hierarchical instead of k-means"; it is that a chaining linkage can follow a curve and centroid-style methods cannot. Single linkage pays for that flexibility by being easy to fool, since one stray point bridging two real groups will chain them into one.
Why it matters: k-means is the fastest route to a first map of unlabeled data — segments, profiles, structure you didn't know to look for. But it bakes in assumptions (spherical clusters, a k you chose, an initialization that matters) and it never abstains. Choose k with the elbow, silhouette, and domain knowledge; when clusters are elongated or interlocking, reach for density-based or spectral methods; and always treat the groups it hands you as a hypothesis to test, not a discovery to announce.
Common questions
How do I choose k in k-means?
There is no single correct k — it is a modeling choice you make with several tools plus judgment. The elbow method plots the within-cluster sum of squares against k and looks for the 'elbow' where adding another cluster stops buying much reduction; the catch is that the bend is often ambiguous. The silhouette score measures how much better each point fits its own cluster than the next-nearest one, and you can pick the k that maximizes the average silhouette. Gap statistics compare your clustering to random noise. But the most important input is domain knowledge: if theory says there should be three customer segments, that is strong evidence for k = 3. Try a range, look at the diagnostics and the actual clusters, and treat the answer as a hypothesis to validate, not a fact to report.
Why does k-means fail on non-spherical clusters?
Because k-means assigns each point to the nearest centroid by straight-line distance, the boundary between any two clusters is a straight line, and each cluster ends up as a convex, roughly spherical blob of similar size. When the true groups are elongated, curved, or interlocking (like two crescent moons or concentric rings), no set of centroids can carve them out, so k-means confidently returns clusters that cut across the real structure. It is not broken; it is answering the question it was built to answer (minimize within-cluster squared distance), which simply is not the question you meant. For shapes like these the right tools are density-based methods such as DBSCAN, spectral clustering, or hierarchical clustering with single linkage, which can follow a curve because it grows a cluster along a chain of near neighbors instead of around a center.
Are the clusters that k-means finds real?
Not necessarily — k-means will always return exactly the k clusters you ask for, even in data that has no real groups at all, so finding clusters is not evidence that clusters exist. Treat every clustering as a hypothesis and stress-test it. Check stability (do you get similar clusters on resampled data, or with different random initializations and different k?), quantitative quality (silhouette, gap statistic), and above all interpretability (do the clusters correspond to something meaningful in the world, and do they replicate in a fresh sample?). Because the algorithm is also sensitive to its starting centroids, use a smart initializer like k-means++ and several restarts. Real structure survives all of this; artifacts of the algorithm do not.