決定木学習は、分類および回帰タスクの両方に使用される機械学習における教師あり学習手法である。このモデルは木構造であり、内部ノードは入力特徴量に対するテストを表し、分岐はそれらのテストの結果を表し、葉ノードは最終的な予測値またはクラスラベルを表す。その目標は、目的変数に関して可能な限り均質な領域に特徴空間を分割し、解釈が容易ないわゆるif-then-elseルールの系列を作成することである。
決定木の構築プロセスは、選択された分割基準に従ってトレーニングデータを最もよく分離する特徴量を再帰的に選択することを含む。一般的な基準には、情報理論からのエントロピーに基づく情報利得と、ランダムに選ばれた要素がサブセット内のラベルの分布に従ってランダムにラベル付けされた場合に誤ってラベル付けされる頻度を測定するジニ不純度が含まれる。木は、すべてのトレーニング例を含むルートノードから開始してトップダウンで成長し、最大深さに達する、葉ごとの最小サンプル数を持つ、またはそれ以上の分割が基準を改善しないなどの停止条件が満たされるまで続けられる。
歴史的発展
決定木の概念は、1963年にMorganとSonquistによるAutomatic Interaction Detection（AID）システムの開発とともに1960年代に遡る。この初期の研究は、異なる分割基準を使用した1970年代のTHAIDアルゴリズムによって続けられた。この分野は、1986年にRoss Quinlanによって情報利得を分割基準として使用したID3アルゴリズムが導入され、1980年代に大きな勢いを得た。Quinlanはその後1993年にC4.5を開発し、これは連続属性、欠損値、および剪定を処理することでID3を改善した。ほぼ同時期に、Classification and Regression Trees（CART）アルゴリズムが1984年にLeo Breiman、Jerome Friedman、Richard Olshen、およびCharles Stoneによって導入された。CARTは分類にジニ不純度、回帰に平均二乗誤差を使用し、最も広く使用される決定木アルゴリズムの1つとなった。
主要なアルゴリズムと変種
長年にわたっていくつかの決定木アルゴリズムが開発されており、それぞれ独自の特性を持つ。ID3とその後継であるC4.5は主に分類に使用され、カテゴリカルおよび連続特徴量の両方を処理できる（C4.5）。CARTは分類木と回帰木の両方をサポートする汎用性の高いアルゴリズムであり、各内部ノードが正確に2つの分岐を持つ二分木を生成する。1980年に導入されたCHAID（カイ二乗自動相互作用検出）アルゴリズムは、最良の分割を決定するためにカイ二乗検定を使用し、多方向分割を生成できる。より最近のアルゴリズムには、回帰用のM5アルゴリズムや、データのランダムサブセット上に多くの決定木を構築し、それらの予測を平均化して過学習を減らすランダムフォレストアンサンブル法が含まれる。
利点と限界
決定木は、学習されたモデルを人間が容易に理解できるフローチャートとして可視化できるため、その解釈可能性から人気がある。それらは、正規化やスケーリングなどのデータ前処理をほとんど必要とせず、数値データとカテゴリデータの両方を処理できる。しかし、決定木は、特に完全な深さまで成長した場合、トレーニングデータ内のノイズを捕捉できるため、過学習を起こしやすい。また、トレーニングデータの小さな変動に敏感であり、わずかな変更がまったく異なる木をもたらす可能性がある。さらに、決定木は多くのレベルを持つ特徴量に対して偏る可能性があり、これらの特徴量はより多くの分割を生成し、より情報価値が高いように見えるためである。これらの問題を軽減するために、剪定、最小葉サイズの設定、ランダムフォレストや勾配ブースティングなどのアンサンブル法などの技術が一般的に採用されている。
応用と現代の文脈
決定木学習は、医療診断、信用リスク評価、顧客離反予測、画像認識など、多くの領域に適用されてきた。現代の人工知能の文脈では、決定木はしばしば勾配ブースティングマシン（GBM）やXGBoostなどのアンサンブル法における基本学習器として使用され、これらは多くの構造化データコンペティションで最先端の結果を達成している。深層学習モデル（ニューラルネットワークなど）が画像や音声認識などの非構造化データタスクを支配している一方で、決定木はその効率性と解釈可能性により、表形式データに対して依然として強力な選択肢である。それらはまた、残差ネットワークアーキテクチャなど、他の技術と組み合わせて使用されるが、これは主として深層学習の概念である。決定木の単純さと頑健性は、学術研究と産業応用の両方におけるその継続的な関連性を保証している。
ソフトウェアと実装
多くのソフトウェアライブラリが決定木アルゴリズムの実装を提供している。Pythonのscikit-learnライブラリは、CARTの最適化バージョンに基づくDecisionTreeClassifierおよびDecisionTreeRegressorクラスを提供する。Rには、再帰分割用のrpartパッケージと、条件付き推論木用のpartyパッケージがある。データマイニングタスク用の機械学習アルゴリズムのコレクションであるWekaには、J48（C4.5のJava実装）とREPTreeの実装が含まれている。これらのツールにより、実務者は決定木モデルを簡単に構築、可視化、評価でき、この手法を幅広いユーザーが利用できるようにしている。