clustering-mi

Mutual information between clusterings. Maximilian Jerdee, Alec Kirkley, and Mark Newman.

A Python package for computing the mutual information between two clusterings of the same set of objects. This implementation includes multiple variations and normalizations of the mutual information.

The package implements the reduced mutual information (RMI) as described in Jerdee, Kirkley, and Newman (2024), which corrects the standard measure's bias towards labelings with too many groups. The asymmetric normalization of Jerdee, Kirkley, and Newman (2023) is also included to remove the biases of symmetric normalizations. Data used to generate the figures in those papers is available in the examples/data directory of the repository.

The mutual information variation (passed to both mutual_information and normalized_mutual_information) selects the measure:

For normalized_mutual_information, the normalization selects the denominator:

Installation

clustering-mi can be installed through pip:

pip install clustering-mi

or built locally with a c++ compiler by cloning this repository and running

pip install .

in the base directory.

Typical usage

Once installed, the package can be imported as

import clustering_mi as cmi

Note that this is not import clustering-mi.

Two clusterings (or "labelings") can be loaded in several ways; the names of the groups are irrelevant:

# As arrays:
labels1 = ["red", "red", "red", "blue", "blue", "blue", "green", "green"]
labels2 = [1, 1, 1, 1, 2, 2, 2, 2]

# As a contingency table, i.e., a matrix that counts label co-occurrences.
# Columns are the first labeling, rows are the second labeling:
contingency_table = [[3, 1, 0], [0, 2, 2]]

# Or as the path to a space-separated file, one object (label1 label2) per line:
filename = "data/example.txt"

where data/example.txt contains one labeled object per line:

red 1
red 1
red 1
blue 1
blue 2
blue 2
green 2
green 2

The package can then compute the mutual information (in bits) between the two labelings from any format:

# Defaults to the reduced mutual information (RMI)
mutual_information = cmi.mutual_information(labels1, labels2)  # From lists
mutual_information = cmi.mutual_information(contingency_table)  # From contingency table
mutual_information = cmi.mutual_information(filename)  # Reads filename

print(f"Mutual Information: {mutual_information:.3f} (bits)")

# Compute other variants using the "variation" parameter.
# Correcting for chance (random permutations)
adjusted_mutual_information = cmi.mutual_information(labels1, labels2, variation="adjusted")
# Traditional mutual information
traditional_mutual_information = cmi.mutual_information(labels1, labels2, variation="traditional")

The package can also compute the normalized mutual information (NMI) between the two labelings, a measure bounded above by 1 when the two labelings are identical. Depending on the application, a symmetric or asymmetric normalization may be appropriate.

# Symmetric normalization
normalized_mutual_information = cmi.normalized_mutual_information(labels1, labels2, normalization="mean")
# "Normalized Mutual Information" most commonly refers to the Stirling-approximated mutual information
# divided by the mean of the entropies of the two labelings, although this is not our preferred measure.
normalized_stirling_mutual_information = cmi.normalized_mutual_information(labels1, labels2, variation="stirling", normalization="mean")

print(f"(symmetric) Normalized Mutual Information (labels1 <-> labels2): {normalized_mutual_information:.3f}")

# Asymmetric normalization measures how much the first labeling tells us about the second,
# as a fraction of all there is to know about the second labeling.
# This form is appropriate when the second labeling is a "ground truth" and the first is a prediction.
asymmetric_normalized_mutual_information_1_2 = cmi.normalized_mutual_information(labels1, labels2, normalization="second")
# Or when the first labeling is the ground truth and the second is a prediction.
asymmetric_normalized_mutual_information_2_1 = cmi.normalized_mutual_information(labels1, labels2, normalization="first")

print(f"(asymmetric) Normalized Mutual Information (labels1 -> labels2): {asymmetric_normalized_mutual_information_1_2:.3f}")
print(f"(asymmetric) Normalized Mutual Information (labels2 -> labels1): {asymmetric_normalized_mutual_information_2_1:.3f}")

Further usage examples can be found in the examples directory of the repository and the package documentation.