集合に対して再帰的に境界を入れていく操作が決定木の作成。
では、集合のどこに境界を入れれば良いか。
属性をテストすることにより得られる情報量が最も大きくなるように入れる。
汎化能力、みたいな言葉を読んでいくにあたってこの先、結構抽象的な話になるので一度確認。
データが\(n\)個のクラスに分類できるとして、クラス\(i\)に属する確率を\(P_i\)とする。
このとき、あるデータがクラス\(i\)に属することを知るには\(\log_2 \frac{1}{P_i}\)の情報量が必要。
その期待値は\(I(P_1,P_2,\cdots,P_n)=\sum_{i=1}^{n} P_i \log_2 \frac{1}{P_i} = – \sum_{n}^{i=1} P_i \log_2 P_i\)。
情報量の平均をエントロピーとか。
\(D_p\)個のデータを\(D_{left}\)、\(D_{right}\)に分割するとする。
その時、属性\(f\)に関する問いを使って分割する。
2分木の左ノード、右ノードだからleft,right。
\(I(D_p)\)は分割前のエントロピー。
\(I(D_{left})\)、\(I(D_{right})\)は分割後のエントロピー。
分割前には\(I(D_p)\)ビット必要だったのが、
分割後には\(\frac{N_{left}}{N_p} I(D_{left}) + \frac{N_{right}}{N_p} I(D_{right})\)ビット必要になった。と読むらしい。
その差を情報ゲイン\(IG(D_p)\)と呼んで以下のように定義するらしい。
\begin{eqnarray}
IG(D_p,f) = I(D_P) – \frac{N_{left}}{N_p} I(D_{left}) – \frac{N_{right}}{N_p} I(D_{right})
\end{eqnarray}
分割前よりも分割後の方が\(IG(D_p,f)\)だけエントロピーが低い、という事実に関して、
分割に使った問いにより、\(IG(D_p,f)\)の情報量を獲得した、と考えるらしい。
情報ゲインが最大になるような問いを根にもってきて、
再帰的に情報ゲインが大きいものから順に問うことで決定木を作っていく。