決策樹學(xué)習(xí)及其剪枝算法研究.pdf

1、數(shù)據(jù)挖掘是信息處理領(lǐng)域的一項(xiàng)重要課題，它融合了數(shù)據(jù)庫(kù)、人工智能、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)等多個(gè)領(lǐng)域的理論和技術(shù)。其中分類分析在商業(yè)等領(lǐng)域中的成功應(yīng)用使它成為數(shù)據(jù)挖掘中最活躍、最成熟的研究方向。目前常用的分類方法有決策樹、關(guān)聯(lián)規(guī)則、貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、粗糙集模型和統(tǒng)計(jì)模型等。而決策樹方法以其速度快、精度高、生成的模式簡(jiǎn)單易懂以及容易轉(zhuǎn)化成分類規(guī)則等優(yōu)點(diǎn)，在數(shù)據(jù)挖掘領(lǐng)域被廣泛地研究和應(yīng)用。 本文主要介紹如何利用訓(xùn)練數(shù)據(jù)集來(lái)構(gòu)造決策樹模型，

2、以及如何解決決策樹學(xué)習(xí)過(guò)程中的常見問(wèn)題。論文從算法描述角度詳細(xì)地闡述了ID3算法和其它改進(jìn)算法的理論基礎(chǔ)與學(xué)習(xí)過(guò)程，并結(jié)合近年來(lái)流行的數(shù)據(jù)倉(cāng)庫(kù)技術(shù)和數(shù)據(jù)挖掘問(wèn)題，簡(jiǎn)要地討論了決策樹歸納的可擴(kuò)展性。針對(duì)幾種典型的決策樹算法的優(yōu)缺點(diǎn)，文中對(duì)它們進(jìn)行了綜合的分析與比較。 但是通過(guò)學(xué)習(xí)訓(xùn)練數(shù)據(jù)來(lái)構(gòu)造決策樹的策略可能無(wú)法達(dá)到最好的泛化性能。隨機(jī)噪聲和某些決策僅取決于少量的訓(xùn)練數(shù)據(jù)，都會(huì)導(dǎo)致決策樹的分類精度下降，并且過(guò)度擬合訓(xùn)練數(shù)據(jù)。過(guò)度擬

3、合問(wèn)題是決策樹歸納學(xué)習(xí)中的一個(gè)實(shí)踐難題，避免過(guò)度擬合主要是通過(guò)對(duì)樹的剪枝來(lái)實(shí)現(xiàn)的，包括預(yù)剪枝和后剪枝。常用的后剪枝算法有五種，REP、PEP、MEP、CCP算法和后規(guī)則修剪方法。為了在決策樹剪枝中選擇正確的方法，本文主要從計(jì)算復(fù)雜性、誤差估計(jì)和算法理論基礎(chǔ)角度對(duì)它們進(jìn)行闡述。另外，由于在決策樹的構(gòu)造過(guò)程中采用貪心算法，因而造成了決策樹規(guī)模過(guò)大、產(chǎn)生的規(guī)則長(zhǎng)度過(guò)長(zhǎng)等缺點(diǎn)。為了減小決策樹的規(guī)模，提高預(yù)測(cè)精度，文中總結(jié)了五種決策樹優(yōu)化方法。