決策樹過擬合.doc

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