# Random Forest
Random Forest 是以 Decision tree 為 base layer，再使用 bagging 的方法將各個 Decision tree 結合起來，實現「三個臭皮匠，勝過一個諸葛亮」，後續會在介紹 model 是如何運作的。

## Decision tree
Tree 是一種監督式學習(supervised learning)的模型，從根結點開始，根據 feature 將資料分到不同分之，使各節點中的資料盡量乾淨、並從中獲得最大的訊息增益。
> [!NOTE]
> 監督式學習 : 是將多個模型的預測結果結合(可以是同一種、多個)，形成一個更準確、穩定的最終模型的方法。
<div style="display:flex; gap:20px; justify-content:center;align-items:center;">
<img src="https://hackmd.io/_uploads/BJWb91Wpel.png" style="width:48%; height:auto;">
<img src="https://hackmd.io/_uploads/S1qW9ybagx.png" style="width:48%; height:auto;">
</div>

>決策樹的運作如上圖：在每個節點會先挑一個特徵（feature），再設定一個分割門檻（threshold），用來把資料分成兩群。
## bagging
bagging 為一種 Ensemble learning(集成學習) 的方法。使用 boostrap 抽樣的方式，從資料集隨機抽取樣本(可重複抽取)，獨立訓練多個 分類器/分類器 (各分類器為單獨個體，互不影響)，最後各分類器投票並預測最終的結果。
> [!Note]
> *boostrap* : 一種抽樣的方法，重點在於每次抽樣後，樣本會被放回資料池，使同一筆資料可能被多次抽中。
<div style="display:flex; gap:20px; justify-content:center;align-items:center;">
<img src="https://hackmd.io/_uploads/H1WeiJb6xg.png" width="70%" style="display:inline-block;">
<img src="https://hackmd.io/_uploads/S148oJWpel.png" width="70%" style="display:inline-block;">
</div>

>上圖為 bagging 的流程。
## Random Forest
### Discription :
Random Forest 是一種基於 Bagging 的集成學習方法。它透過對訓練資料進行多次隨機抽樣，建立多棵 Decision Tree 作為基礎分類器，並將各樹的預測結果進行投票或平均，以提升模型的穩定性與泛化能力（generalization ability）。
>上圖為 Random Forest 的整體運作流程。中間紅框區塊為訓練完成的多棵 Decision Tree；當新的資料輸入時，會依據訓練階段學的分類規則進行分類或回歸，並透過投票或平均的方式整合各樹的輸出，產生最終預測結果。
### choose feature :
如上述所說的，Random Forest 會用 boostrap 的方法抽樣，並建立特徵池，接著從這些候選特徵中，挑選出最能有效區分資料的特徵，作為該節點的分裂依據。
>[!Important]如何找到「有效」區分資料的特徵?
> - 分類的任務中有幾種方法可以評估 &rightarrow; 使用 Gini impurity 或 Entropy(由於 Gini impurity為比較常見的方式，主要介紹此種方式)。
> - 回歸任務 → 使用 MSE(均方誤差)。

> - 上圖所寫的 $Gini$ 皆代表 $\Delta Gini$。
> - 用 "數字" 分類代表 : 使用 "數字" 這個特徵進行分類。
> - 下面的 data 為此節點(Node) 「現在」的資料樣式，如 : positive 是從父節點，也就是全部 data 所分類出結果為 positive 的資料。
### 計算 $\Delta Gini$ :
Gini（Gini Impurity，不純度）是一個用來量化「節點裡資料有多混亂」的指標。
在決策樹或隨機森林裡，每次要分裂資料時，我們會計算 分裂前後的 Gini 值，找出「能讓資料變得最乾淨（Gini 降最多）」的特徵和 threshold 來切。
Gini 值的公式如下 :
$${Gini}(t) = 1 - \sum_{k=1}^{K} p_{k}^2$$

>[!Tip]我們先來說明如何實際「選擇特徵與 threshold」，以下圖為此次的 dataset：
**Step 1 計算 $Gini(root)$**
$Gini(𝑟𝑜𝑜𝑡)= 1\ \ –\ \ (0.5^2 + 0.5^2) = 0.5$
> 為什麼為 0.5, 0.5 ?
> 原 dataset 是 3 個 1、3 個 0，故要計算結果為 1 的 $p_{k}$ 就會是
> $\frac{result \ \ 為\ \ 1 \ \ 的數量= 3}{總數 = 6} = 0.5$。同理，結果為 0 的 $p_{k}$ 也是 0.5。
>
>
>**Step 2 計算 Threshold**
$X_1$ 由小到大排序：2, 3, 5, 7, 9, 11
$X_1$ Threshold = {2.5, 4, 6, 8, 10}
>
>**Step 3 計算各 threshold 所得的 $\Delta Gini$**
$Threshold = 2.5 → Gini(split) = 0.4,\ \ \Delta Gini = 0.5 \ \ –\ \ 0.4 = 0.1$
$Threshold = 4 → Gini(split) = 0.25,\ \ ΔGini = 0.25$
$Threshold = 6 → Gini(split) = 0,\ \ ΔGini = 0.5$
$Threshold = 8 → Gini(split) = 0.25,\ \ ΔGini = 0.25$
$Threshold = 10 → Gini(split) = 0.4,\ \ \Delta Gini = 0.1$
>
>**Step 4 重複上述步驟計算$X_2$**
>
>**Step 5 選用來分類的 feature**
$X_1$ $\Delta Gini(Max) = 0.5$ (選擇的 threshold = 0.6 & 此 feature 來做分類)
$X_2$ $\Delta Gini(Max) = 0.2$


>[!Tip] 接下來說明如何計算左右子集的 Gini 以及 ΔGini。:
>假設我們已經決定好 Threshold = **2.5**、使用的 feature : **$X_1$**、原本的 Gini 值為 **0.5**
>在 Left 子集 (以 $X_1$ ≤ 2.5 為篩選條件) &rightarrow; 符合條件的值為 : 2 &rightarrow; dataset 上的 result = [1]
>在 Right 子集 (以 $X_1$ > 2.5 為篩選條件) &rightarrow; 符合條件的值為 : 3, 5, 7, 9, 11 &rightarrow; dataset 上的 result = [1, 1, 0, 0, 0]
>
>*從上述可得 :*
>
>$$Left\ \ Node: gini(left) = 1\ \ –\ \ (1^2 + 0^2) = 0$$
>$$Right \ \ Node : gini(right) = 1 \ \ –\ \ (0.4^2 + 0.6^2) = 0.48$$
>$$Gini(split) = {0 * \frac{1}{6} + 0.48 * \frac{5}{6} = 0.4}$$
>$$\Delta Gini(X_1) = Gini(parent)\ \ - \ \ Gini(split)= 0.5 - 0.4 = 0.1$$

### 在 Python 上如何使用 :
以下使用 `scikit-learn` 套件建立簡單的隨機森林分類器：

from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier


# 1. 分割訓練 / 測試資料
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 2. 建立 Random Forest 模型
rf = RandomForestClassifier(n_estimators=100,max_depth=3,random_state=42)

# 3. 訓練模型
rf.fit(X_train, y_train)

>`test_size` : **資料切分比例**，決定多少資料要拿來當作「測試集」。例如 0.2 代表 20% 為測試集、80% 為訓練集。
>`n_estimators` : **樹的數量**，要訓練多少棵 Decision Tree。
>`max_depth` : **樹的最大深度**，控制每棵樹可以生長的層數，越深代表模型越複雜。