How is the upper bound for Normalized Mutual Information determined?

Question

Mutual information between two clusterings $A$ and $B$ can be calculated as:

$$MI(A,B)=H(A)+H(B)-H(A,B)$$

In the 10th page of this paper it is stated that $MI(A,B)$ can vary in the range $[0,\min\{H(A),H(B)\}]$ (I'm not sure why, though). Therefore, to take the mutual information to the normalized range of $[0,1]$, it should be divided by one of the following upper bounds:

$$\min\{H(A),H(B)\}\leq \sqrt{H(A)H(B)} \leq \frac{H(A)+H(B)}{2} \leq\max\{H(A),H(B)\}$$

I've seen in sklearn's implementation that the third one is used, while for example in R's package aricode the default is the fourth one. I personally think that the only one that makes sense is the first one, as it is the actual maximum value $MI(A,B)$ can return.

Which one should be chosen? Why isn't the first bound used everytime if it is the actual maximum value of $MI(A,B)$ according to that paper?

Answer 1

The debate on appropriate normalization for mutual information is a long one. Each normalization has trade-offs, and everybody has their preferences. So I can't really answer your first question of: which one should be chosen. Personally, I don't like any of the mutual information measures for clustering comparisons, and prefer some other measures as discussed in Gates et al (2018).

To answer your second question, the true bound of $min\{H(X),H(Y)\}$ is rarely used because it can equal 1 even if the clusterings X and Y are not identical. This occurs when one clustering places each element in its own cluster.

Here is a quick example using the CluSim package:

from clusim.clustering import Clustering, print_clustering
from clusim.sim import nmi

c1 = Clustering(elm2clu_dict = {0:[0], 1:[1], 2:[2]})
c2 = Clustering(elm2clu_dict = {0:[0], 1:[1], 2:[1]})
print_clustering(c1)
0|1|2
print_clustering(c2)
0|12
nmi(c1, c2, norm_type = 'min')
1.0

See Kvalseth (1987) for some of the earliest opinions on the debate of mutual information normalization.

Also, the choice of $max \{H(X), H(Y)\}$ is sometimes used because it is the only normalization which makes 1-NMI a metric on the lattice of partitions, but it has its own sensitivity issues.