決策樹的后期修剪技術

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

2、assificationproblems.Aproblemthatdecisiontreefacesistorealizebothaccuracysimplificationsoitmustturntotreepruningtechnology.Thearticlesummarizesdiscussessomepostpruningtechnologywhichaimstoprovideaconciseviewofpostpruning

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

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

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

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

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

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

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

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

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