決定木（Decision Tree）は、「もし特徴量 $x_1$ が閾値 $t$ 以上なら左へ、そうでなければ右へ」という条件分岐を繰り返して予測を行うモデルです。人間がフローチャートで意思決定するのと同じ構造を持つため、最も解釈しやすい機械学習モデルの一つとして広く使われています。
しかし決定木は単体ではデータのわずかな変動に敏感で、汎化性能に限界があります。そこで複数の決定木を組み合わせて予測精度を大幅に向上させる手法がランダムフォレスト（Random Forest）です。
本記事の内容
- 決定木の基本構造と分割基準（エントロピー・ジニ不純度）の数学的導出
- CARTアルゴリズムと過学習対策（剪定）
- バギングとランダムフォレストの理論
- OOBスコアと特徴量重要度
- scikit-learn での実装と可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
決定木の基本構造
決定木は以下の要素で構成されます。
| 用語 | 意味 |
|---|---|
| 根ノード（Root Node） | 木の最上位。全データがここから出発する |
| 内部ノード（Internal Node） | 特徴量と閾値による分割条件を持つノード |
| 枝（Branch） | 分割条件の結果（True / False）を表す辺 |
| 葉ノード（Leaf Node） | 最終的な予測値（クラスラベルや回帰値）を出力する末端ノード |
分類問題の場合、各内部ノードでは「特徴量 $x_j$ の値が閾値 $t$ 以下かどうか」で二分岐し、葉ノードでは最も多数派のクラスを予測値とします。回帰の場合は、葉に含まれるサンプルの平均値が予測値になります。
決定木の学習とは、最適な特徴量 $j$ と閾値 $t$ の組を各ノードで選ぶことに他なりません。では「最適」とはどういう意味でしょうか。それを定量化するのが次に紹介する分割基準です。
分割基準1: 情報利得（Information Gain）
エントロピーの定義
あるノードに含まれるデータが $K$ クラスに分類され、クラス $k$ の割合が $p_k$ であるとき、そのノードのエントロピー（不確実性の度合い）は次のように定義されます。
$$ H = -\sum_{k=1}^{K} p_k \log_2 p_k $$
ここで $p_k = 0$ のときは $0 \cdot \log_2 0 = 0$ と約束します。
直感的に言えば、エントロピーはそのノードのデータが「どれだけ混ざっているか」を表します。全サンプルが同一クラスなら $H = 0$（純粋な状態）、各クラスが均等に混ざっていれば $H$ は最大になります。
2クラスの場合を考えてみましょう。クラス1の割合を $p$ とすると、
$$ H(p) = -p \log_2 p – (1-p) \log_2 (1-p) $$
$p = 0$ や $p = 1$（どちらか一方のクラスだけ）のとき $H = 0$、$p = 0.5$（半々）のとき $H = 1$ と最大になります。
情報利得の計算
ノード $m$ を特徴量 $x_j$ と閾値 $t$ で2つの子ノード $m_L$, $m_R$ に分割したとき、情報利得（Information Gain）は次のように計算されます。
$$ \text{IG}(m, j, t) = H(m) – \frac{N_{m_L}}{N_m} H(m_L) – \frac{N_{m_R}}{N_m} H(m_R) $$
ここで $N_m$, $N_{m_L}$, $N_{m_R}$ はそれぞれ親ノード、左の子ノード、右の子ノードのサンプル数です。
情報利得は「分割前のエントロピーから、分割後のエントロピー（重み付き平均）を引いたもの」です。この値が大きいほど、分割によって不確実性が大きく減少した、つまり良い分割であると判断します。
具体的な計算例
10個のサンプルからなるノードがあり、クラスA が 6個、クラスB が 4個とします。
$$ H(\text{親}) = -\frac{6}{10}\log_2 \frac{6}{10} – \frac{4}{10}\log_2 \frac{4}{10} = -0.6 \times (-0.737) – 0.4 \times (-1.322) = 0.971 $$
ある分割で左の子ノードに [A:5, B:1]（6個）、右の子ノードに [A:1, B:3]（4個）が入ったとすると、
$$ \begin{align} H(m_L) &= -\frac{5}{6}\log_2 \frac{5}{6} – \frac{1}{6}\log_2 \frac{1}{6} = 0.650 \\ H(m_R) &= -\frac{1}{4}\log_2 \frac{1}{4} – \frac{3}{4}\log_2 \frac{3}{4} = 0.811 \end{align} $$
よって情報利得は、
$$ \text{IG} = 0.971 – \frac{6}{10}\times 0.650 – \frac{4}{10}\times 0.811 = 0.971 – 0.390 – 0.324 = 0.257 $$
この分割により、エントロピーが 0.257 だけ減少したことになります。
分割基準2: ジニ不純度（Gini Impurity）
定義
ジニ不純度は、エントロピーに代わるもう一つの分割基準です。あるノード内のクラス分布 $\{p_1, p_2, \dots, p_K\}$ に対して、
$$ G = 1 – \sum_{k=1}^{K} p_k^2 $$
と定義されます。ジニ不純度は「ノードからランダムに1つサンプルを取り出し、同じノード内のクラス分布に従ってラベルを割り当てたとき、誤分類される確率」と解釈できます。
導出を見てみましょう。クラス $k$ のサンプルを取り出す確率は $p_k$ です。取り出したサンプルに対して、ノード内の分布でラベルをランダムに付ける場合、正しいラベル $k$ が付く確率は $p_k$ なので、誤分類確率は、
$$ \begin{align} P(\text{誤分類}) &= \sum_{k=1}^{K} p_k \cdot (1 – p_k) \\ &= \sum_{k=1}^{K} p_k – \sum_{k=1}^{K} p_k^2 \\ &= 1 – \sum_{k=1}^{K} p_k^2 \\ &= G \end{align} $$
となり、ジニ不純度そのものになります。
2クラスの場合
クラス1の割合を $p$ とすると、
$$ G(p) = 1 – p^2 – (1-p)^2 = 2p(1-p) $$
$p = 0$ や $p = 1$ で $G = 0$（純粋）、$p = 0.5$ で $G = 0.5$（最も不純）となります。エントロピーと同様の傾向を示しますが、対数計算が不要なぶん計算が軽いため、scikit-learn のデフォルトではジニ不純度が使われています。
具体的な計算例
先ほどと同じ10個のサンプル [A:6, B:4] のノードに対して、
$$ G(\text{親}) = 1 – \left(\frac{6}{10}\right)^2 – \left(\frac{4}{10}\right)^2 = 1 – 0.36 – 0.16 = 0.48 $$
左の子 [A:5, B:1]、右の子 [A:1, B:3] の場合、
$$ \begin{align} G(m_L) &= 1 – \left(\frac{5}{6}\right)^2 – \left(\frac{1}{6}\right)^2 = 1 – 0.694 – 0.028 = 0.278 \\ G(m_R) &= 1 – \left(\frac{1}{4}\right)^2 – \left(\frac{3}{4}\right)^2 = 1 – 0.0625 – 0.5625 = 0.375 \end{align} $$
ジニ不純度の減少量は、
$$ \Delta G = 0.48 – \frac{6}{10}\times 0.278 – \frac{4}{10}\times 0.375 = 0.48 – 0.167 – 0.150 = 0.163 $$
CART アルゴリズム
CART（Classification and Regression Trees）は、決定木を構築する最も代表的なアルゴリズムです。scikit-learn もこのアルゴリズムを採用しています。
CARTの手順は次の通りです。
- 全特徴量と全閾値を探索: 現在のノードのデータに対し、各特徴量 $j = 1, \dots, p$ について、可能な閾値 $t$ を全探索する
- 最良の分割を選択: 不純度の減少量（情報利得またはジニ不純度の減少量）が最大となる $(j, t)$ の組を選ぶ
- データを分割: 選んだ条件で左右の子ノードにデータを振り分ける
- 再帰的に繰り返す: 各子ノードに対して 1〜3 を再帰的に適用する
- 停止条件: 以下のいずれかを満たしたら、そのノードを葉とする – ノードのサンプル数が閾値以下 – ノードの深さが最大深さに達した – 不純度がゼロ（純粋なノード） – それ以上分割しても不純度が改善しない
分類問題の葉ノードでは多数派クラスを、回帰問題では含まれるサンプルの平均値を予測値とします。
過学習と剪定
決定木は停止条件なしで成長させると、訓練データを完全に記憶してしまい、未知のデータに対する汎化性能が低下します。これが過学習（overfitting）です。
過学習を防ぐために、剪定（pruning）と呼ばれる手法が用いられます。
事前剪定（Pre-pruning）
木を成長させる段階で制限をかける方法です。
- 最大深さ（max_depth）: 木の深さに上限を設定する
- 最小サンプル数（min_samples_split）: 分割に必要な最小サンプル数
- 最小葉サンプル数（min_samples_leaf）: 葉に必要な最小サンプル数
- 最大葉数（max_leaf_nodes）: 葉ノードの総数に上限を設ける
事後剪定（Post-pruning）
まず木を十分に成長させてから、不要な枝を刈り取る方法です。代表的な手法にコスト複雑度剪定（Cost-Complexity Pruning）があります。
コスト複雑度は次の式で定義されます。
$$ R_\alpha(T) = R(T) + \alpha |T| $$
ここで $R(T)$ は木 $T$ の誤分類率（または不純度の合計）、$|T|$ は葉ノードの数、$\alpha \geq 0$ は正則化パラメータです。$\alpha$ を大きくするほど葉の数にペナルティがかかるため、木が小さく（単純に）なります。scikit-learn では ccp_alpha パラメータでこの値を設定できます。
決定木の限界
決定木には以下のような弱点があります。
- 高い分散（High Variance）: 訓練データの小さな変動で木の構造が大きく変わる。これはデータの最初の分割が後続のすべてに影響する階層的な構造に起因します
- 軸に平行な分割境界: 各ノードは1つの特徴量に対する閾値で分割するため、斜めの決定境界を直接表現できない
- 局所最適: 各ステップで貪欲に最良の分割を選ぶため、大域的に最適な木が得られる保証はない
特に分散の大きさは深刻な問題です。これを解決するアイデアが、複数の木を組み合わせるアンサンブル手法です。
バギング（Bootstrap Aggregating）
分散を減らす基本原理
統計学の基本的な事実として、独立な確率変数 $X_1, X_2, \dots, X_B$ の平均の分散は各変数の分散の $1/B$ になります。
$$ \text{Var}\left(\frac{1}{B}\sum_{b=1}^{B} X_b\right) = \frac{1}{B^2}\sum_{b=1}^{B}\text{Var}(X_b) = \frac{\sigma^2}{B} $$
つまり、独立な複数のモデルの予測を平均すれば、分散を削減できます。しかし現実には訓練データは1セットしかありません。
ブートストラップ法
そこでブートストラップ法（Bootstrap）を使います。サイズ $N$ の訓練データから、復元抽出（同じサンプルを複数回選んでよい）でサイズ $N$ のサブセットを $B$ 個生成します。各ブートストラップ標本で個別にモデルを学習させ、予測を集約（分類なら多数決、回帰なら平均）するのがバギングです。
ブートストラップ標本1つあたり、ある特定のサンプルが選ばれない確率は、
$$ \left(1 – \frac{1}{N}\right)^N \to \frac{1}{e} \approx 0.368 \quad (N \to \infty) $$
つまり各ブートストラップ標本には、元データの約 63.2% のユニークなサンプルが含まれます。残りの約 36.8% は「袋の外」に残り、これが後述する OOB スコアに利用されます。
ランダムフォレスト
バギングの改良
バギングだけでは、もし強い予測力を持つ特徴量が存在すると、どのブートストラップ標本で学習しても木の上位で同じ特徴量が選ばれ、木同士が相関してしまいます。相関のあるモデルの平均は、分散の削減効果が限定的です。
実際、$B$ 個のモデルが共通の相関 $\rho$ を持つとき、平均の分散は、
$$ \text{Var}\left(\bar{X}\right) = \rho \sigma^2 + \frac{1-\rho}{B}\sigma^2 $$
となります。$B \to \infty$ としても $\rho \sigma^2$ の項は残ります。つまり木同士の相関 $\rho$ を下げることが重要です。
特徴量のランダム選択
ランダムフォレスト（Random Forest, Breiman 2001）は、バギングに加えて各ノードの分割時に使える特徴量をランダムに制限します。
具体的には、$p$ 個の特徴量がある場合、各ノードでランダムに $m$ 個の特徴量だけを候補として選び、その中から最良の分割を探します。推奨される $m$ の値は、
$$ m = \lfloor \sqrt{p} \rfloor \quad (\text{分類の場合}) $$
$$ m = \lfloor p / 3 \rfloor \quad (\text{回帰の場合}) $$
この制約により、特定の強い特徴量が毎回選ばれることを防ぎ、木同士の相関 $\rho$ を小さくします。結果として、分散の削減効果がバギングよりも大きくなります。
ランダムフォレストのアルゴリズム
まとめると、ランダムフォレストのアルゴリズムは次の通りです。
- $b = 1, 2, \dots, B$ について:
– 訓練データからブートストラップ標本 $D_b$ を生成する（復元抽出、サイズ $N$）
– $D_b$ を使って決定木 $T_b$ を学習する。ただし各ノードの分割時に:
- $p$ 個の特徴量から $m$ 個をランダムに選ぶ
- 選ばれた $m$ 個の中で最良の分割を探す
- 木は剪定せず、十分に深く成長させる
- 予測時: – 分類: $B$ 本の木の予測の多数決 $\hat{y} = \text{mode}\{T_1(\bm{x}), \dots, T_B(\bm{x})\}$ – 回帰: $B$ 本の木の予測の平均 $\hat{y} = \frac{1}{B}\sum_{b=1}^{B} T_b(\bm{x})$
OOB（Out-of-Bag）スコア
各ブートストラップ標本に含まれなかったサンプル（約 36.8%）を OOB サンプルと呼びます。サンプル $i$ に対して、$i$ を含まないブートストラップ標本で学習された木だけで予測を行い、その正答率を計算したものが OOB スコアです。
OOB スコアの利点は、交差検証を行わなくてもテスト誤差の推定が得られることです。計算手順は次の通りです。
- 各サンプル $(\bm{x}_i, y_i)$ について、$i$ が OOB だった木の集合 $\mathcal{B}_i$ を特定する
- その木たちの予測を集約する: $\hat{y}_i^{\text{OOB}} = \text{mode}\{T_b(\bm{x}_i) : b \in \mathcal{B}_i\}$
- 全サンプルの OOB 予測から正答率を計算する
$$ \text{OOB Score} = \frac{1}{N}\sum_{i=1}^{N} \mathbb{1}(\hat{y}_i^{\text{OOB}} = y_i) $$
scikit-learn では oob_score=True を設定するだけで計算できます。
特徴量重要度
ランダムフォレストの大きな利点の一つが、特徴量重要度（Feature Importance）を自然に算出できることです。
最もよく使われる方法は不純度ベースの重要度（Mean Decrease Impurity, MDI）です。特徴量 $j$ の重要度は、全ての木・全てのノードで $j$ が分割に使われた際の不純度の加重減少量の平均として計算されます。
$$ \text{Importance}(j) = \frac{1}{B}\sum_{b=1}^{B}\sum_{m \in \mathcal{M}_b(j)} \frac{N_m}{N}\Delta G_m $$
ここで $\mathcal{M}_b(j)$ は木 $b$ で特徴量 $j$ を使って分割したノードの集合、$N_m$ はノード $m$ のサンプル数、$\Delta G_m$ は不純度の減少量です。全特徴量の重要度を合計すると1になるように正規化します。
もう一つの方法として Permutation Importance（並べ替え重要度）があります。これは特定の特徴量の値をランダムにシャッフルし、精度がどれだけ低下するかで重要度を測るもので、不純度ベースよりもバイアスが少ないとされています。
Python 実装
ここでは scikit-learn を使って決定木とランダムフォレストを実装し、決定境界とツリー構造を可視化します。
決定木の学習と可視化
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.model_selection import train_test_split
# データ生成
X, y = make_moons(n_samples=300, noise=0.25, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.3, random_state=42
)
# 決定木の学習（深さ制限あり）
dt = DecisionTreeClassifier(max_depth=5, random_state=42)
dt.fit(X_train, y_train)
print(f"訓練精度: {dt.score(X_train, y_train):.3f}")
print(f"テスト精度: {dt.score(X_test, y_test):.3f}")
# ツリー構造の可視化
fig, ax = plt.subplots(figsize=(20, 10))
plot_tree(dt, filled=True, feature_names=["x1", "x2"],
class_names=["Class 0", "Class 1"], ax=ax, fontsize=9)
plt.title("Decision Tree (max_depth=5)")
plt.tight_layout()
plt.show()
決定境界の可視化
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
# データ生成
X, y = make_moons(n_samples=300, noise=0.25, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.3, random_state=42
)
def plot_decision_boundary(model, X, y, ax, title):
"""決定境界を描画する関数"""
h = 0.02
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
ax.contourf(xx, yy, Z, alpha=0.3, cmap=plt.cm.RdYlBu)
ax.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.RdYlBu, edgecolors="k", s=20)
ax.set_title(title)
ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")
# 3つのモデルを比較
models = [
("Decision Tree (depth=3)", DecisionTreeClassifier(max_depth=3, random_state=42)),
("Decision Tree (no limit)", DecisionTreeClassifier(random_state=42)),
("Random Forest (100 trees)", RandomForestClassifier(n_estimators=100, random_state=42)),
]
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
for ax, (name, model) in zip(axes, models):
model.fit(X_train, y_train)
score = model.score(X_test, y_test)
plot_decision_boundary(model, X_test, y_test, ax, f"{name}\nAccuracy: {score:.3f}")
plt.tight_layout()
plt.show()
深さ制限のない決定木は訓練データに過剰に適合して複雑な境界を形成しますが、ランダムフォレストは滑らかで汎化性能の高い決定境界を描くことが確認できます。
ランダムフォレストの OOB スコアと特徴量重要度
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_wine
from sklearn.ensemble import RandomForestClassifier
# Wine データセットを使用
wine = load_wine()
X, y = wine.data, wine.target
# ランダムフォレストの学習（OOBスコア有効）
rf = RandomForestClassifier(
n_estimators=500,
max_features="sqrt",
oob_score=True,
random_state=42
)
rf.fit(X, y)
print(f"OOB Score: {rf.oob_score_:.3f}")
# 特徴量重要度の可視化
importances = rf.feature_importances_
indices = np.argsort(importances)[::-1]
fig, ax = plt.subplots(figsize=(10, 6))
ax.barh(range(len(importances)), importances[indices], align="center")
ax.set_yticks(range(len(importances)))
ax.set_yticklabels([wine.feature_names[i] for i in indices])
ax.set_xlabel("Feature Importance (MDI)")
ax.set_title("Random Forest Feature Importance (Wine Dataset)")
ax.invert_yaxis()
plt.tight_layout()
plt.show()
木の本数と精度の関係
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_wine
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import cross_val_score
# Wine データセット
wine = load_wine()
X, y = wine.data, wine.target
# 木の本数を変えてOOBスコアの推移を確認
n_trees_list = [1, 5, 10, 20, 50, 100, 200, 500]
oob_scores = []
for n in n_trees_list:
rf = RandomForestClassifier(n_estimators=n, oob_score=True, random_state=42)
rf.fit(X, y)
oob_scores.append(rf.oob_score_)
fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(n_trees_list, oob_scores, "o-", linewidth=2)
ax.set_xlabel("Number of Trees")
ax.set_ylabel("OOB Score")
ax.set_title("OOB Score vs Number of Trees")
ax.set_xscale("log")
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
木の本数を増やすと OOB スコアは改善し、ある程度の本数（100〜200本程度）で収束します。ランダムフォレストは木の数を増やしても過学習しにくいという特性があり、計算資源が許す限り多くの木を使うのが一般的です。
まとめ
本記事では、決定木とランダムフォレストについて解説しました。
- 決定木は条件分岐による直感的なモデルであり、分割基準としてエントロピー（情報利得）やジニ不純度が使われる
- CART アルゴリズムは全特徴量・全閾値を探索して最良の分割を貪欲に選ぶ
- 決定木は分散が大きく過学習しやすいため、事前剪定・事後剪定で対策する
- バギングはブートストラップ標本で複数のモデルを学習し、予測を集約することで分散を削減する
- ランダムフォレストはバギングに加え、各ノードで特徴量をランダムに $\sqrt{p}$ 個に制限することで木同士の相関を下げ、さらに高い汎化性能を実現する
- OOB スコアにより交差検証なしでテスト誤差を推定でき、特徴量重要度でモデルの解釈が可能になる
次のステップとして、アンサンブル学習のもう一つの柱である勾配ブースティング（Gradient Boosting）について学ぶと、XGBoost や LightGBM といった実務で広く使われるモデルの理解が深まります。