Why Cluster Labels Can Switch
A k-means solution assigns each observation to one of \(K\) clusters and represents each cluster by its centroid. The numbers attached to the clusters are bookkeeping labels: “cluster 1” has no inherent meaning that makes it the same cluster in another run. Different initial centroids, a different ordering of output, or another fitted solution may attach different numbers to the same groups of observations.
This matters when comparing cluster profiles. A direct comparison of cluster 1 in two outputs may compare different groups, while the same group may have been called cluster 3 in the second output. Before interpreting a change in a profile, first match the clusters using their memberships or centroids. This tutorial concerns that matching step, not how to choose the number of clusters.
For observations \(x_1,\ldots,x_n\), write \(z_i\) for the label assigned to observation \(i\), and \(\mu_k\) for the centroid of cluster \(k\). The k-means within-cluster sum of squares (WCSS) is
A centroid is the mean feature vector of the observations assigned to its cluster. In this formula, the label \(z_i\) selects the centroid used for observation \(i\); changing the label name does not change the observation or the centroid it is paired with.
Why Relabeling Does Not Change the Solution
Let \(\pi\) be any permutation of the labels \(1,\ldots,K\). Relabel every observation by \(z'_i=\pi(z_i)\), and give the newly named cluster \(j\) the old centroid \(\mu_{\pi^{-1}(j)}\). Then the centroid assigned to observation \(i\) after relabeling is \(\mu_{\pi^{-1}(z'_i)}=\mu_{\pi^{-1}(\pi(z_i))}=\mu_{z_i}\). Consequently, each squared distance in the WCSS is unchanged, so the total is unchanged as well.
This is why cluster numbers cannot be compared as if they were stable identities. It is the partition and its estimated profiles that carry information, not whether a software output used the number 1 or 2.
Matching by Membership Overlap
When two runs use the same \(n\) observations and the same \(K\), a useful first step is a contingency table. Put the clusters from the first run in rows and the clusters from the second run in columns. Each cell records how many observations belong to that row cluster in the first run and that column cluster in the second. A large cell indicates substantial overlap.
If the goal is a one-to-one alignment, choose a pairing of rows and columns that maximizes the total number of observations in the paired cells. For a proposed pairing, add the selected cell counts. For small \(K\), the possible pairings can be checked directly. For larger \(K\), an assignment algorithm, such as the Hungarian algorithm, finds the maximum-total pairing. Importantly, this procedure aligns labels; it does not make the two partitions identical.
Worked Example: Same Partition, Different Numbers
A hypothetical insurer’s two k-means runs cluster the same eight policy records into three groups. Run A labels the groups A1, A2, and A3; Run B uses B1, B2, and B3. The contingency table is:
| B1 | B2 | B3 | Run A total | |
|---|---|---|---|---|
| A1 | 0 | 0 | 3 | 3 |
| A2 | 0 | 3 | 0 | 3 |
| A3 | 2 | 0 | 0 | 2 |
| Run B total | 2 | 3 | 3 | 8 |
Step 1: Find the overlaps. A1 shares all 3 of its records with B3. A2 shares all 3 with B2. A3 shares both of its records with B1.
Step 2: Choose the alignment. Pair A1 with B3, A2 with B2, and A3 with B1. The total matched count is \(3+3+2=8\), which is the full number of records.
Step 3: Interpret the result. Every record is in the same group in both runs, so the partitions are identical. The label correspondence is A1 to B3, A2 to B2, and A3 to B1—not A1 to B1, A2 to B2, and A3 to B3. The method avoids the common mistake of interpreting a label change as a change in the groups.
Check: The row totals \(3+3+2\) and column totals \(2+3+3\) both sum to 8, as required.
Imperfect Matches: Overlap Is Not Identity
With different initializations, two runs may produce partitions that are not identical. The contingency table still helps, but a matched pair should not be described as “the same cluster” without checking how much membership overlaps. One simple measure for a pair of clusters is the Jaccard similarity:
Here \(A\) and \(B\) are sets of observations, \(|A|\) and \(|B|\) are their sizes, and \(|A\cap B|\) is their shared membership. The measure is 1 for identical membership and 0 for no shared observations. It can help describe a pair, while the maximum-overlap assignment provides a convenient one-to-one alignment. Neither removes the need to examine the actual memberships.
Worked Example: Choosing the Best One-to-One Alignment
Two hypothetical runs classify 12 claim records into three clusters. Their membership counts are:
| B1 | B2 | B3 | Run A total | |
|---|---|---|---|---|
| A1 | 3 | 1 | 1 | 5 |
| A2 | 1 | 2 | 1 | 4 |
| A3 | 0 | 1 | 2 | 3 |
| Run B total | 4 | 4 | 4 | 12 |
Step 1: Evaluate the leading alignment. Pair A1 with B1, A2 with B2, and A3 with B3. The matched count is \(3+2+2=7\).
Step 2: Check whether a competing pairing is better. If A1 is paired with B1, the best remaining choice is A2 with B3 and A3 with B2, giving \(3+1+1=5\). If A1 is paired with B2, the largest possible total is \(1+1+2=4\). If A1 is paired with B3, the largest possible total is \(1+2+1=4\). Thus the first alignment, with total 7, is optimal.
Step 3: Describe the strength of the matches. For A1 and B1, the intersection is 3, and the union is \(5+4-3=6\), so \(J=3/6=0.5000\). For A2 and B2, \(J=2/(4+4-2)=2/6=0.3333\). For A3 and B3, \(J=2/(3+4-2)=2/5=0.4000\). These are partial matches, not identical groups.
Check: The aligned pairs contain 7 of the 12 observations in common. Their Jaccard similarities are all below 1, confirming that matching labels has not made the partitions equal. The common mistake here is to call the optimal alignment a perfect match simply because it has the largest overlap.
Matching by Centroids
Centroids offer another way to align clusters, especially when the main interest is in comparing cluster profiles. Compare centroids only when their coordinates refer to the same features on the same scale. If one run used standardized features and another used original units, first express both sets of centroids in a common feature space. Otherwise, a distance can reflect different units rather than different cluster locations.
For centroids \(\mu_k\) and \(\nu_\ell\) represented in the same \(p\)-dimensional space, their Euclidean distance is \(\sqrt{\sum_{j=1}^{p}(\mu_{kj}-\nu_{\ell j})^2}\). A one-to-one centroid alignment can minimize the total distance over possible pairings. This is a different matching criterion from maximizing membership overlap, and the two approaches need not produce the same pairing. Use the criterion that best serves the comparison, and inspect membership or profiles if the choice is ambiguous.
Worked Example: Aligning Two Sets of Centroids
Suppose two runs have two clusters each, described by the same two standardized features. Run P has centroids P1 \(=(1,2)\) and P2 \(=(5,2)\). Run Q has Q1 \(=(5.2,2.1)\) and Q2 \(=(0.9,2.2)\). Find the minimum-distance one-to-one alignment.
Step 1: Calculate all four distances. The distance from P1 to Q1 is \(\sqrt{(1-5.2)^2+(2-2.1)^2}=\sqrt{17.64+0.01}=\sqrt{17.65}\approx4.2012\). The distance from P1 to Q2 is \(\sqrt{(1-0.9)^2+(2-2.2)^2}=\sqrt{0.01+0.04}=\sqrt{0.05}\approx0.2236\).
The distance from P2 to Q1 is \(\sqrt{(5-5.2)^2+(2-2.1)^2}=\sqrt{0.04+0.01}=\sqrt{0.05}\approx0.2236\). The distance from P2 to Q2 is \(\sqrt{(5-0.9)^2+(2-2.2)^2}=\sqrt{16.81+0.04}=\sqrt{16.85}\approx4.1049\).
Step 2: Compare one-to-one assignments. Pairing P1 with Q2 and P2 with Q1 gives a total distance of \(0.2236+0.2236=0.4472\). The other pairing gives approximately \(4.2012+4.1049=8.3061\). Therefore the minimum-distance alignment is P1 to Q2 and P2 to Q1.
Check: Both matched distances are small compared with the cross-pair distances. The common mistake is to pair clusters with the same number; P1 to Q1 and P2 to Q2 would be the much worse alignment here. The distances are rounded to four decimal places.
When the Number of Clusters Differs
If two solutions use different values of \(K\), a full one-to-one matching is impossible: at least one cluster must be left unmatched. More importantly, a cluster in one solution may correspond to several clusters in the other. That can happen when a group is split, or when groups are combined. Do not force a single matched label to imply a complete correspondence.
In this setting, use the contingency table to identify overlaps and describe the pattern. Centroid distances can add context, provided the features are comparable, but they do not establish that two clusters contain the same observations. State whether the evidence suggests a close match, a split, a merge, or a substantially different allocation.
Worked Example: Recognizing a Split Across Different K Values
Run A places 11 hypothetical policyholders into two groups. Run B places the same records into three groups. Their overlap table is:
| B1 | B2 | B3 | Run A total | |
|---|---|---|---|---|
| A1 | 5 | 0 | 0 | 5 |
| A2 | 0 | 3 | 3 | 6 |
| Run B total | 5 | 3 | 3 | 11 |
Step 1: Read the overlaps. All five observations in A1 are in B1. The six observations in A2 are divided evenly: three are in B2 and three are in B3.
Step 2: Describe the correspondence. A1 corresponds exactly to B1, while A2 corresponds to the combined membership of B2 and B3. There is no one-to-one matching that expresses both relationships at once, because A2 overlaps with two B clusters.
Step 3: Avoid overinterpreting the labels. It would be misleading to call B2 or B3 “the” match for A2 and ignore the other half. The membership evidence indicates a split of A2 in the three-cluster solution. This describes how the allocations relate; it does not by itself say which value of \(K\) is preferable.
Check: The table totals \(5+3+3=11\), and the observations in A2 total \(3+3=6\), so the reported split accounts for every record in A2.
Common Mistakes and Practical Checks
- Comparing the same number across runs. A1 and B1 need not be related. Match first, then compare the aligned profiles.
- Calling the best alignment identical. Maximum overlap is relative to the available pairings. Check the overlap counts or a measure such as Jaccard similarity before claiming the memberships agree.
- Comparing centroids in incompatible units. A distance between centroids is meaningful only when both are expressed in the same feature space and scale.
- Forcing a one-to-one match when \(K\) differs. Describe a split, merge, or unmatched cluster where that is what the memberships show.
- Treating alignment as evidence of a preferred solution. Matching is a comparison device; it does not decide which clustering is more useful.
Check Your Understanding
For each problem, find the label correspondence or describe the limitation before interpreting cluster identity.
- Two runs each have three clusters. Their overlap table, with Run A as rows and Run B as columns, is \(\begin{pmatrix}0&4&0\\2&0&0\\0&0&3\end{pmatrix}\). Give the matching and state whether the partitions are identical. (Answer: A1–B2, A2–B1, A3–B3; identical partitions.)
- For two three-cluster runs, the overlap table is \(\begin{pmatrix}3&1&0\\0&2&2\\1&0&2\end{pmatrix}\). Find a maximum-overlap one-to-one alignment and its matched total. (Answer: A1–B1, A2–B2, A3–B3; total overlap 7.)
- Two two-dimensional centroid sets are P1 \(=(1,2)\), P2 \(=(5,2)\), and Q1 \(=(5.2,2.1)\), Q2 \(=(0.9,2.2)\). Which pairing minimizes total Euclidean distance, and what is that total to four decimals? (Answer: P1–Q2 and P2–Q1; total distance \(2\sqrt{0.05}\approx0.4472\).)
- A two-cluster solution and a three-cluster solution have overlap table \(\begin{pmatrix}5&0&0\\0&3&3\end{pmatrix}\). Describe the correspondence without forcing a complete one-to-one match. (Answer: The first cluster corresponds exactly to B1; the second cluster is split evenly between B2 and B3.)
- Two runs have overlap table \(\begin{pmatrix}4&1\\2&3\end{pmatrix}\). Compare the direct pairing (A1–B1, A2–B2) with the crossed pairing and give the maximum matched count. (Answer: Direct pairing gives \(4+3=7\); crossed gives \(1+2=3\); the maximum is 7.)