# 機器學習 04：決策樹
###### tags: `ML model`, `Tree`

**sklearn 使用 CART 算法，它只會產生二元樹，也就是非葉節點一定有兩個子節點**

---

決策樹只需要非常少量的資料來訓練，且不需要特徵尺度的縮放或置中，但它對資料集的旋轉很敏感。舉例來說，把資料往右轉 45 度，就無法良好得預測：


另一個問題是決策樹對於資料小變動很敏感，原預測為：


移除最寬的 iris versicolor 會得到以下決策邊界：

由於 sklearn 會在各節點隨機選擇特徵組評估，所以就算用同一個特徵組，也會得到差異極大的模型（除非設定 random_state）。

## 決策分類樹


其中 samples 代表該節點適用於多少訓練實例；節點的 value 代表該節點適用於各個類別的多少訓練實例；最後節點的 gini 屬性代表它的不純度，如果一個節點適用的所有訓練實例都屬於同一個類別，不純度 gini = 0。

$$gini = 1- \sum\limits_{k=1}^n {P_{i,\space k }}^2$$

- 左節點 $gini = 0$
- 中間節點 $gini = 1 - (0/54)^2 - (49/54)^2 - (5/54)^2 = 0.168$
- 右節點 $gini = 1 - (0/46)^2 - (1/46)^2 - (45/46)^2 = 0.043$

**CART 演算法會貪婪的不斷重複拆開子集合直到最深度，不考慮後果而肓目得生長，此時同常會產生還過得去但不保證最好的解。而尋找最佳樹是 NP-Complete 問題，需要 $O(e^m)$的時間。**

CART 演算法最小化的目標 Loss 有兩種：

1. **Gini**

<font size=5>$$Loss = \frac {m_{left}}{m}G_{left} + \frac {m_{right}}{m}G_{right}$$</font>

其中 $G$ 是子集合的不純度，$m$ 是子集合的實際數量。

2. **熵**

<font size=5>$$Loss = -\sum\limits_{k = 1}^n p_{i,\space k}\log_2(p_{i,\space k})$$</font>

其中 $p$ 為機率。
---


**其中 Gini 傾向將最常見的類別獨立再它自己的分支（B）；熵傾向產生稍微平衡的樹（A）。**

---
以 sklearn 實現：

from sklearn.tree import DecisionTreeClassifier

iris = load_iris()
X = iris.data[:, 2:] # petal length and width
y = iris.target

tree_clf = DecisionTreeClassifier(max_depth=2, random_state=42)
tree_clf.fit(X, y)

有幾種超參數可以調整過擬合：
1. min_samples_split：一個節點至少要有多少樣本才能被拆開
2. min_samples_leaf：一個葉節點必須至少有多少樣本
3. min_weight_fraction_leaf：與 min_samples_leaf 類似，但用加權比率
4. max_leaf_nodes：葉節點最大數量
5. max_features：再拆開各節點時評估的特徵最大數量
...

---

## 決策回歸樹


預測葉節點的 value = 0.111 代表 110 個訓練實例的平均目標值，均方誤差 MSE = 0.015。


每個區域內的預測值一定是該區域的平均目標值，這個演算法是藉著讓大部分的訓練實例盡量靠近預測值來劃分各區域。

CART 回歸是用 MSE 作為 loss function：

<font size=5>$$Loss = \frac {m_{left}}{m}MSE_{left} + \frac {m_{right}}{m}MSE_{right}$$</font>

但如同分類任務，決策樹在不用任何政則化處理回歸任務時很容易過擬合：


---

以 sklearn 實現：

from sklearn.tree import DecisionTreeRegressor

tree_reg = DecisionTreeRegressor(max_depth=2, random_state=42)
tree_reg.fit(X, y)

---
## reference

1. 精通機器學習，使用 Scikit-Learn, Keras 與 Tensorflow－Aurelien Greon
2. [Why are implementations of decision tree algorithms usually binary and what are the advantages of the different impurity metrics?](https://sebastianraschka.com/faq/docs/decision-tree-binary.html)