決策樹剪枝的方法與必要性

1 決策樹剪枝的必要性

本文討論的決策樹主要是基于ID3算法實(shí)現(xiàn)的離散決策樹生成。ID3算法的基本思想是貪心算法，采用自上而下的分而治之的方法構(gòu)造決策樹。首先檢測(cè)訓(xùn)練數(shù)據(jù)集的所有特征，選擇信息增益最大的特征A建立決策樹根節(jié)點(diǎn)，由該特征的不同取值建立分枝，對(duì)各分枝的實(shí)例子集遞歸，用該方法建立樹的節(jié)點(diǎn)和分枝，直到某一子集中的數(shù)據(jù)都屬于同一類別，或者沒有特征可以在用于對(duì)數(shù)據(jù)進(jìn)行分割。ID3算法總是選擇具有最高信息增益(或最大熵壓縮)的屬性作為當(dāng)前結(jié)點(diǎn)的測(cè)試屬性。該屬性使得結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性或“不純性”。這種信息理論方法使得對(duì)一個(gè)對(duì)象分類所需的期望測(cè)試數(shù)目達(dá)到最小，并盡量確保一棵簡(jiǎn)單的(但不必是最簡(jiǎn)單的)樹來刻畫相關(guān)的信息。

在ID3算法中，計(jì)算信息增益時(shí)，由于信息增益存在一個(gè)內(nèi)在偏置，它偏袒具有較多值的屬性，太多的屬性值把訓(xùn)練樣例分割成非常小的空間。因此，這個(gè)屬性可能會(huì)有非常高的信息增益，而且被選作樹的根結(jié)點(diǎn)的決策屬性，并形成一棵深度只為一級(jí)但卻非常寬的樹，這棵樹可以理想地分類訓(xùn)練數(shù)據(jù)。但是這個(gè)決策樹對(duì)于測(cè)試數(shù)據(jù)的分類性能可能會(huì)相當(dāng)差，因?yàn)樗^分地完美地分割了訓(xùn)練數(shù)據(jù)，不是一個(gè)好的分類器。

在J.Mingers關(guān)于ID3算法的研究中，通過對(duì)五種包含噪音的學(xué)習(xí)樣例的實(shí)驗(yàn)發(fā)現(xiàn)，多數(shù)情況下過度擬合導(dǎo)致決策樹的精度降低了10%一25%。過度擬合不僅影響決策樹對(duì)未知實(shí)例的分類精度，而且還會(huì)導(dǎo)致決策樹的規(guī)模增大。一方面，葉子節(jié)點(diǎn)隨分割不斷增多。在極端的情況下，在一棵完成分割的決策樹中，每個(gè)葉子節(jié)點(diǎn)中只包含一個(gè)實(shí)例。此時(shí)決策樹在學(xué)習(xí)樣例上的分類精度達(dá)到100%，而其葉子節(jié)點(diǎn)的數(shù)目等于學(xué)習(xí)樣例中實(shí)例的數(shù)目。但是顯然這棵決策樹對(duì)任何未見的實(shí)例都是毫無意義的。另一方面，決策樹不斷向下生長(zhǎng)，導(dǎo)致樹的深度增加。因?yàn)槊恳粭l自根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑都對(duì)應(yīng)一條規(guī)則，所以樹的深度越大，其對(duì)應(yīng)的規(guī)則越長(zhǎng)。作為一種蘊(yùn)含于學(xué)習(xí)樣例中的知識(shí)，這樣一組過長(zhǎng)的規(guī)則集合是很難被人理解的。過度擬合現(xiàn)象的存在，無論是對(duì)決策樹的分類精度，還是對(duì)其規(guī)模以及可理解性都產(chǎn)生了不利的影響。因此對(duì)與決策樹的剪枝是非常有必要的。

2 決策樹剪枝的方法

一般情況下可以使用如下兩類方法來減小決策樹的規(guī)模:

(l)在決策樹完美分割學(xué)習(xí)樣例之前，停止決策樹的生長(zhǎng)。這種提早停止樹生長(zhǎng)的

方法，稱為預(yù)剪枝方法。

(2)與預(yù)剪枝方法盡量避免過度分割的思想不同，一般情況下即使決策樹可能出現(xiàn)過度擬合現(xiàn)象，算法依然允許其充分生長(zhǎng)。在決策樹完全生長(zhǎng)之后，通過特定標(biāo)準(zhǔn)去掉原決策樹中的某些子樹。通常稱這種方法為后剪枝方法。

2.1 預(yù)剪枝方法

預(yù)剪枝方法實(shí)際上是對(duì)決策樹停止標(biāo)準(zhǔn)的修改。在原始的ID3算法中，節(jié)點(diǎn)的分割一直到節(jié)點(diǎn)中的實(shí)例屬于同一類別時(shí)才停止。對(duì)于包含較少實(shí)例的節(jié)點(diǎn)，可能被分割為單一實(shí)例節(jié)點(diǎn)。為了避免這種情況，我們給出一個(gè)停止閾值a。當(dāng)由一個(gè)節(jié)點(diǎn)分割導(dǎo)致的最大的不純度下降小于a時(shí)，就把該節(jié)點(diǎn)看作是一個(gè)葉子節(jié)點(diǎn)。在該方法中，閾值a的選擇對(duì)決策樹具有很大的影響。當(dāng)閾值a選擇過大時(shí)，節(jié)點(diǎn)在不純度依然很高時(shí)就停止分割了。此時(shí)由于生長(zhǎng)不足，導(dǎo)致決策樹過小，分類的錯(cuò)誤率過高。假設(shè)在一個(gè)兩類問題中，根節(jié)點(diǎn)Root一共包含100個(gè)學(xué)習(xí)樣例，其中正例和負(fù)例均為50。并且使用屬性b可以將正例與負(fù)例完全分開，即決策樹在學(xué)習(xí)樣例上的分類精度R(T)=100%。由信息增益公式可知，使用屬性b分割節(jié)點(diǎn)可以得到不純度下降的最大值0.5。如果設(shè)a=0.7，因?yàn)镚ain(Root，a)=0.5<0.7，所以根節(jié)點(diǎn)Root不需要分割。此時(shí)導(dǎo)致決策樹在學(xué)習(xí)樣例上的分類精度下降為R(T)=50%。當(dāng)閾值a選擇過小時(shí)，例如a近似為0，節(jié)點(diǎn)的分割過程近似等同于原始的分割過程。由此可見，預(yù)剪枝方法雖然原理簡(jiǎn)單，但是在實(shí)際應(yīng)用中，閾值a的選擇存在相當(dāng)大的主觀性。如何精確的給出適當(dāng)?shù)拈撝礱以獲得適當(dāng)規(guī)模的決策樹是十分困難的。

2.2后剪枝方法

決策樹是一種樹形結(jié)構(gòu)。一棵樹是一個(gè)或者多個(gè)節(jié)點(diǎn)的有限集合T，使得

1.有一個(gè)特別指定的節(jié)點(diǎn)，叫做樹的根節(jié)點(diǎn);

2.除根節(jié)點(diǎn)以外，剩余的節(jié)點(diǎn)被劃分成m>=0個(gè)不相交的集合Tl，…，Tm，而且每一個(gè)集合也都是樹。樹Tl，…，Tm稱為這個(gè)根節(jié)點(diǎn)的子樹。根據(jù)上述樹的定義，可以直觀地將決策樹的后剪枝看作是去掉某些子樹中除根節(jié)點(diǎn)外所有節(jié)點(diǎn)的過程，如圖1所示。移除子樹后，還需要對(duì)新生成的葉子節(jié)點(diǎn)賦予一個(gè)類別標(biāo)志，一般是葉子節(jié)點(diǎn)中所占比例最大的類別標(biāo)志。

圖1 決策樹剪枝過程

2.3代價(jià)復(fù)雜度剪枝

代價(jià)復(fù)雜度剪枝過程分成兩個(gè)階段:第一階段，首先由原決策樹通過某種剪枝策略生成一系列決策樹T0，Tl，…，Tk。其中T。是由決策樹生成算法推導(dǎo)出來的屬性決策樹，Ti十1是依次刪除Ti的一棵或者多棵后生成的。重復(fù)此過程，直到最后的決策樹Tk只含有一個(gè)葉子結(jié)點(diǎn)。

第二階段，我們對(duì)上一階段得到的決策樹進(jìn)行評(píng)估，最終選擇一棵最好的作為剪枝后的決策樹。

考慮包含N個(gè)樣例的訓(xùn)練集合，通過決策樹生成算法，如ID3，我們可以推導(dǎo)出一棵屬性決策樹。假定這棵決策樹會(huì)將其中的E個(gè)樣例錯(cuò)誤分類，再定義L(T)是決策樹T中葉子結(jié)點(diǎn)的數(shù)目，L.Breiman等人定義決策樹T的代價(jià)復(fù)雜度為

對(duì)決策樹T的一棵子樹S，我們將能劃分到子樹S中的所有樣例的最普遍類別標(biāo)簽稱之為最可能葉子。從原決策樹T。開始，為了從決策樹Ti產(chǎn)生Ti十1，我們遍歷每一個(gè)非葉子子樹Ti來找到最小的a值，用子樹中最可能葉子代替一棵或多棵值為a的子樹。

在第二階段，我們從上一階段生成的一系列決策樹中，以可靠性為標(biāo)準(zhǔn)找出一棵最好的決策樹。如果繼續(xù)使用生成決策樹時(shí)的訓(xùn)練樣例集合對(duì)決策樹的錯(cuò)誤率進(jìn)行評(píng)估，觀察錯(cuò)誤率可能過于樂觀，也就是說，對(duì)于未見樣例的錯(cuò)誤率可能高于此值。因此，我們使用一個(gè)單獨(dú)的測(cè)試樣例集合，其中包含N’個(gè)樣例，用于估計(jì)對(duì)子樹Ti的分類錯(cuò)誤率。假設(shè)E’是所有子樹Ti中最小的觀察錯(cuò)誤率，定義E’的標(biāo)準(zhǔn)錯(cuò)誤為

最后我們從所有子樹中選擇觀察錯(cuò)誤數(shù)不超過E’+se伍’)中最小的子樹，作為剪枝后的子樹。