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.

Suppose we have two partitions ${\displaystyle X}$ and ${\displaystyle Y}$ of a set ${\displaystyle A}$ into disjoint subsets, namely ${\displaystyle X=\{X_{1},X_{2},..,,X_{k}\}}$, ${\displaystyle Y=\{Y_{1},Y_{2},..,,Y_{l}\}}$. Let ${\displaystyle n=\sum _{i}|X_{i}|+\sum _{j}|Y_{j}|=|A|}$, ${\displaystyle p_{i}=|X_{i}|/n}$ , ${\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:

...
Wikipedia