Definition
Cluster stability (Ben-Hur et al. 2002) is an approach to validating a clustering and choosing the number of clusters based on reproducibility under perturbation: a clustering reflects genuine structure only if independent subsamples of the data yield clusterings that agree with one another. Instability — clusterings that disagree across resamples — signals that the chosen number of clusters is unsupported or that the data have no real cluster structure.
Key Ideas
- Stability = reproducibility. Real structure survives resampling; if repeatedly clustering perturbed (subsampled) versions of the data gives consistent partitions, the pattern is trustworthy.
- Distribution of pairwise similarities. For a candidate number of clusters k, cluster many subsamples, compute a similarity index (set overlap / adjusted Rand-type) between pairs of clusterings, and examine the whole distribution of these similarities — not just its mean.
- Choosing the number of clusters. The largest k whose similarity distribution stays concentrated near 1 estimates the number of clusters; as k exceeds the true number, the distribution spreads toward lower similarity.
- Detecting the absence of structure. If even small k produces unstable clusterings, the data likely have no genuine clusters — a check that internal indices (which always return some partition) cannot provide.
- Algorithm-agnostic wrapper. The procedure treats the clustering algorithm as a black box, so it applies to k-means, hierarchical clustering, spectral methods, or mixture models alike.
Why It Matters
- Answers the count question. Choosing the number of clusters is the central difficulty of unsupervised learning; stability gives a principled, assumption-light criterion where internal validity indices are ad hoc.
- A reproducibility discipline. It imports the cross-validation philosophy — trust what generalizes across resamples — into the unsupervised setting.
- Widely applied. Especially in bioinformatics (microarray/omics data) where the true number of groups is unknown and over-clustering is easy.
Open Questions
- Unequal clusters. Stability can be misleading when clusters differ greatly in size or density; a stable low-k solution can mask real finer structure.
- Choice of similarity and subsampling. Results depend on the pairwise-similarity index, the subsample fraction, and the number of resamples; there is no single canonical setting.
- Stability vs. correctness. A stable clustering need not be the true one — stability is necessary, not sufficient — so it is best combined with model-based (mixture/latent-class) criteria.
Related