Clustering, and What the Objective Assumes

Thirty-six points lie on two concentric rings, twelve on an inner circle, twenty-four on an outer one. Anyone looking at them sees two groups.

Run k-means with $k=2$. It returns two half-moons, slicing both rings by angle: eighteen points and eighteen points, each cluster holding part of the inner ring and part of the outer.

The instinct is that the algorithm converged badly and more restarts would fix it. That instinct is wrong, and checking it is what this unit is about. The half-moon partition scores $263.9069$ on the objective k-means minimises. The by-ring partition, the one the eye wants, scores $396.0000$.

The answer you wanted is worse by the criterion you asked for. Nothing was broken.

This matters because clustering has no test set. There is no response variable, nothing held out, no error to estimate, so the usual way of finding out that a model is wrong is unavailable. What replaces it is knowing which partitions the criterion scores well, and this criterion scores points sitting close to a centre. The mean of a ring falls in the hole.

Two further things about k-means are worth the same scrutiny. It stops at a partition no single point can improve, which is not the best partition: on a nine-point dataset in this unit, a quarter of random starts converge to an answer eighteen times worse than the optimum. And the curve usually used to choose the number of groups falls monotonically whatever the data, so on data with no separated groups it still produces a plot, and reading a $k$ off it means reading in something that is not there.

This unit covers the procedure, what convergence guarantees, how to tell a real elbow from a smooth decay, and how to recognise when the objective rather than the algorithm is the thing that failed.

The canonical statement above gives the objective and the two steps. What follows is what each piece commits you to, since that is what decides how a result should be read.

The objective is a choice, and it is the whole of the method's opinion. Everything k-means believes about what a group is lives in

The two steps are a search procedure for minimising it; swap in a different criterion and you have a different method, not a different implementation. So when a result looks wrong, the question splits: did the search fail, or was the criterion never going to reward the answer you wanted? These have different fixes and are diagnosed differently.

Why both steps only ever lower the objective. Assignment moves a point to a nearer centroid, which cannot raise its squared distance term. Update moves a centroid to the mean of its members, and the mean is the unique minimiser of $\sum \Vert x_i-c{\Vert }^2$ over $c$, that is a property of squared error specifically, and it is why the algorithm is stated with means rather than medians.

What convergence certifies, exactly. Two conditions hold at the end: no single point lowers the objective by changing groups, and each centroid sits at its members' mean. Both are local, statements about single moves. A partition can satisfy both and still be far from optimal, because escaping would require several points to move together, which the algorithm has no mechanism to do.

$k$ is an input. The method partitions into exactly the number of groups it was given. It has no way to report that the data does not support that number, and no way to report that it supports a different one.

Distance is not neutral. Squared Euclidean distance makes the objective scale-dependent: rescale one coordinate and a different partition minimises WCSS. Whether to standardise is therefore a decision about how much each variable should count, taken before clustering and never recoverable from the output.

Each iteration assigns every point to its nearest centroid and then moves each centroid to the mean of its members. Both steps decrease the within-cluster sum of squares or leave it unchanged, and the number of possible assignments is finite, so the algorithm terminates.

Termination is a weaker guarantee than it appears, and three distinct things can go wrong.

Convergence to a local optimum. The algorithm stops when no single point lowers the objective by changing clusters. That condition can hold at a partition far from the best one. On the nine-point dataset in this unit, an initialisation placing two centroids inside one tight group converges to WCSS $14.0850$ against an optimum of $0.7800$, worse by a factor of $18.0577$; $508$ of $2000$ random initialisations, $25.4\mathrm{\%}$, converge to a solution worse than the optimum. Escaping such a partition requires several points to move together, which the update rule cannot do. Restarting from different initialisations and keeping the lowest objective value addresses this failure and no other.

Choosing $k$ from the objective. WCSS decreases monotonically as $k$ increases, since any $k$-partition can be refined into a $(k+1)$-partition without raising the objective, and reaches zero at $k=n$. A decreasing curve therefore carries no information about whether clusters exist. What can be informative is a discontinuity in the successive reductions. On this unit's four-group data the reductions are $192.0000$, $96.0000$, $96.0000$, then $0.4350$: the fourth centroid removes $97.0\mathrm{\%}$ of what remained and the fifth removes $14.7\mathrm{\%}$. On a single elongated Gaussian cloud with no groups, the reductions are $58.3\mathrm{\%}$, $51.7\mathrm{\%}$, $40.1\mathrm{\%}$, $29.7\mathrm{\%}$, $18.0\mathrm{\%}$, $20.8\mathrm{\%}$, decaying smoothly and not monotonically. Both curves slope downwards; only the first contains a value of $k$ to select.

Mismatch between the objective and the cluster structure. Minimising squared distance to a cluster mean favours clusters that are compact around a centre. For a ring of points the mean lies at the centre of the ring, where no data is, so every point is far from it. On the two concentric rings in this unit, k-means with $k=2$ returns a partition cutting both rings by angle, WCSS $263.9069$, while the by-ring partition scores $396.0000$. The by-ring answer is not missed by an incomplete search: it is worse under the objective being minimised, so additional restarts cannot produce it. Single linkage, whose criterion is the distance between nearest members rather than spread about a centre, returns the two rings exactly.

The three modes are distinguishable by evidence. If the intended partition scores better than the returned one, the search failed and restarts are the remedy. If it scores worse, the criterion does not match the structure and a different method is required.

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.

To run k-means on a small dataset by hand.

1. Decide on scaling first. Squared Euclidean distance treats a unit of one variable as equal to a unit of another. If the variables are in different units, standardise, and record that you did, because the partition depends on it.
2. Choose $k$ and place the initial centroids. Record where they started. A result is not reproducible or diagnosable without this.
3. Assign. Compute each point's squared distance to every centroid; give it the label of the nearest.
4. Update. Move each centroid to the coordinatewise mean of its assigned points.
5. Repeat from step 3 until the labels stop changing. The stopping condition is label stability, not a fixed iteration count, stopping at a count leaves you unable to say whether the result is a converged partition or a snapshot of one still moving.
6. Compute the final WCSS and report it alongside the partition. A partition without its objective value cannot be compared with anything.

To establish that a solution is worth reporting.

1. Restart. Run steps 2–6 several times from different initialisations.
2. Compare by objective value, not by appearance. The solution with the lowest WCSS is the best one found; how reasonable a partition looks is not the criterion the method used.
3. Report the best and say how many restarts produced it. "Lowest WCSS over 50 restarts" is a claim a reader can weigh; "k-means gave this" is not.
4. If the restarts disagree substantially, say so. A wide spread of objective values across starts is information about the data, it means the landscape has distinct basins, and suppressing it overstates how determinate the answer is.

To read a WCSS curve.

1. Compute the best WCSS at each $k$, each from multiple restarts, so the curve reflects the objective rather than the luck of initialisation.
2. Tabulate the successive drops, in absolute terms and as a percentage of the previous value.
3. Look for a discontinuity in the drops, not a bend in the curve. A curve always slopes downwards; what distinguishes a real elbow is a large drop followed by a much smaller one.
4. If the drops decay smoothly, name no $k$. That is the finding. Reporting a number anyway attributes structure to data that does not show it.

To diagnose a result that disagrees with what you see.

1. Compute the objective value of the partition you expected, and compare it with the one returned.
2. If yours scores worse, the search did not fail. The returned answer scores better on the criterion, and the mismatch is between the criterion and your notion of a group. Restarts will not help.
3. If yours scores better, the search did fail, and more restarts are exactly the fix.
4. Only then consider a different method, choosing by what its criterion scores rather than by reputation.

Checks. Confirm each centroid lies at the mean of its own members, if not, the update step was applied incorrectly or the run has not converged. Confirm the objective fell at every step; a rise means an arithmetic error, since neither step can raise it. And before reporting a cluster count, ask what the drop sequence would look like if the data had no groups at all: if you cannot say how that would differ from what you are looking at, the curve is not evidence.

The data. Nine points in two dimensions: two groups of three close together on the left, one group of three far away on the right.

We want $k=3$.

The optimum, established by enumeration. Rather than trusting the algorithm, enumerate every way of splitting nine points into three non-empty groups, compute each partition's WCSS exactly, and take the minimum. The best partition has L1, L2 and R each forming a cluster, with

This is the benchmark. Every result below is compared against it, so "worse" means worse than a verified optimum rather than worse than another run.

Run 1: one seed per group. Start the centroids at $(0.0,0.0)$, $(3.0,0.0)$, $(20.0,0.0)$.

Assignment. Each point is nearest the seed in its own group. The between-group gaps ($3.0$ and $17.0$) dwarf the within-group spread (under $0.5$), so the labels are $[0,0,0,1,1,1,2,2,2]$.

Update. Each centroid moves to its group's mean: $(0.2,0.0)$, $(3.2,0.0)$, $(20.2,0.0)$.

Assignment again. No label changes. Converged.

Run 2: two seeds inside the far group. Start at $(20.0,0.0)$, $(20.4,0.3)$, $(0.0,0.0)$. Nothing about this is perverse: it is what happens when initial centres are drawn at random and two land in the same place.

Assignment. The two right-hand seeds split group R between them. The single left seed at $(0.0,0.0)$ is nearest for all six left points, since every one of them is closer to it than to anything near $x=20$.

Update. The left centroid moves to the mean of all six left points, $(1.7,0.0)$. A location with no data near it, sitting in the gap between L1 and L2.

Assignment again. The left points remain nearest that centroid; the right points remain with the two right centroids. Labels settle as $[2,2,2,2,2,2,0,1,0]$.

Both runs converged. In each, no point improves by moving alone and every centroid sits at its members' mean. The definition of convergence is met identically. Yet

so the second answer is eighteen times worse on the very quantity being minimised.

Why run 2 cannot escape. To reach the optimum, one of the two right-hand centroids would have to relocate to the left region. It moves only to the mean of its assigned points, and its assigned points are all on the right. Meanwhile no left point can improve by switching, since both alternatives are far away. The partition is locally unimprovable and globally poor, and the algorithm has no mechanism to notice.

How often this happens. Running k-means from $2000$ random initialisations on this data:

A quarter. Not an edge case.

What detects it. Nothing inside a single run. The objective value of one converged solution carries no information about whether a better one exists, $14.0850$ looks like a number, not like a failure. Only comparison across restarts reveals it: run the algorithm many times from different starts, keep the solution with the lowest WCSS. That is why implementations default to multiple restarts, and why reporting a clustering from a single run leaves out the one check that would have caught the problem.

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.

Reporting a single run. One converged solution carries no information about whether a better one exists: $14.0850$ looks like a number, not like a failure. On this unit's nine-point data, $25.4\mathrm{\%}$ of random starts converge to a solution worse than the optimum, and nothing inside such a run signals it. A clustering reported without restarts has omitted the only check that would have caught the problem.

Reading a $k$ off any downward curve. WCSS falls as $k$ rises by construction, at $k=n$ it is zero. A downward curve is therefore guaranteed whether or not groups exist, and the elongated blob in this unit produces a perfectly respectable-looking plot with nothing in it. Naming a $k$ requires a large drop followed by a much smaller one, not a bend that can be pointed at.

Treating a disagreement with the eye as an algorithmic failure. When the returned partition differs from the expected one, compute the expected partition's objective value before concluding anything. On the rings it scores $396.0000$ against the returned $263.9069$, so the algorithm was right and more restarts would be wasted effort. Reaching for restarts first is the common reflex and it is diagnostically backwards.

Clustering unstandardised variables without saying so. Squared Euclidean distance makes income in euros and age in years directly comparable, which they are not. Rescaling one variable changes which partition minimises the objective, so the partition is partly a consequence of the units the data happened to arrive in. Standardising is also a choice, it asserts every variable should count equally, and that choice belongs in the report.

Interpreting clusters as kinds. The method partitions into exactly the $k$ it was given, whatever the data. Groups will be returned from data with no group structure at all, and they will have centroids, sizes and profiles that can be described at length. That a cluster can be characterised is not evidence that it corresponds to anything.

---

Two that follow from having no test set.

Looking for held-out validation that does not exist. Nothing was predicted, so there is no error to estimate and no split that would settle the question. The discipline that replaces it is knowing which partitions the criterion scores well and checking whether that matches the intended notion of a group, which is reasoning done before and after the fit, not a number computed from it.

Taking stability for correctness. A partition that reappears across restarts is reliably found, which is a fact about the objective's landscape rather than about the data's structure. The rings partition is perfectly stable: k-means returns the same $18/18$ split repeatedly, and it is the same wrong answer every time.

---

And one about the status of the output. Clustering is an exploratory move that proposes groups for a human to interpret, and every step of it, the choice of $k$, the distance, the scaling, the criterion, encodes an assumption the output cannot report back. A clustering presented as a discovery about the data, rather than as the output of a stated set of choices, has hidden the part a reader most needs in order to disagree with it.

Customer segmentation. The commercial question is which customers to treat alike, and k-means on standardised spending and frequency variables gives a workable answer, because segments defined by "similar on these measures" are exactly blobs around a centre. What the method cannot supply is $k$: the number of segments is usually decided by how many distinct campaigns the business can actually run, which is a constraint from outside the data. That is a legitimate way to choose $k$, and it is more honest than deriving the same number from an elbow plot that does not contain it.

Vector quantisation and image compression. Here the criterion is not a proxy for anything. The goal genuinely is to replace each observation with a representative minimising squared error, which is what WCSS measures. Clusters need not correspond to any real category, and nobody interprets them. This is the case where k-means is not an approximation to a better method; it is the method, and the local-optimum problem is handled exactly as this unit prescribes, by restarts compared on objective value.

Document and gene-expression grouping, where the metric is the decision. Squared Euclidean distance on raw counts makes long documents and highly expressed genes dominate, so the substantive work is choosing a representation and distance, cosine similarity, correlation distance, before any clustering runs. The choice determines the answer more than the algorithm does, and it is made on subject-matter grounds that the data cannot settle.

Anomaly detection, where the ring failure is the point. Normal behaviour often occupies a shell or manifold rather than a ball, network traffic within operating bounds, sensor readings on a cycle. A centroid-based method placing a centre in the middle of that shell will score genuinely anomalous points near the centre as typical, since they are close to the mean. This is the concentric-rings failure with consequences, and it is the standard argument for density- and connectivity-based methods in this setting.

Preprocessing for a supervised model. Cluster labels used as features inherit every choice above, and the danger is specific: clustering the full dataset before splitting lets information from the held-out rows influence the features, so the later error estimate is optimistic. The clustering must be fitted on the training split alone and applied to the rest. The same discipline the evaluation unit establishes, applied to a step that does not look like model fitting.

---

In each case the analyst supplies the notion of a group, through $k$, the distance, the scaling, the representation, and the algorithm supplies only the search. The cases where k-means is the right tool are the ones where a cluster genuinely is a blob around a centre, and the cases where it misleads are the ones where that was assumed without being noticed.