決定木（２） - 数学、ときどき統計、ところによりＩＴ

今回は前回の続きで木の成長と剪定について論じます。

はじめに決定木を成長させる手順について議論します。

$\mathcal{X}_{j}$ ( $j=1$ , $2$ , $\ldots$ , $k$ )が量的データの場合、 $\{a_{ij}\}_{i=1}^{n}\subset\mathcal{X}_{j}$ を昇順に並べて重複削除したものを $\{a_{ij}^{\prime}\}_{i=1}^{n(j)}$ として $\mathcal{X}$ の部分集合 $A_{ij}$ ( $i=1$ , $2$ , $\ldots$ , $n(j)-1$ ) を

$\displaystyle A_{ij}:=\left\{ x=(x_{1},x_{2},\ldots,x_{k})\in\mathcal{X}\,\Big|\,x_{j}\ge\frac{1}{2}(a_{ij}^{\prime}+a_{(i+1)j}^{\prime})\right\} ,$

$\mathcal{X}_{j}$ が質的データの場合、 $\{a_{ij}\}_{i=1}^{n}\subset\mathcal{X}_{j}$ から重複を削除したものを $\{a_{ij}^{\prime}\}_{i=1}^{n(j)}$ として $\mathcal{X}$ の部分集合 $A_{ij}$ ( $i=1$ , $2$ , $\ldots$ , $n(j)$ ) を

$\displaystyle A_{ij}:=\left\{ x=(x_{1},x_{2},\ldots,x_{k})\in\mathcal{X}\,|\,x_{j}=a_{ij}^{\prime}\right\}$

と置きます。このとき以下の手順で決定木を成長させます。

$\lambda=0$ とし $T_{\lambda}:=\{\emptyset,\mathcal{X}\}$ とおく。
$t\in\widetilde{T}_{\lambda}$ に対して $\displaystyle t^{\prime}:=\underset{t\cap A_{ij}}{\mathrm{arg\, max}} \ \varDelta\widehat{R}(T,\phi,s;t\cap A_{ij},t\cap A_{ij}^{c}).$ このとき \begin{equation*} L(t):=\begin{cases} t^{\prime}, & t^{\prime}\not\in\{\emptyset,t\},\\ \emptyset, & t^{\prime}\in\{\emptyset,t\}, \end{cases}\quad R(t):=\begin{cases} t\setminus L(t), & L(t)\neq\emptyset,\\ \emptyset, & L(t)=\emptyset. \end{cases} \end{equation*}
決定木 $T_{\lambda+1}$ を次式で定義する。 $\displaystyle T_{\lambda+1}:=T_{\lambda}\cup\bigcup_{t\in\widetilde{T}_{\lambda};L(t)\not\neq\emptyset}\{L(t),R(t)\}.$
$\lambda$ を $\lambda+1$ に置き換えて上記 2 から 3 を繰り返す。そして最終的に得られた決定木を $T$ とする。

上記手順により集合を分割することで決定木を成長させますが、停止条件が無いので木が成長し過ぎてしまいます。そこで適切なサイズになるように調整します。この問題を扱うに際し、いくつかの言葉を準備をします。

定義　 $r$ を根ノードとする決定木 $T$ の部分集合 $T^{\prime}$ が写像 $L$ *1により決定木の構造を有するとき、 $T^{\prime}$ を $T$ の部分木と呼ぶ。さらに部分木 $T^{\prime}$ の根ノードが $r$ のとき $T^{\prime}$ を剪定された部分木と呼び $T^{\prime}\preccurlyeq T$ と表す。また任意の $t\in T$ に対して $t$ とその子孫からなる部分木を分枝と呼ぶ。

$T(t)$ を $t\in T$ を根ノードとする $T$ の分枝、 $\widetilde{T} (t)$ を $T(t)$ の終端ノード全体、 $T^{\prime}$ を $T$ から $T (t)\setminus\{t\}$ を取り除いた部分集合族とします。このとき $T^{\prime}$ は $T$ の剪定された部分木となっています。 $T^{\prime}$ による予測値と観測値との間のペナルティ項付き残差と $T$ によるそれとの差は

$\displaystyle \widehat{R}_{\alpha}(T^{\prime},\phi,s)-\widehat{R}_{\alpha}(T,\phi,s)=\widehat{R}(T^{\prime},\phi,s)-\widehat{R}(T,\phi,s)-\alpha(\#\widetilde{T}(t)-1)$

となります。 $\phi$ の狭義凸性と

$\displaystyle \widehat{R}(T^{\prime},\phi,s)-\widehat{R}(T,\phi,s)=p(t)\sum_{i\in I(t)}\phi(p(c_{i}|t))-\sum_{t'\in\widetilde{T}(t)}p(t^{\prime})\sum_{i\in I(t^{\prime})}\phi(p(c_{i}|t^{\prime}))$

より $\widehat{R}(T^{\prime},\phi,s)-\widehat{R}(T,\phi,s)\gt 0$ が成り立つ*2ことに注意すると

$\displaystyle \alpha=\frac{\widehat{R}(T^{\prime},\phi,s)-\widehat{R}(T,\phi,s)}{\#\widetilde{T}(t)-1}$

のとき $\widehat{R}_{\alpha}(T^{\prime},\phi,s)=\widehat{R}_{\alpha}(T,\phi,s)$ となります。このとき残差の観点から予測において分枝 $T(t)$ は不要と判断します。

以上の議論を踏まえて剪定の手順をまとめます。

$\lambda=0$ とし $T_{\lambda}:=T$ とおく。
非終端ノード全体 $T_{\lambda}\setminus\widetilde{T}_{\lambda}$ 上で定義された関数 $\displaystyle g_{\lambda}(t):=\frac{\widehat{R}(T^{\prime},\phi,s)-\widehat{R}(T,\phi,s)}{\#\widetilde{T}_{\lambda}(t)-1},\quad t\in T_{\lambda}\setminus\widetilde{T}_{\lambda}$ の最小値を $\alpha_{\lambda}$ とする： $\alpha_{\lambda}=\min_{t\in T_{\lambda}\setminus\widetilde{T}_{\lambda}}g_{\lambda}(t)$ .
$t\in g_{\lambda}^{-1}(\alpha_{\lambda})$ に対して $L(t)$ , $R(t)$ を根ノードとする $T_{\lambda}$ の分枝を削除して得られる決定木を $T_{\lambda+1}$ とする。
$T_{\lambda+1}\neq\{\mathcal{X}\}$ ならば $\lambda$ を $\lambda+1$ に置き換えて上記(2)から(3)を繰り返す。