決定木(2)
今回は前回の続きで木の成長と剪定について論じます。
はじめに決定木を成長させる手順について議論します。
(, , , )が量的データの場合、 を昇順に並べて重複削除したものを として の部分集合(, ,,) を
が質的データの場合、 から重複を削除したものを として の部分集合 (, , ,) を
と置きます。このとき以下の手順で決定木を成長させます。
- とし とおく。
- に対して
このとき \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*} - 決定木 を次式で定義する。
- を に置き換えて上記 2 から 3 を繰り返す。そして最終的に得られた決定木を とする。
上記手順により集合を分割することで決定木を成長させますが、停止条件が無いので木が成長し過ぎてしまいます。そこで適切なサイズになるように調整します。この問題を扱うに際し、いくつかの言葉を準備をします。
定義 を根ノードとする決定木 の部分集合 が写像 *1により決定木の構造を有するとき、 を の部分木と呼ぶ。 さらに部分木 の根ノードが のとき を剪定された部分木と呼び と表す。また任意の に対して とその子孫からなる部分木を分枝と呼ぶ。
を を根ノードとする の分枝、 を の終端ノード全体、 を から を取り除いた部分集合族とします。このとき は の剪定された部分木となっています。 による予測値と観測値との間のペナルティ項付き残差と によるそれとの差は
となります。 の狭義凸性と
より が成り立つ*2ことに注意すると
のとき となります。このとき残差の観点から予測において分枝 は不要と判断します。
以上の議論を踏まえて剪定の手順をまとめます。
- とし とおく。
- 非終端ノード全体 上で定義された関数
の最小値を とする:. - に対して , を根ノードとする の分枝を削除して得られる決定木を とする。
- ならば を に置き換えて上記(2)から(3)を繰り返す。
これにより剪定された決定木の列
が得られます。これら決定木による予測をテストデータを使って行い、最も良い精度を出したものを仮説として採用します。