在之前的文章《》,我們介紹是CHAID算法，今天我們介紹另外一種用得非常廣泛的決策樹算法C5.0，該算法是專屬于RuleQuest 研究有限公司（//www.rulequest.com/）。

對于決策樹算法來說，核心技術就是如何確定最佳分組變量和分割點，上次我們介紹的CHAID是以卡方檢驗為標準，而今天我們要介紹的C5.0則是以信息增益率作為標準，所以首先我們來了解下信息增益（Gains），要了解信息增益（Gains），先要明白信息熵的概念。

信息熵是信息論中的基本概念，信息論是1948年由C.E.Shannon提出并發展起來的，主要用于解決信息傳遞中的問題，也稱統計通信理論。這些技術的概念很多書籍或者百度一下都有具體的介紹，我們這里不再贅述，我們通過一個例子來理解信息量和信息熵。

在拳擊比賽中，兩位對手誰能獲得勝利，在對兩位選擇的實力沒有任何了解的情況下，雙方取得勝利的概率都是1/2,所以誰獲得勝利這條信息的信息量,我們通過公式計算  :

其中p是每種情況出現的概率,這里計算出來的1bit就是誰獲得勝利這條信息的信息量。如果信息是最后進入四強的選手誰獲得最終勝利，它的信息量是  :

對比這個例子可以看到，不確定性越高，信息量就越大。

信息熵是信息量的數學期望，數學期望聽起來有點陌生，但均值我相信大家都明白，那么在概率論和統計學中，數學期望指的就是均值，它是試驗中每次可能出現的結果的概率乘以其結果的總和，它反映隨機變量平均取值的大小。信息熵是平均信息量，也可以理解為不確定性。因此，信息熵的計算公式是:

仍以前面拳擊比賽為例子，如果兩對對手獲勝的概率都為50%，那么信息熵:

如果兩位對手A和B,根據以往的比賽歷史經驗判斷，A勝利的概率是80%，B勝利的概率是20%,那么信息熵 : 

對比以上結果，可以看到，經驗減少了判斷所需的信息量，消除了不確定性，A勝利的概率越高，計算出的信息熵就越小，也就是說，越是確定的事情，信息熵就越小。

理解了信息熵之后，我們回到C5.0這個算法，前面講到， 確定該決策樹最佳分組變量和分割點標準是信息增益率，我們通過例子來理解信息增益的內容。

還是以上面的例子，比賽勝利與失敗是結果，那么影響這個結果的會有很多因素，這些因素是用來幫助我們判斷結果的依據，一般會消除不確定性，那么消除不確定性的程度就是信息增益。

如下圖：我們判斷選擇是否獲勝的影響因素有選手類型T1（這里的類型分別為A攻擊型、B綜合型、C防守型）和是否單身T2（1表示非單身，0表示單身），我們收集到的數據如下：

在沒有影響因素的時候，直接對結果是勝利還是失敗的判斷，這個信息熵我們稱為初始熵，當加入了影響因素，或者是說增加了一些輔判斷的信息，這時的信息熵我們稱為后驗熵，信息增益就是初始熵減去后驗熵得到的結果，它反映的是消除不確定性的程度。計算公式如下：

Gains(U,T)=E(U)-E(U/T)

E(U)是初始熵，也就是是否獲勝這個結果的信息熵，我們用公式計算   

這個公式不難理解，上表中一共14條記錄，9條結果是Y,5條結果N，也就是說，Y的概率是9/14,N的概率是5/14,信息量分別是:

和 

信息熵就是每次可能結果的概率乘以其結果的總和，所以得到上面的計算結果。

E(U/T)是后驗熵，我們先以T1為例，T1有三種結果，分別是A、B、C,每一個的概率分別是5/14,4/14,5/14。

在A這一類型里面，一共有5條記錄，其中結果為Y的概率是2/5,結果為N的是3/5。因此獲取結果為A的信息熵為

同理，

B類型的信息熵為:

C類型的信息熵為:

因此

而信息增益Gains(U,T1)=E(U)-E(U/T1)=0.940-0.694=0.246

接下來，對T2進行信息增益的計算，得到的結果為:

通過計算可以看到Gains(U,T1)>Gains(U,T2),因此，應該選擇信息增益最大的輸入變量T1作為最佳分組變量，因為它消除的不確定性程度最大，換句話說，就是因為有了T1這個信息，要確定結果是勝利與否的把握程度要比T2這個信息更高了。

可能，有人會注意到，計算信息增益Gains的時候，類別的值越多，計算得到的Gains值就越大，這會使得類別元素多的指標有天然優勢成為分割節點，因此在C5.0算法中，不是直接使用信息增益，而是使用信息增益率來作為分割標準。

所以，信息增益率:

同理 

因此，GainsR(U,T1)> GainsR(U,T2)，還是要選擇T1作為當前最佳分組變量。

那么以上是針對分類變量的情況，如果是數值變量，那跟我們之前文章講到的CHAID算法一樣，對數值變量進行離散化成為區間，在C5.0里面，使用的是MDLP的熵分箱方法 (還記得嗎？CHAID使用的是ChiMerge分組方法)，MDLP全稱是“MinimalDescription Length Principle”，即最短描述長度原則的熵分箱法。基于MDLP的熵分箱的核心測度指標是信息熵和信息增益。

MDLP分箱法，計算步驟如下：

· Step1:首先也是對連續變量作排序;

· Step2:取兩相鄰值的平均作為分割點的值，分別計算每個分割點的信息增益， 取信息增益最大的分割點作為第一個分割點。

· Step3:第一個分割點確定后，分為兩組，針對第一組和第二組，分別重復Step2,確定下一個分割點。

· Step4:停止條件：當每一組計算得到的最大信息增益值小于標準時，就無需再繼續下去，即確定的分割點，必須滿足：

在決策樹生長完成之后，為了避免它過于“依賴”訓練樣本出現過度擬合的問題，需要對樹進行剪枝，C5.0采用后修剪方法從葉節點向上逐層剪枝，其關鍵的技術點是誤差估計以及剪枝標準的設置。C5.0使用了統計的置信區間的估計方法，直接在Training Data中估計誤差。

估計誤差使用的公式如下：

f為觀察到的誤差率（其中E為N個實例中分類錯誤的個數）

e為真實的誤差率，a為置信度（ 默認值為0.25），z為對應于置信度a的標準差，其值可根據a的設定值通過查正態分布表得到（這里a=0.25，對應的Za/2=1.15）。通過該公式即可計算出真實誤差率e的一個置信度上限，用此上限為該節點誤差率e做一個悲觀的估計。

計算了每個分支節點的誤差估計之后，按“減少-誤差（Reduce-Error)”法判斷是否剪枝。首先，計算待剪子樹中葉節點的加權誤差；然后與父節點的誤差進行比較，如果計算待剪子樹中葉節點的加權誤差大于父節點的誤差，則可以剪掉，否則不能剪掉。

這里值得注意的是，C5.0算法只支持分類變量作為目標，不支持連續變量作為目標。

在C5.0算法里面，它的獨特之處是，除了構建決策樹，還能夠生成推理規則集，它的一般算法是PRISM(Patient Rule Introduction Space Method),它所生成的規則集跟其它決策樹算法生成的規則集原理并不一樣，其它決策樹生成的規則集是根據決策樹生長結果，得到的規則，如下圖（以C5.0生成決策樹為例）：

而C5.0里面構建規則集，是在生成模型之前就可以選擇”規則集”

然后生成的模型結果就不是樹狀圖，而是以下的規則內容：

那么對于C5.0算法中，生成推理規則算法PRISM的具體計算邏輯，感興趣的朋友可以給我們留言，我們下次再做具體介紹。

如果想進一步了解，可以點擊下面的鏈接下載試用版了解！