Gap Statistic: Comparing… — Clustering Evaluation | OneNoughtOne

0/106

Machine LearningClustering Evaluation

Clustering Evaluation

LevelIntermediate

Duration90 mins

TopicClustering Evaluation

4 / 5

Gap Statistic: Comparing Clusters to Null References

The Quest for a Principled k Selection Method

Selecting the number of clusters k is one of the most challenging problems in unsupervised learning. Internal metrics like Silhouette and Calinski-Harabasz help compare clusterings, but they lack a reference point —a baseline that tells us what score to expect if there's no actual cluster structure in the data. The Gap statistic, introduced by Tibshirani, Walther, and Hastie in 2001, addresses this by comparing the within-cluster dispersion of the data to what we'd expect under a null reference distribution —typically data without any cluster structure. This provides a principled basis for deciding whether clusters are 'real' versus artifacts of the algorithm. This page provides rigorous coverage of the Gap statistic, including its mathematical formulation, different reference distributions, implementation details, and practical guidance for k selection.

What You Will Learn

By the end of this page, you will understand: (1) the intuition and mathematical derivation of the Gap statistic, (2) how to generate appropriate null reference distributions, (3) the Gap selection rule and its variants, (4) computational implementation, and (5) limitations and best practices.

The Core Intuition

The Within-Cluster Dispersion Curve When we cluster data into k groups, we can measure the within-cluster dispersion Wₖ—how spread out points are within their assigned clusters. For k-means specifically: $$W_k = \sum_{r=1}^{k} \frac{1}{2n_r} D_r$$ where nᵣ is the number of points in cluster r, and Dᵣ is the sum of pairwise distances within cluster r. As k increases, Wₖ decreases monotonically—more clusters means each cluster is smaller and tighter. The question is: at what point does adding more clusters stop being meaningful?

The Reference Distribution Idea The key insight of the Gap statistic is to compare the observed Wₖ curve to what we'd see for data with no cluster structure. If the data has k genuine clusters: The observed Wₖ will drop sharply when we go from k-1 to k clusters For null data (uniform, no clusters), Wₖ drops gradually with k The Gap is the difference between these curves: $$\text{Gap}(k) = E^*[\log W_k] - \log W_k$$ where E* denotes expectation under the null reference distribution.

Why Log Transform?

We use log(Wₖ) rather than Wₖ because the dispersion values span many orders of magnitude. The log transform makes the comparison more stable and the resulting Gap values more interpretable. It also makes the Gap roughly proportional to the 'information gain' from clustering.

Visual Intuition Imagine plotting log(Wₖ) vs. k: Observed data : Curve drops sharply at the true k, then flattens Null reference : Curve drops smoothly, no sharp transitions The Gap at k is the vertical distance between these curves. A large Gap indicates that the clustering at k captures structure not explainable by chance—the true clusters are revealed.

Mathematical Formulation

Formal Definition Let X be the data matrix with n observations in d dimensions. For a given k: Step 1: Cluster the data into k clusters C₁, ..., Cₖ Step 2: Compute within-cluster dispersion: $$W_k = \sum_{r=1}^{k} \frac{1}{2n_r} \sum_{i, j \in C_r} d(x_i, x_j)^2$$ For k-means with squared Euclidean distance, this simplifies to: $$W_k = \sum_{r=1}^{k} \sum_{i \in C_r} |x_i - \bar{x}_r|^2$$ where x̄ᵣ is the centroid of cluster r.

Step 3: Generate B reference datasets from the null distribution (typically B = 20-100) Step 4: For each reference dataset b = 1, ..., B: Cluster into k clusters Compute W*ₖᵦ Step 5: Compute the Gap statistic: $$\text{Gap}(k) = \frac{1}{B} \sum_{b=1}^{B} \log W_{k,b}^* - \log W_k$$ Step 6: Compute the standard error: $$s_k = \sqrt{\frac{1}{B} \sum_{b=1}^{B} (\log W_{k,b}^* - \overline{\log W_k^*})^2} \cdot \sqrt{1 + \frac{1}{B}}$$ where the factor √(1 + 1/B) accounts for the simulation error.

The Gap Selection Rule The optimal k is chosen as the smallest k such that: $$\text{Gap}(k) \geq \text{Gap}(k+1) - s_{k+1}$$ Interpretation: Choose k when increasing to k+1 doesn't provide a statistically significant improvement in the Gap. This is a conservative rule that prefers simpler models. Alternative rule (first local maximum): $$k^* = \arg\max_k \text{Gap}(k)$$ This simpler rule can work but may overfit to noise.

Choosing the Reference Distribution

The null reference distribution is crucial—it defines what 'no cluster structure' means. Two main approaches exist: 1. Uniform over Bounding Box Generate points uniformly in the d-dimensional bounding box of the data: $$x_j^* \sim \text{Uniform}(\min(x_j), \max(x_j))$$ for each dimension j independently. Pros: Simple, no parametric assumptions Cons: Can give misleading results if data has non-rectangular shape or correlations

2. Uniform over PCA-Rotated Box Project data onto its principal components, generate uniform samples in that space, then rotate back: Compute PCA: X = UΣVᵀ Transform: X' = XV (rotate to principal axes) Generate uniform samples in bounding box of X' Rotate back: X* = X'*Vᵀ Pros : Respects the shape of the data cloud, including elongations and correlations Cons : More complex, still assumes 'no structure' means uniform This is the recommended approach from the original paper.

reference_distributions.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import numpy as np
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
 
def uniform_bounding_box(X, n_samples=None):
    """
    Generate uniform samples in the bounding box of X.
    """
    if n_samples is None:
        n_samples = X.shape[0]
    
    mins = X.min(axis=0)
    maxs = X.max(axis=0)
    
    # Uniform samples in each dimension independently
    samples = np.random.uniform(mins, maxs, size=(n_samples, X.shape[1]))
    return samples
 
 
def uniform_pca_box(X, n_samples=None):
    """
    Generate uniform samples in PCA-rotated bounding box.
    
    This respects the orientation and shape of the data cloud.
    """
    if n_samples is None:
        n_samples = X.shape[0]
    
    # Center the data
    X_centered = X - X.mean(axis=0)
    
    # PCA transformation
    pca = PCA(n_components=X.shape[1])
    X_pca = pca.fit_transform(X_centered)
    
    # Generate uniform in PCA space bounding box
    mins = X_pca.min(axis=0)
    maxs = X_pca.max(axis=0)
    samples_pca = np.random.uniform(mins, maxs, size=(n_samples, X.shape[1]))
    
    # Transform back to original space
    samples = pca.inverse_transform(samples_pca) + X.mean(axis=0)
    return samples
 
 
# Demonstrate the difference
from sklearn.datasets import make_blobs
 
# Create elongated, correlated data
np.random.seed(42)
n_points = 300
 
# Generate data with specific correlation structure
cov = [[2, 1.5], [1.5, 1.5]]
X = np.random.multivariate_normal([0, 0], cov, n_points)
 
# Add some cluster structure
X[:100] += [3, 2]
X[100:200] += [-2, -1]
 
# Generate reference samples
ref_box = uniform_bounding_box(X)
ref_pca = uniform_pca_box(X)
 
# Visualize
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
 
axes[0].scatter(X[:, 0], X[:, 1], alpha=0.5, s=20, label='Original Data')
axes[0].set_title('Original Data with Clusters')
axes[0].set_xlim(X[:, 0].min()-1, X[:, 0].max()+1)
axes[0].set_ylim(X[:, 1].min()-1, X[:, 1].max()+1)
axes[0].set_aspect('equal')
 
axes[1].scatter(ref_box[:, 0], ref_box[:, 1], alpha=0.5, s=20, c='orange')
axes[1].set_title('Uniform Bounding Box')
axes[1].set_xlim(X[:, 0].min()-1, X[:, 0].max()+1)
axes[1].set_ylim(X[:, 1].min()-1, X[:, 1].max()+1)
axes[1].set_aspect('equal')
 
axes[2].scatter(ref_pca[:, 0], ref_pca[:, 1], alpha=0.5, s=20, c='green')
axes[2].set_title('Uniform PCA Box (Recommended)')
axes[2].set_xlim(X[:, 0].min()-1, X[:, 0].max()+1)
axes[2].set_ylim(X[:, 1].min()-1, X[:, 1].max()+1)
axes[2].set_aspect('equal')
 
plt.tight_layout()
plt.show()
 
print("
Note: The PCA-based reference better captures the data's elliptical shape.")
print("Using bounding box on elongated data may add spurious structure to references.")

Choice Matters for High-Dimensional Data

In high dimensions, the bounding box becomes very large compared to the data cloud (curse of dimensionality). PCA-based sampling is strongly preferred in d > 3 dimensions. Some practitioners recommend dimensionality reduction before computing Gap.

Complete Implementation

Here is a complete, production-ready implementation of the Gap statistic with all the details from the original paper:

gap_statistic.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
import numpy as np
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
 
class GapStatistic:
    """
    Gap Statistic for determining optimal number of clusters.
    
    Implementation follows Tibshirani, Walther & Hastie (2001):
    "Estimating the number of clusters in a data set via the gap statistic"
    
    Parameters:
    -----------
    n_refs : int
        Number of reference datasets to generate (default 20)
    cluster_func : callable
        Clustering function, defaults to KMeans
    use_pca_reference : bool
        If True, use PCA-based reference distribution (recommended)
    random_state : int
        Random seed for reproducibility
    """
    
    def __init__(self, n_refs=20, cluster_func=None, use_pca_reference=True, 
                 random_state=42):
        self.n_refs = n_refs
        self.use_pca_reference = use_pca_reference
        self.random_state = random_state
        
        if cluster_func is None:
            self.cluster_func = lambda X, k: KMeans(
                n_clusters=k, n_init='auto', random_state=random_state
            ).fit(X)
        else:
            self.cluster_func = cluster_func
    
    def _compute_wk(self, X, labels):
        """
        Compute within-cluster dispersion Wk.
        
        For k-means, this is the sum of squared distances to centroids.
        """
        unique_labels = np.unique(labels)
        wk = 0
        
        for label in unique_labels:
            cluster_points = X[labels == label]
            if len(cluster_points) > 0:
                centroid = cluster_points.mean(axis=0)
                wk += np.sum((cluster_points - centroid) ** 2)
        
        return wk
    
    def _generate_reference(self, X):
        """
        Generate reference data from null distribution.
        """
        n_samples, n_features = X.shape
        rng = np.random.RandomState(self.random_state + np.random.randint(10000))
        
        if self.use_pca_reference:
            # PCA-based reference
            X_centered = X - X.mean(axis=0)
            pca = PCA(n_components=min(n_features, n_samples))
            X_pca = pca.fit_transform(X_centered)
            
            mins = X_pca.min(axis=0)
            maxs = X_pca.max(axis=0)
            
            ref_pca = rng.uniform(mins, maxs, size=(n_samples, X_pca.shape[1]))
            ref = pca.inverse_transform(ref_pca) + X.mean(axis=0)
        else:
            # Simple bounding box
            mins = X.min(axis=0)
            maxs = X.max(axis=0)
            ref = rng.uniform(mins, maxs, size=(n_samples, n_features))
        
        return ref
    
    def compute_gap(self, X, k_range):
        """
        Compute Gap statistic for a range of k values.
        
        Parameters:
        -----------
        X : ndarray of shape (n_samples, n_features)
        k_range : iterable
            Range of k values to evaluate
        
        Returns:
        --------
        dict with Gap values, standard errors, and recommendation
        """
        k_range = list(k_range)
        n_k = len(k_range)
        
        # Store results
        log_wk = np.zeros(n_k)
        log_wk_ref = np.zeros((n_k, self.n_refs))
        gaps = np.zeros(n_k)
        std_errors = np.zeros(n_k)
        
        # Compute log(Wk) for original data
        print("Computing Gap statistic...")
        for i, k in enumerate(k_range):
            model = self.cluster_func(X, k)
            labels = model.labels_ if hasattr(model, 'labels_') else model.predict(X)
            wk = self._compute_wk(X, labels)
            log_wk[i] = np.log(wk)
            
            # Compute for reference datasets
            for b in range(self.n_refs):
                np.random.seed(self.random_state + b)
                X_ref = self._generate_reference(X)
                model_ref = self.cluster_func(X_ref, k)
                labels_ref = model_ref.labels_ if hasattr(model_ref, 'labels_') else model_ref.predict(X_ref)
                wk_ref = self._compute_wk(X_ref, labels_ref)
                log_wk_ref[i, b] = np.log(wk_ref)
            
            # Gap = E*[log(Wk)] - log(Wk)
            gaps[i] = np.mean(log_wk_ref[i]) - log_wk[i]
            
            # Standard error with simulation correction
            sdk = np.std(log_wk_ref[i])
            std_errors[i] = sdk * np.sqrt(1 + 1/self.n_refs)
            
            print(f"  k={k}: Gap={gaps[i]:.4f} ± {std_errors[i]:.4f}")
        
        # Find optimal k using the standard rule
        optimal_k = k_range[0]
        for i in range(n_k - 1):
            if gaps[i] >= gaps[i+1] - std_errors[i+1]:
                optimal_k = k_range[i]
                break
        
        return {
            'k_range': k_range,
            'gaps': gaps,
            'std_errors': std_errors,
            'log_wk': log_wk,
            'log_wk_ref_mean': np.mean(log_wk_ref, axis=1),
            'optimal_k': optimal_k
        }
    
    def plot_results(self, results, true_k=None):
        """
        Visualize Gap statistic results.
        """
        k_range = results['k_range']
        gaps = results['gaps']
        std_errors = results['std_errors']
        optimal_k = results['optimal_k']
        
        fig, axes = plt.subplots(1, 2, figsize=(14, 5))
        
        # Gap statistic plot
        axes[0].errorbar(k_range, gaps, yerr=std_errors, marker='o', 
                         capsize=5, linewidth=2, markersize=8)
        axes[0].axvline(x=optimal_k, color='red', linestyle='--', 
                        label=f'Optimal k={optimal_k}')
        if true_k:
            axes[0].axvline(x=true_k, color='green', linestyle=':', 
                           label=f'True k={true_k}', linewidth=2)
        axes[0].set_xlabel('Number of Clusters (k)', fontsize=12)
        axes[0].set_ylabel('Gap(k)', fontsize=12)
        axes[0].set_title('Gap Statistic', fontsize=14)
        axes[0].legend()
        axes[0].grid(True, alpha=0.3)
        
        # Log(Wk) comparison plot
        axes[1].plot(k_range, results['log_wk'], 'bo-', 
                     label='Original Data', linewidth=2, markersize=8)
        axes[1].plot(k_range, results['log_wk_ref_mean'], 'rs--', 
                     label='Reference Mean', linewidth=2, markersize=8)
        axes[1].fill_between(k_range, 
                             results['log_wk_ref_mean'] - std_errors,
                             results['log_wk_ref_mean'] + std_errors,
                             alpha=0.2, color='red')
        axes[1].set_xlabel('Number of Clusters (k)', fontsize=12)
        axes[1].set_ylabel('log(Wk)', fontsize=12)
        axes[1].set_title('Within-Cluster Dispersion: Data vs Reference', fontsize=14)
        axes[1].legend()
        axes[1].grid(True, alpha=0.3)
        
        plt.tight_layout()
        plt.show()
        
        return fig
 
 
# Example usage
from sklearn.datasets import make_blobs
 
# Generate data with known structure
np.random.seed(42)
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=1.0, random_state=42)
 
# Compute Gap statistic
gap = GapStatistic(n_refs=20, use_pca_reference=True, random_state=42)
results = gap.compute_gap(X, k_range=range(1, 10))
 
print(f"
Optimal k by Gap statistic: {results['optimal_k']}")
print(f"True k: 4")
 
# Visualize
gap.plot_results(results, true_k=4)

Understanding the Selection Rule

The Gap selection rule deserves careful explanation: $$\text{Choose smallest } k \text{ such that } \text{Gap}(k) \geq \text{Gap}(k+1) - s_{k+1}$$ Why This Rule? The intuition is statistical: we want to know if increasing k significantly improves the Gap. The standard error sₖ₊₁ provides a measure of uncertainty. If Gap(k) is within one standard error of Gap(k+1), we cannot confidently say that k+1 is better, so we prefer the simpler model k. Equivalently Written As: $$\text{Gap}(k) + s_{k+1} \geq \text{Gap}(k+1)$$ This says: stop when adding the uncertainty band to Gap(k) overlaps with Gap(k+1).

Example: Applying the Selection Rule
k	Gap(k)	s_k	Gap(k) ≥ Gap(k+1) - s_{k+1}?	Decision
1	1.20	0.15	1.20 ≥ 2.50 - 0.18 = 2.32? No	Continue
2	2.50	0.18	2.50 ≥ 3.80 - 0.22 = 3.58? No	Continue
3	3.80	0.22	3.80 ≥ 4.10 - 0.25 = 3.85? No	Continue
4	4.10	0.25	4.10 ≥ 3.95 - 0.28 = 3.67? Yes	Stop: k=4
5	3.95	0.28	(not evaluated)

Alternative Selection Rules 1. Maximum Gap : k* = argmax Gap(k) Simpler but may overfit Works well when the maximum is clear 2. First significant increase stops : Similar to elbow method but with Gap 3. One-standard-error rule from k *: Choose smallest k within one SE of max Gap More conservative Inspired by cross-validation selection in supervised learning 4. Two-standard-error rule : Even more conservative Gap(k) \geq Gap(k+1) - 2\cdotsₖ₊₁ Use when false positives (over-clustering) are costly

Practical Recommendation

Plot the Gap curve with error bars and visually inspect. If there's a clear elbow or maximum, trust it. If the curve is flat or noisy, consider that the data may not have clear cluster structure—or try a larger reference sample (increase n_refs).

Gap Statistic Variants

Several variants and extensions of the Gap statistic have been proposed: Weighted Gap For datasets with varying cluster sizes, weight the dispersion calculation: $$W_k^{weighted} = \sum_{r=1}^{k} n_r \cdot \text{AvgDisp}(C_r)$$ This gives more importance to larger clusters. Modified Gap (Yan & Ye, 2007) Uses a modified selection criterion that is less sensitive to the number of reference samples: $$k^* = \min{k : \text{Gap}(k) \geq \max_{j \leq k_{max}} \text{Gap}(j) - s_j}$$ Tibs2001SEmax Another variant that looks for the first k where Gap exceeds the maximum Gap minus its standard error: $$k^* = \min{k : \text{Gap}(k) \geq \text{Gap}(k_{max}) - s_{k_{max}}}$$

gap_variants.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import numpy as np
 
def gap_selection_variants(gaps, std_errors, k_range):
    """
    Compare different Gap selection rules.
    
    Parameters:
    -----------
    gaps : array-like
        Gap values for each k
    std_errors : array-like
        Standard errors for each k
    k_range : list
        Values of k tested
    
    Returns:
    --------
    dict with recommendations from different rules
    """
    k_range = list(k_range)
    n_k = len(k_range)
    
    results = {}
    
    # 1. Standard Tibshirani rule
    optimal_standard = k_range[0]
    for i in range(n_k - 1):
        if gaps[i] >= gaps[i+1] - std_errors[i+1]:
            optimal_standard = k_range[i]
            break
    else:
        optimal_standard = k_range[-1]
    results['standard'] = optimal_standard
    
    # 2. Maximum Gap
    results['maximum'] = k_range[np.argmax(gaps)]
    
    # 3. One-SE rule from maximum
    max_gap_idx = np.argmax(gaps)
    max_gap = gaps[max_gap_idx]
    max_gap_se = std_errors[max_gap_idx]
    threshold = max_gap - max_gap_se
    
    for i, gap in enumerate(gaps):
        if gap >= threshold:
            results['one_se_from_max'] = k_range[i]
            break
    
    # 4. First significant jump
    # Look for first k where gap increases significantly from k-1
    results['first_jump'] = k_range[0]
    for i in range(1, n_k):
        if gaps[i] > gaps[i-1] + std_errors[i]:
            results['first_jump'] = k_range[i]
            break
    
    # 5. Two-SE rule (more conservative)
    optimal_2se = k_range[0]
    for i in range(n_k - 1):
        if gaps[i] >= gaps[i+1] - 2 * std_errors[i+1]:
            optimal_2se = k_range[i]
            break
    else:
        optimal_2se = k_range[-1]
    results['two_se'] = optimal_2se
    
    return results
 
 
# Example with synthetic data
np.random.seed(42)
k_range = list(range(1, 10))
 
# Simulate Gap values that peak at k=4
gaps = np.array([1.0, 2.2, 3.5, 4.2, 4.0, 3.8, 3.6, 3.5, 3.4])
std_errors = np.array([0.15, 0.18, 0.20, 0.22, 0.23, 0.24, 0.25, 0.26, 0.27])
 
results = gap_selection_variants(gaps, std_errors, k_range)
 
print("Gap Selection Rule Comparison")
print("="*50)
print(f"
Gap values: {gaps}")
print(f"Standard errors: {std_errors}")
print()
for rule, k in results.items():
    print(f"  {rule:20s}: k = {k}")
print()
print("Note: Different rules balance sensitivity vs. specificity")
print("      More conservative rules (two_se) prefer fewer clusters")

Practical Considerations

Computational Cost Gap statistic is computationally expensive: For each k: 1 clustering on original data + B clusterings on reference data Total: (k_max) \times (B + 1) clustering runs For k_max = 10 and B = 20: 210 clustering runs Strategies to reduce cost: Use smaller B (20 is often sufficient for modest n) Limit k_max based on domain knowledge Use faster clustering algorithms (mini-batch k-means) Parallelize reference computations

Recommended Settings
Dataset Size	n_refs (B)	k_max	Notes
< 1,000	50-100	10-15	Can afford more references
1,000 - 10,000	20-50	10	Standard settings
10,000	10-20	< 10	Consider sampling
100,000	10	Based on domain	Use mini-batch k-means

When Gap Statistic Works Well ✓ Data has well-separated, roughly spherical clusters ✓ Cluster sizes are relatively balanced ✓ True k is within the tested range ✓ Sufficient samples per expected cluster When Gap Statistic May Fail ✗ Non-convex clusters (moons, rings) ✗ Highly imbalanced cluster sizes ✗ Very high-dimensional data (curse of dimensionality affects references) ✗ Overlapping clusters with ambiguous boundaries ✗ Hierarchical or nested cluster structure

Gap May Suggest k=1

If your data truly has no cluster structure (or structure not capturable by k-means), Gap will correctly suggest k=1. This is a feature, not a bug—but verify by examining the data and trying other algorithms. A result of k=1 may also indicate that preprocessing (normalization, dimensionality reduction) is needed.

Machine LearningClustering Evaluation

Clustering Evaluation

LevelIntermediate

Duration90 mins

TopicClustering Evaluation

4 / 5

Gap Statistic: Comparing Clusters to Null References

The Quest for a Principled k Selection Method

Selecting the number of clusters k is one of the most challenging problems in unsupervised learning. Internal metrics like Silhouette and Calinski-Harabasz help compare clusterings, but they lack a reference point —a baseline that tells us what score to expect if there's no actual cluster structure in the data. The Gap statistic, introduced by Tibshirani, Walther, and Hastie in 2001, addresses this by comparing the within-cluster dispersion of the data to what we'd expect under a null reference distribution —typically data without any cluster structure. This provides a principled basis for deciding whether clusters are 'real' versus artifacts of the algorithm. This page provides rigorous coverage of the Gap statistic, including its mathematical formulation, different reference distributions, implementation details, and practical guidance for k selection.

What You Will Learn

By the end of this page, you will understand: (1) the intuition and mathematical derivation of the Gap statistic, (2) how to generate appropriate null reference distributions, (3) the Gap selection rule and its variants, (4) computational implementation, and (5) limitations and best practices.

The Core Intuition

The Within-Cluster Dispersion Curve When we cluster data into k groups, we can measure the within-cluster dispersion Wₖ—how spread out points are within their assigned clusters. For k-means specifically: $$W_k = \sum_{r=1}^{k} \frac{1}{2n_r} D_r$$ where nᵣ is the number of points in cluster r, and Dᵣ is the sum of pairwise distances within cluster r. As k increases, Wₖ decreases monotonically—more clusters means each cluster is smaller and tighter. The question is: at what point does adding more clusters stop being meaningful?

The Reference Distribution Idea The key insight of the Gap statistic is to compare the observed Wₖ curve to what we'd see for data with no cluster structure. If the data has k genuine clusters: The observed Wₖ will drop sharply when we go from k-1 to k clusters For null data (uniform, no clusters), Wₖ drops gradually with k The Gap is the difference between these curves: $$\text{Gap}(k) = E^*[\log W_k] - \log W_k$$ where E* denotes expectation under the null reference distribution.

Why Log Transform?

We use log(Wₖ) rather than Wₖ because the dispersion values span many orders of magnitude. The log transform makes the comparison more stable and the resulting Gap values more interpretable. It also makes the Gap roughly proportional to the 'information gain' from clustering.

Visual Intuition Imagine plotting log(Wₖ) vs. k: Observed data : Curve drops sharply at the true k, then flattens Null reference : Curve drops smoothly, no sharp transitions The Gap at k is the vertical distance between these curves. A large Gap indicates that the clustering at k captures structure not explainable by chance—the true clusters are revealed.

Mathematical Formulation

Formal Definition Let X be the data matrix with n observations in d dimensions. For a given k: Step 1: Cluster the data into k clusters C₁, ..., Cₖ Step 2: Compute within-cluster dispersion: $$W_k = \sum_{r=1}^{k} \frac{1}{2n_r} \sum_{i, j \in C_r} d(x_i, x_j)^2$$ For k-means with squared Euclidean distance, this simplifies to: $$W_k = \sum_{r=1}^{k} \sum_{i \in C_r} |x_i - \bar{x}_r|^2$$ where x̄ᵣ is the centroid of cluster r.

Step 3: Generate B reference datasets from the null distribution (typically B = 20-100) Step 4: For each reference dataset b = 1, ..., B: Cluster into k clusters Compute W*ₖᵦ Step 5: Compute the Gap statistic: $$\text{Gap}(k) = \frac{1}{B} \sum_{b=1}^{B} \log W_{k,b}^* - \log W_k$$ Step 6: Compute the standard error: $$s_k = \sqrt{\frac{1}{B} \sum_{b=1}^{B} (\log W_{k,b}^* - \overline{\log W_k^*})^2} \cdot \sqrt{1 + \frac{1}{B}}$$ where the factor √(1 + 1/B) accounts for the simulation error.

The Gap Selection Rule The optimal k is chosen as the smallest k such that: $$\text{Gap}(k) \geq \text{Gap}(k+1) - s_{k+1}$$ Interpretation: Choose k when increasing to k+1 doesn't provide a statistically significant improvement in the Gap. This is a conservative rule that prefers simpler models. Alternative rule (first local maximum): $$k^* = \arg\max_k \text{Gap}(k)$$ This simpler rule can work but may overfit to noise.

Choosing the Reference Distribution

The null reference distribution is crucial—it defines what 'no cluster structure' means. Two main approaches exist: 1. Uniform over Bounding Box Generate points uniformly in the d-dimensional bounding box of the data: $$x_j^* \sim \text{Uniform}(\min(x_j), \max(x_j))$$ for each dimension j independently. Pros: Simple, no parametric assumptions Cons: Can give misleading results if data has non-rectangular shape or correlations

2. Uniform over PCA-Rotated Box Project data onto its principal components, generate uniform samples in that space, then rotate back: Compute PCA: X = UΣVᵀ Transform: X' = XV (rotate to principal axes) Generate uniform samples in bounding box of X' Rotate back: X* = X'*Vᵀ Pros : Respects the shape of the data cloud, including elongations and correlations Cons : More complex, still assumes 'no structure' means uniform This is the recommended approach from the original paper.

reference_distributions.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import numpy as np
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
 
def uniform_bounding_box(X, n_samples=None):
    """
    Generate uniform samples in the bounding box of X.
    """
    if n_samples is None:
        n_samples = X.shape[0]
    
    mins = X.min(axis=0)
    maxs = X.max(axis=0)
    
    # Uniform samples in each dimension independently
    samples = np.random.uniform(mins, maxs, size=(n_samples, X.shape[1]))
    return samples
 
 
def uniform_pca_box(X, n_samples=None):
    """
    Generate uniform samples in PCA-rotated bounding box.
    
    This respects the orientation and shape of the data cloud.
    """
    if n_samples is None:
        n_samples = X.shape[0]
    
    # Center the data
    X_centered = X - X.mean(axis=0)
    
    # PCA transformation
    pca = PCA(n_components=X.shape[1])
    X_pca = pca.fit_transform(X_centered)
    
    # Generate uniform in PCA space bounding box
    mins = X_pca.min(axis=0)
    maxs = X_pca.max(axis=0)
    samples_pca = np.random.uniform(mins, maxs, size=(n_samples, X.shape[1]))
    
    # Transform back to original space
    samples = pca.inverse_transform(samples_pca) + X.mean(axis=0)
    return samples
 
 
# Demonstrate the difference
from sklearn.datasets import make_blobs
 
# Create elongated, correlated data
np.random.seed(42)
n_points = 300
 
# Generate data with specific correlation structure
cov = [[2, 1.5], [1.5, 1.5]]
X = np.random.multivariate_normal([0, 0], cov, n_points)
 
# Add some cluster structure
X[:100] += [3, 2]
X[100:200] += [-2, -1]
 
# Generate reference samples
ref_box = uniform_bounding_box(X)
ref_pca = uniform_pca_box(X)
 
# Visualize
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
 
axes[0].scatter(X[:, 0], X[:, 1], alpha=0.5, s=20, label='Original Data')
axes[0].set_title('Original Data with Clusters')
axes[0].set_xlim(X[:, 0].min()-1, X[:, 0].max()+1)
axes[0].set_ylim(X[:, 1].min()-1, X[:, 1].max()+1)
axes[0].set_aspect('equal')
 
axes[1].scatter(ref_box[:, 0], ref_box[:, 1], alpha=0.5, s=20, c='orange')
axes[1].set_title('Uniform Bounding Box')
axes[1].set_xlim(X[:, 0].min()-1, X[:, 0].max()+1)
axes[1].set_ylim(X[:, 1].min()-1, X[:, 1].max()+1)
axes[1].set_aspect('equal')
 
axes[2].scatter(ref_pca[:, 0], ref_pca[:, 1], alpha=0.5, s=20, c='green')
axes[2].set_title('Uniform PCA Box (Recommended)')
axes[2].set_xlim(X[:, 0].min()-1, X[:, 0].max()+1)
axes[2].set_ylim(X[:, 1].min()-1, X[:, 1].max()+1)
axes[2].set_aspect('equal')
 
plt.tight_layout()
plt.show()
 
print("
Note: The PCA-based reference better captures the data's elliptical shape.")
print("Using bounding box on elongated data may add spurious structure to references.")

Choice Matters for High-Dimensional Data

In high dimensions, the bounding box becomes very large compared to the data cloud (curse of dimensionality). PCA-based sampling is strongly preferred in d > 3 dimensions. Some practitioners recommend dimensionality reduction before computing Gap.

Complete Implementation

Here is a complete, production-ready implementation of the Gap statistic with all the details from the original paper:

gap_statistic.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
import numpy as np
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
 
class GapStatistic:
    """
    Gap Statistic for determining optimal number of clusters.
    
    Implementation follows Tibshirani, Walther & Hastie (2001):
    "Estimating the number of clusters in a data set via the gap statistic"
    
    Parameters:
    -----------
    n_refs : int
        Number of reference datasets to generate (default 20)
    cluster_func : callable
        Clustering function, defaults to KMeans
    use_pca_reference : bool
        If True, use PCA-based reference distribution (recommended)
    random_state : int
        Random seed for reproducibility
    """
    
    def __init__(self, n_refs=20, cluster_func=None, use_pca_reference=True, 
                 random_state=42):
        self.n_refs = n_refs
        self.use_pca_reference = use_pca_reference
        self.random_state = random_state
        
        if cluster_func is None:
            self.cluster_func = lambda X, k: KMeans(
                n_clusters=k, n_init='auto', random_state=random_state
            ).fit(X)
        else:
            self.cluster_func = cluster_func
    
    def _compute_wk(self, X, labels):
        """
        Compute within-cluster dispersion Wk.
        
        For k-means, this is the sum of squared distances to centroids.
        """
        unique_labels = np.unique(labels)
        wk = 0
        
        for label in unique_labels:
            cluster_points = X[labels == label]
            if len(cluster_points) > 0:
                centroid = cluster_points.mean(axis=0)
                wk += np.sum((cluster_points - centroid) ** 2)
        
        return wk
    
    def _generate_reference(self, X):
        """
        Generate reference data from null distribution.
        """
        n_samples, n_features = X.shape
        rng = np.random.RandomState(self.random_state + np.random.randint(10000))
        
        if self.use_pca_reference:
            # PCA-based reference
            X_centered = X - X.mean(axis=0)
            pca = PCA(n_components=min(n_features, n_samples))
            X_pca = pca.fit_transform(X_centered)
            
            mins = X_pca.min(axis=0)
            maxs = X_pca.max(axis=0)
            
            ref_pca = rng.uniform(mins, maxs, size=(n_samples, X_pca.shape[1]))
            ref = pca.inverse_transform(ref_pca) + X.mean(axis=0)
        else:
            # Simple bounding box
            mins = X.min(axis=0)
            maxs = X.max(axis=0)
            ref = rng.uniform(mins, maxs, size=(n_samples, n_features))
        
        return ref
    
    def compute_gap(self, X, k_range):
        """
        Compute Gap statistic for a range of k values.
        
        Parameters:
        -----------
        X : ndarray of shape (n_samples, n_features)
        k_range : iterable
            Range of k values to evaluate
        
        Returns:
        --------
        dict with Gap values, standard errors, and recommendation
        """
        k_range = list(k_range)
        n_k = len(k_range)
        
        # Store results
        log_wk = np.zeros(n_k)
        log_wk_ref = np.zeros((n_k, self.n_refs))
        gaps = np.zeros(n_k)
        std_errors = np.zeros(n_k)
        
        # Compute log(Wk) for original data
        print("Computing Gap statistic...")
        for i, k in enumerate(k_range):
            model = self.cluster_func(X, k)
            labels = model.labels_ if hasattr(model, 'labels_') else model.predict(X)
            wk = self._compute_wk(X, labels)
            log_wk[i] = np.log(wk)
            
            # Compute for reference datasets
            for b in range(self.n_refs):
                np.random.seed(self.random_state + b)
                X_ref = self._generate_reference(X)
                model_ref = self.cluster_func(X_ref, k)
                labels_ref = model_ref.labels_ if hasattr(model_ref, 'labels_') else model_ref.predict(X_ref)
                wk_ref = self._compute_wk(X_ref, labels_ref)
                log_wk_ref[i, b] = np.log(wk_ref)
            
            # Gap = E*[log(Wk)] - log(Wk)
            gaps[i] = np.mean(log_wk_ref[i]) - log_wk[i]
            
            # Standard error with simulation correction
            sdk = np.std(log_wk_ref[i])
            std_errors[i] = sdk * np.sqrt(1 + 1/self.n_refs)
            
            print(f"  k={k}: Gap={gaps[i]:.4f} ± {std_errors[i]:.4f}")
        
        # Find optimal k using the standard rule
        optimal_k = k_range[0]
        for i in range(n_k - 1):
            if gaps[i] >= gaps[i+1] - std_errors[i+1]:
                optimal_k = k_range[i]
                break
        
        return {
            'k_range': k_range,
            'gaps': gaps,
            'std_errors': std_errors,
            'log_wk': log_wk,
            'log_wk_ref_mean': np.mean(log_wk_ref, axis=1),
            'optimal_k': optimal_k
        }
    
    def plot_results(self, results, true_k=None):
        """
        Visualize Gap statistic results.
        """
        k_range = results['k_range']
        gaps = results['gaps']
        std_errors = results['std_errors']
        optimal_k = results['optimal_k']
        
        fig, axes = plt.subplots(1, 2, figsize=(14, 5))
        
        # Gap statistic plot
        axes[0].errorbar(k_range, gaps, yerr=std_errors, marker='o', 
                         capsize=5, linewidth=2, markersize=8)
        axes[0].axvline(x=optimal_k, color='red', linestyle='--', 
                        label=f'Optimal k={optimal_k}')
        if true_k:
            axes[0].axvline(x=true_k, color='green', linestyle=':', 
                           label=f'True k={true_k}', linewidth=2)
        axes[0].set_xlabel('Number of Clusters (k)', fontsize=12)
        axes[0].set_ylabel('Gap(k)', fontsize=12)
        axes[0].set_title('Gap Statistic', fontsize=14)
        axes[0].legend()
        axes[0].grid(True, alpha=0.3)
        
        # Log(Wk) comparison plot
        axes[1].plot(k_range, results['log_wk'], 'bo-', 
                     label='Original Data', linewidth=2, markersize=8)
        axes[1].plot(k_range, results['log_wk_ref_mean'], 'rs--', 
                     label='Reference Mean', linewidth=2, markersize=8)
        axes[1].fill_between(k_range, 
                             results['log_wk_ref_mean'] - std_errors,
                             results['log_wk_ref_mean'] + std_errors,
                             alpha=0.2, color='red')
        axes[1].set_xlabel('Number of Clusters (k)', fontsize=12)
        axes[1].set_ylabel('log(Wk)', fontsize=12)
        axes[1].set_title('Within-Cluster Dispersion: Data vs Reference', fontsize=14)
        axes[1].legend()
        axes[1].grid(True, alpha=0.3)
        
        plt.tight_layout()
        plt.show()
        
        return fig
 
 
# Example usage
from sklearn.datasets import make_blobs
 
# Generate data with known structure
np.random.seed(42)
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=1.0, random_state=42)
 
# Compute Gap statistic
gap = GapStatistic(n_refs=20, use_pca_reference=True, random_state=42)
results = gap.compute_gap(X, k_range=range(1, 10))
 
print(f"
Optimal k by Gap statistic: {results['optimal_k']}")
print(f"True k: 4")
 
# Visualize
gap.plot_results(results, true_k=4)

Understanding the Selection Rule

The Gap selection rule deserves careful explanation: $$\text{Choose smallest } k \text{ such that } \text{Gap}(k) \geq \text{Gap}(k+1) - s_{k+1}$$ Why This Rule? The intuition is statistical: we want to know if increasing k significantly improves the Gap. The standard error sₖ₊₁ provides a measure of uncertainty. If Gap(k) is within one standard error of Gap(k+1), we cannot confidently say that k+1 is better, so we prefer the simpler model k. Equivalently Written As: $$\text{Gap}(k) + s_{k+1} \geq \text{Gap}(k+1)$$ This says: stop when adding the uncertainty band to Gap(k) overlaps with Gap(k+1).

Example: Applying the Selection Rule
k	Gap(k)	s_k	Gap(k) ≥ Gap(k+1) - s_{k+1}?	Decision
1	1.20	0.15	1.20 ≥ 2.50 - 0.18 = 2.32? No	Continue
2	2.50	0.18	2.50 ≥ 3.80 - 0.22 = 3.58? No	Continue
3	3.80	0.22	3.80 ≥ 4.10 - 0.25 = 3.85? No	Continue
4	4.10	0.25	4.10 ≥ 3.95 - 0.28 = 3.67? Yes	Stop: k=4
5	3.95	0.28	(not evaluated)

Alternative Selection Rules 1. Maximum Gap : k* = argmax Gap(k) Simpler but may overfit Works well when the maximum is clear 2. First significant increase stops : Similar to elbow method but with Gap 3. One-standard-error rule from k *: Choose smallest k within one SE of max Gap More conservative Inspired by cross-validation selection in supervised learning 4. Two-standard-error rule : Even more conservative Gap(k) \geq Gap(k+1) - 2\cdotsₖ₊₁ Use when false positives (over-clustering) are costly

Practical Recommendation

Plot the Gap curve with error bars and visually inspect. If there's a clear elbow or maximum, trust it. If the curve is flat or noisy, consider that the data may not have clear cluster structure—or try a larger reference sample (increase n_refs).

Gap Statistic Variants

Several variants and extensions of the Gap statistic have been proposed: Weighted Gap For datasets with varying cluster sizes, weight the dispersion calculation: $$W_k^{weighted} = \sum_{r=1}^{k} n_r \cdot \text{AvgDisp}(C_r)$$ This gives more importance to larger clusters. Modified Gap (Yan & Ye, 2007) Uses a modified selection criterion that is less sensitive to the number of reference samples: $$k^* = \min{k : \text{Gap}(k) \geq \max_{j \leq k_{max}} \text{Gap}(j) - s_j}$$ Tibs2001SEmax Another variant that looks for the first k where Gap exceeds the maximum Gap minus its standard error: $$k^* = \min{k : \text{Gap}(k) \geq \text{Gap}(k_{max}) - s_{k_{max}}}$$

gap_variants.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import numpy as np
 
def gap_selection_variants(gaps, std_errors, k_range):
    """
    Compare different Gap selection rules.
    
    Parameters:
    -----------
    gaps : array-like
        Gap values for each k
    std_errors : array-like
        Standard errors for each k
    k_range : list
        Values of k tested
    
    Returns:
    --------
    dict with recommendations from different rules
    """
    k_range = list(k_range)
    n_k = len(k_range)
    
    results = {}
    
    # 1. Standard Tibshirani rule
    optimal_standard = k_range[0]
    for i in range(n_k - 1):
        if gaps[i] >= gaps[i+1] - std_errors[i+1]:
            optimal_standard = k_range[i]
            break
    else:
        optimal_standard = k_range[-1]
    results['standard'] = optimal_standard
    
    # 2. Maximum Gap
    results['maximum'] = k_range[np.argmax(gaps)]
    
    # 3. One-SE rule from maximum
    max_gap_idx = np.argmax(gaps)
    max_gap = gaps[max_gap_idx]
    max_gap_se = std_errors[max_gap_idx]
    threshold = max_gap - max_gap_se
    
    for i, gap in enumerate(gaps):
        if gap >= threshold:
            results['one_se_from_max'] = k_range[i]
            break
    
    # 4. First significant jump
    # Look for first k where gap increases significantly from k-1
    results['first_jump'] = k_range[0]
    for i in range(1, n_k):
        if gaps[i] > gaps[i-1] + std_errors[i]:
            results['first_jump'] = k_range[i]
            break
    
    # 5. Two-SE rule (more conservative)
    optimal_2se = k_range[0]
    for i in range(n_k - 1):
        if gaps[i] >= gaps[i+1] - 2 * std_errors[i+1]:
            optimal_2se = k_range[i]
            break
    else:
        optimal_2se = k_range[-1]
    results['two_se'] = optimal_2se
    
    return results
 
 
# Example with synthetic data
np.random.seed(42)
k_range = list(range(1, 10))
 
# Simulate Gap values that peak at k=4
gaps = np.array([1.0, 2.2, 3.5, 4.2, 4.0, 3.8, 3.6, 3.5, 3.4])
std_errors = np.array([0.15, 0.18, 0.20, 0.22, 0.23, 0.24, 0.25, 0.26, 0.27])
 
results = gap_selection_variants(gaps, std_errors, k_range)
 
print("Gap Selection Rule Comparison")
print("="*50)
print(f"
Gap values: {gaps}")
print(f"Standard errors: {std_errors}")
print()
for rule, k in results.items():
    print(f"  {rule:20s}: k = {k}")
print()
print("Note: Different rules balance sensitivity vs. specificity")
print("      More conservative rules (two_se) prefer fewer clusters")

Practical Considerations

Computational Cost Gap statistic is computationally expensive: For each k: 1 clustering on original data + B clusterings on reference data Total: (k_max) \times (B + 1) clustering runs For k_max = 10 and B = 20: 210 clustering runs Strategies to reduce cost: Use smaller B (20 is often sufficient for modest n) Limit k_max based on domain knowledge Use faster clustering algorithms (mini-batch k-means) Parallelize reference computations

Recommended Settings
Dataset Size	n_refs (B)	k_max	Notes
< 1,000	50-100	10-15	Can afford more references
1,000 - 10,000	20-50	10	Standard settings
10,000	10-20	< 10	Consider sampling
100,000	10	Based on domain	Use mini-batch k-means

When Gap Statistic Works Well ✓ Data has well-separated, roughly spherical clusters ✓ Cluster sizes are relatively balanced ✓ True k is within the tested range ✓ Sufficient samples per expected cluster When Gap Statistic May Fail ✗ Non-convex clusters (moons, rings) ✗ Highly imbalanced cluster sizes ✗ Very high-dimensional data (curse of dimensionality affects references) ✗ Overlapping clusters with ambiguous boundaries ✗ Hierarchical or nested cluster structure

Gap May Suggest k=1

If your data truly has no cluster structure (or structure not capturable by k-means), Gap will correctly suggest k=1. This is a feature, not a bug—but verify by examining the data and trying other algorithms. A result of k=1 may also indicate that preprocessing (normalization, dimensionality reduction) is needed.

Gap Statistic: Comparing Clusters to Null References

The Quest for a Principled k Selection Method

The Core Intuition

The Within-Cluster Dispersion Curve

The Reference Distribution Idea

Visual Intuition

Mathematical Formulation

Formal Definition

The Gap Selection Rule

Choosing the Reference Distribution

1. Uniform over Bounding Box

2. Uniform over PCA-Rotated Box

Complete Implementation

Understanding the Selection Rule

Why This Rule?

Equivalently Written As:

Alternative Selection Rules

Gap Statistic Variants

Weighted Gap

Modified Gap (Yan & Ye, 2007)

Tibs2001SEmax

Practical Considerations

Computational Cost

When Gap Statistic Works Well

When Gap Statistic May Fail

There’s more to understand.

Gap Statistic: Comparing Clusters to Null References

The Quest for a Principled k Selection Method

The Core Intuition

The Within-Cluster Dispersion Curve

The Reference Distribution Idea

Visual Intuition

Mathematical Formulation

Formal Definition

The Gap Selection Rule

Choosing the Reference Distribution

1. Uniform over Bounding Box

2. Uniform over PCA-Rotated Box

Complete Implementation

Understanding the Selection Rule

Why This Rule?

Equivalently Written As:

Alternative Selection Rules

Gap Statistic Variants

Weighted Gap

Modified Gap (Yan & Ye, 2007)

Tibs2001SEmax

Practical Considerations

Computational Cost

When Gap Statistic Works Well

When Gap Statistic May Fail

There’s more to understand.