Wikipediaを読むと「情報理論におけるエントロピーにあたる」と書いてあるのですが、このエントロピーというのは物理学のエントロピーとどう違うのですか?
(単なる検索結果へのリンクはいりません。本当に理解している方に自分の言葉で説明していただければ幸いです)
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となっています。
同様に、どの属性(特徴量、変数)で分岐すべきかを選択するにも、この値の小さい属性&分岐から選択するのが基本的な方法です。
物理のエントロピーとは「乱雑さの指標である」という概念的共通点があるだけと思っていますが、物理のエントロピーは記憶の彼方です、すいません。
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の対数ということでよろしいのでしょうか。
>>このpは分岐の左右それぞれについて計算することになるのでしょうか。
そうなります。両側のエントロピーの和が、分岐のよしあしになります。
>>左のハコがp=4/(4+0)=1
>>右のハコがp=4/(4+8)=0.333
>>という理解でよいのでしょうか。
はい。
>>それから、ここでつかわれているlog xは底が2の対数ということでよろしいのでしょうか。
はい。2が普通です。
ありがとうございます。
ついでにもうひとつ質問です。
回答1では2つに分岐させるやり方を説明していただきましたが
information gainを基準にしたアルゴリズムでは必ず2進木が生成されるのでしょうか?
それともCHAIDのように3つ以上の分岐もありえるのでしょうか?
ありうるか、という問いには、かなり知識ないとnoとは答えにくいですが^o^3つに分ける分岐候補が複数ある中から、エントロピー最小の分岐候補を判定することは、むろんできるわけですし。
ただ、3種類以上のデータを分岐する場合でも、とりあえず1箇所どこで分けるか?と、各変数についてソートして2進木ベースで捜す、ということの方が、楽なのではないでしょうか。分岐1箇所ならともかく、2箇所以上の組となると、適当な分岐候補を発生させるところが若干面倒な気がするので。そのあたりは自信ないです。
ありがとうございます。よくわかります。
2進木にするかそれ以上の分岐をとるかという問題は、ある意味個々の(ツリーの)アルゴリズムをどう構築するかにゆだねられていて、絶対にできないということではないのでしょうね。
ありがとうございます! とても具体的なイメージを持つことができました。
もう少し詳しく教えていただけると助かるのですが、
> 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の対数ということでよろしいのでしょうか。