# Variation of information

In probability theory and information theory, the variation of information or shared information distance is a measure of the distance between two clusterings (partitions of elements). It is closely related to mutual information; indeed, it is a simple linear expression involving the mutual information. Unlike the mutual information, however, the variation of information is a true metric, in that it obeys the triangle inequality. Even more, it is a universal metric, in that if any other distance measure two items close-by, then the variation of information will also judge them close.[1]

## Definition

Suppose we have two clusterings (a division of a set into several subsets) $X$ and $Y$ where $X = \{X_{1}, X_{2}, ..,, X_{k}\}$, $p_{i} = |X_{i}| / n$, $n = \Sigma_{k} |X_{i}|$. Then the variation of information between two clusterings is:

$VI(X; Y ) = H(X) + H(Y) - 2I(X, Y)$

where $H(X)$ is entropy of $X$ and $I(X, Y)$ is mutual information between $X$ and $Y$.

This is equivalent to the shared information distance.

## References

1. ^ Alexander Kraskov, Harald Stögbauer, Ralph G. Andrzejak, and Peter Grassberger, "Hierarchical Clustering Based on Mutual Information", (2003) ArXiv q-bio/0311039