Zenn
📝

決定木を理解する

に公開
機械学習
決定木
tech

決定木とは

🔸 決定木の構築原理：分割による「不純度の減少」

決定木は、「ある特徴量でデータを分割することで、不純度（impurity）をどれだけ減少させられるか」に基づいて構築されます。
この不純度の減少量が、一般的に「情報利得」と呼ばれます。

🔸 一般的な情報利得の定義

ある特徴 A によってデータ集合 D を \{D_1, D_2, ..., D_n\} に分割したとき、情報利得は次のように定義されます（大きい方が良い）：

\text{Information Gain} = \text{Impurity}(D) - \sum_{i=1}^n \frac{|D_i|}{|D|} \cdot \text{Impurity}(D_i)

ここでの「Impurity」は任意の不純度指標です。主に次の3つが使われます。

🔸 主な不純度指標（Impurity Measures）

1. エントロピー（Entropy）

  • 情報理論に基づく不確実性の尺度。
  • 定義（2クラス）：
H(D) = - \sum_{c} p_c \log_2 p_c
  • 特徴：理論的だが計算がやや重い。

2. ジニ不純度（Gini Impurity）

  • 分類の誤り確率（直感的）。
  • 定義：
G(D) = 1 - \sum_{c} p_c^2
  • 特徴：CART決定木でよく使われる。エントロピーより計算が高速。

3. 分類誤差（Classification Error）

  • 誤分類の割合に着目。
  • 定義：
E(D) = 1 - \max_c p_c
  • 特徴：あまり使われない（他より滑らかでないため）。

🔸 分類と回帰での違い

  • 分類問題：上記のような不純度指標（ジニ不純度、エントロピーなど）を用いる。
  • 回帰問題：目標変数が連続値なので、代わりに**分散の減少（分割前後のMSEなど）**を指標とする。

例：回帰木での情報利得

\text{Gain} = \text{Var}(D) - \sum_i \frac{|D_i|}{|D|} \cdot \text{Var}(D_i)

🔸 情報利得の最大化：決定木構築のアルゴリズム視点

  1. すべての特徴量としきい値について、分割後の不純度を計算
  2. 情報利得（不純度の減少量）が最大となる分割を選択
  3. 再帰的に同様の処理を繰り返す

🔸 情報利得を使う代表的なアルゴリズム

アルゴリズム 不純度指標 補足
ID3 エントロピー カテゴリデータ中心
C4.5 エントロピー + 情報利得率 ID3の改良版
CART ジニ不純度 or 分散 分類と回帰両対応

🔚 まとめ

  • 決定木は、「不純度の減少＝情報利得の最大化」に基づいて構築される。
  • 不純度にはエントロピー、ジニ不純度、分類誤差、（回帰では）分散などがある。
  • 情報利得の定義は、それら不純度指標に依存した一般式として捉えられる。

学習

決定木における**分割の基準（どの特徴量としきい値を選ぶか）は、「不純度の減少＝情報利得の最大化」**という原則に基づいて、すべての候補を試して評価し、最もよかったものを選ぶという方法で決まります。

🔍 分割の基準はどう選ばれるか？：概要

分割候補ごとに次の手順を行います：

  1. ある特徴量を選ぶ
  2. しきい値（またはカテゴリ分割）を仮に設定してデータを2分割
  3. 分割後の不純度を計算（例：ジニ不純度・エントロピー）
  4. 情報利得を計算
  5. すべての組み合わせを試して、情報利得が最大となる分割を採用

🔸 具体例（数値特徴量）

例：特徴量 x の値が以下の4つあるとします。

x クラス
2 0
4 0
6 1
8 1

考えられるしきい値（中央値の間）：

  • t = 3, t = 5, t = 7

各しきい値で試す：

  • x < 3 vs x ≥ 3
  • x < 5 vs x ≥ 5
  • x < 7 vs x ≥ 7

→ それぞれについて分割後の不純度を計算し、情報利得が最大の分割を採用します。

🔸 カテゴリ特徴量の場合

例えば、特徴量が「天気 = {晴れ, 曇り, 雨}」のようなカテゴリの場合：

  • 「晴れ vs それ以外」
  • 「曇り vs それ以外」
  • 「晴れまたは曇り vs 雨」など

→ 各グループ分けパターンに対して情報利得を計算し、最良のものを選びます。

📌 選ばれる分割の特徴

  • 情報利得が最も大きい（＝不純度の減少が大きい）分割
  • 数値特徴：しきい値ごとの探索（全候補を総当たり）
  • カテゴリ特徴：グループの分け方（小規模なら全列挙、大規模なら近似）

🧠 実装での裏側（scikit-learnなど）

scikit-learn などのライブラリでは、次のように実装されています：

  • 数値特徴量：ソートして全てのペアの中央値をしきい値候補に
  • カテゴリ特徴量：カテゴリの数が少なければ全てのサブセットで評価

このようにして、**「もっとも良い分割を選ぶ」**という貪欲法（greedy）で木を構築します。

✅ まとめ

観点 内容
目的 情報利得（不純度の減少）を最大化する分割を選ぶ
手法 すべての特徴・しきい値候補を試して評価
特徴量の型 数値→しきい値を順に試す、カテゴリ→サブセットで分割

決定木では「すべて」といっても、**実行可能な範囲での「全探索」**に制限したアルゴリズム的工夫がなされています。

以下で、「なぜ現実的に分割候補を試せるのか」「どのように分割候補を絞っているのか」を詳しく説明します。

✅ 「分割候補を全て試す」とは？

これは、厳密には次のように解釈できます：

  • 数値特徴量：

    • 実数は無限にあるので「すべて」は不可能。
    • 代わりに、**訓練データ中の値の中間点（中央値）**をしきい値として限定的に探索する。

  • カテゴリ特徴量：

    • k 種類あると、理論上 2^{k-1} - 1 通りの2分割が可能。
    • k が小さいときのみ全探索、多い場合は近似アルゴリズムや単純化を用いる。

🔢 数値特徴量の場合：実際の処理

データ例

特徴 x ラベル
2 A
3 B
7 A
10 B

→ ユニークな特徴値のソート結果：2, 3, 7, 10
→ しきい値候補（中央値）：2.5, 5.0, 8.5

評価する分割：

  • x < 2.5 vs x \geq 2.5
  • x < 5.0 vs x \geq 5.0
  • x < 8.5 vs x \geq 8.5

→ 有限個（\leq n - 1）の候補のみを全て試すので、実質的に可能。

🔣 カテゴリ特徴量の場合の処理

例えば「色 = {赤, 青, 緑}」のようなカテゴリ変数：

  • 理論上の分割候補は：

    • {赤} vs {青, 緑}
    • {青} vs {赤, 緑}
    • {緑} vs {赤, 青}
    • {赤, 青} vs {緑}（など合計 2^{k-1} - 1 通り）

→ k が小さい場合（例：3〜4クラス程度）なら全て試す

→ k が大きい（例：20カテゴリなど）の場合は：

  • 頻度順に並べて上位カテゴリだけを使う
  • one-hotにして処理する
  • ラベルエンコーディング後に数値特徴量として扱う（ただし注意が必要）

⏱️ 実行時間と複雑度

  • 数値特徴量：O(mn\log n)
    → m：特徴量数, n：サンプル数

  • scikit-learn などは高速化のために：

    • 特徴量をあらかじめソート
    • 不必要な候補はスキップ
    • 統計情報を使って効率的に分割点を評価

✅ 結論

「すべての分割候補を試す」とは、現実的な候補（訓練データに基づく有限個）について全探索するという意味です。

  • 無限の実数や膨大なカテゴリ全てを試すわけではない
  • 実装上はデータ内のしきい値候補だけを限定的に評価しており、実行可能です

ランダムフォレスト

ランダムフォレストアルゴリズム（決定木学習）

  1. データ点をランダムに選択（ブートストラップ標本を作成）

    • 訓練データからランダムにデータ点を選んでブートストラップ標本を作成する（復元抽出）。

  2. 各決定木の作成（ノードごとに以下の作業を行う）
    a. 特徴量の中からランダムに m 個の特徴量を選択する（特徴量のサブセット、非復元抽出）。
    b. その m 個の特徴量の中から、目的関数（例えばジニ不純度など）に従って最も良い分割を与える特徴量を選んで分割する。

  3. 手順1〜2を k 回繰り返して、 k 本の決定木を作成する。

  4. 多数決で最終的なクラスを決定する（分類の場合）

    • 各決定木の出力のうち、多数派のクラスを最終的な予測結果とする。

このアルゴリズムのポイント：

  • 各木は異なるブートストラップ標本とランダムな特徴量サブセットを用いるため、多様性が生まれ、過学習を抑える効果がある。標本が小さいほど、「ランダム性」が大きいため、汎化性能が上がるが、全体の性能は低下する傾向がある。大きいと木同士が似るので、過学習に陥る可能性が高くなる。
  • 分類タスクでは多数決、回帰タスクでは平均を取るのが一般的。

Discussion