[toc]

# 什麼是 Classification

分類（Classification）是機器學習中一種監督式學習（Supervised Learning）的方法，分類的主要目的是根據資料的特徵（Features），將資料點分配到不同的類別中。這些類別通常是事先定義好的，我們稱之為標籤（Label）。假設我們有一組電子郵件的資料集，我們想知道每封郵件是「垃圾郵件」還是「非垃圾郵件」。這就是一個二分類問題，因為只有兩個可能的結果。我們根據郵件的某些特徵來判斷它是否屬於垃圾郵件，例如「是否包含可疑連結」、「郵件的長度」等。

## 如何進行分類？

分類的過程可以分為以下幾個步驟：

1. 資料準備
在分類問題中，我們需要有標籤的資料來進行訓練，這些資料的特徵和標籤已經被標記出來。接著，我們會將資料分為訓練集和測試集：

* 訓練集（Training Set）：用來訓練模型。 80%
* 測試集（Test Set）：用來評估模型的性能。 20%

2. 選擇分類演算法
有多種不同的分類演算法，每一種演算法都有不同的特點。常見的分類演算法包括：
* K近鄰演算法（K-Nearest Neighbors, KNN）：根據與訓練資料點的距離，選擇最接近的K個鄰居進行投票，判斷新的資料點應該屬於哪一類。
* 決策樹（Decision Tree）：通過分裂資料集，找到能夠最好區分資料的特徵，並構建一棵樹，將每個資料點分配到不同的葉節點。
* 邏輯迴歸（Logistic Regression）：預測一個資料點屬於某一類的概率，並通過閾值來做二分類決策。
3. 訓練模型
我們用訓練集來訓練模型，模型會學習特徵和標籤之間的關聯性，從而對新資料進行預測。
4. 評估模型
在模型訓練完成後，我們需要使用測試集來評估模型的準確性，這就涉及到一些關鍵的評估指標。

### 評估指標

在分類問題中，以下四個指標是非常重要的：

1. 準確率（Accuracy）
準確率衡量的是模型預測正確的比例。公式為：
\begin{equation}
Accuracy = \frac{正確預測的樣本數}{總樣本數}
\end{equation}
例如，如果模型預測100封電子郵件中有90封正確，那麼準確率就是90%。

2. 精確率（Precision）
精確率關注的是模型預測為某個類別（例如「垃圾郵件」）時，預測的準確性。公式為：
\begin{equation}
Precision= \frac{真陽性（True Positive）}{真陽性 + 假陽性（False Positive）}
\end{equation}
假設模型預測了50封垃圾郵件，實際上其中有40封確實是垃圾郵件，則精確率為 $\frac{40}{50} = 0.8$ （即80%）。
3. 召回率（Recall）
召回率衡量的是模型在實際屬於某類別（例如「垃圾郵件」）的資料中，預測正確的比例。公式為：
\begin{equation}
Recall = \frac{真陽性（True Positive）}{真陽性 + 假陰性（False Negative）}
\end{equation}
如果我們有100封實際垃圾郵件，而模型正確預測了其中80封，則召回率為 $\frac{80}{100} = 0.8$
4. F1分數（F1-Score）
F1分數是精確率和召回率的調和平均數，用來平衡兩者的影響。公式為：
\begin{equation}
F1 = 2 × \frac{Precision×Recall}{Precision+Recall}
\end{equation}

> 在分類問題中，當我們使用模型進行預測後，結果可以分為以下四種情況，這些情況和 **真陽性（True Positive）、假陽性（False Positive）、假陰性（False Negative）和真陰性（True Negative）** 有關。這些概念是分類器性能評估中的關鍵，特別是在二分類問題中（例如判斷是否是垃圾郵件、是否患病等）。下面詳細解釋每個概念：
>
> 1. 真陽性（True Positive, TP）
> 真陽性是指模型預測結果為「正類別」，而實際情況也確實是「正類別」。
> 例子：系統預測病人有病，實際病人也有病。這是正確的預測，因此是「真陽性」。
> 含義：模型對於正類別的正確判斷。
>
> 2. 假陽性（False Positive, FP）
> 假陽性是指模型預測結果為「正類別」，但實際情況是「負類別」。
> 例子：系統預測病人有病，但實際病人無病。這是一個錯誤預測，系統誤判病人有病，因此是「假陽性」。
> 含義：模型錯誤地將負類別預測為正類別。
>
> 3. 假陰性（False Negative, FN）
> 假陰性是指模型預測結果為「負類別」，但實際情況是「正類別」。
> 例子：系統預測病人無病，但實際病人有病。這是一個嚴重的錯誤，因此是「假陰性」。
> 含義：模型錯誤地將正類別預測為負類別。
>
> 4. 真陰性（True Negative, TN）
> 真陰性是指模型預測結果為「負類別」，而實際情況也確實是「負類別」。
> 例子：系統預測病人無病，實際病人也無病。這是正確的預測，因此是「真陰性」。
> 含義：模型對於負類別的正確判斷。

# 過擬合與欠擬合

## 過擬合（Overfitting）
過擬合是指模型在訓練資料上表現很好，但在測試資料上表現不佳。這通常是因為模型學到了訓練資料中的噪音或不相關的特徵，導致其無法泛化到新資料上。

簡單來說過擬合是對特定事物了解得太多以致於無法變通，以月亮為例，認得出各種各樣的月亮，但一旦出現了不是月亮的東西，就開始胡言亂語

## 欠擬合（Underfitting）

欠擬合則是指模型過於簡單，無法捕捉資料中的關鍵模式，導致訓練資料和測試資料的預測效果都不好。

認得出滿月🌕是月亮，上弦月🌓下弦月🌗殘月🌖這些都認不出是月亮，即沒學明白，訓練集效果差驗證集效果也差

# 熵（Entropy）與資訊增益（Information Gain）

熵（Entropy）和資訊增益（Information Gain）是分類問題中非常重要的概念，尤其是在決策樹等分類演算法中。它們用來衡量資料集的不確定性和特徵對於分類效果的貢獻。

## 熵（Entropy）

熵源自資訊理論，是由 Claude Shannon 提出的，用來度量資料的「不確定性」或「混亂程度」。在分類問題中，熵用來衡量資料集中類別分佈的純度。熵的值越高，表示資料越混亂；熵的值越低，表示資料越純。

假設一個資料集 $S$ 中有 $k$ 個類別，每個類別 $C_{i}$ 出現的機率為 $p_{i}$ ，那麼資料集的熵可以計算為：

\begin{equation}
H(S) = − \sum_{i=1}^{k} p_{i} log(p_{i})
\end{equation}

其中:
* $p_{i}$ 是類別 $C_{i}$ 的出現機率。
* $log_{2}$ 是以 2 為底的對數，因為我們衡量的是二進制資訊。

熵的值範圍是從 0 到 $log_{2}(k)$ 取決於類別分佈：
* 當熵為 0 時，表示資料集非常純，即所有樣本都屬於同一個類別。這種情況下，資料集沒有任何不確定性，模型已經知道所有資料都屬於一個類別，不需要進一步的分類。
* 熵較高 表示資料集中有多個類別，並且類別分佈比較均勻，這樣的資料集存在更大的不確定性，模型需要努力學習如何區分不同的類別。

假設我們有一個資料集，其中有 10 個樣本，屬於兩個類別：類別 A 和類別 B。資料的分佈情況如下：
* 7 個樣本屬於類別 A。
* 3 個樣本屬於類別 B。

此時，類別 A 出現的機率 $p_{A} = \frac{7}{10}$ ，類別 B 出現的機率 $p_{B} = \frac{3}{10}$。則這個資料集的熵為：

\begin{equation}
H(S) = − (\frac{7}{10}log_{2}\frac{7}{10} + \frac{3}{10}log_{2}\frac{3}{10})
\end{equation}

計算結果大約為：

\begin{equation}
H(S) \approx 0.881
\end{equation}

這個熵值表明資料集中的樣本有些混亂，但還沒有完全隨機。

> 熵越低，資料集越純，分類的效果越好。這在決策樹中非常重要，因為我們希望通過分裂資料集來減少不確定性（也就是降低熵），以便更好地進行分類。

### 具體應用和意義

資料集通常需要包含多個類別來進行分類模型的訓練。如果一個資料集中的所有資料都屬於同一個類別，那麼這個資料集是無法有效進行分類模型訓練的，因為模型沒有辦法學習如何區分不同的類別。

為什麼熵為 0 不適合訓練？

當資料集中的所有樣本都屬於一個類別時，熵為 0。這意味著資料集中沒有任何不確定性，沒有混亂。雖然這對於理論上的「純度」來說是理想的，但對於訓練分類模型來說是無意義的，因為模型沒有其他類別可以學習如何進行區分。
> 如果一個資料集中的所有樣本都屬於「垃圾郵件」，那麼模型只會學習到「所有郵件都是垃圾郵件」，無法學習如何區分垃圾郵件和正常郵件。

在決策樹演算法中，我們用熵來選擇特徵進行分裂。決策樹的目標是逐步減少熵，也就是說，通過使用某些特徵，將資料集分成更純的子集，從而降低每個子集的混亂程度。

* 初始資料集：在模型開始訓練時，資料集中可能包含多個類別，並且類別之間的分佈可能很混亂（熵較高）。
* 分裂資料集：我們使用一個特徵來將資料集進行分裂，希望分裂後的子集每個都變得更加「純」。例如，分裂後的某些子集可能只包含一個類別（熵為 0），而其他子集則依然混亂（熵較高）。
* 遞迴分裂：模型會反覆分裂資料集，直到每個子集的熵都接近 0，也就是資料基本被分類到某個單一的類別中。

## 資訊增益（Information Gain）

資訊增益是在分類問題中，用來衡量使用某個特徵進行資料分裂後，資料集的不確定性（熵）減少了多少。換句話說，資訊增益告訴我們一個特徵在減少分類混亂程度上有多大的貢獻。決策樹等演算法會選擇資訊增益最大的特徵來進行分裂，從而逐步構建分類樹。

假設我們有一個資料集 $S$ 使用特徵 $A$ 進行分裂，特徵 $A$ 有 $v$ 種不同的取值，將資料集 $S$ 分裂為 $v$ 個子集 $S_{1}, S_{2},...S_{v}$ 。每個子集 $S_{i}$ 包含資料集 $S$ 中那些特徵 $A$ 取值為 $v_{i}$ 的樣本。則使用特徵 $A$ 進行分裂後的資訊增益 $IG(S,A)$ 為：

\begin{equation}
IG(S,A) = H(S) - \sum_{i=1}^{v}\frac{|S_{i}|}{|S|}H(S_{i})
\end{equation}

其中：
* $H(S)$ 是分裂前資料集 $S$ 的熵。
* $H(S_{i})$ 是分裂後子集 $S_{i}$ 的熵。
* $\frac{|S_{i}|}{|S|}$ 是子集 $S_{i}$ 相對於原資料集的比例。

假設我們的資料集有兩個特徵：「顏色」和「形狀」，樣本分佈如下：

| 樣本 | 顏色 | 形狀 | 類別 |
| -------- | -------- | -------- | -------- |
| 1 | 紅色 | 圓形 | A |
| 2 | 紅色 | 圓形 | A |
| 3 | 藍色 | 圓形 | A |
| 4 | 藍色 | 方形 | B |
| 5 | 藍色 | 方形 | B |

這個資料集中有 3 個樣本屬於類別 A，2 個樣本屬於類別 B，我們先計算資料集的初始熵：

\begin{equation}
H(S) = - (\frac{3}{5}log_{2}\frac{3}{5} + \frac{2}{5}log_{2}\frac{2}{5})
\end{equation}

計算結果大約為：

\begin{equation}
H(S) \approx 0.971
\end{equation}

#### 使用特徵「顏色」進行分裂

如果我們使用「顏色」這個特徵來分裂資料集，我們會得到兩個子集：

* 子集 1：顏色為紅色的樣本 $[1,2]$，這兩個樣本都屬於類別 A（熵為 0）。
* 子集 2：顏色為藍色的樣本 $[3,4,5]$，其中 1 個樣本屬於 A，2 個樣本屬於 B。

首先計算每個子集的熵：

* 子集 1 的熵：因為所有樣本都屬於類別 A，熵為 0。
* 子集 2 的熵：

\begin{equation}
H(S) = - (\frac{1}{3}log_{2}\frac{1}{3} + \frac{2}{3}log_{2}\frac{2}{3})
\end{equation}

計算結果大約為：

\begin{equation}
H(S_{2}) \approx 0.918
\end{equation}

接下來，我們計算分裂後的總熵（加權平均熵）：

\begin{equation}
H_{split} = \frac{2}{5} × 0 + \frac{3}{5} × 0.918 \approx 0.551
\end{equation}

最後，計算使用「顏色」特徵進行分裂的資訊增益：

\begin{equation}
IG(S,顏色) = H(S) - H_{split} = 0.971 - 0.551 = 0.42
\end{equation}

> 加權平均熵（Weighted Average Entropy） 是在決策樹演算法中，衡量使用某個特徵分裂資料集後，所有子集的熵的加權平均值。它是根據每個子集中樣本數量相對於整個資料集的比例來計算的，並且反映了分裂後整個資料集的總熵。
> 在決策樹中，我們希望通過特徵的分裂，將資料集逐步分成更加純的子集（即熵更低的子集）。但是，分裂後可能會產生多個子集，而這些子集中的資料數量可能不均衡。為了更精確地衡量整個資料集的純度變化，我們需要考慮每個子集的熵以及它們的大小。因此，我們使用加權平均熵來計算分裂後的總熵。

#### 使用特徵「形狀」進行分裂

接下來，我們使用「形狀」這個特徵來分裂資料集，也得到兩個子集：

子集 1：形狀為圓形的樣本 $[1,2,3]$，其中 3 個樣本屬於 A（熵為 0）。
子集 2：形狀為方形的樣本 $[4,5]$，其中 2 個樣本屬於 B（熵為 0）。

由於這兩個子集中的樣本都屬於同一個類別，因此兩個子集的熵都為 0。

分裂後的總熵為：

\begin{equation}
H_{split} = 0
\end{equation}

資訊增益為：

\begin{equation}
IG(S,形狀) = = 0.971 - 0 = 0.971
\end{equation}

在這個例子中，使用「形狀」特徵的資訊增益比「顏色」特徵更大，因此決策樹會優先選擇「形狀」作為第一個分裂的特徵，因為它能夠更好地將資料集分得更純。

# 常見演算法

## ID3（Iterative Dichotomiser 3）

ID3 是由 Ross Quinlan 在 1986 年提出的演算法，是決策樹演算法的一個經典版本。ID3 演算法的核心思想是使用 **資訊增益（Information Gain）** 來選擇每次分裂的最佳特徵，讓決策樹能夠盡量將資料集分成更純的子集。

> 決策樹（Decision Tree） 是一種基於樹狀結構的分類演算法，它通過遞迴地分裂資料集來進行分類。每個內部節點代表一個特徵，分支代表該特徵的不同取值，葉節點則是分類的結果。決策樹非常直觀，並且能夠同時處理類別型和數值型資料。

### ID3 的關鍵概念
1. 熵（Entropy） 上述筆記有
2. 資訊增益（Information Gain） 上述筆記有

在 ID3 中，每次選擇特徵時，我們會計算每個特徵的資訊增益，選擇資訊增益最大的特徵進行分裂。這樣可以最大化分類的效果，並使資料集變得更加純（熵更低）。

### ID3 演算法的步驟

1. 計算初始熵：對於給定的資料集，首先計算資料集的熵，這是一個衡量資料集內部混亂程度的指標。

2. 計算各特徵的資訊增益：遍歷每個特徵，對每個特徵進行分裂，計算分裂後的子集的熵，並基於加權平均熵計算該特徵的資訊增益。

3. 選擇資訊增益最大的特徵進行分裂：選擇資訊增益最大的特徵作為當前節點的分裂依據，並根據該特徵的取值將資料集分裂為子集。

4. 遞迴構建子樹：對於每個子集，重複上述過程，直到資料集中的樣本都屬於同一類別（熵為 0），或沒有更多特徵可用來分裂。

5. 終止條件：當所有資料集都被正確分類，或無更多特徵可以使用時，決策樹結束構建，樹的每個葉節點對應於最終的分類結果。

根節點（頂端節點）：
1. `shape ≤ 0.5`：這表示第一個用來分裂資料集的特徵是「形狀」。根據「形狀」的值是否小於等於 0.5 來進行分裂。這裡的 0.5 代表的是數值化之後的形狀特徵值。
2. `entropy = 0.971`：表示在這個節點的資料集的熵（不確定性）為 0.971。熵越高，資料集越混亂，表示類別分佈比較混合。
3. `samples = 5`：表示這個節點包含 5 個樣本。
4. `value = [3, 2]`：表示這個節點中的 5 個樣本裡有 3 個屬於類別 A，2 個屬於類別 B。
5. `class = A`：這表示根據當前節點中的資料，模型的預測是類別 A，因為大多數樣本屬於類別 A。

分支：

* 左邊的 `True` 表示「形狀」特徵的數值小於等於 0.5 的樣本走這個分支。
* 右邊的 `False` 表示「形狀」特徵的數值大於 0.5 的樣本走右邊的分支。

葉節點（最終節點）：

* 左側葉節點：
* `entropy` = 0.0：表示這個子集的資料完全純，所有樣本屬於同一類別。
* `samples` = 3：這個節點包含 3 個樣本。
* `value` = [3, 0]：所有樣本都屬於類別 A。
* `class` = A：最終分類為 A，因為所有樣本都屬於類別 A。
* 右側葉節點：
* `entropy` = 0.0：表示這個子集的資料也完全純，所有樣本屬於同一類別。
* `samples` = 2：這個節點包含 2 個樣本。
* `value` = [0, 2]：所有樣本都屬於類別 B。
* `class` = B：最終分類為 B，因為所有樣本都屬於類別 B。

## 隨機森林（Random Forest）

隨機森林（Random Forest） 是一種基於集成學習（Ensemble Learning）技術的分類與回歸演算法，由 Leo Breiman 在 2001 年提出。它是通過構建多棵決策樹（Decision Tree），並將這些樹的預測結果進行集成，來提高分類或回歸的準確性和穩健性。

隨機森林的核心思想是通過多樣性來提高模型的性能。具體來說，隨機森林會使用不同的子資料集來訓練多棵決策樹，並且在每棵樹的構建過程中隨機選擇特徵進行分裂。最終，通過對所有樹的預測結果進行投票（分類問題）或取平均值（回歸問題），來產生最終預測。

### 隨機森林的基本原理

隨機森林的主要特點是通過隨機性來降低模型的方差（variance），從而提高泛化能力。這裡的隨機性體現在兩個方面：

* 資料集的隨機性：每棵決策樹是通過對原始資料集的 **有放回隨機抽樣** （Bootstrap Sampling）來生成的不同子資料集訓練的。這使得每棵樹都基於不同的資料進行學習。
* 特徵的隨機性：在每棵決策樹的每次分裂過程中，隨機選擇部分特徵來計算最佳分裂點，而不是考慮所有的特徵。這進一步增加了模型的多樣性。

隨機森林通過這兩種隨機性，使得各個決策樹的預測結果相對獨立，並且最終通過集成的方式大大減少了過擬合的風險。

### 隨機森林的構建過程

1. 訓練集的隨機抽樣（Bootstrap Sampling）
對於一個擁有 $N$ 個樣本的資料集，隨機森林會從中進行有放回的隨機抽樣，生成 $m$ 個子資料集。這些子資料集的樣本數與原始資料集相同（也是 $N$ ），但由於是有放回的抽樣，因此有些樣本可能會被重複選取，而有些樣本可能不會被選中。

每個子資料集會用來訓練一棵決策樹，這樣產生的每棵決策樹都有不同的訓練資料，從而具備多樣性。

2. 隨機選擇特徵進行分裂
對於每棵決策樹的每個節點，在進行分裂時，隨機森林不會考慮所有的特徵來選擇最佳分裂點，而是會隨機選擇 $k$ 個特徵（其中 $k$ 通常是所有特徵數的平方根）。然後，僅在這些隨機選出的特徵中選擇分裂點。這種方法防止了決策樹過度依賴少數特徵，進一步增加了樹與樹之間的多樣性。

3. 生成多棵決策樹
隨機森林會構建 $m$ 棵決策樹，每棵決策樹都是通過上述步驟生成的。每棵樹的結構不同，對資料的預測結果也可能不同。

4. 集成投票或平均
* 分類問題：隨機森林中每棵決策樹會對輸入的樣本進行分類，隨機森林的最終預測結果是所有決策樹的預測結果的多數投票結果，即選擇預測次數最多的類別作為最終分類結果。
* 回歸問題：對於回歸問題，隨機森林會對所有決策樹的預測結果取平均值作為最終預測結果。

### 隨機森林的應用

讓我們來看一個簡單的隨機森林分類問題範例，假設我們有一個資料集，包含數個特徵和目標類別，想要判斷一個物品是否為「好」或「壞」。

資料集樣本如下：

| 樣本 | 特徵 1 | 特徵 2 | 特徵 3 | 類別 |
| -------- | -------- | -------- | -------- | -------- |
| 1 | 2.5 | 1.5 | 4.7 | 好 |
| 2 | 1.2 | 2.2 | 3.4 | 壞 |
| 3 | 3.3 | 4.1 | 1.2 | 好 |
| 4 | 2.9 | 3.3 | 2.8 | 壞 |
| 5 | 4.5 | 2.0 | 1.9 | 好 |

步驟1: 訓練集的隨機抽樣（Bootstrap Sampling）

在隨機森林中，首先要生成多棵決策樹，每棵樹的訓練資料集來自於有放回的隨機抽樣。假設我們要構建 3 棵決策樹，那麼對每棵樹，我們將從原始資料集中隨機抽樣。

第一棵樹的抽樣：

| 樣本 | 特徵 1 | 特徵 2 | 特徵 3 | 類別 |
| -------- | -------- | -------- | -------- | -------- |
| 1 | 2.5 | 1.5 | 4.7 | 好 |
| 3 | 3.3 | 4.1 | 1.2 | 好 |
| 5 | 4.5 | 2.0 | 1.9 | 好 |
| 1 | 2.5 | 1.5 | 4.7 | 好 |
| 2 | 1.2 | 2.2 | 3.4 | 壞 |

> 注意：樣本 1 被重複抽取了兩次，這是因為抽樣是有放回的，而樣本 4 沒有被抽取，這些沒有被選中的樣本即為袋外樣本（OOB 樣本）。

第二棵樹的抽樣：

| 樣本 | 特徵 1 | 特徵 2 | 特徵 3 | 類別 |
| -------- | -------- | -------- | -------- | -------- |
| 4 | 2.9 | 3.3 | 2.8 | 壞 |
| 2 | 1.2 | 2.2 | 3.4 | 壞 |
| 3 | 3.3 | 4.1 | 1.2 | 好 |
| 5 | 4.5 | 2.0 | 1.9 | 好 |
| 4 | 2.9 | 3.3 | 2.8 | 壞 |

> 這裡樣本 4 被選取了兩次，而樣本 1 沒有被選中。

第三棵樹的抽樣：

| 樣本 | 特徵 1 | 特徵 2 | 特徵 3 | 類別 |
| -------- | -------- | -------- | -------- | -------- |
| 3 | 3.3 | 4.1 | 1.2 | 好 |
| 2 | 1.2 | 2.2 | 3.4 | 壞 |
| 5 | 4.5 | 2.0 | 1.9 | 好 |
| 1 | 2.5 | 1.5 | 4.7 | 好 |
| 5 | 4.5 | 2.0 | 1.9 | 好 |

> 這裡樣本 5 被選取了兩次，而樣本 4 沒有被選中。

> 袋外樣本（OOB樣本）：袋外樣本是那些在訓練某棵決策樹時沒有被抽樣到的樣本。隨機森林可以利用這些袋外樣本進行模型的內部評估，無需單獨的測試集。比如：
> * 第一棵樹的 OOB 樣本是樣本 4。
> * 第二棵樹的 OOB 樣本是樣本 1。
> * 第三棵樹的 OOB 樣本是樣本 4。
> 隨機森林可以通過這些袋外樣本來進行內部交叉驗證，計算模型的準確率，而無需使用單獨的測試集。

步驟2: 隨機選擇特徵進行分裂

隨機森林中的每棵決策樹在分裂每個節點時，並不使用所有特徵進行分裂，而是從所有特徵中隨機選擇一部分特徵來決定最佳分裂點。這進一步增加了樹與樹之間的多樣性，從而減少過擬合。

我們有 3 個特徵（特徵 1、特徵 2、特徵 3），對於每次分裂，我們隨機選擇兩個特徵來計算分裂點。

第一棵樹的第一個節點分裂：
* 隨機選擇了「特徵 1」和「特徵 2」。
* 計算使用「特徵 1」和「特徵 2」進行分裂的資訊增益或基尼不純度。
* 假設選擇「特徵 1」作為分裂依據，這是因為它的資訊增益較大。

第二棵樹的第一個節點分裂：
* 隨機選擇了「特徵 2」和「特徵 3」。
* 假設這次選擇「特徵 3」作為分裂依據。

第三棵樹的第一個節點分裂：
* 隨機選擇了「特徵 1」和「特徵 3」。
* 假設這次選擇「特徵 3」作為分裂依據。

在這種隨機選擇特徵的過程中，不同的樹會使用不同的特徵來進行分裂，進而使得每棵樹的結構不同。

步驟3: 生成多棵決策樹

在經過上述的隨機抽樣和隨機選擇特徵後，我們可以生成多棵決策樹。每棵樹根據它的訓練資料和隨機選擇的特徵進行分裂，最終構建出一棵分類樹。

決策樹 1 的結構：
* 第一個節點選擇了「特徵 1」進行分裂，然後根據「特徵 1」的取值將樣本分為兩組。
* 對於每個子集，繼續隨機選擇特徵進行分裂，直到所有樣本被分類到某個葉節點。

決策樹 2 的結構：
* 第一個節點選擇了「特徵 3」進行分裂，分裂過程類似於決策樹 1，但使用了不同的特徵。

決策樹 3 的結構：
* 第一個節點選擇了「特徵 3」，然後進行後續分裂，結構與前兩棵樹不同。

### 集成投票或平均

當我們需要對一個新的樣本進行分類時，隨機森林會將該樣本輸入到所有決策樹中，並收集所有決策樹的預測結果。隨機森林會根據這些結果進行投票或取平均值。

假設我們對新樣本進行分類，三棵決策樹的結果分別為：

* 決策樹 1 預測該樣本屬於「好」。
* 決策樹 2 預測該樣本屬於「壞」。
* 決策樹 3 預測該樣本屬於「好」。

那麼最終隨機森林的預測結果是「好」，因為「好」得到了多數投票。

---

### 資訊增益與基尼不純度

在隨機森林中的每次節點分裂時，決策樹會使用 **資訊增益（Information Gain）或基尼不純度（Gini Impurity）** 來衡量分裂的質量，從而選擇最佳的分裂特徵。

基尼不純度：

基尼不純度衡量的是資料集中的不純度。它反映了隨機從資料集中選取兩個樣本，這兩個樣本屬於不同類別的概率。基尼不純度的值範圍是從 0 到 0.5，當資料集中的所有樣本都屬於同一類別時，基尼不純度為 0（純）；當樣本均勻分佈於不同類別時，基尼不純度為最大（0.5）。

\begin{equation}
Gini(S) = 1 - \sum_{i=1}^{k}p_{i}^2
\end{equation}

假設我們有一個資料集 $S$ ，其中其中有 10 個樣本，這些樣本屬於「好」或「壞」兩個類別。資料集的分佈情況如下：
* 6 個樣本屬於「好」類別。
* 4 個樣本屬於「壞」類別。

步驟 1：計算每個類別的比例
* $p(好) = \frac{6}{10} = 0.6$
* $p(壞) = \frac{4}{10} = 0.4$

步驟 2：套入基尼不純度公式

\begin{equation}
Gini(S) = 1 - (p(好)^2 + p(壞)^2)
\\ =>
Gini(S) = 1 - (0.6^2 + 0.4^2)
\\ => 0.48
\end{equation}

這個資料集的基尼不純度是 0.48。這表示資料集中存在一定程度的混亂，因為樣本分佈在兩個類別中，但不算太高（基尼不純度的最大值是 0.5，當兩個類別完全均勻時）。

再假設我們使用一個特徵進行分裂，結果將資料集 $S$ 分成兩個子集:

* 子集 $S_{1}$：包含 7 個樣本，其中 4 個屬於「好」，3 個屬於「壞」。
* 子集 $S_{2}$：包含 3 個樣本，全部屬於「好」。

現在我們要計算分裂後的加權基尼不純度。

* 子集 $S_{1}$ 的基尼不純度:
在 $S_{1}$ 中，4 個樣本屬於「好」，3 個樣本屬於「壞」。
* $p(好) = \frac{4}{7}$
* $p(壞) = \frac{3}{7}$

基尼不純度為：
\begin{equation}
Gini(S_{1}) = 1 - ((\frac{4}{7})^2 + (\frac{3}{7})^2) = 1 - (0.3265 + 0.1837) = 0.4898
\end{equation}

* 子集 $S_{2}$ 的基尼不純度:
在 $S_{2}$ 中，所有樣本都屬於「好」，因此基尼不純度為 0（資料集是純的）。
\begin{equation}
Gini(S_{2}) = 1 - ((\frac{3}{3})^2 + (0)^2) = 0
\end{equation}

分裂後的總基尼不純度是根據每個子集中樣本數所佔比例進行加權計算的。加權基尼不純度的公式為：

\begin{equation}
Gini_{split} = \frac{|S_{1}|}{|S|}Gini(S_{1}) + \frac{|S_{2}|}{|S|}Gini(S_{2})
\end{equation}

其中 $|S_{1} = 7|$ 和 $|S_{2} = 3|$ ，所以我們代入數值：
\begin{equation}
Gini_{split} = \frac{7}{10} × 0.4898 + \frac{3}{10} × 0 = 0.3429
\end{equation}

分裂後的總基尼不純度為 0.3429，這比分裂前的基尼不純度 0.48 更低，表示分裂使資料集更加純。隨機森林或決策樹演算法會選擇這樣的分裂方式，因為它有效地降低了不純度。

## 支持向量機（Support Vector Machine, SVM）

## K近鄰演算法（K-Nearest Neighbors, KNN）

## 邏輯迴歸（Logistic Regression）

## 朴素貝葉斯分類器（Naive Bayes Classifier）

## 梯度提升樹（Gradient Boosting Decision Tree, GBDT）

## XGBoost（Extreme Gradient Boosting）

## 貝葉斯網絡（Bayesian Networks）