The within-cluster sum cannot choose K

Topic: K-means clustering · more questions on this topic
‹ Reading the gap statistic What a K-means diagram must show ›

A student reports that K=10 is best because it gives the smallest total within-cluster sum of squares among K=1,\ldots,10. Explain what is wrong with the argument and what to compute instead.

Worked answer (click to show)

Ask what the unpenalised objective would prefer if every observation were allowed its own cluster. That limiting case shows why raw training fit cannot select complexity.

The globally minimised within-cluster sum of squares never increases as clusters are added, because any partition into K clusters can be refined into K+1 clusters without raising the criterion, and it equals 0 when every point is its own cluster. Finite runs from poor starts need not follow this ordering, but the global objective favours the largest K tried. The comparison says nothing about structure. Use a criterion that accounts for how much improvement is expected by chance, or that penalises complexity. The gap statistic compares \log W with its value under a structureless reference. A plot of W against K asks where the decrease levels off. For a mixture model, a penalised likelihood such as BIC, or a likelihood computed on held-out observations, plays the analogous role.