Variation of Information¶

Background¶

The variation of information (VI) is a metric on the space of clusterings, introduced by Marina Meila. It measures how much information is lost and gained when moving from one clustering to another. Unlike many clustering comparison measures, VI is a true metric: it satisfies non-negativity, symmetry, and the triangle inequality.

VI is defined in terms of conditional entropies:

where \(H(X \mid Y)\) is the conditional entropy of clustering \(X\) given clustering \(Y\). When two clusterings are identical, \(\mathrm{VI} = 0\).

Computing VI efficiently for large datasets requires sparse matrix operations because the joint probability matrix between cluster labels is typically very sparse.

Objective¶

This example demonstrates how to:

• build sparse matrices from cluster assignment data using COO format
• convert between sparse formats (COO to CSR)
• compute marginal and conditional probabilities from sparse joint distributions
• use sparse.diags for efficient diagonal matrix operations
• implement the variation of information metric using sparse matrix arithmetic

Setup¶

Given two clusterings \(X\) and \(Y\) of \(n\) data points, each point receives a cluster label. The joint distribution \(p(x, y)\) counts how many points have label \(x\) in the first clustering and label \(y\) in the second, then normalizes by \(n\). This joint distribution is naturally sparse because most cluster pairs have no shared points.

The marginal distributions are:

The conditional entropy \(H(Y \mid X)\) is:

where \(p(y \mid x) = p(x, y) / p(x)\).

Code¶

Building Sparse Matrices from Coordinate Data¶

The COO (Coordinate) format stores entries as (row, col, data) triples, making it the natural choice for constructing a joint distribution from paired cluster labels.

```python import numpy as np from scipy import sparse

x = np.array([1, 0, 2, 1, 1, 2]) # cluster labels from first clustering y = np.array([0, 1, 1, 2, 0, 2]) # cluster labels from second clustering data = np.ones(len(x)) # count 1 for each data point

coo = sparse.coo_matrix((data, (x, y)), shape=(3, 3)) print(coo) ```

(1, 0) 1.0 (0, 1) 1.0 (2, 1) 1.0 (1, 2) 1.0 (1, 0) 1.0 (2, 2) 1.0

Converting to CSR and Normalizing¶

CSR (Compressed Sparse Row) format supports efficient arithmetic operations. Converting and normalizing produces the joint probability distribution.

python csr = coo.tocsr() pxy = csr.copy() pxy.data /= np.sum(pxy.data) print("Sum:", pxy.sum()) # 1.0

Computing Marginal Probabilities¶

Row sums give \(p(x)\) and column sums give \(p(y)\).

python px = np.array(pxy.sum(axis=1)).ravel() # p(x): sum over y py = np.array(pxy.sum(axis=0)).ravel() # p(y): sum over x print("p(x):", px) # [0.1667, 0.5, 0.3333] print("p(y):", py) # [0.3333, 0.3333, 0.3333]

Diagonal Matrices and Safe Operations¶

The sparse.diags function creates diagonal matrices efficiently. Two helper functions handle the numerical edge cases where \(0 \cdot \log 0 = 0\) by convention and division by zero must be avoided.

```python def safe_inverse(arr): """Invert array elements, leaving zeros as zeros.""" result = arr.copy() nz = np.nonzero(arr) result[nz] = 1 / arr[nz] return result

def xlogx(arr): """Compute x * log2(x), treating 0 * log(0) = 0.""" result = arr.copy() nz = np.nonzero(arr) result[nz] = arr[nz] * np.log2(arr[nz]) return result

px_inv = sparse.diags([safe_inverse(px)], [0]) py_inv = sparse.diags([safe_inverse(py)], [0]) ```

Variation of Information¶

Combining all the pieces, the VI computation uses sparse matrix products to compute conditional probabilities and entropies.

```python def variation_of_information(x, y): """ Compute Variation of Information between two clusterings.

VI(X;Y) = H(X|Y) + H(Y|X)

Parameters
----------
x, y : array-like
    Cluster assignment arrays of the same length.

Returns
-------
float
    VI score. Lower is better; 0 means identical clusterings.
"""
pxy = sparse.coo_matrix(
    (np.ones(x.size), (x.ravel(), y.ravel())), dtype=float
).tocsr()
pxy.data /= np.sum(pxy.data)

px = np.array(pxy.sum(axis=1)).ravel()
py = np.array(pxy.sum(axis=0)).ravel()

px_inv = sparse.diags([safe_inverse(px)], [0])
py_inv = sparse.diags([safe_inverse(py)], [0])

# H(Y|X) via p(y|x) = diag(1/p(y)) @ p(x,y)
hygx = -(px * xlogx(py_inv.dot(pxy)).sum(axis=1)).sum()
# H(X|Y) via p(x|y) = p(x,y) @ diag(1/p(x))
hxgy = -(py * xlogx(pxy.dot(px_inv)).sum(axis=1)).sum()

return hygx + hxgy

c1 = np.array([0, 0, 1, 1, 2, 2]) c2 = np.array([0, 0, 1, 1, 2, 2]) c3 = np.array([0, 1, 0, 1, 0, 1])

print("VI(identical):", variation_of_information(c1, c2)) # ~0 print("VI(different):", variation_of_information(c1, c3)) # > 0 ```

VI(identical): 0.0 VI(different): 1.459

Interpretation¶

The variation of information captures two complementary types of mismatch between clusterings:

• \(H(X \mid Y)\) measures the information about \(X\) that is not explained by \(Y\). If \(Y\) perfectly predicts \(X\), this term is zero.
• \(H(Y \mid X)\) measures the information about \(Y\) that is not explained by \(X\).

When both conditional entropies are zero, the clusterings are identical and \(\mathrm{VI} = 0\). A larger VI indicates more disagreement.

Statistical Insight¶

The sparse matrix approach is essential for scalability. If there are \(k_1\) clusters in \(X\) and \(k_2\) clusters in \(Y\), the joint distribution matrix has shape \(k_1 \times k_2\). For fine-grained clusterings of large datasets, most entries are zero because most cluster pairs share no points. Sparse storage reduces memory from \(O(k_1 k_2)\) to \(O(\min(n, k_1 k_2))\) and sparse arithmetic avoids wasted computation on zero entries.

The key sparse patterns used here generalize to many information-theoretic computations:

Extensions¶

• Compute the normalized variation of information \(\mathrm{NVI} = \mathrm{VI} / \log n\) to obtain a value between 0 and 1
• Implement mutual information \(I(X; Y) = H(X) + H(Y) - H(X, Y)\) using the same sparse framework
• Compare VI against the adjusted Rand index on synthetic clustering benchmarks
• Scale the implementation to clusterings with millions of points and observe the memory advantage of sparse formats

Exercises¶

Exercise 1. Given the joint probability matrix below in dense form, compute \(H(X \mid Y)\) by hand using base-2 logarithms.

Exercise 2. Prove that \(\mathrm{VI}(X; Y) = 0\) if and only if \(X = Y\) (i.e., the two clusterings assign the same label to every point, up to relabeling).

Exercise 3. Write a function that computes the mutual information \(I(X; Y)\) using the same sparse matrix framework. Verify that \(I(X; Y) = H(X) - H(X \mid Y)\).

px = np.array(pxy.sum(axis=1)).ravel()
py = np.array(pxy.sum(axis=0)).ravel()

# H(X)
hx = -np.sum(xlogx(px))
# H(Y)
hy = -np.sum(xlogx(py))
# H(X, Y) from joint distribution
hxy = -np.sum(xlogx(pxy.data))

return hx + hy - hxy

Exercise 4. Explain why COO format is preferred for constructing the joint distribution matrix, while CSR format is preferred for the subsequent arithmetic. Under what conditions would CSC format be more efficient than CSR for the VI computation?