Decision tree （決策樹）

12 Decision tree (決策樹)

決策樹可用於分類，亦可用於回歸，是依給定實例的特徵（或稱屬性, attributes) 設定條件判斷實例是否滿足來進行分類，就如果常見的機智問答節目中，參賽者提問是否滿足某條件？主持人僅能回答 Yes or No，參賽者再依回答縮小思考範圍，再提問另一問題，並依回答再度小思考範圍，依此進行提問，最後終於把答案猜出。例如猜動物，參賽者可先問是不是地上行走的，如回答是，可再提問是不是有4隻腳等。決策樹的演算法是依所給定的訓練資料的特徵，依據原則選定特徵，逐步一一歸納，並建立分類所需的樹狀圖，圖形建立完成後，樹狀圖就等同於線性分類時依訓練結果所得的斜率及截距所建的直線，可用於對測試資料進行分類。

 一般是以二元樹來當決策樹，在二元樹中，每個節點代表提問者所提的一個問題，最高層的節點稱為根節點(Root node)，根節點再依問題的滿足與否分裂 (split)成左右兩個子節點，如左子節點可代表Yes 而右子節點代表No，亦即左節點僅含滿足此問題的實例，而右節點是不滿足的實例。這些左及右的子節點可依需要再度依問題分裂出所屬的左及右子節點，依此進行逐層分裂。若分裂後節點的實例僅含單一類別，則此節點就不再行分裂，這種節點稱為葉節點 (Leaf node)，演算法是依給定的特徵逐一過濾，於所有節點都是葉節點後結束。選擇時特徵可先計算節點所含實例中的資訊量、依各特徵分裂後子節點的平均資訊量，並計算其差值，此差稱資訊增益 (Information gain)。計算後選取具最大資訊增益的特徵進行分裂，並於分裂後的各子節點依此程序進行，直至全部節點都是葉節點。

∎ 熵(Entropy)、資訊增益 (Information gain, IG)
有各種不同的資訊量計算方式 ，熵(Entropy) 是一種很常見的資訊量的定義，常用於資訊理論(Information theory)的領域。資訊量代表不確定性 (Uncertainty) ，不確定性愈高，資訊量就愈大。對於某一有$n$個出象(outcome) 試驗$X$，資訊量的定義是
$H(x)=-\sum_{i=1}^{n}p(x_i)\log _2p(x_i)$
其中因為機率值會小於1，取對數後為負，所以定義中加上一個負號使定義值為正。例如丟一個公正的銅板，正反兩面出現的機率都是$1/2$，所以熵為
$H(x)=-\frac{1}{2}\log _2\frac{1}{2}-\frac{1}{2}\log _2\frac{1}{2}=1$
如果銅板不是公正的，出現正反面的機率分別是0.8 和 0.2，則

import math
x=[0.8,0.2]
def entropy(x):
    hx = 0
    for i in range(len(x)):
        hx = hx + x[i]*math.log(x[i],2)
    return -hx
a = entropy(x)
print(a)

0.7219280948873623
可見非公正的銅板的熵比公正銅板小，這是因為試驗中若都是猜正面，則有0.8的機率會猜中，表示不確定性減少 了，所以熵也要減少 。熵的單位為位元，表示具有多少位元的資訊，在公正銅板的試驗中，1就是表示一個位元的資訊量。若把上列程式第二行改成x=[0.25,0.25,0.25,0.25]，則輸出是2.0，表示4個等機率的出象其熵是2，這說明在試驗中若所有出象的機率是相同，則隨機性最大，熵也就最大。在二元分類中，若某節點只剩下一種類別，則其熵為 0，也就不必再分裂了。

在二元分類中，某一節點某一類別出現的機率就是該類別的數目除節點中實例的總數。資訊增益 ($IG$) 的定義是父節點的熵減去左$ (l) $右$ (r) $子節點平均熵數，
$IG(x)=H(x)-p(c_l)H(c_l)-p(c_r)H(c_r)$
其中$H(c_i)$表示子節點 $i$ 的熵，$p(c_i)$表示子節點 $i$ 的機率，是父節點的實例數目除該子節點的實例數目。因依據不同特徵分裂後，子節點所含的實例會不同，所以其熵值也會不同。

∎ 二元數實例
我們以文獻裡的一組資料來說明如何建立二元樹

實例	Play fetch	Is grumpy	Favorite food	Species
1	Yes	No	Bacon	Dog
2	No	Yes	Dog food	Dog
3	No	Yes	Cat food	Cat
4	No	Yes	Bacon	Cat
5	No	No	Cat food	Cat
6	No	Yes	Bacon	Cat
7	No	Yes	Cat food	Cat
8	No	No	Dog food	Dog
9	No	Yes	Cat food	Cat
10	Yes	No	Dog food	Dog
11	Yes	No	Bacon	Dog
12	No	No	Cat food	Cat
13	Yes	Yes	Cat food	Cat
14	Yes	Yes	Bacon	Dog

其中共有14 個實例，6 貓 8 狗，特徵（或稱屬性）Play fetch （玩你丟我撿）、Is grumpy （壞脾氣）、Favorite food （喜好位物，有狗食、貓食、培根）三種，最後的Label 是 Species（種類）。此例要根據所給的資料建立二元樹用以分類貓和狗這兩種動物。

以下我們以Iterative Dichotomiser 3(ID3)演算法來建立二元樹，首先計算根節的熵以及決定一開始要選用的特徵，所以必需針每一特徵求其子節點的熵，並計算IG，之後選取具有最大IG的特徵。計算Play fetch如下

Play fetch

因此特徵是個 Yes or No的問題，以1表示 Yes, 0表示 No，第一個方塊代表根節點，提的問題play fetch 是否小於等於0.5，如果回答Yes的話表示訓練集裡不玩你丟我撿的實例，若回答是No 則要選到那些要玩的實例。根節點中還有列山entropy 是0.9852，而 samples （樣本）就是表示實例的數目，此節點是一原始的14個。在左側的子節點中，樣本有9個，其中7個cats, 2個dogs以向量value = [7. 2.]表示，所以向量第一個數值代表 cat，第二個代dog （以下都相同）。可以依以上數據求出此點的entropy，如圖中所示的0.7642，此節點的機率是9/14。右子節點是do play fetch 的實例，共有5個樣本，其中有 1 cat, 4 dogs，可算出此節點的熵是0.7219，另外也此點的機率是5/14。由以上資訊我們可以求出選play fetch特徵的IG是

$IG = 0.9852-\frac{9}{14}\times 0.7642-\frac{5}{14}\times 0.7219=0.2361$

以下Is grumpy?的資訊量

Is grumpy

由類似的計算，我們可以求出選此特徵的IG

$IG = 0.9852-\frac{6}{14}\times 0.9183-\frac{8}{14}\times 0.8113=0.128$

再看若選cat food <=0.5,

cat food

由類似的計算，我們可以求出選此特徵的IG

$IG = 0.9852-\frac{8}{14}\times 0.8113-\frac{6}{14}\times 0.0=0.5216$

因有三種food，所以我們還必需求選dog food<=0.5的IG，此情況是0.3210，另bacon<=的IG是0.0481，所以共有5個IG值，我們選取最大的當為我們根節點分裂所依據的特徵，所以就選cat food<=0.5。

開始後就上述演算法計算樹狀節點的資訊量並逐層分裂，最終得下圖

樹狀節點圖

到最終節點8和9時，8只有 cat 而9只有dog，所以都不必再分裂了，演算法就結束了。我們以下列測試集進行測試

實例	Play fetch	Is grumpy	Favorite food	Species
1	Yes	No	Bacon	Dog
2	Yes	Yes	Dog food	Dog
3	No	Yes	Dog food	Cat
4	No	Yes	Bacon	Cat
5	No	No	Cat food	Cat

測試集實例 1的favorite food是bacon，所代入節點1進到節點2，因此實例是not grumpy 所代入節點2後會進入節點4，此節點是單一類dog，所以此實例就判定為dog。依相似的方法，可對測試的實例進行分類。將結果表示如下
測試實例 1：$1\rightarrow 2\rightarrow4 \mbox{ dog}$
測試實例 2：$1\rightarrow 2\rightarrow 5\rightarrow 6 \mbox{ dog}$
測試實例 3：$1\rightarrow 2\rightarrow 5\rightarrow 6 \mbox{ dog}$
測試實例 4：$1\rightarrow 2\rightarrow 5\rightarrow 7 \rightarrow 8 \mbox{ cat}$
測試實例 5：$1\rightarrow 3 \mbox{ cat}$

結果顯示 實例3是錯的，其他都正確。

參考文獻
Gavin Hackeling, Mastering Machine Learning with scikit-learn, 2nd, Packt Publishing, 2017