この記事の読者

機械学習・マシンラーニングの手法の１つである「決定木 / Decision Tree」について知りたい.

キーワード・知ってると理解がしやすい

決定木概要
ノード分割規則
ホールドアウト法
交差確認法
決定木 / Decision Tree #まとめ編
- yhayato1320.hatenablog.com

Index

Index
決定木アルゴリズム / Decision Tree
木の剪定アルゴリズム
参考

決定木アルゴリズム / Decision Tree

#01 では、決定木の「概要」、「定義と数式化」、「クラスの割り当て」などを #02 では、「ノード分割規則」を記した.

#アルゴリズム編 #02
- yhayato1320.hatenablog.com

#03 では、「木の剪定アルゴリズム」について記す.

木の剪定アルゴリズム

木を構成した学習データに対する再代入誤り率を 誤り率と木の複雑さから定義し、 許容範囲まで木を剪定するアルゴリズムを考える.

葉ノードにおける誤り率

まずは、葉ノードにおける誤り率.

葉ノードにおける誤り率葉ノード $t \in \tilde{T}$ における誤り数 $M(t)$ は、葉ノードに属する学習データのうち、事後確率を最大にしないクラスの学習データ数である. このノードの誤り率は、

$R(t)\ =\ \displaystyle \frac{M(t)}{N},\ \ (t \in \tilde{T}) \tag{1}$

である.

(ここでは誤り率を用いて説明するが、ジニ係数等でもよい)

ノード $t$ における誤率は

$1 - \max_{i} P(C_i | t)$

と定義しており、つまりここでいう、

$\displaystyle \frac{M(t)}{N(t)}$

となりそうだが、ノード単体で見たときは、前者のように解釈することもできるが、木全体で見たときは後者のように、分母(全事象)を全データ件数とすることで、木全体の誤り率について議論を進めていく.

$N$ は総学習データ数である. 木全体での再代入誤り率の推定値は、

木全体における再代入誤り率

$R(T)\ =\ \displaystyle \sum_{t \in \tilde{T}} R(t)$

となる.

木の複雑さ

木の複雑さを葉ノードの数で評価することにする.

木 $T$ のノード数を $|T|$ で表現すれば、葉ノード数は $|\tilde{T}|$ と表現できる.

複雑さを加味した葉ノードにおけるコスト一つの葉ノードがあることによる複雑さのコストを $\alpha$ で以下のように表せば、
一つの葉ノードにおける誤り率と複雑さのコストの和になる.

$R_{\alpha}\ =\ R(t) + \alpha$

(コスト) = (誤り率) + (複雑さ)

木全体では以下のようになる.

複雑さを加味した木全体におけるコスト

$\begin{align} R_{\alpha} (T)\ &=\ \displaystyle \sum_{t \in \tilde{T}} R_{\alpha} (t) \\ &=\ \displaystyle \sum_{t \in \tilde{T}} (R(t) + \alpha) \\ &=\ \displaystyle \sum_{t \in \tilde{T}} R(t)\ +\ \displaystyle \sum_{t \in \tilde{T}} \alpha \\ &=\ R(T)\ +\ \alpha | \tilde{T} | \end{align}$

目的は木のコスト $R_{\alpha} (T)$ を最小にすることであるが、葉ノード数 $|\tilde{T}|$ が大きくなれば誤り率 $R(T)$ は減少し、逆に葉ノードの数が減れば誤り率は大きくなる.

係数 $\alpha$ は、これら二つの要素の間のバランスをとる正則化パラメータの役割を果たしている.

$\alpha$ を小さく設定すれば大きな木が好まれ、大きく設定すれば小さな木が好まれる.

任意のノード $t$ における再代入誤り率は、識別クラスが最大事後確率で決まるので、

$\begin{align} r(t)\ &=\ 1 - \max_{i} P(C_i | t) \\ &=\ \displaystyle \frac{M(t)}{N(t)} \end{align}$

である.

上で記した葉ノードにおける誤り率式 (1) で定義した $R(t)$ は、式 (1) で定義したノード $t$ に学習データが属する $p(t)\ =\ \displaystyle \frac{N(t)}{N}$ を用いれば、

$\begin{align} R(t)\ &=\ r(t)\ p(t) \\ \\ \left( \displaystyle \frac{M(t)}{N}\ \right. &=\ \left. \displaystyle \frac{M(t)}{N(t)}\ \displaystyle \frac{N(t)}{N} \right) \end{align}$

と書くことができる.

これは、ノード $t$ が葉ノードであれば、全体の誤りに対する $t$ の寄与と考えられる.

任意のノード $t$ を根ノードとする分枝 ( $t$ のすべえての子孫からなる部分木) を $T_t$ で表す.

もし、 $R_{\alpha} (T_t)\ \lt \ R_{\alpha} (t)$ であれば、 $t$ を葉ノードと考えたときの誤りと複雑さのコストより、 $t$ の分枝がもつコストの方が小さいので、 $T_t$ をそのままにしておりた方が全体のコストは小さくなる.

しかし、正則化パラメータ $\alpha$ を次第に大きくしていけば両者は等しくなり、そのときの $\alpha$ は、

$\begin{array}{cccc} & R_{\alpha} (T_t)\ &=&\ R_{\alpha} (t) &のとき \\ & & \\ & & \\ & R_{\alpha} (T_t)\ &=&\ R(T_{t}) + \alpha |\tilde{T_t}| \\ & R_{\alpha} (t)\ &=&\ R(t) + \alpha &より \\ & & & \\ & & & \\ & R_{\alpha} (T_t)\ &=&\ R_{\alpha} (t) \\ \Leftrightarrow\ &R(T_t) + \alpha |\tilde{T_t}|\ &=&\ R(t) + \alpha \\ \\ \Leftrightarrow\ &\alpha (|\tilde{T_t}| - 1)\ &=&\ R(t) - R(T_t)\\ \\ \Leftrightarrow\ &\alpha\ &=&\ \displaystyle \frac{R(t) - R(T_t)}{|\tilde{T_t}| - 1} \end{array}$

で与えられる.

リンクの強さ

すなわち、ノード $t$ を葉ノードにしてもコストは変わらないので、 $T_t$ を選定してしまってよいことになる.

リンクの強さそこで、 $\alpha$ を $t$ の関数とみなして、

$g (t)\ =\ \displaystyle \frac{R(t) - R(T_t)}{|\tilde{T_t}| - 1}$

と定義する.

これをノード $t$ のリンクの強さに関する尺度と考える.

木の剪定は、すべての非終端ノードの集合 $T-\tilde{T}$ について $g(t)$ を計算し、

$g_1 (t_1)\ =\ \displaystyle \min_{t \in (T-\tilde{T})} g(t)$

とする. ( $t_1$ はリンクの強さが最小になるノード)

木の剪定アルゴリズム

最小値をとるすべてのノードを終端ノードとし、、その子孫を削除して木を剪定する.

剪定された木に対して同じ手続きを繰り返し、根ノードのみになるまで剪定する.

木の剪定アルゴリズム

$T^{0} = T,\ \alpha_{0}\ =\ 0,\ k\ =\ 0$ とする. (初期化)

$g_k (t^k)\ =\ \displaystyle \min_{t \in (T^k-\tilde{T}^k)} g(t)$ を計算する (リンクの強さ計算)

$\alpha_{k+1} = g_{k} (t^{k})$ (リンクの強さ更新)

最小値をとるノードの集合を $\tilde{T}^{k}\ =\ \{ t_{1}^{k},\ \cdots,\ t_{m_{k}}^{k} \}$ とする.

$i=1,\ \cdots,\ m_k$ について以下を繰り返す. (木の剪定)

$left(t_i^k)$ を根とする分枝を $T^k$ から削除する
$rightt(t_i^k)$ を根とする分枝を $T^k$ から削除する

$k\ =\ k+1$ とする (インデックスの更新)

剪定された木を $T^{k}$ とする. (木の更新)

$|T^{k}| = 1$ であれば終了. そうでなければ (2) に戻る. (終了 or 繰り返し)

例

2つのクラスをデータを分類する過程を考える.

[手順1] 分割規則を適応した決定木がこちら

[手順2] 非終端ノードのリンクの強さを計算する

[手順4] 最小のノード集合を確定

[手順5] 剪定

[手順2] 再度、非終端ノードのリンクの強さを計算する

[手順4] 最小のノード集合を確定

[手順5] 剪定

[手順2] 再度、非終端ノードのリンクの強さを計算する

[手順4] 最小のノード集合を確定

[手順5] 剪定

剪定した履歴がこちら

各剪定段階における再代入誤り率が下表のようになったとしよう.

|k|0|1|2|3| | :---: |:---:|:---:| :---: | :---: | | $\alpha_k$ |0.0|0.0067|0.013|0.146| | $| \tilde{T}^{k} |$ |5|4|3|1| | $R(T^{k})$ |3/150|4/150|6/150|60/150|