精华内容
下载资源
问答
  • 标准化互信息NMI计算步骤及其Python实现

    万次阅读 多人点赞 2017-10-28 21:37:19
    Excellence is a continuous process and not an ...标准化互信息NMI计算步骤及其Python实现 标准化互信息NMI具体定义可以参考另一篇博客: https://smj2284672469.github.io/2017/10/27/community-detection-mea

    Excellence is a continuous process and not an accident.

    卓越是一个持续的过程而不是一个偶然事件。

    原文地址:https://dreamhomes.github.io/posts/202005120940.html

    标准化互信息NMI计算步骤及其Python实现

    假设对于17个样本点 ( v 1 , v 2 , . . . , v 17 ) (v_1,v_2,...,v_{17}) (v1,v2,...,v17)进行聚类:

    某一种算法得到聚类结果为:

    A=[1 2 1 1 1 1 1 2 2 2 2 3 1 1 3 3 3]

    标准的聚类结果为:

    B=[1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3]

    问题:需要度量算法结果与标准结果之间的相似度,如果结果越相似NMI值应接近1;如果算法结果很差则NMI值接近0。

    根据公式计算MI的值其中X=unique(A)=[1 2 3] , Y=unique(B)=[1 2 3]:

    M I ( X , Y ) = ∑ i = 1 ∣ X ∣ ∑ j = 1 ∣ Y ∣ P ( i , j ) l o g ( P ( i , j ) P ( i ) P ′ ( j ) ) MI(X,Y)=\sum_{i=1}^{|X|}\sum_{j=1}^{|Y|}P(i,j)log(\frac{P(i,j)}{P(i)P^{'}(j)}) MI(X,Y)=i=1Xj=1YP(i,j)log(P(i)P(j)P(i,j))

    首先计算上式分子中联合概率分布 P ( i , j ) = ∣ X i ∩ Y j ∣ N P(i,j)=\frac{|X_i\cap Y_j|}{N} P(i,j)=NXiYj

    P ( 1 , 1 ) = 5 / 17 , P ( 1 , 2 ) = 1 / 17 , P ( 1 , 3 ) = 2 / 17 P(1,1)=5/17,P(1,2)=1/17,P(1,3)=2/17 P(1,1)=5/17,P(1,2)=1/17,P(1,3)=2/17

    P ( 2 , 1 ) = 1 / 17 , P ( 2 , 2 ) = 4 / 17 , P ( 2 , 3 ) = 0 P(2,1)=1/17,P(2,2)=4/17,P(2,3)=0 P(2,1)=1/17,P(2,2)=4/17,P(2,3)=0

    P ( 3 , 1 ) = 0 , P ( 3 , 2 ) = 1 / 17 , P ( 3 , 3 ) = 3 / 17 P(3,1)=0,P(3,2)=1/17,P(3,3)=3/17 P(3,1)=0,P(3,2)=1/17,P(3,3)=3/17

    再计算分母中概率函数 P ( i ) = X i / N P(i)=X_i/N P(i)=Xi/N P ( i ) P(i) P(i) i i i的概率分布函数, P ′ ( j ) P^{'}(j) P(j) j j j的概率分布函数:

    对于 P ( i ) P(i) P(i)

    P ( 1 ) = 8 / 17 , P ( 2 ) = 5 / 17 , p ( 3 ) = 4 / 17 P(1)=8/17,P(2)=5/17,p(3)=4/17 P(1)=8/17,P(2)=5/17,p(3)=4/17

    对于 P ( j ) P(j) P(j)

    P ′ ( 1 ) = 6 / 17 , P ′ ( 2 ) = 6 / 17 , P ′ ( 3 ) = 5 / 17 P^{'}(1)=6/17,P^{'}(2)=6/17,P^{'}(3)=5/17 P(1)=6/17,P(2)=6/17,P(3)=5/17

    根据以上计算可以计算出MI的值。

    至于标准化互信息使用第二个公式计算:

    N M I ( X , Y ) = 2 M I ( X , Y ) H ( X ) + H ( Y ) NMI(X,Y)=\frac{2MI(X,Y)}{H(X)+H(Y)} NMI(X,Y)=H(X)+H(Y)2MI(X,Y)

    上式分母中 H ( X ) , H ( Y ) H(X),H(Y) H(X),H(Y)分别为 X , Y X,Y X,Y的熵:

    H ( X ) = − ∑ i = 1 ∣ X ∣ P ( i ) l o g ( P ( i ) ) ; H ( Y ) = − ∑ j = 1 ∣ Y ∣ P ′ ( j ) l o g ( P ′ ( j ) ) H(X)=-\sum_{i=1}^{|X|}P(i)log(P(i));H(Y)=-\sum_{j=1}^{|Y|}P^{'}(j)log(P^{'}(j)) H(X)=i=1XP(i)log(P(i));H(Y)=j=1YP(j)log(P(j))

    对于上面的例子,根据公式计算熵如下:

    H ( X ) = P ( 1 ) l o g 2 ( P ( 1 ) ) + P ( 2 ) l o g 2 ( P ( 2 ) ) + P ( 3 ) l o g 2 ( P ( 3 ) ) H(X)=P(1)log_2(P(1))+P(2)log_2(P(2))+P(3)log_2(P(3)) H(X)=P(1)log2(P(1))+P(2)log2(P(2))+P(3)log2(P(3))

    H ( Y ) = P ′ ( 1 ) l o g 2 ( P ′ ( 1 ) ) + P ′ ( 2 ) l o g 2 ( P ′ ( 2 ) ) + P ′ ( 3 ) l o g 2 ( P ′ ( 3 ) ) H(Y)=P^{'}(1)log_2(P^{'}(1))+P^{'}(2)log_2(P^{'}(2))+P^{'}(3)log_2(P^{'}(3)) H(Y)=P(1)log2(P(1))+P(2)log2(P(2))+P(3)log2(P(3))

    综上则可以计算出NMI的值。

    代码实现以上计算过程:

    • 可以直接调用scikit-learn包中集成的度量函数
    • 自己编写函数实现计算过程

    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)
    
    展开全文
  • 使用具有标准化互信息的层次框架对医学图像进行非刚性配准
  • 这里给出三个聚类效果评价指标:互信息,标准化互信息,调整互信息(MI, NMI, AMI),分别给出它们的计算方法与代码。需要指出的是,这三个指标均需要已知数据点的真实标签。 Preliminaries and Notation 已知 NNN 个...

    聚类效果评价指标:MI, NMI, AMI(互信息,标准化互信息,调整互信息)

    简介

    在无监督学习中,常见的两种任务为聚类与降维。这里给出三个聚类效果评价指标:互信息,标准化互信息,调整互信息(MI, NMI, AMI),分别给出它们的计算方法与代码。需要指出的是,这三个指标均需要已知数据点的真实标签。

    Preliminaries and Notation

    已知 N N N D D D 维的数据,构成数据矩阵 X = [ x 1 , x 2 , ⋯   , x N ] ∈ R D × N \mathbf{X} = [x_1, x_2, \cdots, x_N] \in \mathbb{R}^{D\times N} X=[x1,x2,,xN]RD×N

    对每个数据 x i ∈ R D × 1 x_i \in \mathbb{R}^{D\times 1} xiRD×1 ,其对应标签(label)为 u i ∈ R u_i \in \mathbb{R} uiR

    标签中共有 R R R 个不同的取值,或者说数据共有 R R R 类,其对应的标签组成向量 U = [ u 1 , u 2 , ⋯   , u N ] ∈ R N U = [u_1, u_2, \cdots, u_N] \in \mathbb{R}^N U=[u1,u2,,uN]RN

    我们取自然数 1 1 1 N N N 来为这 N N N 个数据点依次编号,并取 S = { 1 , 2 , ⋯   , N } S = \left\{1, 2, \cdots, N\right\} S={1,2,,N} ,则有
    S = ∪ i = 1 R U i = { U 1 , U 2 , ⋯   , U R } S = \mathop{\cup}\limits_{i=1}^R U_i = \left\{U_1, U_2, \cdots, U_R\right\} S=i=1RUi={U1,U2,,UR}
    其中 U i U_i Ui 代表归属于第 i i i 类的数据集合;如对向量 U = [ 1 , 1 , 2 , 2 , 3 , 3 , 3 ] U = [1, 1, 2, 2, 3, 3, 3] U=[1,1,2,2,3,3,3] ,则有
    N = 7 , R = 3 , U 1 = { 1 , 2 } , U 2 = { 3 , 4 } , U 3 = { 5 , 6 , 7 } N = 7, R = 3, U_1 = \left\{1, 2\right\}, U_2 = \left\{3, 4\right\}, U_3 = \left\{5, 6, 7 \right\} N=7,R=3,U1={1,2},U2={3,4},U3={5,6,7}

    这里需要指出的是,如果整个数据集共有5类,则我们默认用自然数1至5来代表这5类;

    对于 U U U 而言,其包含 R R R 类,则用自然数 1 1 1 R R R 来代表这 R R R 个类别。

    所谓聚类问题,即为对原始数据集 X \mathbf{X} X 进行一种划分;通过某种聚类算法(如DBSCAN、谱聚类等),我们可以得到一个对 X \mathbf{X} X 的划分,即 V = [ v 1 , v 2 , ⋯   , v N ] ∈ R N V = [v_1, v_2, \cdots, v_N] \in \mathbb{R}^N V=[v1,v2,,vN]RN

    类似地,我们有
    S = ∪ i = 1 C V i = { V 1 , V 2 , ⋯   , V C } S = \mathop{\cup}\limits_{i=1}^C V_i = \left\{V_1, V_2, \cdots, V_C \right\} S=i=1CVi={V1,V2,,VC}
    其中 V i V_i Vi 代表聚类结果中归属于第 i i i 类的数据集合。

    信息熵与列联表(contingency table)

    在介绍互信息之前,首先介绍一下香农熵(信息熵)和列联表(contingency table)。

    对上述标签向量 U ∈ R N U \in \mathbb{R}^N URN ,其香农熵(信息熵)可以被计算为:
    H ( U ) = − ∑ i = 1 R p i log ⁡ p i (1) \text{H}(U) = -\sum_{i=1}^R p_i \log p_i \tag{1} H(U)=i=1Rpilogpi(1)
    其中对数函数的底常取 2 2 2 或自然对数 e e e

    p i p_i pi 为归属于第 i i i 类的数据个数占数据总量的比例,即
    p i = ∣ U i ∣ N (2) p_i = \frac{\left| U_i \right|}{N} \tag{2} pi=NUi(2)

    如对向量 U = [ 1 , 1 , 1 ] U = [1, 1, 1] U=[1,1,1] ,则有 p 1 = 1 p_1 = 1 p1=1 H ( U ) = − 1 ⋅ log ⁡ ( 1 ) = 0 \text{H} (U) = - 1 \cdot \log(1) = 0 H(U)=1log(1)=0

    对向量 U = [ 1 , 2 , 3 ] U = [1, 2, 3] U=[1,2,3] ,则有 p 1 = p 2 = p 3 = 1 3 p_1 = p_2 = p_3 = \frac{1}{3} p1=p2=p3=31 H ( U ) = − 3 ⋅ 1 3 ⋅ log ⁡ ( 1 3 ) = log ⁡ 3 \text{H} (U) = - 3 \cdot \frac{1}{3} \cdot \log(\frac{1}{3}) = \log 3 H(U)=331log(31)=log3

    对向量 U = [ 1 , 2 , 2 ] U = [1, 2, 2] U=[1,2,2] ,则有 p 1 = 1 3 , p 2 = 2 3 p_1 = \frac{1}{3}, p_2 = \frac{2}{3} p1=31,p2=32 H ( U ) = − 1 3 ⋅ log ⁡ ( 1 3 ) − 2 3 ⋅ log ⁡ ( 2 3 ) = log ⁡ 3 − 2 3 ⋅ log ⁡ 2 \text{H} (U) = - \frac{1}{3} \cdot \log(\frac{1}{3}) - \frac{2}{3} \cdot \log(\frac{2}{3}) = \log 3 - \frac{2}{3} \cdot \log2 H(U)=31log(31)32log(32)=log332log2

    不难发现,信息熵是非负的,因为 0 < p i ≤ 1 0 < p_i \leq 1 0<pi1

    我们取矩阵 M ∈ R R × C M \in \mathbb{R}^{R\times C} MRR×C 为真实标签向量 U U U 与预测标签向量 V V V 的列联表(contingency table),满足
    m i j = ∣ U i ∩ V j ∣ (3) m_{ij} = \left|U_i \cap V_j\right| \tag{3} mij=UiVj(3)
    其中 i = 1 , 2 , ⋯   , R i = 1, 2, \cdots, R i=1,2,,R j = 1 , 2 , ⋯   , C j = 1, 2, \cdots, C j=1,2,,C

    如对向量 U = [ 1 , 1 , 2 , 2 ] , V = [ 1 , 1 , 1 , 2 ] U = [1, 1, 2, 2], V = [1, 1, 1, 2] U=[1,1,2,2],V=[1,1,1,2] ,有
    U 1 = { 1 , 2 } U 2 = { 3 , 4 } V 1 = { 1 , 2 , 3 } V 2 = { 4 } \begin{aligned}U_1 &= \left\{1, 2\right\} & U_2 &= \left\{3, 4\right\} \\V_1 &= \left\{1, 2, 3\right\} & V_2 &= \left\{4\right\}\end{aligned} U1V1={1,2}={1,2,3}U2V2={3,4}={4}
    因此,
    m 11 = ∣ U 1 ∩ V 1 ∣ = ∣ { 1 , 2 } ∣ = 2 m 12 = ∣ U 1 ∩ V 2 ∣ = ∣ ∅ ∣ = 0 m 21 = ∣ U 2 ∩ V 1 ∣ = ∣ { 3 } ∣ = 1 m 22 = ∣ U 2 ∩ V 2 ∣ = ∣ { 4 } ∣ = 1 \begin{aligned} m_{1 1} & = \left|U_1 \cap V_1\right| = \left|\left\{1, 2\right\}\right| = 2 \\ m_{1 2} & = \left|U_1 \cap V_2\right| = \left|\varnothing\right| = 0 \\ m_{2 1} & = \left|U_2 \cap V_1\right| = \left|\left\{3 \right\}\right| = 1 \\ m_{2 2} & = \left|U_2 \cap V_2\right| = \left|\left\{4 \right\}\right| = 1 \\ \end{aligned} m11m12m21m22=U1V1={1,2}=2=U1V2==0=U2V1={3}=1=U2V2={4}=1

    列联表为

    M = [ 2 0 1 1 ] M = \left[ \begin{array}{l} 2 & 0 \\ 1 & 1 \end{array} \right] M=[2101]

    互信息(Mutual information)

    互信息的计算公式如下:

    MI ( U , V ) = ∑ i = 1 R ∑ i = 1 C p i , j log ⁡ ( p i , j p i × p j ) (4) \text{MI}(U, V) = \sum_{i = 1}^R\sum_{i=1}^C p_{i,j} \log\left(\frac{p_{i, j}}{p_i \times p_j}\right) \tag{4} MI(U,V)=i=1Ri=1Cpi,jlog(pi×pjpi,j)(4)
    其中
    p i , j = ∣ U i ∩ V j ∣ N = m i j N (5) p_{i,j} = \frac{\left|U_i \cap V_j \right|}{N} = \frac{m_{ij}}{N} \tag{5} pi,j=NUiVj=Nmij(5)

    p i = ∣ U i ∣ N , p j = ∣ V j ∣ N p_i = \frac{\left| U_i \right|}{N}, p_j = \frac{\left| V_j \right|}{N} pi=NUi,pj=NVj

    如对向量 U = [ 1 , 1 , 2 , 2 ] , V = [ 1 , 1 , 1 , 2 ] U = [1, 1, 2, 2], V = [1, 1, 1, 2] U=[1,1,2,2],V=[1,1,1,2] ,有
    p 1 , 1 = m 11 / N = 0.5 p 1 , 2 = m 12 / N = 0 p 2 , 1 = m 21 / N = 0.25 p 2 , 2 = m 22 / N = 0.25 \begin{aligned} p_{1, 1} & = m_{11} / N = 0.5 \\ p_{1, 2} & = m_{12} / N = 0 \\ p_{2, 1} & = m_{21} / N = 0.25 \\ p_{2, 2} & = m_{22} / N = 0.25 \\ \end{aligned} p1,1p1,2p2,1p2,2=m11/N=0.5=m12/N=0=m21/N=0.25=m22/N=0.25

    标准化互信息(NMI, Normalized Mutual Information)

    通常采用NMI和AMI来作为衡量聚类效果的指标。

    标准化互信息的计算方法如下:

    NMI ( U , V ) = MI ( U , V ) F ( H ( U ) , H ( V ) ) (6) \text{NMI}(U, V) = \frac{\text{MI}(U, V)}{F\left(\text{H}\left(U\right), \text{H}\left(V\right)\right)} \tag{6} NMI(U,V)=F(H(U),H(V))MI(U,V)(6)

    其中 F ( x 1 , x 2 ) F(x_1, x_2) F(x1,x2) 可以为 min ⁡ \min min/ max ⁡ \max max 函数;可以为几何平均,即 F ( x 1 , x 2 ) = x 1 x 2 F(x_1, x_2) = \sqrt{x_1x_2} F(x1,x2)=x1x2 ;可以为算术平均,即 F ( x 1 , x 2 ) = x 1 + x 2 2 F(x_1, x_2) = \frac{x_1 + x_2}{2} F(x1,x2)=2x1+x2

    通常我们选取算术平均,则标准化互信息即可被计算为
    NMI ( U , V ) = 2 MI ( U , V ) H ( U ) + H ( V ) (7) \text{NMI}(U, V) = 2 \frac{\text{MI}(U, V)}{\text{H}\left(U\right) + \text{H}\left(V\right)} \tag{7} NMI(U,V)=2H(U)+H(V)MI(U,V)(7)

    调整互信息(AMI, Adjusted Mutual Information)

    调整互信息的计算要复杂一些,其计算方法如下:

    AMI ( U , V ) = MI ( U , V ) − E { MI ( U , V ) } F ( H ( U ) , H ( V ) ) − E { MI ( U , V ) } (8) \text{AMI}(U, V) = \frac{\text{MI}(U, V) - \mathbb E\left\{ \text{MI}(U, V) \right\}}{F\left(\text{H}\left(U\right), \text{H}\left(V\right)\right) - \mathbb E\left\{ \text{MI}(U, V) \right\}} \tag{8} AMI(U,V)=F(H(U),H(V))E{MI(U,V)}MI(U,V)E{MI(U,V)}(8)

    其中, E { MI ( U , V ) } \mathbb E\left\{ \text{MI}(U, V) \right\} E{MI(U,V)} 为互信息 MI ( U , V ) \text{MI}(U, V) MI(U,V) 的期望,计算方法为
    E { MI ( U , V ) } = ∑ i = 1 R ∑ j = 1 C ∑ k = ( a i + b j − N ) + min ⁡ ( a i , b j ) k N log ⁡ ( N × k a i × b j ) a i ! b j ! ( N − a i ) ! ( N − b j ) ! N ! k ! ( a i − k ) ! ( b j − k ) ! ( N − a i − b j + k ) ! (9) \begin{aligned} \mathbb E\left\{ \text{MI}(U, V) \right\} &= \\ \sum_{i=1}^R \sum_{j=1}^C &\sum_{k = \left(a_i + b_j - N \right)^+}^{\min \left(a_i, b_j\right)} \frac{k}{N} \log\left(\frac{N \times k}{a_i \times b_j}\right)\frac{a_i!b_j!\left(N - a_i\right)!\left(N - b_j\right)!}{N!k!\left(a_i - k\right)!\left(b_j - k\right)!\left(N - a_i - b_j + k\right)!} \end{aligned} \tag{9} E{MI(U,V)}i=1Rj=1C=k=(ai+bjN)+min(ai,bj)Nklog(ai×bjN×k)N!k!(aik)!(bjk)!(Naibj+k)!ai!bj!(Nai)!(Nbj)!(9)
    其中 ( a i + b j − N ) + \left(a_i + b_j - N \right)^+ (ai+bjN)+ max ⁡ ( 1 , a i + b j − N ) \max \left(1, a_i + b_j - N \right) max(1,ai+bjN)

    a i , b j a_i, b_j ai,bj 分别为列联表 M M M 的第 i i i 行和与第 j j j 列和,具体为
    a i = ∑ j = 1 C m i j b j = ∑ i = 1 R m i j (10) \begin{aligned} a_i = \sum_{j=1}^C m_{ij} \\ b_j = \sum_{i=1}^R m_{ij} \end{aligned} \tag{10} ai=j=1Cmijbj=i=1Rmij(10)
    如果我们选取函数 F ( x 1 , x 2 ) F(x_1, x_2) F(x1,x2) max ⁡ \max max 函数,则调整互信息可被计算为
    AMI ( U , V ) = MI ( U , V ) − E { MI ( U , V ) } max ⁡ ( H ( U ) , H ( V ) ) − E { MI ( U , V ) } (11) \text{AMI}(U, V) = \frac{\text{MI}(U, V) - \mathbb E\left\{ \text{MI}(U, V) \right\}}{\max\left(\text{H}\left(U\right), \text{H}\left(V\right)\right) - \mathbb E\left\{ \text{MI}(U, V) \right\}} \tag{11} AMI(U,V)=max(H(U),H(V))E{MI(U,V)}MI(U,V)E{MI(U,V)}(11)

    如果我们选取函数 F ( x 1 , x 2 ) F(x_1, x_2) F(x1,x2) 为几何平均,则调整互信息可被计算为

    AMI ( U , V ) = MI ( U , V ) − E { MI ( U , V ) } H ( U ) ⋅ H ( V ) − E { MI ( U , V ) } (12) \text{AMI}(U, V) = \frac{\text{MI}(U, V) - \mathbb E\left\{ \text{MI}(U, V) \right\}}{\sqrt{\text{H}\left(U\right) \cdot \text{H}\left(V\right)} - \mathbb E\left\{ \text{MI}(U, V) \right\}} \tag{12} AMI(U,V)=H(U)H(V) E{MI(U,V)}MI(U,V)E{MI(U,V)}(12)

    如果我们选取函数 F ( x 1 , x 2 ) F(x_1, x_2) F(x1,x2) 为算术平均,则调整互信息可被计算为

    AMI ( U , V ) = MI ( U , V ) − E { MI ( U , V ) } 1 2 ( H ( U ) + H ( V ) ) − E { MI ( U , V ) } (13) \text{AMI}(U, V) = \frac{\text{MI}(U, V) - \mathbb E\left\{ \text{MI}(U, V) \right\}}{\frac{1}{2}\left(\text{H}\left(U\right) + \text{H}\left(V\right)\right) - \mathbb E\left\{ \text{MI}(U, V) \right\}} \tag{13} AMI(U,V)=21(H(U)+H(V))E{MI(U,V)}MI(U,V)E{MI(U,V)}(13)

    编程实现

    Python中的 sklearn 库里有这三个指标的类,可以直接调用;

    matlab中似乎没有找到现成的包,因此自己编写。

    python

    这里NMI和AMI的计算均采用算术平均; log ⁡ \log log 函数的底为自然对数 e e e

    from sklearn.metrics.cluster import entropy, mutual_info_score, normalized_mutual_info_score, adjusted_mutual_info_score
    
    MI = lambda x, y: mutual_info_score(x, y)
    NMI = lambda x, y: normalized_mutual_info_score(x, y, average_method='arithmetic')
    AMI = lambda x, y: adjusted_mutual_info_score(x, y, average_method='arithmetic')
    
    A = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]
    B = [1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 3, 3, 3]
    #print(entropy(A))
    #print(MI(A, B))
    print(NMI(A, B))
    print(AMI(A, B))
    
    C = [1, 1, 2, 2, 3, 3, 3]
    D = [1, 1, 1, 2, 1, 1, 1]
    print(NMI(C, D))
    print(AMI(C, D))
    

    matlab

    这里的NMI与AMI的代码实现均采用的算术平均, log ⁡ \log log 函数的底采用自然对数 e e e

    函数文件:

    NMI_AMI.m

    function [NMI, AMI] = NMI_AMI(X, Y)
    %NMI_AMI return NMI, AMI
    % MI: mutual information
    % H; entropy
    % NMI: normalized mutual infomation
    % AMI: adjusted mutual infomation
    % NMI(X, Y) = MI(X, Y) / F(H(X), H(Y))
    % AMI(X, Y) = (MI(X, Y) - EMI(X, Y)) / (F(H(X) + H(Y)) - EMI(X, Y))
    % F(x, y) is a function, can be "mean", "max", "geometric", "arithmetic"
    % here we both use arithmetric
    
    NMI = 2 * MI(X, Y) / (H(X) + H(Y));
    
    AMI = (MI(X, Y) - EMI(X, Y)) / (1/2 * (H(X) + H(Y)) - EMI(X, Y));
    
    end
    
    
    
    function [res] = MI(X, Y)
    %MI mutual infomation
    
    n = length(X);
    X_list = unique(X);
    Y_list = unique(Y);
    res = 0;
    for x = X_list
        for y = Y_list
            loc_x = find(X == x);
            loc_y = find(Y == y);
            loc_xy = intersect(loc_x, loc_y);
            res = res + length(loc_xy) / n * log(length(loc_xy) / n / ((length(loc_x) / n) * (length(loc_y) / n)) + eps);
        end
    end
    
    end
    
    
    
    function [res] = H(X)
    %H information entropy
    
    n = length(X);
    X_list = unique(X);
    res = 0;
    
    for x = X_list
        loc = find(X == x);
        px = length(loc) / n;
        res = res - px * log(px);
    end
    
    end
    
    
    
    function [res] = f(a, b)
    % F calculate a! / b!
    % sometimes a and b can be very large, hence, directly calculate a! or b! is not
    % suitable; but maybe a-b is small; 
    % a,b should both be positive integers
    
    res = 1;
    if a > b
        for i = b+1:a
            res = res * i;
        end
    elseif a < b
        for i = a+1:b
            res = res / i;
        end
    else
        res = 1;
    end
    
    end
    
    
    
    function [res] = EMI(U, V)
    % EMI expected mutual information, E[MI(X, Y)]
    
    N = length(U);
    
    U_list = unique(U);
    V_list = unique(V);
    R = length(U_list);
    C = length(V_list);
    
    M = zeros(R, C);
    for i = 1:R
        for j = 1:C
            U_loc = find(U == U_list(i));
            V_loc = find(V == V_list(j));
            M(i, j) = length(intersect(U_loc, V_loc));
        end
    end
    
    a = sum(M, 2);
    b = sum(M, 1);
    res = 0;
    
    for i = 1:R
        for j = 1:C
            for nij = max(a(i) + b(j) - N, 1):min(a(i), b(j))
                res = res + nij / N * log(N * nij / (a(i) * b(j)) + eps) * f(a(i), a(i) - nij) * f(b(j), b(j) - nij) * f(N - a(i), N) * f(N - b(j), N - a(i) - b(j) + nij) / factorial(nij);
            end
        end
    end
    
    end
    
    

    主文件(或脚本):

    clc;
    format long
    
    A = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3];
    B = [1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 3, 3, 3];
    [NMI, AMI] = NMI_AMI(A, B)
    
    C = [1, 1, 2, 2, 3, 3, 3];
    D = [1, 1, 1, 2, 1, 1, 1];
    [NMI, AMI] = NMI_AMI(C, D)
    

    结果对比

    python代码的运行结果为:

    0.36456177185718985

    0.26018122538925054

    0.28483386264113447

    0.056748831755324296

    matlab代码的运行结果为:

    NMI =

    0.364561771857190

    AMI =

    0.260181225389251

    NMI =

    0.284833862641135

    AMI =

    0.056748831755324

    总结与反思

    这里仅给出了三个指标的计算方法,方便直接使用;对于各个指标的优缺点、构造思想等,并没有研究。

    References

    1. https://en.wikipedia.org/wiki/Adjusted_mutual_information (科学上网)

    2. Vinh, Nguyen Xuan; Epps, Julien; Bailey, James (2010), “Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance” (PDF), The Journal of Machine Learning Research, 11 (oct): 2837–54

      论文链接:http://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf

    展开全文
  • 标准化互信息的python实现(sklearn)

    万次阅读 2019-05-27 20:06:13
    标准化互信息(normalized Mutual Information, NMI)用于度量聚类结果的相似程度,是community detection的重要指标之一,其取值范围在[0 1]之间,值越大表示聚类结果越相近,且对于[1, 1, 1, 2] 和 [2, 2, 2, 1]的...

    标准化互信息(normalized Mutual Information, NMI)用于度量聚类结果的相似程度,是community detection的重要指标之一,其取值范围在[0 1]之间,值越大表示聚类结果越相近,且对于[1, 1, 1, 2] 和 [2, 2, 2, 1]的结果判断为相同
    其论文可参见Effect of size heterogeneity on community identification in complex networks
    举例说明:
    对于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]
    也可查看Mutual information and Normalized Mutual information 互信息和标准化互信息查看相关解析
    在python中,sklearn已集成了相关计算步骤,直接调用即可:

    from sklearn import metrics
    if __name__ == '__main__':
        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)
    
    result_NMI: 0.30192109848
    
    展开全文
  • Mutual information and Normalized Mutual information 互信息和标准化互信息 实验室最近用到nmi( Normalized Mutual information )评价聚类效果,在网上找了一下这个算法的实现,发现满意的不多. 浙江大学蔡登...
     
    

    实验室最近用到nmi( Normalized Mutual information )评价聚类效果,在网上找了一下这个算法的实现,发现满意的不多.

    浙江大学蔡登教授有一个,http://www.zjucadcg.cn/dengcai/Data/code/MutualInfo.m ,他在数据挖掘届地位很高,他实现这个算法的那篇论文引用率高达三位数。但这个实现,恕个人能力有限,我实在是没有看懂:变量命名极为个性,看的如坠云雾;代码倒数第二行作者自己添加注释why complex,我就更不懂了;最要命的是使用他的函数MutualInfo(L1,L2)得到的结果不等于MutualInfo(L2,L1),没有对称性!

     还有个python的版本http://blog.sun.tc/2010/10/mutual-informationmi-and-normalized-mutual-informationnmi-for-numpy.html,这个感觉很靠谱,作者对nmi的理解和我是一样的。

     

    我的理解来自wiki和stanford,其实很简单,先说一下问题:例如stanford中介绍的一个例子:

     

    比如标准结果是图中的叉叉点点圈圈,我的聚类结果是图中标注的三个圈。

    或者我的结果: A = [1 1 1 1 1 1   2 2 2 2 2 2    3 3 3 3 3];

    标准的结果   : B = [1 2 1 1 1 1   1 2 2 2 2 3    1 1 3 3 3];

    问题:衡量我的结果和标准结果有多大的区别,若我的结果和他的差不多,结果应该为1,若我做出来的结果很差,结果应趋近于0。 


     

    MI可以按照下面的公式计算。X=unique(A)=[1 2 3],Y=unique(B)=[1 2 3];

     

     

    分子p(x,y)为x和y的联合分布概率,

    p(1,1)=5/17, p(1,2)=1/17, p(1,3)=0;

    p(2,1)=1/17, p(2,2)=4/17, p(2,3)=1/17;

    p(3,1)=2/17, p(3,2)=0, p(3,3)=3/17;

    分母p(x)为x的概率函数,p(y)为y的概率函数,x和y分别来自于A和B中的分布,所以即使x=y时,p(x)和p(y)也可能是不一样的。

    对p(x): p(1)=6/17 p(2)=6/17 p(3)=5/17

    对p(y): p(1)=8/17 p(2)=5/17 P(3)=4/17 

    这样就可以算出MI值了。

     

    标准化互聚类信息也很简单,有几个不同的版本,大体思想都是相同的,都是用熵做分母将MI值调整到0与1之间。一个比较多见的实现是下面所示:

     

    H(X)和H(Y)分别为X和Y的熵,下面的公式中log的底b=2。

     

    例如H(X) =  -p(1)*log2(p(1)) - -p(2)*log2(p(2)) -p(3)*log2(p(3))。

     

    matlab实现代码如下

    复制代码
    function MIhat = nmi( A, B ) 

    %NMI Normalized mutual information
    % http://en.wikipedia.org/wiki/Mutual_information
    % http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html

    % Author: http://www.cnblogs.com/ziqiao/   [2011/12/13] 

    if length( A ) ~= length( B)
        error('length( A ) must == length( B)');
    end
    total = length(A);
    A_ids = unique(A);
    B_ids = unique(B);

    % Mutual information
    MI = 0;
    for idA = A_ids
        for idB = B_ids
             idAOccur = find( A == idA );
             idBOccur = find( B == idB );
             idABOccur = intersect(idAOccur,idBOccur); 
             
             px = length(idAOccur)/total;
             py = length(idBOccur)/total;
             pxy = length(idABOccur)/total;
             
             MI = MI + pxy*log2(pxy/(px*py)+eps); % eps : the smallest positive number

        end
    end

    % Normalized Mutual information
    Hx = 0; % Entropies
    for idA = A_ids
        idAOccurCount = length( find( A == idA ) );
        Hx = Hx - (idAOccurCount/total) * log2(idAOccurCount/total + eps);
    end
    Hy = 0; % Entropies
    for idB = B_ids
        idBOccurCount = length( find( B == idB ) );
        Hy = Hy - (idBOccurCount/total) * log2(idBOccurCount/total + eps);
    end

    MIhat = 2 * MI / (Hx+Hy);
    end

    % Example :  
    % (http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html)
    % A = [1 1 1 1 1 1   2 2 2 2 2 2    3 3 3 3 3];
    % B = [1 2 1 1 1 1   1 2 2 2 2 3    1 1 3 3 3];
    % nmi(A,B)

    % ans = 0.3646  

    复制代码


    为了节省运行时间,将for循环用矩阵运算代替,1百万的数据量运行 1.795723second,上面的方法运行3.491053 second;  

    但是这种方法太占内存空间, 五百万时,利用matlab2011版本的内存设置就显示Out of memory了。

    复制代码
    function MIhat = nmi( A, B )
    %NMI Normalized mutual information
    % http://en.wikipedia.org/wiki/Mutual_information
    % http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering- 1.html
    % Author: http://www.cnblogs.com/ziqiao/   [2011/12/15] 

    if length( A ) ~= length( B)
        error('length( A ) must == length( B)');
    end
    total = length(A);
    A_ids = unique(A);
    A_class = length(A_ids);
    B_ids = unique(B);
    B_class = length(B_ids);
    % Mutual information
    idAOccur = double (repmat( A, A_class, 1) == repmat( A_ids', 1, total ));
    idBOccur = double (repmat( B, B_class, 1) == repmat( B_ids', 1, total ));
    idABOccur = idAOccur * idBOccur';
    Px = sum(idAOccur') / total;
    Py = sum(idBOccur') / total;
    Pxy = idABOccur / total;
    MImatrix = Pxy .* log2(Pxy ./(Px' * Py)+eps);
    MI = sum(MImatrix(:))
    % Entropies
    Hx = -sum(Px .* log2(Px + eps),2);
    Hy = -sum(Py .* log2(Py + eps),2);
    %Normalized Mutual information
    MIhat = 2 * MI / (Hx+Hy);

    % MIhat = MI / sqrt(Hx*Hy); another version of NMI

    end

    % Example :  
    % (http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html)
    % A = [1 1 1 1 1 1   2 2 2 2 2 2    3 3 3 3 3];
    % B = [1 2 1 1 1 1   1 2 2 2 2 3    1 1 3 3 3];
    % nmi(A,B) 

    % ans =  0.3646

    复制代码


     

    参考: stanford的讲解:http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html

       wiki百科的讲解:http://en.wikipedia.org/wiki/Mutual_information 

    某作者的python的实现:http://blog.sun.tc/2010/10/mutual-informationmi-and-normalized-mutual-informationnmi-for-numpy.html  

          蔡登的matlab实现:http://www.zjucadcg.cn/dengcai/Data/code/MutualInfo.m 

    展开全文
  • 标准化互信息NMI计算步骤及其Python实现 Excellence is a continuous process and not an accident. 卓越是一个持续的过程而不是一个偶然事件. 标准化互信息NMI计算步骤及其Python实现 本文介绍其计算...
  • 对于NMI计算的python实现
  • 1.NMI指数,互信息和标准化互信息      具体公式和matlab代码参见博客,Python代码参加,C++代码参见 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
  • NMI(标准化互信息) python实现

    万次阅读 多人点赞 2017-03-14 15:26:53
    介绍NMI是社区发现(community detection)在有标准ground-truth的情况下的重要衡量指标,基本可以比较客观地评价出一个社区划分与标准划分之间相比的准确度。NMI的值域是0到1,越高代表划分得越准。具体的原理和例子...
  • 为了在特征选择过程中得到较优的特征子集, 结合标准化互信息和遗传算法提出了一种新的两阶段特征选择方法。该方法首先采用标准化的互信息对特征进行排序, 然后用排序在前的特征初始化第二阶段遗传算法的部分种群, ...
  • DMTF (分布式管理工作组)通过开放云计算标准孵化器致力于操作和安全机制方面的标准化。 ETSI (欧洲电信标准协会)致力于信息技术和电信融合的问题。 NIST (国家标准核技术研究院)致力于云计算概念的...
  • 全民健康信息互联互通标准化成熟度测评(以下简称:区域测评)是互联 通测评的重要组成部分,通过对各级卫生健康委组织建设的以电子健康档案和区域全 民健康信息平台为核心的区域全民健康信息化项目进行标准符合性...
  • 为了在特征选择过程中得到较优的特征子集, 结合标准化互信息和遗传算法提出了一种新的两阶段特征选择方法。该方法首先采用标准化的互信息对特征进行排序, 然后用排序在前的特征初始化第二阶段遗传算法的部分种群, ...
  • 互信息

    千次阅读 2018-04-03 13:06:57
    我们可以有线性相关系数(皮尔逊积矩相关系数)、卡方检验(此处不谈)和互信息这几个指标来进行量化。 使用线性相关系数的前提自变量与因变量是线性关系,取值范围为[-1,1],负数表示负相关: ρx,y=cov(X,Y)σX,σ...
  • 归一化互信息(NMI)评价指标

    万次阅读 2019-03-24 23:23:13
    信息熵 对信息进行量化度量。可以理解为某种特定信息的出现概率。 计算公式 相对熵 【百度百科】相对熵(relative entropy),又被称为Kullback-Leibler散度(Kullback-Leibler divergence,KL散度)或信息...
  • sklearn:点互信息互信息

    万次阅读 2017-06-03 00:07:53
    1、点互信息PMI 机器学习相关文献里面,经常会用到点互信息PMI(Pointwise Mutual Information)这个指标来衡量两个事物之间的相关性(比如两个 词)。 其原理很简单,公式如下: 在概率论中,我们知道,如果x跟y不...
  • 通过对通过电子申请和综合司法信息系统发展网络正义的当前工作进行回顾,本文分析了旨在促进司法和司法外处理争端的工具的操作性和标准化所面临的挑战。 考虑到相关法律变量和信息流参数的复杂性,本文建议使用...
  • 马修斯相关系数MCC和标准互信息NMI

    千次阅读 2019-07-23 12:26:00
    1 机器学习知识补充 机器学习分为三个阶段: ...只有通过优秀的评价标准才能选择出性能更好的分类器。 2.马修斯相关系数(性能评估的指标) . 马修斯相关系数是应用在机器学习中,用以测量二分类的分类性能的指标...
  • 为了解决上述问题,提出了基于归一模糊互信息最大的特征评价准则,基于模糊等价关系计算变量的信息熵、条件熵、联合熵;利用联合互信息最大替换累积加和的度量方法;基于归一联合互信息对特征重要性进行评价;...
  • 研究了下sklearn.feature_selection()中参考的Estimating Mutual Information论文与Mutual Information between Discrete and Continuous Data Sets论文,整理一篇基于k-最近邻的互信息算法。
  • 云计算和大数据的标准化需求和标准化组织有哪些?
  • 医院信息互联互通标准化成熟度测评指标体系,三级医院要实现院内各诊疗环节信息互联互通,达到医院信息互联互通标准化成熟度测评4级水平”,
  • MIC 即:Maximal Information Coefficient 最大互信息系数。 使用MIC来衡量两个基因之间的关联程度,线性或非线性关系,相较于Mutual Information(MI)互信息而言有更高的准确度。MIC是一种优秀的数据关联性的计算...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 69,521
精华内容 27,808
关键字:

标准化互信息