Reading the gap statistic

Topic: K-means clustering · more questions on this topic
‹ A Voronoi boundary The within-cluster sum cannot choose K ›

For k=1,\ldots,5 the gap values are 0.30, 0.70, 1.10, 1.15, 1.00 and s'(k)=0.05, 0.05, 0.06, 0.06, 0.07. Which k^* does the selection rule \operatorname{Gap}(k)\ge\operatorname{Gap}(k+1)-s'(k+1) select?

Worked answer (click to show)

Apply the stopping rule in increasing order of the number of clusters. The selected value need not maximise the numerical gap.

Check \operatorname{Gap}(k)\ge\operatorname{Gap}(k+1)-s'(k+1) in order.

• k=1: 0.30\ge 0.70-0.05=0.65? No.
• k=2: 0.70\ge 1.10-0.06=1.04? No.
• k=3: 1.10\ge 1.15-0.06=1.09? Yes.

So k^*=3, even though the gap is numerically largest at k=4. The increase from 3 to 4 is only 0.05, which is smaller than s'(4)=0.06.