標準化された相互情報NMI計算ステップとそのPython実装

Excellence is a continuous process and not an accident.
卓越は偶然ではなく持続的なプロセスです.

標準化された相互情報NMI計算ステップとそのPython実装

標準化された相互情報NMIの具体的な定義は、別のブログを参照してください.https://smj2284672469.github.io/2017/10/27/community-detection-measures/#moreこの文書では、その計算手順とコード実装について説明します.
17個のサンプルポイント(v 1,v 2,...,v 17)をクラスタリングするとします.
アルゴリズムによってクラスタリングされた結果は次のとおりです.
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)=[12 3]、Y=unique(B)=[12 3]:
MI(X,Y)=∑i=1|X|∑j=1|Y|P(i,j)log(P(i,j)P(i)P′(j))
まず上式分子における結合確率分布P(i,j)=|Xi∩Yj|Nを計算する
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(3,1)=0,P(3,2)=1/17,P(3,3)=3/17
分母における確率関数P(i)=Xi/N,P(i)がiの確率分布関数,P’(j)がjの確率分布関数を再計算する.
P(i):
P(1)=8/17,P(2)=5/17,p(3)=4/17
P(j):
P′(1)=6/17,P′(2)=6/17,P′(3)=5/17
以上の計算からMIの値を算出することができる.
標準化された相互情報については、2番目の式を使用して計算します.
NMI(X,Y)=2MI(X,Y)H(X)+H(Y)
上式分母におけるH(X),H(Y)はそれぞれX,Yのエントロピーである.
H(X)=−∑i=1|X|P(i)log(P(i));H(Y)=−∑j=1|Y|P′(j)log(P′(j))
上記の例では、式に基づいてエントロピーを計算すると、以下のようになります.
H(X)=P(1)log2(P(1))+P(2)log2(P(2))+P(3)log2(P(3))
H(Y)=P′(1)log2(P′(1))+P′(2)log2(P′(2))+P′(3)log2(P′(3))
以上をまとめるとNMIの値を算出することができる.
コードは以上の計算プロセスを実現します.

はscikit-learnパケットに統合されたメトリック関数

を直接呼び出すことができる.

自己作成関数実装計算プロセス

Pythonコードは以下のように実現される(上記2つの方式を含む).

# -*- 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)