決策樹（三）分類演算法小結
引言
本文主要是對分型別決策樹的一個總結。在分類問題中，決策樹可以被看做是if-then規則的結合，也可以認為是在特定特徵空間與類空間上的條件概率分佈。決策樹學習主要分為三個步驟：特徵選擇、決策樹的生成與剪枝操作。本文簡單總結ID3和C4.5演算法，之後是決策樹的修剪。
ID3演算法
ID3演算法和核心是：在決策樹各級節點上選擇屬性時，用資訊增益（information gain）作為屬性的選擇標準，具體做法是：檢測所有的屬性，選擇資訊增益最大的屬性產生決策樹節點，由該屬性的不同取值建立分支，再對各分支迴圈呼叫該方法建立決策樹節點的分支，直到所有子集僅包含同一類別為止。
資訊增益
瞭解資訊增益，首先介紹熵與條件熵的概念。
熵表示隨機變數不確定性的度量。設$X$是一個取有限值的離散隨機變數，其概率分佈為：
$$p(X=x_i)=p_i$$
則隨機變數 $X$ 的熵定義為:
$$H(X)=-\sum_{i=1}^np_ilogp_i ， i=1,2,n$$
由定義可知，熵只依賴於$X$的分佈，而與$X$的取值無關。
熵越大，隨機變數的不確定性越高，並且：
$$0\leqslant{H(p)}\leqslant{logn}$$
當隨機變數只有兩個取值時，例如0，1，則$X$的分佈為：
$$p(X=1)=p，p(X=0)=1-p， 0\leqslant{p}\leqslant1$$
熵為：
$$H(p)=-plog_2p-(1-p)log_2(1-p)$$
當$p=0$或$p=1$時，$H(p)=0$，隨機變數完全沒有不確定性，當$p=0.5$時，$H(p)=1$，熵取最大值，隨機變數的不確定性最大。
條件熵
設隨即變數$(X,Y)$，其聯合概率分佈為：
$$P(X=x_i,Y=y_i)=p_{ij},i=1,2,\dots,n;j=1,2,\dots,n$$
條件熵$H(Y|X)$表示在已知隨機變數$X$的條件下隨機變數$Y$的不確定性，隨機變數$X$給定的條件下隨機變數$Y$的條件熵$H(Y|X)$，定義為$X$給定的條件下$Y$的條件概率分佈的熵對$X$的數學期望：
$$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$$
這裡，$p_i=P(X=x_i)$
資訊增益
特徵$A$對訓練資料集$D$的資訊增益，定義為集合$A$的經驗熵$H(D)$與特徵$A$給定條件下$D$的經驗條件熵$H(D|A)$之差：
$$g(D,A)=H(D)-H(D|A)$$
小結
ID3演算法就是在每次需要分裂時，計算每個屬性的增益率，然後選擇增益率最大的屬性進行分裂.
其核心是：決策樹各級結點上選擇屬性時，用資訊增益（information gain）作為屬性的選擇標準，以使得在每一個非葉結點進行測試時，能獲得關於被測試記錄最大的類別資訊。
其方法是：檢測所有的屬性，選擇資訊增益最大的屬性產生決策樹結點，由該屬性的不同取值建立分支，再對各分支的子集遞迴呼叫該方法建立決策樹結點的分支，直到所有子集僅包含同一類別的資料為止。最後得到一棵決策樹。
C4.5演算法
C4.5演算法首先定義了“分裂資訊”，即資訊增益比：
$$g_R(D,A)=\frac{g(D,A)}{H(D)}\qquad$$
C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
- 1：用資訊增益率來選擇屬性，克服了用資訊增益選擇屬性時偏向選擇取值多的屬性的不足
- 2：能夠完成對連續屬性的離散化處理；
- 3：能夠對不完整資料進行處理。
決策樹剪枝
決策樹構造時，由於訓練資料中的噪音或孤立點，許多分枝反映的是訓練資料中的異常，使用這樣的判定樹對類別未知的資料進行分類，分類的準確性不高。因此試圖檢測和減去這樣的分支，檢測和減去這些分支的過程被稱為樹剪枝。樹剪枝方法用於處理過分適應資料問題。通常，這種方法使用統計度量，減去最不可靠的分支，這將導致較快的分類，提高樹獨立於訓練資料正確分類的能力。
樹枝修剪包括事先修剪和事後修剪兩種方法：
（1）事前修剪方法：在決策樹生成分支的過程，除了要進行基礎規則的判斷外，還需要利用統計學的方法對即將分支的節點進行判斷，比如$\chi^2$或統計資訊增益，如果分支後使得子集的樣本統計特性不滿足規定的閾值，則停止分支；但是閾值如何選取才合理是比較困難的。
（2）事後修剪方法：在決策樹充分生長後，修剪掉多餘的分支。根據每個分支的分類錯誤率及每個分支的權重，計算該節點不修剪時預期分類錯誤率；對於每個非葉節點，計算該節點被修剪後的分類錯誤率，如果修剪後分類錯誤率變大，即放棄修剪；否則將該節點強制為葉節點，並標記類別。產生一系列修剪過的決策樹候選之後，利用測試資料（未參與建模的資料）對各候選決策樹的分類準確性進行評價，保留分類錯誤率最小的決策樹。
除了利用分類錯誤率進行樹枝修剪，也可以利用決策樹的編碼長度進行修剪。所謂最佳決策樹是編碼長度最短的決策樹，這種修剪方法利用最短描述長度（MDL）原則來進行決策樹的修剪。