### Random Forest
# part1 決定木モデル

## このシリーズについて
### 目標
- Random Forestについて学ぶ

### シリーズ構成
1. 決定木モデル 理論
2. 決定木モデル 実装
3. Random Forest 理論
4. Random Forest 実装

### モチベーション
- NNの他にどのような機械学習アルゴリズムがあるのかを学びたい
- アルゴリズムの特徴を知ることで、適材適所を考える事ができる

### 決定木モデルのメリット
- アルゴリズムがシンプルなため理解しやすい
- 結果のモデルを図で示すことが容易
- データに対して寛容
- スケールに依存しないため標準化などの必要がない
- 例 1m~10m のデータに対して 1mm~1km のデータであろうと、情報量で分けるだけなので、同じモデルで決定木を作ることが可能
- 特徴量が２値でも連続値でも対応できる

## 決定木モデル
樹形図を描いて、分類を行うためのルールを作る



> 出典 wikipedia https://ja.wikipedia.org/wiki/%E6%B1%BA%E5%AE%9A%E6%9C%A8

### 決定木が使われていそうなサービス
[アキネイター](http://jp.akinator.com/): 質問に答えると該当するキャラクターを当ててくれる

### 目的変数
最終的に求めたい変数

### 説明変数
目的変数を導出するために用いるパラメータ

### 評価尺度
- ジニ係数
- エントロピー
- カイ二乗統計量
など

#### ジニ係数
- 0から1の値をとる
- 0は値の純粋さを意味し、これ以上分割できない状態
- 分類前のデータは1に近い状態にある
- ジニ係数を1から0へと近づけていくように分類していくことが、決定木における分類の考え方

#### エントロピー
- 物理学的なエントロピーとは関係ない。情報の量を測るための概念。
- こちらも不純度は0が最も小さく、1が最も大きい

### 情報利得
$$
IG({ D }_{ p },\quad f)={ I }_{ G }({ D }_{ p })-\frac { { N }_{ left } }{ { N }_{ p } } { I }_{ G }({ D }_{ left })-\frac { { N }_{ right } }{ { N }_{ p } } { I }_{ G }({ D }_{ right })
$$
左辺の値が最も大きくなる説明変数から順に使って枝を伸ばして決定木を出力する

### 決定木の複雑さの制御
決定木を複雑に分けすぎると複雑になり過剰適合してしまう場合がある、
それを防ぐためには大きく分けて次の2つの方法がある。
- 事前枝刈り
- 完全に終わる前に終了条件を決めてしまう
- 木の深さを制限する
- 葉の最大値を制限する
- 葉の中に含まれるデータの最小数を決める
- 事後枝刈り
- 一度構築が終わった後に情報の少ないノードを削除していく

### 参考文献
決定木分析
http://www5.atpages.jp/kera/up/log/20.pdf
決定木アルゴリズム-Pythonと機械学習
http://darden.hatenablog.com/entry/2016/12/09/221630