<style></style> <style></style> <style></style> <style></style>
注：本系列所有博客將持續更新并發布在github上，您可以通過github下載本系列所有文章筆記檔案，
1 演算法概述¶
我們每天都做著各種形形色色的決策——周末怎么嗨、是否買下衣服、出差選哪種交通工具等等，這些決策的程序我們用圖形的形式表現出來就是一種類似樹形的結構，將這種決策思想應用到機器學習演算法領域，那就是我們本文要說的決策樹演算法，
決策樹演算法屬于有監督學習演算法的一員，在決策前需要先根據先驗資料進行學習，構建并訓練出一個決策樹模型，決策樹模型中每一個非葉子結點代表著一個特征屬性，其下每一個分支都代表對該特征屬性值域的不同取值劃分，每一個葉子結點代表一個輸出分類，應用模型進行決策時，從第一個非葉子結點（根節點）開始，根據特征屬性和值選擇分支直到最后的葉子結點，最后的葉子結點所代表的分類就是最終的決策結果，
決策樹演算法的本質是根據訓練資料進行學習，構建一顆最優的決策樹，之所以說最優，是因為對于同一個資料集，在不同的策略下可能構造出不一樣的決策樹，假設我們有如下一個資料集，用于判斷同事是否是程式員（純屬瞎編娛樂，請勿深究）：
我們可能構建出下面這棵樹：
也有可能構建出下面這棵樹：
甚至還有其他結構的決策樹，對于不同結構的決策樹，當然對決策的效率，甚至是準確率都是有所影響，那么，怎么構建一顆最優的決策樹呢？
我們知道，決策樹是一種遞回的邏輯結構，其每一個節點都可以作為一棵樹，那么，我們只需要做到每個節點最優，就可以保證整個決策樹最優，所以，對于構建一顆決策樹，如何選擇最優分裂特征屬性，即從當前資料的特征中選擇一個特征屬性作為當前節點的劃分標準，使分裂后各子樹的樣本子集的“純度”越來越高，
在決策樹演算法中，根據選擇最優分裂特征屬性的策略不同，分為多種決策樹演算法，最經典的就是ID3、C4.5、CART，本文主要ID3和C4.5兩種分類樹，CART由于其特殊性，將在下一篇博客中介紹，
2 ID3決策樹演算法¶
之前說過，選擇分裂特征屬性時，分裂后的樣本子集“純度”越高越好，對于這個純度，有一個專門的概念用于量化衡量——資訊熵(entropy)，
資訊熵是資訊論中的概念，通常簡稱為熵，表示隨機變數不確定性或者說混亂程度，設當前樣本集合$X$包含$n$個分類，${p_i}$表示第$k$類所在的比例，則集合$X$的熵定義為：
$$Ent(X) = - \sum\limits_{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$作為分裂節點后的熵為：
$$En{t_A}(X) = - \sum\limits_{i = 1}^L {{{|{X_i}|} \over {|X|}}Ent({X_i})} $$特征屬性$A$的資訊增益定義為：
$$Gain(A) = Ent(X) - En{t_A}(X)$$屬性$A$的資訊增益$Gain(A)$越大，表示使用屬性$A$作為當前資料集的分裂節點對資料集“純度”的提升越大，ID3演算法選擇最優分裂特征屬性的策略就是每次選擇資訊增益最大的一個特征屬性最為當前資料集的分裂特征屬性，然后對每一個分支節點的資料子集重復迭代這一策略，直到資料子集都屬于同一分類或者所有特征屬性都已用完，
我們已上面表格中用于判斷同事是否是程式員的資料為例，通過實體感受一下ID3演算法，
首先計算整個資料集的熵：
$$Ent(X) = - ({7 \over {10}} \times lo{g_2}{7 \over {10}} + {3 \over {10}} \times lo{g_2}{3 \over {10}}) = 0.88129$$采用屬性$A$（是否穿格子襯衫）的作為分裂特征屬性后的熵為：
$$En{t_A}(X) = - \{ {5 \over {10}} \times ({4 \over 5} \times lo{g_2}{4 \over 5} + {1 \over 5} \times lo{g_2}{1 \over 5}){\rm{ + }}{5 \over {10}} \times ({3 \over 5} \times lo{g_2}{3 \over 5} + {2 \over 5} \times lo{g_2}{2 \over 5})\} = 0.84645$$那么，屬性$A$的資訊增益為：
$$Gain(A) = 0.88129 - 0.84645 = 0.034840$$用同樣的方法可以計算出屬性$B$（頭發稀疏程度）和屬性$C$（近視程度）的資訊增益分別為：
$$En{t_B}(X) = - \{ {3 \over {10}} \times ({2 \over 3} \times lo{g_2}{2 \over 3}{\rm{ + }}{1 \over 3} \times lo{g_2}{1 \over 3}) + {4 \over {10}} \times ({4 \over 4} \times lo{g_2}{4 \over 4}{\rm{ + }}0){\rm{ + }}{3 \over {10}} \times ({1 \over 3} \times lo{g_2}{1 \over 3}{\rm{ + }}{2 \over 3} \times lo{g_2}{2 \over 3})\} = 0.612197$$ $$Gain(B) = 0.88129 - 0.61220 = 0.269093$$ $$En{t_C}(X) = - \{ {3 \over {10}} \times ({3 \over 3} \times lo{g_2}{3 \over 3}{\rm{ + }}0) + {4 \over {10}} \times ({3 \over 4} \times lo{g_2}{3 \over 4}{\rm{ + }}{1 \over 4} \times lo{g_2}{1 \over 4}){\rm{ + }}{3 \over {10}} \times ({1 \over 3} \times lo{g_2}{1 \over 3}{\rm{ + }}{2 \over 3} \times lo{g_2}{2 \over 3})\} = 0.6$$ $$Gain(C) = 0.88129 - 0.6 = 0.28129$$對比三個屬性的資訊增益，顯然屬性$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} = - \sum\limits_{i = 1}^L {{{|{X_i}|} \over {|X|}}} lo{g_2}({{|{X_i}|} \over {|X|}})$$內部資訊$Instr\_inf{o_A}$用于度量屬性$A$進行分裂時分支的數量資訊和尺寸資訊，屬性$A$的取值數量越多，分支越多$Instr\_inf{o_A}$就越大，${1 \over {Instr\_inf{o_A}}}$就越小，因此可以將${1 \over {Instr\_inf{o_A}}}$作為一個懲罰因子與資訊增益相結合，于是有了資訊增益率：
$$Gain\_ratio(A) = {{Gain(A)} \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$屬性來計算資訊增益率，
對于缺失值處理和樹剪枝，又是一個大話題了，可以參考這篇檔案，本文不再敘述，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67685.html
標籤：其他