機器學習回顧篇（7）：決策樹算法（ID3、C4.5）
- 2019 年 10 月 22 日
- 筆記
1 算法概述¶
我們每天都做着各種形形色色的決策——周末怎麼嗨、是否買下衣服、出差選哪種交通工具等等，這些決策的過程我們用圖形的形式表現出來就是一種類似樹形的結構，將這種決策思想應用到機器學習算法領域，那就是我們本文要說的決策樹算法。
決策樹算法屬於有監督學習算法的一員，在決策前需要先根據先驗數據進行學習，構建並訓練出一個決策樹模型。決策樹模型中每一個非葉子結點代表着一個特徵屬性，其下每一個分支都代表對該特徵屬性值域的不同取值劃分，每一個葉子結點代表一個輸出分類。應用模型進行決策時，從第一個非葉子結點（根節點）開始，根據特徵屬性和值選擇分支直到最後的葉子結點，最後的葉子結點所代表的分類就是最終的決策結果。
決策樹算法的本質是根據訓練數據進行學習，構建一顆最優的決策樹。之所以說最優，是因為對於同一個數據集，在不同的策略下可能構造出不一樣的決策樹。假設我們有如下一個數據集，用於判斷同事是否是程序員（純屬瞎編娛樂，請勿深究）：
我們可能構建出下面這棵樹：
也有可能構建出下面這棵樹：
甚至還有其他結構的決策樹。對於不同結構的決策樹，當然對決策的效率，甚至是準確率都是有所影響，那麼，怎麼構建一顆最優的決策樹呢？
我們知道，決策樹是一種遞歸的邏輯結構，其每一個節點都可以作為一棵樹，那麼，我們只需要做到每個節點最優，就可以保證整個決策樹最優。所以，對於構建一顆決策樹，如何選擇最優分裂特徵屬性，即從當前數據的特徵中選擇一個特徵屬性作為當前節點的劃分標準，使分裂後各子樹的樣本子集的“純度”越來越高。
在決策樹算法中，根據選擇最優分裂特徵屬性的策略不同，分為多種決策樹算法，最經典的就是ID3、C4.5、CART，本文主要ID3和C4.5兩種分類樹，CART由於其特殊性，將在下一篇博客中介紹。
2 ID3決策樹算法¶
之前說過，選擇分裂特徵屬性時，分裂後的樣本子集“純度”越高越好，對於這個純度，有一個專門的概念用於量化衡量——信息熵(entropy)。
信息熵是信息論中的概念，通常簡稱為熵，表示隨機變量不確定性或者說混亂程度。設當前樣本集合$X$包含$n$個分類，${p_i}$表示第$k$類所在的比例，則集合$X$的熵定義為：
$$Ent(X) = – sumlimits_{i = 1}^n {{p_i}} lo{g_2}{p_i}$$
$Ent(X)$的值越趨近於0，表示$D$的純度越高，越趨近於1，表示$D$的純度越低。
在ID3決策樹算法中，採用信息增益作為選擇最優分裂特徵屬性的標準。假設$A$是$X$中的一個離散型特徵屬性，包含$L$個可能取值，則根據屬性$A$對$X$進行分裂可產生$L$個分支，第$i$個分支上獲得的樣本子集記為${X_i}$，我們可以根據上式計算出每一個分支下獲得的分裂子集${X_i}$的熵，由於各子集${X_i}$的樣本數量不同，我們在熵的基礎上添加一個權重${{|{X_i}|} over {|X|}}$，也就是說，樣本子集中樣本數量越多，所佔權重越大，以特徵屬性$A$作為分裂節點後的熵為：
特徵屬性$A$的信息增益定義為：
屬性$A$的信息增益$Gain(A)越大，表示使用屬性$A$作為當前數據集的分裂節點對數據集“純度”的提升越大。ID3算法選擇最優分裂特徵屬性的策略就是每次選擇信息增益最大的一個特徵屬性最為當前數據集的分裂特徵屬性，然後對每一個分支節點的數據子集重複迭代這一策略，直到數據子集都屬於同一分類或者所有特徵屬性都已用完。
我們已上面表格中用於判斷同事是否是程序員的數據為例，通過實例感受一下ID3算法。
首先計算整個數據集的熵：
採用屬性$A$（是否穿格子襯衫）的作為分裂特徵屬性後的熵為：
那麼，屬性$A$的信息增益為：
用同樣的方法可以計算出屬性$B$（頭髮稀疏程度）和屬性$C$（近視程度）的信息增益分別為：
對比三個屬性的信息增益，顯然屬性$C$（近視程度）具有最大的信息增益，因此使用屬性$C$作為當前分裂特徵屬性。
使用屬性$C$作為當前分支節點後，每個分支產生新的數據子集，對每個子集重複上述步驟計算各特徵屬性的信息增益，選擇最優分裂特徵屬性，直到數據子集都屬於同一分類或者所有特徵屬性都已用完，整個決策樹就算構建好了。
ID3算法是經典的決策樹構建算法，結構簡單清晰、靈活方便，但存在以下不足：
（1）在選擇最優分裂特徵屬性時，偏好於多取值的特徵屬性。在選擇最優分裂特徵屬性時，某特徵屬性的取值越多，分裂後的數據子集就越多，子集中類別相對而言就可能更少，數據“純度”更高，信息增益更大，所以更有可能被選為當前分裂節點的特徵屬性。如果還不理解，那麼，我們將這種情況極端化，數據集中都有一個ID屬性，如果以ID作為分裂特徵屬性計算信息增益時，每一條數據都是一個分裂，那麼多有分裂的分裂後的熵都是0，多以信息增益一定是1，一定會被選為最優分裂特徵屬性。
（2）不能處理連續型特徵屬性。
（3）沒有樹剪枝過程，容易發生過擬合現象。
針對ID3決策樹算法的不足，有大能進行優化改進，於是就有了C4.5決策樹算法。
3 C4.5決策樹算法¶
C4.5決策樹算法是在ID3決策樹算法基礎上發展而來，所以總體而言，兩者是極其相似的。當然，既然說發展，就肯定有更進一步改進的內容。
（1）信息增益率
上文提過，ID3決策樹算法在選擇最優分裂特徵屬性時，偏好於多取值的特徵屬性，針對這一問題，C4.5決策樹算法不再以信息增益作為選擇選最優分裂特徵屬性的標準，而在選擇在信息增益基礎上更進一步計算獲得的信息增益率作為選擇最優分裂特徵屬性的標準。
在介紹信息增益率之前，還得說說“內部信息”的定義:
內部信息$Instr_inf{o_A}$用於度量屬性$A$進行分裂時分支的數量信息和尺寸信息，屬性$A$的取值數量越多，分支越多$Instr_inf{o_A}$就越大，${1 over {Instr_inf{o_A}}}$就越小，因此可以將${1 over {Instr_inf{o_A}}}$作為一個懲罰因子與信息增益相結合，於是有了信息增益率：
用信息增益率替代信息增益作為最優分裂特徵屬性的選擇標準，就可以很好的解決ID3決策樹算法在選擇最優分裂特徵屬性時，偏好於多取值的特徵屬性的問題。
（2）連續型特徵屬性處理
對於連續型特徵屬性，C4.5算法採用的策略是採用二分法將特徵屬性離散化。假設數據集$X$中屬性$A$有$n$個不同取值，我們先將其按升序排序得到集合${ {a_1},{a_2}, cdots ,{a_n}} $，將每兩個相鄰元素的中間點$t = {{{a_i} + {a_{i + 1}}} over 2}$看做潛在分裂點，於是有$n-1$個潛在的分裂點，每一個潛在分裂點都可以將數據集劃分為不大於$t$和大於$t$兩類，對每一個潛在分裂點計算信息增益，然後選擇信息增益最大的一個潛在分裂點作為當前的最優劃分點。
在計算各特徵屬性的信息增益率時，就可以用最優劃分點二分離散化之後的$A$屬性來計算信息增益率。
對於缺失值處理和樹剪枝，又是一個大話題了，可以參考這篇文檔，本文不再敘述。
