決定木の分割基準とCART/ID3の内部

決定木は「再帰的二分割」で育つ

決定木（decision tree） は、特徴量に対する条件分岐を木構造で連ねて予測する教師あり学習モデルです。学習の本質は単純で、データを最もよく分離する1つの分割を選び、できた部分集合に対して同じ手続きを再帰的に繰り返すことにあります。この貪欲（greedy）かつトップダウンな成長を 再帰的二分割（recursive binary splitting） と呼びます。

各ノードでアルゴリズムがやることは、概念的には総当たりです。

全特徴量 j について:
  特徴量 j の取りうるしきい値（分割点）t をすべて試す:
    分割「x_j <= t か否か」で左右の子に分ける
    左右の子の「不純度の加重和」を計算する
最も不純度の加重和が小さい (j, t) を採用する
→ できた左右の子について同じ手続きを再帰

「不純度（impurity）」とは、そのノードに含まれるサンプルのラベルがどれだけ混ざっているかの尺度です。すべて同じクラスなら不純度ゼロ、半々に混ざると最大になります。よい分割とは、分割後の子ノードがそれぞれ「純粋」に近づく分割であり、これを定量化するのが分割基準です。

分類の不純度：ジニとエントロピー

分類木で使う代表的な不純度が ジニ不純度（Gini impurity） と エントロピー（entropy） です。ノード内のクラス k の割合を p_k とすると、それぞれ次で定義します。

ジニ不純度:     Gini = 1 - Σ_k (p_k)^2
エントロピー:    H    = - Σ_k p_k · log2(p_k)

どちらも、すべて1クラスなら 0、クラスが均等に混ざるほど大きくなります。2クラスで陽性率を p とすると、ジニは 2p(1-p)、エントロピーは -p·log2(p) - (1-p)·log2(1-p) で、どちらも p = 0.5 で最大、p = 0 と p = 1 で最小という同じ形の凸関数です。実用上、両者で得られる木はほぼ同じになります。

分割の良し悪しは、親の不純度から子の不純度の加重和を引いた減少量で測ります。エントロピーを使った場合、この減少量が 情報利得（information gain） です。

情報利得 = H(親) - [ (N_L/N)·H(左) + (N_R/N)·H(右) ]
  N    = 親ノードのサンプル数
  N_L, N_R = 左右の子のサンプル数（重み = サンプル割合）

情報利得は情報理論の言葉で言えば「その特徴量を知ることでクラスについての不確実性がどれだけ減るか」、すなわち相互情報量に相当します。ジニ不純度を使う場合も同じ式の H をジニに置き換えるだけで、不純度の加重和が最小になる分割＝減少量が最大になる分割を選ぶ点は変わりません。

ID3・C4.5・CARTの系譜

決定木のアルゴリズムは大きく3系統あり、分割基準と木の形が異なります。

ID3 は情報利得が最大の特徴量で分割します。しかしここに弱点があります。情報利得は取りうる値が多い特徴量を不当に優遇するのです。極端な例として「ID番号」のような全行で異なる特徴量は、各子が1サンプルずつの純粋なノードになり情報利得が最大化されますが、当然まったく汎化しません。

C4.5 はこの偏りを 情報利得比（gain ratio） で補正します。分割そのものが生む情報量（分割情報, split information）で情報利得を割り、値が多い特徴量にペナルティをかけます。

分割情報:  SplitInfo = - Σ_v (N_v/N)·log2(N_v/N)   v は特徴量の各値
情報利得比: GainRatio = 情報利得 / SplitInfo

分割の枝が多いほど SplitInfo が大きくなるので、多値特徴量の見かけ上の利得が割り引かれます。C4.5 はさらに連続値のしきい値分割・欠損値処理・学習後の剪定を備え、ID3 を実用レベルに引き上げた版です。

CART（Classification And Regression Trees） は思想が異なり、常に二分木を作ります。多値・連続を問わずすべての分割を「x_j <= t か否か」という二択に落とすため、ID3 の多値バイアス問題が構造的に起きにくくなります。scikit-learn の DecisionTreeClassifier / DecisionTreeRegressor はこの CART を基盤に実装されており、勾配ブースティング（GBDT）やランダムフォレストの弱学習器もこの二分木です。

回帰木：不純度を「分散」に置き換える

CART の強みは、不純度の定義を差し替えるだけで回帰にも使える点です。回帰木では各ノードの予測値をそこに属するサンプルの平均とし、不純度を**二乗誤差（=分散の N 倍）**で測ります。

ノードの予測:   c = (1/N) Σ y_i             （ノード内の目的変数の平均）
ノードの不純度:  Σ (y_i - c)^2                （二乗誤差 = 分散 × N）

分割の評価: 親の二乗誤差 - [ 左の二乗誤差 + 右の二乗誤差 ]
→ この「分散減少（variance reduction）」が最大の分割を選ぶ

直感的には、分割後の左右で目的変数のばらつきが最も小さくなる切り方を探します。分類のジニ・エントロピーが「クラスの混ざり具合」を測ったのと完全に対応しており、不純度関数を分散に置き換えただけで同じ再帰的二分割の枠組みが回帰に拡張されます。予測時は、入力が落ち着いた葉ノードの平均値（分類なら多数決クラス）を返します。

剪定：コスト複雑度で過学習を抑える

木を制限なく伸ばすと、最終的に各葉が1サンプルだけの完全に純粋な木になり、訓練データを丸暗記して過学習します。これを抑えるのが 剪定（pruning） です。CART が採用する コスト複雑度剪定（cost-complexity pruning, 別名 weakest-link pruning） は、木の予測誤差に葉の数へのペナルティを加えた評価量を最小化します。

評価量:  R_alpha(T) = R(T) + alpha · |T|
  R(T)  = 木 T の予測誤差（分類なら誤分類率、回帰なら二乗誤差）
  |T|   = 木 T の葉ノードの数（複雑さ）
  alpha = 複雑さへのペナルティ係数（alpha >= 0）

alpha が 0 なら誤差最小のフルツリーが選ばれ、alpha を上げるほど「葉が多い＝複雑な木」が不利になり、木は小さく剪定されます。アルゴリズムは、部分木を1枚の葉に潰したときに R_alpha の増加が最も小さい（=単位ペナルティあたりの誤差増が最小の）枝から順に切り戻し、alpha を増やしながら入れ子になった部分木の列を生成します。この「最も弱いリンク」を切るのが weakest-link の名の由来です。

最終的にどの alpha を採るかは交差検証で決めます。各 alpha に対応する剪定木を検証データで評価し、汎化誤差が最小になる alpha を選びます。scikit-learn では cost_complexity_pruning_path で alpha の候補列を取得し、ccp_alpha に設定して剪定を適用します。

決定木が過学習しやすいのは、深い木が高バリアンス（訓練データの小さな変化で構造が大きく変わる）だからです。剪定や深さ制限は木の複雑さを下げてバリアンスを抑える操作であり、その効きはバイアス・バリアンスの観点で整理すると一貫して理解できます。単体の木の高バリアンスを、多数の木の平均（ランダムフォレスト）や逐次補正（ブースティング）で抑えるのがアンサンブル手法の出発点です。

まとめ

決定木は再帰的二分割で成長し、各ノードで子の不純度の加重和が最小（不純度の減少が最大）になる分割を貪欲に選ぶのが共通原理です。分類はジニ不純度かエントロピー（その減少が情報利得）、回帰は分散（二乗誤差）の減少を不純度に使います。ID3 は情報利得で分割しますが多値特徴量に偏るため、C4.5 が情報利得比で補正し、CART は常に二分木で分類・回帰を統一的に扱います。伸ばし切った木は過学習するので、CART はコスト複雑度剪定 R(T) + alpha·|T| で葉数にペナルティを課し、交差検証で最適な alpha を選んで切り戻します。分割基準と剪定の原理を押さえれば、ハイパーパラメータ調整は当てずっぽうではなく、不純度減少とバリアンス抑制のバランスを動かす意図的な操作になります。