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


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

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

回答の条件
  • 1人5回まで
  • 登録:2006/06/12 15:55:32
  • 終了:2006/06/18 07:32:15

ベストアンサー

id:Z9M9Z No.1

Z9M9Z回答回数343ベストアンサー獲得回数112006/06/12 23:03:12

ポイント50pt

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となっています。

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

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

id:akdamar

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

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

> 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の対数ということでよろしいのでしょうか。

2006/06/13 10:02:33

その他の回答(2件)

id:Z9M9Z No.1

Z9M9Z回答回数343ベストアンサー獲得回数112006/06/12 23:03:12ここでベストアンサー

ポイント50pt

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となっています。

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

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

id:akdamar

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

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

> 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の対数ということでよろしいのでしょうか。

2006/06/13 10:02:33
id:Z9M9Z No.2

Z9M9Z回答回数343ベストアンサー獲得回数112006/06/13 20:03:59

ポイント25pt

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

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

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

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

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

はい。

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

はい。2が普通です。

id:akdamar

ありがとうございます。

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

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

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

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

2006/06/15 10:35:04
id:Z9M9Z No.3

Z9M9Z回答回数343ベストアンサー獲得回数112006/06/16 01:32:50

ポイント25pt

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

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

id:akdamar

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

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

2006/06/16 16:48:21

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません