「年収が500万円以上 かつ 勤続年数が3年以上なら、ローンを承認」—— このような規則を、データから自動的に学習できたら、どれほど便利でしょうか。
決定木（Decision Tree）は、まさにそのような「if-then ルール」の集合体です。 直感的でありながら数学的に厳密なこの手法の仕組みを、一緒に見ていきましょう。
決定木とは何か — 人間の思考プロセスを数式にする
機械学習の手法の中で、決定木は「最も人間の思考プロセスに近い」とよく言われます。 なぜなら、私たちが日常的に行う判断——「雨が降っていたら傘を持つ、晴れなら必要なし」——を、 そのまま数学的に表現したものだからです。
少し具体的に考えてみましょう。銀行のローン審査を例に取ります。 「年収が500万円以上 かつ 勤続年数が3年以上なら承認、それ以外は審査が必要」 という判断基準は、誰でも直感的に理解できます。 決定木は、このような「if-then ルール」をデータから自動的に学習する手法です。
まず「特徴空間」という概念を押さえましょう。 特徴量とは各データが持つ属性のことです。家賃を予測するなら「駅からの距離（X₁）」「築年数（X₂）」 などが特徴量です。これらを軸にした空間が特徴空間です。
決定木の核心的なアイデアはシンプルです。この特徴空間を長方形の領域に再帰的に分割し、各領域で一定値を予測するというものです。 下のアニメーションを見てください。
座標系（特徴空間）に点群が現れ、縦・横の分割線によって3つの矩形領域に区切られていくアニメーションでは2つの特徴量 X₁（横軸）と X₂（縦軸）で構成された特徴空間が、 2段階の分割によって3つの矩形領域に分かれていきます。 各領域に含まれるデータ点の多数派クラス（または平均値）が、 その領域の予測値になります。
この手法が医療・金融・法律など「説明責任」が求められる分野で特に人気な理由はここにあります。 「このデータが青い領域（X₁ ≤ 2.5 かつ X₂ > 3.5 の範囲）に入ったから、クラスAと予測した」 という説明が自然に生まれるからです。
本章では、まず数値を予測する 回帰木 の構築方法を学び、 次にカテゴリを予測する 分類木 に進みます。 最後に決定木の強みと弱みを整理します。
回帰木の構築 — どこで分割するか
特徴空間を分割するアイデアは理解できました。でも、「どこで」「どの変数を使って」分割すれば 最も良い予測ができるのでしょうか？ここが決定木の核心です。
基本思想：分割後の各領域内で、データが「どれだけバラついているか」を 最小にする分割点を選ぶ。
具体的には、分割する変数 $j$（例：駅からの距離）と 分割点 $s$（例：500m）を使って2つの領域を作ります：
$$R_1(j,s) = \{X \mid X_j \leq s\}, \quad R_2(j,s) = \{X \mid X_j > s\}$$
次に、各領域の予測値を定数 $c_1$（領域1の代表値）、$c_2$（領域2の代表値）とし、 この予測がどれだけ外れているかを二乗誤差の合計で測ります：
$$\min_{j,s} \left[ \min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right]$$
この式は「各領域の予測値 $c_1, c_2$ を最適に選んだときの 二乗誤差の合計を最小にする、変数 $j$ と 分割点 $s$ の組み合わせを探す」という意味です。
嬉しいことに、この最適化には明快な解があります。 各領域の 最適な予測値は、その領域に含まれるデータの平均値 です：
$$\hat{c}_m = \text{ave}(y_i \mid x_i \in R_m)$$
下のアニメーションで、この「分割点スキャン」の過程を見てみましょう。 左パネルで分割線が左から右へ動き、右パネルで対応する誤差の変化が見られます。
左：分割線が左から右へスキャン。右：対応する誤差の変化（谷型曲線の最低点が最適分割点）このプロセスを 二分再帰分割（Binary Recursive Partitioning） と呼びます。 全ての変数と分割点の組み合わせをスキャンして最良の分割を選び、それを繰り返す貪欲アルゴリズム（greedy algorithm） です。
「貪欲（greedy）」とは、先のことを考えずに「今この瞬間の最善手」だけを選び続ける戦略です。 チェスで先を10手読む代わりに「今一番有利な手」だけ指し続けるイメージです。 全ての可能な分割の組み合わせを探索すると計算量が爆発的に増大するため、 この近似が実用上不可欠です。
木のサイズ問題 — 大きすぎる木は過学習する
分割を繰り返すほど、訓練データへの適合は良くなります。 しかし、これは危険な道です。
極端な場合を想像してください。各データ点が1つの葉（終端ノード）に対応するまで分割し続けると、 訓練誤差はゼロになります。でも、このモデルは「訓練データを丸暗記」しているだけで、 新しいデータには全く使えません。これが 過学習 です。
では、最適な木のサイズはどう決めるのでしょうか？
大きな木（青ノード＋緑の葉）から、不要な枝を剪定（赤くなって消える）して最適なサイズへ答えは「コスト複雑度剪定（Cost-Complexity Pruning）」です。 アニメーションのように、まず意図的に大きすぎる木 $T_0$ を育て、 次に少しずつ枝を刈り（剪定し）て、最適なサイズを交差検証で決めます。
最適化の基準となるコスト複雑度規準の記号を確認しましょう：
$$C_\alpha(T) = \sum_{m=1}^{|T|} N_m Q_m(T) + \alpha|T|$$
第1項 $\sum N_m Q_m(T)$ は木の訓練データへの適合度（小さいほど良い）、 第2項 $\alpha|T|$ は木の複雑さへのペナルティです。
$\alpha$ はモデルの学習には直接関与せず、外から設定する「調整つまみ」です。 このような調整パラメータを ハイパーパラメータ と呼びます。
$\alpha$ を大きくすると複雑さへのペナルティが強くなり、 小さい木が選ばれます。交差検証で$\alpha$ の最適値を選べば、汎化性能の高い木が得られます。
分類木 — 不純度という考え方
ここまでは数値を予測する「回帰木」でした。カテゴリ（クラス）を予測する「分類木」では、 分割の良さをどう測ればよいでしょうか？
回帰では「誤差の二乗和」が使えましたが、分類には3つの指標があります。 まず記号を確認します：ノード $m$ に含まれるデータのうち、 クラス $k$ に属するデータの割合を $p_{mk}$ とします。
下のアニメーションで、3つの指標の形を比べてみましょう。横軸はクラス1の割合$p$（0から1）、縦軸は不純度の値です。
赤：誤分類率（折れ線型）、青：Gini指標（より丸い山型）、黄：交差エントロピー（最も丸い山型）3つの指標を整理します：
誤分類率（Misclassification Rate）
$$1 - p_{\hat{k}(m)}$$
最多数クラスに分類したときの誤り率。シンプルですが、 後述する理由から分割の最適化には向きません。
$$\sum_{k=1}^{K} p_{mk}(1 - p_{mk})$$
全クラスに渡る「不確実性」の指標。ノードが純粋（全データが同じクラス）なら0、 全クラスが均等なら最大になります。 アニメーションの青い放物線がGini指標です。
$$-\sum_{k=1}^{K} p_{mk} \log p_{mk}$$
情報理論から来る不純度指標で、「ノード内の情報量の多さ」を測ります。 全データが同じクラスならゼロ、クラスが均等に混ざるほど大きくなります。 アニメーションの黄色い曲線が交差エントロピーです。
なぜ Gini や交差エントロピーが好まれるのか？
アニメーションで比べると、誤分類率（赤）は山が「とがった」形をしています。 分割点付近で値がほぼ平らになり、「どの分割が良いか」の判断が難しいのです。
一方、Gini と交差エントロピーはクラス確率の分布全体を見るため、 微妙な改善も検出できます。また、微分可能なため数値最適化に適しています。 実践では Gini 指標がよく使われます（計算が少し軽いため）。
決定木の強みと弱み — 組み合わせると真価を発揮する
決定木は直感的で強力ですが、万能ではありません。 その特性を正直に見ていきましょう。
強み
- 解釈可能性：予測結果を「if-then ルール」として説明できる。 医療診断や信用審査など、説明責任が必要な場面で非常に有用。
- 非線形関係の自動検出：複雑な交互作用や非線形性を自然に捉える。 事前に「どの変数を非線形にするか」を決める必要がない。
- 混合型データへの対応：カテゴリ変数も直接扱える。 数値変数と混合しても前処理が最小限で済む。
弱み：不安定性
ここが決定木の最大の弱点です。下のアニメーションを見てください。
左右で点の位置が微妙に異なるだけで、境界線のパターンが全く変わってしまうアニメーションで見たように、訓練データを 少し変えると木構造が大きく変わります。 これは決定木の「階層的な性質」に起因します。 もし最初の分割（根ノード）が変わると、その下の全ての分割も影響を受けるため、 小さな変化が大きな違いを生みます。
弱み：滑らかさの欠如
決定木の予測値は段階的です（長方形の境界が生む急な変化）。 本当は滑らかな関数がある場合、多くの細かい分割が必要になります。
弱み：加法構造の捕捉が困難
例えば次のような関係を決定木で表すのは非効率です：
$$Y = c_1 \cdot I(X_1 < t_1) + c_2 \cdot I(X_2 < t_2)$$
ここで $I(\cdot)$ は括弧内の条件が真なら1、偽なら0を返す関数です。 このような「変数ごとに独立した効果が加算される構造」を決定木で表すには、 非効率な多数の分割が必要になります。
弱みへの対処法
これらの弱点への解決策も提案されています。
不安定性への根本的な対策は「バギング（Bagging）」や 「ランダムフォレスト」です——多数の決定木を作って予測を多数決（平均）することで、 1本の木より安定した予測が得られます（第15章で詳しく扱います）。
加法構造の問題は「MARS（Multivariate Adaptive Regression Splines）」という手法で改善されます（第9.4節）。
決定木は「1本では限界があるが、組み合わせると非常に強力」という性質を持つ手法として、 現代の機械学習における基礎的な部品となっています。 次のページでは、決定木とは別のアプローチで加法構造を直接学習する「MARS」を見ていきましょう。