Comparing Model-Based Clusters with External Labels

Why Compare Clusters With External Labels?

A clustering algorithm groups observations without using class labels as its target. Sometimes, however, labels are available from an independent source: a clinical diagnosis, a known species, or a previously defined category. Comparing the fitted clusters with those labels can describe how closely the two groupings align. It does not, by itself, establish that the labels are correct, that the clusters are meaningful, or that the fitted model can classify new observations.

The first practical issue is that cluster numbers have no intrinsic meaning. A fitted cluster called “1” could correspond closely to reference category “B,” while cluster “2” corresponds to “A.” A useful comparison must not depend on the arbitrary names assigned to groups. The contingency table records their overlap, and the adjusted Rand index summarizes agreement through pairs of observations.

Definition: Suppose the same \(n\) observations are assigned to a reference partition with groups \(R_1,\ldots,R_r\) and a fitted clustering with groups \(C_1,\ldots,C_s\). The contingency table has cell counts \(n_{ij}=|R_i\cap C_j|\), row totals \(a_i=\sum_j n_{ij}\), column totals \(b_j=\sum_i n_{ij}\), and grand total \(n\). Each observation must have one assignment in each partition for this table to compare the two groupings directly.

The reference categories and fitted clusters need not have the same number of groups. The table also does not require a one-to-one match between groups: a reference group may be split across several clusters, or a cluster may contain observations from several reference groups. The pattern of counts makes those cases visible.

Pairs of Observations and the Adjusted Rand Index

A pair is “together” in a partition if both observations belong to the same group, and “apart” if they belong to different groups. Let \(A\) be the number of unordered pairs together in both partitions. Let \(U\) be the number together in the reference partition, and \(B\) the number together in the fitted clustering. The total number of pairs is \(T=\binom{n}{2}\).

A=\sum_{i=1}^r\sum_{j=1}^s \binom{n_{ij}}{2}, \qquad U=\sum_{i=1}^r\binom{a_i}{2}, \qquad B=\sum_{j=1}^s\binom{b_j}{2}, \qquad T=\binom{n}{2}.

The unadjusted Rand index is the proportion of pairs on which the two partitions agree, counting pairs together in both and pairs apart in both. It can be high partly because many pairs may be apart under both partitions. The adjusted Rand index (ARI) instead compares the number of jointly grouped pairs with its expected value under a fixed-margin chance model.

Definition: For two partitions of the same \(n\) observations, their adjusted Rand index is

\operatorname{ARI} = \frac{A-\dfrac{UB}{T}} {\dfrac{1}{2}(U+B)-\dfrac{UB}{T}}, \qquad T=\binom{n}{2},

provided the denominator is nonzero. Here the chance expectation \(UB/T\) corresponds to randomly allocating observations to groups while holding both sets of group sizes fixed. If the denominator is zero, this formula is undefined; report that case rather than silently treating the quotient as an ordinary value.

Why the Chance Correction Has This Form

The fixed-margin model gives a precise interpretation to the adjustment. Imagine that the reference partition is fixed and the fitted partition is randomly assigned among all allocations with its observed group sizes. For each pair that is together in the reference partition, the probability that it is together in the random fitted partition is \(B/T\): among all \(T\) possible pairs, exactly \(B\) are together in that partition. Summing this probability over the \(U\) reference-together pairs gives the expected number together in both.

Theorem: Under uniform random allocation of the fitted labels subject to fixed column totals \(b_1,\ldots,b_s\), with the reference partition held fixed, \(E[A]=UB/T\). Consequently, whenever the ARI denominator is nonzero, the expected ARI under this fixed-margin model is zero.

Proof. For each unordered pair \(q\), let \(I_q=1\) if its observations are together in the reference partition and \(0\) otherwise. Let \(J_q=1\) if they are together in the randomly allocated fitted partition and \(0\) otherwise. Then \(A=\sum_q I_qJ_q\), and \(\sum_q I_q=U\). Because the fitted groups have fixed sizes, exactly \(B=\sum_j\binom{b_j}{2}\) of the \(T\) pairs are together in them. Uniform random allocation makes each pair equally likely to be one of those \(B\) pairs, so \(E[J_q]=B/T\). By linearity of expectation,

E[A] = \sum_q I_q E[J_q] = \sum_q I_q\frac{B}{T} = \frac{UB}{T}.

The quantities \(U\), \(B\), and \(T\) are fixed in this randomization model, so the ARI denominator is fixed as well. Taking the expectation of its numerator gives \(E[A]-UB/T=0\). Dividing by the nonzero denominator proves the stated expectation. \(\square\)

This is a particular chance model, not a claim that all ways of generating unrelated partitions produce the same expected agreement. The adjustment is useful because it accounts for the group sizes actually observed in the two partitions. It does not correct for biased reference labels, unrepresentative observations, or choices made after inspecting the labels.

Worked Calculations

Worked Example: Computing the ARI From a Two-Group Table

Suppose a reference classification and a clustering of 20 observations give this table:

	Cluster 1	Cluster 2	Row total
Reference A	8	2	10
Reference B	2	8	10
Column total	10	10	20

The jointly grouped pair count is \(A=2\binom{8}{2}+2\binom{2}{2}=2(28)+2(1)=58\). The reference-together and cluster-together counts are both \(U=B=2\binom{10}{2}=2(45)=90\), and \(T=\binom{20}{2}=190\). The fixed-margin expected jointly grouped count is \(UB/T=90\cdot90/190=810/19\).

Therefore,

\operatorname{ARI} = \frac{58-\frac{810}{19}}{90-\frac{810}{19}} = \frac{\frac{292}{19}}{\frac{900}{19}} = \frac{73}{225} \approx 0.324.

The positive value indicates more pairwise agreement than the fixed-margin chance expectation, but the agreement is far from perfect. In particular, each reference group is split between the two clusters.

Worked Example: Perfect Agreement Despite Different Label Names

Consider ten observations with a reference partition and clustering summarized by

	Cluster X	Cluster Y	Cluster Z
Reference A	4	0	0
Reference B	0	3	0
Reference C	0	0	3

Every reference group matches one cluster exactly, so \(A=U=B=\binom{4}{2}+\binom{3}{2}+\binom{3}{2}=6+3+3=12\). Also \(T=\binom{10}{2}=45\), and \(UB/T=144/45=16/5\). The numerator and denominator of the ARI are both \(12-16/5=44/5\), giving \(\operatorname{ARI}=1\). Renaming the clusters would not change this result: the table’s rows or columns can be permuted without changing any of the sums in the formula.

Worked Example: Pairwise Agreement and Classification Accuracy Differ

Suppose twelve observations produce this table:

	Cluster 1	Cluster 2	Row total
Reference A	5	1	6
Reference B	2	4	6
Column total	7	5	12

Here \(A=\binom{5}{2}+\binom{1}{2}+\binom{2}{2}+\binom{4}{2}=10+0+1+6=17\). The row totals give \(U=2\binom{6}{2}=30\), while the column totals give \(B=\binom{7}{2}+\binom{5}{2}=21+10=31\). Since \(T=\binom{12}{2}=66\), the chance expectation is \(UB/T=930/66=155/11\).

The ARI is

\operatorname{ARI} = \frac{17-\frac{155}{11}}{\frac{1}{2}(30+31)-\frac{155}{11}} = \frac{\frac{32}{11}}{\frac{361}{22}} = \frac{64}{361} \approx 0.177.

If one instead chose the one-to-one label mapping that maximizes the number of matching observations, the diagonal assignment shown here gives \(5+4=9\) matches out of 12, or \(75\%\). That accuracy is a different summary from the ARI: the ARI counts pairs, whereas this accuracy counts individual matches after choosing a mapping. Neither number is, by itself, evidence of how accurately a classifier predicts labels for new observations.

Agreement Is Not Predictive Classification

An external-label comparison is ordinarily a retrospective evaluation of two partitions of the same observations. The clustering assigns groups using its fitted unsupervised model; the reference labels supply a separate grouping for comparison. Calculating an ARI does not fit a rule that takes a new observation’s features and predicts its reference label. Nor does it establish that a particular cluster number has a stable meaning across independently fitted models.

Predictive classification asks a different question: can a procedure, trained using labeled observations, predict labels for observations not used to fit or select it? A predictive evaluation therefore needs an appropriate training and test design, a defined rule for assigning labels, and performance measured on held-out observations. If a mapping from cluster identities to reference categories is used for prediction, that mapping must be determined from training data, not chosen using the test outcomes.

The distinction matters even when the same table is used to calculate an apparent match rate. Maximizing a cluster-to-label mapping on the full data describes the best alignment of those observed groups; it does not validate a classifier. Likewise, a high ARI can reflect strong correspondence on the analyzed sample without demonstrating generalization, causal relevance, or clinical usefulness.

Interpretation and Common Pitfalls

Treating cluster numbers as meaningful labels. Cluster labels are arbitrary. Compare the table or an index invariant to row and column permutations, rather than demanding that “cluster 1” match “reference 1.”
Calling the ARI a percentage correct. It is a chance-adjusted pairwise index, not the fraction of observations assigned to the “right” cluster. State the index and the comparison being made.
Assuming the reference is unquestionable truth. Reference labels can be noisy, incomplete, or defined for a different purpose. The ARI measures agreement with those labels, not their validity.
Interpreting zero as proof of independence. Zero is the expectation under the specified fixed-margin randomization model. A realized ARI near zero is not a general test establishing independence or absence of scientifically useful structure.
Using agreement as evidence of prediction. Same-sample agreement is not held-out classification performance. A prediction claim requires a separate predictive procedure and evaluation design.

Key takeaway: Use the contingency table to inspect how reference groups and fitted clusters overlap, and the ARI to summarize their pairwise agreement relative to a fixed-margin chance model. Interpret both as external agreement measures, not as substitutes for predictive validation.

Check Your Understanding

Answer each question using the definitions and calculations above.

What does a cell count \(n_{ij}\) represent, and what are the row and column totals used for?
Why does the fixed-margin chance expectation for the number of jointly grouped pairs equal \(UB/T\)?
Suppose the rows and columns of a contingency table are permuted. Which quantities in the ARI formula change, and why does the ARI remain the same?
Why is a label-matched accuracy calculated on the clustering sample not automatically a measure of predictive classification performance?
What should be reported if the denominator in the ARI formula is zero?