【理解してる方向け】決定木・CARTアルゴリズム簡易まとめ | LI techno  

【理解してる方向け】決定木・CARTアルゴリズム簡易まとめ

決定木の基本設定

定義・名前

根ノード:最も上にあるノード
中間ノード:図の丸のノード
葉ノード:図の四角のノード
親ノード:分岐するノード
子ノード:分岐した後のノード

n個のデータを\((\bf{x_1},y_1), (\bf{x_2},y_2), \cdots, (\bf{x_n},y_n)\)
Mクラスが存在するとして\(C=\{c_1, c_2,\cdots, c_M\}\)として\(y_i\in C\)のようにクラスが与えられているとする。
また各ノードには番号が割り当てられていて、根ノードの番号を1とする。さらにノード番号rに割り当てられている学習データ番号の集合を\(I_r\)と定義する。例えば\(I_1=\{1,2,\cdots, n\}\)というように根ノードには全データが与えられている。
最後に\(I_r\)の中でクラスが\(y_i\in C\)である学習データの割合を\(P(y|I_r)=\frac{| \{i \in I_r|y_i=y\} |}{|I_r|}\)と定義する。

必要な関数

不純度(Impurity) \(I(I_r)\)

あるノードrの不純度を意味する関数
例)ジニ関数:\(I(I_r)=1-\sum_{y \in C}P(y|I_r)^2\)
エントロピー:\(I(I_r)=-\sum_{y \in C}P(y|I_r)\log_{2}P(y|I_r)\)
誤分類率:\(I(I_r)=1-\max_{y \in C}P(y|I_r)\)

分割指数

j番目の特徴量と閾値\(\theta _j\)の選択基準に関して、不純度の減少量を意味する関数
\(I_r\)の中で\(x_j < \theta _j\)を満たすデータの割合を\(P_L(I_r, j,\theta _j))\)、満たさないデータの割合を\(P_R(I_r, j,\theta _j))\)と定義する。そのとき分割指数\(G(I_r, j, \theta j)\)は
\(G(I_r, j, \theta j)=I(I_r)-P_L(I_r, j, \theta _j)I(\{I \in I_r|x_{ij} < \theta _j\})\\-P_R(I_r, j, \theta _j)I(\{I \in I_r|x_{ij} \geq \theta _j\})\)

分割指数が大きいほど分割によって分割指数は大きく減少するので、分割指数Gが最大となるjと\(\theta _j\)を選択すればいい。
具体的には以下の3式を計算する。

\( \theta _j ^* = argmax_{\theta _j}G(I_r, j, \theta _j) \tag{1}\)
\(j_r = argmax_{j}G(I_r, j, \theta _j ^*) \tag{2}\)
\(G_r = G(I_r, j_r, \theta _{j_r}) \tag{3}\)

この式は、ノードrではj番目の特徴量で閾値\(\theta _j\)を選択するということ

分類CARTアルゴリズム

STEP.1
初期値を設定
根ノードの番号を1とし、初期値として葉ノードの集合\(N_{Leaf}\)を\(N_{Leaf}=\{1\}\)、分類木の総ノード数NをN=1とする。根ノードの学習データ番号の集合を\(I_1=\{1,2,\cdots, n\}\)とする。またr=1として式(1), (2), (3)を計算して\(F_1 = G_1\)とする。
STEP.2
分岐するノードを選択する
分岐するノードrを\(r=argmax_{s \in N_{Leaf}}F_s\)として選ぶ。選んだノードrを親ノードとして次のような子ノード\(r_L=N+1, r_R=N+2\)を作成する。

\( I_{r_L} = \{ i \in I_r|x_{ij_r} < \theta _{j_r} ^*\}, I_{r_L} = \{ i \in I_r|x_{ij_r} \geq \theta _{j_r} ^*\}\)

またN:=N+2と更新して、さらに\(N_{Leaf}\)を次式のように更新する。

\(N_{Leaf} := N_{Leaf} \cup \{r_L, r_R\}\setminus{r}\)

この式の意味は新たに生成した子ノードを葉ノードの集合\(N_{Leaf}\)に追加、親ノードを\(N_{Leaf}\)から除外するということ。

STEP.3
子ノードの分岐選択基準(F_r)を計算する
\(r:=r_L\)として式(1), (2), (3)を計算して\(F_{rL}=G_{rL}\frac{|I_{rL}|}{|I_1|}\)とする。同様に\(r:=r_R\)として式(1), (2), (3)を計算して\(F_{rR}=G_{rR}\frac{|I_{rR}|}{|I_1|}\)とする。
STEP.4
停止条件に達するまで繰り返し、最終的に結果を出力
全ての葉ノードに対して中の学習データがある値\(S_{min}\)より小さくなれば学習をストップして、最終的な出力結果であるデータ予測クラス\(\hat{y_r} \in \{c_1, c_2,\cdots, c_M\}\)を次の式\( \hat{y_r}=argmax_{y \in C}P(y|I_r)\)として得る。
全ての葉ノードに対して中の学習データがある値\(S_{min}\)より大きければ学習を継続し、Step2-3を繰り返す。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です