佘為++韓昌豪

摘要：決策樹算法是數(shù)據(jù)挖掘中的一個(gè)常用算法，它通過構(gòu)造決策樹來發(fā)現(xiàn)數(shù)據(jù)中蘊(yùn)含的分類規(guī)則，如何構(gòu)造精度高、規(guī)模小的決策樹是決策樹算法的核心內(nèi)容。決策樹算法中常用的一種是ID3算法，該文針對傳統(tǒng)ID3算法的缺點(diǎn)，提出一種改進(jìn)的ID3算法，通過實(shí)驗(yàn)證實(shí)，改進(jìn)的ID3算法在生成的決策樹的規(guī)模和精度方面都比傳統(tǒng)的ID3算法好，使用這種改進(jìn)的ID3算法可以提高性能。

關(guān)鍵詞：決策樹；ID3算法；信息增益；剪枝

中圖分類號： TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）11-0091-01

1 ID3算法

決策樹分類算法中的ID3算法是Quilan在1986年提出來的，也是決策樹構(gòu)造中的經(jīng)典算法[1]。ID3算法是以信息論為基礎(chǔ)，它使用信息熵和信息增益兩個(gè)指標(biāo)為衡量標(biāo)準(zhǔn)，選擇信息增益最大的屬性劃分訓(xùn)練樣本，從而生成決策樹。

定義1、按類標(biāo)簽對訓(xùn)練集D的屬性集A進(jìn)行劃分，信息熵為：

[infoD=-i=0mpilog2pi]

Pi為訓(xùn)練集D中屬于第i類的概率。

定義2、按屬性集A中每個(gè)屬性進(jìn)行劃分，得到一組信息熵：

[infoAD=-j=0nDjDinfoDj]

Dj為屬性集中每個(gè)屬性的出現(xiàn)的次數(shù)，D為所有屬性的總次數(shù)。

定義3、信息增益為：

Gain（A）=info（D）-infoA（D）

ID3算法對每個(gè)節(jié)點(diǎn)中選擇Gain（A）中最大的屬性A作為選擇分支的屬性。這種算法的缺點(diǎn)是：傾向于選擇取值較多的屬性[2]，在有些情況下這類屬性可能不會(huì)提供什么有意義的信息，ID3學(xué)習(xí)簡單邏輯表達(dá)式的能力差[3]。此外，ID3將注意力集中在屬性的選擇方面，而屬性的選擇對決策樹的影響如何，仍無定論[4]。

2 改進(jìn)的ID3算法

1）調(diào)整信息增益

針對ID3算法偏向于選擇取值較多但實(shí)際中并不總是最優(yōu)的屬性作為測試屬性的缺點(diǎn)，調(diào)整信息增益。Gain（A）= Gain（A） /X，其中X的取值大于等于1，主要由屬性A的取值個(gè)數(shù)和使用者根據(jù)經(jīng)驗(yàn)及領(lǐng)域知識來確定，一般取值個(gè)數(shù)越多則X越大。改進(jìn)的ID3算法通過調(diào)整每個(gè)屬性的信息增益，使生成決策樹時(shí)數(shù)量少但又很重要的屬性不會(huì)被淹沒，最終使決策樹克服了對取值多的屬性的偏愛，因?yàn)閷傩匀≈翟蕉?，調(diào)整后的信息增益就越小，這個(gè)屬性當(dāng)然就很難被選中為判斷屬性了。

2）剪枝

剪枝方法主要是考慮在決策樹的哪個(gè)位置產(chǎn)生葉子合適[5]。剪枝算法分前剪枝和后剪枝。前剪枝是在決策樹構(gòu)造過程中選取某個(gè)預(yù)定義的閥值，使得某些節(jié)點(diǎn)不再繼續(xù)分裂，限制樹的生長。后剪枝是將已生成的決策樹做去分支處理[6]。前剪枝由于很難選取一個(gè)合適的閥值，應(yīng)用困難。后剪枝的時(shí)間復(fù)雜度高，但生成的決策樹準(zhǔn)確度高，但主要應(yīng)用的幾種后剪枝算法都存在過剪枝或欠剪枝現(xiàn)象。由于各種剪枝算法都有缺點(diǎn)，所以本文提出采用靈活的剪枝方法進(jìn)行剪枝。

剪枝方法為：首先，根據(jù)具體需要設(shè)定生成決策樹的高度、精確度等信息，設(shè)定主要依據(jù)經(jīng)驗(yàn)和領(lǐng)域知識來確定。然后，針對決策樹節(jié)點(diǎn)a來說，對a進(jìn)行剪枝，則產(chǎn)生的錯(cuò)誤分配樣本數(shù)為：[e'a=ea+12]。

未剪枝的子樹錯(cuò)誤分配樣本數(shù)為：[E'Ta=E'（Ti）]。

未剪枝的子樹誤差為：[SeTi=Ca2]。

其中，e（a）為a節(jié)點(diǎn)的錯(cuò)誤分配樣本數(shù)，Ti（i=1，2，…，n）是Ta節(jié)點(diǎn)的子節(jié)點(diǎn)，Ca是Ta節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)。如果葉子節(jié)點(diǎn)的[e'a≤E'Ti+Se（Ti）]成立，那么Ta可以剪枝。

3實(shí)驗(yàn)測試結(jié)果

實(shí)驗(yàn)所用數(shù)據(jù)為UCI數(shù)據(jù)庫中的Iris數(shù)據(jù)集（樣本數(shù)209個(gè)，屬性7個(gè)）、Breast數(shù)據(jù)集（樣本數(shù)817個(gè)，屬性11個(gè)）和Segmentation數(shù)據(jù)集（樣本數(shù)2932個(gè)，屬性26個(gè)）。對這三個(gè)數(shù)據(jù)集所有連續(xù)值的屬性使用DBChi2算法對數(shù)據(jù)進(jìn)行離散，隨機(jī) （下轉(zhuǎn)第96頁）

（上接第91頁）

抽取每個(gè)數(shù)據(jù)集中的2/3用于訓(xùn)練樣本集，其余的1/3用作測試樣本集，然后分別用傳統(tǒng)的ID3算法和改進(jìn)的ID3算法構(gòu)建決策樹，最后通過測試樣本集測試準(zhǔn)確度。上述構(gòu)造決策樹的方法反復(fù)進(jìn)行十次，得出的結(jié)果如表1。

表1 實(shí)驗(yàn)結(jié)果

[數(shù)據(jù)集＼&傳統(tǒng)ID3算法的平均準(zhǔn)確度＼&傳統(tǒng)ID3算法的平均葉子數(shù)＼&改進(jìn)ID3算法的平均準(zhǔn)確度＼&改進(jìn)ID3算法的平均葉子數(shù)＼&Iris＼&75%＼&7.4個(gè)＼&81%＼&5.6個(gè)＼&Breast＼&87%＼&8.2個(gè)＼&89%＼&6.3個(gè)＼&Segmentation＼&72%＼&11.2個(gè)＼&85%＼&9.6個(gè)＼&]

從表1中能明顯的得出，改進(jìn)的ID3算法平均的分類準(zhǔn)確度更高，生成決策樹的平均葉子數(shù)也高過傳統(tǒng)的ID3算法，具有更低的復(fù)雜性。從實(shí)驗(yàn)還得出改進(jìn)的ID3算法通過不斷的學(xué)習(xí)調(diào)整信息增益，從而克服了傳統(tǒng)ID3算法傾向于選擇取值較多的屬性的缺點(diǎn)，但是改進(jìn)的ID3算法通過實(shí)驗(yàn)得出在時(shí)間復(fù)雜度上和傳統(tǒng)ID3幾乎一致。

4 結(jié)束語

改進(jìn)的ID3算法調(diào)整了傳統(tǒng)的ID3算法的信息增益計(jì)算方法，又加入了靈活的剪枝策略。它可以依靠經(jīng)驗(yàn)或領(lǐng)域知識人工增強(qiáng)重要屬性在分類決策中調(diào)整信息增益，從而減少非重要屬性的信息量，特別是它可以減少ID3算法對取值較多的屬性的依賴性，從而改善分類規(guī)則和結(jié)果。

參考文獻(xiàn)：

[1] 趙微，蘇健民.基于ID3算法決策樹的研究與改進(jìn)[J]. 科技信息， 2008（23）： 383.

[2] Quinlan J R， Induction of decision trees[J]. Machine Learning， 1986， 1（1）： 81-106.

[3] Tu P L， Chung J Y.A new decision-tree classification algorithm for machine learning[C]// Proceedings of the 1992 IEEE International Conference on Tools for Artificial Intelligence. Arlington Virginia， USA： IEEE Computer Society， 1992 370-377.

[4] Hong J R.A new algorithm of decision tree induction[J]. Chinese Journal of Computers， 1995， 18（6）： 470-473.

[5] 孫娟，王熙照. 規(guī)則簡化與模糊決策樹剪枝的比較[J]. 計(jì)算機(jī)工程， 2006，12（32）： 210-211.

[6] 李仁良，李義杰. 基于多策略的決策樹剪枝算法及其應(yīng)用[J]. 計(jì)算機(jī)仿真， 2010， 11（27）： 78-80.