高海賓

?

基于Weka平臺的決策樹J48算法實驗研究

高海賓

(淮南聯(lián)合大學計算機系, 安徽淮南 232001)

在介紹了ID3算法和J48算法之間的關(guān)系以及J48算法的流程的基礎(chǔ)上, 著重對信息增益率的計算方法進行了說明, 然后在Weka平臺上選用鳶尾花數(shù)據(jù)集(Iris)進行分類實驗, 并對結(jié)果進行了分析, 最后隨機選取了幾種常見的決策樹算法繼續(xù)實驗, 與J48算法實驗結(jié)果進行對比分析可知, J48算法在同類決策樹算法中不僅分類準確率高而且速度快. 實驗研究結(jié)果旨在為J48算法研究工作提供一些參考.

J48算法; 決策樹; Weka; 信息增益率

決策樹方法(Decision Tree Method)最早產(chǎn)生于20世紀60年代. 決策樹方法是一種逼近離散函數(shù)的方法, 是當前數(shù)據(jù)挖掘中最常用的一種分類方法[1]. 這種方法易于理解和解釋, 它對數(shù)據(jù)的準備要求不高, 而其他的技術(shù)多數(shù)對于數(shù)據(jù)屬性有一定的約束性, 要對數(shù)據(jù)進行一般化處理后才可以應(yīng)用, 比如需要刪除空值或者多余的屬性[2]. 另外決策樹是一個白盒模型, 假設(shè)有一個觀察的模型, 那么通過所產(chǎn)生的決策樹能很方便地推導相應(yīng)的邏輯規(guī)則[3]. 由于決策樹可以對有許多屬性的數(shù)據(jù)集構(gòu)造決策樹, 所以可以很好地擴展到大型數(shù)據(jù)庫中, 同時它的大小獨立于數(shù)據(jù)庫的大小, 能夠在較短的時間內(nèi)對大型數(shù)據(jù)源做出可行而且很好的處理結(jié)果.

決策樹算法是一種典型的監(jiān)管學習, 所謂監(jiān)管學習就是給定一堆樣本, 每個樣本都有一個類別和一組屬性, 這些類別是預(yù)先確定好的, 通過學習得到一個分類規(guī)則, 根據(jù)這個規(guī)則能夠?qū)π鲁霈F(xiàn)的實例進行正確地分類. 決策樹算法在數(shù)據(jù)處理過程中, 把數(shù)據(jù)按照樹形結(jié)構(gòu)分成若干分枝的決策樹, 樹的分枝包含數(shù)據(jù)元組的類別歸屬共性, 然后從每個分枝中提取有用信息, 形成分類規(guī)則[4]. 如何構(gòu)造精確度高、規(guī)模小的決策樹是決策樹算法的核心內(nèi)容. 決策樹J48算法是近幾年最為流行的一種決策樹算法, 在機器學習和數(shù)據(jù)挖掘的分類問題中已經(jīng)得到了廣泛應(yīng)用.

1 決策樹J48算法介紹

1975年J.Ross Quinlan提出了分類預(yù)測ID3算法, 算法的核心是“信息熵”[5]. ID3算法(Iteratie Dichotomic Version 3)采用信息增益度作為屬性劃分的衡量標準, 尋找具有最大信息量的屬性字段, 建立決策樹的根節(jié)點, 再根據(jù)該屬性字段的不同取值建立樹的分支, 在每個分支集中重復建立樹的下一個節(jié)點和分支[6]. 但是ID3算法在實際應(yīng)用中也存在一定問題, 信息增益度的缺點是傾向于選擇取值較多的屬性, 但是這類屬性很可能都是一些用處不大甚至是無用的信息. 其次ID3算法只能對離散型屬性的數(shù)據(jù)集構(gòu)造決策樹.

1993年J.Ross Quinlan在ID3算法的基礎(chǔ)上進行改進后提出了C4.5算法[7]. 決策樹C4.5算法除了繼承了ID3算法所有的功能, 還可以利用信息增益率來選擇屬性, 合并具有連續(xù)屬性值、處理含有未知屬性值的訓練樣本等. 對ID3算法的改進具體包括以下幾方面:

(1) 在樹的構(gòu)造過程中進行剪枝; (2) 能夠很好地處理不完整的數(shù)據(jù); (3) 對于連續(xù)屬性值能夠很好地進行離散化處理; (4) 最佳分裂屬性的選擇用信息增益率高低來確定, 解決了用信息增益度確定屬性時傾向選擇取值多的屬性的缺陷[8].

引入信息增益率是C4.5算法是對ID3算法的最大改進之處. 利用信息增益率來選擇屬性, 完成對連續(xù)屬性的離散化處理, 將知識表示為決策樹的形式, 并最終生成規(guī)則. 信息增益率的計算過程如下:

得出信息增益率以后, 選擇信息增益率最高的屬性作為根節(jié)點, 然后向下遞歸建樹最終形成產(chǎn)生式規(guī)則. 在Weaka平臺中把C4.5算法的實現(xiàn)命名為J48算法, 以下均稱為J48算法. J48算法基本工作流程如圖1所示[9].

2 決策樹J48算法在Weka中的實驗與分析

2.1 Weak平臺介紹

Weka(Waikato Environment for Knowledge Analysis)全名是懷卡托智能分析環(huán)境, 它是一款免費的、非商業(yè)化、基于Java環(huán)境下開源的機器學習和數(shù)據(jù)挖掘軟件. Weka這個名詞來源于新西蘭的一種鳥的名字. Weka是由新西蘭的懷卡托大學開發(fā)的, 經(jīng)歷近二十多年的發(fā)展, 功能已經(jīng)十分強大, 代表了當今數(shù)據(jù)挖掘和機器學習領(lǐng)域的最高水平. 作為一個公開的數(shù)據(jù)挖掘工作平臺, 匯集了當今最前沿的機器學習算法和數(shù)據(jù)預(yù)處理工具, 包括對數(shù)據(jù)進行預(yù)處理、分類、聚類、回歸、關(guān)聯(lián)規(guī)則等, 它為數(shù)據(jù)挖掘?qū)嶒灥恼麄€過程, 包括準備要輸入的數(shù)據(jù), 用統(tǒng)計方法評估學習方案, 以及可視化輸入數(shù)據(jù)和學習結(jié)果, 提供了廣泛的支持[10].

2.2 鳶尾花數(shù)據(jù)集

鳶尾花數(shù)據(jù)集(Iris)是一個非常著名的用于數(shù)據(jù)挖掘測試的數(shù)據(jù)集, 經(jīng)常作為比較數(shù)據(jù)挖掘算法的基準. 鳶尾花數(shù)據(jù)集包括三個類別: Iris Virginica(維基亞鳶尾), Iris Setosa(山鳶尾)和Iris Versicolour(變色鳶尾), 每個類別各有50個實例. 數(shù)據(jù)集定義了5個屬性: sepal width(花萼寬)、sepal length(花萼長)、petal width(花瓣寬)、petal length(花瓣長)、class(類別). 最后一個屬性作為類別屬性, 其余屬性都是數(shù)值. 表1摘錄了鳶尾花數(shù)據(jù)集(Iris)片段.

2.3決策樹J48算法在Weka平臺上的實驗

利用Weka對鳶尾花數(shù)據(jù)集進行分類處理, 具體實驗步驟如下:

(1) 在預(yù)處理Preproccess標簽頁點擊 open file, 選擇Weka安裝目錄下data 文件夾中的iris.arff數(shù)據(jù)集文件.

(2) 選擇Classify標簽頁然后點擊Classifiers→tree→J48. 打開J48參數(shù)設(shè)置面板主要參數(shù)設(shè)置如下, 使用未剪枝confidenceFactor參數(shù)設(shè)置用于修剪的置信因子(小于該值將導致修剪), 設(shè)置值為0.25; numFolds參數(shù)設(shè)置用于reduced-error(減少-誤差)修剪的數(shù)據(jù)量, 設(shè)置值為3; seed參數(shù)設(shè)置是減少誤差修剪時, 用于隨機化數(shù)據(jù)的種子, 設(shè)置值為1; reducedErrorPruning參數(shù)設(shè)置是否使用減少-誤差修剪, 而不是C4.5修剪, 設(shè)置值為False, 使用C4.5修剪; minNumObj參數(shù)設(shè)置每個葉的最小實例數(shù)量,設(shè)置值為2;

subtreeRaising參數(shù)設(shè)置修剪樹的時候是否考慮子樹上升操作, 設(shè)置值為True; unpruned參數(shù)設(shè)置修剪是否需要, 設(shè)置值為False; useLaplace參數(shù)設(shè)置是否葉節(jié)點基于拉普拉斯平滑, 設(shè)置值為False.

(3)選擇cross-validation Folds的值為10, 可以保證生成的模型的準確性, 不至于出現(xiàn)過擬合(overfitting)的現(xiàn)象.

(4)單擊Start按鈕, 啟動實驗. 實驗結(jié)果如圖2所示.

根據(jù)圖2可以看出, Correctly Classified Instances反映訓練好的模型的準確度, 有144個實例被正確分類, 準確率高達96%, 6個實例被錯誤分類, 錯誤率4%. Kappa Statistic = 0.94, 用于評判分類器的分類結(jié)果和隨機分類的差異度.= 1表示分類結(jié)果完全與隨機分類結(jié)果相異(理想狀況),= 0表示分類結(jié)果與隨機分類相同(說明分類器沒有效果),= ?1表示分類結(jié)果比隨機分類還要差. 所以越接近于1越好, 0.94反映實驗分類結(jié)果很好. 平均絕對差Mean absolute error = 0.035, 用于評判預(yù)測值和實際值之間的差異度. 均方根誤差Root mean squared error = 0.1586, 預(yù)測標簽與真實標簽偏差的平方和與測試樣本數(shù)比值的平方根. 這兩個值很好地反映預(yù)測的精密度, 值很小說明實驗預(yù)測精密度高.

在resultlist中選擇Visualize tree可以看到可視化的決策樹, 如圖3所示. 樹的根節(jié)點選擇了petalwidth屬性, 說明petalwidth的信息增益率最大, 以它做分裂結(jié)點能得到更純的子結(jié)點.

最后, 分裂結(jié)點選擇的屬性是petallength. 決策樹建立的規(guī)則的是根據(jù)花瓣的寬度和長度不同判斷出不同種類的鳶尾花. 例如: 當petalwidth小于等于0.6時, 即為iris-setosa; 當petalwidth大于1.7, 即為Iris-virginica; 當petalwidth小于等于1.7大于0.6而petallength小于等于4.9時, 為iris-versicolor; 當petalwidth小于等于1.5大于0.6而petallength大于4.9時, 為iris-virginica; 當petalwidth小于等于1.7大于1.5而petallength大于4.9時, 為iris-versicolor.

2.4幾種決策樹算法實驗比較

常用的分類算法度量標準有TP、FP、Precision和Recall等. TP為識別率, 表示對某一分類的實例有多少概率把它識別出來. TP是一個很重要的標準, 例如在醫(yī)療系統(tǒng)中提高識別率很重要, 如果病人有病, 卻沒有識別出來, 后果就會很嚴重. FP為誤判率, 表示對其他分類的實例, 有多少概率把實例識別成本分類. Precision為精準度, 表示對某一個類別的分類中正確的實例數(shù)占總數(shù)的比率. Recall為召回率, 又稱查全率, 表示識別正確的實例數(shù)占該類別的實例的總數(shù).

為了更好地驗證J48決策樹算法的分類效果, 再隨機選取BTree、LADTree、NBTree、RandomForest、REPTree等幾種決策樹算法分別在Iris數(shù)據(jù)集進行分類實驗. 由于篇幅有限, 相關(guān)參數(shù)設(shè)置和實驗過程不一一介紹, 這里直接給出運行結(jié)果, 對實驗結(jié)果匯總處理, 見表2.

通過幾種算法在Iris數(shù)據(jù)集的實驗結(jié)果可以看出, J48算法在進行分類過程中, 準確率要高于其他幾種決策樹算法, 運行速度方面也是最快的. REPTree 算法用時約為0.02秒, 速度快, 但是準確率0.94劣于其他算法. LADTree算法的時間0.03秒, 但是準確率卻是最低的. 隨機森林RandForest算法準確率較高, 但是運行速度0.08秒, 要遜于J48算法. J48算法的運行時間約等于0, 用時最少, 識別率也是最高的.

綜上可以認為J48算法要明顯優(yōu)于其他幾種決策樹算法.

3 結(jié)束語

通過實驗結(jié)果可以看出J48算法對數(shù)據(jù)集分類運行速度快, 產(chǎn)生的分類規(guī)則也易于理解, 準確率在同類決策樹算法中也是較高的, 因而在醫(yī)學、制造和生產(chǎn)、天文學、金融分析、分子生物學和遙感影像分類、機器學習和知識發(fā)現(xiàn)等領(lǐng)域都可以廣泛應(yīng)用. 但是該算法自身也存在一定的不足, 比如在構(gòu)造樹的過程中, 需要對數(shù)據(jù)集進行反復地順序掃描和排序, 這樣就會耗費大量的內(nèi)存資源, 導致算法運行低效. 另外如果數(shù)據(jù)集增大了一點, 那么學習時間就會有一個迅速地增長, 這些問題需要在今后的數(shù)據(jù)挖掘工作中進行深入地研究. J48決策樹算法所涉及的知識實在太廣泛, 筆者僅從一個Iris數(shù)據(jù)集實驗角度進行了討論和分析, 得出的結(jié)論和觀點難免有些偏頗, 僅供廣大決策樹算法研究人員參考.

[1] 王小妮. 數(shù)據(jù)挖掘技術(shù)[M]. 北京: 北京航空航天大學出版社, 2014: 9~10

[2] 黃 震. 數(shù)據(jù)挖掘在電信客戶流失預(yù)警中的應(yīng)用[D]. 北京: 北京郵電大學碩士學位論文, 2008: 12~14

[3] 宋 鑒. 基于C 4.5算法的BBS檢索排名策略[D]. 北京: 北京郵電大學碩士學位論文, 2009: 28~29

[4] 張建良. 數(shù)據(jù)挖掘在煉鐵系統(tǒng)中的應(yīng)用現(xiàn)狀及展望(上) [J]. 冶金自動化, 2012, 36(5): 6~9

[5] 王志春. 一種改進C4.5算法[J]. 電子技術(shù)與軟件工程, 2016. 37 (09): 182~183

[6] 張同偉. 基于多分類器組合的垃圾網(wǎng)頁的檢測[D]. 廣州: 華南理工大學碩士學位論文, 2010: 15~16

[7] 晁 進. 基于數(shù)據(jù)挖掘技術(shù)的電網(wǎng)智能報警系統(tǒng)的研究[D]. 北京: 華北電力大學碩士學位論文, 2011: 7~8

[8] 何廣東. 高校就業(yè)工作中決策樹技術(shù)應(yīng)用初探[J]. 成功(教育).2013, 21(1): 56~58

[9] 梁 偉. VoIP呼叫分揀關(guān)鍵技術(shù)研究與設(shè)計[D]. 鄭州: 解放軍信息工程大學碩士學位論文, 2012: 17~19

[10] 段軼軒. 探索B2C賬號在線評論特征[D]. 重慶: 重慶工商大學碩士學位論文, 2014: 6~7

Experimental Study on J48 Algorithm of Decision Tree Based on Weka

GAO Haibin

(Department of Computer Science, Huainan Union University, Huainan 232001, China)

Firstly, we introduce what J48 algorithm and algorithm flow, focusing on the information rate of gain calculation methods were introduced. Then we use the Iris data set on the Weka platform to classify experiments and analyze the results. Finally, several common decision tree algorithms are randomly selected and compared with the experimental results of J48 algorithm, and some conclusions are drawn. The experimental results are intended to provide some reference for J48 algorithm research.

J48 algorithm, decision tree, Weka, information gain ratio

TP312

A

1672-5298(2017)01-0021-05

2016-12-20

安徽省高等學校省級自然科學研究項目“基于Bandit算法的推薦系統(tǒng)優(yōu)化研究” (KJ2017A585)

高海賓(1979? ), 男, 安徽淮北人, 碩士, 淮南聯(lián)合大學計算機系講師. 主要研究方向: 軟件技術(shù)