＃＃ 導入
デシジョン ツリー (DT) は、分類と回帰に使用されるノンパラメトリック教師あり学習方法です。目標は、データの特徴から推測される単純な決定ルールを学習することによって、ターゲット変数の値を予測するモデルを作成することです。
エントロピー
トレーニングの目標は、最適なツリーを見つけるためにノード内の最適な分割を見つけることです。分割は、エントロピー などのいくつかの基準を使用して行われます。
エントロピーには次のような多くの定義が存在します。
-
エントロピーは、情報源に含まれる情報の量に対応します。
-
エントロピーは、セット内のランダム性または驚きの測定値とみなすこともできます。
-
エントロピーは、システム内の予測不可能性または不純性を測定する指標です。
デシジョン ツリーでは、ノード内の純度の尺度としてエントロピーを考慮します。デシジョン ツリー モデルの目標は、各分割におけるノードのエントロピーを削減することです。
したがって、親ノードのエントロピーと子ノードのエントロピーの差を最大化したいと考えます。この差は 情報利得 と呼ばれます。
集合 $X$ のエントロピー $H$ は、次のように数学的に定式化されます。
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
情報の獲得
情報ゲインは、親ノードのエントロピーとchlidノードのエントロピーの加重和の間の差**であり、次のように定式化できます。
$$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$$
$$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$$
どこ：
-
$H(.)$ はエントロピーです。
-
$Y$ は分割前の母集団であり、親ノードを表します。
-
$X$ は、分割に使用する変数です。
-
$x$ は X の一意の値です。
-
$Y[X==x]$ は、$x$ 値のみを含む分割リストです。
適切な例を見てみましょう:
X の値を使用して親ノードを分割するときの情報ゲインを計算します。
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
まず、親ノードのエントロピーを計算します。
$$ H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow) $$
$$ = - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3 $$
\
次に、X の一意の値を使用して、分割後の各子ノードの内部確率を計算します。
$$ unique(X) = [Circle, Square] $$
$$ \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square) $$
$$ + P(Circle|X) \times H(Y | X = Circle) $$
$$ = \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle) $$
のような：
-
$H(Y | X = Square)$ : 最初の子ノードのエントロピーを表します。
-
$H(Y | X = Circle)$ : 2 番目の子ノードのエントロピーを表します。
\
最初の子ノードから始めます。
$$ H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square) $$
$$ - P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square) $$
$$ = - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23 $$
\
次に 2 番目の子ノード:
$$ H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle) $$
$$ - P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle) $$
$$ = - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28 $$
\
最後に、情報利得の式にエントロピーを代入します。
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
$$ = 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041 $$
\
\
前に述べたように、ノード分割の目的は、情報ゲインを最大化し、結果として得られる子ノードのエントロピーを最小化することです。これを行うには、さまざまな入力セット $ X_1, X_2, \ldots, Xn $ を使用してノードを分割してみて、情報ゲインを最大化する分割のみを維持する必要があります。
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
分割を停止するタイミング
デシジョン ツリーでのノードの分割は再帰的であるため、分割を停止するために使用できる基準が必要です。最も実装されている基準は次のとおりです。
-
ノードが純粋な場合: H(node) = 0。これ以上ノードを分割しても意味がありません。
-
深さの最大数: モデルが到達できる最大深度を設定できます。これは、ノードが純粋でない場合でも分割が停止されることを意味します。
-
ノードあたりの最小サンプル数: ノードあたりのサンプルの最小数 $N$ を設定することもできます。ノードあたりのサンプル数が $N$ に等しい場合、ノードが純粋でなくても分割を停止します。
トレーニング (分割) の終わりまでに、デシジョン ツリーの終わりに依存する各ノードは、サブツリーのルートではないため、「リーフ」と呼ばれます。各リーフは、最も多くのサンプルを持つクラスの収量を表します。
＃＃ 結論
デシジョン ツリーは、その効率性、直感的な背景、簡単な実装により、最も有名な機械学習アルゴリズムの 1 つです。このアルゴリズムはさらに、数値独立変数 ( ガウス決定木 ) とともに使用することができ、回帰タスクを解決するために拡張することもできます。
