分類回帰木/CART
CART は、入力確率変数 X が与えられた場合に、出力確率変数 Y の条件付き確率分布を学習する方法です。
意味
CART は、デシジョン ツリーがバイナリ ツリーであり、内部ノードの特徴が「はい」と「いいえ」の値を持ち、左の分岐が値「はい」の分岐、右の分岐が値が「はい」の分岐であると想定します。値は「いいえ」です。このような決定木は、各特徴を再帰的に二等分し、入力空間、つまり特徴空間を限られた数のユニットに分割し、これらのユニット上の予測確率分布、つまり出力の条件付き確率を決定することに相当します。与えられた入力条件下で。
CART アルゴリズムは次の 2 つのステップで構成されます。
- ツリーの生成: トレーニング データ セットに基づいてデシジョン ツリーを生成します。生成されるデシジョン ツリーはできるだけ大きくなければなりません。
- ツリー枝刈り: 検証データセットを使用して、生成されたツリーを枝刈りし、最適なサブツリーを選択します。このとき、最小損失関数が枝刈り基準として使用されます。
決定木の生成は、二分決定木を再帰的に構築するプロセスです。回帰ツリーには二乗誤差最小化基準が使用され、分類ツリーにはジニ指数最小化基準が使用され、二分木が生成されます。
回帰木の生成
X と Y がそれぞれ入力ベクトルと出力ベクトルであり、トレーニング データセット 回帰木を生成する方法を考えます。
回帰木は、入力空間 (特徴空間) とその分割単位上の出力値の分割に対応します。入力空間が M ユニット $latex R_{1}、R_{2}、\ldots、R_{M}$ に分割されており、各ユニットに固定出力値 $latex c_{ があると仮定します。 $latex R_{m} $ mしたがって、回帰木モデルは $latex f(x)=\sum_{m=1}^{M} として表すことができます。 c_{m} I\left(x \in R_{m}\right) $
入力空間の分割が決まると、二乗誤差 $latex \sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right) ^ を使用できます {2}$
トレーニング データの回帰木の予測誤差を表すために、各ユニットの最適な出力値が最小二乗誤差の基準を使用して解決されます。ユニット $latex R_{m} $ の $latex c_{m} $ の最適値は、すべての入力インスタンス $latex x_{i} の $latex R_{m} $、出力 $latex y_ {i} の $ であることが簡単にわかります。 $の平均値は
問題は、入力空間をどのように分割するかです。ここでは、ヒューリスティックな方法を使用して、 j 変数 $latex x^{(j)}$ とその値 s をセグメンテーション変数およびセグメンテーション ポイントとして使用し、次の 2 つの領域を定義します。
次に、最適な分割変数を見つけます。 j 最適な分割ポイント s 。具体的な、解決する
固定入力変数の場合 j 最適な分割ポイントを見つけることができます s
すべての入力変数を調べて、最適な分割変数を見つけます j 、ペア $latex (j, s) $ を形成し、入力空間を 2 つの領域に順番に分割します。そして、停止条件が満たされるまで、領域ごとに上記の分割処理が繰り返される。
分類木の生成
分類ツリーは、Gini インデックスを使用して最適な特徴を選択し、特徴の最適なバイナリ セグメンテーション ポイントを決定します。
ジニ指数
分類プロセス中、K 個のクラスがあり、サンプル点が k 番目のクラスに属する確率は $latex p_{k} $ であると仮定すると、確率分布のジニ指数は次のように定義されます。
2 クラス分類問題の場合、サンプル点が最初のクラスに属する確率が p の場合、確率分布のジニ指数は次のようになります。
特定のサンプルセット D のジニ指数は次のとおりです。
このうち、 $latex C_{k} $ は D の k 番目のクラスに属するサンプル部分集合であり、K はクラスの数です。
特徴 A が特定の可能な値 a を取るかどうかに基づいて、サンプル セット D が $latex D_{1}$ と $latex D_{2}$ の 2 つの部分に分割される場合、つまり次のようになります。
次に、特徴 A の条件の下で、セット D のジニ指数は次のように定義されます。
ジニ指数 $latex {Gini}(D) $ は集合 D の不確実性を表し、ジニ指数 $latex {Gini}(D, A) $ は集合 D を A=a で割った後の不確実性を表します。ジニ指数が大きいほど、エントロピーに似たサンプル セットの不確実性が大きくなります。
生成アルゴリズム
入力: 学習データセット D、計算を停止する条件
出力: CART デシジョン ツリー
トレーニング データ セットに従って、ルート ノードから開始して各ノードに対して次の操作を再帰的に実行して、二分決定木を構築します。
- ノードのトレーニング データ セットを D とし、このデータ セットの既存の特徴のジニ係数を計算します。このとき、特徴量 A ごとに、取り得る値 a ごとに、サンプル点 A=a の検定が「はい」か「いいえ」かに応じて、D を $latex D_{1} $ と $latex D_{2} $ に分割します。 " 2 つの部分、A=a の場合のジニ指数を計算します
- すべての可能な特徴 A とその可能なすべてのセグメンテーション ポイント a の中で、最小のジニ インデックスを持つ特徴とそれに対応するセグメンテーション ポイントを最適な特徴と最適なセグメンテーション ポイントとして選択し、最適な特徴と最適なセグメンテーション ポイントに基づいて、次から 2 つの子ノードを生成します。現在のノードにトレーニング データ セットを割り当て、特性に応じて 2 つの子ノードにトレーニング データ セットを割り当てます。
- 停止条件が満たされるまで、2 つの子ノードで (1) と (2) を再帰的に呼び出します。
- CART デシジョン ツリーを生成する