「エントロピーと情報ゲイン」とは何ですか? 質問する

Question

エントロピーは建築の文脈で言及されたと思います決定木。

例えば、次のようなタスクを想像してみてください。学ぶに分類するファーストネームを男性/女性のグループに分けます。それぞれにまたはのラベルが付けられた名前のリストが与えられm、fモデルデータに適合し、新しい未知のファーストネームの性別を予測するために使用できます。

name       gender
-----------------        Now we want to predict 
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

最初のステップは決定する何特徴データは、予測したいターゲットクラスに関連しています。特徴の例には、最初/最後の文字、長さ、母音の数、母音で終わるかどうかなどがあります。特徴抽出後のデータは次のようになります。

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

目標は、決定木. の例木だろう：

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

基本的に各ノードは単一の属性に対して実行されるテストを表し、テストの結果に応じて左または右に進みます。クラス予測（mまたはf）を含むリーフノードに到達するまでツリーをトラバースし続けます。

したがって、このツリーでAmroという名前を実行すると、まず「長さは 7 未満か?」というテストから始まり、答えはyesなので、そのブランチに進みます。ブランチに続いて、次のテスト「母音の数は 3 未満か?」は再びtrueと評価されます。これはというラベルの付いたリーフノードにつながりm、したがって予測は男性です(私はたまたま男性なので、ツリーは結果を予測しました)。正しく）。

決定木はトップダウン方式で構築されたしかし、各ノードでどの属性を分割するかをどのように選択するかが問題です。答えは、ターゲットクラスを可能な限り純粋な子ノード (つまり、男性と女性が混在しないノード、1 つのクラスのみを持つ純粋なノード) に分割するのに最適な機能を見つけることです。

この純度の尺度は情報。それは期待される数の情報これは、ノードに到達した例に基づいて、新しいインスタンス (first-name) を男性と女性のどちらに分類するかを指定するために必要になります。これは、ノードの男性クラスと女性クラスの数に基づいて計算します。

エントロピ一方、不純物の尺度（その逆）は、バイナリクラス値a/bは次のようになります:

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

これバイナリエントロピー関数は下の図に示されています (ランダム変数は 2 つの値のいずれかを取ります)。確率がのときに最大になり、つまりまたは同様にまたはのいずれかになる確率が 50%/50% であるp=1/2ことを意味します(不確実性は最大になります)。エントロピー関数は、確率がのとき、またはが完全に確実にのとき (それぞれまたは、後者はを意味します)、最小値 0 になります。p(X=a)=0.5p(X=b)=0.5abp=1p=0p(X=a)=1p(X=a)=0p(X=b)=1

もちろん、エントロピーの定義は、N 個の結果 (2 つだけではなく) を持つ離散ランダム変数 X に対して一般化できます。

エントロピ

（log式中のは通常、2を底とする対数）

名前の分類のタスクに戻り、例を見てみましょう。ツリーを構築するプロセスのある時点で、次の分割を検討していたと想像してください。

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

ご覧のとおり、分裂前は男性が 9 人、女性が 5 人、つまりP(m)=9/14とでしたP(f)=5/14。エントロピーの定義によれば、

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

次に、2 つの子ブランチを見て分割を考慮した後に計算されたエントロピーと比較します。の左ブランチではends-vowel=1、次のようになります。

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

の右枝からはends-vowel=0、次の式が得られます。

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

左/右のエントロピーを各ブランチのインスタンス数を使って組み合わせると、重み係数(7 つのインスタンスが左に行き、7 つのインスタンスが右に行きました)、分割後の最終的なエントロピーを取得します。

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

分裂前と分裂後のエントロピーを比較すると、情報獲得、または特定の機能を使用して分割を行うことで得られた情報の量:

Information_Gain = Entropy_before - Entropy_after = 0.1518

上記の計算は次のように解釈できます。特徴量で分割することでend-vowels、サブツリー予測結果の不確実性をわずか0.1518（ビットとして情報の単位）。

ツリーの各ノードでは、この計算がすべての特徴に対して実行され、最大の情報ゲインを持つ特徴が分割のために選択される。よく深い方法 (したがって、不確実性/エントロピーが低い純粋な分割を生成する機能を優先します)。このプロセスはルートノードから再帰的に適用され、リーフノードにすべて同じクラスを持つインスタンスが含まれると停止します (それ以上分割する必要はありません)。

いくつか省略しましたが詳細これらはこの記事の範囲を超えており、どのように対処するかなど数値特徴、欠損値、過剰適合そして剪定木など

Answer 1