Skip to content

Instantly share code, notes, and snippets.

@jwcarr
Last active June 20, 2024 08:50
Show Gist options
  • Save jwcarr/626cbc80e0006b526688 to your computer and use it in GitHub Desktop.
Save jwcarr/626cbc80e0006b526688 to your computer and use it in GitHub Desktop.
Variation of information (VI)
# Variation of information (VI)
#
# Meila, M. (2007). Comparing clusterings-an information
# based distance. Journal of Multivariate Analysis, 98,
# 873-895. doi:10.1016/j.jmva.2006.11.013
#
# https://en.wikipedia.org/wiki/Variation_of_information
from math import log
def variation_of_information(X, Y):
n = float(sum([len(x) for x in X]))
sigma = 0.0
for x in X:
p = len(x) / n
for y in Y:
q = len(y) / n
r = len(set(x) & set(y)) / n
if r > 0.0:
sigma += r * (log(r / p, 2) + log(r / q, 2))
return abs(sigma)
# Identical partitions
X1 = [ [1,2,3,4,5], [6,7,8,9,10] ]
Y1 = [ [1,2,3,4,5], [6,7,8,9,10] ]
print(variation_of_information(X1, Y1))
# VI = 0
# Similar partitions
X2 = [ [1,2,3,4], [5,6,7,8,9,10] ]
Y2 = [ [1,2,3,4,5,6], [7,8,9,10] ]
print(variation_of_information(X2, Y2))
# VI = 1.102
# Dissimilar partitions
X3 = [ [1,2], [3,4,5], [6,7,8], [9,10] ]
Y3 = [ [10,2,3], [4,5,6,7], [8,9,1] ]
print(variation_of_information(X3, Y3))
# VI = 2.302
# Totally different partitions
X4 = [ [1,2,3,4,5,6,7,8,9,10] ]
Y4 = [ [1], [2], [3], [4], [5], [6], [7], [8], [9], [10] ]
print(variation_of_information(X4, Y4))
# VI = 3.322 (maximum VI is log(N) = log(10) = 3.322)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment