Normalized mutual information

The problem, from first principles

Another way to compare a clustering with ground truth is to ask how much knowing one labeling tells you about the other. Mutual information measures that shared information in nats. It is hard to read on its own, because its scale depends on the entropy of each labeling, so normalized mutual information (NMI) divides it by the average of the two entropies. The result lies in [0, 1].

Implement normalized_mutual_information(labels_true, labels_pred) with arithmetic-mean normalization.

• Contingency counts n_ij over the two labelings, with p_ij = n_ij / N, and marginals p_i and p_j.
• MI = Σ p_ij · log(p_ij / (p_i · p_j)), summed over cells with p_ij > 0.
• H(U) = −Σ p_i log p_i, and H(V) likewise.
• NMI = MI / ((H(U) + H(V)) / 2).
• If both entropies are zero (each labeling has a single cluster), return 1.0.

Constraints

• Inputs must have the same length, otherwise raise ValueError.
• Use the natural logarithm.

Hints

Open one at a time. Each gives away a little more than the last.