Extrinsic Evaluation: Purity, ARI, and NMI

What Is Extrinsic Evaluation?

Extrinsic evaluation requires ground truth labels (gold-standard annotations). It measures how well the discovered clusters match the known true classes. There is no requirement that cluster labels match class label numbers; only that points from the same class tend to end up in the same cluster.

Purity

How It Works

1. For each discovered cluster, find the majority true class among its members.
2. Sum the counts of majority-class members across all clusters.
3. Divide by the total number of points:

$\text{Purity} = \frac{1}{N} \sum_{k=1}^{K} \max_{c} |C_k \cap T_c|$

where $C_k$ is the set of points in discovered cluster $k$, and $T_c$ is the set of points with true class $c$.

Range and Interpretation

Purity ranges from 0 to 1, with 1 being perfect. Higher is better.

Critical Flaw

Purity is misleading. The trivial clustering where every point is its own singleton cluster achieves purity = 1 (each “cluster” has exactly one point, so the majority class is trivially 100%). This “perfect” score is meaningless. Purity rewards fragmentation; it does not penalise splitting true classes across multiple clusters.

Adjusted Rand Index (ARI)

How It Works

ARI considers every pair of points. For each pair, both the true labels and the discovered clustering either place the pair in the same group or different groups. This produces a 2x2 contingency table of agreements/disagreements. ARI corrects for the number of agreements expected by chance (much like Cohen’s $\kappa$):

$\text{ARI} = \frac{\text{RI} - \text{Expected RI}}{\text{Max RI} - \text{Expected RI}}$

Range and Interpretation

ARI ranges from $-1$ to $1$:

• $1$: perfect match with ground truth.
• $0$: no better than random chance.
• $-1$: worse than random.

ARI is interpretable much like Cohen’s $\kappa$: it is chance-corrected and does not reward singleton clusters.

Normalised Mutual Information (NMI)

How It Works

NMI is information-theoretic. It measures how much knowing the discovered cluster assignment reduces uncertainty about the true class (mutual information), normalised to the range $[0, 1]$:

$\text{NMI}(C, T) = \frac{I(C; T)}{\frac{1}{2}[H(C) + H(T)]}$

where $I(C; T)$ is mutual information between cluster assignments $C$ and true classes $T$, and $H$ is entropy. The denominator uses the arithmetic mean of the two entropies (other normalisation variants exist; the course does not require memorising the exact normalisation denominator).

Range and Interpretation

NMI ranges from 0 to 1, with 1 being perfect. NMI = 0 means the clustering tells you nothing about the true class (statistical independence).

Why NMI Is Preferred in MLRD

NMI handles chance correctly and does not reward singleton clusters (splitting each point into its own cluster gives NMI near 0, not 1). It is the MLRD course’s recommended extrinsic metric for this reason.

Comparison Table

Metric	Range	Chance-Corrected?	Penalises Over-Fragmentation?	Best For
Purity	$[0, 1]$	No	No (rewarded by it)	Quick sanity check only
ARI	$[-1, 1]$	Yes	Yes	Balanced accuracy-like measure
NMI	$[0, 1]$	Yes	Yes	Preferred MLRD metric

Worked Example

Suppose we have 6 points with true classes: $T = [A, A, A, B, B, B]$. Discovered clustering gives $C = [1, 1, 2, 2, 2, 2]$.

Purity

• Cluster 1 contains: $[A, A, B]$ → majority class A, count = 2.
• Cluster 2 contains: $[A, B, B, B]$ → majority class B, count = 3.

$\text{Purity} = \frac{2 + 3}{6} = \frac{5}{6} \approx 0.83$

Why Purity Fails

If we instead had $C = [1, 2, 3, 4, 5, 6]$ (six singleton clusters), purity would be $\frac{1+1+1+1+1+1}{6} = 1$. This is the best possible purity score for the worst possible clustering. By contrast, both ARI and NMI would be near zero for singleton clusters.

Summary

Aspect	Detail
Purity	Majority-class accuracy; flawed (rewards singletons)
ARI	Pairwise agreement corrected for chance; $[-1, 1]$
NMI	Information-theoretic; $[0, 1]$; preferred MLRD metric
Extrinsic requirement	Ground truth labels must exist
Key distinction	Intrinsic = no labels needed; Extrinsic = labels required

Past paper questions: y2024p3q7e