MerQuR+Statistics Glossary

Statistics Glossary → Gap statistic

Gap statisticconcept

A criterion in cluster analysis for choosing the number of clusters by comparing within-cluster spread for different numbers of clusters with what would be expected in cluster-free (uniform) reference data.

It was proposed by Tibshirani, Walther and Hastie (2001). For each k the within-cluster sum of squares W_k is computed. Many reference data sets are then generated uniformly over the region covered by the data, and the same clustering is applied to them. Gap(k) = E*[log W_k] − log W_k measures how much 'more clustered' the real data are than cluster-free data. The suggested rule is the smallest k with Gap(k) ≥ Gap(k + 1) − s_{k+1}, where s is the standard error from the reference simulations.

It is more objective than eyeball methods such as the elbow, and it can also consider k = 1 (no clustering). Because the reference data are simulated, however, the result depends on the random seed, and it can mislead when clusters differ greatly in size, are elongated or nested. It should be used together with criteria such as the silhouette coefficient and Calinski-Harabasz, keeping in mind how interpretable the clusters are.

An everyday example

A retailer wants to group customers by spending and visit frequency. For k = 2, 3, 4 and 5 the gap values are 0.41, 0.62, 0.64 and 0.60, with standard errors of about 0.03. For k = 2 the condition fails, since 0.41 < 0.62 − 0.03; for k = 3 it holds, since 0.62 ≥ 0.64 − 0.03 = 0.61, so the rule suggests 3 clusters: a fourth cluster adds no meaningful structure.

In MerQur

In k-means clustering, the 'K selection criterion' option offers the gap statistic: with a uniform null distribution (B = 50), the smallest k with Gap(k) ≥ Gap(k+1) - SE(k+1) is chosen. The silhouette and Calinski-Harabasz criteria are also reported for judging the number and quality of clusters.

Analyses where this concept appears

K-Means Clustering

Related concepts

Choosing the number of clustersSilhouette coefficient