Why does k-means cut one elongated band of points into three round clusters?
answer
- what shape does the objective reward?
- boundaries are straight lines between centres
- spread along the long axis is expensive
- convex cells cannot bend around a shape
basics
~10 sk-means minimises total squared distance to cluster centres, so it rewards compact, roughly round groups. An elongated band has large spread along its long axis, so slicing it crosswise lowers that objective.
solid answer
~40 sThe objective is the whole story. k-means minimises the within-cluster sum of squares, and a long thin band contains points far from any single centre placed inside it, which is expensive. Putting three centres along the band and cutting it crosswise shortens every point's distance to its centre, so the split genuinely scores better — the algorithm is not failing, it is optimising something that does not match what you mean by a cluster. Geometrically, each point joins its nearest centroid, so every boundary is the perpendicular bisector between two centres: the regions are convex cells with straight sides that cannot bend around a curved or stringy shape. Take runners' pace-versus-distance data, one diagonal band: k = 3 returns three arbitrary segments of a continuous trend, and raising k only makes finer slices.
go deeper
Be ready to say that k-means assumes compact, roughly round groups of similar size, and that long or curved shapes break that assumption. Recognising the picture of a band cut crosswise is enough at this level.
Explain the mechanism both ways: the objective penalises squared distance so splitting a stretched group lowers it, and nearest-centroid assignment makes every cluster region a convex cell with straight boundaries. Say why raising k does not help.
Show the diagnosis. Separate shape mismatch from bad seeding, unscaled features and a wrong k, using restart agreement and where boundaries fall relative to dense regions. Then state the remedy you would choose and what you would tell the stakeholder.
Own the call between reshaping the features, switching to a method with different shape assumptions, and declaring that no meaningful clusters exist. Decide when convenience buckets are an acceptable deliverable and how that must be communicated.
## The failure is built into the objective k-means minimises `WCSS = sum over clusters of sum over its points of ||x - centroid||^2` — the total squared distance from each point to its own cluster's centre. Every property people associate with k-means output follows from that one line: - **It prefers compact clusters.** Distance is penalised, and squared distance is penalised harshly, so a far-flung member costs far more than two moderately distant ones. - **It prefers roughly round (isotropic) clusters.** The penalty is the same in every direction, so the objective has no way to express "this group is legitimately stretched along one axis". - **It prefers clusters of similar diameter.** A group with large spread contributes a lot of cost and is an attractive candidate to split; a tight group is cheap and is a tempting place to merge into a neighbour. An elongated band violates the second and third of these directly. Suppose the true structure is a single diagonal band — runners plotted as average pace against distance run, where faster paces go with shorter distances and the whole population lies along one continuous trend. Put one centre in the middle of that band and every runner at either end is far away, at a squared cost. Put three centres along the band and cut it crosswise into three chunks, and every runner is now close to a centre. The objective drops. **The crosswise slicing is not a mistake in the arithmetic; it is the correct answer to the question k-means was asked.** ## The geometric restatement A point is assigned to whichever centroid is nearest. For any two centroids, the set of points equidistant from both is the perpendicular bisector of the segment joining them — a straight line in two dimensions, a flat hyperplane in more. So the feature space is carved into a Voronoi partition: every cluster region is convex, with flat boundaries, and every cluster is the set of points inside one such cell. That single fact tells you what k-means can never produce: a cluster that curves, wraps, or has a hole, because such a region is not convex. If the structure you are looking for is not describable as "everything nearest to this point", k-means cannot express it no matter how well it optimises. ## Distinguishing this failure from the ones that look like it Senior candidates are expected to tell four things apart, because the remedies are unrelated: 1. **A bad local optimum.** Different runs give materially different groupings. Remedy: better seeding and more restarts. 2. **Features on incomparable scales.** One feature spans thousands and another spans single digits, so distance is effectively one-dimensional and the clusters line up with the large-range feature. Remedy: put the features on comparable scales before fitting. 3. **A wrong number of clusters.** The groups are blob-shaped but sub-divided or merged relative to what the domain expects. 4. **A shape mismatch — this case.** Every run agrees, the features are scaled, and the boundaries still cut across visibly continuous structure. The tell for case 4 is *stability of the wrong answer*: restart it ten times, and the crosswise cuts appear in nearly the same places every time, with the boundaries falling in the middle of dense regions rather than in gaps. Real cluster boundaries fall where the data is sparse; these fall where the data is thickest. ## Raising k does not rescue it The reflex response is to increase the number of clusters until the picture looks better. This never recovers the band: it splits it into more, smaller convex pieces. The objective keeps falling, which makes the change look like an improvement, and you now have six arbitrary segments of a trend instead of three. The pieces are stable, reproducible and meaningless — the worst combination, because they survive every sanity check that measures consistency instead of validity. ## What a senior actually does about it - **Check whether groups exist at all.** The band may be a continuous gradient rather than a set of populations. If a domain expert cannot say what makes the boundary between segment one and segment two meaningful, there probably is no boundary. Reporting "there are no natural clusters here, there is a trend" is a legitimate and often correct result. - **Reshape the features so the structure becomes blob-like.** If the elongation reflects one dominant direction of variation, working in a rotated or derived coordinate system, or replacing two correlated features with a ratio the domain actually uses, can turn a stretched band into separated compact groups — or reveal that it stays one group. - **Change the method, not the settings.** Methods that model clusters as stretched, that build clusters from connectivity, or that grow them from dense regions can represent shapes k-means cannot. Choosing one of those is a modelling decision, not a tuning decision. - **Say what the segments are for.** If the deliverable is a manageable set of buckets for an operational process, arbitrary but stable slices of a trend may be acceptable — as long as everyone is told they are convenience bins, not discovered populations. The defect is claiming discovery, not the slicing itself.
- Would raising the number of clusters rescue the elongated band?No. It chops the band into more convex pieces rather than recovering it as one cluster. The within-cluster sum of squares keeps falling, so the change looks like progress while producing finer arbitrary slices of the same continuous trend. Shape mismatch is not a tuning problem, and no value of k makes a Voronoi cell curve.
- How would you tell a shape mismatch from an unlucky initialisation?Restart the fit many times from different seeds and compare. Unlucky initialisation shows up as runs that disagree materially and as a wide spread of objective values. Shape mismatch shows up as the opposite: every run lands on nearly the same cuts, and those cuts fall through dense regions instead of through gaps. A stable wrong answer is the signature.
- When are arbitrary slices of a continuous trend still acceptable to ship?When the deliverable is a set of operational buckets rather than a claim about discovered populations — for example a manageable number of tiers a team can act on differently. The requirement is honesty in the write-up: say the boundaries are conveniences chosen by an objective, note they will move if the data shifts, and never present them as natural groups.
Cutting a long baguette into three pieces makes each piece compact and easy to hold, but the pieces were never three separate loaves.
saying these in an interview costs you the question
- Increases the number of clusters until the picture looks right
- Blames the random seed for a shape mismatch
- Says more data or more iterations will fix it
- Claims k-means can find clusters of any shape given enough clusters
- Never checks whether the features are on comparable scales
- Presents slices of a continuous trend as discovered populations