Feature selectionのためのInformation GainとBi-normal Separation


こんにちは。胡です。
最近は、文章カテゴリ化課題におけるFeature selectionの問題についていろいろと調べてみました。

Feature extractionとFeature selection

文章のカテゴリ化という課題を解決するために、
ベクトル空間モデルが良く使われますが、
語彙数が多い場合は次元の呪いにかかってしまいます。
その時に、次元の削減が必要となります。
次元を削減するための方法は、主に以下の2つがあります。

方法 内容 手法例・選択尺度
Feature extraction 高次元を低次元に圧縮 主成分分析潜在意味解析など
Feature selection 特徴となる要素を選出 Information Gain,Bi-normal Separationなど

*詳しい情報については参考文献[1][2]をご参照ください。

Feature selectionを行う際に、特徴を選出するための尺度はいろいろありますが、
今回は「このカテゴリに属しているかどうか」という2値分類の課題を想定して、
Information GainとBi-normal Separationについてご説明いたします。

Information Gain

Information Gainは、情報量理論に基づいた尺度であり、

G(t) = \qquad -\sum_{i=1}^{m}Pr(c_i)\log{Pr(c_i)} \\ \qquad \qquad +Pr(t)\sum_{i=1}^{m}Pr(c_i|t)\log{Pr(c_i|t)} \\ \qquad \qquad +Pr(\overline{t})\sum_{i=1}^{m}Pr(c_i|\overline{t})\log{Pr(c_i|\overline{t})}

により求められる[3]。
ここのcはカテゴリで、t\overline{t}は事象出現の有無です。

さらに、2値分類の場合(このカテゴリに属しているかどうか)は、
G(w, c) = e(POS, NEG) - [p(w)e(TP, FP) + p(\overline{w})e(FN, TN)]
に変形できます[2][4]。
ここで、wcはそれぞれ単語とカテゴリであり、ほかの要素は以下のように取得/計算できます。

カテゴリcに属する カテゴリcに属さない
wが出現 TP FP
wが出現しない FN TN

 
POS = TP + FN
NEG = FP + TN
p(w) = \frac{(TP + FP)}{POS + NEG}
p(w) = \frac{(FN + TN)}{POS + NEG}

また、e(x, y)について、以下の式に満たします。
e(x, y) = -\frac{x}{x + y}\log{2}{\frac{x}{x + y}} - \frac{y}{x + y}\log{2}{\frac{y}{x + y}}

それでは、このIG(w, c)をPythonで計算してみましょう。
まずは、e(x, y)の関数を作ります。

import numpy as np
def e(x, y):
    return - (1.0 * x / (x + y)) * np.log2(1.0 * x / (x + y)) - (1.0 * y / (x + y)) * np.log2(1.0 * y / (x + y))

これをふまえて、IG(w, c)を以下の関数で求められます。

def ig(word, data, category):
    total = len(data)
    tp = np.sum([word in data[i] for i in range(0, len(data)) if category[i] == 1])
    fp = np.sum([word in data[i] for i in range(0, len(data)) if category[i] == 0])
    pos = np.sum(category)
    neg = len(data) - pos
    fn = pos - tp
    tn = neg - fp
    return e(pos, neg) - (1.0 * (tp + fp) / total * e(tp, fp) + (1.0 - 1.0 * (tp + fp) / total) * e(fn, tn))

*上記のコードについて、dataはドキュメント集合(単語リスト群)で、categoryは2値のカテゴリリストです。

Bi-normal Separation

Bi-normal Separation(BNS)は、Feature selectionのもう1つの選択です。
文献[2]では、BNSはFeature selectionの尺度として優れた性能を持つと、
実験を通して主張しています。
BNSスコアは、
BNS = |F^{-1}(tpr) - F^{-1}(fpr)|
により計算できます。
ここで、tprfpr
tpr = \frac{tp}{pos}
fpr = \frac{fp}{neg}
のように求められます。
また、Fは標準正規分布の累積関数、
F^{-1}はその逆関数でPythonではnorm.ppt()で求められます。

それでは、おさらいします。
BNSを実装したコード以下となります。

import numpy as np
from scipy.stats import norm
def bns(word, data, category):
    total = len(data)
    tp = np.sum([word in data[i] for i in range(0, len(data)) if category[i] == 1])
    fp = np.sum([word in data[i] for i in range(0, len(data)) if category[i] == 0])
    pos = np.sum(category)
    neg = len(data) - pos
    tpr = 1.0 * tp / pos
    fpr = 1.0 * fp / neg
    print tpr, fpr
    return np.abs(norm.ppf(tpr) - norm.ppf(fpr))

*上記のコードについて、dataはドキュメント集合(単語リスト群)で、categoryは2値のカテゴリリストです。

Information GainとBNSの使い方

Information GainスコアやBNSスコアの使い方として、
・スコアを高い順に並び替え、Top m件の単語を特徴として抽出
・しきい値でフィルタリング
・もっとも高いスコアの特徴から始め、分類器に突っ込んでcross-validationなどで評価することを何回も繰り返し、最適な特徴を抽出
などが挙げられます。
詳細は、参考文献[1]3.1.1節のFilter Policyをご参照くださいませ。

参考文献

[1] Cunningham, P. Dimension reduction. Technical Report: UCD-CSI-2007-7, 2007.
[2] Forman, G. An extensive empirical study of feature selection metrics for text classification. JMLR, 3:1289–1306, 2003.
[3] Yang, Y. and Pedersen, J.O. A comparative study on feature selection in text categorization. In International Conference on Machine Learning(ICML), 1997.
[4] Simeon M., Hilderman R. Categorical proportional Difference: A feature selection method for text categorization. In Proceedings of the 17th Australasian Data Mining Conference, pages 201-208, 2008.


This entry was posted in 技術, 機械学習, 自然言語処理(NLP). Bookmark the permalink.