決策樹過擬合.doc

決策樹學(xué)習(xí)的過擬合問題姓名：專業(yè)：通信與信號系統(tǒng)學(xué)號：一 決策樹學(xué)習(xí)簡介決策樹學(xué)習(xí)是一種逼近離散值目標(biāo)函數(shù)的方法，這種方法將從一組訓(xùn)練數(shù)據(jù)中學(xué)習(xí)到的函數(shù)表示為一棵決策樹。決策樹葉子為類別名，其他的結(jié)點(diǎn)由實(shí)體的特征組成，每個(gè)特征的不同取值對應(yīng)一個(gè)分枝。若要對一個(gè)實(shí)體分類，從樹根開始進(jìn)行測試，按特征的取值向下進(jìn)入新結(jié)點(diǎn)，對新結(jié)點(diǎn)進(jìn)行測試，過程一直進(jìn)行到葉結(jié)點(diǎn)，實(shí)例被判為屬于該葉子結(jié)點(diǎn)所標(biāo)記的類別。它可以表示任意的離散函數(shù)和離散特征，可以將實(shí)例分成兩個(gè)或多個(gè)類。二 決策樹學(xué)習(xí)的過擬合問題產(chǎn)生原因決策樹是判斷給定樣本與某種屬性相關(guān)聯(lián)的決策過程的一種表示方法。決策樹的每個(gè)內(nèi)部結(jié)點(diǎn)是對屬性的一個(gè)測試，每個(gè)分支代表一個(gè)測試輸出，每個(gè)葉結(jié)點(diǎn)表示某個(gè)類別或類別的分布。當(dāng)一個(gè)待分類的樣本沿根結(jié)點(diǎn)經(jīng)內(nèi)部結(jié)點(diǎn)的測試達(dá)到某個(gè)葉結(jié)點(diǎn)時(shí)，則判定該樣本屬于此葉結(jié)點(diǎn)所標(biāo)識的類別。建立決策樹的過程，即樹的生長過程是不斷地把訓(xùn)練數(shù)據(jù)集進(jìn)行劃分的過程，每次劃分對應(yīng)一個(gè)屬性，也對應(yīng)著一個(gè)內(nèi)部結(jié)點(diǎn)，劃分所選的屬性應(yīng)使劃分后的分組“差異”最大。決策樹生成算法的不同主要體現(xiàn)在對“差異”的衡量方式上。通常直接生成的完全決策樹不能立即用于對未知樣本進(jìn)行分類。由于完全決策樹對訓(xùn)練樣本的特征描述得“過于精確”，無法實(shí)現(xiàn)對新樣本的合理分析，所以此時(shí)它不是一棵分析新數(shù)據(jù)的最佳決策樹。一棵完全決策樹能非常準(zhǔn)確地反映訓(xùn)練集中數(shù)據(jù)的特征，但因失去了一般代表性而無法用于對新數(shù)據(jù)的分類或預(yù)測，這種現(xiàn)象一般稱為“過擬合”。過度擬合定義為：給定一個(gè)假設(shè)，如果在假設(shè)空間上存在另一個(gè)假設(shè)，使得在訓(xùn)練集上H的錯(cuò)誤率差比小，而在測試集上的錯(cuò)誤率卻比要大，那么稱假設(shè)過度擬合訓(xùn)練數(shù)據(jù)。通常導(dǎo)致決策樹過擬合的原因有多種，但主要有以下兩種：噪聲數(shù)據(jù)導(dǎo)致過分?jǐn)M合在現(xiàn)實(shí)世界中，數(shù)據(jù)伴有隨機(jī)的錯(cuò)誤或噪聲往往是難以完全避免的。例如在對用戶是否離網(wǎng)的分類中，目標(biāo)變量“是否流失”可能被錯(cuò)誤的標(biāo)記，利用此數(shù)據(jù)擬合得到的模型，就有可能因?yàn)閿M合錯(cuò)誤標(biāo)記的訓(xùn)練記錄，導(dǎo)致在模型應(yīng)用階段產(chǎn)生錯(cuò)誤分類，不能很好的進(jìn)行推廣。缺乏代表性樣本導(dǎo)致過分?jǐn)M合在訓(xùn)練數(shù)據(jù)缺乏具有代表性的樣本的情況下，往往需要繼續(xù)細(xì)化模型才能得到較好擬合訓(xùn)練集的模型，這樣得到的模型同樣可能具有較高的泛化誤差。三 決策樹過擬合問題的解決方法由于實(shí)際問題中存在太多不確定因素，用決策樹算法對訓(xùn)練集分類時(shí)，所得到的決策樹規(guī)模太大，難免會過度擬合訓(xùn)練數(shù)據(jù)。而實(shí)際上大而復(fù)雜的決策樹并不意味著可以得到更加準(zhǔn)確的規(guī)則集。另外，尋找最小決策樹被證明是NP問題，所以在現(xiàn)實(shí)中找不到絕對的最小決策樹。為了避免過度擬合，我們只能通過分析造成過度擬合的原因，來尋找一些簡化技術(shù)來修剪決策樹。避免決策樹學(xué)習(xí)中過度擬合的途徑可以被分為兩大類：預(yù)剪枝方法和后剪枝方法。預(yù)剪枝（pre-pruning）法 預(yù)剪枝法通過提前停止分支的生長過程來實(shí)現(xiàn)， 具體在什么時(shí)候停止決策樹的生長有多種不同的方法：a.一種最為簡答的方法就是在決策樹到達(dá)一定高度的情況下酒停止樹的生長；b.到達(dá)此結(jié)點(diǎn)的實(shí)例具有相同的特征向量，而不必一定屬于同一類，也可以停止生長。這種情況可以處理數(shù)據(jù)中的數(shù)據(jù)沖突問題；c.到達(dá)此結(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某一個(gè)閾值也可以停止樹的生長；d.計(jì)算每次擴(kuò)張對系統(tǒng)性能的增益，如果這個(gè)增益值小于某個(gè)閾值則不進(jìn)行擴(kuò)展。如果在最好的情況下的擴(kuò)展增益都小于閾值，即使有些葉子結(jié)點(diǎn)的實(shí)例不屬于同一類，也停止樹的增長。該方法的優(yōu)點(diǎn)在于避免產(chǎn)生過分?jǐn)M合訓(xùn)練數(shù)據(jù)的過于復(fù)雜的子樹，但是，我們很難為提前終止選取正確的閥值，閥值太高將導(dǎo)致擬合不足的模型，而閥值太低則不能充分地解決過分?jǐn)M合問題。此外，即便是使用已有的屬性測試條件得不到顯著的增益，接下來的劃分也可能產(chǎn)生較好的子樹。預(yù)剪枝有一個(gè)缺點(diǎn)，即視野效果問題。也就是說在相同的標(biāo)準(zhǔn)下，也許當(dāng)前的擴(kuò)展會造成過度擬合訓(xùn)練數(shù)據(jù)，但是更進(jìn)一步的擴(kuò)展能夠滿足要求，也有可能準(zhǔn)確地?cái)M合訓(xùn)練數(shù)據(jù)。這將使得算法過早地停止決策樹的構(gòu)造。后剪枝（post-pruning）法后剪枝法從一個(gè)“充分生長”樹中，按照自底向上的方式修剪掉多余的分支，修剪有兩種方法：（1） 用新的葉子結(jié)點(diǎn)替換子樹，該葉子結(jié)點(diǎn)的類標(biāo)號由子樹記錄中的多數(shù)類確定；（2） 用子樹中最常用的分支代替子樹。J48決策樹算法采用了子樹提升與子樹替換的修剪策略。計(jì)算修剪前后的預(yù)期分類錯(cuò)誤率，如果修剪導(dǎo)致預(yù)期分類錯(cuò)誤率變大，則放棄修剪，保留相應(yīng)結(jié)點(diǎn)的各個(gè)分支，否則就將相應(yīng)結(jié)點(diǎn)分支修剪刪去。在產(chǎn)生一系列經(jīng)過修剪的決策樹候選之后，利用一個(gè)獨(dú)立的測試數(shù)據(jù)集，對這些經(jīng)過修剪的決策樹的分類準(zhǔn)確性進(jìn)行評價(jià)， 保留下預(yù)期分類錯(cuò)誤率最小的 （修剪后） 決策樹。與預(yù)剪枝相比，后剪枝傾向于產(chǎn)生更好的結(jié)果，因?yàn)榕c預(yù)剪枝不同，后剪枝是根據(jù)完全生長的樹做出的剪枝決策，預(yù)剪枝則可能過早終止決策樹的生長。下面介紹三種主要的后剪枝方法：悲觀錯(cuò)誤剪枝(Mistic Error Pruning，PEP)，最小錯(cuò)誤剪枝(Minimum Error Pruning，MEP)，代價(jià)復(fù)雜度剪枝(Cost Complexity Pruning，CCP)。悲觀錯(cuò)誤剪枝（PEP）悲觀錯(cuò)誤剪枝法是根據(jù)剪枝前后的錯(cuò)誤率來判定子樹的修剪。該方法引入了統(tǒng)計(jì)學(xué)上連續(xù)修正的概念彌補(bǔ)REP中的缺陷，在評價(jià)子樹的訓(xùn)練錯(cuò)誤公式中添加了一個(gè)常數(shù)，假定每個(gè)葉結(jié)點(diǎn)都自動(dòng)對實(shí)例的某個(gè)部分進(jìn)行錯(cuò)誤的分類。該方法需要對決策樹上所有的非葉子結(jié)點(diǎn)進(jìn)行計(jì)算分析。搜索時(shí)從決策樹的根結(jié)點(diǎn)開始，計(jì)算每個(gè)分枝結(jié)點(diǎn)被剪后或者是被子樹替換后的期望錯(cuò)誤率。為了使數(shù)據(jù)源的數(shù)據(jù)特性得到最大限度的保留，把數(shù)據(jù)源作為一個(gè)整體，而不是將其分為訓(xùn)練集和測試集兩個(gè)部分。因此需要考慮最壞的情況，取置信區(qū)間的上限作悲觀情況下的錯(cuò)誤估計(jì)。給定一個(gè)置信度，錯(cuò)誤總數(shù)服從項(xiàng)貝努利(Bernoulli)分布是很明顯的，因而有概率等式如下：在該公式中，表示估計(jì)的錯(cuò)誤率，表示被修剪的子樹下的實(shí)例總數(shù)，假設(shè)表示修剪后出現(xiàn)的錯(cuò)誤實(shí)例數(shù)，那么是實(shí)際觀測到的錯(cuò)誤率。令 ，取置信區(qū)間的上限作為該結(jié)點(diǎn)的悲觀錯(cuò)誤率估計(jì)，則可得該結(jié)點(diǎn)的錯(cuò)誤率計(jì)算公式如下：在該公式中，根號前的“”號表示取置信區(qū)間的上限，就是估計(jì)的悲觀錯(cuò)誤率。給定一個(gè)期望錯(cuò)誤率最高閾值。當(dāng)剪去結(jié)點(diǎn)時(shí)，如果導(dǎo)致的錯(cuò)誤率不高于給定的閥值，則剪去結(jié)點(diǎn)下的子樹；否則，保留結(jié)點(diǎn)下的子樹。最小錯(cuò)誤剪枝（MEP）MEP算法希望通過剪枝得到一棵相對于獨(dú)立數(shù)據(jù)集來說具有最小期望錯(cuò)誤率的決策樹。所使用的獨(dú)立數(shù)據(jù)集是用來簡化對未知樣本的錯(cuò)分樣本率的估計(jì)的，并不意味真正使用了獨(dú)立的剪枝集，實(shí)際情況是無論早期版本還是改進(jìn)版本均只利用了訓(xùn)練集的信息。對于類問題，定義樣本到達(dá)結(jié)點(diǎn)且屬于第類的期望概率為： ；其中為由訓(xùn)練集得來的屬于第類的先驗(yàn)概率，表示先驗(yàn)概率對期望概率的影響程度，反映了剪枝的程度，為簡單起見認(rèn)為所有類別的均相同。當(dāng)一個(gè)新樣本到達(dá)結(jié)點(diǎn)而被分類時(shí)，結(jié)點(diǎn)的期望錯(cuò)誤率表示為當(dāng)且時(shí)，可得在MEP中，自底向上計(jì)算每個(gè)內(nèi)部結(jié)點(diǎn)的期望錯(cuò)誤率，稱為靜態(tài)錯(cuò)誤， ；樹的期望錯(cuò)誤稱為動(dòng)態(tài)錯(cuò)誤，是其孩子結(jié)點(diǎn)的期望錯(cuò)誤的加權(quán)和。MEP算法自底向上順序遍歷完全決策樹并計(jì)算子樹 的靜態(tài)錯(cuò)誤和動(dòng)態(tài)錯(cuò)誤，當(dāng)子樹的靜態(tài)錯(cuò)誤和動(dòng)態(tài)錯(cuò)誤滿足時(shí)則剪枝，并用一個(gè)葉結(jié)點(diǎn)來代替，該葉結(jié)點(diǎn)所標(biāo)識的類別由“大多數(shù)原則”來確定。代價(jià)復(fù)雜度剪枝（CCP）CCP算法采用一種二分遞歸分割的技術(shù)，將當(dāng)前的樣本集分為兩個(gè)子樣本集，使得生成的的每個(gè)非葉子結(jié)點(diǎn)都有兩個(gè)分支。因此，CCP算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。CCP算法是通過在完全生長的樹上剪去分枝實(shí)現(xiàn)的，通過刪除結(jié)點(diǎn)的分支來剪去樹結(jié)點(diǎn)。最下面未被剪枝的結(jié)點(diǎn)成為樹葉。CCP用的成本復(fù)雜性標(biāo)準(zhǔn)是分類樹的簡單誤分(基于驗(yàn)證數(shù)據(jù)的)加上一個(gè)對樹的大小的懲罰因素。懲罰因素是有參數(shù)的，我們用表示，每個(gè)結(jié)點(diǎn)的懲罰。成本復(fù)雜性標(biāo)準(zhǔn)對于一個(gè)數(shù)來說是,其中是驗(yàn)證數(shù)據(jù)被樹誤分部分，是樹T的葉結(jié)點(diǎn)數(shù)，是每個(gè)結(jié)點(diǎn)的懲罰成本：一個(gè)從向上變動(dòng)的數(shù)字。當(dāng)對樹有太多的結(jié)點(diǎn)沒有懲罰，用的成本復(fù)雜性標(biāo)準(zhǔn)是完全生長的沒有剪枝的樹。在剪枝形成的一系列樹中，從其中選擇一個(gè)在驗(yàn)證數(shù)據(jù)集上具有最小誤分的樹是很自然的，我們把這個(gè)樹成為最小誤分樹。三種算法的比較在以上三種算法中，對于給定剪枝集，PEP剪枝算法中當(dāng)某個(gè)子樹滿足剪枝條件時(shí)將不再對其后裔進(jìn)行剪枝判斷，因此PEP方法收斂速度較快，但最壞情況下仍然每個(gè)結(jié)點(diǎn)都要遍歷，為線性復(fù)雜度。在MEP剪枝算法中的選擇比較關(guān)鍵，因?yàn)榧糁Τ潭韧ㄟ^控制，越大剪枝越嚴(yán)重。當(dāng)接近無窮時(shí)，而是對訓(xùn)練集中屬于第類樣本所占比重的估計(jì)，只有當(dāng)剪枝到只剩一個(gè)葉結(jié)點(diǎn)時(shí)期望錯(cuò)誤率最少，此時(shí)剪枝程度最大，較小時(shí)剪枝程度也較小。大多數(shù)情況下剪枝并不會使預(yù)測精度降低，只有個(gè)別鄰域可能較難控制；而對于所生成的剪枝樹的復(fù)雜程度來說，MEP，