Normalized Mutual Information(NMI, 归一化互信息)

Normalized Mutual Information(NMI, 归一化互信息)

• 值域是 $[0,1]$，值越高表示两个聚类结果越相似。归一化是指将两个聚类结果的相似性值定量到 $0\sim 1$ 之间。

$$
\text{NMI}=\frac{2\sum_i\sum_jn_{ij}ln\frac{n_{ij}N}{n_in_j}}{-\sum_in_iln\frac{n_i}{N}-\sum_jn_jln\frac{n_j}{N}}
$$

$$
\text{NMI(Y,C)}=\frac{2\times I(Y;C)}{H(Y)+H(C)}
$$

• 其中Y代表数据真实的类别；C表示聚类的结果。
• $H(\cdot)$ 表示信息熵，$H(X)=-\sum_{i=1}^N p(i)\log\ p(i)$，此处的 $log$ 以2为底。
• $I(Y;C)$ 代表互信息， $I(Y;C)=H(Y)-H(Y|C)$ ，互信息是信息论里的一种信息度量，可以看成是一个随机变量中包含的关于另一个随机变量的信息量。

例子

假定共有20个样本，真实类簇为3个，而模型学习得到2个类簇，如下：

1. 计算 $Y$ 的信息熵 $H(Y)$

   H(Y) 表示数据真实标签的交叉熵，它是一个固定的值。可以在聚类之前计算出。
   $$
   \begin{split}
   H(Y)&=-\sum_{y=1}^3 P(Y=y)logP(Y=y)\
   &=-(\frac{1}{4}log(\frac{1}{4})+\frac{1}{4}log(\frac{1}{4})+\frac{1}{2}log(\frac{1}{2}))\
   &=1.5\ bit
   \end{split}
   $$

2. 计算 $C$ 的信息熵
   $$
   \begin{split}
   H(C)&=-\sum_{c=1}^3 P(C=c)logP(C=c)\
   &=-(\frac{1}{2}log(\frac{1}{2})+\frac{1}{2}log(\frac{1}{2}))\
   &=1\ bit
   \end{split}
   $$

3. 计算 $Y$ 和 $C$ 的互信息
   $$
   \begin{split}
   H(Y|C)&=H(Y|C=1)+H(Y|C=2)\
   &=-P(C=1)\sum_{y=1}^3 P(Y=y|C=1)logP(Y=y|C=1)\
   &-P(C=2)\sum_{y=1}^3 P(Y=y|C=2)logP(Y=y|C=2)\
   &=-\frac{1}{2}(\frac{3}{10}log(\frac{3}{10})+\frac{3}{10}log(\frac{3}{10})+\frac{4}{10}log(\frac{4}{10})\
   & +\frac{2}{10}log(\frac{2}{10})+\frac{7}{10}log(\frac{7}{10})+\frac{1}{10}log(\frac{1}{10}))\
   &=1.3639\ bit
   \end{split}
   $$

   $$
   \begin{split}
   I(Y;C)&=H(Y)-H(Y|C)\
   &=1.5-1.3639\
   &=0.1361\ bit
   \end{split}
   $$

4. 计算 $Y$ 和 $C$ 的归一化互信息

$$
\begin{split}
\text{NMI(Y,C)}&=\frac{2\times I(Y;C)}{H(Y)+H(C)}\
&=\frac{2\times 0.1361}{1.5+1}\
&=0.1089
\end{split}
$$