決策樹過擬合.doc

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