---
title: '決策樹 (Decision Tree)'
disqus: hackmd
---
決策樹 (Decision Tree)
===
## Table of Contents
[TOC]
## 簡介
決策樹 (Decision Tree,DT) 是機器學習中最簡單、同時也是最成功的一類演算法。
它的核心思想是 **「Divide and Conquer+Greedy」** —— 不斷將資料依照某個特徵切分成更小的子集合，直到子集合足夠純粹（大部分樣本屬於同一類別），或無法再分裂為止。
:::success
**Greedy（貪婪式策略）**：
* 每次分裂(執行)只考慮「當下最佳」的結果，而不是整體最優解。
* 好處：速度快、實作簡單。
* 限制：可能導致**局部最優**，不一定是全域最佳解。
單一決策樹**沒辦法完全避免**局部最優，因為：
搜尋整體最優解需要窮舉所有可能分裂方式 → 計算成本太高。
所以大部分演算法（ID3, C4.5, CART，下面會介紹）都選擇用貪婪策略來「取一個合理的近似解」。
:::
---
### 主要特點
* **可解釋性 (Interpretability)**
決策樹其實很像在玩「**二十個問題遊戲**」，每次只問一個問題（例如：**年齡大於 30 嗎？**），然後根據答案把資料往不同的方向走，最後走到葉子節點，就得到最終的分類或預測：
* 節點 (node) = 條件判斷
* 邊 (branch) = 條件的結果
* 葉節點 (leaf) = 決策/分類結果
→ 人類可以直觀地閱讀規則並理解模型。
:::info
決策樹就像一堆 `if-else` 規則，樹狀結構清清楚楚，別人看了也能理解模型的判斷依據。
:::
* **輸入與輸出**
* 輸入：一組特徵值（例如：年齡、收入、是否有車）
* 輸出：一個決策（例如：批准貸款 / 不批准貸款）
* 最簡單的情況：是/否（二元分類）
* **分裂依據**
* 通常根據單一特徵（attribute）進行分裂
* 目標是讓子集合越來越「乾淨」 → 大部分樣本屬於同一類別
* **什麼時候適合用？**
* 資料需要規則化表示（如醫療診斷、風險判斷）
* 需要模型能被人類看懂（不像深度學習是黑箱）
* 適合做 **分類**（是/否、多類別）和 **回歸**（數值預測）
先備數學概念
---
### 資訊量 (Information Content, Self-Information)
資訊量用來衡量「一個事件發生時，帶來多少新資訊」(單位一般用bit，電腦紀錄單位本來就是bit)，資訊理論之父克勞德‧艾爾伍德‧香農(Claude Elwood Shannon )對資訊量的定義。
對於事件 $x$，其發生機率為 $p(x)$，則資訊量定義為：
$$
I(x) = -\log_b p(x)
$$
* $p(x)$：事件 $x$ 發生的機率
* $b$：對數的底
:::success
* $b=2$ → 單位是 **bit**（binary digit，香農聽從 J. W. Tukey 建議創造出來的字）
* $b=10$ → 單位是 **digit**
* $b=e$ → 單位是 **nat**（自然單位）
:::
#### 黑箱例子：蘋果與橘子
#### 1. 初始狀態（抽之前）
黑箱總共有 10 個水果：
* 蘋果機率：$p=0.2$
* 橘子機率：$p=0.8$
這是我們一開始對隨機過程的認知。
#### 2. 抽到蘋果之後
抽出 1 個蘋果後，剩下：
* 蘋果：1
* 橘子：8
* 總數：9
新的機率：
* 蘋果：$1/9 \approx 0.11$
* 橘子：$8/9 \approx 0.89$
👉 **變化解釋**：
* 原本蘋果是 20%，現在剩 11% → 代表「蘋果更稀有了」
* 這讓我們更「驚訝」於剛剛竟然抽到了一個機率較小的事件
* 因此：抽到蘋果的資訊量比較大。
#### 3. 抽到橘子之後
抽出 1 個橘子後，剩下：
* 蘋果：2
* 橘子：7
* 總數：9
新的機率：
* 蘋果：$2/9 \approx 0.22$
* 橘子：$7/9 \approx 0.78$
👉 **變化解釋**：
* 橘子原本 80%，現在還有 78% → 幾乎沒什麼改變
* 所以「抽到橘子」這件事幾乎在預期之內，不怎麼改變我們對黑箱的理解
* 因此：抽到橘子的資訊量很小。
#### 4. 關鍵洞察
* **資訊量大**：表示「事件的發生強烈改變了我們對世界的認知（機率分布）」。
* **資訊量小**：表示「事件幾乎在意料之中，對後續分布幾乎沒什麼改變」。
這就是「越小機率的事件 → 資訊量越大；越常見的事件 → 資訊量越小」的直觀數學化。
:::info
#### 實際例子:摩斯密碼與機率的關係
設計背景：摩斯密碼是在 1830–1840 年代，由 Samuel Morse 和 Alfred Vail 設計。
依據：參考了英文信件裡字母的出現頻率統計（Alfred Vail 當時看報紙文章數字統計）。
結果：
* 出現最頻繁的字母 E → 一個點 ·（最短）
* 出現次多的 T → 一個劃 –
* 比較少見的字母（例如 Q、Z） → 用 4 個符號（例如 --.-, --..）
這樣的分配讓摩斯電碼在平均傳輸時間上比較高效。
摩斯密碼的設計確實依照字母出現機率來分配長短，和 Shannon 熵、Huffman 編碼背後的「機率越大 → 編碼越短」完全一致。
[資料來源](https://www.101computing.net/morse-code-using-a-binary-tree/)
:::
### 熵 (Entropy)
在前一節，我們提到 **資訊量 (Information Content, Self-Information)**：
$$
I(x) = -\log_b p(x)
$$
它描述的是 **單一事件** 的驚喜程度。
但是在現實中，我們通常面對的不是單一事件，而是一個隨機變數 $X$，它可能有多種結果（例如：郵件可能是垃圾信、商務信、私人信）。
這時候我們想問：
> **平均而言，這個隨機過程會帶來多少資訊量？**
#### 熵的定義
Shannon 在 1948 年資訊理論中提出，用「熵」來表示 **平均資訊量**：
$$
H(X) = -\sum_{i=1}^n p(x_i) \log_b p(x_i)
$$
* $p(x_i)$：事件 $x_i$ 的機率
* $n$：可能的事件數
* $b$：對數的底（常用 $b=2$，單位是 bit）
:::success
熵其實就是「資訊量的期望值 (Expectation)」(或平均、average的概念)。
:::
* 如果事件結果幾乎確定（例如 $p=0.99$ vs $0.01$），熵很低（接近 0 bit）。
* 如果事件結果非常均勻（例如丟公平骰子，每面 $p=1/6$），熵最高（最模糊、最難預測）。
### 資訊增益 (Information Gain)
#### 為什麼需要資訊增益？
決策樹的建構核心問題是：
>**每次要選哪個特徵來切分資料？**
* 如果隨便挑一個特徵，可能切完後子集合還是很「混亂」，分類沒幫助。
* 我們需要一個「指標」來衡量：
* **切分前有多混亂**（用熵 $H(S)$ 測量）
* **切分後子集合是否更乾淨**（再算子集合的熵，做加權平均）
#### 正式定義
假設我們有一個資料集 $S$，要預測目標類別（例如「打球 / 不打球」）。
某個特徵 $A$ 可以把 $S$ 分成幾個子集，資訊增益的定義是：
$$
IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} \, H(S_v)
$$
逐一拆解：
* **$H(S)$**：整體資料集 $S$ 的熵
* 代表「在不知道任何特徵的情況下，分類有多模糊」
* **$Values(A)$**：特徵 $A$ 的所有可能取值
* 例如「天氣」特徵的可能值 = {晴天、陰天、雨天}
* **$S_v$**：子資料集
* 只包含特徵 $A = v$ 的樣本
* 例如「天氣=晴天」這一群樣本
* **$\frac{|S_v|}{|S|}$**：子資料集的比例
* 有些取值可能樣本很多，有些很少 → 所以要加權
* **$H(S_v)$**：子資料集的熵
* 表示「在知道特徵 A = v 的前提下，這群資料的混亂程度」
演算法流程
---
```sequence
Alice->Bob: Hello Bob, how are you?
Note right of Bob: Bob thinks
Bob-->Alice: I am good thanks!
Note left of Alice: Alice responds
Alice->Bob: Where have you been?
```
> Read more about sequence-diagrams here: http://bramp.github.io/js-sequence-diagrams/
模型可解釋性
---
```mermaid
gantt
title A Gantt Diagram
section Section
A task :a1, 2014-01-01, 30d
Another task :after a1 , 20d
section Another
Task in sec :2014-01-12 , 12d
anther task : 24d
```
> Read more about mermaid here: http://mermaid-js.github.io/mermaid/
## 特徵重要性 (Feature Importance)
:::info
**Find this document incomplete?** Leave a comment!
:::
###### tags: `Templates` `Documentation`
Sign in with Wallet
Connect another wallet