人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

決定木のアルゴリズムで使われるinformation gainとはどういう概念で、それをどのように分岐のルールに取り入れているのでしょうか?

Wikipediaを読むと「情報理論におけるエントロピーにあたる」と書いてあるのですが、このエントロピーというのは物理学のエントロピーとどう違うのですか?

(単なる検索結果へのリンクはいりません。本当に理解している方に自分の言葉で説明していただければ幸いです)

●質問者: akdamar
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:Wikipedia アルゴリズム エントロピー リンク ルール
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● Z9M9Z
●50ポイント ベストアンサー

AとBが、以下のように順番に並んでいたとします。

AAAABBAABABAABBBB

これはどこに分岐を入れるべきでしょうか。いくつか考えられます。

AAAA|BBAA BA BA BBBB = A4B0 | A4B8

AAAA BBAA|BA BA BBBB = A6B2 | A2B6

AAAA BBAA BA|BA BBBB = A7B3 | A1B5

AAAA BBAA BA BA|BBBB = A8B4 | A0B4

右側に書いたのは、分岐の左右でのAとBの頻度です。これらの候補からどれを選ぶかの基準として登場するのがinformation gainです。

Wikiにもあるように、AxByなら、p=x/(x+y) として - p log p - (1-p)log(1-p)で計算します。これが小さい分け方を選択します。

極端な例では、こんな並びの属性があれば、そこには自明な分岐があって、

AAA | BBB = A3B0 | A0B3

information gainは最小の0となっています。

同様に、どの属性(特徴量、変数)で分岐すべきかを選択するにも、この値の小さい属性&分岐から選択するのが基本的な方法です。

物理のエントロピーとは「乱雑さの指標である」という概念的共通点があるだけと思っていますが、物理のエントロピーは記憶の彼方です、すいません。

◎質問者からの返答

ありがとうございます! とても具体的なイメージを持つことができました。

もう少し詳しく教えていただけると助かるのですが、

> AxByなら、p=x/(x+y) として - p log p - (1-p)log(1-p)で計算します。

と、いうことは、このpは分岐の左右それぞれについて計算することになるのでしょうか。

例えば上で挙げられている

AAAA|BBAA BA BA BBBB = A4B0 | A4B8

の場合でいえば、

左のハコがp=4/(4+0)=1

右のハコがp=4/(4+8)=0.333

という理解でよいのでしょうか。

初歩的な質問でまことにすみません。

それから、ここでつかわれているlog xは底が2の対数ということでよろしいのでしょうか。


2 ● Z9M9Z
●25ポイント

>>このpは分岐の左右それぞれについて計算することになるのでしょうか。

そうなります。両側のエントロピーの和が、分岐のよしあしになります。

>>左のハコがp=4/(4+0)=1

>>右のハコがp=4/(4+8)=0.333

>>という理解でよいのでしょうか。

はい。

>>それから、ここでつかわれているlog xは底が2の対数ということでよろしいのでしょうか。

はい。2が普通です。

◎質問者からの返答

ありがとうございます。

ついでにもうひとつ質問です。

回答1では2つに分岐させるやり方を説明していただきましたが

information gainを基準にしたアルゴリズムでは必ず2進木が生成されるのでしょうか?

それともCHAIDのように3つ以上の分岐もありえるのでしょうか?


3 ● Z9M9Z
●25ポイント

ありうるか、という問いには、かなり知識ないとnoとは答えにくいですが^o^3つに分ける分岐候補が複数ある中から、エントロピー最小の分岐候補を判定することは、むろんできるわけですし。

ただ、3種類以上のデータを分岐する場合でも、とりあえず1箇所どこで分けるか?と、各変数についてソートして2進木ベースで捜す、ということの方が、楽なのではないでしょうか。分岐1箇所ならともかく、2箇所以上の組となると、適当な分岐候補を発生させるところが若干面倒な気がするので。そのあたりは自信ないです。

◎質問者からの返答

ありがとうございます。よくわかります。

2進木にするかそれ以上の分岐をとるかという問題は、ある意味個々の(ツリーの)アルゴリズムをどう構築するかにゆだねられていて、絶対にできないということではないのでしょうね。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ