* 特徴選択/情報ゲイン (feature selection/information gain) [#f73e46c4]

決定木アルゴリズム [[ID3]] で利用される情報ゲイン (information gain) を用いた特徴選択.
フィルター法による特徴選択で使われる,代表的な特徴の良さの規準.

情報ゲインは,クラスの変数を \(C\),特徴の集合を \(X_A\) として,次式
\[\mathrm{Gain}(X_A)=H(C) - H(C|X_A)\]
ただし,\(H(\cdot)\) はエントロピー関数.
特徴集合 \(X_A\) に含まれる特徴が \(X_1,\ldots,X_k\) であり,これらの特徴の定義域を \(\mathcal{D}(X_1),\ldots,\mathcal{D}(X_k)\) とする.
\(H(C|X_A)\)は,\(\mathcal{D}(X_1)\times\cdots\times\mathcal{D}(X_k)\) の値を取る変数が与えられたときの,クラス変数 \(C\) の条件付エントロピー.

backward stepwise selection の場合は,\(X_A\) が全特徴の状態から,情報ゲインが最も大きくなるような特徴を一つずつ取り除く.
forward stepwise selection の場合は,逆に特徴が何もない状態から,情報ゲインが最も大きくなるような特徴を一つずつ追加する.
どちらの場合も,情報ゲインの改善がなくなったときに停止する.

この情報ゲインには劣モジュラ性があるため,こうした欲張りアルゴリズムによる探索でも,比較的高い確率で良い特徴集合が選択できる.

> -- しましま

**関連項目 [#k39bc246]

-[[特徴選択]]
-[[劣モジュラ]]
-[[ID3]]
-[[エントロピー]]
-[[条件付エントロピー]]

**リンク集 [#r210817c]

//関連するWWW資源があればリンクしてください.
- [[Beyond Convexity: Submodularity in Machine Learning>http://www.submodularity.org]]:劣モジュラ性に関するチュートリアル.
情報ゲインを使った特徴選択と劣モジュラ性の関連について.

**関連文献 [#w63402bf]

-[[Book/データマイニングの基礎]] 4.2.b節

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS