聚类的评价指标NMI标准化互信息+python实现+sklearn调库

概念

标准化互信息（normalized Mutual Information, NMI）用于度量聚类结果的相似程度，是community detection的重要指标之一，其取值范围在[0 1]之间，值越大表示聚类结果越相近，且对于[1, 1, 1, 2] 和 [2, 2, 2, 1]的结果判断为相同

引例

对于6个点(v1, v2, …, v6)，若聚成3个类
真实值为v1, v2, v3一个类，v4一个类，v5，v6一个类，则其结果可写为[1, 1, 1, 2, 3, 3] （相同的数字表示对应的id属于同一个类）

通过自己的聚类算法，得到v1, v4一个类，v2, v5一个类 v3, v6一个类，则结果为[1, 2, 3, 1, 2, 3]

如何度量算法结果与标准结果之间的相似度，使结果越相似，值应接近1；如果算法结果很差则值接近0？

公式

信息熵

$$H(X)=-\sum _{i}p\left(x_i\right)\log p\left(x_i\right)$$

相对熵（relative entropy）

又被称为Kullback-Leibler散度（Kullback-Leibler divergence，KL散度）或信息散度（information divergence）

是两个概率分布（probability distribution）间差异的非对称性度量 。在在信息理论中，相对熵等价于两个概率分布的信息熵（Shannon entropy）的差值

设p(x),q(x)是随机变量X上的两个概率分布，则在离散与连续随机变量的情形下，相对熵的定义分别为： K L ( p ∥ q ) = ∑ p ( x ) log ⁡ p ( x ) q ( x ) K L ( p ∥ q ) = ∫ p ( x ) log ⁡ p ( x ) q ( x )

$$\begin{array}{l} K L(p \| q)=\sum p(x) \log \frac{p(x)}{q(x)} \\ \\ K L(p \| q)=\int p(x) \log \frac{p(x)}{q(x)} \end{array}$$ KL(p∥q)=∑p(x)logq(x)p(x)​KL(p∥q)=∫p(x)logq(x)p(x)​​
KL散度可以理解为两个概率分布的距离，但不是真的距离，即p对q的相对熵与q对p的相对熵不相等。

互信息

互信息(Mutual Information)是信息论里一种有用的信息度量，它可以看成是一个随机变量中包含的关于另一个随机变量的信息量，或者说是一个随机变量由于已知另一个随机变量而减少的不肯定性。

设两个随机变量 $(X,Y)$的联合分布为 $p(x,y)$，边缘分布分别为 $p(x),p(y)$

互信息 $I(X;Y)$ 是联合分布 $p(x,y)$与乘积分布 $p(x)(y)$ 的相对熵，即公式为：
$$I(X;Y)=\sum _x\sum _{y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$$

*归一化互信息(NMI)

将互信息缩放在[0,1]之间。比较常见的归一化方法：
$$NMI(X;Y)=2\frac{I(X;Y)}{H(X)+H(Y)}$$

代码

python

# -*- coding:utf-8 -*-
'''
Created on 2017年10月28日

@summary: 利用Python实现NMI计算

@author: dreamhome
'''
import math
import numpy as np
from sklearn import metrics
def NMI(A,B):
    #样本点数
    total = len(A)
    A_ids = set(A)
    B_ids = set(B)
    #互信息计算
    MI = 0
    eps = 1.4e-45
    for idA in A_ids:
        for idB in B_ids:
            idAOccur = np.where(A==idA)
            idBOccur = np.where(B==idB)
            idABOccur = np.intersect1d(idAOccur,idBOccur)
            px = 1.0*len(idAOccur[0])/total
            py = 1.0*len(idBOccur[0])/total
            pxy = 1.0*len(idABOccur)/total
            MI = MI + pxy*math.log(pxy/(px*py)+eps,2)
    # 标准化互信息
    Hx = 0
    for idA in A_ids:
        idAOccurCount = 1.0*len(np.where(A==idA)[0])
        Hx = Hx - (idAOccurCount/total)*math.log(idAOccurCount/total+eps,2)
    Hy = 0
    for idB in B_ids:
        idBOccurCount = 1.0*len(np.where(B==idB)[0])
        Hy = Hy - (idBOccurCount/total)*math.log(idBOccurCount/total+eps,2)
    MIhat = 2.0*MI/(Hx+Hy)
    return MIhat

if __name__ == '__main__':
    A = np.array([1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3])
    B = np.array([1,2,1,1,1,1,1,2,2,2,2,3,1,1,3,3,3])
    print NMI(A,B)
    print metrics.normalized_mutual_info_score(A,B)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

标准化互信息NMI计算步骤及其Python实现 https://blog.csdn.net/DreamHome_S/article/details/78379635?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.baidujs&dist_request_id=1328603.9611.16149098780214877&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.baidujs

sklearn

from sklearn import metrics
A = [1, 1, 1, 2, 3, 3]
B = [1, 2, 3, 1, 2, 3]
result_NMI=metrics.normalized_mutual_info_score(A, B)
print("result_NMI:",result_NMI)
1
2
3
4
5