Cluster Stability Across Initializations

Why Repeat K-Means Starts?

For a fixed data set and a chosen number of clusters \(K\), K-means can converge to different solutions from different initial centers. Each run alternates assignments and center updates until its stopping rule is met. The resulting solution is a local optimum, not necessarily the same solution every time. Repeating the algorithm with different initializations reveals whether a particular clustering recurs or whether the result depends strongly on the start.

Stability is not the same as fit. Within-cluster sum of squares (WCSS) measures how closely observations lie to their assigned centers; a lower WCSS is preferred when comparing solutions with the same \(K\) and data. Stability asks a different question: do repeated runs produce similar memberships and centers? A run with the smallest WCSS may be an uncommon outcome, while a more frequently recurring partition may have a slightly larger WCSS. Both facts are useful, and neither answers the other question.

Definition: A repeated-initialization stability assessment runs K-means multiple times on the same observations, using the same variables, preprocessing, distance measure, value of \(K\), and convergence settings, while varying the initial centers. A solution is more stable when the resulting partitions and, where relevant, their centers recur or remain similar across runs.

The comparison must hold the analysis conditions fixed. If one run uses standardized variables and another uses raw units, a difference in the partitions cannot be attributed to initialization alone. Likewise, changing \(K\) changes the problem being solved. The earlier material on feature scaling and the choice of \(K\) addresses those separate decisions.

Comparing Memberships Without Relying on Cluster Names

Cluster labels such as “cluster 1” and “cluster 2” are arbitrary. One run can call a group cluster 1 and another can call the same group cluster 2. Therefore, comparing the printed labels observation by observation can falsely suggest disagreement. A simple label-invariant comparison asks whether each pair of observations is placed together or apart in each run.

Definition: For two partitions of \(n\) observations, pairwise agreement is the number of observation pairs that are together in both partitions or apart in both partitions, divided by the total number of pairs, \(\binom{n}{2}=n(n-1)/2\). Its value lies between 0 and 1. A value of 1 means the two partitions agree on every pair’s together/apart status.

This statistic does not require the cluster names to match. It is also not a complete measure of clustering quality: it gives equal weight to every pair, and the many pairs placed apart can dominate when clusters are small relative to the full data set. Use it alongside exact partition recurrence, cluster sizes, and WCSS rather than treating one number as a verdict.

Why Pairwise Agreement Uses All Observation Pairs

The denominator follows directly from the number of distinct unordered pairs. The first observation can be paired with \(n-1\) others, the second with \(n-2\) not already counted, and so on. Thus the total is \((n-1)+(n-2)+\cdots+1=n(n-1)/2\), which is \(\binom{n}{2}\). For each such pair, record one binary status in each run: together or apart. Agreement is the fraction with matching statuses.

\text{Pairwise agreement} = \frac{\text{pairs together in both}+\text{pairs apart in both}} {\binom{n}{2}}.

The derivation also explains the limitation: a pairwise statistic summarizes relationships among pairs, not the frequency with which whole partitions recur. Different partitions can have a respectable pairwise agreement without being identical.

Worked Example: Counting Pairwise Agreement Correctly

Six hypothetical policy records, labeled \(A\) through \(F\), are clustered in two runs with \(K=2\). Run 1 gives \(\{A,B,C\}\) and \(\{D,E,F\}\). Run 2 gives \(\{A,B\}\) and \(\{C,D,E,F\}\). Find the number and proportion of agreeing pairs. The method is to count pairs together in both runs and pairs apart in both; this avoids comparing arbitrary cluster labels.

There are \(\binom{6}{2}=6(5)/2=15\) pairs. The pair \(AB\) is together in both runs, giving 1 pair. The pairs \(DE, DF, EF\) are also together in both, giving 3 more. Pairs between \(A\) or \(B\) and any of \(D,E,F\) are apart in both; there are \(2(3)=6\) such pairs. Thus \(1+3+6=10\) pairs agree.

For a check, the five disagreements are \(AC\), \(BC\), \(CD\), \(CE\), and \(CF\). In the first run, \(A,B,C\) are together; in the second, \(C\) joins \(D,E,F\), so those five pairs change status. The count \(10+5=15\) accounts for all pairs.

\text{Pairwise agreement}=\frac{10}{15}=\frac{2}{3}=0.6667.

The result is \(0.6667\) to four decimal places. The common mistake is to count only \(AC\) and \(BC\) as disagreements, overlooking the three pairs between \(C\) and \(D,E,F\). The complete pair list provides a useful check.

WCSS and Stability Answer Different Questions

For a partition \(C_1,\ldots,C_K\), with observations \(x_i\) and cluster means \(\bar{x}_k\), WCSS is the sum of squared Euclidean distances from each observation to its assigned cluster mean. For the same data and \(K\), lower WCSS indicates a tighter fit to that criterion. It does not indicate how often the partition arises from different starts.

\operatorname{WCSS}=\sum_{k=1}^{K}\sum_{i\in C_k}\lVert x_i-\bar{x}_k\rVert^2.

Worked Example: A Lower WCSS Does Not Establish Stability

Consider the hypothetical one-dimensional observations \(0,1,2,8,9,10\) and \(K=2\). Two converged runs produce partitions \(P=\{0,1,2\},\{8,9,10\}\) and \(Q=\{0,1\},\{2,8,9,10\}\). Calculate each WCSS, then compare their fit and membership agreement. This example avoids the trap of treating the lowest WCSS as evidence that the solution recurs.

For \(P\), the first mean is \((0+1+2)/3=1\), and the second is \((8+9+10)/3=9\). The first cluster contributes \((0-1)^2+(1-1)^2+(2-1)^2=1+0+1=2\). The second contributes \((8-9)^2+(9-9)^2+(10-9)^2=1+0+1=2\). Therefore, \(\operatorname{WCSS}(P)=2+2=4\).

For \(Q\), the first mean is \((0+1)/2=0.5\), and its contribution is \((0-0.5)^2+(1-0.5)^2=0.25+0.25=0.5\). The second mean is \((2+8+9+10)/4=29/4=7.25\). Its contribution is \((2-7.25)^2+(8-7.25)^2+(9-7.25)^2+(10-7.25)^2\) \(=27.5625+0.5625+3.0625+7.5625=38.75\). Thus \(\operatorname{WCSS}(Q)=0.5+38.75=39.25\).

Run \(P\) has the lower WCSS. The partitions’ pairwise agreement is \(10/15=0.6667\), as counted in the previous calculation for the same membership pattern. This comparison says that \(P\) fits more tightly by WCSS and that the two runs are not identical. It does not tell us whether \(P\) is stable: that requires examining the outcomes across all the repeated starts, not just these two.

Summarizing a Set of Repeated Runs

A practical assessment should report several summaries, each with a clear interpretation. Exact recurrence measures how often the most common partition appears. Pairwise agreement can summarize the similarity of two runs or be averaged over all pairs of runs. WCSS summaries show the distribution of fit across starts, including the minimum and a typical value. If centroids are compared, first match the clusters across runs; a mere permutation of cluster labels is not a substantive change.

For a fixed data set, exactly identical memberships imply exactly identical arithmetic centroids, apart from numerical precision. When memberships differ, center comparisons can help describe the change, but they need context: which observations moved, how large the shifts are, and whether the cluster identities have been aligned. Centroid similarity alone can also conceal membership changes.

Worked Example: Combining Recurrence, Agreement, and WCSS

Five hypothetical starts are run on the six observations \(0,1,2,8,9,10\) with \(K=2\). Three starts produce partition \(P\) from the preceding example, each with WCSS 4; two produce partition \(Q\), each with WCSS 39.25. Calculate the most common partition’s recurrence, mean WCSS, and the average pairwise agreement across the ten pairs of runs.

Partition recurrence. The most frequent partition is \(P\), appearing in 3 of 5 runs. Its recurrence is \(3/5=0.6000\), or 60%.

Mean WCSS. The five WCSS values are \(4,4,4,39.25,39.25\). Their sum is \(3(4)+2(39.25)=12+78.5=90.5\), so the mean is \(90.5/5=18.1\). The minimum is 4, while the median is 4 because the ordered third value is 4.

Average agreement between runs. There are \(\binom{5}{2}=10\) pairs of runs. Three pairs compare two runs that both produced \(P\), and one pair compares two runs that both produced \(Q\); all 4 of these comparisons have agreement 1. The remaining \(3(2)=6\) pairs compare \(P\) with \(Q\), each with agreement \(10/15=2/3\). The average is \((4(1)+6(2/3))/10=(4+4)/10=0.8000\).

These summaries tell different parts of the story: the best WCSS is 4, but the most common partition occurs in only 60% of starts. The average run-pair agreement is 0.8000, higher than the direct two-partition agreement because some run pairs are exact matches. The common mistake is to report only the minimum WCSS and omit how frequently the corresponding partition occurs.

How to Interpret Stability in Practice

A repeated solution is evidence that the algorithm is finding a recurring structure under the specified setup. It is not proof that the clusters are objectively correct, represent natural populations, or will persist under different variables, scaling, or samples. Conversely, instability warns that the chosen \(K\) and data may admit materially different local solutions, but it does not by itself identify the cause.

A useful report states the number of starts, the fixed settings, how often each distinct partition occurred, and the WCSS distribution. Add a membership comparison when runs differ. If centers are included, state how clusters were matched across runs. When deciding whether a solution is sufficiently stable, use a threshold that makes sense for the analysis; there is no universal recurrence percentage that guarantees adequacy.

Hold the analysis fixed.
Use the same observations, variables, preprocessing, \(K\), distance measure, and stopping settings for every run.

Run multiple initializations.
Record each converged partition and its WCSS, rather than retaining only the run with the smallest WCSS.

Compare memberships.
Count exact partition recurrence and use a label-invariant measure such as pairwise agreement when partitions differ.

Interpret fit and recurrence together.
Report whether low-WCSS solutions recur and whether their memberships remain similar; do not treat either summary as a substitute for the other.

Common Mistakes

Calling the minimum-WCSS run stable. A minimum is a fit summary for one run; stability requires comparison across repeated starts.
Comparing cluster numbers literally. Labels can be permuted. Compare observation memberships or align clusters before comparing centers.
Counting only pairs that stay together. Pairwise agreement includes pairs that are apart in both runs as well as pairs together in both.
Changing the setup between runs. If the variables or scaling differ, the comparison no longer isolates initialization sensitivity.
Claiming stability proves the correct number of clusters. Stability is a diagnostic of reproducibility under a specified setup, not proof of a uniquely true grouping.

Key takeaway: Assess K-means stability by examining repeated partitions, not just the best objective value. Track recurrence, compare memberships without relying on cluster names, and interpret those results alongside WCSS.

Check Your Understanding

Use the definitions and counting methods above. Each problem concerns hypothetical data or runs.

Two runs cluster the same eight observations. How many distinct observation pairs are available for a pairwise agreement calculation? (Answer: \(\binom{8}{2}=28\) pairs.)
For five observations \(A,B,C,D,E\), run 1 gives \(\{A,B\},\{C,D,E\}\) and run 2 gives \(\{A,C\},\{B,D,E\}\). How many pairs agree, and what is their pairwise agreement? (Answer: 4 of 10 pairs; \(0.4000\).)
Six observations have partitions \(\{A,B,C\},\{D,E,F\}\) and \(\{A,B\},\{C,D,E,F\}\). How many pairs agree in together/apart status, and what is the pairwise agreement? (Answer: 10 of 15 pairs; \(10/15=0.6667\).)
Four starts produce WCSS values \(12,12,12,20\), and the three runs with WCSS 12 have the same partition. What is that partition’s recurrence, and what is the mean WCSS? (Answer: recurrence \(3/4=0.7500\); mean WCSS \((12+12+12+20)/4=14\).)
Two runs on the same four observations produce exactly the same two membership sets, but the reported center coordinates are listed in reverse cluster order. What is the partition agreement, and should this be counted as a membership disagreement? (Answer: agreement is 1; no, reversing cluster labels does not change the partition.)

What You'll Learn