決策樹學習及其剪枝算法研究.pdf

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

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

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