ARI / NMI in Machine Learning

The Problem with Naive Clustering Evaluation

Imagine you cluster 1000 customers into 5 segments using K-means, and you happen to know the true customer segments from manual labeling by your marketing team. You want to know: did K-means recover the true structure? The simplest approach is the Rand Index (RI), proposed by William Rand in 1971. It counts all pairs of data points and checks whether the clustering and the ground truth agree -- both say they're in the same group, or both say they're in different groups. Divide agreements by total pairs, and you get a number between 0 and 1.

Sounds reasonable, right? Here's the catch: even a completely random clustering will agree with the ground truth on a large fraction of pairs, especially when clusters are roughly equal in size. For 1000 points in 5 balanced clusters, a random labeling will score an RI of approximately 0.8 -- which looks deceptively good. This is the chance agreement problem, and it plagued clustering evaluation throughout the 1970s.

Hubert and Arabie's Fix: The Adjusted Rand Index

In 1985, Lawrence Hubert and Phipps Arabie published their landmark paper "Comparing Partitions" in the Journal of Classification. Their key insight was simple but powerful: subtract the expected Rand Index under a random model (the generalized hypergeometric distribution), then normalize so that the maximum score is 1. This gives you the Adjusted Rand Index (ARI).

With ARI, random clusterings score near 0 regardless of the number of clusters or data points. Perfect agreement still scores 1. And -- critically -- clusterings that are worse than random can score negative, down to approximately -0.5 for maximally discordant partitions. This chance correction made ARI the gold standard for pair-counting-based clustering evaluation, recommended by Milligan and Cooper (1986) as the preferred external validation measure.

The Information-Theoretic Alternative: NMI

Meanwhile, information theorists had a different toolkit. If you think of cluster labels and class labels as random variables, their mutual information tells you how much knowing one reduces your uncertainty about the other. The problem: raw mutual information grows with the number of clusters, making it hard to compare across different values of k.

Normalized Mutual Information (NMI) solves this by dividing by a normalizer -- typically the arithmetic or geometric mean of the two entropies. This bounds the score between 0 (no shared information) and 1 (perfect agreement). Fred and Jain (2003) popularized NMI for clustering evaluation, and it became the standard information-theoretic companion to ARI.

However, NMI has its own subtlety: it's not corrected for chance. Vinh, Epps, and Bailey showed in their influential 2010 JMLR paper that NMI can produce inflated scores when the number of clusters is large relative to the number of data points. This led to the development of Adjusted Mutual Information (AMI), which applies Hubert-Arabie-style chance correction to the mutual information framework.

Why Both Survive

Why do practitioners still use both ARI and NMI instead of picking one? Because they capture subtly different aspects of clustering quality. ARI is based on pairwise agreement -- do the two labelings put the same pairs together? NMI is based on information content -- how much does one labeling tell you about the other? These perspectives are complementary, and they can diverge when clusters have very different sizes or when the number of clusters differs between prediction and ground truth.

Key Insight: ARI and NMI exist because the naive Rand Index inflates scores for random clusterings. ARI fixes this with combinatorial chance correction; NMI uses information-theoretic normalization. Together, they provide a robust, complementary evaluation of clustering quality.

The Pair-Counting Intuition (ARI)

Here's the simplest way to think about ARI. Take every pair of data points in your dataset. For each pair, ask two questions:

1. Does your clustering put them in the same cluster?
2. Does the ground truth put them in the same class?

If both answers agree -- both say "same" or both say "different" -- that's a concordant pair. If they disagree, that's a discordant pair. The raw Rand Index is just the fraction of concordant pairs.

Now imagine a lazy colleague who assigns cluster labels by throwing darts at a board. Even this random clustering will produce a bunch of concordant pairs by accident -- especially the "both say different" pairs, which dominate when there are many clusters. The Adjusted Rand Index subtracts out this expected agreement. What's left is the genuine agreement beyond chance.

Think of it like grading an exam on a curve. If the average student scores 60% by guessing, a student who scores 80% hasn't really demonstrated 80% knowledge -- they've demonstrated performance that's 20 percentage points above the baseline. ARI does the same thing for clustering: it measures how much better your clustering is than random, normalized so that perfect agreement = 1.

The Information Theory Intuition (NMI)

Now think about NMI from a completely different angle. Imagine you're playing 20 Questions to guess the true class of a data point. You get to ask one question: "What cluster is it in?" How much does the answer help?

If the clusters perfectly correspond to classes, knowing the cluster tells you exactly the class -- maximum information gain. If clusters are randomly shuffled relative to classes, knowing the cluster tells you nothing -- zero information gain. NMI quantifies this: what fraction of the uncertainty about the true class is resolved by knowing the cluster assignment?

The normalization is key. Raw mutual information in bits depends on the number of clusters and classes, making comparisons unfair. Dividing by the average entropy puts everything on a 0-to-1 scale where 0 means "clusters are useless for predicting classes" and 1 means "clusters perfectly predict classes."

When They Disagree

Here's something practitioners learn the hard way: ARI and NMI can disagree, and when they do, it's informative. ARI is strict about the number of clusters. If the ground truth has 5 classes and you predict 50 micro-clusters (each containing only one class), NMI can be very high (each micro-cluster is pure), but ARI will be lower (too many splits). Conversely, if you merge several classes into one big cluster, NMI penalizes the information loss but ARI might not drop as dramatically.

The takeaway: ARI cares about exact partition match, NMI cares about information preservation. Report both, and investigate when they diverge.

Mental Model: ARI is like a strict math teacher who checks if every pair of students is seated correctly. NMI is like a librarian who checks if knowing the shelf number tells you the book's genre. Both are valid, complementary perspectives on the same question: did your clustering find the real structure?

Contingency Table Foundation

Let $U = \{U_1, \ldots, U_R\}$ and $V = \{V_1, \ldots, V_C\}$ be two partitions of $n$ data points into $R$ and $C$ clusters respectively. The contingency table $\mathbf{N}$ has entries:

$n_{ij} = |U_i \cap V_j|$

with row sums $a_i = \sum_j n_{ij}$ and column sums $b_j = \sum_i n_{ij}$.

Rand Index (RI)

The Rand Index counts pairwise agreements:

$\text{RI}(U, V) = \frac{\binom{n}{2} - \frac{1}{2}\left(\sum_i a_i^2 + \sum_j b_j^2\right) + \sum_{i,j} n_{ij}^2}{\binom{n}{2}}$

Equivalently, RI = (number of concordant pairs) / (total pairs), where concordant pairs are those assigned to the same group in both $U$ and $V$, or to different groups in both.

Adjusted Rand Index (ARI)

The ARI corrects for chance using the generalized hypergeometric distribution as the null model:

$\text{ARI} = \frac{\sum_{ij} \binom{n_{ij}}{2} - \left[\sum_i \binom{a_i}{2} \cdot \sum_j \binom{b_j}{2}\right] / \binom{n}{2}}{\frac{1}{2}\left[\sum_i \binom{a_i}{2} + \sum_j \binom{b_j}{2}\right] - \left[\sum_i \binom{a_i}{2} \cdot \sum_j \binom{b_j}{2}\right] / \binom{n}{2}}$

This has the general form:

$\text{ARI} = \frac{\text{Index} - \text{Expected Index}}{\text{Maximum Index} - \text{Expected Index}}$

Properties of ARI:

• $\text{ARI} = 1$ when $U = V$ (up to permutation)
• $\mathbb{E}[\text{ARI}] = 0$ under the null hypothesis of random labeling
• $\text{ARI} \in [-0.5, 1]$ in theory; practical lower bound depends on partition structure
• Symmetric: $\text{ARI}(U, V) = \text{ARI}(V, U)$
• Permutation invariant: renaming cluster labels does not change the score

Mutual Information

Define the entropies and mutual information:

$H(U) = -\sum_{i=1}^R \frac{a_i}{n} \log \frac{a_i}{n}, \quad H(V) = -\sum_{j=1}^C \frac{b_j}{n} \log \frac{b_j}{n}$

$I(U; V) = \sum_{i=1}^R \sum_{j=1}^C \frac{n_{ij}}{n} \log \frac{n \cdot n_{ij}}{a_i \cdot b_j}$

Normalized Mutual Information (NMI)

NMI normalizes mutual information using one of several strategies:

Arithmetic mean (default in scikit-learn >= 0.22): $\text{NMI}_{\text{arith}}(U, V) = \frac{2 \cdot I(U; V)}{H(U) + H(V)}$

Geometric mean (original Strehl-Ghosh formulation): $\text{NMI}_{\text{geom}}(U, V) = \frac{I(U; V)}{\sqrt{H(U) \cdot H(V)}}$

Min normalization: $\text{NMI}_{\text{min}}(U, V) = \frac{I(U; V)}{\min(H(U), H(V))}$

Max normalization: $\text{NMI}_{\text{max}}(U, V) = \frac{I(U; V)}{\max(H(U), H(V))}$

Properties of NMI:

• $\text{NMI} \in [0, 1]$ for all normalization variants
• $\text{NMI} = 1$ when $U = V$ (up to permutation)
• $\text{NMI} = 0$ when $U$ and $V$ are independent
• Symmetric: $\text{NMI}(U, V) = \text{NMI}(V, U)$
• Not adjusted for chance: can be inflated when $R \cdot C$ is large relative to $n$

V-Measure: Decomposing NMI

V-measure (Rosenberg and Hirschberg, 2007) decomposes the information-theoretic evaluation into two intuitive components:

Homogeneity: Each cluster contains only members of a single class. $h = 1 - \frac{H(V|U)}{H(V)}$

Completeness: All members of a given class are assigned to the same cluster. $c = 1 - \frac{H(U|V)}{H(U)}$

V-measure: The harmonic mean of homogeneity and completeness: $V = \frac{2 \cdot h \cdot c}{h + c}$

Note that V-measure with equal weighting is equivalent to $\text{NMI}_{\text{arith}}$.

Complexity Analysis

For $n$ data points with $R$ and $C$ clusters:

• ARI: $O(n + R \cdot C)$ using the contingency table approach
• NMI: $O(n + R \cdot C)$ similarly via contingency table
• Space: $O(R \cdot C)$ for the contingency table

Both are efficient even for $n > 1$M, as $R \cdot C$ is typically small (e.g., $R, C < 100$).

ARI (Adjusted Rand Index) and NMI (Normalized Mutual Information) are the two most widely used external clustering evaluation metrics, forming a complementary pair that captures different facets of clustering quality. ARI, introduced by Hubert and Arabie (1985), uses pair-counting with chance correction to measure agreement between a predicted clustering and ground truth labels. Its chance correction ensures random clusterings score near 0, making it a principled metric for clustering comparison. NMI, rooted in information theory, measures how much information the cluster assignments carry about the true class labels, normalized to a [0, 1] scale.

The key distinction practitioners must understand: ARI is corrected for chance, NMI is not. This means NMI can be inflated when comparing clusterings with many clusters relative to the data size. For this reason, Adjusted Mutual Information (AMI) was developed as a chance-corrected alternative, and should be preferred when comparing algorithms that produce very different numbers of clusters. V-measure (Rosenberg and Hirschberg, 2007) provides a useful decomposition of NMI into homogeneity (cluster purity) and completeness (class coverage), offering diagnostic insight beyond a single score.

In practice, report both ARI and NMI for robust evaluation. When they agree, your assessment is reliable. When they diverge -- typically NMI high and ARI moderate -- investigate over-splitting (many pure but fragmented clusters). Both metrics are computationally efficient at $O(n + R \cdot C)$, requiring only a contingency table and basic arithmetic. They are standard in academic literature across computer science, bioinformatics, and social network analysis. The main limitation is that both require ground truth labels, restricting them to development-time validation. In production, switch to internal metrics (Silhouette, Davies-Bouldin) for monitoring, but use the ARI/NMI evaluation during development to establish that your internal metrics are tracking genuine cluster quality.