Repeated Train-Test Perturbations For Clusters

Why Perturb Clustering With Train-Test Splits?

A clustering solution can look convincing on the subjects used to construct it and still be sensitive to which subjects were included. Repeated train-test perturbations examine this sensitivity by fitting clusters on one subset of subjects, assigning the held-out subjects using the fitted solution, and repeating the process with new random partitions. The central question is not whether a particular cluster label is correct, but whether the grouping pattern persists when the training sample changes.

This procedure is useful only when the clustering method has a defined way to assign new subjects to clusters. For example, a fitted centroid-based solution can assign a held-out subject to its nearest training centroid. Other clustering methods may need a prespecified extension, such as assignment to the nearest training medoid. If no defensible out-of-sample assignment rule exists, the proposed procedure does not directly evaluate that clustering method.

As in the earlier material on subgroup stability, stability describes reproducibility under specified perturbations. It does not establish that subgroups are true biological classes, nor that they predict a clinical outcome.

Definition and Protocol

Definition: A repeated train-test perturbation for clustering repeatedly partitions subjects into a training set and a held-out test set. A clustering algorithm is fit using the training subjects only. Each test subject is assigned to a training cluster by a prespecified out-of-sample rule. The resulting assignments are compared across runs, usually on subjects held out in both runs.

Let \(X_i\) denote the measured feature vector for subject \(i\), and let \(b\) index a random split. Write \(R_b\) for the training subjects and \(T_b\) for the held-out subjects, with \(R_b\cap T_b=\varnothing\). Fit the clustering algorithm to \(\{X_i:i\in R_b\}\), then use its assignment rule to obtain \(z_i^{(b)}\) for every \(i\in T_b\). The numeric values of \(z_i^{(b)}\) are labels for that run, not universal cluster identities.

For two runs \(b\) and \(c\), define their common test set as \(O_{bc}=T_b\cap T_c\). One simple label-invariant comparison is pairwise agreement: for each pair of subjects in \(O_{bc}\), ask whether the two runs agree on whether the pair belongs to the same cluster. Let \(M_{bc}\) be the number of unordered subject pairs in \(O_{bc}\), and let \(\mathbf{1}(\cdot)\) equal 1 when its condition is true and 0 otherwise.

A_{bc}= \frac{1}{M_{bc}} \sum_{\substack{i<j\\i,j\in O_{bc}}} \mathbf{1}\!\left[ \mathbf{1}\{z_i^{(b)}=z_j^{(b)}\} = \mathbf{1}\{z_i^{(c)}=z_j^{(c)}\} \right], \qquad M_{bc}=\binom{|O_{bc}|}{2}.

This comparison avoids matching cluster numbers across runs: changing every label in one run leaves every within-cluster equality unchanged. It is a descriptive agreement measure, not a chance-adjusted statistic. In particular, a high value can occur when both runs place most pairs in different clusters. Interpret it alongside cluster sizes and the split design, rather than as a standalone verdict.

Assumptions and Design Choices

The procedure needs an explicit target. A typical target is reproducibility of the clustering-and-assignment rule for new subjects drawn from the same population as the study subjects. That interpretation requires the following conditions to be reasonably credible:

Comparable subjects. The random split is appropriate for the sampling structure. If multiple observations come from one person, the person, not an individual measurement, must be kept intact across a split.
A defined feature space. Training and test subjects must be represented using compatible measurements and units. Any preprocessing must not use held-out information in a way that makes the test assignment artificially favorable.
A prespecified assignment rule. The held-out assignment must use the fitted training solution, not a new clustering fit that incorporates the test subjects.
A stable target configuration. For a focused comparison, hold the number of clusters and other essential algorithm settings fixed. Changing them between runs changes what is being compared.
Sufficient overlap. Each compared pair of runs needs enough shared test subjects to make a pair-based summary informative. If \(|O_{bc}|<2\), then \(M_{bc}=0\), so \(A_{bc}\) is undefined.

Split proportions are a design choice, not a universal constant. A small training set may produce poorly estimated clusters; a small test set may leave too few shared subjects for comparison. Repeated random splits also reuse subjects, so pairwise summaries from different run pairs are dependent. Their distribution is useful for describing sensitivity, but should not be treated as a collection of independent observations for a standard error or significance test.

Worked Examples

Worked Example: Assigning Held-Out Subjects to Fitted Centroids

Suppose a hypothetical two-feature omics analysis fits two clusters on the training subjects, with centroids \(C_1=(0,0)\) and \(C_2=(4,0)\). The prespecified rule assigns a held-out subject to the centroid with the smallest squared Euclidean distance. Three held-out subjects have feature vectors \(x_A=(1,0)\), \(x_B=(3,1)\), and \(x_C=(2,0)\).

For subject A, the squared distances are \((1-0)^2+(0-0)^2=1\) to \(C_1\), and \((1-4)^2+(0-0)^2=9\) to \(C_2\). A is assigned to cluster 1.

For B, the distances are \((3-0)^2+(1-0)^2=10\) and \((3-4)^2+(1-0)^2=2\). B is assigned to cluster 2. For C, both distances equal \((2-0)^2=4\). This is a tie, so the assignment rule must specify how ties are handled; suppose ties are assigned to cluster 1. The held-out assignments are therefore \(z_A=1,z_B=2,z_C=1\).

The tie rule is part of the procedure, not a harmless implementation detail. A different rule could change a held-out grouping and hence the stability summary. This calculation also assumes the features are on the scale used to fit the centroids; if one feature has a much larger numerical scale, the distance rule may be dominated by it.

Worked Example: Comparing Two Runs on Their Shared Test Subjects

Suppose run 1 holds out subjects A, B, C, and D, with assignments \(1,1,2,2\), respectively. Run 2 holds out B, C, D, and E, with assignments \(7,8,9,7\). The shared test set is \(O_{12}=\{B,C,D\}\), so there are \(\binom{3}{2}=3\) pairs to compare.

In run 1, B and C are in different clusters, B and D are in different clusters, and C and D are in the same cluster. In run 2, all three pairs are in different clusters. Thus the runs agree for B-C and B-D, but disagree for C-D. Substitution into the formula gives

A_{12}=\frac{2}{3}=0.667.

The labels 1, 2, 7, and 8 do not need to correspond across runs. The comparison asks only whether each pair is co-clustered or separated. With only three pairs, this value is coarse: one pair changing its status changes the summary by one third.

Worked Example: Why a Different Partition Can Lower Agreement

Consider four shared held-out subjects A, B, C, and D. Run 1 groups them as \(\{A,B\}\) and \(\{C,D\}\); run 2 groups them as \(\{A,C\}\) and \(\{B,D\}\). There are \(\binom{4}{2}=6\) pairs. In run 1, A-B and C-D are together. In run 2, A-C and B-D are together. These four pairs have different same-cluster status across runs. The remaining pairs A-D and B-C are separated in both.

Therefore only two of the six pairwise comparisons agree, giving \(A_{12}=2/6=0.333\). This low agreement reflects a substantial rearrangement of the grouping, even though both runs contain two clusters of size two. Cluster counts and sizes alone would not reveal that the subjects have been regrouped.

Derivation and Interpretation

The pairwise comparison is invariant to arbitrary relabeling. To see why, let \(\pi\) be any one-to-one renaming of the cluster labels in a run. Because \(\pi\) is one-to-one,

z_i^{(b)}=z_j^{(b)} \quad\Longleftrightarrow\quad \pi(z_i^{(b)})=\pi(z_j^{(b)}).

Thus each same-cluster indicator in the agreement formula is unchanged by relabeling, and so is \(A_{bc}\). This is important because cluster labels such as “1” and “2” have no intrinsic ordering or identity. Directly counting equal numeric labels across runs would be invalid unless labels had first been matched by a separate procedure.

A single split comparison can be noisy, especially when the shared test set is small. A practical summary reports the distribution of \(A_{bc}\) across eligible run pairs, together with the number of shared subjects and pairs contributing to each comparison. For example, a median agreement can describe a typical run-pair comparison, while a lower quantile can expose especially discordant runs. These summaries do not remove the dependence among comparisons or turn them into formal confidence intervals.

Diagnostics, Alternatives, and Limitations

Inspect more than the final agreement values. Record the training and test sizes, the number of subjects shared by each compared pair of runs, the cluster sizes in each fitted training solution, and how many test subjects are assigned to each cluster. Look for runs in which a cluster disappears, becomes extremely small, or receives many assignments near a decision boundary. Such patterns can explain low agreement or reveal that the assignment rule is unstable.

A low score can arise because the fitted clusters change with the training sample, because the out-of-sample assignment rule behaves poorly, or because many subjects lie near cluster boundaries. Conversely, high raw agreement may mostly reflect pairs that are separated in both runs. Check whether the summary is being driven by this common “different cluster” status, and report cluster-size information. Also investigate whether split results depend strongly on a few unusual subjects or on the random split seed.

Approach	What it varies or compares	Key distinction
Repeated train-test perturbations	Refits on training subsets and compares assignments of shared held-out subjects	Tests how a fitted solution assigns new subjects after the training sample changes
Subsampling without replacement	Refits on repeated subsets of observed subjects	Can summarize the resulting partitions without requiring a held-out assignment rule
Bootstrap assessment	Refits on samples drawn with replacement	Uses a different resampling scheme; duplicated and omitted subjects affect the perturbation
External group labels	Compares cluster assignments with an independently observed classification	Evaluates agreement with that external label, not reproducibility across training samples

The main advantage of train-test perturbations is that they distinguish fitting clusters from assigning new subjects. Their main limitation is that the result depends on the assignment rule as well as on the clustering fit. A method that cannot naturally assign held-out subjects may require an added rule that changes the scientific meaning of the analysis. The procedure also assesses only the chosen feature representation, preprocessing, split design, cluster count, and algorithm settings; it does not establish that these choices are appropriate.

A common mistake is to compare the numeric cluster labels directly and declare two runs unstable whenever “cluster 1” in one run has label 2 in another. The correction is to compare label-invariant group structure, such as whether pairs are together or apart, on subjects held out in both runs. Another mistake is to treat a high agreement value as proof of valid biological subtypes. Stability is evidence of reproducibility under the specified perturbation, not evidence of biological truth, causal structure, or clinical utility.

Key takeaway: Repeated train-test perturbations evaluate the reproducibility of a complete fit-and-assign procedure. Define the split unit, clustering settings, and held-out assignment rule in advance; compare runs only on their shared test subjects; and interpret agreement together with overlap and cluster-size diagnostics.

Check Your Understanding

Answer each question, then check the solutions below.

Why must a clustering method have a prespecified rule for assigning held-out subjects?
Two runs share five held-out subjects. How many unordered subject pairs contribute to their pairwise agreement?
In one run, subjects A and B are together; in another, they are separate. Does changing cluster numbers alone affect this comparison? Explain.
Why should repeated pairwise agreement values not automatically be treated as independent observations?
Give one interpretation that a high agreement score supports, and one conclusion it does not support.

Solutions. (1) Without an out-of-sample rule, test subjects cannot be assigned using the training fit, so the proposed fit-and-assign procedure is undefined. (2) The number is \(\binom{5}{2}=5(4)/2=10\) pairs. (3) No. The comparison uses whether A and B are together, which is unchanged by a one-to-one renaming of cluster labels; their different same-cluster status across the runs is still a disagreement. (4) Different run pairs can reuse the same subjects and split fits, making their summaries dependent. (5) A high score supports reproducibility of the specified clustering-and-assignment procedure under the chosen splits. It does not prove that the clusters are true biological classes or that they cause or predict an outcome.