ノードの分割

トレーニング中は、各決定ノードで最適な分割を見つける必要があります。データを2つのノードに分割する際、異なるクラスが別々のノードに分かれることを目指します。

• 最良の場合: ノード内のすべてのデータポイントが同じクラスに属する場合
• 最悪の場合: 各クラスのデータポイント数が等しい場合

ジニ不純度

分割の良さを測るために、ジニ不純度を計算します。これは、ノードからランダムに2点（復元抽出）を選んだとき、それらが異なるクラスである確率です。この確率（不純度）が低いほど、分割は良いとされます。

二値分類のジニ不純度は、次の式で計算可能：

ここで

• $m_i$ - ノード内のクラス$i$のインスタンス数；
• $m$ - ノード内のインスタンス数；
• $p_i = \frac{m_i}{m}$ - クラス$i$を選択する確率。

多クラス分類の場合、式は次の通り：

ここで

• $C$ - クラス数。

分割の良さは、分割によって得られる両ノードのジニスコアの加重平均で評価可能。この値を最小化することが目標。

決定ノードを分割するには、分割する特徴量としきい値を見つける必要がある。

決定ノードでは、アルゴリズムは各特徴量に対して貪欲に最適な閾値を見つけます。そして、すべての特徴量の中から最もジニ不純度が低い分割を選択します（同点の場合はランダムに選択）。

エントロピー

エントロピーは不純度の別の指標です。2値分類問題の場合、ノードのエントロピー $H$ は次の式で計算されます：

ここで：

• $p$ は正例（クラス1）の割合；
• $1 - p$ は負例（クラス0）の割合。

多クラス分類問題の場合、ノードのエントロピー $H$ は次の式で計算されます：

ここで：

• $k$ はクラス数；
• $p_i$ はノード内でクラス $i$ に属するサンプルの割合。

ジニ不純度と同様に、分割によって得られる子ノードのエントロピー値の加重和を計算することで、分割の良さを評価できます。この値を最小化することで、情報利得を最大化することができます。