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

對(duì)于決策樹算法來(lái)說(shuō)，核心技術(shù)就是如何確定最佳分組變量和分割點(diǎn)，上次我們介紹的CHAID是以卡方檢驗(yàn)為標(biāo)準(zhǔn)，而今天我們要介紹的C5.0則是以信息增益率作為標(biāo)準(zhǔn)，所以首先我們來(lái)了解下信息增益（Gains），要了解信息增益（Gains），先要明白信息熵的概念。

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

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

其中p是每種情況出現(xiàn)的概率,這里計(jì)算出來(lái)的1bit就是誰(shuí)獲得勝利這條信息的信息量。如果信息是最后進(jìn)入四強(qiáng)的選手誰(shuí)獲得最終勝利，它的信息量是  :

對(duì)比這個(gè)例子可以看到，不確定性越高，信息量就越大。

信息熵是信息量的數(shù)學(xué)期望，數(shù)學(xué)期望聽起來(lái)有點(diǎn)陌生，但均值我相信大家都明白，那么在概率論和統(tǒng)計(jì)學(xué)中，數(shù)學(xué)期望指的就是均值，它是試驗(yàn)中每次可能出現(xiàn)的結(jié)果的概率乘以其結(jié)果的總和，它反映隨機(jī)變量平均取值的大小。信息熵是平均信息量，也可以理解為不確定性。因此，信息熵的計(jì)算公式是:

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

如果兩位對(duì)手A和B,根據(jù)以往的比賽歷史經(jīng)驗(yàn)判斷，A勝利的概率是80%，B勝利的概率是20%,那么信息熵 : 

對(duì)比以上結(jié)果，可以看到，經(jīng)驗(yàn)減少了判斷所需的信息量，消除了不確定性，A勝利的概率越高，計(jì)算出的信息熵就越小，也就是說(shuō)，越是確定的事情，信息熵就越小。

理解了信息熵之后，我們回到C5.0這個(gè)算法，前面講到， 確定該決策樹最佳分組變量和分割點(diǎn)標(biāo)準(zhǔn)是信息增益率，我們通過例子來(lái)理解信息增益的內(nèi)容。

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

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

在沒有影響因素的時(shí)候，直接對(duì)結(jié)果是勝利還是失敗的判斷，這個(gè)信息熵我們稱為初始熵，當(dāng)加入了影響因素，或者是說(shuō)增加了一些輔判斷的信息，這時(shí)的信息熵我們稱為后驗(yàn)熵，信息增益就是初始熵減去后驗(yàn)熵得到的結(jié)果，它反映的是消除不確定性的程度。計(jì)算公式如下：

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

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

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

和 

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

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

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

同理，

B類型的信息熵為:

C類型的信息熵為:

因此

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

接下來(lái)，對(duì)T2進(jìn)行信息增益的計(jì)算，得到的結(jié)果為:

通過計(jì)算可以看到Gains(U,T1)>Gains(U,T2),因此，應(yīng)該選擇信息增益最大的輸入變量T1作為最佳分組變量，因?yàn)樗牟淮_定性程度最大，換句話說(shuō)，就是因?yàn)橛辛薚1這個(gè)信息，要確定結(jié)果是勝利與否的把握程度要比T2這個(gè)信息更高了。

可能，有人會(huì)注意到，計(jì)算信息增益Gains的時(shí)候，類別的值越多，計(jì)算得到的Gains值就越大，這會(huì)使得類別元素多的指標(biāo)有天然優(yōu)勢(shì)成為分割節(jié)點(diǎn)，因此在C5.0算法中，不是直接使用信息增益，而是使用信息增益率來(lái)作為分割標(biāo)準(zhǔn)。

所以，信息增益率:

同理 

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

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

MDLP分箱法，計(jì)算步驟如下：

· Step1:首先也是對(duì)連續(xù)變量作排序;

· Step2:取兩相鄰值的平均作為分割點(diǎn)的值，分別計(jì)算每個(gè)分割點(diǎn)的信息增益， 取信息增益最大的分割點(diǎn)作為第一個(gè)分割點(diǎn)。

· Step3:第一個(gè)分割點(diǎn)確定后，分為兩組，針對(duì)第一組和第二組，分別重復(fù)Step2,確定下一個(gè)分割點(diǎn)。

· Step4:停止條件：當(dāng)每一組計(jì)算得到的最大信息增益值小于標(biāo)準(zhǔn)時(shí)，就無(wú)需再繼續(xù)下去，即確定的分割點(diǎn)，必須滿足：

在決策樹生長(zhǎng)完成之后，為了避免它過于“依賴”訓(xùn)練樣本出現(xiàn)過度擬合的問題，需要對(duì)樹進(jìn)行剪枝，C5.0采用后修剪方法從葉節(jié)點(diǎn)向上逐層剪枝，其關(guān)鍵的技術(shù)點(diǎn)是誤差估計(jì)以及剪枝標(biāo)準(zhǔn)的設(shè)置。C5.0使用了統(tǒng)計(jì)的置信區(qū)間的估計(jì)方法，直接在Training Data中估計(jì)誤差。

估計(jì)誤差使用的公式如下：

f為觀察到的誤差率（其中E為N個(gè)實(shí)例中分類錯(cuò)誤的個(gè)數(shù)）

e為真實(shí)的誤差率，a為置信度（ 默認(rèn)值為0.25），z為對(duì)應(yīng)于置信度a的標(biāo)準(zhǔn)差，其值可根據(jù)a的設(shè)定值通過查正態(tài)分布表得到（這里a=0.25，對(duì)應(yīng)的Za/2=1.15）。通過該公式即可計(jì)算出真實(shí)誤差率e的一個(gè)置信度上限，用此上限為該節(jié)點(diǎn)誤差率e做一個(gè)悲觀的估計(jì)。

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

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

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

而C5.0里面構(gòu)建規(guī)則集，是在生成模型之前就可以選擇”規(guī)則集”

然后生成的模型結(jié)果就不是樹狀圖，而是以下的規(guī)則內(nèi)容：

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

如果想進(jìn)一步了解，可以點(diǎn)擊下面的鏈接下載試用版了解！