---
title: 第8單元決策樹的原理
tags: 人工智慧
---
# 8-1 決策樹介紹

> 歡迎來到「決策樹」小島。島上有一個小鎮種了許多`決策樹（Decision Tree）`，每棵決策樹的核心是一個`機器學習模型`，具備著獨特的`辨識`功能。在小鎮中心有一個實驗中心，在你了解決策樹的運作之前，你有一項任務，就是到下列這兩個網站進行體驗，之後再到實驗中心實習。

## 20Q網站 http://www.20q.net/

> 這個線上AI軟體是一個可以通過20個問題來猜測你心中所想的事物，該網站提供多種不同語種版本，當然支援中文，使用方法很簡單，想象一個目標，然後 AI 程式將嘗試通過問一些簡單的問題來猜測你所想象的目標！對於所想的事物必需是大家所熟知的，不能是一個特殊的人物，地點或事情。


> 可以點help幫助你了解如何使用這個網站


> 依據20Q網站所問的問題，依序回答即可。


## akinator網站 https://cn.akinator.com/
> 這個是一個跟 20Q 網站類似的網站、APP，會問出不同的問題來猜出玩家正在想的人物或角色。

> 玩家點擊開始按鈕並想出一個著名人物或角色（音樂家、運動員、政治人物、演員、虛構影片/電視節目角色、動漫人物、網路名人等）。之後程式（即燈神）就會開始問出一系列不同的問題，玩家可以回答「是」、「否」...


> 如果在玩家回答完25道問題之前，符合條件的人物就只剩一個，程式就會詢問玩家它所猜出的這個人物是否正確。如果程式猜錯了三次，它就會請求玩家輸入角色名稱，以擴大它的資料庫。

思考一下，為什麼 20Q 跟 Akinator 網站能夠猜出你心裡所想的人物或物件呢？


Question：若有西瓜、蘋果、葡萄、葡萄柚、檸檬、香蕉、櫻桃等7 種水果，提出的問題及回答：「1.是綠色的嗎？不是。2.是黃色的嗎？不是。3.是小的嗎？是。」請猜出是指那一種水果？
- [ ] 檸檬
- [ ] 西瓜
- [ ] 蘋果
- [ ] 櫻桃
ans:D

Question:呈上題，分類水果採用的特徵有哪些？
- [ ] 顏色、形狀、大小
- [ ] 顏色、大小
- [ ] 顏色、甜度、大小
- [ ] 顏色、形狀、甜度
ans:A

#### 種魔法樹囉!

根據這些特徵，我們可以建構出決策樹，如下。

##任務：
若要將空格中填入適合的特徵，要怎麼填寫

有個資深島民種植的決策樹如下，可以提供你參考喔

如果在此決策樹中再加入柚子，那麼決策樹該如何修改呢？

# 8-2 建構決策樹

> 現在，你將前往實驗中心。這時你的手機傳來一則訊息，顯示下一個任務。如下

附件檔案為銷售紀錄，你需在抵達「Decision Tree LAB」前建構出決策樹，才可進入 LAB 中進行實作。

> 為了瞭解決策樹的運作方式，現在你要化身為島中的3C科技賣場的員工，針對消費者是否購買筆記型電腦的消費紀錄，建構出一棵決策樹。這樣我們如果拿到一個客戶資料，那麼就可以通過這個就決策樹去判斷是否買電腦。

<銷售紀錄表>

| 年紀 | 收入 | 是否為學生 | 購買筆電與否 |
| -------- | -------- | -------- | -------- |
| <=30 | 高 | 否 | 否 |
| 31...40 | 高 | 否 | 是 |
| >40 | 中 | 否 | 是 |
| >40 | 低 | 是 | 否 |
| 31...40 | 低 | 是 | 是 |
| <=30 | 中 | 否 | 是 |
| <=30 | 低 | 是 | 是 |
| <=30 | 中 | 是 | 是 |
| 31...40 | 中 | 否 | 是 |
| 31...40 | 高 | 是 | 是 |
| >40 | 中 | 是 | 否 |

> 決策樹是一種在機器學習領域中很常見的分類模型，模型的建立可透過樹狀結構分支來呈現，不斷地以條件式分支進行二元分類分割訓練資料，來決定輸出結果。

> 依據現有的資料建構出一棵決策樹，通常採「由上而下」的方式，將整群資料從某個特徵開始，根據該特徵值分為數個子群，各個子群再根據某個特徵，將子群再分為更小的子群，直到子群內的資料都是同一種類別為止。

> 決策樹中的每個節點代表某種特徵屬性，每條分支表示可能的特徵值，葉節點表示預測的類別。

### 樹的建立
剛開始所有訓練集都放在根節點，依據選定的特徵進行條件延伸分支，由上往下直到抵達葉節點，葉節點顯示最後預測的類別之機率。

### 樹的剪枝
找到包含雜訊或異常值的分支路徑，將其刪除

當有新的資料需要分類，只需將這筆新資料輸入決策樹，跟著決策樹的節點對特徵進行測試，找到一條通往葉節點的路徑，該葉節點即為分類的結果

8-3 特徵好壞決定一棵樹的高

# 特徵值選擇
你可以用列舉的方式，將每個特徵值都做分類的條件，一一去建構決策樹，再進一步分析哪一種可以有最好的。但這樣做是沒有效率的。

因此，最佳的做法是先對資料的特徵值作分析。

# 評斷特徵好壞的依據－熵(Entropy)
> 資料集C不須多做說明即可看出都屬於同一種類型，
> 資料集B則需要部份的說明來解釋資料集中不同類型的資料的意義
> 資料集A則需要最多的說明，來解釋在同一資料集中不同類型的資料間的差異
> 結論：淨度越高的資料不須過多資訊即可表示，越雜亂的資料則需要較多的資訊才能夠完整呈現資料的意義。

在資訊理論（Information Gain）中度量資訊而衍生出熵(Entropy)的概念。熵指的是計算資料的亂度。
當所有的資料是一致的，得到的熵為0。
如果分屬二類資料類型的數量各自一半時，熵為1。
熵的計算方式
Entropy = -p * log2 p – q * log2q

p：成功的機率（或true的機率）
q：失敗的機率（或false的機率

## 購買筆電與否的熵

| 購買筆電與否 | 出現次數 | 出現機率 |
| -------- | -------- | -------- |
| 是 | 7 | 7/11 |
| 否 | 4 | 4/11 |

Info(購買筆電與否) 可簡化為 Info(7,4) 參數7、4分別代表7筆友購買筆電及4筆沒有購買筆電的資料
Entropy
= I(7,4)
= -(7/11) * log2 (7/11) – (4/11) * log2(4/11)
= 0.425 + 0.531
= 0.956

## 在「收入」這個特徵值下「購買筆電與否」的熵

| 收入| 購買筆電| 未購買筆電|
| -- | ------ | ------- |
| 高 | 2 | 1 |
| 中 | 3 | 2 |
| 低 | 2 | 1 |

Info 收入 (原始資料)
= Info 收入高 + Info 收入中 +Info 收入低
= (3/11) * I(2,1) + (5/11) * I(3,2) + (3/11) * I(1,1)
= (3/11) * (-(2/3) * log2 (2/3) – (1/3) * log2(1/3)) <br>+ (5/11) * (-(3/5) * log2 (3/5) – (2/5) * log2(2/5)) <br>+ (3/11) * (-(2/3) * log2 (2/3) – (1/3) * log2(1/3))
= 0.250 + 0.441 + 0.250
= 0.941

## 在「年紀」這個特徵值下「購買筆電與否」的熵

| 年紀 | 購買筆電| 未購買筆電|
| ------- | ------ | ------- |
| <=30 | 2 | 2 |
| 30...40 | 4 | 0 |
| >40 | 1 | 2 |

Info 年紀 (原始資料)
= Info 年紀<=30 + Info 年紀30~40 +Info 年紀>40
= 4/11 * I(2,2) + 4/11 * I(4,0) + 3/11 * I (1,2)
= 4/11 * (-(2/4) * log2(2/4) - (2/4) * log2(2/4)) <br>+ 4/11 * (-(4/4) * log2(4/4) - (0/4) * log2(0/4)) <br> + 3/11 * (-(1/3) * log2(1/3) - (2/3) * log2(2/3))
= 0.364 + 0 + 0.250
= 0.614

## 「是否為學生」這個特徵值下「購買筆電與否」的熵

| 學生 | 購買筆電| 未購買筆電|
| --- | ------ | ------- |
| 是 | 4 | 1 |
| 否 | 3 | 3 |

Info 學生 (原始資料)
= Info 是學生 + Info 不是學生
= 5/11 * I(4,1) + 6/11 * I(3,3)
= 5/11 * (-(4/5) * log2(4/5) - (1/5) * log2(1/5)) <br>+ 6/11 * (-(3/6) * log2(3/6) - (3/6) * log2(3/6))
= 0.084 + 0.545
= 0.953

經過計算，得到各個熵
是否買筆電的熵 = 0.956
在「收入」這個特徵值下「購買筆電與否」的熵 = 0.941
在「年紀」這個特徵值下「購買筆電與否」的熵 = 0.614
「是否為學生」這個特徵值下「購買筆電與否」的熵 = 0.953

# 資訊獲利
計算完熵，便可利用其計算結果來探討「資訊獲利」(Information Gain)，資訊獲利就是來衡量特徵值於分類資料的能力。
特徵值「收入」的資訊獲利 = 0.956 - 0.945 = 0.015
特徵值「年紀」的資訊獲利 = 0.956 - 0.614 = 0.342
特徵值「是否為學生」的資訊獲利 = 0.956 - 0.953 = 0.003
資訊獲利值越大，表示使用此特徵作為判斷條件，可帶來較佳的分類結果。
因此這個例子優先選擇「年紀」這個特徵

年紀<=30
| 年紀 | 收入 | 是否為學生 | 購買筆電與否 |
| -------- | -------- | -------- | -------- |
| <=30 | 高 | 否 | 否 |
| <=30 | 中 | 否 | 是 |
| <=30 | 低 | 是 | 是 |
| <=30 | 中 | 是 | 是 |

年紀介於31至40
| 年紀 | 收入 | 是否為學生 | 購買筆電與否 |
| -------- | -------- | -------- | -------- |
| 31...40 | 高 | 否 | 是 |
| 31...40 | 低 | 是 | 是 |
| 31...40 | 中 | 否 | 是 |
| 31...40 | 高 | 是 | 是 |

年紀>40
| 年紀 | 收入 | 是否為學生 | 購買筆電與否 |
| -------- | -------- | -------- | -------- |
| >40 | 中 | 否 | 是 |
| >40 | 低 | 是 | 否 |
| >40 | 中 | 是 | 否 |

建構決策樹

----
## 在特徵值「年紀<=30」中「購買筆電與否」的熵

| 購買筆電與否 | 出現次數 | 出現機率 |
| -------- | -------- | -------- |
| 是 | 2 | 2/4 |
| 否 | 2 | 2/4 |

= I(2,2)
= -(2/4) * log2 (2/4) – (2/4) * log2(2/4)
= 0.5 + 0.5
= 1

## 細看「年紀<=30」中「收入」這個特徵值下「購買筆電與否」的熵

| 收入| 購買筆電| 未購買筆電|
| -- | ------ | ------- |
| 高 | 0 | 1 |
| 中 | 1 | 1 |
| 低 | 1 | 0 |

Info 收入 (原始資料)
= Info 收入高 + Info 收入中 +Info 收入低
= (1/4) * I(0,1) + (2/4) * I(1,1) + (1/4) * I(1,0)
= (1/4) * (-(0/1) * log2 (0/1) – (1/1) * log2(1/1)) <br>+ (2/4) * (-(1/2) * log2 (1/2) – (1/2) * log2(1/2)) <br>+ (1/4) * (-(1/1) * log2 (1/1) – (0/1) * log2(0/1))
= 0 + 0.5 + 0
= 0.5

## 細看「年紀<=30」中「是否為學生」這個特徵值下「購買筆電與否」的熵

| 學生 | 購買筆電| 未購買筆電|
| --- | ------ | ------- |
| 是 | 2 | 0 |
| 否 | 0 | 2 |

Info 學生 (原始資料)
= Info 是學生 + Info 不是學生
= 2/4 * I(2,0) + 2/4 * I(0,2)
= 2/4 * (-(2/2) * log2(2/2) - (0/2) * log2(0/2)) <br>+ 2/4 * (-(0/2) * log2(0/2) - (2/2) * log2(2/2))
= 0 + 0
= 0

經過計算，在「年紀<=30」的4筆資料中
「收入」的資訊獲利= 1 - 0.5 = 0.5
「是否為學生」的資訊獲利= 1 - 0 = 1
所以下一支點將以「是否為學生」為判斷條件


年紀<=30且不是學生
| 年紀 | 收入 | 是否為學生 | 購買筆電與否 |
| -------- | -------- | -------- | -------- |
| <=30 | 高 | 否 | 否 |
| <=30 | 中 | 否 | 是 |

年紀<=30且是學生
| 年紀 | 收入 | 是否為學生 | 購買筆電與否 |
| -------- | -------- | -------- | -------- |
| <=30 | 低 | 是 | 是 |
| <=30 | 中 | 是 | 是 |

----
## 在特徵值「年紀30...40」中「購買筆電與否」的熵

最後生成的決策樹

https://youtu.be/C3CAkJJbBJA