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 works without labels and asks a more exploratory question: are there natural groups in these data at all? It can find customer segments, species, or symptom profiles you did not know to look for. k-means, the most widely used method, is simple and useful but easy to fool.
Unsupervised: structure without answers
In unsupervised learning there is no outcome to predict and nothing to be "right" about. You give the algorithm feature vectors and ask it to organize them. Clustering, the most common kind, divides the data into groups so that points in the same group are similar and points in different groups are not. The result is a hypothesis about hidden structure, which you then have to interpret and validate, because the algorithm will produce 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.
Neither step can increase the total within-cluster spread, so the loop always converges, usually within a few iterations. Step through it below and watch the centroids move into place. (You can also drag any point to 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 and update (gray points are not yet assigned), and the centroid trails show their path. Build the elbow plot by moving the k slider. Then switch to Two moons, where k-means returns a clean split that cuts across both moons. Drag any point to reshape the data.
Choosing k
You supply k, so choosing it well matters more than anything else. 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 have captured the real groups, and then flattens. The bend, or "elbow", marks a good k (three, for the blobs above). The silhouette score asks, for each point, how much closer it is to its own cluster than to the next-nearest one; pick the k that maximizes the average. Neither diagnostic settles the question, and theory is the strongest input. If you expected three segments before you looked, that is good 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. Give it two interlocking crescents and it cuts them down the middle, a split that makes geometric sense but ignores the real structure, because no pair of centers can follow a curve. It is also sensitive to initialization: a bad set of starting centroids can converge to a poor local solution. So k-means++ (spreading the initial centers apart) and several random restarts are standard. Reseed the centroids on the moons and you will get different wrong answers, each with no warning.
k-means always returns exactly k clusters, even from pure noise, so a clustering is never proof that groups exist. Validate the clusters by their stability and silhouette, and by whether they mean something and replicate.
Clustering without naming k first
Hierarchical clustering does not ask for k. 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 of clusters after seeing the structure, where k-means makes you pick it before.
Hierarchical clustering needs a different choice, the 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.
Single linkage works well on the data where k-means fails. Run all four on two interlocking moons of 100 points each: single linkage recovers both moons perfectly, putting 100% of points in the right group, where k-means gets 73%. Complete, average and Ward all score near 82%, barely better. So hierarchical clustering is not better in general. A chaining linkage can follow a curve, and methods built around centers cannot. The cost of that flexibility is that single linkage is easy to fool: one stray point between two real groups can chain them into one.
Why it matters: k-means is the fastest way to get a first map of unlabeled data, such as segments, profiles, or structure you did not know to look for. But it builds in assumptions (spherical clusters, a k you chose, a starting point that matters), and it returns clusters whether or not real groups exist. Choose k with the elbow, the silhouette and your knowledge of the field. When clusters are elongated or interlocking, use density-based or spectral methods. And treat the groups it finds as a hypothesis that still needs testing on new data.
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 another cluster stops reducing it by much, but the bend is often unclear. 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 with clusterings of random noise. The most important input, though, is knowledge of the field: 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. 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 separate them, so k-means returns clusters that cut across the real structure. The algorithm is working correctly. It minimizes within-cluster squared distance, and that is not the question you meant to ask. For shapes like these, use density-based methods such as DBSCAN, spectral clustering, or hierarchical clustering with single linkage. Single linkage can follow a curve because it grows a cluster along a chain of near neighbors, not around a center.
Are the clusters that k-means finds real?
Not necessarily. k-means always returns exactly the k clusters you ask for, even in data with no real groups at all, so finding clusters is not evidence that clusters exist. Treat every clustering as a hypothesis and 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?). The algorithm is also sensitive to its starting centroids, so use a careful initializer such as k-means++ and several restarts. Clusters that reflect real structure pass these checks, and artifacts of the algorithm usually do not.