決定木についてまとめます。

1. 決定木とは

データを 木構造 で分岐させながら分類・予測を行うアルゴリズムです。
質問に はい / いいえ で答えながら枝分かれしていく、フローチャートのようなイメージです。

決定木（Decision Tree）

2. 学習の基本ステップ

  1. 根（ルート）からスタート
    • 全データが混ざった状態
  2. 最良の分岐を探す
    • 全ての特徴量・全ての閾値を試し 不純度 が最も下がる条件を選ぶ
  3. データを分割
    • 選んだ条件で左右（Yes/No）のノードに分ける
  4. 再帰的に繰り返す
    • 各子ノードでも同じ処理を行う。
  5. 停止条件で打ち切る
    • 最大深さ、最小サンプル数、改善がほとんどない場合など
  6. 葉（リーフ）で予測を確定
    • 分類なら多数派クラス、回帰なら平均値を予測する

各分岐は 貪欲法（Greedy Search）で決まります。 その時点で最も良い分岐を選び、後戻りはしません。

そのため局所最適の積み重ねになり、過学習しやすいという特徴があります（ランダムフォレストなどで改善されます）。

3. エントロピーを迷いの量で理解する

エントロピーは情報理論では システムの不確実性 ですが、決定木では どれだけ分類に迷うか と考えると理解しやすくなります。

ケース 1：犬5匹・猫5匹

犬 猫
5 5
  • エントロピー = 1（最大）
    • $H(p) = -\frac{1}{2}\log_{2}\frac{1}{2} - \frac{1}{2}\log_{2}\frac{1}{2} = 1 \quad \text{※}\ -\log_{2}\frac{1}{2} = 1$
  • 犬か猫か半々なので最も迷う状態

ケース 2：犬9匹・猫1匹

犬 猫
9 1
  • エントロピー ≈ 0.47
    • $H(p) = -\frac{9}{10} \log_{2}\frac{9}{10} - \frac{1}{10} \log_{2}\frac{1}{10}$
    • $H(p) \approx 0.136 + 0.332 = 0.47$
  • たぶん犬と予想できるので迷いが減る。

ケース 3：犬10匹・猫0匹

犬 猫
10 0

つまりエントロピーが小さいほどその集団は純粋で予測しやすいといえます。

4. 木を降りるたびに不純度が下がるイメージ

最初は犬5匹・猫5匹。

  • 犬： 5 匹
  • 猫： 5 匹
\[H_{\text{親}}(p) = -\frac{1}{2}\log_{2}\frac{1}{2} -\frac{1}{2}\log_{2}\frac{1}{2} = 1\]

完全に混ざっている状態です。

ここで決定木が 耳が立っていますか？ という質問をすると以下になるとします。

          耳が立っていますか？
              /            \
            Yes            No
        犬4 猫1        犬1 猫4

左右とも片方のクラスに偏りました。

\[\begin{aligned} H_{\text{左}}(p) &= -\frac{4}{5}\log_{2}\frac{4}{5} -\frac{1}{5}\log_{2}\frac{1}{5} \approx 0.26 + 0.46 = 0.72 \\ H_{\text{右}}(p) &= -\frac{1}{5}\log_{2}\frac{1}{5} -\frac{4}{5}\log_{2}\frac{4}{5} \approx 0.46 + 0.26 = 0.72 \\ H_{\text{左右}} &= H_{\text{左}}(p) \text{ と } H_{\text{右}}(p) \text{ の加重平均} = \frac{1}{2} \times 0.72 + \frac{1}{2} \times 0.72 = 0.72 \end{aligned}\]

さらに左側に対して 体重15kg以上？ という質問をすると以下になるとします。

        犬4 猫1
           │
      体重15kg以上？
        /         \
      Yes         No
   犬3 猫0    犬1 猫1

左上は犬だけになりました。

このように質問を重ねるたびに混ざった集団を、より純粋な集団へ分解していくのが決定木です。

5. 与信審査の例

最初の100人。

  • 承認：50 人
  • 却下 50 人

迷いは最大です。

年収400万円以上？

Yes No
承認40・却下10 承認10・却下40

どちらも偏りました。

さらに左側で

勤続3年以上？

Yes No
承認35・却下2 承認5・却下8

「Yes」はほぼ承認だけになっています。

6. 不純度を測る指標

ジニ不純度

\[Gini = 1 - \sum_i p_i^2\]
  • ランダムに2人選んだとき（復元抽出）クラスが異なる確率のイメージ。
  • 0なら完全に純粋。

エントロピー

\[\begin{aligned} H(p) = -p\log_{2}(p) - (1-p)\log_{2}(1-p) \quad &\text{ベルヌーイ分布} \\ H(X)= -\sum_{i=1}^{n}p_i\log_2p_i \quad &\text{カテゴリカル分布} \end{aligned}\]
  • 情報理論由来。
  • ジニ不純度と似た動きをする。
  • scikit-learn のデフォルトはジニ不純度。

ジニ不純度の具体例（犬と猫）

エントロピーのときと同じ 3 ケースで計算します。犬・猫の 2 クラスなので、犬の割合を $p_{\text{犬}}$、猫の割合を $p_{\text{猫}}$ とすると

\[Gini = 1 - \left(p_{\text{犬}}^2 + p_{\text{猫}}^2\right)\]

です。

ケース 1：犬5匹・猫5匹

\[Gini = 1 - \left\{\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2\right\} = 1 - \left(\frac{1}{4} + \frac{1}{4}\right) = 0.5\]
  • 2 クラスのときのジニ不純度の最大値（エントロピーの最大値 1 に対応）
  • ランダムに 1 匹ずつ 2 回引いたとき、犬と猫が異なる確率は $2 \times \frac{1}{2} \times \frac{1}{2} = 0.5$

ケース 2：犬9匹・猫1匹

\[Gini = 1 - \left\{\left(\frac{9}{10}\right)^2 + \left(\frac{1}{10}\right)^2\right\} = 1 - (0.81 + 0.01) = 0.18\]
  • 犬に偏っているので不純度は小さい
  • 2 回引いて種類が異なる確率は $2 \times 0.9 \times 0.1 = 0.18$ で一致する

ケース 3：犬10匹・猫0匹

\[Gini = 1 - \left\{\left(\frac{10}{10}\right)^2 + \left(\frac{0}{10}\right)^2\right\} = 1 - 1 = 0\]
  • 犬しかいないので完全に純粋

エントロピーとの比較

犬 : 猫 ジニ不純度 エントロピー
5 : 5 0.5 1
4 : 1 0.32 0.72
9 : 1 0.18 0.47
10 : 0 0 0

どちらも 50:50 で最大、100:0 で 0 になり、偏るほど小さくなります。ジニ不純度は対数計算が不要な分、計算が軽くなります。

分岐の評価（ジニ不純度の減少量）

エントロピーの情報利得と同様に、親ノードのジニ不純度から、子ノードのジニ不純度の加重平均を引いた値で分岐を評価します。

\[\Delta Gini = Gini_{\text{親}} - \left(\frac{n_{\text{左}}}{n}Gini_{\text{左}} + \frac{n_{\text{右}}}{n}Gini_{\text{右}}\right)\]

例 1：耳が立っていますか？（犬5・猫5 → 左：犬4猫1、右：犬1猫4）

\[\begin{aligned} Gini_{\text{親}} &= 0.5 \\ Gini_{\text{左}} &= 1 - \left\{\left(\frac{4}{5}\right)^2 + \left(\frac{1}{5}\right)^2\right\} = 1 - (0.64 + 0.04) = 0.32 \\ Gini_{\text{右}} &= 1 - \left\{\left(\frac{1}{5}\right)^2 + \left(\frac{4}{5}\right)^2\right\} = 1 - (0.04 + 0.64) = 0.32 \\ \text{分岐後} &= \frac{5}{10} \times 0.32 + \frac{5}{10} \times 0.32 = 0.32 \\ \Delta Gini &= 0.5 - 0.32 = 0.18 \end{aligned}\]

例 2：体重15kg以上？（犬4・猫1 → 左：犬3猫0、右：犬1猫1）

\[\begin{aligned} Gini_{\text{親}} &= 0.32 \\ Gini_{\text{左}} &= 1 - \left\{\left(\frac{3}{3}\right)^2 + \left(\frac{0}{3}\right)^2\right\} = 0 \\ Gini_{\text{右}} &= 1 - \left\{\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2\right\} = 0.5 \\ \text{分岐後} &= \frac{3}{5} \times 0 + \frac{2}{5} \times 0.5 = 0.2 \\ \Delta Gini &= 0.32 - 0.2 = 0.12 \end{aligned}\]

犬だけの純粋なノード（$Gini = 0$）ができ、残りの犬1猫1のノードは最大の不純度 0.5 のまま残っています。

同じ分岐をエントロピー（情報利得）で計算した場合との比較です。

分岐 ジニ不純度の減少量 情報利得
耳が立っていますか？（親：5:5） 0.18 $1 - 0.72 = 0.28$
体重15kg以上？（親：4:1） 0.12 $0.72 - 0.4 = 0.32$

指標ごとに値の大きさ（ジニ不純度の最大は 0.5、エントロピーの最大は 1）が異なるため、値の比較は同じ指標の中で行います。

例 3：与信審査 年収400万円以上？（承認50・却下50 → Yes：承認45却下5、No：承認5却下45）

\[\begin{aligned} Gini_{\text{Yes}} = Gini_{\text{No}} &= 1 - \left\{\left(\frac{45}{50}\right)^2 + \left(\frac{5}{50}\right)^2\right\} = 1 - (0.81 + 0.01) = 0.18 \\ \text{分岐後} &= 0.5 \times 0.18 + 0.5 \times 0.18 = 0.18 \\ \Delta Gini &= 0.5 - 0.18 = 0.32 \end{aligned}\]

（同じ分岐の情報利得は 0.53 です。）

7. 分岐の良さ（情報利得）

決定木は親より子の方がどれだけ迷いが減ったかで分岐を評価します。

\[\text{情報利得} = H_{\text{親}} - \left(\frac{n_{\text{左}}}{n}H_{\text{左}} + \frac{n_{\text{右}}}{n}H_{\text{右}}\right)\]

重要なのは、Yes 側だけではなく Yes と No の両方を合わせて評価することです。

8. 両方の枝を足す理由

次の分割があります。

グループ 内容
99人 50:49
1人 1:0

1人だけ完璧に分離できても、99人はほぼ混ざったままです。
決定木は人数で重み付けした 加重平均 で評価します。

\[\frac{99}{100}H_{\text{左}} + \frac{1}{100}H_{\text{右}}\]

9. 実際の情報利得の計算例

親ノード

承認 却下
50 50

親ノードのエントロピー：

\[H = 1\]

年収400万円以上？ で分ける

枝 人数 内訳 エントロピー
Yes 50 承認45・却下5 0.47
No 50 承認5・却下45 0.47

分岐後の不純度：

\[0.5 \times 0.47 + 0.5 \times 0.47 = 0.47\]

情報利得は以下のとおりです。

\[1 - 0.47 = 0.53\]

左右両方の枝を人数で重み付けした合計の 不純度 が最も小さくなる質問を選びます。

10. $p$ の変化

親ノードの割合を $p$ とすると、

分岐後：

  • $p_{\text{Yes}}$
  • $p_{\text{No}}$

決定木は $p_{\text{Yes}}$ と $p_{\text{No}}$ を 0 または 1 に近づけるような特徴量と閾値を探しています。

11. 決定木の全体像

根：承認・却下が混在（不純度 高）
              │
      年収400万円以上？
         /           \
       Yes           No
       │             │
 勤続3年以上？    延滞歴あり？
    /      \        /      \
 承認     さらに分岐  却下   さらに分岐

木を降りるたびに、

が小さくなり、最終的に純粋な葉ノードで予測が確定します。

12. エントロピーを情報理論として見る

情報理論ではエントロピーは正解を知るために平均何ビットの情報が必要かという意味があります。

状態 エントロピー
50:50 1ビット
90:10 約0.47ビット
100:0 0ビット

つまり決定木は次の1問で最も多く迷い（情報）を減らせる質問は何か？を毎回探しながら木を成長させているアルゴリズムです。