The two steps.
Reassign points colors every point by whichever centroid is nearest — the shaded
regions show those territories. Update centroids moves each centroid to the mean of its own
points. Nothing else ever happens: k-means is just these two steps until nothing changes.
Three things worth trying.
1. Packed circles, k = 4, and put all four centroids in one corner. About five times out of
six it gets stuck, and almost always in the same way: two circles end up sharing a single centroid
while a third circle is split down the middle. J lands at roughly double its best value. Reset,
place the four sensibly, and watch J halve.
2. Now try the same sabotage on Gaussian mixture, k = 3 — put all three centroids
inside one blob. It recovers every time. When clusters are this well separated the starting point
barely matters; a bad start only really bites when the clusters are close together.
3. Elongated, k = 2 — two long thin clusters lying side by side. k-means cuts
straight across them instead of separating them, and only about 60% of points land
in the right group. The interesting part is that this is not a bad start: 200 random
restarts all converge to the same answer, because that answer genuinely has the lower J. Splitting
the data into one cigar each scores J = 2,242,000, while the wrong crosswise answer scores
1,444,000. Restarting cannot help, because k-means is not failing to optimize — it is
optimizing the wrong thing. Squared distance to a center rewards compact balls, and a long thin
cluster is not a ball. These are the identical 180 points as Elongated on the GMM page,
where a full covariance gets every one of them right.
4. Try Smiley at k = 3. Usually k-means lumps both eyes into one cluster and chops the
mouth in half; it only lands on the true eyes-and-mouth answer about one start in ten, and from
k = 6 upwards it can no longer keep the mouth in one piece at all. The mouth is what breaks it:
k-means territories are straight-edged wedges, and a long curve is not. Unlike (1), restarting
barely helps here — the shape of the answer is wrong, not the starting point. That gap is
exactly what density-based methods like DBSCAN exist to fill.
| Topic | Use | What the class should see |
|---|---|---|
| K-Means | Packed circles + Gaussian mixture |
Gaussian mixture is the case k-means was built for — round, separated, equal-sized — and it scores 1.00. Then switch to packed circles and put all four centroids in one corner: it gets stuck about five times in six, with J roughly doubling. The failure is the starting point, not the algorithm. |
| Agglomerative Hierarchical |
Gaussian mixture | Run it once per linkage on the same points. Ward recovers the three blobs exactly (1.00); single linkage manages only 0.57 on that identical data, because one near-pair is enough to chain two blobs together. The lesson is that the linkage choice matters more than the data does. |
| DBSCAN and Mean Shift |
Uniform + Gaussian mixture |
These two choose their own number of clusters, so the interesting question is whether they can decline. On the blobs Mean Shift answers “3” at every bandwidth tried, and DBSCAN holds at 3 across a wide band of ε. On uniform, Mean Shift reports 8, 12 or 18 clusters depending only on the bandwidth, and DBSCAN 6 — all invented, since there is nothing there. Stability across parameters is the evidence that structure is real. |
| GMM and Fuzzy C-Means |
Uniform + Smiley |
Both give every point a degree of membership, which is invisible on easy data: on the blobs 69% of points are more than 90% committed to one cluster, so it just looks like k-means. On uniform only 21% are that certain, so the graded membership is finally worth drawing. Then Smiley shows the limit: GMM scores about 0.48 where k-means and hierarchical reach 1.00, because an ellipse cannot follow a curve. |