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

一、在決策樹完美分割學(xué)習(xí)樣例之前，停止決策樹的生長。這種提早停止樹生長的方法，稱為預(yù)剪枝方法。

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

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í)由于生長不足，導(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ù)剪枝方法雖然原理簡單，但是在實(shí)際應(yīng)用中，閾值a的選擇存在相當(dāng)大的主觀性。如何精確的給出適當(dāng)?shù)拈撝礱以獲得適當(dāng)規(guī)模的決策樹是十分困難的。

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)志。

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ù)雜度為

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