如同上幾篇我們探讨的SVM一樣，決策樹算法既可以處理分類問題（二分類和多分類），又可以處理回歸問題。同時，決策樹也廣泛的運用在內建算法中，比如随機森林算法。本篇我們沿着決策樹算法的發展，來探讨下決策樹ID3算法和C4.5算法。CART算法決策樹我們下篇單獨再探讨。
1）來自借錢的思考
決策樹的原理其實很簡單，我們生活中已經在運用這些原理。比如，某一個朋友向你借錢，在你心裡一定會有一系列的決策，最後決定是否借錢給他，把你的決策畫成一顆樹狀結構就是決策樹了。比如我的借錢決策：
從上圖我們先來認識下決策樹的基本結構，決策樹由節點（矩形和橢圓）和有向的邊（箭頭）組成，節點按所處在決策樹的位置可以分為根節點，中間節點和葉子節點。其中每個節點代表一個屬性，每個分支代表一個決策（規則），每個葉子代表一個結果（分類值或連續值）。
再回到借錢的栗子上來。假如按照上面的決策樹進行借錢決策，一共外借了4次錢，結果有2次按時還了錢，另外2次借的錢打水漂了，損失有點大。于是我調整了下政策，把是否有工作放在首要位置（跟節點）。決策樹的結構如下：
于是我又外借了4次錢，結果有3次按時還了錢，隻有1次外借的錢打了水漂。對比第一種政策，不還錢的次數減少了，也可以說打水漂的不确定性減少了。是以，隻要不确定性有所降低，我們的決策樹就有所優化。那麼，不确定性又該怎麼去度量呢？幸運的是，早在1948年克勞德·愛爾伍德·香農提出了資訊熵的概念，專門用來描述事物的不确定性。
2）資訊熵（Information Entropy）
資訊熵，它是表示對随機變量不确定的度量，不确定性越大，資訊熵越大。随機變量 x x x的資訊熵的表達式如下(資訊熵表達式的由來可參考本篇部落格資訊熵部分)：
H ( x ) = − ∑ x p ( x ) l o g ( p ( x ) ) = − ∑ i = 1 n p ( x i ) l o g p ( x i ) H(x) = -\sum_{x}p(x)log(p(x))=-\sum_{i=1}^{n}p(x_i)logp(x_i) H(x)=−∑xp(x)log(p(x))=−∑i=1np(xi)logp(xi)
從表達式中可以看出，随機變量的取值個數越多，狀态數也就越多，資訊熵就越大，混亂程度就越大。當随機分布為均勻分布時，資訊熵最大。
再讓我們回到栗子中來。隻要不确定性減少，決策政策就得到了優化。是以我們在進行特征選擇時，可以選擇目前不确定性減少最多的特征（貪心法）。那麼該怎麼去定義不确定性的減少呢？ID3算法使用資訊增益，C4.5使用資訊增益率，CART樹使用Gini系數。
3）ID3算法
ID3算法是用資訊增益來定義不确定性的減少程度，選擇資訊增益最大的特征來建立決策樹的目前節點。特征A對訓練集D的資訊增益 g ( D , A ) g(D,A) g(D,A)表達式如下：
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)
資訊增益具體的算法過程：
輸入：訓練資料集D合特征A；
輸出：特征A對訓練資料集D的資訊增益 g ( D , A ) g(D,A) g(D,A)
a)計算資料D的資訊熵 H ( D ) H(D) H(D)
H ( D ) = − ∑ k = 1 K C k D l o g 2 C k D H(D)=-\sum _{k=1}^K\frac{C_k}{D}log_2\frac{C_k}{D} H(D)=−∑k=1KDCklog2DCk
b)計算特征A對資料集D的條件熵 H ( D ∣ A ) H(D|A) H(D∣A)（條件熵概念可以參考本篇部落格）
H ( D ∣ A ) = − ∑ i = 1 n D i D H ( D i ) = − ∑ i = 1 n D i D ∑ k = 1 K D i k D i l o g 2 D i k D i H(D|A)=-\sum _{i=1}^n\frac{D_i}{D}H(D_i)=-\sum _{i=1}^n\frac{D_i}{D}\sum _{k=1}^K\frac{D_{ik}}{D_i}log_2\frac{D_{ik}}{D_i} H(D∣A)=−∑i=1nDDiH(Di)=−∑i=1nDDi∑k=1KDiDiklog2DiDik
c)計算資訊增益
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)
下面我們來看看ID3的生成算法：
輸入：訓練資料集D，特征集A，門檻值 ε \varepsilon ε；
輸出：決策樹T
a)初始化資訊增益的門檻值 ε \varepsilon ε；
b)若D中所有執行個體屬于同一類 C k C_k Ck，則T為單節點樹。标記類别為 C k C_k Ck，傳回T；
c)若 A A A為空，則T為單節點樹，将D中執行個體數最大的類 C k C_k Ck作為該節點的 類标記，傳回T；
d)否則，計算A中各特征對D的資訊增益，選擇資訊增益最大的特征 A g A_g Ag；
e)如果 A g A_g Ag的資訊增益小于門檻值 ε \varepsilon ε，則傳回單節點樹T，将D中執行個體數最大的類 C k C_k Ck作為該節點的 類标記，傳回T；
f)否則，按特征 A g A_g Ag的不同取值 a i a_i ai，依 A g = a i A_g=a_i Ag=ai将D分割為若幹個非空子集 D i D_i Di，将 D i D_i Di中執行個體數最大的類作為标記，建構子節點，由節點和子節點構成樹T，傳回T。
g)對第 i i i個子節點，以 D i D_i Di為資料集，以 A − A g A-{A_g} A−Ag為特征集，遞歸的調用 a 步 − f 步 a步-f步 a步−f步，得到子樹 T i T_i Ti，傳回 T i T_i Ti。
3）ID3的局限性
ID3由 Ross Quinlan 在1986年提出，算法本身還存在很大的局限性：
- 采用資訊增益做特征選擇，會存在偏向于選擇特征取值較多的特征；
- 無法處理處理連續變量；
- 無法對缺失值進行處理；
- 沒有剪枝政策，容易過拟合；
為了克服上述不足，Ross Quinlan 對ID3算法進行了改進，這就是下面将要探讨的C4.5算法。
4）C4.5算法
C4.5重大的改進是，提出利用資訊增益比（Information Gain Ratio）來做特征選擇，解決ID3算法存在的特征偏向問題。
特征A對訓練集D的資訊增益比 g R ( D , A ) g_R(D,A) gR(D,A)，為資訊增益 g ( D , A ) g(D,A) g(D,A)與訓練集D關于特征A的值的熵 H A ( D ) H_A(D) HA(D)之比，表達式為：
g R ( D , A ) = g ( D , A ) H A ( D ) g_R(D,A)=\frac{g(D,A)}{H_A(D)} gR(D,A)=HA(D)g(D,A)
其中 H A ( D ) = − ∑ i = 1 n D i D l o g 2 D i D H_A(D) = -\sum _{i=1}^n\frac{D_i}{D}log_2\frac{D_i}{D} HA(D)=−∑i=1nDDilog2DDi， n n n是特征A取值的個數。對于類别多的特征， H A ( D ) H_A(D) HA(D)的取值會偏大，用來平衡資訊增益帶來的偏倚。
C4.5對于連續性值的處理方式為我們熟知的特征離散化。假如n個樣本的連續性特征A有m個取值。C4.5算法首先将m個取值從小到大排序為 a 1 , a 2 . . . a m a_1,a_2...a_m a1,a2...am，分别對相鄰的兩個樣本取平均數，一共得到 m − 1 m-1 m−1個劃分點，其中第 i i i個劃分點為 a i + a i + 1 2 \frac{a_i+a_{i+1}}{2} 2ai+ai+1；然後對于m-1個劃分點，分别計算以該劃分點作為二進制分類點時的資訊增益，并選擇資訊增益最大的點作為該連續特征的二進制離散分類點
對缺失值的處理，本質就是算法怎麼填補缺失值，C4.5在缺失值處理也做了優化。樣本中存在缺失值，會引起兩個問題：第一，如何在特征值缺失的情況下進行特征選擇，即存在缺失值特征的資訊增益比該怎麼計算？第二，特征標明之後，缺失樣本該分到那個子節點中去？
對于第一個問題，C4.5的做法是，計算不含缺失值樣本的特征A的資訊增益比，乘上一個權重，權重為不含缺失樣本占總樣本的比例；對于第二個問題，C4.5的做法是，将缺失特征的樣本同時劃分入所有的子節點中，每個子節點所占的權重為每個該子節點樣本占總樣本的比例。
對于過拟合問題，C4.5采用後剪枝的方式來簡化決策樹。我們在CART樹再一起讨論。
5）C4.5的局限性
雖然C4.5在ID3算法上進行了很大的改進，但是還是存在一些明顯的局限性：
- 當特征的類别特别多時，生成決策樹（多叉樹）時，運作效率會變得非常低；
- 隻能處理分類問題；
- 不管資訊增益還是資訊增益比，都擁有大量耗時的對數運算，甚至連續值還有排序運算，比較消耗算力；
下篇我們重點讨論CART算法如何優化C4.5所存在的這些局限性。
（歡迎大家在評論區探讨交流，也歡迎大家轉載，轉載請注明出處。)
上一篇：Scikit-learn 支援向量機庫總結與簡單實踐
下一篇：決策樹（Decision Tree）算法原理總結（二）