意思決定ツリーの分岐でシャノンのエントロピー測定が使用されるのはなぜですか?
エントロピー(S) = - p(+)log( p(+) ) - p(-)log( p(-) )
私はそれがノーの尺度であることを知っています。情報をエンコードするために必要なビット数。分布が一様であるほど、エントロピーは大きくなります。しかし、決定木の作成 (分岐点の選択) に頻繁に適用される理由がわかりません。
意思決定ツリーの分岐でシャノンのエントロピー測定が使用されるのはなぜですか?
エントロピー(S) = - p(+)log( p(+) ) - p(-)log( p(-) )
私はそれがノーの尺度であることを知っています。情報をエンコードするために必要なビット数。分布が一様であるほど、エントロピーは大きくなります。しかし、決定木の作成 (分岐点の選択) に頻繁に適用される理由がわかりません。
最も多くの情報が得られる質問をしたいからです。目標は、ツリー内の決定/質問/分岐の数を最小限に抑えることです。そのため、最も多くの情報を提供する質問から始めて、次の質問を使用して詳細を入力します。
決定木のために、ビット数を忘れて、式自体に集中してください。トレーニング データに同数の + と - の例があるバイナリ (+/-) 分類タスクを考えてみましょう。最初、エントロピーは 1 なのでp(+) = p(-) = 0.5
. エントロピーを最も減少させる (つまり、クラスの分布のランダム性を最小にする) 属性でデータを分割したいと考えています。クラスにまったく関係のない属性 A1 を選択した場合、データを A1 の値で分割した後もエントロピーは 1 のままであるため、エントロピーの減少はありません。ここで、別の属性 A2 がクラスを完全に分離しているとします (たとえば、クラスは常に+
for でA2="yes"
あり、常に-
forA2="no"
です。この場合、エントロピーはゼロであり、これが理想的なケースです。
実際のケースでは、通常、属性はデータを完全に分類しません (エントロピーは 0 より大きくなります)。したがって、データを「最適」に分類する属性を選択します (エントロピーの最大の削減を提供します)。この方法でデータが分離されると、最初の分割からの分岐ごとに別の属性が同様の方法で選択され、その分岐に沿ってエントロピーがさらに削減されます。このプロセスは、ツリーを構築するために続行されます。
この方法の背後にある数学を理解しているようですが、この方法が使用される理由の背後にある直感を与える簡単な例を次に示します。100 人の生徒がいる教室にいると想像してください。各学生は机に座っており、机は 10 行 10 列に配置されています。100 人に 1 人の生徒に賞品がありますが、賞品を受け取るにはどの生徒かを当てる必要があります。キャッチは、あなたが推測するたびに、賞品の価値が減るということです. 賞品を持っているかどうかを各生徒に個別に尋ねることから始めることができます。ただし、最初は正しく推測できる可能性は 1/100 しかなく、賞品を見つける頃には価値がなくなっている可能性があります (すべての推測は決定木の分岐と考えてください)。その代わり、各質問で検索スペースを大幅に削減する幅広い質問をすることができます。たとえば、「生徒は 1 行目から 5 行目のどこかにいますか?」答えが「はい」であろうと「いいえ」であろうと、ツリー内の潜在的な枝の数が半分に減りました。