カイ二乗値を用いた特徴選択
相互情報量を用いた特徴選択(2010/6/19)のつづきです。今回は、相互情報量ではなく、カイ二乗値を用いて特徴語を抽出してみます。カイ二乗検定は独立性の検定によく使いますけど、特徴語の抽出にも応用できるってのははじめて知りました。結局のところ相互情報量もカイ二乗値もカテゴリと単語がどれくらい依存しているかを表す尺度なのでアプローチは似ている感じがします。IIRの13.5を参考にして実装します。
カイ二乗値
カイ二乗値の定義は、
です。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..は下の式で計算できます。
で、さっきのカイ二乗値の式は実際の文書数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です。ではまた横軸にボキャブラリサイズの対数スケール、縦軸に分類精度としてグラフを描いてみます。
相互情報量のときとあまり変わらない・・・ただこれもIIRに載ってますが、Reuters-RCV1というデータセットだと相互情報量とカイ二乗値では差が出てきます。相互情報量の方が単語数が少なくても分類精度が高い。とりあえず両方試してみるのがいいのかも。
今回はなじみのない英語の文書だったので、次回からは日本語のブログ記事(このブログ)のデータを分類してみようと思います。
参考文献
- ハンバーガー統計学にようこそ! - カイ二乗検定の分かりやすい解説
- プログラミングのための確率統計 - わかりやすい入門書