Clustering, and What the Objective Assumes

Four well-separated groups, $k$ genuinely identifiable. Twelve points in four tight triples at the corners of a square, at $(0,0)$, $(8,0)$, $(0,8)$, $(8,8)$. Best WCSS by $k$:

The drop at $k=4$ removes $97.0\mathrm{\%}$ of what remained; the next removes $14.7\mathrm{\%}$. That collapse is what an elbow actually looks like, and here $k=4$ is defensible.

One elongated blob, no $k$ to find. Forty points drawn from a Gaussian with standard deviations $3$ and $1$. A single cloud, stretched. The same procedure gives drops of $58.3\mathrm{\%}$, $51.7\mathrm{\%}$, $40.1\mathrm{\%}$, $29.7\mathrm{\%}$, $18.0\mathrm{\%}$, $20.8\mathrm{\%}$.

No cliff. The reductions decay smoothly, and the last one is larger than the one before it, so the sequence is not even monotone. The curve identifies no number of groups, because there are none to identify. A reader determined to find an elbow could point at $k=2$ or $k=3$ and neither claim would survive the next drop.

Two concentric rings, where the criterion favours a different partition. Twelve points at radius $1$, twenty-four at radius $4$. With $k=2$, the best partition k-means finds over $1000$ restarts scores $263.9069$ and cuts both rings by angle, $18$ points against $18$. The by-ring partition scores $396.0000$.

The method is not failing to find the rings. It is rejecting them, correctly, under the criterion it was given.

The same rings under a different criterion. Single linkage merges the two groups whose nearest members are closest. Applied to the same thirty-six points with $k=2$, it returns exactly $12$ and $24$. The rings, recovered. Nothing about the data changed; the definition of a good group did.

---

The first is the case the elbow method is sold on, and it works. The second shows the same plot produced from data with no structure, which is why the plot alone is not evidence. The third shows the objective preferring an answer the analyst does not want, which no amount of computation will overturn. The fourth shows that the disagreement was never about the data. Two criteria, two different right answers.

A bad search against a bad criterion.

Both look identical from the outside: a result that disagrees with what you expected. The single computation that separates them is the objective value of the partition you wanted. If it beats what was returned, the search failed. If it loses, the search succeeded and the criterion is the thing that does not match.

The two failures have opposite remedies, and restarts address only the first.

A sharp elbow against a smooth decay.

Four separated groups: drops of $49.6\mathrm{\%}$, $49.2\mathrm{\%}$, $97.0\mathrm{\%}$, $14.7\mathrm{\%}$. One elongated blob: $58.3\mathrm{\%}$, $51.7\mathrm{\%}$, $40.1\mathrm{\%}$, $29.7\mathrm{\%}$, $18.0\mathrm{\%}$.

Both curves fall monotonically; both can be plotted and pointed at. Only the first contains a discontinuity, and it is the discontinuity rather than the downward slope that carries the information. Note that the blob's first drop, $58.3\mathrm{\%}$, is larger than three of the four-group case's drops, so "a big drop" is not the signal. The signal is a big drop followed by a small one.

k-means against single linkage, on identical data.

The thirty-six ring points, $k=2$. k-means returns $18/18$, cutting across both rings; single linkage returns $12/24$, one ring each. Same points, same $k$, different answers, because one criterion scores closeness to a centre and the other scores connectivity between nearest members.

Neither is the true clustering. What single linkage gains in recovering elongated structure it pays for in fragility: a single point between the rings would chain them into one cluster, which is a failure mode k-means does not have. Neither method dominates.

Convergence against optimality.

Run 1 and run 2 on the nine points both satisfy the stopping condition exactly. No point improves alone, every centroid at its members' mean. One scores $0.7800$, the other $14.0850$. Convergence is a property both share, and optimality is not.

A number of groups the data supports, against a number you supplied.

k-means with $k=5$ on the four-group data returns five clusters, splitting one real group in two. It does not report that the fifth was unnecessary. The objective improved by $0.4350$, so by its own criterion the fifth group was an improvement. Nothing in the output distinguishes a $k$ the data supports from a $k$ it merely tolerates.

That once k-means stops changing its labels it has found the best partition, so a single run settles the question. Convergence only means no single point lowers the objective by changing clusters and every centroid is at its members' mean; it says nothing about whether another partition scores better. On the nine-point dataset of this unit, two nearby groups of three on the left and one distant group of three on the right, the optimal three-cluster partition has within-cluster sum of squares $0.7800$, while an initialisation placing two centroids inside the distant group converges to $14.0850$, worse by a factor of $18.0577$. Both runs converged; one is eighteen times worse. Over $2000$ random initialisations, $508$ of them, $25.4\mathrm{\%}$, settled on a solution worse than the optimum, so this is the common case rather than a contrived one. What detects it is running the algorithm several times from different starts and keeping the solution with the lowest objective value, which is why implementations default to multiple restarts.

That a dataset has a true number of clusters and a true grouping, which a good method finds and a bad one misses. A clustering method returns the partition that best satisfies a stated criterion, and different criteria have different best answers on the same data. On the two concentric rings of this unit, twelve points at radius $1$ and twenty-four at radius $4$, k-means with $k=2$ returns a partition cutting both rings by angle, sizes $18$ and $18$, with within-cluster sum of squares $263.9069$. The grouping by ring, which every reader sees, scores $396.0000$. The intended answer is not merely missed: it is worse by the objective k-means minimises, so the algorithm returned the correct answer to the question it was asked. Single linkage, whose criterion is the distance between the nearest members of two groups rather than the spread around a centre, recovers the rings exactly at sizes $12$ and $24$. Neither answer is the true one; the question is which criterion matches what the grouping is for.