Resampling To Assess Cluster Stability

Why Assess Cluster Stability?

A clustering algorithm always produces groups from the data supplied to it, but that fact alone does not show that the groups are persistent. Small changes in the observed records may change the memberships substantially. Resampling assesses this sensitivity by fitting the clustering procedure repeatedly to perturbed versions of the data and comparing the resulting assignments.

This is a question about stability, not proof that a set of groups is objectively true. A cluster solution can be stable but not useful for the business problem, and an unstable solution may reflect genuine overlap or limited information in the available data. Stability is one diagnostic to report alongside the clustering method, its inputs, and any relevant internal indices.

Resampling Designs and What Gets Compared

In a bootstrap, a resample of size \(n\) is drawn with replacement from \(n\) observed records. A record can appear more than once or not appear at all in a particular resample. In subsampling, a specified number of records is drawn without replacement, so no record is duplicated within a resample. The resampling scheme should be chosen and described before interpreting stability.

Each resample is clustered using the same preprocessing decisions, distance measure, clustering method, and number of clusters as the reference fit. If the aim is to evaluate whether a chosen cluster count is stable, hold that count fixed during this comparison. Changing it across fits makes it harder to separate membership sensitivity from changes in the number of groups.

The comparison also needs a defined set of observations. One option is to compare assignments only for records present in both fits. Another is to fit on each resample and then assign all original records using a defined extension of that clustering method, such as assignment to the nearest fitted \(k\)-means centroid. That extension is not available for every method. For methods without a natural assignment rule for new records, compare only the shared records or state a justified alternative explicitly.

Bootstrap resamples contain duplicate copies of some records. If a method or comparison treats copies as separate observations, their repeated presence can affect the fitted clusters. A report should state how duplicates are handled and should not silently treat a bootstrap fit as if every original record appeared exactly once. Subsampling avoids within-resample duplicates, but a record omitted from a fit cannot contribute a membership comparison for that fit unless an assignment rule is defined.

Matching Clusters Across Fits

Cluster labels such as “cluster 1” and “cluster 2” are arbitrary. A fit that calls a group cluster 1 and another fit that calls the same group cluster 2 has not changed its memberships. Therefore, compare sets of observations, not the numeric labels themselves.

For a reference cluster \(C\) and a cluster \(D\) from a resampled fit, their Jaccard overlap is the number of shared observations divided by the number appearing in either cluster. It ranges from 0, for no shared observations, to 1, for identical sets.

With multiple clusters, match clusters across the two fits to maximize total overlap, typically using the one-to-one matching with the largest sum of Jaccard values. This prevents a reference cluster from being matched independently to several resampled clusters. If the number of clusters differs, any unmatched cluster needs an explicit treatment; do not imply that a one-to-one comparison covers all groups.

A cluster-level stability summary can be the mean matched Jaccard value for that reference cluster across resamples. The average should be accompanied by the number of usable comparisons and, where informative, the range or distribution of values. An average alone can conceal a cluster that is stable in most fits but fails in a few.

Assignment Consistency for Individual Observations

A different summary asks how often each record remains in its reference cluster. First align the cluster labels in every fit to the reference solution, using a stated matching procedure. For observation \(i\), let \(B_i\) be the resamples in which a comparable assignment for \(i\) is available, and let \(M_i\) be the number of those assignments that agree with its reference cluster after alignment. Its assignment consistency is \(M_i/|B_i|\).

This value is defined only relative to the chosen reference and comparison rule. If an observation is absent from some subsamples and has no out-of-sample assignment rule, those resamples are excluded from its denominator. Reporting only a consistency value without that denominator can be misleading: a value based on two usable fits is less informative than the same value based on many.

Pairwise Co-Assignment and Why It Is Label-Invariant

Pairwise co-assignment asks whether two observations are placed in the same cluster, without requiring cluster labels to be matched. For a pair \(i,j\), calculate the proportion of usable resampled fits in which both observations can be compared that place them together. A fit contributes to the denominator only if the comparison is defined for both observations.

Here \(I_{bij}=1\) when fit \(b\) places \(i\) and \(j\) in the same cluster, and \(I_{bij}=0\) when it places them in different clusters. \(N_{ij}\) is the number of fits in which both observations have comparable assignments. This measure is unchanged if a fit renames its clusters, because it uses only the same-cluster relationship.

The justification is direct. Imagine independently generating resamples under the chosen resampling design and fitting the fixed clustering procedure each time. For each usable fit, \(I_{bij}\) records whether the pair is grouped together. If the probability of this event under that design is \(p_{ij}\), then each indicator has expectation \(E[I_{bij}]=p_{ij}\). For \(N_{ij}\) independent usable fits with the same design, the average indicator has expectation

Thus the observed co-assignment rate is the natural empirical estimate of the probability that the pair is grouped together under repeated perturbations of this kind. This interpretation depends on a consistent resampling design and comparable fits; it is not a probability that the pair belongs to a “true” cluster.

Interpreting Stability and Avoiding Common Traps

Resampling stability is conditional on the entire analysis procedure. Different preprocessing, distance calculations, clustering algorithms, or resampling designs can produce different stability results. If stability is low, investigate whether particular records move between groups, whether a cluster repeatedly splits or merges, and whether the instability is concentrated in a small number of observations. Do not infer a cause from a stability score alone.

A common exam trap is to mistake cluster label switching for instability. Suppose a reference fit has \(\{A,B\}\) and \(\{C,D\}\), while a resampled fit reports “cluster 1” as \(\{C,D\}\) and “cluster 2” as \(\{A,B\}\). The memberships are identical: the correct matched Jaccard values are both 1. A comparison of numeric labels would incorrectly count all four assignments as changed.

Another mistake is to calculate overlap using the intersection divided by the size of just one cluster. That quantity is not Jaccard overlap and can be asymmetric. For example, if \(C=\{A,B,C\}\) and \(D=\{A,B,D\}\), their intersection has size 2 and their union has size 4, so the Jaccard value is \(2/4=0.5\). Dividing by \(|C|=3\) gives \(2/3\), which is a different measure and changes if the roles of \(C\) and \(D\) are reversed.

Finally, a high stability score does not establish predictive performance, causal meaning, or practical value. It only indicates that similar assignments were recovered under the stated perturbations and procedure. In a report aligned with the SOA Exam PA (Predictive Analytics) syllabus, describe what was resampled, how labels or observations were compared, how many comparisons were usable, and what the results do and do not support.