「この患者は病気かどうか」を判定するとき、医師は一連の質問を繰り返して診断を絞り込みます。「熱はありますか？」→ はい → 「咳はありますか？」→ はい → 「旅行歴は？」…。この質問の連鎖で分類に到達するプロセスを、そのまま数学的に定式化したのが決定木（decision tree）です。
決定木は機械学習で最も直感的なアルゴリズムの一つです。モデルの判断過程が「if-then-else」のルールとして可視化でき、専門家でなくてもモデルの根拠を理解できます。この解釈可能性は、医療・金融・法律など説明責任が求められる分野で非常に重要です。
決定木を理解すると、以下のような場面で活用できます。
- 解釈可能なモデル: モデルの判断理由を人間が理解できる形で提示する
- ランダムフォレストの基盤: アンサンブル手法の構成要素として
- 特徴量の重要度: どの特徴量が分類に重要かを定量化する
- 非線形な決定境界: 特徴量空間の軸平行な分割で複雑なパターンを捉える
本記事の内容
- 決定木の基本概念と構造
- 分割基準（エントロピー、ジニ不純度、情報利得）
- CARTアルゴリズムの数理
- 枝刈りと過学習の制御
- Pythonでのスクラッチ実装と可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 交差エントロピーを完全理解 — エントロピーの基礎
- 評価指標の全体像 — 分類の評価方法
決定木とは
木構造による分類
決定木は、各内部ノード（internal node）で特徴量に関する条件分岐を行い、葉ノード（leaf node）で最終的な予測を出力するモデルです。
例えば、果物の分類を考えると: – 「色は赤いか？」→ はい → 「直径は5cm以上か？」→ はい → リンゴ – 「色は赤いか？」→ いいえ → 「直径は3cm以下か？」→ はい → ブドウ
この構造は、特徴量空間を軸平行な超平面で再帰的に分割していくことに対応します。2次元の場合、各分割は $x_1 \leq t$ や $x_2 \leq t$ の形であり、最終的に特徴量空間が長方形の領域に分かれます。
分割基準の必要性
木を構築するとき、各ノードで「どの特徴量を、どの値で分割するか」を決める必要があります。良い分割とは、分割後の子ノードが可能な限り「純粋」（一つのクラスが支配的）になるような分割です。
この「純粋さ」を定量化するのが不純度（impurity）の概念であり、代表的な不純度の指標がエントロピーとジニ不純度です。
エントロピーと情報利得
エントロピー（不純度の指標）
ノードに含まれるデータのクラス分布を $\bm{p} = (p_1, p_2, \ldots, p_K)$ とするとき、エントロピーは
$$ \begin{equation} H(\bm{p}) = -\sum_{k=1}^K p_k \log_2 p_k \end{equation} $$
$p_k = 0$ のときは $0 \log_2 0 = 0$ と定義します。
エントロピーは「不確実性の度合い」を測ります。
- 全てのサンプルが同じクラス（$p_k = 1$）: $H = 0$（完全に純粋）
- 全クラスが等確率（$p_k = 1/K$）: $H = \log_2 K$（最大の不純度）
情報利得（Information Gain）
特徴量 $x_j$ の値 $t$ で分割したとき、不純度がどれだけ減少するかを情報利得（information gain）で測ります。
$$ \begin{equation} \text{IG}(S, x_j, t) = H(S) – \frac{|S_L|}{|S|}H(S_L) – \frac{|S_R|}{|S|}H(S_R) \end{equation} $$
$S$ は親ノードのデータ集合、$S_L$ と $S_R$ は分割後の左右の子ノードのデータ集合です。情報利得が最大になる $(x_j, t)$ の組が、そのノードでの最適な分割です。
情報利得は必ず非負です。分割によって不純度の加重平均が減少することが保証されています（エントロピーの凹性による）。
ジニ不純度
定義
ジニ不純度（Gini impurity）はエントロピーの代替として広く使われます。
$$ \begin{equation} G(\bm{p}) = 1 – \sum_{k=1}^K p_k^2 = \sum_{k=1}^K p_k(1 – p_k) \end{equation} $$
ジニ不純度は「ランダムに選んだサンプルが誤分類される確率」と解釈できます。データセットからランダムにサンプルを1つ選び、そのラベルをクラス分布 $\bm{p}$ に従ってランダムに割り当てたとき、元のラベルと一致しない確率です。
エントロピーとジニ不純度の比較
二値分類（$K = 2$）の場合: – エントロピー: $H(p) = -p\log_2 p – (1-p)\log_2(1-p)$、最大値 $1$（$p = 0.5$） – ジニ不純度: $G(p) = 2p(1-p)$、最大値 $0.5$（$p = 0.5$）
両者は非常に似た形状をしており、実用的にはほとんど同じ結果を与えます。scikit-learnのデフォルトはジニ不純度です。計算が対数を含まないため若干高速です。
import numpy as np
import matplotlib.pyplot as plt
p = np.linspace(0.001, 0.999, 500)
# 二値分類の不純度
entropy = -p * np.log2(p) - (1-p) * np.log2(1-p)
gini = 2 * p * (1 - p)
misclass = np.minimum(p, 1-p) # 誤分類率
fig, axes = plt.subplots(1, 2, figsize=(14, 5.5))
# (a) 不純度の比較
ax = axes[0]
ax.plot(p, entropy, "b-", linewidth=2.5, label="Entropy $H(p)$")
ax.plot(p, gini, "r-", linewidth=2.5, label="Gini $2p(1-p)$")
ax.plot(p, misclass, "g-", linewidth=2.5, label="Misclassification $\\min(p, 1-p)$")
ax.set_xlabel("$p$ (probability of class 1)", fontsize=12)
ax.set_ylabel("Impurity", fontsize=12)
ax.set_title("Impurity Measures for Binary Classification", fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
# (b) 情報利得の例
ax = axes[1]
# 親ノード: p=0.5 → 分割後のクラス比率
p_left = np.linspace(0.01, 0.99, 200)
ratio = 0.6 # 左ノードのデータ割合
# 右ノードのクラス比率を計算: 0.5 = ratio * p_left + (1-ratio) * p_right
p_right = (0.5 - ratio * p_left) / (1 - ratio)
valid = (p_right > 0) & (p_right < 1)
p_left_valid = p_left[valid]
p_right_valid = p_right[valid]
# 情報利得（エントロピーベース）
H_parent = 1.0 # H(0.5) = 1 for binary
H_left = -p_left_valid * np.log2(p_left_valid) - (1-p_left_valid) * np.log2(1-p_left_valid)
H_right = -p_right_valid * np.log2(p_right_valid) - (1-p_right_valid) * np.log2(1-p_right_valid)
IG = H_parent - ratio * H_left - (1-ratio) * H_right
ax.plot(p_left_valid, IG, "b-", linewidth=2.5)
ax.set_xlabel("$p_{left}$ (class 1 ratio in left child)", fontsize=12)
ax.set_ylabel("Information Gain", fontsize=12)
ax.set_title("Information Gain (parent: p=0.5, left ratio=60%)", fontsize=13)
ax.grid(True, alpha=0.3)
# 最大値を表示
best_idx = np.argmax(IG)
ax.axvline(p_left_valid[best_idx], color="red", linestyle="--", linewidth=1.5,
label=f"Best split: $p_L$={p_left_valid[best_idx]:.2f}")
ax.legend(fontsize=10)
plt.tight_layout()
plt.savefig("decision_tree_impurity.png", dpi=150, bbox_inches="tight")
plt.show()
このグラフから、不純度指標と情報利得の特性が読み取れます。
-
左図（不純度の比較）: エントロピー（青）とジニ不純度（赤）はほぼ同じ形状で、$p = 0.5$ で最大、$p = 0$ または $p = 1$ で0になります。誤分類率（緑）は線形で、分割に対する感度がエントロピーやジニ不純度より低いため、実用的にはあまり使われません
-
右図（情報利得）: 親ノードが $p = 0.5$（最大エントロピー）のとき、左子ノードのクラス比率が0か1に近いほど情報利得が大きくなります。つまり、分割後の子ノードが純粋になるほど良い分割です
CARTアルゴリズム
アルゴリズムの概要
CART（Classification and Regression Trees; Breiman et al., 1984）は、最も広く使われている決定木アルゴリズムです。
ステップ1: 最適な分割の探索
各ノードで、全ての特徴量 $x_j$ と全ての候補閾値 $t$ について不純度の減少を計算し、最大の減少を与える $(x_j^*, t^*)$ で分割します。
ステップ2: 再帰的な分割
左右の子ノードに対して同じ処理を再帰的に適用します。
ステップ3: 停止条件
以下のいずれかを満たすとき、分割を停止して葉ノードとします。 – ノードのサンプル数が最小値以下 – ノードの深さが最大深さに到達 – ノードが純粋（全サンプルが同じクラス） – 情報利得が閾値以下
Pythonでのスクラッチ実装
import numpy as np
import matplotlib.pyplot as plt
class Node:
"""決定木のノード"""
def __init__(self, depth=0):
self.depth = depth
self.feature_idx = None
self.threshold = None
self.left = None
self.right = None
self.value = None # 葉ノードの予測値（クラス分布）
self.prediction = None # 予測クラス
class DecisionTreeClassifier:
"""CARTアルゴリズムによる決定木分類器"""
def __init__(self, max_depth=5, min_samples_split=2, criterion="gini"):
self.max_depth = max_depth
self.min_samples_split = min_samples_split
self.criterion = criterion
self.root = None
self.n_classes = None
def _impurity(self, y):
"""不純度の計算"""
n = len(y)
if n == 0:
return 0
counts = np.bincount(y, minlength=self.n_classes)
probs = counts / n
if self.criterion == "gini":
return 1 - np.sum(probs ** 2)
else: # entropy
probs = probs[probs > 0]
return -np.sum(probs * np.log2(probs))
def _best_split(self, X, y):
"""最適な分割を探索"""
n, d = X.shape
best_gain = -np.inf
best_feature = None
best_threshold = None
parent_impurity = self._impurity(y)
for j in range(d):
# ユニークな値をソート
thresholds = np.unique(X[:, j])
# 隣接する値の中点を候補閾値とする
thresholds = (thresholds[:-1] + thresholds[1:]) / 2
for t in thresholds:
left_mask = X[:, j] <= t
right_mask = ~left_mask
if left_mask.sum() < 1 or right_mask.sum() < 1:
continue
# 情報利得の計算
n_l = left_mask.sum()
n_r = right_mask.sum()
gain = parent_impurity - (n_l/n) * self._impurity(y[left_mask]) \
- (n_r/n) * self._impurity(y[right_mask])
if gain > best_gain:
best_gain = gain
best_feature = j
best_threshold = t
return best_feature, best_threshold, best_gain
def _build_tree(self, X, y, depth):
"""木の再帰的構築"""
node = Node(depth=depth)
node.value = np.bincount(y, minlength=self.n_classes) / len(y)
node.prediction = np.argmax(node.value)
# 停止条件
if (depth >= self.max_depth or
len(y) < self.min_samples_split or
len(np.unique(y)) == 1):
return node
# 最適な分割の探索
feature, threshold, gain = self._best_split(X, y)
if feature is None or gain <= 0:
return node
node.feature_idx = feature
node.threshold = threshold
left_mask = X[:, feature] <= threshold
node.left = self._build_tree(X[left_mask], y[left_mask], depth + 1)
node.right = self._build_tree(X[~left_mask], y[~left_mask], depth + 1)
return node
def fit(self, X, y):
self.n_classes = len(np.unique(y))
self.root = self._build_tree(X, y, depth=0)
return self
def _predict_one(self, x, node):
if node.left is None:
return node.prediction
if x[node.feature_idx] <= node.threshold:
return self._predict_one(x, node.left)
return self._predict_one(x, node.right)
def predict(self, X):
return np.array([self._predict_one(x, self.root) for x in X])
# テスト: 2次元データの分類
np.random.seed(42)
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=300, noise=0.25, random_state=42)
# スクラッチ実装
tree_scratch = DecisionTreeClassifier(max_depth=5, criterion="gini")
tree_scratch.fit(X, y)
# scikit-learnとの比較
from sklearn.tree import DecisionTreeClassifier as SklearnDT
tree_sklearn = SklearnDT(max_depth=5, criterion="gini", random_state=42)
tree_sklearn.fit(X, y)
fig, axes = plt.subplots(1, 2, figsize=(14, 5.5))
for ax, model, title in zip(axes,
[tree_scratch, tree_sklearn],
["Scratch Implementation", "scikit-learn"]):
# 決定境界の描画
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.linspace(x_min, x_max, 200),
np.linspace(y_min, y_max, 200))
Z = model.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
ax.contourf(xx, yy, Z, alpha=0.3, cmap="RdBu")
ax.scatter(X[y==0, 0], X[y==0, 1], c="blue", s=20, alpha=0.6, label="Class 0")
ax.scatter(X[y==1, 0], X[y==1, 1], c="red", s=20, alpha=0.6, label="Class 1")
acc = np.mean(model.predict(X) == y)
ax.set_title(f"{title} (Acc={acc:.3f})", fontsize=13)
ax.set_xlabel("$x_1$", fontsize=12)
ax.set_ylabel("$x_2$", fontsize=12)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig("decision_tree_scratch.png", dpi=150, bbox_inches="tight")
plt.show()
このグラフから、スクラッチ実装の正しさが検証できます。
-
左図（スクラッチ実装）: 二つの三日月形のデータを軸平行な長方形の分割で近似的に捉えています。決定境界が階段状なのは決定木の特徴で、各分割が1つの特徴量の閾値による条件分岐に対応しています
-
右図（scikit-learn）: ほぼ同じ決定境界と精度を示しており、スクラッチ実装がCARTアルゴリズムを正しく再現していることが確認できます
決定木の過学習と枝刈り
過学習の問題
決定木は制約なしに成長させると、訓練データの各サンプルを完全に分類する「完全な木」になります。しかし、これはノイズまで学習した過学習状態です。
事前枝刈り（Pre-pruning）
木の成長を事前に制限する方法です。
- 最大深さ（
max_depth）: 木の深さを制限 - 最小サンプル数（
min_samples_split）: 分割に必要な最小サンプル数 - 最小情報利得（
min_impurity_decrease）: 分割に必要な最小の不純度減少
事後枝刈り（Post-pruning / Cost-Complexity Pruning）
完全な木を成長させた後に、不要な枝を刈り込む方法です。コスト複雑度枝刈りでは、木 $T$ の目的関数を
$$ R_\alpha(T) = R(T) + \alpha|T| $$
$R(T)$ は木の誤分類率、$|T|$ は葉ノードの数、$\alpha$ は複雑度パラメータです。$\alpha$ を大きくするほど小さな木が選ばれます。
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score
from sklearn.datasets import make_moons
np.random.seed(42)
X, y = make_moons(n_samples=300, noise=0.3, random_state=42)
fig, axes = plt.subplots(1, 3, figsize=(16, 5))
depths = [2, 5, 20]
titles = ["Underfitting (depth=2)", "Good fit (depth=5)", "Overfitting (depth=20)"]
for ax, depth, title in zip(axes, depths, titles):
model = DecisionTreeClassifier(max_depth=depth, random_state=42).fit(X, y)
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.linspace(x_min, x_max, 200),
np.linspace(y_min, y_max, 200))
Z = model.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
ax.contourf(xx, yy, Z, alpha=0.3, cmap="RdBu")
ax.scatter(X[y==0, 0], X[y==0, 1], c="blue", s=20, alpha=0.6)
ax.scatter(X[y==1, 0], X[y==1, 1], c="red", s=20, alpha=0.6)
train_acc = model.score(X, y)
cv_score = cross_val_score(model, X, y, cv=5).mean()
ax.set_title(f"{title}\nTrain={train_acc:.3f}, CV={cv_score:.3f}", fontsize=12)
ax.set_xlabel("$x_1$", fontsize=11)
ax.set_ylabel("$x_2$", fontsize=11)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig("decision_tree_depth.png", dpi=150, bbox_inches="tight")
plt.show()
このグラフから、決定木の深さと過学習の関係が読み取れます。
-
左図（depth=2）: 分割が少なすぎて三日月形の決定境界を十分に捉えられず、訓練精度もCV精度も低い未学習状態です
-
中央図（depth=5）: 適度な複雑さで決定境界が三日月形によくフィットしています。訓練精度とCV精度の差が小さく、バランスの取れた状態です
-
右図（depth=20）: 非常に複雑な決定境界で、訓練データの個々のノイズにまでフィットしています。訓練精度は非常に高いですがCV精度との差が大きく、過学習していることがわかります
まとめ
本記事では、決定木の理論とCARTアルゴリズムの実装について解説しました。
- 決定木は特徴量空間を軸平行な超平面で再帰的に分割する、解釈可能な分類・回帰モデル
- エントロピーとジニ不純度はノードの「純粋さ」を測る不純度指標で、実用上ほぼ同じ結果を与える
- 情報利得は分割による不純度の減少量であり、CARTは情報利得を最大化する分割を貪欲に選ぶ
- 過学習の制御には事前枝刈り（最大深さ、最小サンプル数）と事後枝刈り（コスト複雑度）がある
- 決定木単体では汎化性能に限界があるが、アンサンブル手法（ランダムフォレスト、勾配ブースティング）の基盤として極めて重要
次のステップとして、以下の記事も参考にしてください。
- ランダムフォレストの理論と実装 — 決定木のBagging
- 勾配ブースティングの理論と実装 — 決定木のBoosting
- アンサンブル学習の全体像 — アンサンブルの体系的理解