王曉

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

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

1 簡(jiǎn)述

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

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

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

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

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

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

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

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

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

（1） 錯(cuò)誤率降低后修剪

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2） 有效性

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

（3） 交叉有效性

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

.

（4） 余一有效性

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

.

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

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

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

5 總結(jié)

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

參考文獻(xiàn)

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