一種改進(jìn)ID3型決策樹挖掘算法

潘大勝, 屈遲文

(百色學(xué)院 信息工程學(xué)院， 廣西 百色 533000)

?

一種改進(jìn)ID3型決策樹挖掘算法

潘大勝, 屈遲文

(百色學(xué)院 信息工程學(xué)院， 廣西 百色 533000)

摘要：分析經(jīng)典ID3型決策樹挖掘算法中存在的問題，對其熵值計(jì)算過程進(jìn)行改進(jìn)，構(gòu)建一種改進(jìn)的ID3型決策樹挖掘算法.重新設(shè)計(jì)決策樹構(gòu)建中的熵值計(jì)算過程，以獲得具有全局最優(yōu)的挖掘結(jié)果,并針對UCI數(shù)據(jù)集中的6類數(shù)據(jù)集展開挖掘?qū)嶒?yàn).結(jié)果表明：改進(jìn)后的挖掘算法在決策樹構(gòu)建的簡潔程度和挖掘精度上，都明顯優(yōu)于ID3型決策樹挖掘算法.

關(guān)鍵詞：數(shù)據(jù)挖掘； ID3型決策樹； 熵值計(jì)算； UCI數(shù)據(jù)集

數(shù)據(jù)倉庫技術(shù)的出現(xiàn)，成功地解決了大數(shù)據(jù)的存儲和管理問題，并配套數(shù)據(jù)挖掘技術(shù)從海量數(shù)據(jù)中提取最有價值的信息[1-2].數(shù)據(jù)挖掘技術(shù)是從已有數(shù)據(jù)信息中提取有價值信息，甚至形成知識.目前，已經(jīng)出現(xiàn)的數(shù)據(jù)挖掘技術(shù)包括基于機(jī)器學(xué)習(xí)的挖掘技術(shù)、基于聚類分析的挖掘技術(shù)、基于關(guān)聯(lián)規(guī)則的挖掘技術(shù)等[3-5].在各種基于機(jī)器學(xué)習(xí)的挖掘技術(shù)中，決策樹挖掘算法獲得了廣泛的應(yīng)用[6-12].ID3型決策樹挖掘法是最經(jīng)典的決策樹挖掘算法之一.在決策樹的各級節(jié)點(diǎn)上，采用信息增益構(gòu)建屬性選擇依據(jù)，最高的信息增益屬性最終會被確定為節(jié)點(diǎn)的判別標(biāo)準(zhǔn)，這樣就可以達(dá)成訓(xùn)練樣本的信息最小化，提升決策樹的構(gòu)建速度，并簡化決策樹的結(jié)構(gòu).本文在經(jīng)典ID3型決策樹算法的基礎(chǔ)上，構(gòu)建一種改進(jìn)型的決策樹挖掘算法.

1改進(jìn)的決策樹挖掘算法

經(jīng)典的ID3型決策樹挖掘算法具有搜索空間完整、測試次數(shù)少、分類挖掘速度快、構(gòu)建的決策樹節(jié)點(diǎn)少、適合于噪聲數(shù)據(jù)和離散數(shù)據(jù)的挖掘等優(yōu)點(diǎn).然而，其最大的局限性在于它的建樹原則是依據(jù)信息熵理論計(jì)算出的屬性增益.這種算法選取出的最佳屬性是一種多值屬性，并不一定是最優(yōu)的，導(dǎo)致其挖掘結(jié)果往往只具有局部最優(yōu)的特性，而無法達(dá)到全局最優(yōu).文中對經(jīng)典的ID3型決策樹算法進(jìn)行改進(jìn)，構(gòu)建一種能夠達(dá)到全局最優(yōu)的決策樹.

信息熵值的計(jì)算是ID3型決策樹算法挖掘過程實(shí)現(xiàn)的關(guān)鍵.文中主要對熵值的計(jì)算進(jìn)行改進(jìn)，進(jìn)而在此基礎(chǔ)上重新設(shè)計(jì)執(zhí)行流程.在經(jīng)典ID3型決策樹算法中，屬性A在計(jì)算過程中會出現(xiàn)多值，選取這些值的個數(shù)作為權(quán)重系數(shù)，融入屬性A的熵值計(jì)算中.

假設(shè)屬性A存在m個屬性，這些屬性出現(xiàn)的概率用p1,p2,…,pm表示，屬性A作為節(jié)點(diǎn)對應(yīng)的m個子節(jié)點(diǎn)可以用屬性值集合表示為{θ1,θ2,…,θm}，這些屬性值對應(yīng)的信息熵G(θ1),G(θ2),…,G(θm).改進(jìn)算法最終設(shè)計(jì)的用于計(jì)算屬性A的熵,其表達(dá)式為

改進(jìn)決策樹算法主要有以下5個執(zhí)行步驟.

步驟1對于任意一個屬性Ai，假設(shè)它有mi個屬性值，可以用{θ1,θ2,…,θmi}表示.這些屬性值對應(yīng)的概率分別為p1,p2,…,pmi，其中,每個屬性值對應(yīng)的信息熵計(jì)算式為

步驟2借助式(1)計(jì)算屬性Ai對應(yīng)的熵.

步驟3按照步驟1，2的方法，繼續(xù)計(jì)算屬性Ai+1,Ai+2,…對應(yīng)的熵值，并從所有的熵值中，選擇最小的熵值所對應(yīng)的屬性為節(jié)點(diǎn).

步驟4按照步驟1～3的方法，繼續(xù)各個后繼節(jié)點(diǎn).

步驟5當(dāng)新一輪計(jì)算結(jié)果確定的各個節(jié)點(diǎn)為葉子節(jié)點(diǎn)時，決策樹構(gòu)建完畢；否則,繼續(xù)執(zhí)行以上各步驟.

2驗(yàn)證性實(shí)驗(yàn)

2.1　實(shí)驗(yàn)所用數(shù)據(jù)集

為了驗(yàn)證文中算法的有效性，選擇6種加利福尼亞大學(xué)的UCI測試數(shù)據(jù)集(Wine，Spect Heart，Balance Scale，Vehicle Silhouettes，Hill Valley，Yeast)執(zhí)行數(shù)據(jù)挖掘?qū)嶒?yàn).

Wine數(shù)據(jù)集是用于判斷白酒種類的化學(xué)成分?jǐn)?shù)據(jù)，這些數(shù)據(jù)主要來自產(chǎn)于意大利的白酒，這些化學(xué)成分涉及酒精、果酸、黃酮等.Wine數(shù)據(jù)集中含有178個樣本數(shù)據(jù),13個整數(shù)屬性,3個分類類別.

Spect Heart數(shù)據(jù)集是根據(jù)CT圖像判斷病患心臟是否正常的數(shù)據(jù)集，這些數(shù)據(jù)是根據(jù)質(zhì)子發(fā)射CT掃描結(jié)果得出的.Spect Heart數(shù)據(jù)集中含有267個樣本數(shù)據(jù),22個屬性特征，每個屬性只有“-1”和“1”兩種表達(dá)可能,2個分類類別，即正常和不正常.

Balance Scale數(shù)據(jù)集是根據(jù)心理學(xué)實(shí)驗(yàn)判斷天平是否平衡的數(shù)據(jù)集，這些數(shù)據(jù)根據(jù)天平2個托盤的質(zhì)量、距離和測試者的心理判斷天平是否會發(fā)生傾斜.Balance Scale數(shù)據(jù)集中含有625個樣本數(shù)據(jù)，每個樣本數(shù)據(jù)含有4個屬性特征，這些屬性需要在“1，2，3，4，5”中取值，3個分類類別(左側(cè)傾斜、右側(cè)傾斜、平衡).

Vehicle Silhouettes數(shù)據(jù)集是根據(jù)圖像的二維特征信息判斷汽車類別所形成的數(shù)據(jù)集合.Vehicle Silhouettes數(shù)據(jù)集中含有846個樣本數(shù)據(jù)，每個樣本數(shù)據(jù)含有18個屬性特征，這些屬性需要在整數(shù)空間上取值，4個分類類別.

Hill Valley數(shù)據(jù)集是用于判斷多數(shù)據(jù)點(diǎn)連接曲線后凹凸形狀的數(shù)據(jù)集，它先將100個數(shù)據(jù)點(diǎn)連接成曲線，再判斷曲線的凹凸形狀.Hill Valley數(shù)據(jù)集中含有1 212個樣本數(shù)據(jù)，每個樣本數(shù)據(jù)含有100個屬性，這些屬性在實(shí)數(shù)空間上取值，2個分類類別.

Yeast數(shù)據(jù)集是利用據(jù)蛋白質(zhì)成分推測細(xì)胞位置的數(shù)據(jù)集.Yeast數(shù)據(jù)集含有1 484個樣本數(shù)據(jù)，每個樣本數(shù)據(jù)含有8個屬性，這些屬性在實(shí)數(shù)空間上取值，10個分類類別.

表1　ID3算法與改進(jìn)算法的性能對比結(jié)果

2.2　ID3算法與改進(jìn)算法的實(shí)驗(yàn)對比

分別采用ID3型算法和改進(jìn)算法執(zhí)行挖掘分類實(shí)驗(yàn)，結(jié)果如表1所示.ID3算法與改進(jìn)算法在決策樹構(gòu)建的節(jié)點(diǎn)數(shù)和挖掘精度上的對比結(jié)果，如表1所示.

由表1可知：改進(jìn)算法相比于經(jīng)典的ID3算法，其構(gòu)建的決策樹的節(jié)點(diǎn)數(shù)量更少，表明改進(jìn)算法構(gòu)建的決策樹更加精簡，且在挖掘精度方面也有明顯的提高.

3結(jié)束語

針對ID3型決策樹挖掘算法中存在的數(shù)據(jù)挖掘問題，重新設(shè)計(jì)ID3型決策樹構(gòu)建中的熵值計(jì)算過程，構(gòu)建一種改進(jìn)的ID3型決策樹挖掘算法.通過UCI數(shù)據(jù)集中的6種數(shù)據(jù)集展開實(shí)驗(yàn)，結(jié)果表明改進(jìn)算法具有更精簡的決策樹結(jié)構(gòu)、更高的挖掘精度，優(yōu)于ID3型決策樹挖掘算法.

參考文獻(xiàn)：

[1]SETTOUTI N,AOURAG H.A comparative study of the physical and mechanical properties of hydrogen using data mining research techniques[J].JOM：the Journal of the Minerals, Metals & Materials Society,2015,67(9):2145-2153.

[2]沈偉.基于數(shù)據(jù)挖掘技術(shù)的高職院校招生決策倉庫設(shè)計(jì)與實(shí)現(xiàn)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2015(3):165-167.

[3]錢昭勇,陳梅.數(shù)據(jù)挖掘技術(shù)在突發(fā)事件應(yīng)急系統(tǒng)中的應(yīng)用與研究[J].電子技術(shù)與軟件工程,2014,19(8):217.

[4]PALACIOS A,MARTINEZ A,SANCHEZ L,et al.Sequential pattern mining applied to aeroengine condition monitoring with uncertain health data[J].Engineering Applications of Artifical Intelligence,2015,44:10-24.

[5]羅來曦,朱漁.以XML為基礎(chǔ)的Web數(shù)據(jù)挖掘技術(shù)系統(tǒng)的框架設(shè)計(jì)與實(shí)現(xiàn)[J].電子技術(shù)與軟件工程,2014,15(7):201.

[6]BANAEE H,LOUTFI A.Data driven rule mining and representation of temporal patterns in physiological sensor data[J].IEEE Journal of Biomedical and Health Informatics,2015,19(5):1557-1566.

[7]PORRO-MUNOZ D,OLIVETTI E,SHARMIN N,et al.Tractome: A visual data mining tool for brain connectivity analysis[J].Data Mining and Knowledge Discovery,2015,29(5):1248-1279.

[8]吳春瓊,胡國柱,徐靜.高職院校項(xiàng)目驅(qū)動模式下基于數(shù)據(jù)挖掘決策樹分類的教學(xué)效果分析[J].呂梁教育學(xué)院學(xué)報(bào),2015,32(10):18-21.

[9]李楠,段隆振,陳萌.決策樹C4.5算法在數(shù)據(jù)挖掘中的分析及其應(yīng)用[J].計(jì)算機(jī)與現(xiàn)代化,2008,160(12):160-163.

[10]高媛媛.基于數(shù)據(jù)挖掘的財(cái)務(wù)舞弊識別研究：決策樹-神經(jīng)網(wǎng)絡(luò)組合模型的構(gòu)建[J].科技經(jīng)濟(jì)市場,2014(11):93-95.

[11]ELYASIGOMARI V,MIRJAFARI M S,SCREEN H R C,et al.Cancer classification using a novel gene selection approach by means of shuffling based on data clustering with optimization[J].Applied Soft Computing,2015, 35:43-51.

[12]李翔,劉韶濤.FP-Growth的并行加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,35(5):523-527.

(責(zé)任編輯： 黃曉楠英文審校： 吳逢鐵)

An Improved ID3 Decision Tree Mining Algorithm

PAN Dasheng, QU Chiwen

(School of Information Engineering， Baise University, Baise 533000, China)

Abstract：By analyzing the problem of ID3 decision tree mining algorithm, the entropy calculation process is improved, and a kind of improved ID3 decision tree mining algorithm is built. Entropy calculation process of decision tree is redesigned in order to obtain global optimal mining results. The mining experiments are carried out on the UCI data category 6 data set. Experimental results show that the improved mining algorithm is much better than the ID3 type decision tree mining algorithm in the compact degree and the accuracy of the decision tree construction.

Keywords：data mining; ID3 decision tree; entropy calculation; UCI data set

基金項(xiàng)目：廣西自然科學(xué)基金青年基金資助項(xiàng)目(2014GXNSFBA118283)

通信作者：潘大勝(1975-)，男，副教授，主要從事數(shù)據(jù)挖掘技術(shù)的研究.E-mail:bspandsh@163.com.

收稿日期：2015-11-13

中圖分類號：TP 301.6

文獻(xiàn)標(biāo)志碼：A

doi:10.11830/ISSN.1000-5013.2016.01.0071

文章編號：1000-5013(2016)01-0071-03