人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

カイ二乗値を用いた特徴選択

相互情報量を用いた特徴選択(2010/6/19)のつづきです。今回は、相互情報量ではなく、カイ二乗値を用いて特徴語を抽出してみます。カイ二乗検定は独立性の検定によく使いますけど、特徴語の抽出にも応用できるってのははじめて知りました。結局のところ相互情報量もカイ二乗値もカテゴリと単語がどれくらい依存しているかを表す尺度なのでアプローチは似ている感じがします。IIR13.5を参考にして実装します。

カイ二乗値

カイ二乗値の定義は、

f:id:aidiary:20100625000913p:plain

です。NやEが出てきますが、下のようなクロス表を用いて計算します。たとえば、単語「iPhone」とカテゴリ「IT」のカイ二乗値を求めたいとき、クロス表は下のようになります。たとえば、カテゴリがITで単語iPhoneを含む文書はデータ中にN11個あるなどと解釈します。

カテゴリがITである カテゴリがITでない
単語iPhoneを含む N11 (E11) N10 (E10) N1.
単語iPhoneを含まない N01 (E01) N00 (E00) N0.
N.1 N.0 N

N.1はN01+N11、N1.はN10+N11の略です。ここで、カテゴリITと単語iPhoneが独立であると仮定したときに期待される文書数がEです。2つの事象が独立であるとき上のようなクロス表上では各行(または各列)の出現頻度の比が等しくなります。なので、iPhoneを含むケースでも含まないケースでもカテゴリがITである割合はN.1/Nで、カテゴリがITでない割合はN.0/Nとなります。これはプログラミングのための確率統計でもくどいくらい説明されてました。こんなところで役立つとは!。

以上の結果から具体的な文書数E..は下の式で計算できます。

f:id:aidiary:20100625004119p:plain

で、さっきのカイ二乗値の式は実際の文書数Nijと単語とカテゴリが独立と仮定したときの期待される文書数Eijがどれだけ乖離しているかを表す指標になっています。この乖離が大きいほど単語とカテゴリの依存度合いが強いと解釈できるとのこと。相互情報量のときと同じくカイ二乗値が大きい単語ほどカテゴリに特徴的な単語と言ってよさそうです。

カイ二乗値が高い単語を抽出

上の定義をそのまま素直にPythonで実装してみます。20 Newsgroupsの各カテゴリからカイ二乗値が高い上位k個の単語を求めるのが目標です。クロス表を求めるところまでは相互情報量のときとまったく同じです。

#coding:utf-8
import codecs
import math
import sys
from collections import defaultdict

# feature_selection.py

def chisquare(target, data, k=0):
    """カテゴリtargetにおけるカイ二乗値が高い上位k件の単語を返す"""
    # 上位k件を指定しないときはすべて返す
    if k == 0: k = sys.maxint
    
    V = set()
    N11 = defaultdict(float)  # N11[word] -> wordを含むtargetの文書数
    N10 = defaultdict(float)  # N10[word] -> wordを含むtarget以外の文書数
    N01 = defaultdict(float)  # N01[word] -> wordを含まないtargetの文書数
    N00 = defaultdict(float)  # N00[word] -> wordを含まないtarget以外の文書数
    Np = 0.0  # targetの文書数
    Nn = 0.0  # target以外の文書す
    
    # N11とN10をカウント
    for d in data:
        cat, words = d[0], d[1:]
        if cat == target:
            Np += 1
            for wc in words:
                word, count = wc.split(":")
                V.add(word)
                N11[word] += 1  # 文書数をカウントするので+1すればOK
        elif cat != target:
            Nn += 1
            for wc in words:
                word, count = wc.split(":")
                V.add(word)
                N10[word] += 1
    
    # N01とN00は簡単に求められる
    for word in V:
        N01[word] = Np - N11[word]
        N00[word] = Nn - N10[word]
    # 総文書数
    N = Np + Nn
    
    # 各単語のカイ二乗値を計算
    chiSquare = []
    for word in V:
        n11, n10, n01, n00 = N11[word], N10[word], N01[word], N00[word]
        
        # カテゴリと単語が独立である(帰無仮説)と仮定したときの期待値を求める
        e11 = (n10 + n11) * (n01 + n11) / float(N)
        e10 = (n10 + n11) * (n00 + n10) / float(N)
        e01 = (n00 + n01) * (n01 + n11) / float(N)
        e00 = (n00 + n01) * (n00 + n10) / float(N)
        
        # カイ二乗値の各項を計算
        score = (n00-e00)**2/e00 + (n01-e01)**2/e01 + (n10-e10)**2/e10 + (n11-e11)**2/e11
        chiSquare.append( (score, word) )
    
    # カイ二乗値の降順にソートして上位k個を返す
    chiSquare.sort(reverse=True)
    return chiSquare[0:k]

if __name__ == "__main__":
    # 訓練データをロード
    trainData = []
    fp = codecs.open("news20", "r", "utf-8")
    for line in fp:
        line = line.rstrip()
        temp = line.split()
        trainData.append(temp)
    fp.close()
    
    # カイ二乗値を用いて特徴選択
    target = "comp.graphics"
    features = chisquare(target, trainData, k=10)
    print "[%s]" % target
    for score, word in features:
        print score, word

行すると、comp.graphicsカテゴリの相互情報量が高い順に10件の単語が出力されます。

[comp.graphics]
1457.58534448 graphics
612.848781005 image
607.658961581 animation
534.398607189 polygon
483.393632538 gif
389.517701949 tiff
367.564520621 pov
365.271144653 images
349.145975364 cview
340.23014597 jpeg

いかにもcomp.graphicsっぽい単語が並んでます。相互情報量と少し違った単語が上位に上がってます。どちらがいいんでしょうか?

[comp.os.ms-windows.misc]
3254.01838505 windows
863.806249156 cica
783.368406974 dos
619.487823399 ini
517.674741517 file
468.921312024 microsoft
462.793325495 win
438.326468403 ms
422.676491104 drivers
385.311002551 files

[rec.sport.baseball]
2242.51216749 baseball
1482.94560718 pitching
1028.09080232 mets
936.43915033 hitter
910.661498564 braves
882.2585267 phillies
851.746184022 season
848.192467208 pitcher
775.729371181 pitchers
750.249334866 cubs

[sci.space]
2291.74284858 space
1941.32877456 orbit
1528.74443512 nasa
1403.56063934 launch
1302.97108661 moon
1257.05550119 shuttle
1157.29780773 lunar
993.562973086 spacecraft
922.346259941 nsmca
827.767660218 flight

[talk.politics.guns]
2759.33818739 gun
2135.88183801 guns
1865.90273163 firearms
1347.63548737 weapons
1087.54646142 firearm
1025.85886288 handgun
1023.15971587 batf
851.875428063 weapon
800.696565647 waco
794.415883505 nra

[talk.religion.misc]
774.507903866 sandvik
593.936874472 jesus
590.599644857 kendig
576.386454526 newton
569.000025676 kent
498.495688011 ksand
486.967079804 alink
477.218439237 bskendig
473.722409841 christian
464.190984532 royalroads

特徴選択を考慮したナイーブベイズ

では、本題のナイーブベイズで特徴選択を考慮した分類器を作成できるようにします。news20、news20.tのデータはそのままでナイーブベイズのプログラム側でカイ二乗値が大きい上位k個のボキャブラリのみ使うようにします。NaiveBayesクラスのコンストラクタにkの値を指定します。相互情報量のナイーブベイズプログラムで

from feature_selection import mutual_information
features = mutual_information(cat, data)

の部分を

from feature_selection import chisquare
features = chisquare(cat, data)

と書き換えるだけでOKです。ではまた横軸にボキャブラリサイズの対数スケール、縦軸に分類精度としてグラフを描いてみます。

f:id:aidiary:20100625214420p:plain

相互情報量のときとあまり変わらない・・・ただこれもIIRに載ってますが、Reuters-RCV1というデータセットだと相互情報量とカイ二乗値では差が出てきます。相互情報量の方が単語数が少なくても分類精度が高い。とりあえず両方試してみるのがいいのかも。

今回はなじみのない英語の文書だったので、次回からは日本語のブログ記事(このブログ)のデータを分類してみようと思います。

参考文献