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

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

2、assificationproblems.Aproblemthatdecisiontreefacesistorealizebothaccuracysimplificationsoitmustturntotreepruningtechnology.Thearticlesummarizesdiscussessomepostpruningtechnologywhichaimstoprovideaconciseviewofpostpruning

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

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

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

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

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

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

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

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

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