# 特徵間相關性
## Mutual Information
針對 <font color = 'red'>**離散型特徵 X、Y**</font> 間的相關性分析。

**I(X,Y)** 越大表示兩特徵間 **相關性越強**，何謂「相關性強」
=> 已知一個 attribute，其值對於另一個 attribute 的值可以提供多少資訊，也就是對另一個特徵的值有多大的影響。
ex: I(X,Y) = 0，表示 P(Y = Yk | X = Xk) = P(Y = Yk)，給定 X 值條件與否與 Yk 的機率無關，是 independent。

但有時候值會過大導致比較不準確，所以可以正規化到 [0,1] 間，其中 J、K 分別為 X、Y 兩特徵可能的 value 個數。

## Symmetric Uncertainty

Symmetric uncertainty 同樣是衡量兩離散型特徵間相關性的指標，與 MI 較不同的是其對 MI 做 normalize，因此值會介於 **[0,1]**，而為何需要 SU:
* MI ∈ [0,∞]，沒有固定的最大值，因此在比較上可能較不準確。
* MI 會受到 X、Y 變數 X、Y 變數 **熵** 的大小而波動，縱使 X、Y 間相關性不高，但只要 H(X)、H(Y) 其中一者較大就會使整體 MI 提升。
=> 因此需要標準化 MI

## Goodness
此指標要衡量 **attribute subset S** 對於 **類別值** 的相關性，也就是其預測的能力。


分子部分衡量 attribute subset 內每個變數對於類別值的相關性，而分母則是衡量兩兩特徵間的相關性，其目的也是為了 normalize，兩兩特徵配對需要考慮所有配對可能。

>[!Warning]注意
>分母的意義是假如兩變數間呈現 **強相關** 或 **完全相關**，則放 X 或 X + Y 去預測 class 並不會有顯著的效果提升，兩特徵有 redundant 的壞處，其 **su(X、Y)** 值會越接近 1，會在分母處對整體 Goodness 大小作懲罰。

# Entropy Based 離散化
**supervised discretization** 方法的一種，不用自己決定 intervals 數量，是根據 **Information gain** 的大小進行切割。
1. 先將 attibute value 由小到大排序。
2. 決定切割點，只要任兩樣本的類別值不一樣，其 **中點值** 都當作切割點候選。
3. 每個候選切割點都計算其切割後的 Information gain，選擇增益最大的點作為 cut point，切割成左右區間。
4. 左右區間再重複同樣方法不斷 <font color = 'red'>**遞迴切割**</font>，直到所有區間都找不到切割點為止。

做 Entropy based discretization 會用到以下指標
* **Ent(S)**
**離散化前** 原始 Set 的 entropy 大小，衡量這個 Set 中的類別分布情形，值越大代表不純度越高，類別分布越均勻，否則類別分布越單一化，其中 k 為類別數。
* **Ent(A,S,T)**
Attibute A 中以 T 作為切點切割 Set S 後的 entropy 大小，其綜合了 **左右區間**。

T 點並不存在於任何一個樣本的 Attribute value 中，而是當相鄰兩樣本類別不一樣時，**兩樣本 attribute value 的中間值**。

如何選擇好的 cut point，使用 <font color = 'red'>**Information gain**</font>

* **Information gain**
涵意為使用 cut point T 切割後能 **降低多少 entropy**，因此要 **最小化 Ent(A,S,T)**，當 IG 越大表示此切割點讓其資訊增益越多，切割點越好。

>[!Important]
>Entropy base 離散化方式是不斷做二元切割，目的為找到一個最佳的 cut point，該點分割出的 **兩區間內 class 單一化**，使 entropy 越小越好。

# Decision Tree
## Hunt Algorithm
建構決策樹的演算法之一，步驟為:
* **Step1:**
若節點中的所有 instances 都 **屬於同一個類別**，則將此節點設為 **leaf**，並指派該類別當作此節點的結果。
* **Step2:**
若該節點中有超過兩個以上的類別存在，須選一個 **attribute 做為切割依據**，將節點中所有 instances 切成兩個 subsets，再對這兩個 subsets 重複做 step2。

## Impurity Measure
那在建構 DT 時要如何挑選特徵，就必須要看 **切割前原始節點的類別分布** 與 **切割後兩個子節點的類別分布** 情形，看是否有效地將類別分布更單一化。

**Impurity Measure** 是衡量一個節點 t 裡的類別分布狀況，稱「不純度」，記作 **I(t)**，不純度越高代表節點中類別分布越 uniform，不好。


上述三個都是 Impurity measure 的指標之一，其中 **Pi** 為節點 t 裡 **class value i** 的出現機率，ex: Pi = 0.5。

## Information Gain
計算切割後 **Impurity 可以降低多少**，以此做為選擇特徵的依據，降低越多表示該 Attribute 能將樣本更好地切割。

Information Gain 的公式如下，其中 k 為切割出的 subset 數量，N 為父節點的樣本數，而 Ni 是第 i 個 subset 內涵蓋的樣本數。


我們選 split attribute 的標準就是想 **最大化 IG**，而因為 I(parent) 的值是固定的 (尚未切割前樣本都不動)，因此要最大化 IG 就是要 ==**最小化 I(child)**==，盡量使切割出的區間內類別分布越單一越好。

## Gain Ratio
當一個 test attribute 會分裂出大量節點時，會造成每個 child node 含有的 records 數太少，難以作 prediction，有兩種解法:
* 強制作 **binary split**，如 CART。
* 用 <font color = 'red'>**Gain Ratio**</font> 作為 attribute 選擇的 criterion。

>[!Tip]
>**SplitInfo** 會隨著分支越多其最大值會越大，也就是 Attribute 能分裂的可能越多，Max(SplitInfo) 就越大。
>且當分得越均勻時，SplitInfo 也會越大，如二元分類最大值為 -0.5log(0.5)-0.5log(0.5) = 1，當類別分布呈現均勻時。

SplitInfo 是用來調整 IG 的，避免過度傾向選擇會 <font color = 'red'>**大量分支**</font> 的特徵。
* splitInfo 大: 分支多，**Gain ratio 降低**，避免選此 Att.。
* splitInfo 小: 分支較平衡，較可能選此 Att.。

最後補充: 如何對 **Continous Attribute** 作 cut point 挑選 ?

* **Step1:**
以 Attribute value 的值對所有 records 做 **sort**。
* **Step2:**
可考慮的分割點為兩個相鄰節點 **類別值不一樣** 的情況下，兩相鄰樣本的 midpoint，上圖有兩個切割點，分別為 80、97.5。
* **Step3:**
計算每個可能切割點的 Impurity。
* **Step4:**
選 Impurity 最小的切割點做 split。

# Model Overfitting
**Model Seleciton** 是希望在眾多模型 (同一個 algorithm) 中選擇一個 **Generalized error 最低** 的模型，因此我們需要有方法來估計 Generalized error。

最簡單是以 **Training error** 直接估計 generalized error，雖然此方法很直觀，但太過粗暴與無法在每個情況都準確，因此衍生出以下方法，同樣是**基於 training error 來估計 generalize error**，並考慮 <font color = 'red'>**模型複雜度**</font>。

## Pessimistic error estimate
「悲觀誤差估計」，補償 model 在訓練資料太樂觀的情況，不只單純以 **training error 估計泛化誤差**，同時考慮的模型複雜度。


舉例比較下列兩棵樹的 generalize error estimate


<font color = 'red'>**Pessimistic error estimate = training error + model complexity**</font>

可以看出雖然左邊的樹 training error 較小，但因為其模型複雜度較大 (leaf node 較多)，懲罰係數 * k 會拉高整體 error，同理右邊樹雖然 training error 大，但其樹較小棵不會過度拉高 generalized error，因此此方法考慮了 **訓練誤差及模型複雜度** 的綜合影響來評估要選取大樹還是小樹，避免 overfitting。

>[!Important]涵義
>樹越大棵，training error 應越小，但 leaf 數量越多，**Ω 會乘以較大的 k 值**，使 generalized error 上升，有 **平衡** 的效果。

## MDL Principle
**「Minimum Description Length Priciple**」，指的是一個好的模型應該要能 ==**最簡潔地描述模型資訊**==，讓「模型 + 資料」所需的 **傳遞成本** 最小，也就是當我們訓練完一個模型，將此模型傳遞給另一個人使用，若此傳遞成本越小代表此模型效能越好。

<font color = 'purple'>**cost(model,data) = cost(model) + cost(data | model)**</font>

* **cost(mode)**
The cost of encoding model，也等於訓練此模型的成本。
* **cost(data | model)**
The cost of encoding mislabeled record，傳遞的是分類錯誤的資訊，若模型是 100% 正確，那 cost(model,data) 就等於訓練模型所需的成本而已。

## Statistical bounds on training error
由於 generalized error 通常 > Training error，為了避免 training error 過於樂觀，會預估一個 **training error 的上界 (upper bound) 來模擬最壞情況**，以此 upper bound 估計 generalized error。


α: 顯著水準，例如 α = 0.05 代表有 95% 的信心估計此 generalized error。
N: 訓練樣本數。
e: 訓練錯誤率。
z α/2: 在顯著水準下的 Z 分數。

ex: 以 Decision Tree 為例，在建樹過程想觀察某節點有沒有繼續分裂的必要，可以用 statistical upper bound 來分別估計節點分裂與不分裂的誤差，左子樹 TL 的該節點分裂成兩個 leaf node，右子樹 TR 該節點則成為 leaf node。

<img src="https://hackmd.io/_uploads/rkBNqvUklx.png" width="85%" height="650">

結果得出 TL 的兩個葉節點 error upper = 0.585 > TR 的 0.503，因此 **TR 不分裂的樹誤差較小**，此節點應該選擇不繼續增長。

>[!Tip]
>這裡也可以看出使用 **上界估計** 得到的誤差 = 0.503 > 原本的訓練 error rate 2/7 = 0.28，**避免了訓練誤差過於樂觀的結果**。

# Rule-based Classifier
一個分類的 rule 表示為 `r : A → y`，其中 A 為一組 **attribute test condition**。
==**ri : (Condition i) → yi**==
* **Condition i : antecedent/precondition**
稱為「前件」，為一組條件，可包含多個子條件，用 AND/OR 連結，包含了一組 conjunction of attribute tests。
* **yi : consequent**
* 「後件」，前件成立時所預測出的 y 值。

其中 **Condition i = (A1 op v1) ∩ (A2 op v2) ∩...∩ (Ak op vk)**，每一組 (Ai,vi) 是 Attribute value set，op 為各種邏輯判斷子 {=,<,>,<=,>= 等等}，每一組 (Ai op vi) 被稱做 conjunct。
ex : r1 : (Give births = no) ∩ (Aerial creature = Yes) → Birds

## Two properties of rule set
1. **Mutually Exclusive**
同一筆 instance 不能 **同時觸發** rule set 中的任兩條 rules，此規則限制了 **一筆樣本最多只能觸發一條 rule**。
3. **Exhaustive**
每筆 instance 都 **至少** 被一條 rule cover。

如果 rule set 不是 Exhaustive，就必須要設定 `default rule, rd : () → yd`，來涵蓋那些 **沒有被任何一條 rule 包住的 instances**。
* **rd : ()**
是一個 **empty antecedent**，對於某筆樣本，當 **所有 rules 都失敗時** 即觸發 default rule。
* **yd**
從訓練資料那些未被已存在的 rules 覆蓋的樣本，挑選 **majority class** 做為 yd 的值。

<font size = 4>**有序性**</font>
* **Unordered rule set**
rule set 裡的 rules 沒有順序重要性，instances 進來會 **測試每條 rule** 是否符合，最終再用 **vote** 決定哪條 rule 要當做此筆樣本的預測。
* **Ordered rule set**
一開始要先將 <font color = 'red'>**rules 排序 (sort)**</font>，instance 進入後從第一條開始測試是否符合，不斷往下直到找到 **第一條符合的 rule**，此方法 model building 成本較高，因為需先排序。

## Sequential Covering Algorithm
建立 Rule-based Classifier 前須先萃取一個 **rule set**，**Sequential Covering Algorithm** 是一種從 **「data」** 中 extract classification rules 的演算法。

// 一次針對一個類別 extract rule
1. E : training instances, A : Attribute-value pairs (discrete)
2. Ordered class value : {y1,y2,...,yk}，以錯誤懲罰為排序依據，越大的越靠前
3. Rule set R = {}
4. For each class value y in {y1,y2,...,yk} do
5.    Restore E (每個類別 y 都要以完整的 training instances 尋找規則)
6.    while stopping condition is not meet
7.        r ⟵ learn-one-rule(E,A,y)
8.        從 E 移除被 r 覆蓋的 instances
9.        R ⟵ R ∪ {r}
10.   end while
11. end for
12. 將 default rule{} → yk 加入 R 中 

<font size = 4>**Learn-one-rule function**</font>
其目標是從訓練資料 (可能不為原始 E) ==**「找到一條 rule」**==，能涵蓋最多 positive examples，且不涵蓋或僅涵蓋少量 negative examples。

generate a initial rule
* r : { } → y
* r : {Give births = no} → y
* r : {Give births = no, Aerial = Yes} → y **(要評估新規則是否更準確)**
.
.
.

直到 stopping criterion => 已找到一條 **best rule**

## FOIL Information gain
最普通用於評估一條 rule 的好壞的標準可以用以下兩個指標:
* **Coverage (rule)** = |A| / |D|
* **Accuracy (rule)** = |A ∩ y| / |A|
A : 滿足 rule antecedent (不一定 consequent 為 y) 的 records 數
D : records 數
A ∩ y : 同時滿足 antecedent 與 consequent 的 records 數

由上述可觀察到 Accuracy 並 **未考慮到 Coverage**，就算準確度很高但可能此 rule **只涵蓋到少量的樣本**。

因此需要有一種 evaluation metric 來評估某個 **conjuct** 在 rule-growing 階段是否可以被加入到 rule 中 => <font color = 'red'>**FOIL Information gain**</font> (on test condition X = x)

* po : origin rule 中涵蓋的 positive examples 數。
* no : origin rule 中涵蓋的 negative examples 數。
* p1 : new rule 中涵蓋的 positive examples 數。
* n1 : new rule 中涵蓋的 negative examples 數。

此評估方法是看 **new rule (新加一個 antecedent)** 是否對 accuracy 有提升，並考慮了涵蓋的 positive examples 數，考慮到 Coverage。

# RIPPER
是一種基於 **Rule based** 的演算法，並具有 **Pruning (剪枝)** 的能力。

Steps:
* 對類別依照樣本數排序 {y1,y2,...,yk}，其中 **y1 為最少數類別**。
* 優先學最少數類別 y1 => **y1 : positive,其餘類別 : negative**。
* repeat learning rule to y2,y3,...yk-1。
* yk 類別被指派到 **default rule**。

<font color = 'red'>**How to learn ?**</font>
1. **Rule growing**
使用 **general-to-specific** + **FOIL 評估法則來生成 rule**。
→ 從 {} 不斷加 **antecedent** (用 FOIL 評估 antecedent) 直到 rule 可以 **涵蓋所有的 positive examples**，new rule : {X1 = x1,X2 = x2,,,,} → y。
3. **Rule Pruning**
因為前一步生成的 rule 涵蓋最多 antecedent 與所有正類別樣本，有 **「overfitting」** 的風險，故做 pruning。
→ 根據 <font color = 'purple'>**validation set (未參與 rule growing)**</font> 的樣本對 rule 做評估，
計算 `(p - n) / (p + n)`，其中 p / n 為 validation set 中 **被此 rule 涵蓋的 positive / negative records 數**。

5. 將修剪完的 rule 新增到 Rule set 中，**移除此 rule 涵蓋的例子**，針對當前類別 yi 還需要尋找下一條 rule 直到所有 y record 都被涵蓋 (或 can't improve)。

# Nearest Neighbors Classifier
首先了解 classification learner 可以分為兩種

## k-Neareset Neighbors
test instance 的類別值是靠 **k 個與其距離最相近** 的訓練集 record 的類別值決定 (**lazy learner，訓練集都不做行為直到有 testing data 進來)**。

Algorithm:

1. 指定 k,training set D
2. For each testing instances z = (x',y')
3.    計算所有 training instances (x,y) ∈ D 與 z 的距離 d(x',x)
4.    決定 Dz : 測試點 z 的 k closest neighbors set
5.    做 majority voting 決定 z 點的類別值
6. End for

>[!Tip]
>當 k 太小時，考慮的 training 樣本數太少，可能納入過多 **noise** 導致 **overfitting**，當 k 太大可能會納入 **過多 far away 的樣本** 導致分類不準確。

# Naive Bayesian Classifier
## Bayesian Classifier
一種基於 **「貝氏定理」** 的分類器，主要想抓取 **Attribute set X 與 class value Y 間的統計關係**，計算 <font color = 'red'>**P(Y | X) 判斷在 X 條件下哪一個類別 Y 發生的機率最大**</font> 來做預測。

因此我們要求的目標是 **P(Y | X)**，又被稱為 **posterior probabilities**，其是衍生自 **prior probabilities,P(Y)**，加上進入的 **evidence X**。

**Bayesian Classifier** 的運作即是先學習 **訓練集的每一組 (X,Y) 的後驗機率 P(Y | X)** 並儲存到模型中，等到一筆 test instace (X') 進入模型後，就可以去尋找 **哪個 Y' 可以最大化後驗機率**
**P(Y' | X')**，即可得到預測結果 Y'。
由上圖可以得知 P(Y | X) 的計算公式，而 P(X) 對於每種類別值 y 都是固定的，且 P(Y) 也很容易能從資料集中算出，因此要專注考慮的是 **P(X | Y)，又被稱作 class-condition**，其中有一種方法可以快速計算此值，並推導出最後目標後驗機率 P(Y | X)，稱作 **「Naive Bayesian Classifier」**。

## Confidence Independence
給定 class value y 值，Naive Bayesian Classifier 會將 **X 裡所有特徵視為 independent**，將 **class-condition P(X | Y)** 拆解成 **每一個 Xi 的機率 (給定 y 前提下)**，attribute set X = {X1,X2,...,Xd}。


有了 **Confidence Independence** 幫助，我們就可以只單純計算 **每個 Xi, given Y** 的機率，得出 **class-condition P(X | Y)**，應用 Naive Bayesian Classifier 時，只要計算 test data 對於 **每個類別值 Cj (此處 y = Cj) 對應的後驗機率 P(Cj | X)**，找出能最大化後驗機率的類別值即可。


其中 `P(Xi | Cj) = Nij / Nj`，`P(Cj) = Nj / N`
* Nij : 類別為 j 的樣本中，特徵 X 值為 i 的數量。
* Nj : 資料集中 class value 為 Cj 的樣本數。
* N : 總資料筆數。

>[!Warning]機率為 0
>但原始 Naive Bayesian Classifier 會遇到以下問題
>
>
>若在訓練資料或測試資料中有 **「從未出現過的特徵值與類別組合」**，則此 P(Xi | Cj) 會等於 0，這樣會使整個 P(X | Cj) 都被降為 0，進而導致 **最終的後驗機率 = 0**，這樣讓 **此特徵組合 X 下類別 Cj 永遠無法被選擇**，即使其餘特徵值 P(Xi | Cj) 十分強大，因此可以使用 <font color = 'red'>**Laplace estimate**</font> 來改善。

## Laplace estimate
核心思想是 **「即使不存在的特徵值與類別值組合也給予其一個非常小的機率值 (不為零)」**

## Continuous Attribute
上述說明的特徵 Xi = xi 都是 **離散型特徵**，特徵值種類是少量的，但如果今天是 **連續型特徵**，如收入，範圍會過大且具有太多特徵可能，計算機率會十分龐大，因此有兩種方法可以處理連續型特徵:
1. **Discretization**
將連續型的 attribute value 離散化成 ordinal value。
3. **Gaussian distribution**
因為 Attributei | Y = yi ~ Normal (μ,σ)，我們可以用這個平均值與標準差來估計在特定類別值下 Attributei 的 **P(Ai = xi | Y = yi)**，注意此機率不是 class-condition，而是 **「其中的一個特徵」** 的可能特徵值的機率。

>[!Tip]注意
>同一個 Attribute，在 **不同類別值 y** 下的 (μ,σ) 會不一樣。

# Ensemble Methods
「集成學習」會從訓練資料中建構一組 classification models 集合，並對 base models 的預測做 vote 來決定最終預測。

ex:
有一個 **ensemble model** 集合 **25 個 base models**，每個 base model 的 **error rate ε = 0.35**，因此 ensemble model 可以預測正確的機率為 **P(M{Xi} = 1)**

可以看到原本的預測正確率是 1 - ε = 0.65，使用集成模型後提升到 0.94，而其優勢在於，若每個 base model 都是 **Independent**，結合最終預測是使用 **majority voting**，必須要 **超過半數的 base models 預測錯誤**，才會使最終結果錯誤。

>[!Important]Ensemble model 的條件:
>* 錯誤率 error rate < 0.5，必須要好過亂猜。
>* base models 間要 **Independent**。

<font size = 4>**How to construct a ensemble model:**</font>
* **Manipulating the training set**
每個 base model 使用的 training set 會從 origin data 中 **resampling**，<font color = 'red'>**大小通常與原始訓練集一樣**</font>，且樣本可能完全一樣或部分不同，看演算法而定，常見的抽取方式有 **Bagging**、**Boosting**。
* **Manipulating the input features**
每個 base model 會使用 **不同的 subset of features** 來建構訓練資料，可以 **隨機選取** 或依照專家經驗，如 **Random Forest** 就是使用部分特徵集合來建立每棵 Decision Tree。

Algorithm.general procedure for ensemble method

D : original traing data (size = N),k : number of base classifiers
1. For i = 1 to k do
2.     Create training set Di from D (size = N)
3.     Build a base classifier Ci from Di
4. End for
5. For each test record x do
       // 對 base model 的預測結果投票
6.     class*(x) = vote(C1(x),C2(x),...,Ck(x))  
7. End for

## Bagging
**「Bootstrap Aggregating」**，Boostrap 是指在訓練集 <font color = 'red'>**抽樣時採取後放回**</font> 的作法，而 Baaging 將每個 base model 用到的訓練集都採 **Bootstrap** 的方法產生，產生的 training set 大小與原始訓練集一樣，且因為採 **with replacement，同一筆資料可能重複出現在同一個訓練集裡多次**，Bagging 的意義在於可以 **減少 variance (模型對資料的敏感度)**。


Bagging 對於 stable 與 unstable model 有不同的效果:
* **Unstable model**
首先了解 Boostrap 會使抽樣後訓練集大約 **包含 63% 的原始訓練集資料**，減少 training set 抽取到大量 noise 的機會，而 **unstable model 對於資料的波動性非常敏感** (Decision Tree)，可能某筆資料的類別值改動就會造成結果相差，因此 <font color = 'red'>**Bagging 可以降低 training data 的資料波動性**</font>，提升模型泛化能力。
* **Stable model**
穩定模型 (Naive Bayes) 對於 **訓練資料的波動不敏感**，所以每次 Bagging 出的訓練集對模型來說都 **「差不多」**，訓練出的 base classifier 幾乎一樣，故提升效果不顯著，且 Bootstrap sample 大約只包含 63% 的原始樣本，對於 stable model 樣本量不足，**甚至可能有降低泛化能力的風險**。

## Boosting
Boosting 的做法是會在 **訓練過程中不斷改變樣本被抽取的機率 (權重)**，來更專注在那些較難被分類正確的樣本，其生成 base model 是 <font color = 'red'>**有順序性的**</font>，前一個 base model 生成預測完畢，才能繼續改變樣本權重並生成下一個 base model，那些 **被預測錯誤的樣本權重會在下一輪 bootstrap 時上升**，而被分類正確的樣本權重則會下降。
>[!Warning]缺點
>Boosting 缺點在於 **可能過度擬合那些錯誤樣本**，而讓先前預測正確的樣本後來被分類錯誤，最後 ensemble 後 Accuracy 不好。

比較:

| 說明 | Bagging | Boosting |
| -------- | -------- | -------- |
| Bootstrap 樣本機率 | 每個樣本被抽取機率相同 | 依照前一個 base model 結果調整樣本權重 |
| base model 是否平行生成|是，平行挑選訓練集並平行生成 base model | 只能順序挑選樣本並產生 base model|
| 預測結果 | 採 Majority vote | 採 Weighted vote |
| 效能 | 能提升泛化能力 | 可能較 Bagging 不好 |

## Random Forest
<font color = 'purple'>**Random Forest = Bagging + Decision Tree + Feature Randomness**</font>

**隨機森林** 是由多棵決策樹集合而成，以多數決投票方式決定最終預測，RF 引入 **「隨機性」**，讓每顆樹盡量 **Independent**，進而提升模型泛化能力。

* **資料隨機性**
用 **Bagging** 產生每棵決策樹的 training set。
* **特徵隨機性**
每棵 decision tree 分裂時不是從全部特徵中找分裂屬性，而是從 **一部分隨機挑選出的特徵** 中選取，這樣讓每棵樹都是 <font color = 'red'>**應用到不同 attribute subset**</font> 來增長，提高隨機性，讓每棵樹都長得不一樣。
* **Unpruning**
每顆決策樹都 **不剪枝**，讓他完全生長，這樣能讓每棵樹間越 **Independent**。
→ 大多數 ensemble 強調 <font color = 'purple'>**decorrelated**</font>，讓 base models 的預測盡量不一樣

# Cross Validation
交叉驗證想要評估的是 <font color = 'red'>**Algorithm**</font> 的效能，而非 model，因為 model 的預測能力是取決於當下挑到的訓練集樣本。
## K-fold cross validation
* **Bias**
指的是做 k-fold 後得到的平均準確率與實際準確率的偏差。
* **Variance**
做 k-fold 所產生的 k 個子模型的準確率間的變異性。

影響 k-fold 的四大因素:
1. **The number of folds (k)**
k 值越小，代表訓練集被分成較少的 folds，**k 次訓練的樣本數會減少** (因為當測試集的那個 folds 包含更多原始訓練集樣本)，模型雖然會更具泛化性，但容易欠擬合，會導致有更大的 Bias，而 k 若較大，每回訓練的樣本數就變多，更能學習到與原始數據相近的關係，最終的平均準確率 Bias 較低，但因為測試集 fold 包含樣本較少，單一樣本預測錯誤就會造成估計準確率波動，因此 Variance 提高。
2. **The number of instances in a fold**
當每個 fold 包含的樣本數很少，就會對單一樣本的預測更敏感，Variance 容易提高，當每個 fold 的樣本數多，雖然會提高 Bias (因為訓練樣本可能不足)，但能降低 Variance。
3. **The level of averaging**
如何將 k 次測試結果取平均，如做簡單平均或加權平均，不當的平均方法可能高估或低估最終估計準確率。
4. **The repetition of k-folds cross validation**
單次 k-fold 可能會受到樣本分組的隨機性影響，多次重複可以減少這種隨機誤差，提高結果的穩定性。通常稱為 **Repeated k-fold Cross Validation**，可以顯著降低 variance。

## Sampling Distribution
以往都沒有探討 **sampling distrubtion** 對於 cross validation 的效能評估差異，以下將介紹 sampling distribution 對於 k-folds、leave one out cross validation 的差異。