決策樹(shù)過(guò)擬合.doc

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