はじめに
回帰とニューラルネットワークについては、イメージがつくが、決定木については、中々イメージが付かないので、整理してみた。
決定木とは
- 決定木とは、ある簡単な基準に基づいてデータの分割を繰り返し、木のような構造を作り出すアルゴリズム。
- 分類・回帰問題の両方に適用可能。
- 「CART」と「C4.5(C5.0)」と呼ばれる2つの代表的なアルゴリズムが存在する。
不純度
基準となる特徴量やしきい値はどう決めるのか?
(分割前の不純度) - (分割後の不純度)
が最大になるように、分割の基準を決定する。つまり、(分割後の不純度)が最小になるような分割を行う。
「不純度」とは、簡単にいうと、どれだけいろいろなクラスの観測値が混じり合っているかを表す指標。
分類問題の場合は、1つのノードに1つのクラスの観測値のみがあるのが理想(不純度=0)。
数式で考えると
Nm個の観測値を持つ領域Rｍにおけるクラスｋの観測値の割合を次のように書く。
$$\hat{P}mk =1/N_m\sum_{x_i\in R_i}I(y_i = k)$$
不純度を表す関数
- ジニ指数（微分可能）
$$1 -\sum_{k=1}^K\hat{P}_mk^2$$
- 交差エントロピー（微分可能）
$$- \sum_{k+1}^K\hat{P}mk\log\hat{P}_mk$$
irisデータセットの場合（ジニ指数）
左:
gini = 0.168,
samples = 54,
value [0, 49, 5],
class = versicolor
右:
gini = 0.043,
samples = 46,
value = [0, 1, 45],
class = virgica
左
$$1- \Biggl(\frac{0}{54}\Biggr)^2
- \Biggl(\frac{49}{54}\Biggr)^2
- \Biggl(\frac{49}{54}\Biggr)^2
\approx 0.168
$$
右
$$1- \Biggl(\frac{0}{46}\Biggr)^2
- \Biggl(\frac{1}{46}\Biggr)^2
- \Biggl(\frac{45}{46}\Biggr)^2
\approx 0.043
$$
よって、全体の不純度は、
$$\frac{54}{100}\times0.168 + \frac{46}{100}\times0.043 \approx 0.111$$
決定木のメリットとデメリット
メリット
- 理解が容易である(ホワイトボックス)。
- 分類・回帰のいずれにも適用できる。
- あらゆる問題に広く適用できる。
デメリット
- 分散が大きい(外れ値の影響を受けやすい)。
- 過学習しやすい(ノンパラメトリックモデル)。
- 予測面が滑らかではない。
過学習を防止するためには、
- パラメータの調整が大切。
- 木の深さの上限(max-depth)や、1つのノードが最低持たなければならない観測値の数
(min_samples_leaf)などを
適切に設定する。
回帰問題への適用
回帰問題の場合、コスト関数を以下のように定義する。
$$\hat{c}mk =1/N_m\sum_{x_i\in R_i}y_i$$
$$Q_m(T) =1/N_m\sum_{x_i\in R_i}(y_i - \hat{c}_m)^2$$
$\hat{c}_m$はその領域に含まれる観測値の平均を表している。よって、このコスト関数は平均2乗誤差である。2つに分割したそれぞれの領域の平均2乗誤差の重み付き和が最小になるように分割を行う。
最後に
決定木は、勾配ブースティングに使われる学習器。また、分類だけでなく、回帰にも使えるて万能。理論は理解したので、実装方法を身につけたい。