Put each of the textbook's seventeen documents in a cluster of its own, and the Rand index is 0.676. That is exactly the score of the clustering the textbook examines, which groups the documents sensibly into three. How can a measure tell a real clustering from one that earns its score for nothing? It can subtract what a random clustering with the same cluster sizes would score, and report only the excess. Measures built that way give the singletons 0.
A measure corrected for chance has two properties. Its expected value is 0 for a clustering unrelated to the classes, and it is 1 when the clusters are the classes. The two in common use are the adjusted Rand index and adjusted mutual information. They correct the Rand index and the mutual information that evaluating clusterings defines, and this article assumes that one.
Here is the route. First we derive the adjusted Rand index from a chance model and compute it on the seventeen documents. Then we apply the same correction to mutual information. Next we feed every external measure clusterings that should score badly: singletons, a single cluster, and random ones. Finally we follow the measures on Reuters as the number of clusters grows from 2 to 50, and solve one problem in full.
The running example is the one of evaluating clusterings: seventeen documents of Manning, Raghavan, and Schütze (2008, §16.3) in three classes of 8, 5 and 4 (written x, o and ◇) and three clusters of 6, 6 and 5. That article computes the quantities used below. Of the $\binom{17}{2} = 136$ pairs of documents, 40 share a cluster and 44 share a class. The pair counts are $TP = 20$, $FP = 20$, $FN = 24$ and $TN = 72$, and the Rand index is $92/136 = 0.676$. The mutual information is $I = 0.3919$ nats, the entropies are $H(\Omega) = 1.0951$ and $H(C) = 1.0551$ with mean 1.0751, and NMI is 0.365. Purity is 0.706, $F_1$ is 0.476 and $F_5$ is 0.456.
The adjusted Rand index
The Rand index gives credit for agreement that would happen anyway. The fix is to count how many true positives a clustering has beyond what chance would give. Here is the idea in plain words: leave the clusters as they are, deal the class labels out again at random, and count the same-cluster pairs that share a class on average.
The chance model. Hubert and Arabie (1985) fix both sets of sizes, the cluster sizes $n_k$ and the class sizes $n_j$. Every way of dealing the $N$ class labels to the $N$ documents is taken as equally likely; in the example the labels are eight x, five o and four ◇. This is the hypergeometric model of a contingency table with fixed margins: only the cells $n_{kj}$ vary.
The expectation. Take any one pair of documents, and count the $N$ labels as $N$ separate tokens. The two labels dealt to the pair are equally likely to be any of the $\binom{N}{2}$ pairs of tokens, and $\binom{n_j}{2}$ of those pairs are two labels of class $j$. So the pair shares a class with probability
$$\frac{\sum_j \binom{n_j}{2}}{\binom{N}{2}} = \frac{TP + FN}{\binom{N}{2}} = \frac{44}{136},$$
the overall fraction of same-class pairs. TP counts the same-cluster pairs that share a class, and there are always $\sum_k \binom{n_k}{2} = 40$ same-cluster pairs, because the clusters do not change. An expectation of a sum is the sum of the expectations, whether or not the pairs are independent, so
$$E[TP] = \frac{(TP + FP)(TP + FN)}{\binom{N}{2}} = \frac{40 \times 44}{136} = 12.94.$$
The script confirms this in two ways. Under the model, each cell $n_{kj}$ follows a hypergeometric distribution, and summing $\binom{x}{2}$ over those distributions for the nine cells gives 12.94. On a table of five documents, averaging TP over all 120 deals gives the formula's value exactly.
The index. The example's 20 true positives exceed the expectation by 7.06. To put this on a scale whose top is 1, divide by the largest excess allowed for. TP cannot exceed either the 40 same-cluster pairs or the 44 same-class pairs. Hubert and Arabie take the maximum to be the average of the two, 42. The adjusted Rand index is then
$$\mathrm{ARI} = \frac{TP - E[TP]}{\tfrac{1}{2}\left[(TP + FP) + (TP + FN)\right] - E[TP]} = \frac{20 - 12.94}{42 - 12.94} = \frac{7.06}{29.06} = 0.243.$$
Why the average of the two maxima. That choice makes the ARI exactly the Rand index corrected for chance, $(\mathrm{RI} - E[\mathrm{RI}])/(1 - E[\mathrm{RI}])$. To see it, write $A = TP + FP$ for the same-cluster pairs, $B = TP + FN$ for the same-class pairs and $T = \binom{N}{2}$. The errors are $FP = A - TP$ and $FN = B - TP$, so
$$\mathrm{RI} = 1 - \frac{FP + FN}{T} = 1 - \frac{A + B - 2\,TP}{T}.$$
$A$, $B$ and $T$ are fixed by the model, so $E[\mathrm{RI}] = 1 - (A + B - 2E[TP])/T$. Subtracting,
$$\frac{\mathrm{RI} - E[\mathrm{RI}]}{1 - E[\mathrm{RI}]} = \frac{2\,(TP - E[TP])/T}{(A + B - 2E[TP])/T} = \frac{TP - E[TP]}{\tfrac{1}{2}(A + B) - E[TP]} = \mathrm{ARI}.$$
In the example $E[\mathrm{RI}] = 1 - (84 - 25.88)/136 = 0.5727$, and $(0.6765 - 0.5727)/(1 - 0.5727) = 0.243$ again.
The denominator is positive except in two degenerate cases. Since $A \le T$ and $B \le T$, $E[TP] = AB/T \le \min(A, B) \le \tfrac{1}{2}(A + B)$. Equality throughout needs $A = B$ and $AB/T = A$, that is, $A = B = T$ (one cluster and one class) or $A = B = 0$ (every cluster and every class a single document). In those two cases the ARI is undefined. In every other case the denominator is positive, and the properties below hold.
Three properties follow. The ARI is 1 exactly when the Rand index is 1, that is, when the clusters are the classes. Its expected value under the chance model is exactly 0, because the numerator has expectation 0 and the denominator is constant. It is negative when a clustering has fewer true positives than chance gives.
The value 0.243 is the same that scikit-learn's implementation returns for this table. It is much lower than the Rand index of 0.68. Most of the Rand index's credit here was for the 72 true negatives, which a random clustering of the same sizes would also earn in large numbers: the expected Rand index of such a clustering is 0.57.
Adjusted mutual information
Mutual information also gives credit for chance agreement, and the same correction applies to it. Adjusted mutual information (Vinh, Epps, and Bailey, 2010) uses the chance model of the adjusted Rand index. Under that model the cell $n_{kj}$ takes the value $x$ with the hypergeometric probability $\binom{n_j}{x} \binom{N - n_j}{n_k - x} / \binom{N}{n_k}$, the chance that a cluster of $n_k$ documents draws $x$ of the $n_j$ labels of class $j$. The expected mutual information $E[I]$ is the sum, over all cells and all values $x \ge 1$, of that probability times the cell's term $\frac{x}{N} \log \frac{N x}{n_k n_j}$. The adjusted measure is
$$\mathrm{AMI} = \frac{I - E[I]}{[H(\Omega) + H(C)]/2 - E[I]}.$$
Vinh, Epps, and Bailey give versions with other upper bounds in the denominator. This one matches the NMI of evaluating clusterings and is scikit-learn's default.
For the example the script evaluates the sum and finds $E[I] = 0.1517$ nats, so $\mathrm{AMI} = (0.3919 - 0.1517)/(1.0751 - 0.1517) = 0.260$. The script's exact sum agrees with scikit-learn's value, and on a five-document table it equals the average of $I$ over all 120 deals. Because the entropies are fixed by the model, the expected NMI of a random clustering with these sizes is $0.1517/1.0751 = 0.141$. Chance alone accounts for more than a third of the example's NMI of 0.365.
Both adjusted measures depend on the size of the collection. Problem 1 of evaluating clusterings replaces each of the seventeen documents by two identical copies. That leaves purity and NMI unchanged and raises the Rand index and $F_5$. The chance-adjusted measures also change. The AMI rises from 0.260 to 0.323 for a reason of its own. $I$ and both entropies are unchanged, but the expected mutual information falls from 0.152 to 0.066, because the same proportions are less likely to arise by chance among 34 documents than among 17. The ARI rises from 0.243 to 0.291 for two reasons at once: the 17 copy pairs raise the Rand index from 0.676 to 0.686, and the expected Rand index falls from 0.573 to 0.558. Either change alone would raise it to about 0.27. The adjusted measures answer the question "how far beyond chance", whose answer does depend on the size of the collection.
Degenerate and random clusterings
Feeding the measures clusterings that should score badly shows what each one rewards. Three are useful for the example's seventeen documents:
- every document in its own cluster (singletons);
- all documents in one cluster;
- random clusterings that keep the three cluster sizes 6, 6 and 5 but assign documents to them at random.
Example (which measures rate the singletons at least as highly as the real clustering). Three of purity, NMI, the Rand index and the adjusted Rand index do. Purity gives singletons a perfect 1, NMI rates them higher than the example, and the Rand index ties them with it. Only the adjusted Rand index scores them at chance level. The table gives the values.
The random row gives the median over 30 seeded shuffles. Values are rounded to three decimals.
| Clustering | Purity | NMI | RI | ARI |
|---|---|---|---|---|
| The example | 0.706 | 0.365 | 0.676 | 0.243 |
| Singletons | 1 | 0.543 | 0.676 | 0 |
| One cluster | 0.471 | 0 | 0.324 | 0 |
| Random, same sizes | 0.529 | 0.114 | 0.574 | 0.002 |
The interquartile ranges of the random clusterings are 0.471 to 0.632 for purity, 0.050 to 0.228 for NMI, 0.544 to 0.618 for the Rand index, and −0.067 to 0.105 for the ARI. The F measures of the first three clusterings follow. For the singletons no pair shares a cluster, so precision is $0/0$. We take it, and hence $F_1$ and $F_5$, to be 0, since recall is $0/44 = 0$ and no same-class pair is found.
| Clustering | $F_1$ | $F_5$ |
|---|---|---|
| The example | 0.476 | 0.456 |
| Singletons | 0 | 0 |
| One cluster | 0.489 | 0.926 |
Each measure has a blind spot:
- Purity gives the singletons a perfect 1, as evaluating clusterings shows.
- NMI also prefers the singletons, 0.543, to the actual clustering, 0.365. The normalization reduces the reward for fragmentation but does not remove it. For singletons $I = H(C)$ and $H(\Omega) = \log N$, both shown in the NMI section of evaluating clusterings, so NMI is $H(C) / \tfrac{1}{2}[\log N + H(C)] = 2H(C)/(H(C) + \log N)$. Here that is $2 \times 1.0551/(1.0551 + 2.8332) = 2.1102/3.8883 = 0.543$. With the class sizes held in proportion, $H(C)$ stays fixed while $\log N$ grows without bound, so the value falls toward 0 only as $N$ grows. With 17 documents and three classes it is still large. Random clusterings also score above 0, a median of 0.114; their exact expected NMI is 0.141, from the previous section.
- The Rand index gives the singletons exactly the same score as the example, 92/136 = 0.676. The singletons get every one of the 92 different-class pairs right by never putting anything together. The example earns the same 92 correct decisions a different way, 20 true positives plus 72 true negatives.
- The adjusted Rand index gives both degenerate clusterings exactly 0 (Problem 1 below proves it for any classes) and random clusterings about 0, as it was designed to, while keeping a clear positive score for the example. The random clusterings' median Rand index, 0.574, sits at the expected value 0.573 that the ARI subtracts.
- Adjusted mutual information behaves like the ARI: 0.260 for the example and exactly 0 for both degenerate clusterings. For the singletons every deal of the labels gives $I = H(C)$, so $E[I] = H(C) = I$. For one cluster every deal gives $I = 0$, so $E[I] = 0 = I$. Over the same 30 shuffles its median is −0.032, with interquartile range −0.106 to 0.101.
- $F_5$, which weights recall heavily, gives its best score of the table, 0.926, to the single cluster, because putting everything together finds every same-class pair. A heavily recall-weighted F measure rewards lumping in the same way that purity rewards splitting. Even $F_1$ rates the single cluster, 0.489, slightly above the example, 0.476.
None of the measures is wrong; each answers a narrower question than "is this a good clustering". A common shortcut is to report the Rand index alone because it looks high; the singletons show how little a high Rand index can mean. Purity and $F_\beta$ with large $\beta$ should only compare clusterings with the same number of clusters. Measures adjusted for chance, the ARI and the AMI, are the safest when the number of clusters differs.
The measures on Reuters
The collection is the six-category Reuters collection of K-means in practice, 7,487 stories clustered by k-means. Evaluating clusterings reads the purity and NMI of its six-cluster runs. Here the number of clusters varies.
The blind spots found on seventeen documents show up at scale when the number of clusters varies. The same collection was clustered with nine values of $K$ from 2 to 50 (2, 3, 4, 6, 8, 12, 20, 30 and 50), with 30 k-means++ runs for each. Every clustering was also compared with a random clustering of the same cluster sizes.
Example (the purity of a random clustering of Reuters). A random clustering of Reuters scores a purity of about 0.52 for every $K$ in this range. The earn category holds 52 percent of the 7,487 stories. In a random cluster of any reasonable size, earn is almost always the majority, so about 52 percent of the stories match their cluster's majority category.
| $K$ | Purity | NMI | Rand index | Adjusted Rand |
|---|---|---|---|---|
| 2 | 0.601 | 0.268 | 0.521 | 0.081 |
| 4 | 0.744 | 0.439 | 0.706 | 0.347 |
| 6 | 0.796 | 0.496 | 0.736 | 0.388 |
| 12 | 0.863 | 0.493 | 0.697 | 0.249 |
| 20 | 0.885 | 0.454 | 0.670 | 0.160 |
| 50 | 0.912 | 0.402 | 0.647 | 0.078 |
(Medians of 30 runs, rounded to three decimals.) Purity rises at every step, from 0.60 to 0.91, because more clusters can each be dominated by one category. By $K = 50$ the clustering has carved the collection into small, nearly pure pieces, and purity says it is the best yet. The adjusted Rand index says the opposite. It peaks at $K = 6$ and falls to 0.08 at $K = 50$, because fifty clusters separate most pairs of stories that share a category.
NMI sits between them, nearly flat from 6 to 12 clusters and falling slowly after. Its normalization does what the textbook says on a collection of this size. Assigning each of the 7,487 stories its own cluster would score an NMI of only 0.24, far below the real clusterings. That is the singleton formula $2H(C)/(H(C) + \log N)$ with $\ln 7487 = 8.92$ in the denominator, computed by the Reuters script.
The chance baselines explain the starting points of the curves. A random clustering's purity is about 0.52 for every $K$, as the example above explains. Random NMI rises slightly with $K$, from 0.0002 to 0.007, and random ARI stays at 0. On a collection this large, chance NMI is negligible; on the seventeen documents above it was not.
The other caution is the classes themselves. A low external score can mean the algorithm failed, or that it found a different and equally sensible structure. Reading the contingency table, and the terms that characterize each cluster, is usually more informative than any single number.
Worked problems
The problem is posed here on the article's own example. The script eval_worked.py checks every number in it. The course text's exercises on the other measures are solved in evaluating clusterings.
Problem 1 (the ARI of the degenerate clusterings). Show that the adjusted Rand index of the single cluster, and of the singletons, is exactly 0 for any classes, provided there are at least two classes and some class has at least two documents.
Solution. Write $S$ for the number of same-class pairs and $T = \binom{N}{2}$ for the number of all pairs. At least two classes means $S < T$, and a class of two or more documents means $S > 0$.
One cluster. Every pair is a same-cluster pair, so $TP + FP = T$ and $TP = S$. The expectation is $E[TP] = T \cdot S / T = S$, equal to TP, so the numerator $TP - E[TP]$ is 0. The denominator is $\tfrac{1}{2}(T + S) - S = \tfrac{1}{2}(T - S) > 0$. So the ARI is 0. In the example $TP = E[TP] = 44$ and the denominator is $\tfrac{1}{2}(136 + 44) - 44 = 46$.
Singletons. No pair shares a cluster, so $TP + FP = 0$, $TP = 0$ and $E[TP] = 0 \cdot S / T = 0$. The numerator is 0 and the denominator is $\tfrac{1}{2}(0 + S) - 0 = S/2 > 0$. So the ARI is 0. In the example the denominator is $44/2 = 22$.
Both clusterings leave nothing to chance: once the sizes are fixed, every deal of the labels gives the same pair counts, so the observed count is the expected count.
What we have learned
The adjusted Rand index and adjusted mutual information subtract from a score what the chance model expects, a random dealing of the class labels with the cluster and class sizes fixed. On the seventeen documents they are 0.243 and 0.260, well below the Rand index and the NMI they correct. Degenerate clusterings expose each unadjusted measure's blind spot. Only the two adjusted measures score both the singletons and the single cluster 0. On Reuters, purity kept rising with $K$ while the ARI peaked clearly at six clusters, the number of categories.
Every clustering so far has been flat, with $K$ fixed in advance. Hierarchical clustering builds a tree of clusters instead and compares it with k-means on Reuters.
The seventeen-document numbers are recomputed by tools/experiments/clustering/eval_worked.py in the site repository, the script shared with evaluating clusterings. The Reuters measures come from reuters_restarts.py in the same folder, and reuters_labels.py --check compares them with the values printed here.
References
- Hubert, L., and Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1), 193–218. record
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 16.3. Cambridge University Press. record · 93 pages
- Vinh, N. X., Epps, J., and Bailey, J. (2010). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11, 2837–2854. record