Choosing K: the gap statistic

Section of K-means clustering, part of Statistical learning

Type	Section
Taught in	K-means clustering
Part	Statistical learning
Questions using it	1

The criterion \widetilde W falls as K increases, and it equals zero at K=n, with one cluster for each point. Minimising it over K therefore selects the largest K on the list. The objective that justifies the algorithm cannot choose K. Choosing K is a model-selection problem: which member of a family is appropriate, once each member can be fitted. A Bayesian treatment would put a prior on K and report a posterior. This section seeks one K. For K-means, one standard comparison is the gap statistic. It asks how much smaller \log W is for the data than for reference samples that have the same coordinate-wise range and no clusters.

Record the coordinate-wise sample minima and maxima. Run K-means for each k=1,\ldots,K_{\max} on the data and store the within-cluster scatter W_{\mathrm{data}}^{(k)}. Draw B reference samples of size n from the uniform distribution on the box with those minima and maxima as corners, in the same spirit as a draw from a featureless distribution on that box. For each reference sample and each k, run K-means and store W_b^{(k)}. The gap and its simulation scale are

\operatorname{Gap}(k)=\frac1B\sum_{b=1}^B\log W_b^{(k)}-\log W_{\mathrm{data}}^{(k)},

s'(k)=\sqrt{1+1/B}\times\bigl(\text{standard deviation of }\log W_1^{(k)},\ldots,\log W_B^{(k)}\bigr).

Choose the smallest k at which a further cluster does not raise the gap by more than that scale,

k^*=\min\bigl\{k:\operatorname{Gap}(k)\ge\operatorname{Gap}(k+1)-s'(k+1)\bigr\}.

Equivalently, k^* is the smallest k with \operatorname{Gap}(k+1)-\operatorname{Gap}(k)\le s'(k+1): the next increase in the gap is no larger than the variability of the reference scores at k+1 clusters. Take the smallest k at which adding a cluster no longer improves the gap beyond that variability.

The rule is a comparison with a chosen reference distribution, not a test proving that a particular number of populations exists. Its result depends on the reference geometry and on how well each clustering optimisation is solved. The reference box may be aligned with the coordinate axes, or it may be aligned with the principal components of the data. The two boxes need not give the same answer.

An outlier can stretch the reference box and change the benchmark substantially. Rotating to principal components addresses orientation and does not make the method insensitive to skewness or outliers. Inspect the reference samples as well as the gap curve. A featureless reference is a modelling decision, and its consequences should be visible.

Remark 1 (Why the raw sum of squares cannot choose K). W, in either the pairwise or the unweighted version, is non-increasing in the number of clusters and reaches 0 at k=n, so minimising it over k always selects the largest k. The gap statistic corrects for this by comparing \log W_{\mathrm{data}}^{(k)} with what is expected for data without cluster structure, which also falls as k grows.

Article: Why the raw sum of squares cannot choose →

A plot of the within-cluster sum of squares against k is often called an elbow plot. The elbow is a judgement about where the decrease levels off. The gap curve, with bars of height proportional to the simulation scale s'(k), is the comparison the selection rule actually uses. The two pictures can point at different values of k, because one looks at the raw decrease and the other looks at the decrease relative to a uniform box.

Used in

Taught in K-means clustering
Questions that use it (1) — The within-cluster sum cannot choose K (answer)
All 8 questions on K-means clustering

Used in

See also