決策樹學(xué)習(xí)的剪枝方法

王曉

摘要：決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法，對噪音數(shù)據(jù)有很好的健壯性且能夠?qū)W習(xí)淺析表達(dá)式。本論文主要介紹決策樹學(xué)習(xí)的剪枝方法以及評價一棵決策樹優(yōu)劣的標(biāo)準(zhǔn)。

關(guān)鍵詞：決策樹學(xué)習(xí) 決策樹學(xué)習(xí)的剪枝方法

1 簡述

在決策樹的生成過程中，如果對每一個分支都一直增長到恰好對訓(xùn)練樣例完美地分類，這個策略并非總行的通的。事實上，當(dāng)數(shù)據(jù)中有噪音或訓(xùn)練樣例的數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣時，這個策略會遇到困難。

對于一個假設(shè)，當(dāng)存在其他的假設(shè)對訓(xùn)練樣例的擬合比它差，但事實上在實例的整個分布上卻表現(xiàn)的更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例。

圖1描述了決策樹學(xué)習(xí)的一個典型應(yīng)用中過度擬合的影響。在這個例子中，ID3算法用來學(xué)習(xí)哪一種病人患有糖尿病。這副圖的橫軸表示決策樹建造中樹的結(jié)點總數(shù)，縱軸表示決策樹做出的預(yù)測精度。實線表示決策樹在訓(xùn)練樣例上的精度，虛線表示在一套獨立測試樣例（沒有被包含在訓(xùn)練樣例中）上測量出的精度。可以看出，隨著樹的增長，在訓(xùn)練樣例上的精度是單調(diào)上升的，然而，在獨立的測試樣例上測出的精度先上升后下降。說明對樹的進(jìn)一步精化盡管可以提高它在訓(xùn)練數(shù)據(jù)上的精度，卻降低了它在測試樣例上的精度。

過度擬合對于決策樹學(xué)習(xí)和其他一些學(xué)習(xí)算法是一個重要的實踐難題，在決策樹學(xué)習(xí)中解決這個問題的途徑主要是對決策樹進(jìn)行修剪，有兩種修剪方法：預(yù)修剪和后修剪。

2 決策樹的后修剪學(xué)習(xí)算法

后修剪算法已經(jīng)得到了廣泛的應(yīng)用，在這個算法中輸入為一個未經(jīng)修剪的決策樹，輸出為對它剪枝之后的決策樹，這棵樹是將原樹中一個或幾個子樹刪除所得的結(jié)果。剪枝過程中，將一些子樹刪除用一些葉結(jié)點來代替，這個葉結(jié)點所屬的類用這棵子樹中大多數(shù)訓(xùn)練實例所屬的類代替，并且在相應(yīng)的葉子上標(biāo)記出所屬這個類的訓(xùn)練實例所占的比例。

經(jīng)過剪枝的決策樹，對訓(xùn)練樣例的錯誤率已經(jīng)不為0，但由于在這種剪枝算法當(dāng)中位于底層的子樹將被優(yōu)先剪掉，這些結(jié)點包含的實例很少，所以這種方法將減少噪音對決策樹構(gòu)造的影響。

后修剪算法有兩種可能的剪枝策略，一種是自上而下的，一種是自下而上的。自下而上的算法是首先在最低層的內(nèi)結(jié)點開始剪枝，剪去那些滿足一定標(biāo)準(zhǔn)的內(nèi)結(jié)點，生成新的決策樹，然后在新的決策樹上遞歸調(diào)用這個算法，直到?jīng)]有新的結(jié)點可以剪枝為止。而與之相反，自上而下的算法是從根結(jié)點開始向下逐個考慮每個結(jié)點是否應(yīng)該被剪枝。

后修剪的算法很多，這兒介紹兩種比較常用的方法：錯誤率降低后修剪和規(guī)則后修剪。

（1） 錯誤率降低后修剪

錯誤率降低后修剪是一種自上而下的修剪方法，修剪過程由以下步驟組成：刪除以此結(jié)點為根的子樹；使它成為葉結(jié)點；把和該結(jié)點關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它。僅當(dāng)修剪后的樹對于驗證集合的性能不比原樹差時才刪除該結(jié)點。

如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來引導(dǎo)修剪是一個有效的方法.這個方法的主要缺點是當(dāng)數(shù)據(jù)有限時，從中保留一部分用作驗證集進(jìn)一步減少了訓(xùn)練可以使用的樣例。下面的這種方法在數(shù)據(jù)有限的許多實際情形下，也是有效的。

（2） 規(guī)則后修剪

規(guī)則后修剪是實踐中一種發(fā)現(xiàn)高精度假設(shè)的非常成功的方法，這種方法的一個變體被成功的應(yīng)用到C4.5系統(tǒng)中。規(guī)則后修剪包括下面的步驟：

1）從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地擬合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生；

2）將決策樹轉(zhuǎn)化為等價的規(guī)則集，方法是從根結(jié)點到葉結(jié)點的每一條路徑創(chuàng)建一條規(guī)則；

3）通過刪除任何能導(dǎo)致估計精度提高的前件來修剪每一條規(guī)則；

4）按照修剪過的規(guī)則的估計精度對它們進(jìn)行排序，并按照這樣的順序應(yīng)用這些規(guī)則來分類后來的實例。

為什么修剪以前要把決策樹轉(zhuǎn)化成規(guī)則集呢？這樣做主要有三個好處：

1）轉(zhuǎn)化為規(guī)則集可以區(qū)分決策結(jié)點使用的不同上下文。因為貫穿決策結(jié)點的每條不同路徑產(chǎn)生一條不同的規(guī)則，所以對于不同路徑，關(guān)于一個屬性測試的修剪決策可以不同。相反如果直接修剪樹本身，只有兩個選擇，要么完全刪除決策結(jié)點，要么保留它的本來狀態(tài)。

2）轉(zhuǎn)化為規(guī)則集消除了根結(jié)點附近的屬性測試和葉結(jié)點附件的屬性測試的區(qū)別。于是避免了凌亂的記錄問題，比如，若是根結(jié)點被修剪了保留它下面的部分子樹時如何保留它下面的部分子樹時如何重新組織這棵樹。

3）轉(zhuǎn)化為規(guī)則集可以提高可讀性。對人來說規(guī)則總是更容易理解的。

3 決策樹預(yù)修剪學(xué)習(xí)算法

在生成一棵完整決策樹的算法中都要求每一個葉結(jié)點中的訓(xùn)練實例都屬于同一個類或者已經(jīng)沒有屬性可供選擇作為算法停止條件。然而在預(yù)修剪算法中，并不使用這個標(biāo)準(zhǔn)，而是在這個標(biāo)準(zhǔn)得到滿足之前就停止繼續(xù)擴展決策樹。具體在什么時候停止決策樹的擴張就成為這種方法的主要研究內(nèi)容。

一種最為簡單的方法就是在決策樹達(dá)到一定高度的情況下就停止決策樹的擴張，這種停止標(biāo)準(zhǔn)在一定情況下能夠取得比較好的效果。更為普遍的做法是計算每次擴張對系統(tǒng)性能的增益，如果這個增益值小于某個閾值則不進(jìn)行擴展，即使葉結(jié)點的實例不屬于同一類。一般情況下，作為判斷是否停止擴張決策樹的增益的選擇標(biāo)準(zhǔn)，與每次擴展時選擇測試屬性的標(biāo)準(zhǔn)相同。

如何尋找停止決策樹擴張的標(biāo)準(zhǔn)一直是決策樹預(yù)修剪學(xué)習(xí)算法的一個難點問題，它限制了這種方法的廣泛應(yīng)用，同時與信息增益進(jìn)行比較的那個閾值需要人為的確定，這就需要人們的先驗知識和專家領(lǐng)域知識。這樣就降低了學(xué)習(xí)過程的智能性，況且有時這些先驗知識是很難獲得或者根本不能獲取的。

4 決策樹學(xué)習(xí)算法的評價

決策樹的各種學(xué)習(xí)算法各有優(yōu)缺點，它們的優(yōu)缺點又是怎么評價的呢？下面給出幾種評價決策樹的一些量化的評價標(biāo)準(zhǔn)[6]。

（1） 過學(xué)習(xí)

過學(xué)習(xí)也就是前面提到的學(xué)習(xí)過程中的過度擬合問題。一個好的算法生成的決策樹應(yīng)該出現(xiàn)過學(xué)習(xí)現(xiàn)象的程度比較小。

（2） 有效性

最為直接的估計一棵決策樹在測試實例集合上的性能的方法是，將它在測試實例集合上進(jìn)行測試，但這是不現(xiàn)實的。一般采用訓(xùn)練實例集本身來估計訓(xùn)練算法的有效性，一種最簡單的方法是用訓(xùn)練集的一部分（例如2/3的訓(xùn)練實例）對決策樹進(jìn)行訓(xùn)練，而用另一部分（例如1/3的訓(xùn)練實例）對決策樹檢測其有效性。但這樣往往減小訓(xùn)練實例空間，而增大了學(xué)習(xí)中過度擬合的可能性。一般采用下面兩種方法來評測一個決策樹學(xué)習(xí)系統(tǒng)的有效性。

（3） 交叉有效性

在此方法中，我們將訓(xùn)練實例T分為互不相交且大小相等的k個子集T1，T2， ……， Tk。對任意子集Ti，用T-Ti訓(xùn)練決策樹，用對生成的決策樹進(jìn)行測試，得到錯誤率ei，然后估計整個算法的錯誤率：

.

（4） 余一有效性

這種有效性的度量與交叉有效性類似，不同之處在于將每個Ti的大小定為1。假設(shè)|T|=n，則整個算法的錯誤率為：

.

（5） 決策樹的復(fù)雜程度

決策樹的復(fù)雜程度也是度量決策樹學(xué)習(xí)效果的一個重要標(biāo)準(zhǔn)。如果決策樹是單變量的，那么決策樹的復(fù)雜程度主要由樹的結(jié)點個數(shù)決定；如果是多變量的，則主要由結(jié)點中屬性的總個數(shù)決定。

綜合上面的5種評價標(biāo)準(zhǔn)，前面的4個標(biāo)準(zhǔn)可以用測試錯誤率或者測試正確率來體現(xiàn)，這樣我們可以把衡量決策樹性能的標(biāo)準(zhǔn)總結(jié)為兩個：決策樹的測試錯誤率（或者測試正確率）以及決策樹的復(fù)雜程度。

5 總結(jié)

本論文主要從決策樹學(xué)習(xí)的修剪方法介紹了決策樹學(xué)習(xí)算法的工作過程，然后給出了評價一棵決策樹優(yōu)劣的標(biāo)準(zhǔn)。

參考文獻(xiàn)

[1]史忠植，知識發(fā)現(xiàn)[M].北京：清華大學(xué)出版社，2012.