文書分類タスクでよく利用されるfeature selection

"Bias Analysis in Text Classification for Highly Skewed Data"(Lei and Huan)を読んでいて、「文書分類タスクでよく使われるfeature selectionは4つある。Information GainとChi-squared testとOdds ratioとBi-Normal Separationだ」みたいなことが書いてあった。

自分の中で、あんまりわかってないまま使ってる感があったので、しっかり調べてみた。

Information Gain

Information GainはよくIGとか省略される。

IGは要は、「クラスとの関連性がでかい単語ほど大きい値になるよ」というやり方。

簡潔にまとめると、

  1. 単語数×クラス数のクロス集計表をつくる。クロス表は(termが出現 or Not)×(クラス=c or Not)の4要素
  2. クロス表で同時確率と周辺確率を求めて、IGの式に代入。値を求める。

とってもわかりやすい説明

Chi-squared test

日本ではみんなカイ二乗検定とよく言う(と思うたぶん)。英語ではChiと省略すると思う(たぶん)

クロス集計表を作りまくって、データ中でよく特徴を示している要因を特定するときに使ったりしていた。

feature selectionも同じ発想で行う。

クロス表をつくる点では、IGと似ている。

が、Chiは「featureとインスタンス(文書)が独立だった場合を仮定して、実際の出現数と差を取る。」という点で異なる。

ちなみに、独立仮定時と実際の差が大きいほど、「クラスとの関係性が大きい単語」とみなされる。

引き続きわかりやすい説明

Bi-Normal Separation

よく頭文字をとってBNSと表現される

これだけは日本語で上手く説明されたところが見つからなかったので、自分で色々と試してみた。

BNSは直感的に説明すると、「正クラスと負クラスでfeatureが出現している量を比較して、その差を値に示す」というもの。

こう書くと、IGとChiと何ら変わらないように聞こえてしまうが、BNSは2クラスでの出現割合を考慮しているところがミソになる(後述)

2値の文書分類タスクを例に考えてみる。

いま、"iphone"というtermが図の回数で文書に登場しているとする。

f:id:kensuke-mi:20150429170802p:plain

まずはこの回数から、tpr(True classに出現する割合)とnpr(False classに出現する割合)を求める。

この例だと、

tpr=19 / (19 + 5), npr=5 / (19 + 5)になる。

そして、tprとnprを「正規累積分布の逆関数」に代入して、値を求める。(「正規累積分布の逆関数」に関しては後述しまーす)

そして、求めた値の差をとって、BNSの値にする。

「正規累積分布の逆関数」をF_inv()と表現すると、BNSは次に式になる。

BNS= | F_inv(tpr) - F_inv(fpr) |

iphoneの例で一連の流れをしめすと、下図のような感じ

f:id:kensuke-mi:20150429171625p:plain

さっきの図でのデータセット中での"iphone"は1.624435603のBNS値を持つことになる。

ちなみに、tprとnprの値を変化させてBNSを求めると、下図のようになった

f:id:kensuke-mi:20150429175614p:plain

IGとChiとBNSの違い

3つとも出発点になっている考え方は似ているのだが、BNSは他の2つと大きく表現方法が違っている。

この違いはSkewed data(クラスに属するデータ量に偏りがでかいデータセット)のときに、差が如実に現れる。

Lei and HuanではSkewed dataにおけるfeature selectionの比較を行っている。

Lei and HuanはIGとChiとオッズ比とBNSを使って、skewed dataからfeature selectionをしてみた。

その結果、IGとChiは選択するfeature数を少なくすれば少なくするほど、Majorなclassのfeatureばかりが選択される現象を報告している。(ちなみにオッズ比は論外の結果だと言っている)

対して、BNSだけは、選択するfeature数を少なくしても、Majorなclassのfeatureばかりが選ばれることはなく、skewed dataに頑健なfeature selectionだと言っている。

つまり

skewed dataで2値分類をするときは、BNSをfeature selectionに使いましょう。

(参考)正規累積分布の逆関数ってなによ

一言で説明すると、「正規累積分布の逆関数をとったもの」。。としか説明できない。

一応、挙動を確かめてみた。

まず、正規確率密度関数から。もちろん平均は0で標準偏差は1

もちろん、一般的に知られている形になる

f:id:kensuke-mi:20150429172111p:plain

そして、確率累積関数にしてみる

f:id:kensuke-mi:20150429172136p:plain

確率累積関数なので、累積確率を代入すると、元の値になる(一応、確認のため)

f:id:kensuke-mi:20150429172229p:plain

累積確率の逆関数を0.9から0.1まで変化させると、左下がりの形になった

f:id:kensuke-mi:20150429172329p:plain