データマイニング分野のトップ 10 の古典的なアルゴリズムの 1 つ - CART アルゴリズム (コード付き)

導入

CART は C4.5 に似ており、決定木アルゴリズムの一種です。さらに、一般的な決定木アルゴリズムである ID3 があります。3 つの違いは、特徴の分割にあります。

• ID3: 情報ゲインに基づく特徴分割
• C4.5: 情報利得比に基づく特徴分割
• CART: ジニ係数に基づく特徴分割

基本的な考え方

CART では、決定木がバイナリ ツリーであり、内部ノード機能の値が「はい」と「いいえ」であり、左のブランチが「はい」の値を持つブランチ、右のブランチが「いいえ」の値を持つブランチであると想定しています。このような決定木は、各特徴を再帰的に 2 つに分割し、入力空間、つまり特徴空間を有限数のユニットに分割し、これらのユニット上の予測確率分布、つまり、与えられた入力条件下での出力の条件付き確率分布を決定することと同等です。

CART アルゴリズムは次の 2 つのステップで構成されます。

• 決定木の生成: トレーニング データ セットに基づいて決定木を生成します。生成される決定木はできるだけ大きくする必要があります。
• 決定木の剪定: 検証データセットを使用して、生成されたツリーを剪定し、最適なサブツリーを選択します。このとき、最小損失関数が剪定基準として使用されます。

CART 決定木の生成は、バイナリ決定木を再帰的に構築するプロセスです。 CART 決定木は分類と回帰の両方に使用できます。この記事では、分類のための CART についてのみ説明します。分類ツリーの場合、CART はジニ係数最小化基準を使用して特徴選択を実行し、バイナリ ツリーを生成します。 CART 生成アルゴリズムは次のとおりです。

• 入力: トレーニングデータセットD、計算停止条件:
• 出力: CART 決定ツリー。

トレーニング データ セットに従って、ルート ノードから開始して、各ノードに対して次の操作を再帰的に実行し、バイナリ決定木を構築します。

ノードのトレーニングデータセットが D であると仮定し、データセットの既存の特徴のジニ係数を計算します。このとき、各特徴 A について、各可能な値 a について、サンプル ポイントが A=a を「はい」とテストするか「いいえ」とテストするかに応じて、D を D1 と D2 の 2 つの部分に分割し、A=a の場合のジニ係数を計算します。

すべての可能な特徴 A とすべての可能な分割点 a の中で、ジニ係数が最小の特徴とそれに対応する分割点が最適な特徴と最適な分割点として選択されます。最適な特徴と最適な分割ポイントに基づいて、現在のノードから 2 つの子ノードが生成され、特徴に基づいてトレーニング データ セットが 2 つの子ノードに配布されます。

停止条件が満たされるまで、2 つの子ノードに対して手順 1 ～ 2 を再帰的に呼び出します。

CART 決定ツリーを生成します。

アルゴリズムが計算を停止する条件は、ノード内のサンプル数が所定のしきい値未満であるか、サンプル セットのジニ係数が所定のしきい値未満であるか (サンプルは基本的に同じカテゴリに属している)、またはそれ以上の特徴がないこととなります。

コード

コードはgithub（sklearn呼び出し）に実装されており、ここにも投稿されています。

テストデータセットはMNISTデータセットであり、取得アドレスはtrain.csvである。

運用結果