Machine Learning & Information Theory
Variation of Information (VI) and Normalized Partition Distance Formula
Compute Meilă’s (2007) true metric distance between clusterings VI(U, V) = 2*H(U, V) - H(U) - H(V) in bits and Kraskov’s Normalized Variation of Information in [0, 1].
Use a true triangle-inequality metric when comparing clusterings across runs
Pair-counting scores like Rand and Fowlkes-Mallows violate metric distance axioms, whereas Meilă’s (2007) Variation of Information VI(U, V) = H(U|V) + H(V|U) = 2 * H(U, V) - H(U) - H(V) satisfies non-negativity, symmetry, label-permutation invariance (VI = 0 iff identical partitions), and the triangle inequality across the entire space of partitions.
Test a balanced 2x2 contingency table of N = 100 items: n_11 = 40 (B2), n_12 = 10 (C2), n_21 = 10 (B3), n_22 = 40 (C3). Because row marginals (50, 50) and column marginals (50, 50) are 50/50, marginal entropies are H(U) = 1.0000 bit and H(V) = 1.0000 bit. Joint entropy over {0.40, 0.10, 0.10, 0.40} is H(U, V) = 1.7219 bits, giving Mutual Information I(U, V) = 1 + 1 - 1.7219 = 0.2781 bits, VI = 2*1.7219 - 2 = 1.4439 bits, and Normalized NVI = VI / H(U, V) = 0.8385.
| Information Metric (Bits) | Shannon Formula (0*log2(0) = 0) | Sample Output |
|---|---|---|
| Marginal Entropies H(U), H(V) | -SUM(p_i * LOG(p_i, 2)) | 1.0000 bit, 1.0000 bit |
| Joint Entropy H(U, V) | -SUM(p_ij * LOG(p_ij, 2)) | 1.7219 bits |
| Variation of Information VI | 2 * H(U, V) - H(U) - H(V) | 1.4439 bits |
| Normalized VI (Jaccard Info Dist) | VI(U, V) / H(U, V) = 1 - I / H(U,V) | 0.8385 (Swapped labels -> 0) |
Variation of Information VI(U, V) (in Bits) Formula
Guard empty contingency cells (n_ij = 0) individually with IF(x <= 0, 0, -(x / N) * LOG(x / N, 2)) so 0 * log(0) evaluates cleanly to 0 rather than #NUM!.
=LET(n_tot, SUM(B2:C3), IF(n_tot <= 0, "Empty Partition", LET(r_a, B2 + C2, r_b, B3 + C3, c_a, B2 + B3, c_b, C2 + C3, h_u, IF(r_a <= 0, 0, -(r_a / n_tot) * LOG(r_a / n_tot, 2)) + IF(r_b <= 0, 0, -(r_b / n_tot) * LOG(r_b / n_tot, 2)), h_v, IF(c_a <= 0, 0, -(c_a / n_tot) * LOG(c_a / n_tot, 2)) + IF(c_b <= 0, 0, -(c_b / n_tot) * LOG(c_b / n_tot, 2)), h_uv, IF(B2 <= 0, 0, -(B2 / n_tot) * LOG(B2 / n_tot, 2)) + IF(C2 <= 0, 0, -(C2 / n_tot) * LOG(C2 / n_tot, 2)) + IF(B3 <= 0, 0, -(B3 / n_tot) * LOG(B3 / n_tot, 2)) + IF(C3 <= 0, 0, -(C3 / n_tot) * LOG(C3 / n_tot, 2)), ROUND(2 * h_uv - h_u - h_v, 4))))Label-Permutation Invariance Check (Swapped Cluster IDs)
Test label-permutation invariance by setting B2 = 0, C2 = 50, B3 = 50, C3 = 0 (exact same two clusters with reversed labels 1 <-> 2): H(U) = 1, H(V) = 1, H(U, V) = 1, and VI drops identically to 0!
=IF(F3 <= 0, 0, ROUND(F4 / F3, 4))Try the example
Use the original values or change them to test your understanding.