1 基本概念
決定木（Decision Tree）は、機械学習やデータマイニングにおいて広く用いられる教師あり学習の一種であり、特徴量の条件分岐を木構造で表現することで、分類や回帰の予測モデルを構築する手法である。各内部ノードは特徴量に対するテスト、各枝はテストの結果、各葉ノードはクラスラベルまたは数値予測を表す。解釈のしやすさと可視化の容易さから、医療診断、金融リスク評価、マーケティング分析など様々な分野で応用されている。
1.1 木構造の構成要素
1.1.1 ルートノード
ルートノードは決定木の最上位に位置するノードであり、最初の分割を行う特徴量とその閾値を決定する。すべてのデータはルートノードから木の探索を開始する。ルートノードの選択は学習アルゴリズムの分割基準に基づいて行われ、モデルの性能に大きな影響を与える。
1.1.2 内部ノード
内部ノードはルートノードと葉ノードの間に位置するノードであり、特定の特徴量に対するテスト条件を保持する。データは内部ノードの条件に従って子ノードへと分岐し、木の深さが進むにつれてデータの分割が繰り返される。
1.1.3 葉ノード
葉ノードは決定木の末端に位置するノードであり、それ以上分割は行われない。葉ノードには予測結果が格納される。分類問題では最も多数のクラスラベル、回帰問題では目的変数の平均値などが割り当てられる。
1.2 決定ルールの抽出
決定木からは、ルートノードから葉ノードに至る経路を論理積の条件として読み取ることで、解釈可能な決定ルールを抽出できる。例えば「年齢 > 30 かつ 収入 > 500万」の場合に「ローン承認」といった形のルールが得られ、人間が理解しやすい知識表現となる。
2 学習アルゴリズム
決定木の学習は、訓練データを再帰的に分割しながら木を成長させる過程で行われる。分割のたびに、最適な特徴量とその分割点を選択するための基準が必要となる。また、過学習を防ぐために剪定（Pruning）が行われる。
2.1 分割基準
2.1.1 情報利得（ID3アルゴリズム）
情報利得は、分割前後のエントロピーの減少分として定義される。エントロピーはデータの不純度を測る指標であり、情報利得が最大となる特徴量が選択される。ID3アルゴリズムはこの基準を用いるが、多数の値を持つ特徴量を優先する傾向がある。
2.1.2 利得比（C4.5アルゴリズム）
利得比は情報利得を分割情報量（Split Information）で正規化した指標である。分割情報量は特徴量の取りうる値の数に応じて増加するため、利得比を用いることで多くの値を取る特徴量への過度な偏りを補正する。C4.5アルゴリズムで採用されている。
2.1.3 ジニ不純度（CARTアルゴリズム）
ジニ不純度は、ランダムに選んだ2つのサンプルが異なるクラスに属する確率を表す指標である。値が小さいほど純粋なノードとみなされる。CART（Classification and Regression Tree）アルゴリズムではこのジニ不純度を分割基準として用いる。二値分割が基本となる。
2.2 剪定（Pruning）
剪定は、学習後の決定木の複雑さを削減し、過学習を抑制するための手法である。主に事前剪定と事後剪定の2種類に分類される。
2.2.1 事前剪定
事前剪定は、木の成長中にあらかじめ停止条件を設定する方法である。例えば、ノードの最小サンプル数や木の最大深さを制限することで、それ以上の分割を禁止する。計算コストが低いが、適切な停止条件の選択が難しい。
2.2.2 事後剪定
事後剪定は、まず完全に成長させた木を構築した後、不要な枝を削除する方法である。コスト複雑度剪定（Cost-Complexity Pruning）などが代表的であり、検証データを用いて剪定後の誤差を評価しながら最適な部分木を選択する。事前剪定より精度が高い場合が多い。
3 代表的なアルゴリズム
3.1 ID3
ID3（Iterative Dichotomiser 3）は、情報利得を分割基準として用いる古典的な決定木アルゴリズムである。カテゴリカル特徴量のみを扱い、多値分割を行う。離散値データに適しているが、連続値の扱いやノイズへの耐性に課題がある。
3.2 C4.5
C4.5はID3の改良版であり、利得比を用いることで多値特徴への偏りを緩和した。連続値特徴量への対応（閾値による二値分割）、欠損値処理、事後剪定の機能を持つ。実用的な応用が広く、後のアルゴリズムに大きな影響を与えた。
3.3 CART
CART（Classification and Regression Tree）は、二値分割のみを行う汎用的な決定木アルゴリズムである。分類問題ではジニ不純度、回帰問題では平均二乗誤差を分割基準として用いる。コスト複雑度剪定を標準装備しており、アンサンブル学習の基盤としても頻繁に利用される。
3.3.1 分類木
CARTの分類木は、目的変数がカテゴリカルである場合に用いられる。各ノードでの分割候補は、ジニ不純度を最小化する特徴量と閾値の組み合わせとして探索される。葉ノードには最頻クラスが割り当てられる。
3.3.2 回帰木
CARTの回帰木は、目的変数が連続値である場合に用いられる。分割基準には平均二乗誤差（MSE）や平均絶対誤差（MAE）が使われ、葉ノードにはその領域内の目的変数の平均値が予測値として設定される。
4 長所と短所
4.1 長所
4.1.1 解釈性の高さ
決定木は人間が直感的に理解できる木構造を出力するため、モデルの予測根拠を説明しやすい。視覚化も容易であり、ビジネスや医療などの分野で意思決定支援に適している。
4.1.2 非線形関係のモデリング
決定木は非線形な決定境界を自然に表現できる。特徴量間の交互作用も自動的に捉えることができ、前処理としてのスケーリングが不要である点も利点である。
4.2 短所
4.2.1 過学習のリスク
決定木は訓練データに対して過度に適合しやすい性質を持つ。特に深い木はノイズまで学習してしまい、汎化性能が低下する。剪定やハイパーパラメータの調整が必須となる。
4.2.2 不安定性
決定木はデータのわずかな変化によって木の構造が大きく変わりうる。これは分割基準が貪欲（グリーディ）な選択に依存するためであり、アンサンブル学習によってこの不安定性を軽減することが一般的である。
5 応用と関連手法
5.1 アンサンブル学習との統合
決定木は単体でも強力だが、複数の木を組み合わせるアンサンブル学習によって性能を大幅に向上できる。
5.1.1 ランダムフォレスト
ランダムフォレストは、複数の決定木をバギング（Bootstrap Aggregating）と特徴量のランダムサブセット選択を用いて構築し、それらの予測を多数決または平均によって統合する手法である。過学習に強く、高い汎化性能を持つ。
5.1.2 勾配ブースティング木（GBT）
勾配ブースティング木（Gradient Boosting Tree, GBT）は、前の木の誤差を次の木で修正する逐次学習を行うアンサンブル手法である。XGBoost、LightGBM、CatBoostなどの実装が広く使われ、多くの機械学習コンペティションで高い性能を示している。
5.2 実世界での利用例
5.2.1 医療診断支援
決定木は患者の症状や検査結果から疾患を予測する診断支援システムに利用される。例えば、発熱や咳などの条件からインフルエンザの可能性を判定するルールを抽出でき、医師の判断を補助する。
5.2.2 クレジットスコアリング
金融機関では、申請者の年収、職業、過去の返済履歴などの特徴量から、ローンやクレジットカードの与信判断を行う際に決定木が活用される。透明性が求められる規制環境下でも、決定ルールを説明しやすい点が評価される。
6 関連項目
- 機械学習
- 教師あり学習
- アンサンブル学習
- ランダムフォレスト
- 勾配ブースティング
- 過学習
- エントロピー
- ジニ係数
7 参考文献
1. Quinlan, J. R. (1986). Induction of decision trees. *Machine Learning*, 1(1), 81–106. 2. Quinlan, J. R. (1993). *C4.5: Programs for Machine Learning*. Morgan Kaufmann. 3. Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). *Classification and Regression Trees*. CRC Press. 4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). *The Elements of Statistical Learning* (2nd ed.). Springer. 5. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). *An Introduction to Statistical Learning*. Springer.