Assess Cluster Count And Stability With Resampling

Why Cluster Count and Stability Need Separate Checks

A clustering algorithm will produce groups even when the data do not contain a useful grouping. It may also produce different group assignments when the number of clusters, the sampled observations, or the algorithm's starting values change. A defensible analysis therefore asks two distinct questions: does this cluster count give a useful partition, and does that partition persist under reasonable perturbations?

Within-cluster variation helps compare candidate counts, but it cannot identify a uniquely correct count by itself. Stability checks measure sensitivity to changes in the data or algorithm; they do not establish that clusters are real, meaningful, or predictive of an outcome. The aim is to combine quantitative evidence with an interpretation of what the groups represent.

Definition: For a partition into $k$ clusters $C_1,\ldots,C_k$, the within-cluster sum of squares (WCSS) is $$ W_k=\sum_{r=1}^{k}\sum_{i\in C_r}\lVert x_i-\bar{x}_r\rVert^2, $$ where $x_i$ is the feature vector for observation $i$, $\bar{x}_r$ is the mean feature vector in cluster $C_r$, and the squared distance is computed using the chosen feature scaling. Smaller WCSS means observations are closer to their assigned cluster means.

For k-means, the algorithm seeks a partition and cluster means that reduce WCSS. For a fixed data set, increasing $k$ cannot increase the minimum attainable WCSS: a cluster can be split, and the previous assignment can be retained as a possible solution. At $k=n$, where $n$ is the number of observations, each observation can form its own cluster and WCSS is zero. That endpoint is not a useful selection rule.

Comparing Candidate Counts

A common diagnostic is an elbow plot: plot WCSS against $k$, then look for a point after which adding clusters produces much smaller improvements. The elbow is a judgment, not a theorem. If the curve has no clear bend, the data may not support a single obvious count. A useful candidate partition should also have groups that can be described meaningfully in terms of the features and the intended use.

Interpretability does not mean inventing a story for every group. Check whether group profiles differ in a way that is relevant, coherent, and not driven by an anomalous observation or an arbitrary coding choice. For example, a split that creates a tiny cluster containing one extreme record may reduce WCSS, but that improvement may not justify treating the record as a stable segment.

Comparisons require a consistent feature set and distance scale. If one feature has values in thousands and another in fractions, the first can dominate Euclidean distances unless scaling is appropriate for the problem. Candidate counts should be compared using the same preprocessing choices; otherwise a WCSS difference may reflect a changed scale rather than a changed partition. The earlier material on scaling and cluster shape addresses the choice of distance representation.

Worked Example: Finding a Plausible Elbow

A hypothetical insurer summarizes six policy records by one standardized exposure score: $2,4,6,12,14,16$. Consider the displayed partitions for $k=1,2,3$: for $k=2$, use $\{2,4,6\}$ and $\{12,14,16\}$; for $k=3$, use $\{2,4\}$, $\{6\}$, and $\{12,14,16\}$. Calculate WCSS and assess whether the extra cluster appears useful. The method is direct calculation of squared deviations; the common mistake to avoid is reporting the WCSS of one cluster as the total for the partition.

For $k=1$: The mean is $(2+4+6+12+14+16)/6=54/6=9$. The squared deviations are $49,25,9,9,25,49$, so $W_1=49+25+9+9+25+49=166$.

For $k=2$: The first cluster mean is $(2+4+6)/3=4$; its squared deviations sum to $(2-4)^2+(4-4)^2+(6-4)^2=4+0+4=8$. The second mean is $(12+14+16)/3=14$; its squared deviations sum to $4+0+4=8$. Therefore $W_2=8+8=16$.

For $k=3$: The means are $3$, $6$, and $14$. The first cluster contributes $(2-3)^2+(4-3)^2=1+1=2$. The singleton contributes zero, and the last cluster contributes $4+0+4=8$. Thus $W_3=2+0+8=10$.

The reductions are $W_1-W_2=166-16=150$, then $W_2-W_3=16-10=6$. The much smaller second reduction suggests an elbow around $k=2$ for these displayed partitions. The two-cluster result also separates the lower and higher scores cleanly. This is evidence for considering $k=2$, not proof that it is the uniquely correct answer. The arithmetic check is $W_1>W_2>W_3$, as expected; in particular, the two three-point clusters at $k=2$ contribute $8$ each, for a total of $16$.

Measuring Agreement Between Partitions

Cluster labels have no intrinsic meaning: relabeling cluster 1 as cluster 2 does not change a partition. Comparing labels observation by observation can therefore give a misleadingly poor agreement score. The adjusted Rand index (ARI) avoids this problem by comparing pairs of observations. It is $1$ for identical partitions, near $0$ for agreement at the level expected under a chance-adjusted comparison, and can be negative when agreement is less than that benchmark.

Definition: Given two partitions of the same $n$ observations, let $n_{ij}$ be the number assigned to cluster $i$ in the first partition and cluster $j$ in the second. Let $a_i=\sum_j n_{ij}$, $b_j=\sum_i n_{ij}$, and $N=\binom{n}{2}$. The ARI is $$ \operatorname{ARI}= \frac{\displaystyle\sum_{i,j}\binom{n_{ij}}{2} -\frac{\left(\sum_i\binom{a_i}{2}\right)\left(\sum_j\binom{b_j}{2}\right)}{N}} {\displaystyle\frac{1}{2}\left(\sum_i\binom{a_i}{2}+\sum_j\binom{b_j}{2}\right) -\frac{\left(\sum_i\binom{a_i}{2}\right)\left(\sum_j\binom{b_j}{2}\right)}{N}}. $$ Here $\binom{m}{2}=m(m-1)/2$ counts pairs within a group. The index is undefined in degenerate cases where its denominator is zero; report that circumstance rather than treating the formula as an ordinary comparison.

The adjustment in this formula has a pair-count interpretation. The observed shared-pair count is $\sum_{i,j}\binom{n_{ij}}{2}$: it counts pairs grouped together in both partitions. If the first partition has $A=\sum_i\binom{a_i}{2}$ same-cluster pairs and the second has $B=\sum_j\binom{b_j}{2}$, a chance benchmark with those group sizes fixed is $AB/N$. To see why, a given pair has probability $A/N$ of being together in the first partition and $B/N$ of being together in the second; under the chance benchmark, the expected shared count is $N(A/N)(B/N)=AB/N$. The numerator subtracts this expected agreement. The denominator scales the adjustment by the maximum average pair agreement beyond that benchmark.

Worked Example: Comparing Two Eight-Record Partitions

Two clustering runs assign eight hypothetical claim profiles to two groups. Their contingency table is $$ \begin{array}{c|cc|c} &\text{Run 2: A}&\text{Run 2: B}&\text{Run 1 total}\\ \hline \text{Run 1: A}&3&1&4\\ \text{Run 1: B}&1&3&4\\ \hline \text{Run 2 total}&4&4&8 \end{array} $$ Calculate the ARI. The method is pair counting with a chance adjustment; the trap is to use raw matching counts as if cluster labels were meaningful.

The shared within-cell pair count is $\binom{3}{2}+\binom{1}{2}+\binom{1}{2}+\binom{3}{2}=3+0+0+3=6$. Each row total is 4, so the row pair total is $2\binom{4}{2}=2(6)=12$. Each column total is also 4, so the column pair total is 12. The total number of pairs is $N=\binom{8}{2}=28$.

The chance-adjusted expected count is $12(12)/28=144/28=36/7$. The numerator is $6-36/7=6/7$. The denominator is $(12+12)/2-36/7=12-36/7=48/7$. Thus $\operatorname{ARI}=(6/7)/(48/7)=6/48=0.1250$, to four decimal places.

The result indicates modest chance-adjusted agreement, not near-identical clusters. A raw count might emphasize that six records lie on the diagonal, but the ARI also accounts for how many same-cluster pairs each run creates. As a check, the ARI is below 1 because the off-diagonal cells contain observations, so the two partitions are not identical.

Resampling and Initialization Stability

Resampling asks whether a partition is sensitive to which observations were used. A practical procedure is to hold the candidate $k$, feature definitions, distance choices, and preprocessing rule fixed; repeatedly draw subsamples; fit the clustering method; then compare assignments on observations shared by each pair of fits. Subsampling without replacement makes the comparison set straightforward. With bootstrap samples, repeated copies of an observation need careful handling: compare unique observation identities, or specify explicitly how multiplicities are treated.

For k-means, initialization is a separate source of variation. Fit the same $k$ several times on the same data with different starting centroids. Similar final WCSS values and high agreement between assignments suggest that the algorithm is finding a consistent solution. Different solutions can reveal local minima or weakly separated groups. A single run cannot distinguish a data-sensitive partition from a fortunate or unfortunate start.

For hierarchical clustering, the starting-point issue is different: a fixed distance definition and linkage rule produce a deterministic hierarchy, but the partition at a chosen cut can still be sensitive to the sample, feature perturbations, or reasonable modeling choices. Repeat the clustering under resampling and compare the cut assignments on common observations. In either method, state what was perturbed. Stability to initial centroids is not the same as stability to resampling.

Worked Example: Interpreting Resampling Agreement

A reference two-cluster solution and two perturbed fits are compared on the same eight common hypothetical records. The first perturbed fit has the contingency table from the preceding example, so its ARI is $0.1250$. The second perturbed fit puts four records together in each group exactly as in the reference partition; its table, after relabeling clusters if needed, has diagonal cells 4 and 4 and off-diagonal cells 0. Calculate the mean ARI and interpret it. The method is to calculate each label-invariant agreement and average the two; the mistake to avoid is treating one strong replicate as evidence that all perturbations are stable.

For the first fit, the ARI is $0.1250$, as calculated above. For the second fit, the partitions are identical up to label switching, so its ARI is $1$. The mean is $(0.1250+1)/2=1.1250/2=0.5625$.

A mean ARI of $0.5625$ conceals substantial variation: one perturbation agrees perfectly, while the other agrees only weakly beyond the chance adjustment. Report the individual scores or their spread along with the mean. This small illustration does not establish that $k=2$ is stable; a real assessment would use many perturbations and examine the distribution of agreement scores. For hierarchical clustering, compute the ARI on records assigned in both fits; for k-means, keep the chosen $k$ fixed when comparing assignment stability.

Putting the Evidence Together

A practical decision considers both fit and robustness. WCSS will generally fall as $k$ increases, so compare its reductions rather than selecting the smallest value. Then inspect whether candidate clusters have meaningful profiles, whether tiny groups are defensible, and whether resampling or initialization produces similar memberships. A candidate with a modestly higher WCSS can be preferable if it yields clearer and more stable groups.

Stability is not a substitute for interpretation. A method can repeatedly recover a partition because the same distance scale or modeling choice consistently separates an unimportant feature. Conversely, weak stability can be informative: it may indicate overlapping groups, a borderline cluster count, influential observations, or a partition that depends heavily on algorithm settings. The conclusion should be calibrated to the evidence, not framed as proof that a population has a fixed number of natural groups.

Compare candidate counts.
Compute WCSS on the same feature representation and look for a meaningful change in its reductions.

Inspect the partitions.
Describe the group profiles and check whether any apparent segment is too small, anomalous, or difficult to interpret.

Perturb the analysis.
Use resampling to assess data sensitivity and, for k-means, repeated starts to assess initialization sensitivity.

Compare assignments fairly.
Use a label-invariant index such as ARI on common observations, and report variability as well as an average.

Do not equate lower WCSS with a better final choice. Its ability to decrease with $k$ is built into the optimization problem.
Do not compare cluster numbers by their labels. Cluster labels can be permuted without changing a partition.
Do not call a result stable based on one repeat. Examine several perturbations and describe the range of agreement.
Do not interpret stability as outcome evidence. Clustering is an unsupervised description of features, not evidence that a group predicts or causes an outcome.

Key takeaway: Use WCSS reductions and interpretable group profiles to screen candidate cluster counts, then test the selected candidates for sensitivity to resampling and, for k-means, initialization. Stability strengthens a descriptive conclusion but does not by itself validate the clusters.

Check Your Understanding

Work each item by counting deviations or pairs carefully. Answers are included for checking.

A one-feature partition is $\{1,3\}$ and $\{8,10\}$. Find WCSS using cluster means. (Answer: $4$.)
A partition is $\{0,2,4\}$ and $\{10,12\}$. Find WCSS and state the two cluster means. (Answer: means $2$ and $11$; WCSS $=10$.)
Two partitions of four observations have contingency table $\begin{pmatrix}2&0\\0&2\end{pmatrix}$. Find the ARI. (Answer: $1.0000$.)
Two partitions of six observations have contingency table $\begin{pmatrix}2&1\\1&2\end{pmatrix}$. Here the shared within-cell pair count is $2$, each partition has $6$ same-cluster pairs, and $N=15$. Calculate the ARI. (Answer: $-0.1111$.)
A k-means fit has a lower WCSS at $k=5$ than at $k=4$, but repeated starts at $k=5$ give substantially different assignments. What should be reported before choosing $k=5$? (Answer: The WCSS reduction, the assignment variability across starts, and whether the extra clusters are interpretable; the lower WCSS alone does not justify $k=5$.)

What You'll Learn