Clustering Stability and Bootstrap Validation
Bootstrap stability testing checks whether a clustering result is real structure or an accident of one particular sample, by re-running the clustering on many resampled versions of the data and seeing if the same groups keep showing up.
Prerequisites: Silhouette and Cluster Validity Indices
Clustering algorithms will always produce some answer, even when there's no real group structure in the data — feed k-means pure noise and it will happily draw boundaries anyway. Bootstrap stability testing checks whether the clusters found are trustworthy by resampling the dataset many times (with replacement) and re-clustering each resample, then seeing how consistently the same groupings reappear.
If clustering the same data with small random perturbations (bootstrap resamples) keeps producing the same groups, the structure is likely real; if the clusters shuffle unpredictably from one resample to the next, the original clustering was probably fitting noise rather than genuine structure.
How it's done
Draw a bootstrap sample (same size, sampled with replacement) from the dataset, re-run the clustering algorithm, and compare the new cluster assignments to the original using an agreement measure such as the Jaccard index or adjusted Rand index. Repeat this hundreds of times and look at the distribution of agreement scores — clusters that consistently score above roughly 0.7–0.8 agreement are considered stable; ones that regularly score near what random chance would give are not.
Worked example
A dataset is clustered into 3 groups. Across 200 bootstrap resamples, cluster A is recovered with an average Jaccard similarity of 0.85 to the original — it shows up reliably regardless of which subsample is drawn. Cluster C, on the other hand, only manages an average similarity of 0.35, close to what unrelated random partitions would score by chance, meaning cluster C is likely an artifact of the specific sample rather than a real group in the population.
Stability is not the same as validity — a clustering can be highly stable (the same wrong answer every time) if the algorithm has a strong bias, such as k-means always drawing roughly spherical clusters even when the true structure is elongated.
Related concepts
Practice in interviews
Further reading
- Hennig, 'Cluster-wise Assessment of Cluster Stability'