ID3分類及其剪枝算法研究

劉沖+楊磊+李娜

摘 要：分類是數(shù)據(jù)挖掘的一個重要課題。分類的目的是建立一個分類模型，該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個利用該模型形成分類規(guī)則并預(yù)測未來數(shù)據(jù)趨勢[1]。決策樹歸納是經(jīng)典的分類算法，構(gòu)建決策樹模型算法中最有影響力的方法是ID3算法。針對ID3算法缺點，使用預(yù)剪枝和后剪枝相結(jié)合的辦法處理決策樹中的過學(xué)習(xí)情況，可生成一個更簡單、更精確的決策樹。

關(guān)鍵詞：ID3分類算法； 決策樹； 剪枝算法

DOIDOI：10.11907/rjdk.162536

中圖分類號：TP312

文獻標(biāo)識碼：A文章編號：1672-7800（2016）012-0033-02

1 ID3分類算法

1.1 ID3算法原理

決策樹歸納是經(jīng)典的分類算法[1]。ID3算法是Quinlan提出的一個著名的決策樹生成方法。決策樹是指具有以下性質(zhì)的樹：每個內(nèi)部節(jié)點都被標(biāo)記一個屬性，每個弧都被標(biāo)記一個值，這個值對應(yīng)于相應(yīng)父節(jié)點屬性；每個葉節(jié)點都被標(biāo)記一個類[2]。ID3算法是一種基于信息熵的決策樹算法，算法的核心是在生成決策樹時使用信息增益作為訓(xùn)練樣本集合的分裂度量標(biāo)準(zhǔn)，選擇信息增益最大值的屬性對訓(xùn)練樣本劃分，該屬性使得劃分樣本分類所需的信息量最小。該方法可以減少訓(xùn)練樣本的劃分次數(shù)，并盡可能得到一棵簡單的決策樹來描述相關(guān)信息。

1.2 ID3算法缺點

（1）對噪聲較為敏感，訓(xùn)練數(shù)據(jù)的輕微錯誤會導(dǎo)致不同結(jié)果，魯棒性較差；算法結(jié)果隨訓(xùn)練集記錄個數(shù)的改變而不同，不便于漸行漸進學(xué)習(xí)。

（2）ID3算法只能處理離散屬性的數(shù)據(jù)，對于連續(xù)屬性數(shù)據(jù)，必須先進行離散化處理才能使用。如產(chǎn)品名稱是一個離散性屬性，適合用ID3算法處理，而產(chǎn)品價格是連續(xù)性屬性，必須對產(chǎn)品價格進行離散化處理后才能使用。

（3） ID3算法不能處理屬性為空的記錄，而在實際業(yè)務(wù)數(shù)據(jù)中，又存在大量的空記錄，如果僅僅有一個缺失值就單純地刪除整條記錄的話，那么最終可能得到一個很小的訓(xùn)練集，同時這個訓(xùn)練集可能已經(jīng)丟失了業(yè)務(wù)數(shù)據(jù)中所包含的一些重要信息，所以要對缺省屬性進行處理才能使訓(xùn)練集適用于ID3算法。

（4）ID3算法在搜索過程中不進行回溯，每當(dāng)選擇了一個屬性進行分類后，以后的處理過程就不會再考慮該屬性了，這樣算法很容易收斂到局部最優(yōu)而不是全局最優(yōu)。

（5）ID3算法對于較小的數(shù)據(jù)集很有效，當(dāng)這些算法用于非常大的數(shù)據(jù)庫挖掘時，算法效率成為瓶頸。

2 剪枝算法

決策樹是分類和預(yù)測的強有力工具，而易于理解和表示規(guī)則是決策樹的優(yōu)勢。在最終形成的決策樹上，每個內(nèi)部節(jié)點都被標(biāo)記一個屬性，每個弧都被標(biāo)記一個值，這個值對應(yīng)于相應(yīng)父節(jié)點屬性；每個葉節(jié)點都被標(biāo)記一個類；每個分枝代表對該屬性的測試輸出。決策樹的生成過程分為兩個步驟：一是生成樹，二是對樹的剪枝，就是去掉一些可能是噪聲或者是錯誤的數(shù)據(jù)[3]。

樣本分為訓(xùn)練集和測試集，給定一個決策樹A，如果在假設(shè)空間中存在另一個決策樹B，使得A在訓(xùn)練集上的錯誤率比B小，但是在測試集上A的錯誤率差比B大，則稱A為過度擬合訓(xùn)練數(shù)據(jù)。

導(dǎo)致這種過度擬合現(xiàn)象的發(fā)生原因是：①訓(xùn)練樣本中存在隨機錯誤或噪聲，噪聲會導(dǎo)致分類結(jié)果沖突，比如對某個實例的每個屬性都有相同的屬性值，但在訓(xùn)練集和測試集中卻有著不同的分類結(jié)果；②當(dāng)訓(xùn)練樣本數(shù)據(jù)量比較小時，特別是當(dāng)決策樹中的某些分枝與客觀事實不符合時，很可能出現(xiàn)巧合的規(guī)律性[4-5]。第①種情況適應(yīng)于后剪枝方法，第②種情況適應(yīng)于預(yù)剪枝方法。

（1）預(yù)剪枝：在生成決策樹之前，通過一定規(guī)則較早地停止樹的生長。由于預(yù)剪枝不必生成整棵決策樹，且算法相對簡單，效率較高，適合處理大規(guī)模數(shù)據(jù)問題。該方法能大大縮短決策樹規(guī)則生成時間，但如果閾值設(shè)置不準(zhǔn)確，會大大降低算法的精確度。預(yù)剪枝具體在什么時候停止決策樹生長衍生出多種方法：最簡單的方法是在決策樹生長到某一固定高度時停止樹的生長；如果某節(jié)點的實例個數(shù)與總樣本的個數(shù)之比小于某個閾值就停止樹的生長。

（2）后剪枝：允許決策樹過度擬合數(shù)據(jù)，它由完全生長的樹剪去分枝。通過刪除節(jié)點分枝剪掉樹節(jié)點。這種方法能保證結(jié)果具有較高的準(zhǔn)確度，但代價是處理大規(guī)模數(shù)據(jù)分類集時會耗費較多時間。常用的后剪枝算法有REP方法、PEP方法和MEP方法等。后剪枝方法主要是通過不斷修改子樹使之成為葉節(jié)點[6]。

3 ID3改進算法實現(xiàn)

決策樹生成后，從根到葉子結(jié)點可以創(chuàng)建一條IF-THEN形式規(guī)則，規(guī)則左邊為規(guī)則前件，葉子節(jié)點的屬性值為規(guī)則后件。分類規(guī)則的質(zhì)量可以用準(zhǔn)確率和覆蓋率兩個參數(shù)度量[7]。

（1）準(zhǔn)確率：是指結(jié)點在測試集上正確預(yù)測的實例數(shù)與分配給該節(jié)點的實例總數(shù)之比，度量該節(jié)點能夠正確預(yù)測目標(biāo)值的可能性。實際中由于測試集數(shù)目較大，求出各個結(jié)點的準(zhǔn)確率會影響算法的執(zhí)行效率，故采用總的準(zhǔn)確率來評估分類質(zhì)量，也就是用所有節(jié)點在測試集中預(yù)測正確的實例數(shù)與測試集大小的比例來反映總體評價標(biāo)準(zhǔn)。

（2）覆蓋率：指節(jié)點中占某一類最多的實例數(shù)量與訓(xùn)練樣本集中該類的實例數(shù)量之比，以此度量從訓(xùn)練集中分配了多少實例給該節(jié)點。覆蓋率也叫置信度，置信度小于某個閾值的節(jié)點會被預(yù)剪掉，如果一個父節(jié)點所有的子結(jié)點都被剪枝掉了，則該父節(jié)點成為葉結(jié)點。把父節(jié)點的節(jié)點名替換為該節(jié)點中某實例所對應(yīng)的類標(biāo)號，并且釋放掉分裂屬性，以便讓后續(xù)節(jié)點可以重新利用該屬性。通過設(shè)置置信度閾值，可以較快得到一棵決策樹。

3.1 算法數(shù)據(jù)結(jié)構(gòu)

改進后的算法實現(xiàn)過程中用到的決策樹結(jié)點代碼：

class TreeNode { TreeNode parent； //父節(jié)點 String parentAttribute； //指向父結(jié)點的哪個屬性 String nodeName； //節(jié)點名 String[] attributes； //屬性數(shù)組 TreeNode[] childNodes； //子節(jié)點數(shù)組 String maxAttribute； //結(jié)點中占最多實例數(shù)所對應(yīng)的屬性 int errorNum； //記錄決策樹在測試集中的錯誤數(shù) double percent； //置信度，置信度小于某個閾值，屬性提前停止分裂

}

3.2 算法實現(xiàn)

根據(jù)未剪枝前的決策樹和測試集遞歸調(diào)用算法，計算出樹中每個節(jié)點的錯誤數(shù)，然后根據(jù)REP剪枝準(zhǔn)則來剪枝決策樹，代碼如下：

public void repairDTree（TreeNode node）

{

TreeNode[] childs = node.childNodes；int total=0；

for （int i = 0； i < childs.length； i++）

if （childs[i] ！= null）

total=total+childs[i].errorNum； //計算出子結(jié)點的錯誤總數(shù)

//如果父節(jié)點錯誤數(shù)不大于子結(jié)點的錯誤總數(shù)，則刪除子結(jié)點

if（total>=node.errorNum）

node.childNodes = new TreeNode[0]；

else for （int i = 0； i < childs.length； i++）

{

if （childs[i] ！= null） repairDTree（childs[i]）；

}

}

4 實驗結(jié)果比較

針對不同的訓(xùn)練集，ID3算法在改進前后的性能比較情況如表1所示。從數(shù)據(jù)倉庫中隨機抽取4個樣本集作為數(shù)據(jù)來源，且所有實驗都在同一配置同一操作系統(tǒng)的機器上進行。

從時間復(fù)雜度上分析：改進后的算法在決策樹生成時間上明顯比改進前短，而且隨著數(shù)據(jù)量的增大，改進前后算法在時間上都非線性遞增。數(shù)據(jù)量越大，遞增的幅度越大，在時間復(fù)雜度上試驗結(jié)果與理論相符。

從準(zhǔn)確率上分析：ID3改進算法在測試集上的預(yù)測準(zhǔn)確率比改進前高。由于采用了后剪枝算法，從而消除了決策樹生成過程中的過學(xué)習(xí)問題，提高了預(yù)測準(zhǔn)確率。ID3算法改進后的預(yù)測準(zhǔn)確率隨著訓(xùn)練集和測試集的增長呈現(xiàn)出線性增長趨勢，即樣本集越大，效果越明顯。

參考文獻：

[1] 鄒媛.基于決策樹的數(shù)據(jù)挖掘算法的應(yīng)用與研究[J].科學(xué)技術(shù)與工程，2010，10（18）：4510-4515.

[2] 孫愛東，朱梅階.基于屬性值的ID3算法改進[J].計算機工程設(shè)計，2008，29（12）： 3011-3012.

[3] 楊學(xué)兵.決策樹算法及其核心技術(shù)[J].計算機技術(shù)與發(fā)展，2007，17（1）：43-45.

[4] 魯為，王樅.決策樹算法的優(yōu)化與比較[J].計算機工程，2007，33（16）：189-190.

[5] 李道國.決策樹剪枝算法的研究和改進[J].計算機工程，2005（8）：33-46.

[6] 邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法[M].北京：中國水利水電出版社，2003.

[7] 朱顥東.ID3算法的優(yōu)化[J].華中科技大學(xué)學(xué)報，2010，38（5）：9-12.

（責(zé)任編輯：杜能鋼）