決策樹的后期修剪技術(shù)

1、決策樹的后期修剪技術(shù)決策樹的后期修剪技術(shù)北方交通大學(xué)姜海摘要：摘要：決策樹是對分類任務(wù)進(jìn)行深入研究的一種解決方案，決策樹面臨的一個(gè)重要問題是，在確保決策精確的同時(shí)，又要使樹簡單和易于理解，這就需要借助于樹的修剪技術(shù)。本文總結(jié)和評價(jià)了一些常用的后期修剪技術(shù)，目的在于提供一個(gè)清晰、詳細(xì)的后期修剪技術(shù)視圖。關(guān)鍵詞：關(guān)鍵詞：決策樹、后期修剪、狀態(tài)空間搜索Abstract:Decisiontreeisawidelyusedsolutiontocl

2、assificationproblems.Aproblemthatdecisiontreefacesistorealizebothaccuracysimplificationsoitmustturntotreepruningtechnology.Thearticlesummarizesdiscussessomepostpruningtechnologywhichaimstoprovideaconciseviewofpostpruning

3、technology.Keywds:DecisionTree、PostPruning、StateSpaceSearch引言引言總結(jié)樹修剪技術(shù)的關(guān)鍵問題在于解決方法的多樣性。要駕御這種多樣性，可以將這些方法分為五類。類的建立是將樹歸納看作是對預(yù)想樹空間的即席狀態(tài)搜索。第一類中的方法直接控制樹的大小，如前期修剪或后期修剪等，這些方法是通過對樹的二次搜索完成的。第二類中技術(shù)側(cè)重于狀態(tài)（即樹）的搜索空間。第三類中主要是調(diào)整搜索規(guī)則本身。第四類通

4、過在搜索進(jìn)程中不考慮某些事例或事例特征來限制數(shù)據(jù)庫。最后一類通過轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)來簡化樹，如轉(zhuǎn)換成決策表或決策圖。在決策樹的分類框架中，最常用的是直接控制樹的大小，包括前期修剪和后期修剪等，下面將詳細(xì)介紹這類修剪技術(shù)中的后期修剪。一、后期修剪技術(shù)概述一、后期修剪技術(shù)概述由于前期修剪會引起樹在不完全成熟之前停止，即樹可能在不應(yīng)停止時(shí)停止擴(kuò)展（hizon效應(yīng)），為避免hizon效應(yīng)，許多研究人員將目光轉(zhuǎn)向后期修剪技術(shù)。后期修剪算法輸入一個(gè)未修剪

5、的樹T，輸出修剪了T中一個(gè)或多個(gè)子樹后獲得的樹T’。算法并非搜索每個(gè)可能的T’，而是借助于啟發(fā)式搜索減少搜索量。修剪將子樹轉(zhuǎn)化為葉，進(jìn)而用葉節(jié)點(diǎn)替代內(nèi)部節(jié)點(diǎn)。與前期修剪不同的是，后期修剪沒有使用一個(gè)消除細(xì)節(jié)的函數(shù)，而是直接采用默認(rèn)的同質(zhì)暫停規(guī)則。如果決策樹采用同質(zhì)暫停規(guī)則，將不會產(chǎn)生替代錯(cuò)誤，因而，修剪僅僅會削弱訓(xùn)練集中替代精確度。然而，當(dāng)樹相對培訓(xùn)集冗余時(shí)（即噪聲參與了建模時(shí)），修剪將非常有效地提高精確度。例如，給定培訓(xùn)集m，假設(shè)包含

6、培訓(xùn)集n的葉節(jié)點(diǎn)類標(biāo)簽為多數(shù)滿足n’〈=n，則替代錯(cuò)誤率為（nn’）m，低層葉節(jié)點(diǎn)對替代精確度的影響最小，因而被最先修剪。后期修剪方法借助于多種評價(jià)函數(shù)，用以確定修剪一個(gè)節(jié)點(diǎn)是削弱還是增強(qiáng)了事例集的精確度。修剪是是可以提高分類的精確度的，尤其是當(dāng)培訓(xùn)集噪聲級別比較高時(shí)，修剪相當(dāng)有效。有些后期修剪方法將培訓(xùn)集分為兩個(gè)子集。一個(gè)用于生成樹，另一個(gè)用于后期修剪，不妨成之為生成集和修剪集。生成集常用于生成一個(gè)樹，然后，按2、排錯(cuò)修剪（排錯(cuò)修剪（

7、REP）REP，作為ID3系統(tǒng)的一部分，也使用修剪集。MCCP在樹歸納和修剪過程中均應(yīng)用生長集，而RPE則僅在歸納時(shí)應(yīng)用，在生成和評價(jià)修剪樹時(shí)應(yīng)用修剪集。RPE自下而上修剪樹，不降低修剪集的精確度。REP可以在修剪集的基礎(chǔ)上，生成最小的樹，而且錯(cuò)誤率最低。RPE方法不但在精確度方面與其它方法不相上下，而且比大多數(shù)方法生成的樹要小。3、最小錯(cuò)誤修剪（最小錯(cuò)誤修剪（MEP）MEP方法基于生長集計(jì)算內(nèi)部節(jié)點(diǎn)的錯(cuò)誤概率，參數(shù)m確定一個(gè)類對錯(cuò)誤計(jì)

8、算的影響，MEP自下而上檢查內(nèi)部節(jié)點(diǎn)，如果子樹產(chǎn)生的錯(cuò)誤大于用葉來替代它產(chǎn)生的錯(cuò)誤，就剪掉子樹。當(dāng)m取不同的值時(shí)，MEP可以生成一個(gè)修剪樹集，再由領(lǐng)域?qū)＜掖_定其中最好的樹。目前設(shè)計(jì)的自選樹的方案是選擇最小的和錯(cuò)誤率最低的樹。MEP屬于不徹底修剪，但精確度不比其它方法遜色。4、關(guān)鍵值修剪（關(guān)鍵值修剪（CVP）CVP方法可以選擇地使用修剪集，包括兩步：首先，針對測試集選擇參數(shù)cv（關(guān)鍵值）。在自下而上的修剪過程中，若評價(jià)函數(shù)取值小于或等于關(guān)

9、鍵值，則包含事例集和測試集的節(jié)點(diǎn)將被修剪掉。選擇不同的關(guān)鍵值重復(fù)進(jìn)行這一過程，則會得到一個(gè)修剪樹集。其次，從樹集中選擇一個(gè)最好的樹，主要考慮決策精度和重要程度，通常借助于統(tǒng)計(jì)表完成，但統(tǒng)計(jì)表難以用于比較不同樹之間的“相關(guān)重要性”。也有人認(rèn)為概率測度是不合理的，應(yīng)借助于修剪集測試CVP。CVP屬于不徹底修剪，精確度不高。5、保守錯(cuò)誤修剪（、保守錯(cuò)誤修剪（PEP）PEP算法的出現(xiàn)與ID3相關(guān)，像MCCP的CV變量一樣不用修剪集。PEP強(qiáng)加了

10、一個(gè)糾正機(jī)制，以盡量減少錯(cuò)誤，而且，子樹都建立在應(yīng)該被修剪的假設(shè)前提下，除非其錯(cuò)誤估計(jì)至少比根節(jié)點(diǎn)錯(cuò)誤估計(jì)少一個(gè)標(biāo)準(zhǔn)錯(cuò)誤。盡管PEP算法在測試中最精確，但仍有其局限性。PEP是唯一一種采取自頂向下修剪策略的算法，它面臨著與前期修剪同樣的問題：樹在某節(jié)點(diǎn)被剪掉，而其子樹不應(yīng)按同一規(guī)則被剪掉。其次，PEP有時(shí)不會作修剪工作，即使是對隨機(jī)數(shù)據(jù)。第三，將創(chuàng)建樹的數(shù)據(jù)樣本看作是隨機(jī)樣本是不合適的，盡管這些局限性，PEP仍保持了高的精確度，自頂向下

11、的修剪策略也要比其它方法高效。6、基于錯(cuò)誤的修剪（、基于錯(cuò)誤的修剪（EBP）EBP用于ID3的子類C4.5，是PEP的一個(gè)子類。EBP算法事先定義節(jié)點(diǎn)的培訓(xùn)數(shù)據(jù)集、占優(yōu)勢的類、以及不屬于此類的事例集，EBP將培訓(xùn)數(shù)據(jù)集作為一個(gè)分布樣本，在適當(dāng)?shù)募s束下，估計(jì)節(jié)點(diǎn)的錯(cuò)誤率，并將之作為子類概率分布的上限。另外，EBP新增一個(gè)修剪操作，該操作允許用節(jié)點(diǎn)的子樹替代此節(jié)點(diǎn)。保留好的節(jié)點(diǎn)，而將其父節(jié)點(diǎn)修剪，這就減少了EBP受hizon效應(yīng)的影響，擴(kuò)展