---
# System prepended metadata

title: 決策樹 (Decision Tree)
tags: [Documentation, Templates]

---

---
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) = 決策/分類結果
    → 人類可以直觀地閱讀規則並理解模型。
    ![image](https://hackmd.io/_uploads/rJj9Npz3eg.png)

    :::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 編碼背後的「機率越大 → 編碼越短」完全一致。

![image](https://hackmd.io/_uploads/r1jXZyW2ex.png)
[資料來源](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`
