はじめに
決定木は、ノードを2つ以上のサブノードに最適に分割するためのさまざまなアルゴリズムを使用します。これらのサブノードの形成により、同質性が向上します。基本的に、これは、対象変数に対するノードの純度が増加することを意味します。決定木は、分割するための全ての可能な変数を調べ、もっとも同質性の高いサブノードを生成する変数を選択します。
この記事では、ID3、C4.5、CART、CHAID、およびMARSの5つの主要な決定木アルゴリズムを紹介します。
ID3アルゴリズム
Iterative Dichotomiser 3 (ID3) アルゴリズムは、もっとも古く、もっともよく知られた決定木アルゴリズムの1つです。カテゴリカルな特徴量を持つ分類タスクに主に使用されます。ID3アルゴリズムは、Information Gain基準に基づいてデータセットを分割するための最適な属性を選択することによって動作します。Information Gain(IG)は、次のように計算されます。
ここで、
C4.5アルゴリズム
C4.5はID3アルゴリズムの拡張版です。C4.5は、連続的な属性や欠損値の扱いなど、ID3の制限に対処するために開発されました。C4.5アルゴリズムは、Information Gainの変更版であるGain Ratio基準を使用して最適な属性を選択します。Gain Ratio(GR)は次のように定義されます。
ここで、
CARTアルゴリズム
Classification and Regression Trees(CART)は、別の人気のある決定木アルゴリズムで、分類および回帰タスクの両方を処理できます。ID3やC4.5とは異なり、CARTは各内部ノードが正確に2つの子ノードを持つバイナリツリーを生成します。CARTアルゴリズムは、分類タスクにはGini不純度基準、回帰タスクには平均二乗誤差(MSE)を使用して、最適な属性を選択します。Gini不純度(GI)は次のように計算されます。
回帰タスクでは、MSEは次のように定義されます。
ここで、
CHAIDアルゴリズム
Chi-squared Automatic Interaction Detector (CHAID) アルゴリズムは、決定木アルゴリズムで、独立性のChi-squaredテストに依存して最適な属性を選択します。CHAIDは、カテゴリカル変数間の相互作用を探索するのに特に有用で、各内部ノードが2つ以上の子ノードを持つマルチウェイツリーを作成できます。アルゴリズムは、残りの属性に基づく代替の分割ルールである代替分割を介して欠損データを処理できます。
Chi-squared統計量は次のように計算されます。
ここで、
MARSアルゴリズム
Multivariate Adaptive Regression Splines (MARS) は、決定木ベースのアルゴリズムです。MARSは、主に回帰タスクに使用され、高次元でノイズの多いデータを処理するように設計されています。データに基づいて基底関数と呼ばれる分段線形回帰関数を適合させることでモデルを構築します。MARSは、前向き選択、後ろ向き削除、ノット選択などの技術を組み合わせて、解釈可能で柔軟かつ正確なモデルを作成します。MARSは従来の決定木アルゴリズムではありませんが、複雑な関係をモデル化するためのアプローチや構造にいくつかの類似点があります。
MARSモデルは次のように表されます。
ここで、
ここで、
ここで、