Adjusted mutual information

Given a set S of N elements ${\displaystyle S=\{s_{1},s_{2},\ldots s_{N}\}}$, consider two partitions of S, namely ${\displaystyle U=\{U_{1},U_{2},\ldots ,U_{R}\}}$ with R clusters, and ${\displaystyle V=\{V_{1},V_{2},\ldots ,V_{C}\}}$ with C clusters. It is presumed here that the partitions are so-called hard clusters; the partitions are pairwise disjoint:

${\displaystyle U_{i}\cap U_{j}=\varnothing =V_{i}\cap V_{j}}$

for all ${\displaystyle i\neq j}$, and complete:

${\displaystyle \cup _{i=1}^{R}U_{i}=\cup _{j=1}^{C}V_{j}=S}$

The mutual information of cluster overlap between U and V can be summarized in the form of an RxC contingency table ${\displaystyle M=[n_{ij}]_{j=1\ldots C}^{i=1\ldots R}}$, where ${\displaystyle n_{ij}}$ denotes the number of objects that are common to clusters ${\displaystyle U_{i}}$ and ${\displaystyle V_{j}}$. That is,

${\displaystyle n_{ij}=\left|U_{i}\cap V_{j}\right|}$

Suppose an object is picked at random from S; the probability that the object falls into cluster ${\displaystyle U_{i}}$ is:

${\displaystyle P_{U}(i)={\frac {|U_{i}|}{N}}}$

The entropy associated with the partitioning U is:

${\displaystyle H(U)=-\sum _{i=1}^{R}P_{U}(i)\log P_{U}(i)}$

H(U) is non-negative and takes the value 0 only when there is no uncertainty determining an object's cluster membership, i.e., when there is only one cluster. Similarly, the entropy of the clustering V can be calculated as:

${\displaystyle H(V)=-\sum _{j=1}^{C}P_{V}(j)\log P_{V}(j)}$

where ${\displaystyle P_{V}(j)={|V_{j}|}/{N}}$. The mutual information (MI) between two partitions:

${\displaystyle MI(U,V)=\sum _{i=1}^{R}\sum _{j=1}^{C}P_{UV}(i,j)\log {\frac {P_{UV}(i,j)}{P_{U}(i)P_{V}(j)}}}$

where ${\displaystyle P_{UV}(i,j)}$ denotes the probability that a point belongs to both the cluster ${\displaystyle U_{i}}$ in U and cluster ${\displaystyle V_{j}}$ in V:

${\displaystyle P_{UV}(i,j)={\frac {|U_{i}\cap V_{j}|}{N}}}$

MI is a non-negative quantity upper bounded by the entropies H(U) and H(V). It quantifies the information shared by the two clusterings and thus can be employed as a clustering similarity measure.

Like the Rand index, the baseline value of mutual information between two random clusterings does not take on a constant value, and tends to be larger when the two partitions have a larger number of clusters (with a fixed number of set elements N). By adopting a hypergeometric model of randomness, it can be shown that the expected mutual information between two random clusterings is:

${\displaystyle {\begin{aligned}E\{MI(U,V)\}=&\sum _{i=1}^{R}\sum _{j=1}^{C}\sum _{n_{ij}=(a_{i}+b_{j}-N)^{+}}^{\min(a_{i},b_{j})}{\frac {n_{ij}}{N}}\log \left({\frac {N\cdot n_{ij}}{a_{i}b_{j}}}\right)\times \\&{\frac {a_{i}!b_{j}!(N-a_{i})!(N-b_{j})!}{N!n_{ij}!(a_{i}-n_{ij})!(b_{j}-n_{ij})!(N-a_{i}-b_{j}+n_{ij})!}}\\\end{aligned}}}$

where ${\displaystyle (a_{i}+b_{j}-N)^{+}}$ denotes ${\displaystyle \max(1,a_{i}+b_{j}-N)}$. The variables ${\displaystyle a_{i}}$ and ${\displaystyle b_{j}}$ are partial sums of the contingency table; that is,

${\displaystyle a_{i}=\sum _{j=1}^{C}n_{ij}}$

and

${\displaystyle b_{j}=\sum _{i=1}^{R}n_{ij}}$

The adjusted measure[1] for the mutual information may then be defined to be:

${\displaystyle AMI(U,V)={\frac {MI(U,V)-E\{MI(U,V)\}}{\max {\{H(U),H(V)\}}-E\{MI(U,V)\}}}}$.

The AMI takes a value of 1 when the two partitions are identical and 0 when the MI between two partitions equals the value expected due to chance alone.

• Matlab code for computing the adjusted mutual information
• R code for fast and parallel calculation of adjusted mutual information
• Python code for computing the adjusted mutual information