Comparing clusterings: Rand Index vs Variation of Information

I was wondering if anybody had any insight or intuition behind the difference between the Variation of Information and the Rand Index for comparing clusterings.

I have read the paper "Comparing Clusterings - An Information Based Distance" by Marina Melia (Journal of Multivariate Analysis, 2007), but, other than noticing the difference in the definitions, I don't understand what is it that the variation of information captures that the rand index does not capture.

In my opinion, there are huge differences. The Rand index is very much affected by the granularity of the clusterings on which it operates. In what follows I'll use the Mirkin distance, which is an adjusted form of the Rand index (easy to see, but see e.g. Meila). I'll also use the split/join distance, which is also mentioned in some of Meila's papers (disclaimer: split/join distance was proposed by me). Suppose a universe of one hundred elements. I'll use Top to denote the clustering with a single cluster containing all elements, Bottom to denote the clustering where all nodes are in separate singleton sets, Left to denote the clustering {{1,2,..10},{11,12..20},{21,22..30}, ..., {91,92,..100}}, and Right to denote the clustering {{1,11,..91}, {2,12,..92}, {3,13,..93}, ..., {10,20,..100}}.

To my mind, Bottom and Top are consistent (nesting) clusters, whereas Left and Right are maximally conflicting clusters. The distances from the mentioned metrics for these two pairwise comparisons are as follows:

               Top-Bottom     Left-Right

Mirkin            9900          1800
VI                4.605         4.605
Split/join        99            180


It follows that Mirkin/Rand consider the consistent Top-Bottom pair much further apart than the maximally conflicting Left-Right pair. This is an extreme example to illustrate the point, but Mirkin/Rand are in general very much affected by the granularity of the clusterings on which it operates. The reason underlying this is a quadratic relationship between this metric and cluster sizes, explained by the fact that the counting of pairs of nodes is involved. In effect, the Mirkin distance is a Hamming distance between edge sets of unions of complete graphs induced by clusterings (this is the answer to your question I think).

Regarding the diffferences between Variation of Information and Split/Join, the first is more sensitive to certain conflict situations as demonstrated by Meila. That is, Split/Join only considers the best match for each cluster, and disregards the fragmentation that might occur on the remaining part of that cluster, whereas Variation of Information will pick this up. That said, Split/Join is easily interpretable as the number of nodes that need to be moved to obtain one cluster from the other, and in that sense its range is more easily understood; in practice the fragmentation issue may also be not that common.

Each of these metrics can be formed as the sum of two distances, namely the distances from each of the two clusterings to their greatest common subclustering. I feel it is often beneficial to work with those separate parts rather than just their sum. The above table then becomes:

               Top-Bottom     Left-Right

Mirkin          0,9900          900,900
VI              0,4.605       2.303,2.303
Split/join      0,99             90,90


The subsumption relationship between Top and Bottom becomes immediately clear. It is often quite useful to know whether two clusterings are consistent (i.e. one is (nearly) a subclustering of the other) as a relaxation of the question of whether they are close. A clustering can be quite distant from a gold standard, but still be consistent or nearly consistent. In such a case there may be no reason to consider the clustering bad with respect to that gold standard. Of course, the trivial clusterings Top and Bottom will be consistent with any clustering, so this must be taken into account.

Finally, I believe that metrics such as Mirkin, Variation of Information, and Split/Join are the natural tools to compare clusterings. For most applications methods that try to incorporate statistical independence and correct for chance are overly contrived and obfuscate rather than clarify.

Second example Consider the following pairs of clusterings: C1 = { { 1, 2, 3, 4, 5, 6, 7, 8}, { 9, 10, 11, 12, 13, 14, 15, 16} } with C2 = { { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16} }

and C3 = { { 1, 2, 3, 4}, {5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16} } with { { 1, 2, 3, 4}, {5, 6, 7, 8, 9, 10, 11, 12}, {13, 14, 15, 16} }

Here C2 can be formed from C1 by moving nodes 9 and 10 and C3 can be formed from C3 by moving nodes 11 and 12. Both changes are identical ("move two nodes") except for the fact that the sizes of the clusters involved differ. The clustering metrics table for these two examples is this:

            C1-C2         C3-C4

Mirkin       56            40
VI            0.594         0.520
Split/Join    4             4


It can be seen that Mirkin/Rand and Variation of information are affected by the cluster sizes (and Mirkin to a larger extent; this will be more pronounced as cluster sizes diverge), whereas the Split/Join distance is not (its value is 4 as it "moves" nodes from one clustering to the other always via the largest common subclustering). This may be a desirable trait depending on circumstances. The simple interpretation of Split/Join (number of nodes to move) and its independence of cluster size are worth being aware of. Between Mirkin and Variation of Information I think the latter is very much preferable.

• Thanks micans, this is very insightful. I am not sure I understood the second table. Why are there two numbers separated by a comma for each entry in the table? Also, do you know how this argument relates to @Suresh's? Mar 21 '12 at 21:14
• If A and B are clusterings, then d(A,B) can be split up as d(A,B) = d(A,X) + d(B,X) where X is the largest clustering that is a subclustering of both. In Suresh's notation we have that d(A,B) = f(A)+f(B)-2f(X). This can be rewritten as f(A)+f(X)-2f(X) + f(B)+f(X)-2f(X) = d(A,X) + d(B,X). Above I have written the two components d(A,X) and d(B,X) separated by commas. The biggest difference between the two by far is the quadratic characteristics of Mirkin/Rand. If you look at the Top/Bottom and Left/Right examples, the Top-Bottom distance is huge; this is entirely due to the size of Top. Mar 22 '12 at 10:36

The difference between the two methods is subtle. The best way to think about it is to consider the lattice defined by the merge-split operation on clusterings. Both these measures can be reconstructed by defining a function $f$ on a clustering, and then defining the distance between two clusterings by the formula:

$d(C, C') = f(C) + f(C') - 2f(C \wedge C')$ where $C \wedge C'$ is the join of the two clusterings in the lattice.

Now let $C = \{ C_1, C_2, \ldots, C_k\}$ and let $n_i = |C_i|$. Setting $f(C) = \sum n_i^2$ yields the rand index, and setting $f(C) = \sum n_i \log n_i$ yields VI.

• Thanks Suresh! Do you know if (and how) the difference in these formulas explains why the rand index and the variation of information penalize consistency (how much one of the clusterings is a subclustering of the other) between clusterings differently? (according to micans'answer) Mar 21 '12 at 19:54
• As micans points out, the Rand Index has quadratic behaviour, so it's more sensitive to changes in containment than the entropy function, which is close to linear. Mar 21 '12 at 20:24
• Sorry, but I don't still see how containment affects the quadratic terms more than other types of discrepancies between clusterings. Would you mind elaborating on this a bit further? Mar 21 '12 at 21:12
• @user023472 Hello user023472. I am interested in your findings, you asked this question some time ago it seems. Have you learned what the difference between the two methods truly amounts to? Thanks. Mar 10 '14 at 2:06