はじめに

決定木は、ノードを2つ以上のサブノードに最適に分割するためのさまざまなアルゴリズムを使用します。これらのサブノードの形成により、同質性が向上します。基本的に、これは、対象変数に対するノードの純度が増加することを意味します。決定木は、分割するための全ての可能な変数を調べ、もっとも同質性の高いサブノードを生成する変数を選択します。

この記事では、ID3、C4.5、CART、CHAID、およびMARSの5つの主要な決定木アルゴリズムを紹介します。

ID3アルゴリズム

Iterative Dichotomiser 3 (ID3) アルゴリズムは、もっとも古く、もっともよく知られた決定木アルゴリズムの1つです。カテゴリカルな特徴量を持つ分類タスクに主に使用されます。ID3アルゴリズムは、Information Gain基準に基づいてデータセットを分割するための最適な属性を選択することによって動作します。Information Gain（IG）は、次のように計算されます。

IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)

ここで、Sはデータセット、Aは属性、S_vは属性値vを持つSのサブセットを表し、Hはエントロピー関数です。

H(S) = - \sum_{c \in Classes} p(c) \log_2 p(c)

C4.5アルゴリズム

C4.5はID3アルゴリズムの拡張版です。C4.5は、連続的な属性や欠損値の扱いなど、ID3の制限に対処するために開発されました。C4.5アルゴリズムは、Information Gainの変更版であるGain Ratio基準を使用して最適な属性を選択します。Gain Ratio（GR）は以下のように定義されます。

GR(S, A) = \frac{IG(S, A)}{IV(S, A)}

ここで、IV(S, A)は属性Aの固有値です。

IV(S, A) = - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}

CARTアルゴリズム

Classification and Regression Trees（CART）は、別の人気のある決定木アルゴリズムで、分類および回帰タスクの両方を処理できます。ID3やC4.5とは異なり、CARTは各内部ノードが正確に2つの子ノードを持つバイナリツリーを生成します。CARTアルゴリズムは、分類タスクにはGini不純度基準、回帰タスクには平均二乗誤差（MSE）を使用して、最適な属性を選択します。Gini不純度（GI）は次のように計算されます。

GI(S) = 1 - \sum_{c \in Classes} p(c)^2

回帰タスクでは、MSEは以下のように定義されます。

MSE(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar{y})^2

ここで、y_iはインスタンスiのターゲット値、\bar{y}はデータセットの平均ターゲット値です。

CHAIDアルゴリズム

Chi-squared Automatic Interaction Detector (CHAID) アルゴリズムは、決定木アルゴリズムで、独立性のChi-squaredテストに依存して最適な属性を選択します。CHAIDは、カテゴリカル変数間の相互作用を探索するのに特に有用で、各内部ノードが2つ以上の子ノードを持つマルチウェイツリーを作成できます。アルゴリズムは、残りの属性に基づく代替の分割ルールである代替分割を介して欠損データを処理できます。

Chi-squared統計量は以下のように計算されます。

\chi^2 = \sum_{i=1}^n \sum_{j=1}^m \frac{(O_{ij} - E_{ij})^2}{E_{ij}}

ここで、O_{ij}は属性とクラスjのカテゴリiのインスタンスの観測された頻度、E_{ij}は独立性の仮定の下での期待頻度、nは属性のカテゴリ数で、mはクラスの数です。CHAIDアルゴリズムは、事前に定義された有意水準を満たす場合に、もっとも高いChi-squared値を持つ属性を選択します。

MARSアルゴリズム

Multivariate Adaptive Regression Splines (MARS) は、決定木ベースのアルゴリズムです。MARSは、主に回帰タスクに使用され、高次元でノイズの多いデータを処理するように設計されています。データに基づいて基底関数と呼ばれる分段線形回帰関数を適合させることでモデルを構築します。MARSは、前向き選択、後ろ向き削除、ノット選択などの技術を組み合わせて、解釈可能で柔軟かつ正確なモデルを作成します。MARSは従来の決定木アルゴリズムではありませんが、複雑な関係をモデル化するためのアプローチや構造にいくつかの類似点があります。

MARSモデルは次のように表されます。

y(x) = \beta_0 + \sum_{i=1}^M \beta_i B_i(x)

ここで、y(x)は入力xに対する予測されるターゲット値であり、\beta_0は定数項、Mはモデル内の基底関数B_i(x)の数、\beta_iはそれに対応する係数です。基底関数は以下のような分段線形関数です。

B_i(x) = \max(0, x - t)またはB_i(x) = \max(0, t - x)

ここで、tはアルゴリズムによって選択されたノットの位置です。MARSは、残差二乗和を最小化するための係数とノットの位置を最適化します。

RSS = \sum_{i=1}^N (y_i - y(x_i))^2

ここで、Nはデータセット内のインスタンスの数であり、y_iとx_iは、それぞれインスタンスiのターゲット値と入力特徴量です。