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.^[1][2][3]

Suppose we have two partitions 👁 {\displaystyle X}
and 👁 {\displaystyle Y}
of a set 👁 {\displaystyle A}
, namely 👁 {\displaystyle X=\{X_{1},X_{2},\ldots ,X_{k}\}}
and 👁 {\displaystyle Y=\{Y_{1},Y_{2},\ldots ,Y_{l}\}}
.

Let:

👁 {\displaystyle n=\sum _{i}|X_{i}|=\sum _{j}|Y_{j}|=|A|}

👁 {\displaystyle p_{i}=|X_{i}|/n}
and 👁 {\displaystyle q_{j}=|Y_{j}|/n}

👁 {\displaystyle r_{ij}=|X_{i}\cap Y_{j}|/n}

Then the variation of information between the two partitions is:

👁 {\displaystyle \mathrm {VI} (X;Y)=-\sum _{i,j}r_{ij}\left[\log(r_{ij}/p_{i})+\log(r_{ij}/q_{j})\right]}
.

This is equivalent to the shared information distance between the random variables i and j with respect to the uniform probability measure on 👁 {\displaystyle A}
defined by 👁 {\displaystyle \mu (B):=|B|/n}
for 👁 {\displaystyle B\subseteq A}
.

We can rewrite this definition in terms that explicitly highlight the information content of this metric.

The set of all partitions of a set form a compact lattice where the partial order induces two operations, the meet 👁 {\displaystyle \wedge }
and the join 👁 {\displaystyle \vee }
, where the maximum 👁 {\displaystyle {\overline {\mathrm {1} }}}
is the partition with only one block, i.e., all elements grouped together, and the minimum is 👁 {\displaystyle {\overline {\mathrm {0} }}}
, the partition consisting of all elements as singletons. The meet of two partitions 👁 {\displaystyle X}
and 👁 {\displaystyle Y}
is easy to understand as that partition formed by all pair intersections of one block of, 👁 {\displaystyle X_{i}}
, of 👁 {\displaystyle X}
and one, 👁 {\displaystyle Y_{i}}
, of 👁 {\displaystyle Y}
. It then follows that 👁 {\displaystyle X\wedge Y\subseteq X}
and 👁 {\displaystyle X\wedge Y\subseteq Y}
.

Let's define the entropy of a partition 👁 {\displaystyle X}
as

where 👁 {\displaystyle p_{i}=|X_{i}|/n}
. Clearly, 👁 {\displaystyle H({\overline {\mathrm {1} }})=0}
and 👁 {\displaystyle H({\overline {\mathrm {0} }})=\log \,n}
. The entropy of a partition is a monotonous function on the lattice of partitions in the sense that 👁 {\displaystyle X\subseteq Y\Rightarrow H(X)\geq H(Y)}
.

Then the VI distance between 👁 {\displaystyle X}
and 👁 {\displaystyle Y}
is given by

The difference 👁 {\displaystyle d(X,Y)\equiv |H\left(X\right)-H\left(Y\right)|}
is a pseudo-metric as 👁 {\displaystyle d(X,Y)=0}
doesn't necessarily imply that 👁 {\displaystyle X=Y}
. From the definition of 👁 {\displaystyle {\overline {\mathrm {1} }}}
, it is 👁 {\displaystyle \mathrm {VI} (X,\mathrm {1} )\,=\,H\left(X\right)}
.

If in the Hasse diagram we draw an edge from every partition to the maximum 👁 {\displaystyle {\overline {\mathrm {1} }}}
and assign it a weight equal to the VI distance between the given partition and 👁 {\displaystyle {\overline {\mathrm {1} }}}
, we can interpret the VI distance as basically an average of differences of edge weights to the maximum

For 👁 {\displaystyle H(X)}
as defined above, it holds that the joint information of two partitions coincides with the entropy of the meet

and we also have that 👁 {\displaystyle d(X,X\wedge Y)\,=\,H(X\wedge Y|X)}
coincides with the conditional entropy of the meet (intersection) 👁 {\displaystyle X\wedge Y}
relative to 👁 {\displaystyle X}
.

The variation of information satisfies

👁 {\displaystyle \mathrm {VI} (X;Y)=H(X)+H(Y)-2I(X,Y)}
,

where 👁 {\displaystyle H(X)}
is the entropy of 👁 {\displaystyle X}
, and 👁 {\displaystyle I(X,Y)}
is mutual information between 👁 {\displaystyle X}
and 👁 {\displaystyle Y}
with respect to the uniform probability measure on 👁 {\displaystyle A}
. This can be rewritten as

👁 {\displaystyle \mathrm {VI} (X;Y)=H(X,Y)-I(X,Y)}
,

where 👁 {\displaystyle H(X,Y)}
is the joint entropy of 👁 {\displaystyle X}
and 👁 {\displaystyle Y}
, or

👁 {\displaystyle \mathrm {VI} (X;Y)=H(X|Y)+H(Y|X)}
,

where 👁 {\displaystyle H(X|Y)}
and 👁 {\displaystyle H(Y|X)}
are the respective conditional entropies.

The variation of information can also be bounded, either in terms of the number of elements:

👁 {\displaystyle \mathrm {VI} (X;Y)\leq \log(n)}
,

Or with respect to a maximum number of clusters, 👁 {\displaystyle K^{*}}
:

👁 {\displaystyle \mathrm {VI} (X;Y)\leq 2\log(K^{*})}

To verify the triangle inequality 👁 {\displaystyle \mathrm {VI} (X;Z)\leq \mathrm {VI} (X;Y)+\mathrm {VI} (Y;Z)}
, expand using the identity 👁 {\displaystyle \mathrm {VI} (X;Y)=H(X|Y)+H(Y|X)}
. It suffices to prove 👁 {\displaystyle H(X|Z)\leq H(X|Y)+H(Y|Z)}
The right side has a lower bound 👁 {\displaystyle H(X|Y)+H(Y|Z)\geq H(X|Y,Z)+H(Y|Z)=H(X,Y|Z)}
which is no less than the left side.

• Partanalyzer includes a C++ implementation of VI and other metrics and indices for analyzing partitions and clusterings
• C++ implementation with MATLAB mex files