数学、ときどき統計、ところによりIT

理論と実践の狭間で漂流する数学趣味人の記録

決定木(2)

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

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

 \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\}

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

  1.  \lambda=0 とし  T_{\lambda}:=\{\emptyset,\mathcal{X}\} とおく。
  2.  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*}
  3. 決定木  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)\}.
  4.  \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) は不要と判断します。

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

  1.  \lambda=0 とし  T_{\lambda}:=T とおく。
  2. 非終端ノード全体  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).
  3.  t\in g_{\lambda}^{-1}(\alpha_{\lambda}) に対して  L(t),  R(t) を根ノードとする  T_{\lambda} の分枝を削除して得られる決定木を  T_{\lambda+1} とする。
  4.  T_{\lambda+1}\neq\{\mathcal{X}\} ならば  \lambda \lambda+1 に置き換えて上記(2)から(3)を繰り返す。

これにより剪定された決定木の列

\displaystyle T=T_{0}\succeq T_{1}\succeq\ldots\succeq\{\mathcal{X}\}

が得られます。これら決定木による予測をテストデータを使って行い、最も良い精度を出したものを仮説として採用します。

*1:正確には写像  L T^{\prime} への制限ですが、煩雑さを避けるため、これも同じ記号  L で表すことにします。

*2:前回の命題 3 の証明と同様にして示すことが出来ます。