迭代二叉樹3代算法的一種改進(jìn)

朱金壇

(西安鐵路職業(yè)技術(shù)學(xué)院 電子信息系, 陜西 西安 710014)

迭代二叉樹3代算法的一種改進(jìn)

朱金壇

(西安鐵路職業(yè)技術(shù)學(xué)院 電子信息系, 陜西 西安 710014)

針對數(shù)據(jù)挖掘決策樹中迭代二叉樹3代算法復(fù)雜的對數(shù)運(yùn)算以及屬性取值多向依賴的缺陷，提出了一種改進(jìn)算法。該算法將對數(shù)運(yùn)算改進(jìn)為簡易的普通運(yùn)算，引入重要度、關(guān)聯(lián)度概念以及調(diào)整系數(shù)，形成一個綜合評價指數(shù)來確定作為決策樹生成的劃分結(jié)點(diǎn)的屬性。仿真結(jié)果表明，改進(jìn)算法簡化了計算過程、提高了運(yùn)算效率，同時使得決策樹的形成不依賴屬性多值取向。

迭代二叉樹3代算法(ID3);決策樹；粗糙集論；重要度；關(guān)聯(lián)度

伴隨信息技術(shù)的快速發(fā)展，數(shù)據(jù)量正在以驚人的速度增長，“豐富的數(shù)據(jù)與貧乏的知識”之間的矛盾日見突出。數(shù)據(jù)挖掘作為一種能夠從海量數(shù)據(jù)中尋求有用信息的工具，在各個領(lǐng)域廣泛應(yīng)用[1]。

目前，決策樹[2-3]已成為一種重要的數(shù)據(jù)挖掘方法，而在決策樹構(gòu)造中，迭代二叉樹3代(Iterative Dichotomiser 3， ID3)算法[4]作為最具有影響力的一種決策樹生成算法，其清晰的理論基礎(chǔ)、簡單易懂的建樹思路，能得到功能較佳的樹形結(jié)構(gòu)。通過此算法得到的知識規(guī)則很容易被理解和使用，但在分類過程中存在對數(shù)運(yùn)算量較多、計算復(fù)雜度倍增，偏向?qū)傩匀≈递^多等缺點(diǎn)。之后Quinlan提出的C4.5[5]算法，與統(tǒng)計方法、神經(jīng)網(wǎng)絡(luò)[6]等分類算法相比，產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高,但在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外C4.5算法只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大到無法在內(nèi)存容納時程序無法運(yùn)行。本文根據(jù)粗糙集論中有關(guān)屬性重要度和關(guān)聯(lián)度的概念[7-9]，針對ID3算法復(fù)雜的對數(shù)運(yùn)算以及屬性取值多向依賴的問題，對決策樹ID3算法進(jìn)行改進(jìn)。

1 ID3算法基本思想

在利用決策樹構(gòu)造方法時需充分考慮選取哪個屬性作為形成決策樹的決策結(jié)點(diǎn)。選擇的依據(jù)是比較誰能最大程度測試樣本集的分類特征。

分類決策樹算法ID3基本思想是：將熵的概念從信息論[9]當(dāng)中抽取出來，屬性分類的能力由屬性的信息增益來決定。選取其中信息增益最大者為決策結(jié)點(diǎn)屬性，之后進(jìn)行結(jié)點(diǎn)的擴(kuò)展工作，所依據(jù)為該屬性的不同取值。再對各分支所對應(yīng)的樣本子集使用遞歸調(diào)用ID3算法的方法來建立決策樹的分支結(jié)點(diǎn)或葉子結(jié)點(diǎn)，同時使用決策樹不在生長的三個必要條件進(jìn)行判斷。ID3算法建立決策樹是采用了信息增益最大的屬性來進(jìn)行。該算法使得所形成的決策樹保證了最小分支和最小冗余。

2 改進(jìn)算法的思路及步驟

改進(jìn)算法主要針對ID3算法存在的計算過程復(fù)雜與對屬性多值取向依賴的問題，采取了簡易的運(yùn)算過程和精確的決策樹生成方法。主要思路是將原算法中較難計算的對數(shù)運(yùn)算改進(jìn)為簡易的普通運(yùn)算；同時根據(jù)粗糙集理論知識，引入重要度、關(guān)聯(lián)度的概念以及調(diào)整系數(shù)，最終形成一個綜合評價指數(shù)來確定作為決策樹生成的劃分結(jié)點(diǎn)的屬性。

設(shè)定測試樣本集為U，樣本集包含的記錄數(shù)為D，樣本屬性個數(shù)為M，關(guān)聯(lián)度為K，調(diào)整系數(shù)為δ(0<δ≤1)，樣本子集分組數(shù)最大度量為I，綜合評價指數(shù)為N。其中調(diào)整系數(shù)δ=I/D，綜合評價指數(shù)N=K+δ(當(dāng)關(guān)聯(lián)度不為零的時候使用)，再一次對多值取向問題進(jìn)行精確改進(jìn)，防止大數(shù)據(jù)掩蓋小數(shù)據(jù)現(xiàn)象的發(fā)生，提高算法的效率和精確度。具體執(zhí)行步驟如下。

步驟1 先確定要進(jìn)行決策樹生成的測試樣本集，按照不同的屬性將樣本集中的記錄進(jìn)行分組，得到以編號為集合的分組記錄。

步驟2 計算按照屬性進(jìn)行分組后的各分組記錄中的最大度量I值。

步驟3 根據(jù)粗糙集論中關(guān)于對屬性重要度知識的描述，計算樣本集屬性的關(guān)聯(lián)度K值。

步驟4 根據(jù)步驟2得到的最大度量I值及本次分組樣本集包含的記錄數(shù)D，計算各屬性對應(yīng)的調(diào)整系數(shù)δ值。

步驟5 計算各屬性對應(yīng)的綜合評價指數(shù)N。

步驟6 由步驟5得到的綜合評價指數(shù)N判斷選擇哪一個屬性作為結(jié)點(diǎn)進(jìn)行進(jìn)一步的劃分。

步驟7 重復(fù)以上步驟直至所有的葉子結(jié)點(diǎn)都?xì)w屬同一個類別時，結(jié)束結(jié)點(diǎn)的劃分，得到分類決策樹，并提取分類規(guī)則。

3 改進(jìn)算法實(shí)例

通過某醫(yī)院“病情信息系統(tǒng)”的樣本數(shù)據(jù)集實(shí)例來闡述改進(jìn)算法的整個執(zhí)行過程。表1為患者信息系統(tǒng)的樣本數(shù)據(jù)集。用U表示整個訓(xùn)練樣本集,年齡段、病情度、手術(shù)、誘發(fā)病因是條件屬性,為了較為容易地對ID3算法及改進(jìn)算法進(jìn)行比較，在樣本集中新增加了一個檢驗屬性，它是5個條件屬性中取值最多的，分類則為決策屬性。

表1 測試樣本集

具體的過程如下。

(1)首先利用屬性對測試樣本集中記錄進(jìn)行統(tǒng)計分組，并計算出樣本子集分組數(shù)最大度量I。

U/類別={{1,2,3,4,5,6,7,8,9},
{10,11,12,13,14}}，
U/年齡段={{1,2,3,10},
{4,5,6,7,11,12},{8,9,13,14}}，
I/年齡段=6，
U/病情度={{1,2,3,4,6,9,10},
{5,7,8,11,12,13,14}}，
I/病情度=7，
U/手術(shù)={{1,3,6,7,8,9,11,13},
{2,4,5,1,12,14}}，
I/手術(shù)=8，
U/誘發(fā)病因={{1,4,11,13,14},
{2,5,8,9},{3,6,7,10,12}}，
I/誘發(fā)病因=5，
U/檢驗標(biāo)志={{1},{2},{3},{4},{5},{6},
{7},{8},{9},{10},{11},{12},{13},{14}}，
I/檢驗標(biāo)志=1。

(2)計算樣本集屬性的關(guān)聯(lián)度

關(guān)聯(lián)度K描述了利用屬性C能夠?qū)⒄撚騏中的元素正確分類到劃分U/D的塊中的比率。其中U為測試樣本集，C*(X)是由D的劃分U/D中的所有塊的C下近似的并構(gòu)成,稱其為劃分U/D對于C的正域。

(3)計算各屬性對應(yīng)的調(diào)整系數(shù)

根據(jù)公式δ=I/D計算年齡段、病情度、手術(shù)、誘發(fā)病因和檢驗標(biāo)志屬性的調(diào)整系數(shù)。

δ/年齡段=6/14=0.429，
δ/病情度=7/14=0.5 ，
δ/手術(shù)=8/14=0.571，
δ/誘發(fā)病因=5/14=0.357，
δ/檢驗標(biāo)志= 1/14=0.071。

(4)計算各屬性對應(yīng)的綜合評價指數(shù)

根據(jù)公式N=K+δ計算年齡段、病情度、手術(shù)、誘發(fā)病因和檢驗標(biāo)志、屬性的綜合評價指數(shù)。

N/年齡段=0+6/14=0.429，
N/病情度=0+7/14=0.5，
N/手術(shù)=0+8/14=0.571，
N/誘發(fā)病因=2/7+5/14=0.715，
N/檢驗標(biāo)志=0+1/14=1/14=0.071。

由此得到，將屬性中的誘發(fā)病因作為測試屬性的原因是因為其最終的綜合評價指數(shù)最大。接著可以從中分裂出3個子樣本集

U1={1,4,11,13,14}，
U2={2,5,8,9}，
U3={3,6,7,10,12}，

它們都來自于樣本集合U。分析得到的3個子樣本集，發(fā)現(xiàn)U2不必再進(jìn)行劃分，原因歸結(jié)于其中的元素都屬于A類。據(jù)此得到一個葉子結(jié)點(diǎn)。剩下的U1與U3仍然采用此方法進(jìn)行綜合評價指數(shù)的計算以便確定之后的劃分原則。

具體執(zhí)行過程如下。

U1/分類={{1，4}，{11，13，14}}，
U1/年齡段={{1}，{4，11}，{13，14}}，
關(guān)聯(lián)度K=3/5=0.6，
I1/年齡段=2 ，
δ1/年齡段=2/5=0.4，
U1/病情度={{1，4}，{11，13，14}}，
關(guān)聯(lián)度K=5/5=1，
I/病情度=3，
δ/病情度=3/5=0.6,
U1/手術(shù)={{1，11，13}，{4，14}},
關(guān)聯(lián)度K=0/5=0，
I/手術(shù)=3，
δ/手術(shù)=3/5=0.6

U1/檢驗標(biāo)志={{1}，{4}，{11}，{13}，{14}},

關(guān)聯(lián)度K=0/5=0，
I/檢驗標(biāo)志=1，
δ/檢驗標(biāo)志= 1/5=0.2。

由此得到U1子樣本集中各個屬性綜合評價指數(shù)為

N1/年齡段=0.6+0.4=1,
N1/病情度=1+0.6=1.6 ,
N1/手術(shù)=0+0.6=0.6,
N1/檢驗標(biāo)志=0+0.2=0.2。

由上面的計算結(jié)果得到，U1的子集本集或者屬于A類，或者屬于B類，這些是取決于病情度屬性的綜合評價指數(shù)最大。符合了決策樹停止生長的條件，所以中止本分支樹的劃分。

同樣的方法針對U3子樣本集進(jìn)行運(yùn)算，得到測試屬性為手術(shù)屬性取決于其計算得到的綜合評價指數(shù)最大。最后劃分子樣本集或者屬于A類，或者屬于B類，到此整個劃分也就終止了。

經(jīng)過以上算法過程執(zhí)行，對樣本集屬性的運(yùn)算之后產(chǎn)生了一個決策樹，如圖1所示。

圖1 決策樹生成圖

由此得到?jīng)Q策樹的提取規(guī)則可表示為

算法：Generate_decision_tree(samples, attribute)。由給定樣本集產(chǎn)生一棵決策樹。

輸入：測試樣本集samples，由離散值屬性表示；候選屬性的集合attribute_list。

輸出：一棵決策樹。

方法：

Generate_decision_tree(samples, attribute_list)

(1) 創(chuàng)建結(jié)點(diǎn)N=誘發(fā)病因；

(2) if samples 都在同一個類別then

(3) returnN作為葉結(jié)點(diǎn)，以類A或者B 標(biāo)記

(4) if attribut_list=心悸 then

(5) returnN=“病情度”標(biāo)記為葉結(jié)點(diǎn)

(6) else

(7) if attribut_list=心律不齊 then

(8) returnN=“手術(shù)”標(biāo)記為葉結(jié)點(diǎn)

(9) 遞歸使用Generate_decision_tree(samples, attribute)方法。

(10) ifN=“病情度”

(11) if attribut_list=危急 then

(12) returnN作為葉結(jié)點(diǎn)，標(biāo)記為B

(13) else returnN作為葉結(jié)點(diǎn)，標(biāo)記為A

(14) ifN=“手術(shù)”

(15) if attribut_list=需要 then

(16) returnN作為葉結(jié)點(diǎn)，標(biāo)記為B

(17) else returnN作為葉結(jié)點(diǎn)，標(biāo)記為A

4 改進(jìn)算法仿真

仿真實(shí)驗中涉及的時間以本地計算機(jī)上的執(zhí)行時間為準(zhǔn)，選取兩個不同的數(shù)據(jù)集作為決策樹生成仿真的實(shí)驗數(shù)據(jù)，仿真實(shí)驗的測試環(huán)境為Intel Core i5-3210M 2.5GHz，內(nèi)存為 2G。仿真實(shí)驗的整個流程如圖2所示。

圖2 改進(jìn)算法仿真流程圖

實(shí)驗開始，先從加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫UCI[10]中選取數(shù)據(jù)集，作為仿真實(shí)驗的輸入項進(jìn)行測試比較，其中數(shù)據(jù)集1選為Segment-Challenge,數(shù)據(jù)集2選為Zoo。測試數(shù)據(jù)與測試結(jié)果分別如表2和表3所示。

表2 測試數(shù)據(jù)集

表3 測試結(jié)果

由表3可知，改進(jìn)算法比原始算法的精確度提高，數(shù)據(jù)集Segment-Challenge與Zoo的節(jié)點(diǎn)數(shù)在使用改進(jìn)前后的算法中有了進(jìn)一步減少，算法的耗時也得到縮減。整個決策樹的準(zhǔn)確率得到了提高，規(guī)模整體縮小。

5 結(jié) 論

改進(jìn)算法采取簡易的運(yùn)算過程和精確的決策樹生成方法的分析，使得在決策樹生成速度和精度上都有很大的提高。實(shí)例分析表明,改進(jìn)算法能有效地對屬性進(jìn)行約簡,并且多數(shù)情況下能提高算法效率,減少約簡的計算復(fù)雜度。

[1] 王春梅. 基于數(shù)據(jù)倉庫的數(shù)據(jù)挖掘技術(shù)[J]. 西安郵電學(xué)院學(xué)報,2006,11(5):99-102.

[2] 陶榮,張永勝,杜宏保.基于粗集論中屬性依賴度的ID3改進(jìn)算法[J].河南科技大學(xué)學(xué)報:自然科學(xué)版,2010(1):42-45.

[3] 牛文穎.改進(jìn)的ID3決策樹分類算法在成績分析中的應(yīng)用研究[D].大連：大連交通大學(xué),2008:10-12.

[4] 鄧全.決策樹算法與客戶流失分析[J].西安郵電大學(xué)學(xué)報,2013,18(3):49-51.

[5] 索永強(qiáng),馬力,譚薇.一種改進(jìn)的粗糙集屬性約簡啟發(fā)式算法[J].西安郵電學(xué)院學(xué)報,2009,14(5):116-120.

[6] Giaci G,章子木. 采用神經(jīng)網(wǎng)絡(luò)和統(tǒng)計算法相結(jié)合的方式檢測遠(yuǎn)程傳感圖象分類[J].圖象識別與自動化,2000(2):45-54.

[7] 王熙照,楊晨曉.分支合并對決策樹歸納學(xué)習(xí)的影響[J].計算機(jī)學(xué)報,2008,8 (8):40-43.

[8] 杜巍.基于數(shù)據(jù)挖掘技術(shù)的人力資源信息系統(tǒng)的需求分析[D].濟(jì)南：山東大學(xué), 2009:19-24.

[9] 張先榮.粗糙集理論在智能數(shù)據(jù)分析中的應(yīng)用[J].河南科技大學(xué)學(xué)報:自然科學(xué)版,2008(5):60-65.

[10] 袁凱.多視角協(xié)同訓(xùn)練算法研究[D].西安：西安電子科技大學(xué),2013:51-66.

[責(zé)任編輯:祝劍]

An improved algorithm of iterative dichotomiser 3

ZHU Jintan

(Department of Electronic Information, Xi’an Railway Vocational and Technical Institute, Xi’an 710014, China)

Iterative dichotomiser 3(ID3) algorithm for data mining of complex logarithmic and property values more dependence on defect，This paper presents an improved algorithm. The difficult part of the logarithmic in the original algorithm is improved into an easy one. At the same time, the importance, the concept of correlation degree and the adjustment of the coefficient are introduced in this article. Finally, a comprehensive evaluation index is formed to determine the choice of a property as the division of the decision tree generated notes. Simulation result show that the improved algorithm can simplify the calculation, improve the efficiency of the operation, and make the formation of the decision tress independent of the formation of attribute value orientation.

Iterative Dichotomiser 3 (ID3), decision tree, rough sets, importance degree, correlation degree

10.13682/j.issn.2095-6533.2014.01.007

2013-11-11

陜西省自然科學(xué)基金資助項目 (2012JQ8050)

朱金壇(1981-)，男，碩士，講師，從事算法處理研究及軟件開發(fā)研究。E-mail:zjt_88@126.com

TP301

A

2095-6533(2014)01-0037-05