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.
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.
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.
