決策樹(Decision Tree)常見的三種算法(ID3、C4.5、CART)

決策樹作為一種常見的分類模型，首先要先知道怎麼分這些節點，哪個節點適合作為起始根部，節點的判斷依據及數值的認定為何，此時就會利用到所謂的決策樹算法，例如ID3、C4.5、CART，他們可以將特徵值量化，自動建構並決定決策樹的每個節點。

ID3

訊息熵表示的是所有樣本中各種類別出現的不確定性之和，熵越大代表不確定性就越大

(1) 計算數據及D的經驗熵(entropy)H(D)

(2) 計算特徵A對數據集D的條件熵H(D|A)

(3) 計算訊息增益

C4.5

選擇訊息增益率來對ID3做改進

CART（Classification and Regression tree）

和熵一樣越大代表不確定性就越大

範例:

ID3:
(1)
H(D) = -9/14*log2(9/14)-5/14*log2(5/14)=0.94
(2)計算每一個feature的訊息熵
H(D|天氣)=5/14[-2/5*log2(2/5)-3/5*log2(3/5)]+4/14[-4/4*log2(4/4)]
+5/14[-3/5*log2(3/5)-2/5log2(2/5)]=0.694
H(D|溫度)=4/14[-2/4*log2(2/4)-2/4*log2(2/4)]
+6/14[-4/6*log2(4/6)-2/6*log2(2/6)]+4/14[-3/4*log2(3/4)-1/4log2(1/4)]=0.911
(3) 計算訊息增益
g(天氣)=H(D)-H(D|天氣)=0.94–0.694=0.246
g(溫度)=H(D)-H(D|溫度)=0.94–0.911=0.029
選擇息增益最大的天氣作為第一個節點

C4.5:
(1)計算feature的分裂訊息
H(天氣) = -5/14*log2(5/14)-5/14*log2(5/14)-4/14*log2(4/14)=1.577
H(溫度) = -4/14*log2(4/14)-6/14*log2(6/14)-4/14*log2(4/14)=1.556
(2)計算訊息增益量
IGR(天氣)=0.246/1.577=0.155
IGR(溫度)=0.029/1.556=0.0186
選擇息增益率最大的天氣作為第一個節點

CART:
(1)
Gini(D) = 1-[(9/14)²+(5/9)²]=0.541
Gini(天氣|進行)=1-[(2/9)²+(4/9)²+(3/9)²]=0.642
Gini(天氣|取消)=1-[(3/5)²+(2/5)²]=0.48
Ginigain(天氣)=0.541-(9/14*0.642+5/14*0.48)=-0.043
Gini(溫度|進行)=1-[(2/9)²+(4/9)²+(3/9)²]=0.642
Gini(溫度|取消)=1-[(2/5)²+(1/5)²+(2/5)²]=0.64
Ginigain(溫度)=0.541-(9/14*0.642+5/14*0.64)=-0.1
選擇gini最大的溫度作為第一個節點

決策樹學習的常見問題

不過決策樹很容易有「Overfitting（過度擬合）」的問題，因為我們如果沒有對樹的成長作限制，演算法最後就會為每個不同特徵值創建新的分類節點，最後將所有資料作到100%正確的分類，因此為了預防Overfitting，我們會採取下列兩種方式：設限及剪枝。

設限
1. Minimum samples for a node split：資料數目不得小於多少才能再產生新節點。
2. Minimum samples for a terminal node (leaf)：要成為葉節點，最少需要多少資料。
3. Maximum depth of tree (vertical depth)：限制樹的高度最多幾層。
4. Maximum number of terminal nodes：限制最終葉節點的數目
5. Maximum features to consider for split：在分離節點時，最多考慮幾種特徵值。