CARTアルゴリズム

1 アルゴリズムの基本原理

1.1 二分木の構造

CARTアルゴリズムが生成する決定木は二分木（バイナリツリー）である。各内部ノードは一つの特徴量とその分割閾値を持ち、ノードからは常に二つの子ノード（左子ノードと右子ノード）が分岐する。根ノードから終端ノード（葉）に至る各経路が一つのif-thenルールに対応する。

1.2 再帰的分割の仕組み

CARTはトップダウン方式で再帰的にデータを分割する。各ノードにおいて、すべての特徴量と可能な分割点を評価し、選択された分割基準を最適化する分割を選ぶ。分割後の各子ノードに対し、同じプロセスを再帰的に適用する。分割は特徴空間を矩形領域に分割することに相当し、各領域が一つの予測値を保持する。

1.3 停止条件と終端ノード

分割の再帰は以下の条件を満たすと停止する：ノード内の全サンプルが同一クラスに属する、またはサンプル数が事前設定した最小値（例：min_samples_leaf）に達する、または最大深さに達する、または分割による不純度の改善が閾値未満である。停止したノードは終端ノードとなり、分類問題では多数決によるクラスラベル、回帰問題では平均値が予測値として割り当てられる。

2 分割基準

2.1 分類木におけるジニ係数

分類木ではジニ不純度（Gini impurity）を分割基準に用いる。ジニ係数はノード内のクラス分布の不純度を測定し、値が小さいほど純度が高い。ノードtにおけるジニ係数は \( G(t) = 1 - \sum_{i=1}^{K} p_i^2 \) で定義される（Kはクラス数、p_iはクラスiの割合）。分割の際には、分割前後のジニ係数の減少が最大となる特徴量と閾値を選択する。

2.2 回帰木における二乗誤差最小化

回帰木では分割基準に二乗誤差最小化を用いる。各ノードにおける二乗誤差は \( \sum_{i \in t} (y_i - \bar{y}_t)^2 \) で計算され（\(\bar{y}_t\)はノード内の平均値）、分割後の二つの子ノードの二乗誤差の和が最も小さくなる分割を選ぶ。この基準により、領域内の応答変数の分散を最小化する。

2.3 その他の分割指標（情報ゲインとの比較）

CARTは情報ゲイン（ID3やC4.5で使用）ではなくジニ係数と二乗誤差を採用する。情報ゲインはエントロピーをベースとするが、ジニ係数は対数計算が不要で計算コストが低く、両者は多くの状況で類似した結果をもたらす。回帰木の二乗誤差は連続変数に自然に適合する一方、情報ゲインは連続値に対して追加の離散化が必要になる。

3 木の成長と剪定

3.1 最大深さと最小サンプル数の制御

木の成長を制限するハイパーパラメータとして、最大深さ（max_depth）、ノードの最小サンプル数（min_samples_split）、終端ノードの最小サンプル数（min_samples_leaf）などがある。これらを設定することで、木が過度に複雑になるのを防ぎ、過学習を軽減できる。

3.2 コスト複雑性剪定（Cost-Complexity Pruning）

3.3 クロスバリデーションによる最適木の選択

最適なα（および対応する剪定木）を選択するために、クロスバリデーションが用いられる。各αに対して剪定木の交差検証誤差を計算し、最小誤差または1標準誤差ルール（最も単純な木を選ぶ）に基づいて最終的な木を決定する。これにより汎化性能を向上させる。

4 アルゴリズムの特徴と限界

4.1 長所

4.1.1 解釈可能性の高さ

CARTの生成する二分木は可視化が容易で、各分岐が明確なif-thenルールとして解釈できる。そのため、モデルの意思決定プロセスを人間が理解しやすく、説明責任が求められる分野（医療、金融など）で広く利用される。

4.1.2 欠損値と外れ値への頑健性

CARTは欠損値を代理分割（surrogate splits）により処理でき、完全な補完前処理が不要である。また、外れ値に対しては、分割が閾値ベースで行われるため、外れ値が木の構造に与える影響は比較的小さい。

4.2 短所

4.2.1 分散の大きさ（過学習傾向）

CARTはデータのわずかな変化で木全体の構造が大きく変わる可能性があり、分散が大きい。剪定を行っても、単一の木は過学習しやすいという欠点がある。この問題は後のアンサンブル学習により改善される。

4.2.2 線形関係への非効率性

CARTは軸平行な分割（各特徴量に沿った分割）に基づくため、線形や対角線上の複雑な関係を捉えるには深い木が必要になり効率が悪い。また、単調な線形関係に対しても階段状の近似となり、精度が十分でない場合がある。

5 応用と拡張

5.1 実データでの典型的な使用例（医療診断、顧客分析）

医療診断では、患者の症状や検査結果から疾患の有無を分類するのにCARTが用いられる。顧客分析では、購買履歴や属性に基づき顧客セグメンテーションや離脱予測を行う。解釈可能性が高いため、ドメイン専門家によるルール評価が容易である。

5.2 アンサンブル学習への発展（ランダムフォレスト、勾配ブースティング）

CARTの高分散問題を克服するため、複数の決定木を組み合わせるアンサンブル手法が発展した。ランダムフォレストはバギングと特徴部分サンプリングを用いて木の多様性を高め、勾配ブースティングは逐次的に残差を学習する。これらの手法は予測精度を大幅に向上させ、一般的な機械学習アルゴリズムとなった。

5.3 CARTと他の決定木（ID3, C4.5）との差異

CARTは二分木のみ生成する点、分割基準にジニ係数と二乗誤差を用いる点、剪定にコスト複雑性剪定を用いる点がID3やC4.5と異なる。ID3とC4.5は多分岐木を構成し、エントロピーと情報ゲイン比を使用する。また、C4.5は離散値と連続値の両方を扱えるが、CARTは連続値も離散値も二分岐で処理する。実装上、CARTは回帰問題にも対応できるという利点がある。