劉沖+楊磊+李娜

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

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

DOIDOI：10.11907/rjdk.162536

中圖分類(lèi)號(hào)：TP312

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

1 ID3分類(lèi)算法

1.1 ID3算法原理

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

1.2 ID3算法缺點(diǎn)

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

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

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

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

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

2 剪枝算法

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

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

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

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

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

3 ID3改進(jìn)算法實(shí)現(xiàn)

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

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

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

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

改進(jìn)后的算法實(shí)現(xiàn)過(guò)程中用到的決策樹(shù)結(jié)點(diǎn)代碼：

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

}

3.2 算法實(shí)現(xiàn)

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

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； //計(jì)算出子結(jié)點(diǎn)的錯(cuò)誤總數(shù)

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

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 實(shí)驗(yàn)結(jié)果比較

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

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

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

參考文獻(xiàn)：

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

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

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

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

[5] 李道國(guó).決策樹(shù)剪枝算法的研究和改進(jìn)[J].計(jì)算機(jī)工程，2005（8）：33-46.

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

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

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