Why Assess Cluster Stability?
A clustering algorithm will return groups for a given data set, but that alone does not show whether those groups would recur under modest changes in the observed profiles. In genomic data, measurements may be noisy, samples may be limited, and many features may contribute weakly to a distance or similarity. Resampling stability asks whether the assignments are reproducible when the data used to fit the clustering are perturbed in a specified way.
The result is a measure of reproducibility under that perturbation, not a test that clusters are biologically real or a guarantee that they will generalize to a new population. Stability depends on the chosen profiles, features, preprocessing, distance, clustering method, tuning choices, and resampling design. These choices must be described so the stability question has a clear meaning.
Designing a Resampling Assessment
Let \(n\) profiles have feature vectors \(x_1,\ldots,x_n\). A clustering fit assigns each profile a label, but the numerical values of labels have no intrinsic meaning: labels 1 and 2 can be exchanged without changing the partition. Stability comparisons therefore need measures that depend on which profiles are grouped together, rather than on label names.
A common design repeatedly draws subsamples without replacement, refits the clustering procedure on each subsample, and compares assignments for profiles appearing together in the relevant fits. Subsampling avoids duplicate copies of the same profile within a fit. The subsample size should be reported: smaller subsamples perturb the data more and may make the assessment more demanding. Bootstrap resampling draws \(n\) profiles with replacement; it can be useful, but duplicates and omitted profiles require an explicit comparison rule.
There are two reasonable bootstrap comparison targets. One is to compare only profiles observed in both resamples, accounting carefully for duplicate occurrences so each original profile contributes at most once to a partition comparison. Another is to refit on each bootstrap sample and then assign every original profile to the fitted clustering using a defined assignment rule. The latter requires a method for assigning profiles not used in the fit; it is not automatically available for every clustering algorithm. Simply treating duplicated rows as distinct profiles can overweight them and does not give a direct comparison of the original profiles.
The pipeline also needs to be specified. If the goal is stability of the entire analysis, repeat data-dependent preprocessing and tuning within each resample, including any choice of number of clusters. If the goal is stability conditional on those choices, hold them fixed and state that condition. Likewise, a clustering algorithm with random initialization can vary even when the data are unchanged. Repeated starts or controlled random seeds can help separate algorithmic variation from perturbation due to resampling.
State the profiles, feature representation, preprocessing, clustering method, tuning choices, and whether those choices are repeated or held fixed.
Draw bootstrap samples or subsamples at the stated unit and size. Record which original profiles are available in each fit.
Apply the stated pipeline to each replicate, using a deliberate approach to random initialization and any tuning decisions.
Use a label-invariant partition measure on common profiles, or summarize pairwise co-membership over replicates in which each pair is jointly observed.
Adjusted Rand Index
For two partitions of the same \(n\) profiles, form a contingency table. Let \(n_{ij}\) be the number of profiles assigned to cluster \(i\) in the first partition and cluster \(j\) in the second. Let \(a_i=\sum_j n_{ij}\) and \(b_j=\sum_i n_{ij}\) be the cluster sizes in the two partitions. For an integer \(m\), \(\binom{m}{2}=m(m-1)/2\) counts pairs drawn from a group of size \(m\).
An ARI of 1 indicates identical partitions; an ARI near 0 indicates agreement about as large as expected under the fixed-cluster-size random reference used in the adjustment. Negative values indicate less agreement than that reference. The ARI is invariant to relabeling and can compare partitions with different numbers of clusters. It is undefined in a degenerate case if its denominator is zero; report how such cases are handled rather than interpreting an undefined value as evidence of stability.
Why the Adjustment Works
Each pair of profiles either is or is not together in a partition. The quantity \(\sum_{ij}\binom{n_{ij}}{2}\) counts pairs together in both partitions. The row and column sums determine the total number together in each partition: \(\sum_i\binom{a_i}{2}\) and \(\sum_j\binom{b_j}{2}\). If the partitions have fixed cluster sizes and their memberships are randomly aligned, the expected number of pairs together in both is the product of the two totals divided by \(N\).
To justify this expectation, consider a pair that is together in the first partition. Among the \(N\) possible profile pairs, the second partition has \(\sum_j\binom{b_j}{2}\) pairs together. Under a uniformly random alignment with those cluster sizes, the probability that the selected pair is together in the second partition is \(\sum_j\binom{b_j}{2}/N\). Summing this probability over the \(\sum_i\binom{a_i}{2}\) pairs together in the first partition gives the expected shared-pair count:
The ARI subtracts this expected agreement from the observed shared-pair count, then scales by the average possible excess agreement in the two partitions. Thus it corrects for agreement that can arise merely because clusters have particular sizes. It does not make an ARI a universal measure of quality: its value depends on the compared partitions and their size structure.
Worked Example: Calculating an ARI by Hand
Suppose six hypothetical genomic profiles are assigned to two clusters in partition A: \(\{1,2,3\}\) and \(\{4,5,6\}\). Partition B assigns them to \(\{1,2\}\), \(\{3,4\}\), and \(\{5,6\}\). The contingency table has rows for A and columns for B:
| B1 | B2 | B3 | Row total | |
|---|---|---|---|---|
| A1 | 2 | 1 | 0 | 3 |
| A2 | 0 | 1 | 2 | 3 |
| Column total | 2 | 2 | 2 | 6 |
There are \(N=\binom{6}{2}=15\) profile pairs. The shared-pair count is \(\sum_{ij}\binom{n_{ij}}{2}=1+0+0+0+0+1=2\). The row-pair total is \(\sum_i\binom{a_i}{2}=\binom{3}{2}+\binom{3}{2}=6\), and the column-pair total is \(3\binom{2}{2}=3\). Therefore,
The partitions agree more than the fixed-size random reference, but their agreement is far from perfect. This value describes the agreement for these two assignments; it is not a probability that the clustering is correct.
Co-Membership Probabilities
An overall ARI summarizes agreement between two fits in one number. A co-membership summary instead focuses on each pair of profiles. For resample \(r\), define \(I_{ij}^{(r)}=1\) if profiles \(i\) and \(j\) are assigned to the same cluster, and \(I_{ij}^{(r)}=0\) otherwise. Let \(R_{ij}\) be the set of replicates in which both profiles are available and comparable. The estimated co-membership probability is the fraction of those replicates in which the pair is grouped together.
This quantity lies between 0 and 1. Values near 1 indicate that the pair is usually grouped together under the specified resampling design; values near 0 indicate that it is usually separated. Values between these extremes flag pairs whose relationship changes across fits. The diagonal is often set to 1, but it carries no stability information because a profile is always in the same cluster as itself.
Worked Example: Reading Co-Membership Frequencies
Four hypothetical profiles are compared in five subsamples. Suppose profiles A and B are both present in all five; they are together in four fits. Profiles A and C are jointly present in four fits and together in one. Profiles B and C are jointly present in only three fits and together in two.
For A and B, \(\widehat{C}_{AB}=4/5=0.8000\). For A and C, \(\widehat{C}_{AC}=1/4=0.2500\). For B and C, \(\widehat{C}_{BC}=2/3\approx0.6667\). Thus A and B have the most reproducible co-membership of these three pairs, while A and C are usually separated. The denominators matter: B and C were jointly observed in three, not five, subsamples.
These are empirical frequencies over the specified resamples, not estimates that the pair has a particular biological relationship with a stated probability. With few replicates, the frequencies can be coarse and variable; report the number of jointly observed replicates alongside them.
Interpreting Variation and Diagnosing Problems
A useful assessment typically examines the distribution of pairwise ARIs across resampled fits, as well as co-membership patterns that reveal which profiles are consistently grouped. If a reference partition is used, state how it was obtained; for example, one might compare every resampled fit with a fit on the full data, or compare pairs of resampled fits on their common profiles. These answer related but different questions. Comparisons must use the same profiles within each ARI calculation.
A low or highly variable ARI can arise because profiles near a cluster boundary switch assignments, because the chosen number of clusters is not reproducible, because features or preprocessing are unstable, or because the algorithm reaches different local solutions. To investigate, examine cluster sizes across replicates, the number of profiles available for each comparison, pairwise co-membership patterns, and sensitivity to algorithm initialization. If \(K\) changes across replicates, report that variation; forcing a single summary without describing how different-sized partitions were compared can conceal an important result.
A high ARI does not establish that the partition is useful. A method can repeatedly find the same structure because of a strong technical artifact, an influential preprocessing decision, or a dominant separation that is irrelevant to the scientific question. Conversely, low stability need not mean the data contain no structure: a few uncertain profiles may lie between otherwise reproducible groups. Resampling assesses sensitivity to the chosen perturbations, not correctness, biological interpretation, or external validity. Those are distinct questions.
Worked Example: Separating Algorithmic and Sampling Instability
Suppose a hypothetical profile data set is clustered by a method with random initialization. In repeated fits to the unchanged data, pairwise ARIs range from 0.62 to 1.00. After using enough starts to retain the best objective value, repeated fits on the unchanged data have ARIs of 1.00. Across subsamples, however, ARIs relative to the full-data partition range from 0.35 to 0.78.
The first set of results shows that random initialization was a source of variation before the start strategy was improved. The second set indicates that substantial changes remain when the sample itself is perturbed. It would be incorrect to attribute all instability to initialization after the unchanged-data fits agree, or to call the clustering fully stable because the algorithm now returns the same answer on the original data. The conclusion is conditional: algorithmic variation was reduced, but assignments are sensitive to the chosen subsampling design.
Choosing a Comparison and Avoiding Pitfalls
| Approach | Strength | Key caution |
|---|---|---|
| Pairwise ARI between fits | Label-invariant summary of whole-partition agreement; accommodates differing cluster counts. | Compare only the same profiles, and report how pairs of fits or a reference partition were selected. |
| Co-membership frequencies | Shows which profile pairs are consistently together or separated. | Track pairwise availability and replicate counts; a single matrix can hide the number of fits behind each entry. |
| Stability of a chosen reference partition | Directly assesses whether resampled assignments reproduce the full-data grouping. | The full-data partition is itself estimated; this is not an independent validation. |
A common mistake is to average cluster labels across resamples or to count exact matches between numerical labels. Cluster labels are arbitrary, so a label swap can make identical partitions look completely different. Use a label-invariant comparison such as ARI or pairwise co-membership instead. Another mistake is to interpret a high stability score as proof that the clusters are true. The correction is to describe stability narrowly: the assignments are reproducible, or not, under the particular data perturbations and analysis pipeline that were used.
There is no universal threshold at which an ARI makes clusters “stable.” The number of resamples, perturbation size, reference choice, sample size, cluster balance, and research purpose all matter. Bootstrap and subsampling are alternatives, not interchangeable labels for the same design: bootstrap duplicates profiles and omits others, whereas subsampling without replacement changes the training set without duplicating rows. State the design and its limitations, and avoid relying on one aggregate number when the pairwise pattern shows meaningful heterogeneity.
Check Your Understanding
Answer each question, then compare your reasoning with the brief solutions.
- Why can two identical clusterings have different numerical labels, and what kind of comparison avoids this problem?
- In a co-membership analysis, a pair is jointly observed in eight replicates and grouped together in six. What is its estimated co-membership frequency, and what should also be reported?
- Why is it misleading to treat duplicated profiles in a bootstrap sample as distinct original individuals when comparing assignments?
- Two partitions have an ARI near zero. Does that establish that neither partition contains meaningful structure? Explain.
- What does a high ARI between resampled fits support, and what does it not establish?
Solutions. (1) Cluster labels are arbitrary; a label-invariant measure such as ARI or co-membership avoids dependence on their names. (2) The frequency is \(6/8=0.7500\); report the eight jointly observed replicates because the denominator indicates how much resampling information supports the estimate. (3) Duplicates would give a sampled original profile extra weight and would not represent distinct original profiles in the comparison. (4) No. An ARI near zero indicates agreement near its fixed-size random reference for those partitions; it does not determine whether either partition is scientifically useful. (5) It supports reproducibility under the stated resampling and pipeline; it does not prove biological validity, correctness, or generalization to a new population.