Skip to main content
v2026.11,986 entries · CC-BY 4.0

Gap Statistic: Formula, Worked Example, R and Python

How the gap statistic picks the number of clusters, with the formula, a computed 3-cluster example, selection rules, and R, Python and Excel steps.

Written and maintained by CASRAI Editorial Board

Published

On this page

The gap statistic is a method for choosing the number of clusters, k, in a data set. For each candidate k it compares how tightly the data cluster (the within-cluster dispersion, W(k)) with how tightly data with no cluster structure would cluster, and the k where the data beat that baseline by the most (judged against simulation error) is the estimate. Tibshirani, Walther and Hastie introduced it in 2001, and it works with the output of any clustering algorithm, including k-means and hierarchical clustering. “Gap statistics” in the plural usually means the same quantity computed for every k in a range.

Gap statistic: definition

Every clustering run reports a within-cluster dispersion. As k rises, W(k) always falls, so the lowest W(k) tells you nothing about the right k. The gap statistic corrects for this by asking how much W(k) falls relative to what random data would show. For each k it compares log W(k) from your data with its expected value under a reference distribution, E*[log W(k)], estimated by repeatedly clustering simulated data with no groups in it. The difference is the gap. The R cluster package documentation for clusGap() describes exactly this: the gap for each k compares log W(k) with its bootstrapped expectation, using a reference distribution that is uniform over a hypercube set by the ranges of the data, centred and by default rotated by a singular value decomposition (principal-axes alignment).

The method answers one narrow question, “which k does the data support, given this algorithm?” It does not tell you whether the clusters are meaningful for your research question, and it does not choose the algorithm. For the surrounding workflow see the guides to clustering in R, in Python and in SPSS.

Formula, with every symbol explained

For a given k, the gap is:

Gap(k) = E*[log W(k)] − log W(k)

  • k: the number of clusters being tried (1, 2, 3, … up to a chosen maximum, K.max in R).
  • W(k): the pooled within-cluster dispersion after clustering the data into k groups. With squared Euclidean distances (the choice Tibshirani et al. proposed, d.power = 2 in R) it equals the sum, over clusters, of the squared distances of each point from its own cluster mean. R’s default d.power = 1 uses unsquared Euclidean distances instead, which matches the historical R implementation.
  • log: the natural logarithm. The logarithm makes the comparison relative, not absolute.
  • E*[log W(k)]: the average of log W(k) over B simulated reference data sets that have no cluster structure. B = 100 is the R default, and the documentation notes that B = 500 gives quite precise results.
  • s(k): the simulation error of the gap. In R it is sqrt(1 + 1/B) times the standard deviation of the B simulated log W(k) values (the SE.sim column). The factor sqrt(1 + 1/B) accounts for the reference average itself being estimated from B draws.

Choosing k from the gaps needs a rule. Tibshirani et al.’s rule, named Tibs2001SEmax in R’s maxSE(), takes the smallest k with Gap(k) ≥ Gap(k+1) − s(k+1). R’s default, firstSEmax, takes the smallest k whose gap is within SE.factor (default 1) standard errors of the first local maximum of the gap curve. The documentation calls the two similar but not the same, and notes that the Tibshirani rule selects k = 1 when every standard error exceeds the gap increments between successive k.

Worked example with real numbers

The example uses 15 two-dimensional points in three visibly separate groups of five. Group A: (1.0, 2.0), (1.5, 1.8), (2.0, 2.5), (1.2, 2.6), (1.8, 2.2). Group B: (6.0, 6.5), (6.4, 7.0), (7.0, 6.2), (6.5, 6.8), (7.2, 7.1). Group C: (11.0, 1.0), (11.5, 1.6), (12.0, 0.8), (12.3, 1.5), (11.2, 0.5). I computed everything with the Python script in the code section below: k-means with the best of 10 random starts, squared Euclidean distances (d.power = 2), B = 500 reference data sets drawn uniformly over the bounding box of the data (the “original” option for the reference space, not R’s rotated default), and random seed 42.

Step 1: the observed W(k)

For k = 1 the single cluster mean is (6.573, 3.340) and the sum of squared distances to it is W(1) = 348.625, so log W(1) = 5.854. For k = 3, clustering recovers the three groups. The within-group sums of squares are 1.128 (A, mean (1.50, 2.22)), 1.476 (B, mean (6.62, 6.72)) and 2.048 (C, mean (11.60, 1.08)). Therefore W(3) = 1.128 + 1.476 + 2.048 = 4.652 and log W(3) = 1.537.

Step 2: the gap at k = 3

Over the 500 simulated no-structure data sets, the average log W(3) is E*[log W(3)] = 3.824. The gap is 3.824 − 1.537 = 2.287, and the simulation error is s(3) = 0.240. Your data are far tighter at k = 3 than structureless data of the same extent, which is what a large positive gap means. The full table of W(k), log W(k), E*[log W(k)], gap and s(k) for k = 1 to 6 is in the data table below.

Step 3: apply the selection rules

k Gap(k) Gap(k+1) − s(k+1) Gap(k) ≥ Gap(k+1) − s(k+1)?
1 −0.578 −0.656 Yes
2 −0.447 2.047 No
3 2.287 1.840 Yes
4 2.111 1.670 Yes
5 1.966 1.388 Yes

Two rules give two answers on this data. Tibs2001SEmax (smallest k that passes the test) returns k = 1, because −0.578 is already at least −0.656. firstSEmax finds the first local maximum of the gap curve at k = 3 (Gap(4) = 2.111 is lower), then takes the smallest k whose gap is at least 2.287 − 0.240 = 2.047, which is k = 3. The gap curve itself, with its big jump from −0.447 at k = 2 to 2.287 at k = 3, is unambiguous, so here the plot is a better guide than the single-k test. Always read the whole gap curve and not only the rule’s output.

How to interpret the gap statistic and cluster analysis results

What you see Reading
Gap near zero or negative at every k The data look no more clustered than the reference distribution; the rule can return k = 1.
A sharp rise to a peak, then a decline (as at k = 3 above) Clear evidence for that k under the chosen reference distribution.
Gaps that keep rising to K.max Raise K.max, or consider that structure exists at several scales.
Gap differences smaller than s(k) The curve is within simulation noise; increase B (R documentation suggests 500) before reading anything into it.
Different k from firstSEmax and Tibs2001SEmax Report both and say which you pre-specified.

What is cluster analysis in statistics?

Cluster analysis is a family of methods that group observations so that cases within a group are more alike than cases in different groups, without using pre-labelled outcomes. The gap statistic is not itself a clustering method: it is a diagnostic that picks k for one that needs k as an input.

What is a cluster, with an example?

A cluster is a set of observations that sit closer to each other than to the rest. In the worked example above, the five points near (1.5, 2.2) form one cluster, and the points near (6.6, 6.7) and (11.6, 1.1) form two more. With the data in two dimensions you can see them; the gap statistic is useful when you cannot, because there are many variables.

What are the four types of clustering?

One common way to group clustering methods is hierarchical (building a tree of merges or splits), partitioning or centroid-based (such as k-means), density-based (such as DBSCAN) and model-based (fitting a mixture of distributions). Other groupings exist. The gap statistic fits any method that produces a W(k) for each k, so it suits partitioning and hierarchical output cut at k clusters. See the guides on k-means and hierarchical versus k-means clustering.

How do you interpret cluster analysis results?

Treat the chosen k as a hypothesis. Check that clusters are interpretable on the variables you did not cluster on, that results are stable when you resample or change the algorithm, and that the clusters are not just a product of scale differences between variables. A high gap shows the data are non-random in shape; it does not show that the groups are scientifically meaningful.

Assumptions and common mistakes

  • The result depends on the reference distribution. Uniform over the data’s bounding box and uniform over its principal-axes box (R’s scaledPCA default) can give different curves. State which you used.
  • The result depends on the clustering algorithm and distance. W(k) comes from whatever algorithm you passed in. The gap is only as good as that clustering, so use multiple starts for k-means.
  • Variables on different scales. Distances are dominated by large-scale variables. Standardise before clustering when the units differ.
  • Too few reference data sets. With B = 100 the curve can be noisy; the R documentation says B = 500 is quite precise.
  • Setting K.max too low. The R function needs K.max of at least 2, and a curve that is still rising at K.max has not found its peak.
  • Mixing up d.power. Published formulas based on Tibshirani et al. use squared distances (d.power = 2); R defaults to 1. Results are not interchangeable.
  • Reading one rule as the truth. As the worked example shows, two documented rules can disagree.

How to report the gap statistic (APA-style example)

Say which algorithm, distance, reference distribution, B, K.max and selection rule you used, and give the selected k with the gap values. For example: “The number of clusters was estimated with the gap statistic (Tibshirani et al., 2001) using k-means with 10 random starts, squared Euclidean distances, B = 500 uniform reference data sets drawn over the range of the data, and K.max = 6. The gap peaked at k = 3 (Gap = 2.29, s = 0.24) and the first-local-maximum rule with one standard error selected k = 3.” Reference entry: Tibshirani, R., Walther, G., & Hastie, T. (2001). Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B, 63(2), 411–423. https://doi.org/10.1111/1467-9868.00293

How to calculate it in R, Python or Excel

R

The cluster package’s clusGap() takes the data, a clustering function, K.max and B, and maxSE() applies a selection rule to its table. This follows the documented signatures; for the data above you would pass the 15 × 2 matrix as x.

library(cluster)
gs = clusGap(x, FUNcluster = kmeans, K.max = 6, B = 500,
             d.power = 2, spaceH0 = "original", nstart = 10)
gs$Tab   # columns logW, E.logW, gap, SE.sim
maxSE(gs$Tab[, "gap"], gs$Tab[, "SE.sim"], method = "firstSEmax")
maxSE(gs$Tab[, "gap"], gs$Tab[, "SE.sim"], method = "Tibs2001SEmax")

Results will differ slightly from the Python numbers because the random reference sets differ.

Python

No standard library function is assumed here; this short script (NumPy only) is the one that produced the worked example. It was run as written.

import numpy as np
X = np.array([[1.0, 2.0], [1.5, 1.8], [2.0, 2.5], [1.2, 2.6], [1.8, 2.2],
              [6.0, 6.5], [6.4, 7.0], [7.0, 6.2], [6.5, 6.8], [7.2, 7.1],
              [11.0, 1.0], [11.5, 1.6], [12.0, 0.8], [12.3, 1.5], [11.2, 0.5]])
def kmeans_w(data, k, rng, n_start=10, iters=50):
    best = np.inf
    for _ in range(n_start):
        c = data[rng.choice(len(data), k, replace=False)]
        for _ in range(iters):
            lab = ((data[:, None, :] - c[None]) ** 2).sum(2).argmin(1)
            new = np.array([data[lab == j].mean(0) if np.any(lab == j) else c[j] for j in range(k)])
            if np.allclose(new, c):
                break
            c = new
        lab = ((data[:, None, :] - c[None]) ** 2).sum(2).argmin(1)
        w = sum(((data[lab == j] - data[lab == j].mean(0)) ** 2).sum() for j in range(k) if np.any(lab == j))
        best = min(best, w)
    return best
rng = np.random.default_rng(42)
B, K = 500, 6
lo, hi = X.min(0), X.max(0)
logw = np.array([np.log(kmeans_w(X, k, rng)) for k in range(1, K + 1)])
ref = np.empty((B, K))
for b in range(B):
    Z = rng.uniform(lo, hi, X.shape)
    ref[b] = [np.log(kmeans_w(Z, k, rng, n_start=5)) for k in range(1, K + 1)]
gap = ref.mean(0) - logw
s = np.sqrt(1 + 1 / B) * ref.std(0)
print(np.round(gap, 3), np.round(s, 3))

For production work in Python, the same logic applies to any clustering routine; see the Python guide linked above.

Excel

Excel has no clustering step of its own in this workflow, so assign cluster labels in another tool or by hand, then use spreadsheet formulas for the arithmetic. For each cluster use =DEVSQ(range) (which, per Microsoft’s documentation, returns the sum of squares of deviations of data points from their sample mean) on each coordinate column of that cluster’s rows and add the results to get its sum of squared deviations from the mean; add across clusters for W(k) and take =LN(W). Generate each reference data set with =min+RAND()*(max-min) per variable, cluster it the same way, and put the B values of log W(k) in a column. Then Gap(k) is =AVERAGE(ref_range)-logW and s(k) is =SQRT(1+1/B)*STDEV.P(ref_range). In practice, B = 500 reference sets are impractical by hand, so R or Python is the sensible route.

Frequently asked questions

What is the gap statistic used for?

It estimates the number of clusters in a data set by comparing the clustering tightness of your data with that of reference data that have no clusters.

What does a large gap mean?

The data cluster much more tightly at that k than structureless data of the same extent. A gap near zero means the data look no more clustered than the reference.

What is the difference between gap statistic and gap statistics?

Nothing substantive: the singular names the quantity at one k, and the plural usually means the set of gap values over a range of k.

Which rule should I use to pick k from the gap values?

R’s default is firstSEmax; Tibshirani et al.’s original is Tibs2001SEmax. They can disagree, as the worked example shows, so state the rule you used and look at the full gap curve.

Does it work with hierarchical clustering?

Yes. The original paper states that the method uses the output of any clustering algorithm, with k-means and hierarchical clustering given as examples.

How many reference data sets are needed?

R defaults to B = 100, and its documentation says B = 500 gives quite precise results.

Sources

  • Tibshirani, R., Walther, G., & Hastie, T. (2001). Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B, 63(2), 411–423. DOI 10.1111/1467-9868.00293. Bibliographic record and abstract: RePEc (read 2026-11-19).
  • R cluster package manual, clusGap and maxSE (read 2026-11-19).
  • Microsoft Support, DEVSQ function (read 2026-11-19).
  • NumPy documentation, Generator.uniform, used to draw the uniform reference data (read 2026-11-19).
  • Worked example: computed for this page with the Python script above (NumPy, seed 42, B = 500).

Data: Gap statistic worked example: W(k), log W(k), reference expectation, gap and simulation error for k = 1 to 6

Computed for this page: k-means (best of 10 starts) on 15 two-dimensional points in three groups, squared Euclidean distances, B = 500 uniform reference data sets over the data's bounding box, NumPy seed 42. Gap = E*[log W(k)] - log W(k); s(k) = sqrt(1+1/B) times the standard deviation of the simulated log W(k), following the definitions in the R cluster package documentation.

Period covered: 2026.

Gap statistic worked example: W(k), log W(k), reference expectation, gap and simulation error for k = 1 to 6
Number of clustersW(k)log W(k)E*[log W(k)]Gap(k)s(k)
k = 1348.6255.8545.2759-0.57810.2091
k = 2120.8134.79424.3477-0.44660.209
k = 34.6521.53733.8242.28670.2401
k = 43.4561.243.35082.11080.2705
k = 52.6710.98262.9491.96640.2963
k = 62.4020.87622.58621.710.3223

Sources

Compiled by CASRAI from the sources above. Free to reuse under CC BY 4.0 with attribution.

Follow CASRAI

Research-administration guidance, standards updates and independent tool reviews.

Ask CASRAI · full access

Ask about Gap Statistic: Formula, Worked Example, R and Python

Full access: large monthly usage, up to 10 source passages behind each answer, and MCP and API access for Claude Code, Codex and other CLIs. Cancel any time.

An AI assistant for research: funder rules, compliance, methods and publishing. It links the sources behind its answers and labels answers that come from a web search.

Answers draw on CASRAI's guides and dictionary plus the federal and funder documents we index: Federal Register, Grants.gov, Regulations.gov and UKRI.

Works on this site and inside Claude, Cursor and the AI tools you already use.

Everything CASRAI publishes — this page, the dictionary, the guides and the news — stays open to read, with no account and no card.

Referenced across the research world

University of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logoUniversity of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logo
  • University of Cambridge logo
  • Columbia University logo
  • Crossref logo
  • University of Edinburgh logo
  • Harvard University logo
  • University of Oxford logo
  • Princeton University logo
  • Stanford School of Medicine logo
  • University College London logo
  • ORCID logo

View CASRAI adoption →