K-means
Cluster random data into solar systems, then break it with the wrong k, rings and supernovas. Each sun pulls in its nearest points, then moves to their centre, again and again. Broke it? See the fix: DBSCAN
The numbers
The fix: DBSCAN
Rings, spirals and supernovas break k-means because it can only cut space into convex cells around its suns. DBSCAN never draws cells. A point is core when at least minPts points sit within eps of it, and clusters flood outward from core to core, so they can take any shape. Points a flood reaches but cannot pass through are border; points no flood reaches are noise.
How it works
Pick k starting suns. Then repeat two steps. Assign: every point joins its nearest sun. Update: every sun moves to the mean of the points that joined it. Each step can only lower the total squared distance, so it always settles, usually within a few dozen rounds.
It settles on a nearby answer, not always the best one. Random starts can put two suns in one cluster and none in another. k-means++ picks each new sun with a chance proportional to D(x)², the squared distance to the nearest sun so far, which spreads them out and is provably close to the best on average.
It assumes round, similar-sized clusters. Rings, spirals and roses break it: it slices them like a pie. Outliers drag a sun away, and a sun that loses every point collapses. Words mode turns each word into two numbers and clusters those, which is all k-means ever sees.
The fix below is DBSCAN. It needs no k: pick a radius eps and a count minPts. Core points have at least minPts points within eps, clusters are everything you can reach by hopping between core points, border points are reached but have too few neighbours to carry on, and everything else is noise. The k-distance chart helps choose eps: sort every point's distance to its (minPts - 1)th neighbour, and the knee where the curve shoots up separates dense regions from gaps.
two simple steps, nearest and average, repeated until nothing moves, find structure in almost anything.