一種改進ID3型決策樹挖掘算法

潘大勝, 屈遲文

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

?

一種改進ID3型決策樹挖掘算法

潘大勝, 屈遲文

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

摘要：分析經典ID3型決策樹挖掘算法中存在的問題，對其熵值計算過程進行改進，構建一種改進的ID3型決策樹挖掘算法.重新設計決策樹構建中的熵值計算過程，以獲得具有全局最優的挖掘結果,并針對UCI數據集中的6類數據集展開挖掘實驗.結果表明：改進后的挖掘算法在決策樹構建的簡潔程度和挖掘精度上，都明顯優于ID3型決策樹挖掘算法.

關鍵詞：數據挖掘； ID3型決策樹； 熵值計算； UCI數據集

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

1改進的決策樹挖掘算法

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

信息熵值的計算是ID3型決策樹算法挖掘過程實現的關鍵.文中主要對熵值的計算進行改進，進而在此基礎上重新設計執行流程.在經典ID3型決策樹算法中，屬性A在計算過程中會出現多值，選取這些值的個數作為權重系數，融入屬性A的熵值計算中.

假設屬性A存在m個屬性，這些屬性出現的概率用p1,p2,…,pm表示，屬性A作為節點對應的m個子節點可以用屬性值集合表示為{θ1,θ2,…,θm}，這些屬性值對應的信息熵G(θ1),G(θ2),…,G(θm).改進算法最終設計的用于計算屬性A的熵,其表達式為

改進決策樹算法主要有以下5個執行步驟.

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

步驟2借助式(1)計算屬性Ai對應的熵.

步驟3按照步驟1，2的方法，繼續計算屬性Ai+1,Ai+2,…對應的熵值，并從所有的熵值中，選擇最小的熵值所對應的屬性為節點.

步驟4按照步驟1～3的方法，繼續各個后繼節點.

步驟5當新一輪計算結果確定的各個節點為葉子節點時，決策樹構建完畢；否則,繼續執行以上各步驟.

2驗證性實驗

2.1　實驗所用數據集

為了驗證文中算法的有效性，選擇6種加利福尼亞大學的UCI測試數據集(Wine，Spect Heart，Balance Scale，Vehicle Silhouettes，Hill Valley，Yeast)執行數據挖掘實驗.

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

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

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

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

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

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

表1　ID3算法與改進算法的性能對比結果

2.2　ID3算法與改進算法的實驗對比

分別采用ID3型算法和改進算法執行挖掘分類實驗，結果如表1所示.ID3算法與改進算法在決策樹構建的節點數和挖掘精度上的對比結果，如表1所示.

由表1可知：改進算法相比于經典的ID3算法，其構建的決策樹的節點數量更少，表明改進算法構建的決策樹更加精簡，且在挖掘精度方面也有明顯的提高.

3結束語

針對ID3型決策樹挖掘算法中存在的數據挖掘問題，重新設計ID3型決策樹構建中的熵值計算過程，構建一種改進的ID3型決策樹挖掘算法.通過UCI數據集中的6種數據集展開實驗，結果表明改進算法具有更精簡的決策樹結構、更高的挖掘精度，優于ID3型決策樹挖掘算法.

參考文獻：

[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]沈偉.基于數據挖掘技術的高職院校招生決策倉庫設計與實現[J].網絡安全技術與應用,2015(3):165-167.

[3]錢昭勇,陳梅.數據挖掘技術在突發事件應急系統中的應用與研究[J].電子技術與軟件工程,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為基礎的Web數據挖掘技術系統的框架設計與實現[J].電子技術與軟件工程,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]吳春瓊,胡國柱,徐靜.高職院校項目驅動模式下基于數據挖掘決策樹分類的教學效果分析[J].呂梁教育學院學報,2015,32(10):18-21.

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

[10]高媛媛.基于數據挖掘的財務舞弊識別研究：決策樹-神經網絡組合模型的構建[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的并行加權關聯規則挖掘算法[J].華僑大學學報(自然科學版),2014,35(5):523-527.

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

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

基金項目：廣西自然科學基金青年基金資助項目(2014GXNSFBA118283)

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

收稿日期：2015-11-13

中圖分類號：TP 301.6

文獻標志碼：A

doi:10.11830/ISSN.1000-5013.2016.01.0071

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