variation_information#

graph_tool.inference.variation_information(x, y, norm=False)[source]#

Returns the variation of information between two partitions.

Parameters:

xiterable of int values

First partition.

yiterable of int values

Second partition.

norm(optional, default: False)

If True, the result will be normalized in the range $[0,1]$.

Returns:

VIfloat

Variation of information value.

Notes

The variation of information [meila_comparing_2003] is defined as

$$\text{VI}(\mathit{x},\mathit{y})=-\frac{1}{N}\sum _{rs}{m}_{rs}[\ln \frac{m_{rs}}{n_r}+\ln \frac{m_{rs}}{n_s^{\prime }}],$$

with $m_{rs}=\sum _i{\delta }_{x_i,r}{\delta }_{y_i,s}$ being the contingency table between $\mathit{x}$ and $\mathit{y}$, and $n_r=\sum _s{m}_{rs}$ and $n_s^{\prime }=\sum _r{m}_{rs}$ are the group sizes in both partitions.

If norm == True, the normalized value is returned:

$$\frac{\text{VI}(\mathit{x},\mathit{y})}{\ln N}$$

which lies in the unit interval $[0,1]$.

This algorithm runs in time $O(N)$ where $N$ is the length of $\mathit{x}$ and $\mathit{y}$.

References

[meila_comparing_2003]

Marina Meilă, “Comparing Clusterings by the Variation of Information,” in Learning Theory and Kernel Machines, Lecture Notes in Computer Science No. 2777, edited by Bernhard Schölkopf and Manfred K. Warmuth (Springer Berlin Heidelberg, 2003) pp. 173–187. DOI: 10.1007/978-3-540-45167-9_14 [sci-hub, @tor]

Examples

>>> x = np.random.randint(0, 10, 1000)
>>> y = np.random.randint(0, 10, 1000)
>>> gt.variation_information(x, y)
4.525389...