人工知能に関する断創録

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

相互情報量を用いた特徴選択

機械学習 自然言語処理

20 Newsgroupsで分類精度を評価（2010/6/18）のつづきです。今回は、特徴選択に挑戦してみようと思います。テキスト分類における特徴とは基本的に単語のことです。

特徴選択

前回、ナイーブベイズの出力結果で

documents: 11269, vocabularies: 53852, categories: 20
accuracy: 0.802265156562

となってました。documentsは訓練データの総文書数、categoriesは訓練データのカテゴリ数、vocabulariesは訓練データの総単語数を表します。テキスト分類において53852個の単語を考慮していることを意味します。しかし、この単語の中には分類に寄与しないばかりかノイズになって逆に性能を悪化させるような単語が含まれていることがあります。たとえば、the, in, toなどのストップワードがその一例です。その他にもすべてのカテゴリに同じくらいの頻度で出現する単語なんかもそうです。そのような単語は分類の役に立ちません。今回は、53852個のボキャブラリをさらに絞り込む（特徴を選択する）のが目標です。

相互情報量

特徴選択で代表的なのは、相互情報量（Mutual Information）という尺度を用いる手法です。IIRの13.5を参考にして実装します。

相互情報量は2つの確率変数の相互依存の尺度を表す量とのこと。テキスト分類の特徴選択で用いる場合は、ある単語tの出現を表す確率変数Uとあるカテゴリcの出現を表す確率変数Cを用いて相互情報量I(U; C)を定義します。Uは1または0の値をとり、U=1のとき単語tが出現する事象、U=0のとき単語tが出現しないという事象を表します。Cも1または0の値をとり、C=1のときカテゴリがcである、C=0のときカテゴリがcでないという事象を表します。相互情報量の定義は、


I(U;C) = \displaystyle \sum_{e_t \in \{1,0\}} \displaystyle \sum_{e_c \in \{1,0\}} P(U = e_t, C = e_c) \log_2 \frac{P(U = e_t, C = e_c)}{P(U = e_t) P(C = e_c)}

です。tはterm、cはcategoryの略で具体的な単語やカテゴリが入ります。同時分布や周辺分布が出てきますが、下のようなクロス表を用いると簡単に計算できます。たとえば、単語「iPhone」とカテゴリ「IT」の相互情報量を求めたいとき、クロス表は下のようになります。

カテゴリがITである カテゴリがITでない
単語iPhoneを含む N11 N10
単語iPhoneを含まない N01 N00

ここで、

  • N11は、訓練文書中でカテゴリがIT（C=1）でかつ単語iPhoneを含む（U=1）文書数
  • N10は、訓練文書中でカテゴリがITでなく（C=0）かつ単語iPhoneを含む（U=1）文書数
  • N01は、訓練文書中でカテゴリがIT（C=1）でかつ単語iPhoneを含まない（U=0）文書数
  • N00は、訓練文書中でカテゴリがITでなく（C=0）かつ単語iPhoneを含まない（U=0）文書数

となります。このようなクロス表が求まれば、

  • P(U=1, C=1) = N11 / N
  • P(U=1) = (N10+N11) / N
  • P(C=1) = (N01+N11) / N

といった感じにすべての同時確率と周辺確率が簡単に計算できます。I(U; C)をNを使って書き直すと

f:id:aidiary:20100619120136p:plain

となります。ここで、N1.はN10+N11の略です。上のようなクロス表は、単語とカテゴリのすべての組み合わせ分だけ生成されます。たとえば、単語が50000個あってカテゴリが20個あれば、50000x20通りのクロス表ができます。相互情報量は0以上の値をとり、値が大きいほどカテゴリの特徴を表すような単語と見なすことができるとのこと。これがなぜかは少し考えてしまったけど、いくつか極端なクロス表を作って相互情報量を計算してみると納得できるかも。単語とカテゴリが完全に独立だと相互情報量は0になってしまうってことは・・・そのような単語はカテゴリの内容を表すとは言いがたいってのが直感的な理解でしょうか？

相互情報量が高い単語を抽出

上の定義をそのまま素直にPythonで実装してみます。20 Newsgroupsの各カテゴリから相互情報量が高い上位k個の単語を求めるのが目標です。

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

# feature_selection.py

def mutual_information(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
    
    # 各単語の相互情報量を計算
    MI = []
    for word in V:
        n11, n10, n01, n00 = N11[word], N10[word], N01[word], N00[word]
        # いずれかの出現頻度が0.0となる単語はlog2(0)となってしまうのでスコア0とする
        if n11 == 0.0 or n10 == 0.0 or n01 == 0.0 or n00 == 0.0:
            MI.append( (0.0, word) )
            continue
        # 相互情報量の定義の各項を計算
        temp1 = n11/N * math.log((N*n11)/((n10+n11)*(n01+n11)), 2)
        temp2 = n01/N * math.log((N*n01)/((n00+n01)*(n01+n11)), 2)
        temp3 = n10/N * math.log((N*n10)/((n10+n11)*(n00+n10)), 2)
        temp4 = n00/N * math.log((N*n00)/((n00+n01)*(n00+n10)), 2)
        score = temp1 + temp2 + temp3 + temp4
        MI.append( (score, word) )
    
    # 相互情報量の降順にソートして上位k個を返す
    MI.sort(reverse=True)
    return MI[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 = mutual_information(target, trainData, k=10)
    print "[%s]" % target
    for score, word in features:
        print score, word

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

[comp.graphics]
0.0396591914417 graphics
0.018190625901 image
0.013256620866 animation
0.0122108176792 gif
0.0109647921474 polygon
0.0102937113306 images
0.00984347501837 files
0.00839170021167 format
0.00832240938732 tiff
0.00799473476391 people

いかにもcomp.graphicsっぽい単語が並んでます。他にもいくつかのカテゴリで試してみます。

[comp.os.ms-windows.misc]
0.094183661915 windows
0.0237696712358 dos
0.0184571833467 file
0.0176200422274 cica
0.0161838846441 win
0.014151739062 ms
0.0135110433857 files
0.0131853055706 drivers
0.0126673382015 driver
0.0126148229575 ini

[rec.sport.baseball]
0.0522161980385 baseball
0.031323260157 pitching
0.0241678683103 season
0.0226248072068 games
0.021565415199 mets
0.0204313593006 team
0.0198532689063 braves
0.0195487548191 hitter
0.0192974411302 game
0.0184112914927 phillies

[sci.space]
0.0648087600801 space
0.0414339611904 nasa
0.0410198092698 orbit
0.0307253416988 launch
0.0290759088133 moon
0.0266171725319 shuttle
0.0242961005478 lunar
0.0224255674403 earth
0.0208045078764 spacecraft
0.0197463695696 flight

[talk.politics.guns]
0.064023268956 gun
0.047075696447 guns
0.0372513306097 firearms
0.0321421838979 weapons
0.0213623165189 batf
0.0201845527411 handgun
0.019986956496 fire
0.018426078685 weapon
0.018311826034 fbi
0.0182303153541 waco

[talk.religion.misc]
0.0167788239223 jesus
0.0152625625906 god
0.014476187063 christian
0.013821963122 sandvik
0.0122269234191 kent
0.0121410088867 bible
0.0116866079726 christians
0.0115979054194 newton
0.010151710003 religion
0.00988892270487 christ

それっぽい、それっぽい。相互情報量でそのカテゴリの特徴語が抽出できるのはけっこう面白い。

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

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

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

# 特徴選択を行うナイーブベイズ分類器

class NaiveBayes:
    """Multinomial Naive Bayes"""
    def __init__(self, k):          # 相互情報量が大きい順にk個の単語をボキャブラリとする
        self.categories = set()     # カテゴリの集合
        self.vocabularies = set()   # ボキャブラリの集合
        self.wordcount = {}         # wordcount[cat][word] カテゴリでの単語の出現回数
        self.catcount = {}          # catcount[cat] カテゴリの出現回数
        self.denominator = {}       # denominator[cat] P(word|cat)の分母の値
        self.k = k                  # ボキャブラリ数
    
    def train(self, data):
        """ナイーブベイズ分類器の訓練"""
        # 文書集合からカテゴリを抽出して辞書を初期化
        for d in data:
            cat = d[0]
            self.categories.add(cat)
        for cat in self.categories:
            self.wordcount[cat] = defaultdict(int)
            self.catcount[cat] = 0
        
        # 特徴選択してボキャブラリを絞り込む
        L = []
        for cat in self.categories:
            features = mutual_information(cat, data)
            L.extend(features)
        L.sort(reverse=True)
        for i in range(len(L)):
            # L[i]=(score, word)なので単語はL[i][1]で取り出せる
            self.vocabularies.add(L[i][1])
            # ボキャブラリの数が指定した数に達したら終了
            if len(self.vocabularies) == self.k: break
        
        # 文書集合からカテゴリと単語をカウント
        for d in data:
            cat, doc = d[0], d[1:]
            self.catcount[cat] += 1
            for wc in doc:
                word, count = wc.split(":")
                count = int(count)
                # 単語がボキャブラリに含まれなければ無視
                if not word in self.vocabularies: continue
                self.wordcount[cat][word] += count
        # 単語の条件付き確率の分母の値をあらかじめ一括計算しておく（高速化のため）
        for cat in self.categories:
            self.denominator[cat] = sum(self.wordcount[cat].values()) + len(self.vocabularies)
    
    def classify(self, doc):
        """事後確率の対数 log(P(cat|doc)) がもっとも大きなカテゴリを返す"""
        best = None
        max = -sys.maxint
        for cat in self.catcount.keys():
            p = self.score(doc, cat)
            if p > max:
                max = p
                best = cat
        return best
    
    def wordProb(self, word, cat):
        """単語の条件付き確率 P(word|cat) を求める"""
        # ラプラススムージングを適用
        # 分母はtrain()の最後で一括計算済み
        return float(self.wordcount[cat][word] + 1) / float(self.denominator[cat])
    
    def score(self, doc, cat):
        """文書が与えられたときのカテゴリの事後確率の対数 log(P(cat|doc)) を求める"""
        total = sum(self.catcount.values())  # 総文書数
        score = math.log(float(self.catcount[cat]) / total)  # log P(cat)
        for wc in doc:
            word, count = wc.split(":")
            count = int(count)
            # 単語がボキャブラリに含まれなければ無視
            if not word in self.vocabularies: continue
            # logをとるとかけ算は足し算になる
            for i in range(count):
                score += math.log(self.wordProb(word, cat))  # log P(word|cat)
        return score
    
    def __str__(self):
        total = sum(self.catcount.values())  # 総文書数
        return "documents: %d, vocabularies: %d, categories: %d" % (total, len(self.vocabularies), len(self.categories))

横軸にボキャブラリサイズの対数スケール、縦軸に分類精度としてグラフを描いてみました。

f:id:aidiary:20100619212419p:plain

あれ？ボキャブラリサイズを減らすと精度は下がってしまいました・・・実はこういうこともあるみたいです。元ネタの論文

でも同じ結果になっています。ただ、データセットによってはボキャブラリサイズを減らすと精度が上がる場合もあるようで、IIRにはReuters-RCV1というデータの実行例が載っています。オリジナルのボキャブラリサイズが132776ですが、相互情報量が大きい順に100個に絞るとaccuracyが20%近く上がっています。こんなお得なこともあるのでとりあえずやってみた方がよいのかも。