CART - 分類木 - 機械学習基礎理論独習

要件

$n$ 組の学習データ $({\bf x}_1,y_1),\ldots,({\bf x}_n,y_n)$ が与えられているとします。
$i$ 番目の学習データの特徴ベクトルは ${\bf x}_i=(x_{i1},\ldots,x_{id})^\top$ と表されます。
$M$ クラス存在すると想定し、 $\mathcal{C}=\{c_1,\ldots,c_M\}$ とします。このとき $y_i\in\mathcal{C}$ です。
この学習データを使った分類木の学習アルゴリズムの一種CARTを以下で説明します。

不純度

各ノードに番号を割り当てます。
根ノードの番号を $1$ とします。
ノード番号 $r$ のノードに割り当てられる学習データ番号の集合を $\mathcal{I}_r$ と定義します。
$\mathcal{I}_r$ の中でクラスが $y\in\mathcal{C}$ であるデータの割合を $P(y|\mathcal{I}_r)$ と定義すると、以下の式で表せます。

$\begin{eqnarray} P(y|\mathcal{I}_r)=\frac{|\{i\in\mathcal{I}_r|y_i=y\}|}{|\mathcal{I}_r|}\tag{1} \end{eqnarray}$

$\mathcal{I}_r$ の学習データにおける不純度を $I(\mathcal{I}_r)$ で表すことにします。
$I(\mathcal{I}_r)$ はエントロピー

$\begin{eqnarray} I(\mathcal{I}_r)=-\sum_{y\in\mathcal{C}}P(y|\mathcal{I}_r)\log_2P(y|\mathcal{I}_r)\tag{2} \end{eqnarray}$

やGini関数

$\begin{eqnarray} I(\mathcal{I}_r)=1-\sum_{y\in\mathcal{C}}P(y|\mathcal{I}_r)^2\tag{3} \end{eqnarray}$

などが利用されます。
CART アルゴリズムではGini関数が用いられることが多いようです。

$M=2$ の時のエントロピーとGini関数のグラフを以下に示します。

f:id:olj611:20210513020817p:plain:w500

$c_1,c_2$ が均等に存在する $P(y=c_1|\mathcal{I}_r)=0.5$ のとき最大値をとり、
$c_1$ のみが存在する $P(y=c_1|\mathcal{I}_r)=1$ または $c_2$ のみが存在する $P(y=c_1|\mathcal{I}_r)=0$ のとき最小値を取ることが分かります。

$M\geq 3$ のときは、すべての $y$ に対して、 $P(y|\mathcal{I}_r)=1/M$ の最大になります。

ノードの分岐

番号 $r$ のノードに対して、属性番号 $j$ と閾値 $\theta_j$ の選択基準について考えます。

$\mathcal{I}_r$ の中で $x_j < \theta_j$ を満たすデータの割合を $P_L(\mathcal{I}_r,j,\theta_j)$ とすると、以下の式で表せます。

$\begin{eqnarray} P_L(\mathcal{I}_r,j,\theta_j)=\frac{|\{i\in\mathcal{I}_r|x_{ij} < \theta_j\}|}{|\mathcal{I}_r|}\tag{4} \end{eqnarray}$

$x_j < \theta_j$ を満たさないデータの割合を $P_R(\mathcal{I}_r,j,\theta_j)=1-P_L(\mathcal{I}_r,j,\theta_j)$ とします。

このとき、分割指数 $G(\mathcal{I}_r,j,\theta_j)$ を平均的な不純度の減少として、次式で定義します。

$\begin{eqnarray} G(\mathcal{I}_r,j,\theta_j)=I(\mathcal{I}_r)-P_L(\mathcal{I}_r,j,\theta_j)I(\{i\in\mathcal{I}_r|x_{ij} < \theta_j\})-P_R(\mathcal{I}_r,j,\theta_j)I(\{i\in\mathcal{I}_r|x_{ij} \geq \theta_j\})\tag{5} \end{eqnarray}$

この分割指数が大きいほど、分割することによって不純度が大きく減少します。

不純度がエントロピーの場合の分割指数 $G$ は相互情報量または情報利得と呼ばれます。
また、不純度がGini関数の場合、Gini係数またはGiniインデックスと呼ばれます。

ここで、番号 $r$ のノードに対して

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} &&\theta_j^*=\argmax_{\theta_j}G(\mathcal{I}_r,j,\theta_j)\tag{6}\\ &&j_r=\argmax_{j}G(\mathcal{I}_r,j,\theta_j^*)\tag{7}\\ &&G_r=G(\mathcal{I}_r,j_r,\theta_{j_r}^*)\tag{8} \end{eqnarray}$

とします。
番号 $r$ のノードでは、属性番号 $j_r$ で閾値 $\theta_{j_r}^*$ を選べばよいことが分かります。

分岐させるノードの選択基準について考えます。

$(5)$ は $1$ データあたりの不純度の減少量を表しているので、
ノード $r$ に割り当てられた学習データの割合を $G_r$ に乗じることによって、ノード $r$ の分岐選択基準

$\begin{eqnarray} F_r=G_r\frac{|\mathcal{I}_r|}{|\mathcal{I}_1|}\tag{9} \end{eqnarray}$

を得ます。

※ $(9)$ の分母 $|\mathcal{I}_1|$ は不要に見えますが、分岐選択基準にある閾値を設ける場合に必要なのだと思います。

CART アルゴリズム

$\mathcal{N}_{Leaf}$ を葉ノードの集合とし、初期値は根ノードだけからなる木とします。
また、分類木の総ノード数を $N$ とします。

1: 根ノードの番号を $1$ とし、初期値として $\mathcal{N}_{Leaf}=\{1\},N=1$ とする。
根ノードの学習データ番号の集合を $\mathcal{I}_1=\{1,\ldots,n$ と設定する。
また、 $r=1$ として、式 $(6),(7),(8)$ を計算し、 $F_1=G_1$ とする。

2: ノード $r$ を

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} r = \argmax_{s\in\mathcal{N}_{Leaf}}F_s\tag{10} \end{eqnarray}$

として選び、ノード $r$ に対して以下のようなデータ集合を持つ $r$ の子ノード $r_L=N+1,r_R=N+2$ を作成する。

$\begin{eqnarray} &&\mathcal{I}_{r_L}=\{i\in\mathcal{I}_r|x_{ij}<\theta_{jr}^*\}\tag{11}\\ &&\mathcal{I}_{r_R}=\{i\in\mathcal{I}_r|x_{ij}\geq\theta_{jr}^*\}\tag{12}\\ \end{eqnarray}$

$N:=N+2$ と更新する。また次式で $\mathcal{N}_{Leaf}$ を更新する。

$\begin{eqnarray} \mathcal{N}_{Leaf}:=\mathcal{N}_{Leaf}\cup\{r_L,r_R\}\backslash\{r\}\tag{13} \end{eqnarray}$

3: $r:=r_L$ として、式 $(6),(7),(8)$ を計算し、 $F_{r_L}=G_{r_L}|\mathcal{I}_{r_L}|/|\mathcal{I}_1|$ とする。
同様に $r:=r_R$ として、式 $(6),(7),(8)$ を計算し、 $F_{r_R}=G_{r_R}|\mathcal{I}_{r_R}|/|\mathcal{I}_1|$ とする。