決策樹(shù)理論
在決策樹(shù)理論中，有這樣一句話，“用較少的東西，照樣可以做很好的事情。越是小的決策樹(shù)，越優(yōu)于大的決策樹(shù)”。數(shù)據(jù)分類是一個(gè)兩階段過(guò)程，包括模型學(xué)習(xí)階段（構(gòu)建分類模型）和分類預(yù)測(cè)階段（使用模型預(yù)測(cè)給定數(shù)據(jù)的類標(biāo)號(hào)）。決策樹(shù)分類算法屬于監(jiān)督學(xué)習(xí)（Supervised learning），即樣本數(shù)據(jù)中有類別標(biāo)號(hào)。下面是兩個(gè)階段的簡(jiǎn)單描述：
決策樹(shù)步驟
第一階段（以分類為例），可以看做是根據(jù)樣本來(lái)學(xué)習(xí)一個(gè)映射或函數(shù)y=f(x)表達(dá)式，能夠使用它預(yù)測(cè)給定元組X的類標(biāo)號(hào)y。
第二階段，使用第一階段學(xué)習(xí)得到的模型進(jìn)行分類。首先評(píng)估分類器的預(yù)測(cè)準(zhǔn)確率。這個(gè)過(guò)程要盡量減少過(guò)擬合（為什么是盡量減少？因?yàn)檫^(guò)擬合是避免不了的，再好的模型也會(huì)有過(guò)擬合的情況的）。
簡(jiǎn)介
決策樹(shù)歸納是從有類標(biāo)號(hào)的訓(xùn)練元組中學(xué)習(xí)決策模型。常用的決策樹(shù)算法有ID3，C4.5和CART。它們都是采用貪心（即非回溯的）方法，自頂向下遞歸的分治方法構(gòu)造。
這幾個(gè)算法選擇屬性劃分的方法各不相同，ID3使用的是信息增益，C4.5使用的是信息增益率，而CART使用的是Gini基尼指數(shù)。下面來(lái)簡(jiǎn)單介紹下決策樹(shù)的理論知識(shí)。內(nèi)容包含熵、信息增益、信息增益率以及Gini指數(shù)的概念及公式。
決策樹(shù)劃分方式
二元?jiǎng)澐趾投嘣獎(jiǎng)澐?；如果采用二元?jiǎng)澐?，?duì)于離散變量而言，選定property分類即可；對(duì)于連續(xù)變量，需要選定split_point。
算法優(yōu)點(diǎn)
算法比較簡(jiǎn)單；
理論易于理解；
對(duì)噪聲數(shù)據(jù)有很好的健壯性。
目前，決策樹(shù)是應(yīng)用最為廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘中受到研究者的廣泛關(guān)注。衍生出很多出色的集成算法，如random forest、adaboost、gradient tree boosting都是基于決策樹(shù)的模型。
算法流程
收集數(shù)據(jù)：任意方法和途徑。
準(zhǔn)備數(shù)據(jù)：書(shū)構(gòu)造算法只適用于標(biāo)稱型數(shù)據(jù)，因此數(shù)據(jù)必須離散化。
分析數(shù)據(jù)：構(gòu)造樹(shù)完成后，檢查圖形是否符合預(yù)測(cè)。
訓(xùn)練算法：決策樹(shù)的數(shù)據(jù)構(gòu)造。
測(cè)試算法：一般將決策樹(shù)用于分類，可以用錯(cuò)誤率衡量，而錯(cuò)誤率使用經(jīng)驗(yàn)率計(jì)算。
使用算法：決策樹(shù)可以用于任何監(jiān)督學(xué)習(xí)算法。
基于信息論的三種決策樹(shù)算法
劃分?jǐn)?shù)據(jù)集的最大原則是：使無(wú)序的數(shù)據(jù)變的有序。如果一個(gè)訓(xùn)練數(shù)據(jù)中有20個(gè)特征，那么選取哪個(gè)做劃分依據(jù)？這就必須采用量化的方法來(lái)判斷，量化劃分方法有多重，其中一項(xiàng)就是“信息論度量信息分類”。基于信息論的決策樹(shù)算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來(lái)。
CART和C4.5支持?jǐn)?shù)據(jù)特征為連續(xù)分布時(shí)的處理，主要通過(guò)使用二元切分來(lái)處理連續(xù)型變量，即求一個(gè)特定的值-分裂值：特征值大于分裂值就走左子樹(shù)，或者就走右子樹(shù)。這個(gè)分裂值的選取的原則是使得劃分后的子樹(shù)中的“混亂程度”降低，具體到C4.5和CART算法則有不同的定義方式。
ID3算法由Ross Quinlan發(fā)明，建立在“奧卡姆剃刀”的基礎(chǔ)上：越是小型的決策樹(shù)越優(yōu)于大的決策樹(shù)（be simple簡(jiǎn)單理論）。
ID3算法中根據(jù)信息論的信息增益評(píng)估和選擇特征，每次選擇信息增益最大的特征做判斷模塊。ID3算法可用于劃分標(biāo)稱型數(shù)據(jù)集，沒(méi)有剪枝的過(guò)程，為了去除過(guò)度數(shù)據(jù)匹配的問(wèn)題，可通過(guò)裁剪合并相鄰的無(wú)法產(chǎn)生大量信息增益的葉子節(jié)點(diǎn)（例如設(shè)置信息增益閥值）。使用信息增益的話其實(shí)是有一個(gè)缺點(diǎn)，那就是它偏向于具有大量值的屬性–就是說(shuō)在訓(xùn)練集中，某個(gè)屬性所取的不同值的個(gè)數(shù)越多，那么越有可能拿它來(lái)作為分裂屬性，而這樣做有時(shí)候是沒(méi)有意義的，另外ID3不能處理連續(xù)分布的數(shù)據(jù)特征，于是就有了C4.5算法。CART算法也支持連續(xù)分布的數(shù)據(jù)特征。
C4.5是ID3的一個(gè)改進(jìn)算法，繼承了ID3算法的優(yōu)點(diǎn)。C4.5算法用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足在樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝；能夠完成對(duì)連續(xù)屬性的離散化處理；能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5算法產(chǎn)生的分類規(guī)則易于理解、準(zhǔn)確率較高；但效率低，因樹(shù)構(gòu)造過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序。也是因?yàn)楸仨毝啻螖?shù)據(jù)集掃描，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集。
CART算法的全稱是Classification And Regression Tree，采用的是Gini指數(shù)（選Gini指數(shù)最小的特征s）作為分裂標(biāo)準(zhǔn),同時(shí)它也是包含后剪枝操作。ID3算法和C4.5算法雖然在對(duì)訓(xùn)練樣本集的學(xué)習(xí)中可以盡可能多地挖掘信息，但其生成的決策樹(shù)分支較大，規(guī)模較大。為了簡(jiǎn)化決策樹(shù)的規(guī)模，提高生成決策樹(shù)的效率，就出現(xiàn)了根據(jù)GINI系數(shù)來(lái)選擇測(cè)試屬性的決策樹(shù)算法CART。
ID3：信息增益作為劃分屬性
熵被用來(lái)衡量一個(gè)隨機(jī)變量出現(xiàn)的期望值。熵越大，一個(gè)變量的不確定性就越大（也就是可取的值很多），把它搞清楚所需要的信息量也就越大，熵是整個(gè)系統(tǒng)的平均消息量。
信息熵是信息論中用于度量信息量的一個(gè)概念。一個(gè)系統(tǒng)越是有序，信息熵就越低；反之，一個(gè)系統(tǒng)越是混亂，信息熵就越高。所以，信息熵也可以說(shuō)是系統(tǒng)有序化程度的一個(gè)度量。
熵（Entropy）的計(jì)算公式
熵定義為信息的期望值。先看看信息的定義：
$$l(x_i)=?log_2p(x_i)$$
對(duì)D中的元組所有分類所有可能值的信息期望，即熵，計(jì)算公式如下：
$$Entropy=H(D)=E(I(D))=?∑_i^np_ilog_2(p_i)$$，$$p_i$$是D中任意元組屬于類$$C_i$$非零概率。
一個(gè)屬性的信息增益越大，表明屬性對(duì)樣本的熵減少的能力就更強(qiáng)，該屬性使得數(shù)據(jù)所屬類別的不確定性變?yōu)榇_定性的能力越強(qiáng)。
信息增益在統(tǒng)計(jì)學(xué)中稱為互信息，互信息是條件概率與后驗(yàn)概率的比值，化簡(jiǎn)之后就可以得到信息增益。所以說(shuō)互信息其實(shí)就是信息增益。計(jì)算方法【互信息=熵-條件熵】。熵描述的是不確定性。
熵越大，不確定性就越大，條件熵$H（B|A）$描述的是在A給定的條件下B的不確定性，如果條件熵越小，表示不確定性就越小，那么B就越容易確定結(jié)果。所以使用熵減去條件熵，就得到了信息增益，他描述的不確定性的降低程度，可以用來(lái)度量?jī)蓚€(gè)變量的相關(guān)性。比如，在給定一個(gè)變量的條件下，另一個(gè)變量它的不確定性能夠降低多少，如果不確定性降低得越多，那么它的確定性就越大，就越容易區(qū)分，兩者就越相關(guān)。注：期望信息越小，分區(qū)的純度越高。
首先計(jì)算特征A對(duì)數(shù)據(jù)集D的經(jīng)驗(yàn)條件熵$H(D|A)$,在數(shù)學(xué)上就是條件概率分布（Condition Probability）.
$H(D|A)=∑_j|Dj||D|×H(D_j)$，項(xiàng)$|Di||D|$充當(dāng)?shù)趈個(gè)分區(qū)的權(quán)重
引入條件熵，在信息論中主要是為了消除結(jié)果的不確定性。然后計(jì)算信息增益:
$Gain(A)=H(D)?H(D|A)$
$Gain(A)$即為所求的信息增益。
在決策樹(shù)中，ID3屬性劃分標(biāo)準(zhǔn)使用的是信息增益，C4.5使用的是信息增益率。
C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：
- 用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足；
- 在樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝；
- 能夠完成對(duì)連續(xù)屬性的離散化處理；
- 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。
C4.5算法有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。另外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。
另外，無(wú)論是ID3還是C4.5最好在小數(shù)據(jù)集上使用，決策樹(shù)分類一般只試用于小數(shù)據(jù)。當(dāng)屬性取值很多時(shí)最好選擇C4.5算法，ID3得出的效果會(huì)非常差，因?yàn)槭褂眯畔⒃鲆鎰澐謺r(shí)它傾向于取值多的屬性。
計(jì)算信息增益率時(shí)，用到了分裂信息計(jì)算公式：
$SplitH(D|A)=?∑|Dj||D|×log_2(|Dj||D|)$
信息增益率定義為：
$GainRate(A)=Gain(A)SplitH(D|A)$
選擇具有最大增益率的特征作為分裂特征。
3.基尼指數(shù)Gini index
基尼指數(shù)主要在CART算法中用到，隨機(jī)森林中用到的屬性劃分標(biāo)準(zhǔn)也是它。Gini index劃分是二元的，它度量的是數(shù)據(jù)分區(qū)或訓(xùn)練元組集D的不純度，表示的是一個(gè)隨機(jī)選中的樣本在子集中被分錯(cuò)的可能性。計(jì)算方式如下：
$Gini(D)=1?∑p_i$，其中，$p_i$是D中元組數(shù)以$C_i$類的概率，對(duì)m個(gè)類計(jì)算和。
Gini指數(shù)越大，不純度越大，越不容易區(qū)分。當(dāng)考慮二元?jiǎng)澐至褧r(shí)，計(jì)算每個(gè)結(jié)果分區(qū)的不純度加權(quán)和。比如A有兩個(gè)值，則特征D被劃分成D1和D2,這時(shí)Gini指數(shù)為：
$$Gini_A(D) = \frac{D_1}{D} Gini(D_1) + \frac{D_2}{D} Gini(D_2)$$
上面的式子表示的是不確定性的大小。對(duì)于每個(gè)屬性，考慮每種可能的二元?jiǎng)澐?，?duì)于離散值屬性，選擇該屬性產(chǎn)生最小Gini指數(shù)的自己作為它的分裂信息。
連續(xù)型數(shù)據(jù)的處理
先把連續(xù)屬性轉(zhuǎn)換為離散屬性再進(jìn)行處理。雖然本質(zhì)上屬性的取值是連續(xù)的，但對(duì)于有限的采樣數(shù)據(jù)它是離散的，如果有N條樣本，那么我們有N-1種離散化的方法：<=vj的分到左子樹(shù)，>vj的分到右子樹(shù)。計(jì)算這N-1種情況下最大的信息增益率。
另外，對(duì)于連續(xù)屬性先進(jìn)行排序（升序），只有在決策屬性（即分類發(fā)生了變化）發(fā)生改變的地方才需要切開(kāi)，這可以顯著減少運(yùn)算量。經(jīng)證明，在決定連續(xù)特征的分界點(diǎn)時(shí)采用增益這個(gè)指標(biāo)（因?yàn)槿舨捎迷鲆媛?，splittedinfo影響分裂點(diǎn)信息度量準(zhǔn)確性，若某分界點(diǎn)恰好將連續(xù)特征分成數(shù)目相等的兩部分時(shí)其抑制作用最大），而選擇屬性的時(shí)候才使用增益率這個(gè)指標(biāo)能選擇出最佳分類特征。
在C4.5中，對(duì)連續(xù)屬性的處理如下：
對(duì)特征的取值進(jìn)行升序排序兩個(gè)特征取值之間的中點(diǎn)作為可能的分裂點(diǎn)，將數(shù)據(jù)集分成兩部分，計(jì)算每個(gè)可能的分裂點(diǎn)的信息增益（InforGain）。優(yōu)化算法就是只計(jì)算分類屬性發(fā)生改變的那些特征取值。選擇修正后信息增益(InforGain)最大的分裂點(diǎn)作為該特征的最佳分裂點(diǎn)計(jì)算最佳分裂點(diǎn)的信息增益率（Gain Ratio）作為特征的Gain Ratio。注意，此處需對(duì)最佳分裂點(diǎn)的信息增益進(jìn)行修正：減去$$\frac{log_2(N-1)}{|D|}$$（N是連續(xù)特征的取值個(gè)數(shù)，D是訓(xùn)練數(shù)據(jù)數(shù)目，此修正的原因在于：當(dāng)離散屬性和連續(xù)屬性并存時(shí)，C4.5算法傾向于選擇連續(xù)特征做最佳樹(shù)分裂點(diǎn)）
實(shí)現(xiàn)連續(xù)特征數(shù)據(jù)集劃分的Python程序?yàn)椋?/p>
def binSplitDataSet(dataSet, feature, value):
mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0]
mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0]
return mat0,mat1
其中dataset為numpy matrix， feature為dataset連續(xù)特征在dataset所有特征中的index，value即為feature臨近兩值的均值。
葉子裁剪
決策樹(shù)為什么要剪枝？原因就是避免決策樹(shù)“過(guò)擬合”樣本。前面的算法生成的決策樹(shù)非常的詳細(xì)而龐大，每個(gè)屬性都被詳細(xì)地加以考慮，決策樹(shù)的樹(shù)葉節(jié)點(diǎn)所覆蓋的訓(xùn)練樣本都是“純”的。因此用這個(gè)決策樹(shù)來(lái)對(duì)訓(xùn)練樣本進(jìn)行分類的話，你會(huì)發(fā)現(xiàn)對(duì)于訓(xùn)練樣本而言，這個(gè)樹(shù)表現(xiàn)堪稱完美，它可以100%完美正確得對(duì)訓(xùn)練樣本集中的樣本進(jìn)行分類（因?yàn)闆Q策樹(shù)本身就是100%完美擬合訓(xùn)練樣本的產(chǎn)物）。但是，這會(huì)帶來(lái)一個(gè)問(wèn)題，如果訓(xùn)練樣本中包含了一些錯(cuò)誤，按照前面的算法，這些錯(cuò)誤也會(huì)100%一點(diǎn)不留得被決策樹(shù)學(xué)習(xí)了，這就是“過(guò)擬合”。C4.5的締造者昆蘭教授很早就發(fā)現(xiàn)了這個(gè)問(wèn)題，他作過(guò)一個(gè)試驗(yàn)，在某一個(gè)數(shù)據(jù)集中，過(guò)擬合的決策樹(shù)的錯(cuò)誤率比一個(gè)經(jīng)過(guò)簡(jiǎn)化了的決策樹(shù)的錯(cuò)誤率要高。那么現(xiàn)在的問(wèn)題就來(lái)了，如何在原生的過(guò)擬合決策樹(shù)的基礎(chǔ)上，通過(guò)剪枝生成一個(gè)簡(jiǎn)化了的決策樹(shù)？
檢測(cè)和減去這些分支的過(guò)程被稱為樹(shù)剪枝。樹(shù)剪枝方法用于處理過(guò)分適應(yīng)數(shù)據(jù)問(wèn)題。通常，這種方法使用統(tǒng)計(jì)度量，減去最不可靠的分支，這將導(dǎo)致較快的分類，提高樹(shù)獨(dú)立于訓(xùn)練數(shù)據(jù)正確分類的能力。
決策樹(shù)常用的剪枝常用的簡(jiǎn)直方法有兩種：預(yù)剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。預(yù)剪枝是根據(jù)一些原則及早的停止樹(shù)增長(zhǎng)，如樹(shù)的深度達(dá)到用戶所要的深度、節(jié)點(diǎn)中樣本個(gè)數(shù)少于用戶指定個(gè)數(shù)、不純度指標(biāo)下降的最大幅度小于用戶指定的幅度等。預(yù)剪枝的核心問(wèn)題是如何事先指定樹(shù)的最大深度，如果設(shè)置的最大深度不恰當(dāng)，那么將會(huì)導(dǎo)致過(guò)于限制樹(shù)的生長(zhǎng)，使決策樹(shù)的表達(dá)式規(guī)則趨于一般，不能更好地對(duì)新數(shù)據(jù)集進(jìn)行分類和預(yù)測(cè)。除了事先限定決策樹(shù)的最大深度之外，還有另外一個(gè)方法來(lái)實(shí)現(xiàn)預(yù)剪枝操作，那就是采用檢驗(yàn)技術(shù)對(duì)當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的樣本集合進(jìn)行檢驗(yàn)，如果該樣本集合的樣本數(shù)量已小于事先指定的最小允許值，那么停止該結(jié)點(diǎn)的繼續(xù)生長(zhǎng)，并將該結(jié)點(diǎn)變?yōu)槿~子結(jié)點(diǎn)，否則可以繼續(xù)擴(kuò)展該結(jié)點(diǎn)。
后剪枝則是通過(guò)在完全生長(zhǎng)的樹(shù)上剪去分枝實(shí)現(xiàn)的，通過(guò)刪除節(jié)點(diǎn)的分支來(lái)剪去樹(shù)節(jié)點(diǎn)，可以使用的后剪枝方法有多種，比如：代價(jià)復(fù)雜性剪枝、最小誤差剪枝、悲觀誤差剪枝等等。后剪枝操作是一個(gè)邊修剪邊檢驗(yàn)的過(guò)程，一般規(guī)則標(biāo)準(zhǔn)是：在決策樹(shù)的不斷剪枝操作過(guò)程中，將原樣本集合或新數(shù)據(jù)集合作為測(cè)試數(shù)據(jù)，檢驗(yàn)決策樹(shù)對(duì)測(cè)試數(shù)據(jù)的預(yù)測(cè)精度，并計(jì)算出相應(yīng)的錯(cuò)誤率，如果剪掉某個(gè)子樹(shù)后的決策樹(shù)對(duì)測(cè)試數(shù)據(jù)的預(yù)測(cè)精度或其他測(cè)度不降低，那么剪掉該子樹(shù)。
1、第一種方法，也是最簡(jiǎn)單的方法，稱之為基于誤判的剪枝。這個(gè)思路很直接，完全的決策樹(shù)不是過(guò)度擬合么，我再搞一個(gè)測(cè)試數(shù)據(jù)集來(lái)糾正它。對(duì)于完全決策樹(shù)中的每一個(gè)非葉子節(jié)點(diǎn)的子樹(shù)，我們嘗試著把它替換成一個(gè)葉子節(jié)點(diǎn)，該葉子節(jié)點(diǎn)的類別我們用子樹(shù)所覆蓋訓(xùn)練樣本中存在最多的那個(gè)類來(lái)代替，這樣就產(chǎn)生了一個(gè)簡(jiǎn)化決策樹(shù)，然后比較這兩個(gè)決策樹(shù)在測(cè)試數(shù)據(jù)集中的表現(xiàn)，如果簡(jiǎn)化決策樹(shù)在測(cè)試數(shù)據(jù)集中的錯(cuò)誤比較少，并且該子樹(shù)里面沒(méi)有包含另外一個(gè)具有類似特性的子樹(shù)（所謂類似的特性，指的就是把子樹(shù)替換成葉子節(jié)點(diǎn)后，其測(cè)試數(shù)據(jù)集誤判率降低的特性），那么該子樹(shù)就可以替換成葉子節(jié)點(diǎn)。該算法以bottom-up的方式遍歷所有的子樹(shù)，直至沒(méi)有任何子樹(shù)可以替換使得測(cè)試數(shù)據(jù)集的表現(xiàn)得以改進(jìn)時(shí)，算法就可以終止。
2、第一種方法很直接，但是需要一個(gè)額外的測(cè)試數(shù)據(jù)集，能不能不要這個(gè)額外的數(shù)據(jù)集呢？為了解決這個(gè)問(wèn)題，于是就提出了悲觀剪枝。該方法剪枝的依據(jù)是訓(xùn)練樣本集中的樣本誤判率。我們知道一顆分類樹(shù)的每個(gè)節(jié)點(diǎn)都覆蓋了一個(gè)樣本集，根據(jù)算法這些被覆蓋的樣本集往往都有一定的誤判率，因?yàn)槿绻?jié)點(diǎn)覆蓋的樣本集的個(gè)數(shù)小于一定的閾值，那么這個(gè)節(jié)點(diǎn)就會(huì)變成葉子節(jié)點(diǎn)，所以葉子節(jié)點(diǎn)會(huì)有一定的誤判率。而每個(gè)節(jié)點(diǎn)都會(huì)包含至少一個(gè)的葉子節(jié)點(diǎn)，所以每個(gè)節(jié)點(diǎn)也都會(huì)有一定的誤判率。悲觀剪枝就是遞歸得估算每個(gè)內(nèi)部節(jié)點(diǎn)所覆蓋樣本節(jié)點(diǎn)的誤判率。剪枝后該內(nèi)部節(jié)點(diǎn)會(huì)變成一個(gè)葉子節(jié)點(diǎn)，該葉子節(jié)點(diǎn)的類別為原內(nèi)部節(jié)點(diǎn)的最優(yōu)葉子節(jié)點(diǎn)所決定。然后比較剪枝前后該節(jié)點(diǎn)的錯(cuò)誤率來(lái)決定是否進(jìn)行剪枝。該方法和前面提到的第一種方法思路是一致的，不同之處在于如何估計(jì)剪枝前分類樹(shù)內(nèi)部節(jié)點(diǎn)的錯(cuò)誤率。
缺失值處理
對(duì)于某些采樣數(shù)據(jù)，可能會(huì)缺少屬性值。在這種情況下，處理缺少屬性值的通常做法是賦予該屬性的常見(jiàn)值，或者屬性均值。另外一種比較好的方法是為該屬性的每個(gè)可能值賦予一個(gè)概率，即將該屬性以概率形式賦值。例如給定Boolean屬性B，已知采樣數(shù)據(jù)有12個(gè)B=0和88個(gè)B=1實(shí)例，那么在賦值過(guò)程中，B屬性的缺失值被賦為B(0)=0.12、B(1)=0.88；所以屬性B的缺失值以12%概率被分到False的分支，以88%概率被分到True的分支。這種處理的目的是計(jì)算信息增益，使得這種屬性值缺失的樣本也能處理。
相對(duì)于那些離散值屬性，分類樹(shù)算法傾向于選擇那些連續(xù)值屬性，因?yàn)檫B續(xù)值屬性會(huì)有更多的分支，熵增益也最大。算法需要克服這種傾向，我們利用增益率來(lái)克服這種傾向。增益率也可以用來(lái)克服連續(xù)值屬性傾向。增益率作為選擇屬性的依據(jù)克服連續(xù)值屬性傾向，這是沒(méi)有問(wèn)題的。但是如果利用增益率來(lái)選擇連續(xù)值屬性的分界點(diǎn)，會(huì)導(dǎo)致一些副作用。分界點(diǎn)將樣本分成兩個(gè)部分，這兩個(gè)部分的樣本個(gè)數(shù)之比也會(huì)影響增益率。根據(jù)增益率公式，我們可以發(fā)現(xiàn)，當(dāng)分界點(diǎn)能夠把樣本分成數(shù)量相等的兩個(gè)子集時(shí)（我們稱此時(shí)的分界點(diǎn)為等分分界點(diǎn)），增益率的抑制會(huì)被最大化，因此等分分界點(diǎn)被過(guò)分抑制了。子集樣本個(gè)數(shù)能夠影響分界點(diǎn)，顯然不合理。因此在決定分界點(diǎn)是還是采用增益這個(gè)指標(biāo)，而選擇屬性的時(shí)候才使用增益率這個(gè)指標(biāo)。這個(gè)改進(jìn)能夠很好得抑制連續(xù)值屬性的傾向。當(dāng)然還有其它方法也可以抑制這種傾向，比如MDL。
i)當(dāng)開(kāi)始決定選擇哪個(gè)屬性用來(lái)進(jìn)行分支時(shí)，如果有些訓(xùn)練樣本缺失了某些屬性值時(shí)該怎么辦？
ii)一個(gè)屬性已被選擇，那么在決定分支的時(shí)候如果有些樣本缺失了該屬性該如何處理？
iii)當(dāng)決策樹(shù)已經(jīng)生成，但待分類的樣本缺失了某些屬性，這些屬性該如何處理？針對(duì)這三個(gè)問(wèn)題，昆蘭提出了一系列解決的思路和方法。
對(duì)于問(wèn)題i),計(jì)算屬性a的增益或者增益率時(shí)，如果有些樣本沒(méi)有屬性a，那么可以有這么幾種處理方式：
(1)忽略這些缺失屬性a的樣本。
(2)給缺失屬性a的樣本賦予屬性a一個(gè)均值或者最常用的的值。
(3)計(jì)算增益或者增益率時(shí)根據(jù)缺失屬性樣本個(gè)數(shù)所占的比率對(duì)增益/增益率進(jìn)行相應(yīng)的“打折”。
(4)根據(jù)其他未知的屬性想辦法把這些樣本缺失的屬性補(bǔ)全。
對(duì)于問(wèn)題ii)，當(dāng)屬性a已經(jīng)被選擇，該對(duì)樣本進(jìn)行分支的時(shí)候，如果有些樣本缺失了屬性a,那么：
(1)忽略這些樣本。
(2)把這些樣本的屬性a賦予一個(gè)均值或者最常出現(xiàn)的值，然后再對(duì)他們進(jìn)行處理。
(3)把這些屬性缺失樣本，按照具有屬性a的樣本被劃分成的子集樣本個(gè)數(shù)的相對(duì)比率，分配到各個(gè)子集中去。至于哪些缺失的樣本被劃分到子集1，哪些被劃分到子集2，這個(gè)沒(méi)有一定的準(zhǔn)則，可以隨機(jī)而動(dòng)。(A)把屬性缺失樣本分配給所有的子集，也就是說(shuō)每個(gè)子集都有這些屬性缺失樣本。
(3)單獨(dú)為屬性缺失的樣本劃分一個(gè)分支子集。
(4)對(duì)于缺失屬性a的樣本，嘗試著根據(jù)其他屬性給他分配一個(gè)屬性a的值，然后繼續(xù)處理將其劃分到相應(yīng)的子集。
對(duì)于問(wèn)題iii)，對(duì)于一個(gè)缺失屬性a的待分類樣本，有這么幾種選擇：
(1)如果有單獨(dú)的確實(shí)分支，依據(jù)此分支。
(2)把待分類的樣本的屬性a值分配一個(gè)最常出現(xiàn)的a的屬性值，然后進(jìn)行分支預(yù)測(cè)。
(3)根據(jù)其他屬性為該待分類樣本填充一個(gè)屬性a值，然后進(jìn)行分支處理。
(4)在決策樹(shù)中屬性a節(jié)點(diǎn)的分支上，遍歷屬性a節(jié)點(diǎn)的所有分支，探索可能所有的分類結(jié)果，然后把這些分類結(jié)果結(jié)合起來(lái)一起考慮，按照概率決定一個(gè)分類。
(5)待分類樣本在到達(dá)屬性a節(jié)點(diǎn)時(shí)就終止分類，然后根據(jù)此時(shí)a節(jié)點(diǎn)所覆蓋的葉子節(jié)點(diǎn)類別狀況為其分配一個(gè)發(fā)生概率最高的類。
[參考內(nèi)容]（http://blog.csdn.net/u011067360/article/details/21861989）
CART
在數(shù)據(jù)挖掘中，決策樹(shù)主要有兩種類型:
- 分類樹(shù) 的輸出是樣本的類標(biāo)
- 回歸樹(shù) 的輸出是一個(gè)實(shí)數(shù)(例如房子的價(jià)格，病人呆在醫(yī)院的時(shí)間等)。
術(shù)語(yǔ)分類和回歸樹(shù) (CART) 包含了上述兩種決策樹(shù), 最先由Breiman 等提出.分類樹(shù)和回歸樹(shù)有些共同點(diǎn)和不同點(diǎn)—例如處理在何處分裂的問(wèn)題。分類回歸樹(shù)(CART,Classification And Regression Tree)也屬于一種決策樹(shù)，結(jié)構(gòu)為二叉樹(shù)。
CART-Tree 的特點(diǎn)
- CART中用于選擇變量的不純性度量是Gini指數(shù)；
- 如果目標(biāo)變量是標(biāo)稱的，并且是具有兩個(gè)以上的類別，則CART可能考慮將目標(biāo)類別合并成兩個(gè)超類別（雙化）；
- 如果目標(biāo)變量是連續(xù)的，則CART算法找出一組基于樹(shù)的回歸方程來(lái)預(yù)測(cè)目標(biāo)變量。
1、從根節(jié)點(diǎn)t=1開(kāi)始，從所有可能候選S集合中搜索使不純性降低最大的劃分S，然后，使用劃分S將節(jié)點(diǎn)1（t=1）劃分成兩個(gè)節(jié)點(diǎn)t=2和t=3；
2、在t=2和t=3上分別重復(fù)劃分搜索過(guò)程。
基尼不純度指標(biāo)
在CART算法中, 基尼不純度表示一個(gè)隨機(jī)選中的樣本在子集中被分錯(cuò)的可能性?；岵患兌葹檫@個(gè)樣本被選中的概率乘以它被分錯(cuò)的概率。當(dāng)一個(gè)節(jié)點(diǎn)中所有樣本都是一個(gè)類時(shí)，基尼不純度為零。
剪枝
其實(shí)剪枝的準(zhǔn)則是如何確定決策樹(shù)的規(guī)模，可以參考的剪枝思路有以下幾個(gè)：
1：使用訓(xùn)練集合(Training Set）和驗(yàn)證集合(Validation Set)，來(lái)評(píng)估剪枝方法在修剪結(jié)點(diǎn)上的效用
2：使用所有的訓(xùn)練集合進(jìn)行訓(xùn)練，但是用統(tǒng)計(jì)測(cè)試來(lái)估計(jì)修剪特定結(jié)點(diǎn)是否會(huì)改善訓(xùn)練集合外的數(shù)據(jù)的評(píng)估性能，如使用Chi-Square（Quinlan，1986）測(cè)試來(lái)進(jìn)一步擴(kuò)展結(jié)點(diǎn)是否能改善整個(gè)分類數(shù)據(jù)的性能，還是僅僅改善了當(dāng)前訓(xùn)練集合數(shù)據(jù)上的性能。
3：使用明確的標(biāo)準(zhǔn)來(lái)衡量訓(xùn)練樣例和決策樹(shù)的復(fù)雜度，當(dāng)編碼長(zhǎng)度最小時(shí)，停止樹(shù)增長(zhǎng)，如MDL(Minimum Description Length)準(zhǔn)則。
1、Reduced-Error Pruning(REP,錯(cuò)誤率降低剪枝）
該剪枝方法考慮將書(shū)上的每個(gè)節(jié)點(diǎn)作為修剪的候選對(duì)象，決定是否修剪這個(gè)結(jié)點(diǎn)有如下步驟組成：
1：刪除以此結(jié)點(diǎn)為根的子樹(shù)
2：使其成為葉子結(jié)點(diǎn)
3：賦予該結(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練數(shù)據(jù)的最常見(jiàn)分類
4：當(dāng)修剪后的樹(shù)對(duì)于驗(yàn)證集合的性能不會(huì)比原來(lái)的樹(shù)差時(shí)，才真正刪除該結(jié)點(diǎn)
因?yàn)橛?xùn)練集合的過(guò)擬合，使得驗(yàn)證集合數(shù)據(jù)能夠?qū)ζ溥M(jìn)行修正，反復(fù)進(jìn)行上面的操作，從底向上的處理結(jié)點(diǎn)，刪除那些能夠最大限度的提高驗(yàn)證集合的精度的結(jié)點(diǎn)，直到進(jìn)一步修剪有害為止(有害是指修剪會(huì)減低驗(yàn)證集合的精度)
REP是最簡(jiǎn)單的后剪枝方法之一，不過(guò)在數(shù)據(jù)量比較少的情況下，REP方法趨于過(guò)擬合而較少使用。這是因?yàn)橛?xùn)練數(shù)據(jù)集合中的特性在剪枝過(guò)程中被忽略，所以在驗(yàn)證數(shù)據(jù)集合比訓(xùn)練數(shù)據(jù)集合小的多時(shí)，要注意這個(gè)問(wèn)題。
盡管REP有這個(gè)缺點(diǎn)，不過(guò)REP仍然作為一種基準(zhǔn)來(lái)評(píng)價(jià)其它剪枝算法的性能。它對(duì)于兩階段決策樹(shù)學(xué)習(xí)方法的優(yōu)點(diǎn)和缺點(diǎn)提供了了一個(gè)很好的學(xué)習(xí)思路。由于驗(yàn)證集合沒(méi)有參與決策樹(shù)的創(chuàng)建，所以用REP剪枝后的決策樹(shù)對(duì)于測(cè)試樣例的偏差要好很多，能夠解決一定程度的過(guò)擬合問(wèn)題。
2、Pessimistic Error Pruning(PEP，悲觀剪枝）
先計(jì)算規(guī)則在它應(yīng)用的訓(xùn)練樣例上的精度，然后假定此估計(jì)精度為二項(xiàng)式分布，并計(jì)算它的標(biāo)準(zhǔn)差。對(duì)于給定的置信區(qū)間，采用下界估計(jì)作為規(guī)則性能的度量。這樣做的結(jié)果，是對(duì)于大的數(shù)據(jù)集合，該剪枝策略能夠非常接近觀察精度，隨著數(shù)據(jù)集合的減小，離觀察精度越來(lái)越遠(yuǎn)。該剪枝方法盡管不是統(tǒng)計(jì)有效的，但是在實(shí)踐中有效。
PEP為了提高對(duì)測(cè)試集合的預(yù)測(cè)可靠性，PEP對(duì)誤差估計(jì)增加了連續(xù)性校正(Continuity Correction)
PEP算法是唯一使用Top-Down剪枝策略，這種策略會(huì)導(dǎo)致與先剪枝出現(xiàn)同樣的問(wèn)題，將該結(jié)點(diǎn)的某子節(jié)點(diǎn)不需要被剪枝時(shí)被剪掉；另外PEP方法會(huì)有剪枝失敗的情況出現(xiàn)。
雖然PEP方法存在一些局限性，但是在實(shí)際應(yīng)用中表現(xiàn)出了較高的精度,。兩外PEP方法不需要分離訓(xùn)練集合和驗(yàn)證機(jī)和，對(duì)于數(shù)據(jù)量比較少的情況比較有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因?yàn)樵诩糁^(guò)程中，樹(shù)中的每顆子樹(shù)最多需要訪問(wèn)一次，在最壞的情況下，它的計(jì)算時(shí)間復(fù)雜度也只和非剪枝樹(shù)的非葉子節(jié)點(diǎn)數(shù)目成線性關(guān)系。
Cost-Complexity Pruning(CCP、代價(jià)復(fù)雜度)
CCP方法包含兩個(gè)步驟：
1：從原始決策樹(shù)T0開(kāi)始生成一個(gè)子樹(shù)序列{T0、T1、T2、...、Tn},其中Ti+1是從Ti總產(chǎn)生，Tn為根節(jié)點(diǎn)
2：從子樹(shù)序列中，根據(jù)樹(shù)的真實(shí)誤差估計(jì)選擇最佳決策樹(shù)。
剪枝過(guò)程特別重要，所以在最優(yōu)決策樹(shù)生成過(guò)程中占有重要地位。有研究表明，剪枝過(guò)程的重要性要比樹(shù)生成過(guò)程更為重要，對(duì)于不同的劃分標(biāo)準(zhǔn)生成的最大樹(shù)(Maximum Tree)，在剪枝之后都能夠保留最重要的屬性劃分，差別不大。反而是剪枝方法對(duì)于最優(yōu)樹(shù)的生成更為關(guān)鍵。
