楊霖+周軍+梅紅巖+杜晶鑫

摘 要：ID3算法是構(gòu)造決策樹的一種經(jīng)典算法，傳統(tǒng)的ID3算法存在很多問題，研究者提出了多種改進(jìn)算法。簡要概述基于粗糙集、粒計算和分類矩陣的ID3改進(jìn)算法，通過實驗分析對比3種改進(jìn)算法的優(yōu)勢和不足，并對ID3算法的應(yīng)用前景提出展望。

關(guān)鍵詞：ID3算法；決策樹；改進(jìn)算法

DOIDOI：10.11907/rjdk.171383

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：1672-7800（2017）008-0021-04

0 引言

分類是一種重要的數(shù)據(jù)分析形式，是數(shù)據(jù)挖掘中最常用的方法之一，是提取刻畫重要數(shù)據(jù)類的模型。決策樹是分類方式之一，它構(gòu)造簡單，不需要設(shè)置參數(shù)，可以處理高維數(shù)據(jù)。決策樹分類采用樹的表示形式較為直觀，學(xué)習(xí)和歸納的步驟簡單且快速，因此很容易被人理解和接受。

在決策樹構(gòu)造算法中，ID3算法的應(yīng)用最為廣泛，但同時也有許多缺點。ID3算法更傾向于選擇屬性值較多的屬性作為根節(jié)點[1-4]，對于數(shù)據(jù)量較大的數(shù)據(jù)集，該方法可能會失效[5-8]，而且非類別屬性越多，需要計算的時間也會急劇增加，并且分類的速度和精確度也大大降低[9-11]。此外，ID3算法對噪聲數(shù)據(jù)比較敏感[12]。為了解決這些問題，近年來許多專家學(xué)者致力于ID3算法研究，提出了多種改進(jìn)和優(yōu)化的ID3算法，使得ID3算法更加完善，效率也更提高。其中，研究較為廣泛的有：基于粗糙集的ID3算法改進(jìn)、基于粒計算的ID3算法改進(jìn)、基于分類矩陣的ID3算法改進(jìn)等。本文將介紹ID3算法的基本原理，重點介紹基于粗糙集、粒計算、分類矩陣的ID3改進(jìn)算法，并分析對比3類ID3改進(jìn)算法。

1 ID3算法理論

ID3算法是J·Ross Quinlan于1986年提出的非回溯方法，其中決策樹以自頂向下遞歸的分治方式構(gòu)造[13]。以信息論為基礎(chǔ)，引入屬性選擇度量的概念，將給定訓(xùn)練元組的數(shù)據(jù)分區(qū)劃分成最純的，即每個分區(qū)的所有元組都屬于相同的類。

ID3算法采用信息增益作為屬性選擇度量，這里引入熵和期望信息的概念。

設(shè)數(shù)據(jù)分區(qū)為N類，屬標(biāo)號為a，且定義a個不同的類Mi（i=1，...，a）。設(shè)Mi，N是N中Mi類元組集合，|N|和|Mi，N|分別為N和Mi，N中元組個數(shù)。則熵（entropy）為：

Info（N）=-∑ai=1pilog2（pi）（1）

若對元組N進(jìn)行元組劃分，將N劃分為v個子集{D1，D2，...，Dv}，則Dj包含D中的元組，理想狀態(tài)下，每個分區(qū)都是純的，則期望信息為：

InfoA（D）=∑vj=1DjD×Info（Dj）（2）

需要的期望信息越小，分區(qū)的純度越高。

信息增益為：

Gain（A）=Info（D）-InfoA（D）（3）

2 ID3算法改進(jìn)

2.1 基于粗糙集的ID3算法改進(jìn)

波蘭數(shù)學(xué)家Z·Pawlak教授[14-16]于1982年提出粗糙集理論數(shù)據(jù)挖掘方法。基于粗糙集技術(shù)的改進(jìn)算法是一種完全數(shù)據(jù)驅(qū)動的歸納算法。針對ID3算法傾向于選取屬性值較多的屬性作為根節(jié)點的問題， 翟俊海[17]等提出基于粗糙集的決策樹歸納。

基于粗糙集的ID3算法描述如下：

輸入：決策表，其中，C={a1，a2，...，am}，決策屬性D的取值為VD={d1，d2，...，dn}；

輸出：決策樹。

算法偽代碼如下：

步驟1：計算決策表關(guān)于決策屬性的分類：π（U）={X1，X2，...，Xn}。其中，Xi=[x]di，i=1，2，...，n。

步驟2：for（i=1；i≤m；i++） { for（j=1；j≤n；j++） { 計算Xj的重要度 } 計算π（U） 的重要度 }

步驟3：計算aj=argmax1≤i≤msgiai（π（U））。

步驟4：計算aj在U中的劃分。

步驟5：for（i=1；i≤k；i++） {

如果Ui中類別屬于同一類，結(jié)束計算；

否則，對于Ui重復(fù)步驟2—步驟5； }

在基于信息熵的ID3算法中，生成的子樹會出現(xiàn)重復(fù)現(xiàn)象，甚至有些屬性在某一路徑上被檢驗許多次，當(dāng)出現(xiàn)對分類無關(guān)屬性較多時，生成的決策樹結(jié)構(gòu)性差。丁春榮等[18]提出一種利用屬性加權(quán)分類粗糙度作為新的啟發(fā)式函數(shù)構(gòu)造決策樹的方法，并用變精度粗糙集進(jìn)行優(yōu)化，提高了分類的效率和效果，王越等[19]也采用了變精度粗糙集進(jìn)行優(yōu)化。章曉等[20]基于粗糙集理論及凹函數(shù)性質(zhì)，引入函數(shù)重要度概念，從理論上分析多值偏向問題，并分析了屬性多值對屬性重要度的影響。離散化方法的連續(xù)值決策樹歸納在選擇擴(kuò)展屬性時，需要度量每一個屬性的每一個割點的分類不確定性，通過割點的不確定性選擇擴(kuò)展屬性，但這一方法的計算時間復(fù)雜度高。翟俊海等[21]提出基于相容粗糙集技術(shù)的連續(xù)值屬性決策樹歸納方法，該方法利用相容粗糙集技術(shù)選擇擴(kuò)展屬性，然后找出該屬性的最優(yōu)割點，分割樣例集，并遞歸構(gòu)建決策樹。

2.2 基于粒計算的ID3算法改進(jìn)

信息粒度化的思想由Zadeh[22]提出，后來Yao等[23]在此基礎(chǔ)上進(jìn)行了粒計算的研究。周浩等[24]提出基于粒計算的決策樹并行算法應(yīng)用，是為了解決海量數(shù)據(jù)的挖掘問題。該方法首先基于二進(jìn)制信息粒關(guān)聯(lián)矩陣，提出新的信息增益計算方法，再在Hadoop平臺上，結(jié)合并行處理模型MapReduce進(jìn)行決策樹分類[25]。

基于MapReduce模型和粒計算的并行化設(shè)計思想主要有兩點：一是二進(jìn)制信息粒關(guān)聯(lián)矩陣并行化計算，此過程中要設(shè)計一個Map和Reduce函數(shù)實現(xiàn)任一節(jié)點的關(guān)聯(lián)矩陣，為計算屬性的信息增益提供數(shù)據(jù)；二是決策樹的任何分支點進(jìn)行最佳分裂屬性選擇的并行化計算，這里的并行采用數(shù)據(jù)和任務(wù)兩種并行方式，在訓(xùn)練階段用兩個Map函數(shù)和Reduce函數(shù)設(shè)計任務(wù)，第一個MapReduce任務(wù)是數(shù)據(jù)處理并行化，第二個任務(wù)是對樹的分枝節(jié)點并行計算出每一個子數(shù)據(jù)集的最佳分裂屬性，然后根據(jù)輸出結(jié)果生產(chǎn)規(guī)則或者構(gòu)建一層決策樹[26-29]。

2.3 基于分類矩陣的ID3算法改進(jìn)

分類矩陣是評估預(yù)測結(jié)果的重要工具，因為它使得結(jié)果更易于理解并說明錯誤預(yù)測的影響。陶道強(qiáng)等[30]提出了基于分類矩陣的決策樹算法，為了提高決策樹分類速度和精確率，解決ID3算法的多值偏向性，同時利用分類矩陣證明了ID3算法具有多值偏向性。

定義分類矩陣[30]，給定一個訓(xùn)練集H，按照非類別屬性L=L1，L2，...，Lm將H分為集合H1，H2，...，Hm，同時集合Hi=（i=1，2，...，m）又按照類別屬性C=C1，C2，...，Cn分為mn個部分，形成L到C的映射，這種映射定義為分類矩陣，記為AX，C，且：

AX，C=a1l…a1naml…amn

根據(jù)ID3算法的信息增益公式推導(dǎo)，得到分類矩陣的信息增益為Gain（AX，C），表示如下：

Gain（AX，C）={（∑mi=1∑nj=1aij）log2（∑mi=1∑nj=1aij）-∑nj=1（∑mi=1aij）log2（∑mi=1aij）-∑mi=1（∑nj=1aij）log2（∑nj=1aij）+∑mi=1∑nj=1（aijlog2aij）（∑mi=1∑nj=1aij）}（4）

為解決ID3算法多值偏向性問題，該算法引入權(quán)重因子Z，將Q暫時作為屬性選擇標(biāo)準(zhǔn)，其中Q=z×Gain（AX，C），Z=1/log2m，m為屬性L的取值個數(shù)，即屬性的選擇標(biāo)準(zhǔn)修改為[30]：

tempGain（AX，C）=Gain（AX，C）log2m（5）

引入權(quán)重因子Z，使增益在[0，1]范圍內(nèi)比較，這種比較更固定、更準(zhǔn)確，同時提高計算速度。當(dāng)取值的非類別屬性個數(shù)相差很大時，基于分類矩陣的改進(jìn)算法能準(zhǔn)確、高效地找出非類別屬性。

2.4 其它ID3改進(jìn)算法

除上述改進(jìn)算法外，研究者還提出如下改進(jìn)算法：基于神經(jīng)網(wǎng)絡(luò)的分類改進(jìn)算法[31]、基于相關(guān)系數(shù)的決策樹優(yōu)化算法[32]、基于樸素貝葉斯與ID3 算法的決策樹分類[33]、粗糙模糊決策樹歸納算法[34]等。

3 部分改進(jìn)算法實驗分析

實驗采用UCI數(shù)據(jù)庫中的6個數(shù)據(jù)集（見表1）進(jìn)行對比分析，其中3個較小的數(shù)據(jù)集和3個較大的數(shù)據(jù)集中，所有數(shù)據(jù)均為離散型，無缺失數(shù)據(jù)。實驗前，選取1/3樣本作為訓(xùn)練集，其余2/3樣本作為測試集，利用文獻(xiàn)[35]對數(shù)據(jù)集中連續(xù)屬性進(jìn)行離散化處理。

在同一臺電腦上，運用MATLAB工具對數(shù)據(jù)集進(jìn)行實驗分析，分別對6個UCI數(shù)據(jù)集進(jìn)行30次實驗， 連續(xù)重復(fù)分類500次，利用測試集進(jìn)行測試，取平均值作為分類的精確率。將較小的數(shù)據(jù)集Wine、Balance-Scale、Car Evaluation用傳統(tǒng)ID3和改進(jìn)分類算法進(jìn)行對比以驗證分類精確率，將較大的數(shù)據(jù)集Nursery、Adult、Bank Marketing用傳統(tǒng)ID3和改進(jìn)分類算法進(jìn)行對比，驗證分類精確率，得到實驗數(shù)據(jù)如表2、表3所示。

基于粗糙集改進(jìn)算法和基于分類矩陣的改進(jìn)算法都是針對ID3分類算法的多值偏向性問題對算法進(jìn)行改進(jìn)。但從實驗過程和結(jié)果可以看出，基于粗糙集的改進(jìn)算法不太適合數(shù)據(jù)集較大的分類模式，對于較小的數(shù)據(jù)集分類效果明顯。若取值的非類別屬性個數(shù)相差很大時，基于分類矩陣的改進(jìn)算法能準(zhǔn)確、高效地找出非類別屬性，分類方法優(yōu)于粗糙集的改進(jìn)方法?；诹Ｓ嬎愕母倪M(jìn)算法處理較大數(shù)據(jù)集時，分類速度快，由于該算法沒有解決多值偏向性問題，因此在處理較小數(shù)據(jù)集時，分類速度會低于傳統(tǒng)的ID3算法。基于粒計算的改進(jìn)算法在數(shù)據(jù)集群下更有效果，很適用于當(dāng)前背景下的大數(shù)據(jù)分類分析。

4 結(jié)語

大數(shù)據(jù)已成為信息時代的一大新興產(chǎn)業(yè)，并引起了國內(nèi)外政府、學(xué)術(shù)界和產(chǎn)業(yè)界的高度關(guān)注，許多國家將大數(shù)據(jù)發(fā)展提升至戰(zhàn)略高度。自2009年的聯(lián)合國“全球脈動計劃”，經(jīng)過2012年美國的“大數(shù)據(jù)研究和發(fā)展倡議”，到現(xiàn)在包括各國各級政府層面、學(xué)術(shù)層面和產(chǎn)業(yè)層面的廣泛關(guān)注，使得大數(shù)據(jù)成為最新的、最具魅力的研究領(lǐng)域。當(dāng)前，大數(shù)據(jù)技術(shù)研究風(fēng)起云涌，大數(shù)據(jù)的“4V”特點（容量、多樣性、速度和價值），使得大數(shù)據(jù)的研究面臨許多新的挑戰(zhàn)，如何對大數(shù)據(jù)中的知識進(jìn)行提取是目前研究的重點。

知識提取方法研究主要針對關(guān)系數(shù)據(jù)庫，包括結(jié)構(gòu)化的靜態(tài)和動態(tài)數(shù)據(jù)知識提取方法研究，半結(jié)構(gòu)化的靜態(tài)和動態(tài)數(shù)據(jù)知識提取方法研究，非結(jié)構(gòu)化的靜態(tài)和動態(tài)數(shù)據(jù)知識提取方法研究等。采用決策樹分類算法，發(fā)現(xiàn)存在于數(shù)據(jù)間的蘊(yùn)含關(guān)系，對數(shù)據(jù)進(jìn)行快速的挖掘分析，提取數(shù)據(jù)中的價值。

本文歸納總結(jié)了多種經(jīng)典的ID3改進(jìn)算法，從實驗結(jié)果來看，都要優(yōu)于最初的ID3分類算法，分類效率大大提高，分類結(jié)果也很好。隨著數(shù)據(jù)挖掘技術(shù)的不斷發(fā)展，結(jié)合更多領(lǐng)域的專業(yè)知識，研究者們會提出更理想的ID3分類算法。在發(fā)展大數(shù)據(jù)技術(shù)的背景下，ID3分類算法將會應(yīng)用到更多的技術(shù)領(lǐng)域。

參考文獻(xiàn)：

[1] 張鳳蓮，林健良.新的決策樹構(gòu)造方法[J].計算機(jī)工程與應(yīng)用，2009，45（10）：141-143.

[2] 武獻(xiàn)宇，王建芬，謝金龍.決策樹ID3算法研究與優(yōu)化[J].微型機(jī)與應(yīng)用，2010，29（21）：7-9.

[3] 潘大勝，屈遲文.一種改進(jìn)ID3型決策樹挖掘算法[J].華僑大學(xué)學(xué)報，2016，37（1）：71-73.

[4] 李瑞，徐旭睿.決策樹ID3算法的分析與優(yōu)化[J].大連交通大學(xué)學(xué)報，2015，36（2）：91-95.

[5] 黃宇達(dá)，范太華.決策樹ID3算法的分析與優(yōu)化[J].計算機(jī)工程與設(shè)計，2012，33（8）：3089-3093.

[6] 王永梅，胡學(xué)鋼.決策樹中ID3算法的研究[J].安徽大學(xué)學(xué)報，2011，35（3）：71-75.endprint

[7] 羅雨滋，付興宏.數(shù)據(jù)挖掘ID3決策樹分類算法及其改進(jìn)算法[J].計算機(jī)系統(tǒng)應(yīng)用，2013，22（10）：136-138，187.

[8] 王小巍，魏玉明.決策樹ID3算法的分析與改進(jìn)[J].計算機(jī)工程與設(shè)計，2011，32（9）：3069-3072，3076.

[9] 張琳，陳燕，李桃迎，等.決策樹分類算法研究[J].計算機(jī)工程，2011，37（13）：66-67，70.

[10] KIIT，ROHTAK.Comparative study of popular classification techniques of data mining[J].International Journal of Advance Research in Computer Science and Management Studies，2015，3（9）：267-272.

[11] 喻金平，黃細(xì)妹，李康順.基于一種新的屬性選擇標(biāo)準(zhǔn)的ID3改進(jìn)算法[J].計算機(jī)應(yīng)用研究，2012，29（8）：2895-2898，2908.

[12] 胡煜，鄭娟.基于粗糙集理論的ID3算法的改進(jìn)與應(yīng)用[J].貴陽學(xué)院學(xué)報，2015，10（1）：16-20.

[13] 韓家煒.數(shù)據(jù)挖掘：概念與技術(shù)[M].第3版.范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2012：213-218.

[14] PAWLAK Z.Rough set[J].International Journal of Infor-mation and Computer Sciences，1982，11（5）：341-356.

[15] PAWLAK Z，SKOWRON A.Rough sets and Boolean reasoning[J].Information Sciences，2006，177（1）：41-73.

[16] PAWLAK Z，SKOWRON A.Rudiments of rough sets[J].Infor-mation Sciences，2007，177（1）：3-27.

[17] 翟俊海，王熙照，張滄生.基于粗糙集技術(shù)的決策樹歸納[J].計算機(jī)工程與應(yīng)用，2009，45（18）：45-47.

[18] 丁春榮，李龍澍，楊寶華.基于粗糙集的決策樹構(gòu)造算法[J].計算機(jī)工程，2010，36（11）：75-77.

[19] 王越，萬洪.一種新的應(yīng)用變精度粗糙集的決策樹構(gòu)造方法[J].重慶理工大學(xué)學(xué)報，2013，21（11）：58-64.

[20] 章曉，何熊熊，朱忠記，等.基于粗糙方法的決策樹多值偏向理論分析[J].杭州：電子科技大學(xué)學(xué)報，2014，32（2）：41-44.

[21] 翟俊海，翟夢堯，李勝杰.基于相容粗糙集技術(shù)的連續(xù)值屬性決策樹歸納[J].計算機(jī)科學(xué)，2012，39（11）：183-186.

[22] 張素蘭，郭平，張繼福，等.圖像語義自動標(biāo)注及其粒度分析方法[J].自動化學(xué)報，2012，38（5）：689-697.

[23] YAO YY.Reational interpretation of neighborhood operators and rough set approximation operators[J].Information Sciences，1998，111（198）：239-259.

[24] 周浩，劉萍，邱桃榮，等.基于粒計算的決策樹并行算法的應(yīng)用[J].計算機(jī)工程與設(shè)計，2015，36（6）：1504-1509.

[25] 徐劍鋒，劉斕，邱桃榮，等.基于粒計算的二進(jìn)制矩陣及在決策樹算法的應(yīng)用[J].廣西師范大學(xué)學(xué)報，2008，26（3）：158-159.

[26] 錢網(wǎng)偉.基于MapReduce的ID3決策樹分類算法研究[J].計算機(jī)與現(xiàn)代化，2012，28（2）：28-29.

[27] WU G，LI H，HU X，et al.MReC4.5：C4.5 ensemble classification with MapReduce[C].ChinaGrid Annual Conference，2009：249-255.

[28] HE Q，ZHANG F，LI J，et al.Parallel implementation of classification algorithms based on MapReduce[M].Rough Set and Knowledge Technology.Springer Berlin Heidelberg，2010：655-662.

[29] 陸秋.基于MapReduce的決策樹算法并行化[J].計算機(jī)應(yīng)用，2012，32（9）：2463-2469.

[30] 陶道強(qiáng)，馬良荔，彭超.基于分類矩陣的決策樹算法[J].計算機(jī)工程與設(shè)計，2012，33（6）：2309-2313.

[31] 楊林，富元齋，黃立平.基于神經(jīng)網(wǎng)絡(luò)的分類算法的改進(jìn)[J].計算機(jī)工程與應(yīng)用，2002（5）：71-73.

[32] 董躍華，劉力.基于相關(guān)系數(shù)的決策樹優(yōu)化算法[J].計算機(jī)工程與科學(xué)，2015，37（9）：1783-1793.

[33] 黃宇達(dá)，王迤冉.基于樸素貝葉斯與ID3 算法的決策樹分類[J].計算機(jī)工程，2012，38（14）：41-47.

[34] 翟俊海，侯少星，王熙照.粗糙模糊決策樹歸納算法[J].南京大學(xué)學(xué)報，2016，52（2）：306-312.

[35] HU X，CERCONE N.Data mining via generalization discrimin-tion and rough set feature selection[J].Konwledge and Infomation System：an International Journal，1999（1）：21-27.endprint