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

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

2、assificationproblems.Aproblemthatdecisiontreefacesistorealizebothaccuracysimplificationsoitmustturntotreepruningtechnology.Thearticlesummarizesdiscussessomepostpruningtechnologywhichaimstoprovideaconciseviewofpostpruning

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

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

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

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

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

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

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

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

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