# Decision Tree (CART Algorithm)

## Reference
https://towardsdatascience.com/decision-tree-from-scratch-in-python-46e99dfea775

## Decision Tree
[Ttianic データ](https://www.kaggle.com/c/titanic/data)の決定木(Decision Tree)例。

上記のように決定木は、ある特徴量とその閾値のセットでデータを分岐する構造を持っている。

## Node
大きく分けると、終端node（Leaf Nodeと呼んだりするが）とそれ以外のnodeに分かれる。
終端node はクラスの**確率密度分布**を持つ（回帰の場合は値の平均値）。
それ以外のnode は 分岐に使う**特徴量**と**閾値**を持つ。

## Prediction
例えば、次の特徴量を持ったAの場合、この決定木に従うと生存(Survived)確率は ==25%==(Node 5) となる。

| Name | Sex | Age | Class |
| -------- | -------- | -------- | -------- |
| A | Male | Child | 3rd |

## Decision Tree Algorithm
今回は **[CART](https://en.wikipedia.org/wiki/Predictive_analytics#Classification_and_regression_trees_.28CART.29)** (Classification and Regression Trees)を扱うが他にも色々ある。
https://scikit-learn.org/stable/modules/tree.html#tree-algorithms-id3-c4-5-c5-0-and-cart

CARTの特徴は以下
* ２つに分岐する（同時に３つ以上は分岐しない）
* ジニ係数（後述）が最小化するように分割する（エントロピーなどを用いることもある）

## Training

### How to split ??

例えば、「Age」という特徴量で閾値を「20」にした時に、絵のようにデータを分けれたとする。
このとき、この分け方が**良いか悪いかを評価**する必要がある。

その評価値として使われるものに、ジニ係数$G$と呼ばれる指標がある。
クラスの数を$k$として、次のように表す。
$$
G=\sum_k{p_k(1-p_k)}=1-\sum_k{p_k^2}
$$

#### Calculatie Gini coefficient
それぞれのnode のジニ係数を計算する
$$
G_P=1-\left(\frac{5}{9}\right)^2-\left(\frac{4}{9}\right)^2=\frac{40}{81} \\
G_L=1-\left(\frac{1}{4}\right)^2-\left(\frac{3}{4}\right)^2=\frac{6}{16} \\
G_R=1-\left(\frac{4}{5}\right)^2-\left(\frac{1}{5}\right)^2=\frac{8}{25}
$$

#### Evaluate good split or bad split
これら３つの $G_P$ と $G_L$,$G_R$ を比較して、分割の良い悪いを決める。
Weighted Average を使って、分割前後のジニ係数を比較する。
$$
split\ before: G_P=0.493... \\
split\ after: \frac{4}{9} G_L + \frac{5}{9}G_R=\frac{1}{6}+\frac{8}{45}=\frac{93}{270}=0.344...
$$
この場合、$split\ before > split\ after$ となるので、「Age」という特徴量で「20」の閾値を使った分割は、**分割する方が良い**という評価になる。

そして、この$split\ after$が**一番低くなる値を網羅的に探索**し、木の分割を繰り返す