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

朱金壇

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

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

朱金壇

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

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

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

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

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

1 ID3算法基本思想

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

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

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

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

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

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

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

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

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

步驟5 計(jì)算各屬性對(duì)應(yīng)的綜合評(píng)價(jià)指數(shù)N。

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

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

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

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

表1 測(cè)試樣本集

具體的過(guò)程如下。

(1)首先利用屬性對(duì)測(cè)試樣本集中記錄進(jìn)行統(tǒng)計(jì)分組，并計(jì)算出樣本子集分組數(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/檢驗(yàn)標(biāo)志={{1},{2},{3},{4},{5},{6},
{7},{8},{9},{10},{11},{12},{13},{14}}，
I/檢驗(yàn)標(biāo)志=1。

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

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

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

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

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

(4)計(jì)算各屬性對(duì)應(yīng)的綜合評(píng)價(jià)指數(shù)

根據(jù)公式N=K+δ計(jì)算年齡段、病情度、手術(shù)、誘發(fā)病因和檢驗(yàn)標(biāo)志、屬性的綜合評(píng)價(jià)指數(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/檢驗(yàn)標(biāo)志=0+1/14=1/14=0.071。

由此得到，將屬性中的誘發(fā)病因作為測(cè)試屬性的原因是因?yàn)槠渥罱K的綜合評(píng)價(jià)指數(shù)最大。接著可以從中分裂出3個(gè)子樣本集

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

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

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

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/檢驗(yàn)標(biāo)志={{1}，{4}，{11}，{13}，{14}},

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

由此得到U1子樣本集中各個(gè)屬性綜合評(píng)價(jià)指數(shù)為

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

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

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

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

圖1 決策樹(shù)生成圖

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

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

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

輸出：一棵決策樹(shù)。

方法：

Generate_decision_tree(samples, attribute_list)

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

(2) if samples 都在同一個(gè)類別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í)驗(yàn)中涉及的時(shí)間以本地計(jì)算機(jī)上的執(zhí)行時(shí)間為準(zhǔn)，選取兩個(gè)不同的數(shù)據(jù)集作為決策樹(shù)生成仿真的實(shí)驗(yàn)數(shù)據(jù)，仿真實(shí)驗(yàn)的測(cè)試環(huán)境為Intel Core i5-3210M 2.5GHz，內(nèi)存為 2G。仿真實(shí)驗(yàn)的整個(gè)流程如圖2所示。

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

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

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

表3 測(cè)試結(jié)果

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

5 結(jié) 論

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

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

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

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

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

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

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

[7] 王熙照,楊晨曉.分支合并對(duì)決策樹(shù)歸納學(xué)習(xí)的影響[J].計(jì)算機(jī)學(xué)報(bào),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é)報(bào):自然科學(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é)基金資助項(xiàng)目 (2012JQ8050)

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

TP301

A

2095-6533(2014)01-0037-05