# Aggregation Map

到目前為止所學會的方法：

| aggregation type | blending | learning |
|:----------------:|:----------------:|:-------------:|
| uniform | voting/averaging | Bagging |
| non-uniform | linear | AdaBoost |
| conditional | stacking | Decision Tree |

- [blending](https://hackmd.io/@ShawnNTU-CS/BywPOgyan)
- 把已有的 $g_{t}$ 拿來打果汁
- [Bagging](https://hackmd.io/@ShawnNTU-CS/BywPOgyan#Bootstrap-Aggregation--Bootstrap-Aggregation)
- 透過 Bootstraping 來抽出多種不同的資料集
- 以此訓練出多樣的 $g_{t}$
- [AdaBoost](https://hackmd.io/@ShawnNTU-CS/SJvNkG16h)
- 透過修改 Error Measure 改變不同資料的重要性
- 這樣每次就可以學到跟上次不一樣的 $g_{t}$

---

# 路徑表示法 Path view

$$
G(\mathbf{x})=\sum_{t=1}^{T}q_{t}(\mathbf{x})\cdot g_{t}(\mathbf{x})
$$

- $G(\mathbf{x})$ 就是我們的決策樹
- $q_{t}$ 是我們的判斷式。在路徑表示法中代表某個 $\mathbf{x}$ 是否在某條路上，而整棵樹有 T 條路
- 通常來說都是很簡單的判斷式
- $g_{t}$ 是樹的葉子，代表最終決策的地方，其實就是之前的 $g_{t}$。
- 通常為一個常數，像是對或錯，但是也可以使用 Regression 或其他方式做簡單的決定

這樣表示法的複雜地方主要是在「路徑上」。

# 遞迴表示法 Recursive View

$$
G(\mathbf{x})=\sum_{c=1}^{C}[[b(\mathbf{x})=c]]\cdot G_{c}(\mathbf{x})
$$

- $G(\mathbf{x})$ 就是我們的決策樹
- $b(\mathbf{x})$ 分枝的判斷，看要分到哪條子樹上，總共有 C 個子樹
- $G_{c}(\mathbf{x})$ 子樹的部分

比較常使用的表示方法。

---

## 決策樹好處

- 可解釋性高
- 簡單，並且在訓練和預測上都很有效率

## 決策樹缺點

- 理論保證通常很少，主要著重在如何設計出好的決策樹
- 是好是壞有很多不同的討論，不一定有很強的理論做支持
- 有時候不只一個「這樣設計可能好」，而是很多種「這樣設計可能好」疊加在一起
- 所以容易讓初學者對於各種巧思跟其相關參數感到困惑
- 也因此並沒有所謂比較代表的決策樹模型
- 有時可能是該時段因為某種原因比較流行某種模型，不一定代表某個模型比較好或不好

---

# 基本演算法

延續上面遞迴的型式：

第一次決策樹函式傳入資料 $\mathcal{D}$。函數內會判斷：

- 如果到了中止條件，回傳 $g_{t}(\mathbf{x})$
- 否則：
- 學會分枝條件 $b(\mathbf{x})$
- 將 $\mathcal{D}$ 依照有幾種 $b(\mathbf{x})$ 分成 C 份
- 將 C 份資料各自再帶入決策樹函式學會子樹 $G_{c}(\mathbf{x})$
- 回傳 $G(\mathbf{x})=\sum_{c=1}^{C}[[b(\mathbf{x})=c]]\cdot G_{c}(\mathbf{x})$

# C&RT

- C 等於 2，永遠都切兩刀
- 也就是說會是一棵二元樹
- $g_{t}(\mathbf{x})$ 是最佳的常數
- 如果是分類問題就是回傳比較多次的 $y_{n}$
- 如果是 Regression 就是回傳 $y_{n}$ 的平均值

:::info
CART 演算法是 California Statistical Software 這個公司註冊的商標。這裡的 C&RT 是老師選取其精華部分。
:::

## Branching in C&RT：Purifying

C&RT 使用 decision stump 去做切兩半的動作。

而每次希望切的兩半，可以「很純」；或者說兩半「加權的不純度」要最低：

$$
b(\mathbf{x})=\underset{\text{decision stump }h(\mathbf{x})}{argmin} \sum_{c=1}^{2}|\mathcal{D}_{c}\ with\ h|\cdot impurity(\mathcal{D}_{c}\ with\ h)
$$

- 希望找到一個 $h$
- 他所切的兩半 $\mathcal{D}_{1}$、$\mathcal{D}_{2}$ 的不純度
- 乘上資料量 $|\mathcal{D}_{c}\ with\ h|$ 作為加權
- 加起來要最低

# Impurity function

回傳一個常數的話，評估不純度會方便很多；所以不純函數就是來算 $E_{in}$。

## For regression

$$
\frac{1}{N}\sum_{n=1}^{N}(y_{n}-\bar{y})^{2}
$$

熟悉的最小平方。

## For Classification

$$
1-\max_{1\le k \le K}\frac{1}{N}\sum_{n=1}^{N}[[y_{n}\ne k]]
$$

也就是只看當前最多的種類到底多不多。

:::warning
這種就是之前 decision stump 做分類時的方法
:::

但是缺點是只看一種而已，把全部種類都納入考量會比較好，所以有了第二種：

### Gini Index / 基尼不純度指標

$$
1-\sum_{k=1}^{K}\left(\frac{\sum_{n=1}^{N}[[y_{n}=k]]}{N}\right)^{2}
$$

將每種的比例的平方加起來得到純度，再用 1 去減得到不純度。

這個叫 「**Gini Index**」，是分類問題最常用的不純度方法。

在維基百科中，原始定義是「**樣本被選中的概率乘以它被分錯的概率**」：

$$
\sum_{i=1}^{K}p_{i}\sum_{k\ne i}^{K}p_{k}=\sum_{i=1}^{K}p_{i}(1-p_{i})
$$

繼續推導就可以得到上面的式子了。

:::warning
可以發現 decision stump 在這裡是用來「切兩半」，跟之前用來「分兩邊」不太一樣。
如果是 For regression，那麼似乎就沒有 S 這個代表方向的參數了，並且也不用對 x 進行排序。
:::

## 停下來 / Fully-grown Tree

- 如果切到兩邊加起來不純度是 0，也就是說切到最純了，那就可以停了
- 此時所有算出的 $y_{n}$ 跟資料的都一樣
- 可以回傳當前的 $h$ 作為 $g_{t}(\mathbf{x})$
- 或者正要下刀的時候，發現所有 $x_{n}$ 都一樣，找不到下刀處
- 此時所有的 $x_{n}$ 都一樣
- 就可以直接回傳常數回去

全都停下來後，我們就得到一顆 **Fully-grown Tree**。

:::info
C&RT 的特色 1：
- 容易處裡 binary class、Regression、multi class 問題
:::

# Overfitting

由於資料會越切越小份，越小份的資料訓練時就容易發生 Overfit，所以需要 Regularizer。

$$
\underset{\text{all possible G}}{argmin}E_{in}(G)+\lambda\Omega(G)
$$

$\Omega(G)$ 是葉子的數量。所謂全部的 G ，就是把各種葉子修剪掉，所得到的各種可能「**修剪過的樹 pruned tree**」。

也就是在葉子數量跟錯誤率之間取一個平衡。

## 修枝 Pruning

所謂的修剪，其實就是把兩片葉子合在一起。

但是全部的可能性太多了，所以改成：

- 先從各個葉子中，摘掉一片葉子；看看各種摘掉一片葉子的樹當中誰的 $E_{in}$ 最小，以那顆樹作為 $G^{1}$。
- 接著再以 $G^{1}$ 重複上面摘掉一片葉子的動作，得到 $G^{2}$
- 重複直到你喜歡摘幾片
- 這些 $G^{1}\sim G^{i}$ 構成上面的 all possible G

## $\lambda$

至於要如何挑 $\lambda$，那就是使用老朋友 Validation。

# Categorical features / Decision subset

有時候得到的資料不是數值資料而是類別資料。

例如一個病人的資料可能有一個 Dimension 叫做「主要症狀」，而主要症狀可能有「發燒、疼痛、疲累、盜汗」，這時候就可以使用 Decision subset。

Decision subset 就是看當前的 $x_{n}$ 是否有落在某個 subset 內，例如說 subset 可能是 「發燒 或 盜汗」，那麼該 Decision subset 就是檢查 $x_{n}$ 是否是發燒或是盜汗；最終找到使得 $E_{in}$ 最小的 subset 回傳回去。

:::info
C&RT 的特色 2：
- 容易處裡 Categorical features
:::

# Missing features / surrogate branch

有時候可能資料的某些維度值會不見，這時候就可以使用決策樹的好處，再疊加 Heuristic 上去。

例如說當前正在判斷體重有沒有大於 50，如果沒有體重資料的話，可以拿身高大於 150 公分來做判斷。

拿身高來代理，就是依照所需情況去疊加 Heuristic。

但是要注意，替代方案切下去得到的「方式要是一致的」

:::success
老師沒說方式一致是甚麼意思，但應該是指切出來的兩堆資料差異不可以太大。
:::

:::info
C&RT 的特色 3：
- 容易處裡 Missing features
:::

# 跟 AdaBoost-Stump 比較

由於決策樹每切一刀，都是在「某個條件下」去純化，所以會比每次都找一個維度來切的 AdaBoost-Stump 更有效率。

# 特色統整

- 可解釋性高
- 容易處理 Multiclass
- 容易處理 Categorical
- 容易處理 Missing
- 很高效的處理非線性資料

# C4.5

另一個有名的決策樹。

CART 在純化數的時候是使用 Gini Index (Multi classifiaction)，而 C4.5 則是使用「信息增益 Information Gain」。

## 信息增益

信息熵定義：

$$
H(T)=I_{E}(p_{1},p_{2},...,p_{J})=-\sum_{i=1}^{J}p_{i}log_{2}p_{i}
$$

而信息增益為：

$$
IG(T,a)=\overbrace{H(T)}^{\text{Parents' Entropy}}-\overbrace{H(T|a)}^{\text{Weighted Sum of Children's Entropy}}\\
=-\sum_{i=1}^{J}p_{i}log_{2}p_{i} - \sum_{a}p(a)\sum_{i=1}^{J}-Pr(i|a)log_{2}Pr(i|a)
$$

其中：
- $p_{1},p_{2},...$ 是各個「目標類別 $y_{n}$」的機率，加總會等於 1。
- 也就是輸出的 Class 的機率，跟 Gini Index 的機率一樣意思。
- $p(a)$ 是 $x_{n}$ 以某個維度分類，看該維度有幾種類別，第 a 種的機率就是 $p(a)$
- $Pr(i|a)$ 就是在第 a 種的條件下，「目標類別 $y_{n}$」的機率

最後看哪個維度的信息增益最高，就以該維度作為劃分。

:::warning
建議搭配下面例子服用，會更容易理解。
:::

## 例子 - [摘自維基百科](https://zh.wikipedia.org/zh-tw/%E5%86%B3%E7%AD%96%E6%A0%91%E5%AD%A6%E4%B9%A0#%E4%BF%A1%E6%81%AF%E5%A2%9E%E7%9B%8A)

數據集有 4 個屬性，或者說維度：
- `outlook (sunny, overcast, rainy)`
- `temperature (hot, mild, cool)`
- `humidity (high, normal)`
- `windy (true, false)`

目標值，或者說 $y_{n}$：
- `play（true, false）`

總共 14 個數據點

使用屬性 `windy` 做劃分時，產生 2 個子節點，`windy` 值為 `true` 與為 `false`。當前數據集：
- 6 個數據點的 `windy` 值為 `true`，其中：
- 3 個點的 `play` 值為 `true`
- 3 個點的 `play` 值為 `false`
- 其餘 8 個數據點的 `windy` 為 `false`，其中：
- 6 個點的 `play` 值為 `true`
- 2 個點的 `play` 值為 `false`。

`windy = true` 的子節點的信息熵計算為：

$$
p(\text{play is true}|\text{windy is true})=\frac{3}{6}\\
p(\text{play is false}|\text{windy is true})=\frac{3}{6}\\
I_{E}([3,3])=-\frac{3}{6}log_{2}\frac{3}{6}+-\frac{3}{6}log_{2}\frac{3}{6}=1
$$

`windy = false` 的子節點的信息熵計算為：

$$
p(\text{play is true}|\text{windy is false})=\frac{6}{8}\\
p(\text{play is false}|\text{windy is false})=\frac{2}{8}\\
I_{E}([6,2])=-\frac{6}{8}log_{2}\frac{6}{8}+-\frac{2}{8}log_{2}\frac{2}{8}=0.8112781
$$

使用屬性 `windy` 劃分的信息熵是兩個子節點信息熵的加權和：

$$
p(\text{windy is true})=\frac{6}{14}\\
p(\text{windy is false})=\frac{8}{14}\\
I_{E}([3,3],[6,2])=I_{E}(\text{windy or not})=\frac{6}{14}\cdot 1+\frac{8}{14}\cdot 0.8112781=0.8921589
$$

- $p(\text{windy is true})$ 就是 $x_{n}$ 以 windy 這個維度分類，該維度有 2 種類別，為 true 的機率，也就是上面提到的 $p(a)$
- $p(\text{play is true}|\text{windy is false})$ 就是在 $\text{windy is false}$ 的條件下，「目標類別 $\text{play is true}$」的機率，也就是上面提到的 $Pr(i|a)$

最後計算最初未劃分的數據集的信息熵，數據集的 `play` 有 9 個 `true` 與 5 個 `false`：

$$
H(T)=I_{E}([9,5])=-\frac{9}{14}log_{2}\frac{9}{14}+-\frac{5}{14}log_{2}\frac{5}{14}=0.940286
$$

於是我們可以知道使用屬性 `windy` 的信息增益是：

$$
IG(\text{windy})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.940286-0.8921589=0.0481271
$$