決策樹算法在Weka平臺(tái)上的數(shù)據(jù)挖掘應(yīng)用

程斐斐，王子牛，侯立鐸

決策樹算法在Weka平臺(tái)上的數(shù)據(jù)挖掘應(yīng)用

程斐斐，王子牛，侯立鐸

決策樹算法可以對(duì)數(shù)據(jù)集進(jìn)行有效的訓(xùn)練學(xué)習(xí)和快速準(zhǔn)確的分類，其中ID3算法是最早提出的一種決策樹算法，但是，此算法只適用于處理取值較多屬性的數(shù)據(jù)，不能處理連續(xù)數(shù)據(jù)，對(duì)噪聲也比較敏感。C4.5算法是對(duì)ID3算法的優(yōu)化，不僅可以對(duì)連續(xù)值屬性進(jìn)行處理，而且增加了對(duì)空值數(shù)據(jù)的處理功能。在研究和分析主流決策樹算法基礎(chǔ)上，針對(duì)二手汽車數(shù)據(jù)庫(kù)在Weka數(shù)據(jù)挖掘平臺(tái)進(jìn)行了C4.5算法的設(shè)計(jì)與實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明該算法對(duì)預(yù)測(cè)數(shù)據(jù)集中的相應(yīng)屬性能進(jìn)行較為準(zhǔn)確的預(yù)測(cè)。

決策樹算法；ID3；C4.5；Weka

0 引言

隨著計(jì)算機(jī)和信息時(shí)代的發(fā)展，人們收集、存儲(chǔ)和訪問(wèn)的數(shù)據(jù)急劇增加，如何從大量的數(shù)據(jù)中提取并發(fā)現(xiàn)有用信息或知識(shí)，引起了學(xué)術(shù)界的廣泛關(guān)注。數(shù)據(jù)挖掘因此應(yīng)運(yùn)而生。數(shù)據(jù)挖掘的方法有很多，包括分類、預(yù)測(cè)、聚類、關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘等。其中分類問(wèn)題是被廣泛研究的課題之一，它是用來(lái)分析數(shù)據(jù)庫(kù)中的一組對(duì)象，找出共同的屬性，構(gòu)造分類模型，然后利用這個(gè)模型對(duì)其它的數(shù)據(jù)對(duì)象進(jìn)行分類。廣泛使用的分類方法有決策樹、貝葉斯分類、遺傳算法和神經(jīng)網(wǎng)絡(luò)等。其中，決策樹是一種常用于預(yù)測(cè)模型的算法，它將大量數(shù)據(jù)有目的的進(jìn)行分類,從中找到一些具有商業(yè)價(jià)值的、潛在的信息。

1 決策樹介紹

1.1 決策樹技術(shù)

決策樹是用于分類與預(yù)測(cè)的主要技術(shù)，它是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，通過(guò)一組無(wú)次序、無(wú)規(guī)則的事例中推理出決策樹表現(xiàn)形式的分類規(guī)則。這種算法采用“自頂向下、分而治之”的方法，通常用來(lái)形成分類器和預(yù)測(cè)模型，可以對(duì)未知數(shù)據(jù)進(jìn)行分類、預(yù)測(cè)和數(shù)據(jù)預(yù)處理等。

決策樹是一個(gè)類似于流程圖的樹結(jié)構(gòu)，每個(gè)分枝代表一個(gè)測(cè)試輸出，樹葉代表類或類分布，樹的最頂層結(jié)點(diǎn)是根結(jié)點(diǎn)。在決策樹的基本結(jié)構(gòu)圖中，中間結(jié)點(diǎn)常用矩形表示，葉子結(jié)點(diǎn)代表目標(biāo)類別屬性的值，用橢圓形表示。是一棵簡(jiǎn)單的決策樹，如圖1所示：

圖1 決策樹結(jié)構(gòu)圖

1.2 決策樹的主要步驟

決策樹構(gòu)造可以分兩步進(jìn)行:

第一步，建樹階段：由訓(xùn)練數(shù)據(jù)集生成決策樹的過(guò)程。按遞歸算法構(gòu)造決策樹，直到每個(gè)葉子結(jié)點(diǎn)屬于同一類為止，其本質(zhì)是貪心算法。

第二步，剪枝階段：它是用數(shù)據(jù)對(duì)生成的決策樹進(jìn)行檢驗(yàn)，將不正確的問(wèn)題進(jìn)行調(diào)整，對(duì)決策樹進(jìn)行剪枝和增加結(jié)點(diǎn)，直到建立一個(gè)正確的決策樹。剪枝的主要目的是去掉噪聲和異常數(shù)據(jù)，使決策樹具有更泛化能力。

利用決策樹對(duì)數(shù)據(jù)進(jìn)行分類和預(yù)測(cè)遵循兩大步驟，如圖2所示：

圖2 決策樹工作原理流程圖

2 常見的決策樹算法

2.1 ID3算法

ID3算法是一種基于信息熵的決策樹學(xué)習(xí)算法，根據(jù)Shannon信息論把信息熵作為選擇測(cè)試屬性的標(biāo)準(zhǔn)，對(duì)訓(xùn)練實(shí)例集進(jìn)行分類，并構(gòu)造決策樹來(lái)預(yù)測(cè)如何由測(cè)試屬性對(duì)整個(gè)實(shí)例空間進(jìn)行劃分。

定義2.1設(shè)U是論域,X1,X2…Xn是U的一個(gè)劃分，其上有概率分布，則稱:為信息源X的信息熵，其中對(duì)數(shù)取以2為底。

2.2 C4.5算法

C4.5算法在選擇測(cè)試屬性上采用基于信息增益率的方法，信息增益率等于信息增益對(duì)分割信息量的比值。設(shè)樣本集S按離散屬性A的n個(gè)不同的取值，劃分為S1,S2…Sn。共n個(gè)子集，則用A對(duì)S進(jìn)行劃分的信息增益率為：

算法在ID3的基礎(chǔ)上增加了新的功能，不但可以對(duì)連續(xù)型屬性處理，而且允許出現(xiàn)屬性空缺的樣本。

3 決策樹分類實(shí)例

本文使用Weka數(shù)據(jù)挖掘工具對(duì)1700多條二手汽車信息數(shù)據(jù)進(jìn)行挖掘分析，Weka存儲(chǔ)數(shù)據(jù)的格式是ARFF文件。首先先進(jìn)行數(shù)據(jù)抽取和處理，把有用的信息抽取到數(shù)據(jù)庫(kù)里，再進(jìn)一步處理，使Weka能夠處理這些數(shù)據(jù)。生成的部分庫(kù)信息，如圖3所示：

圖3 汽車信息表

car.arff文件的部分文件內(nèi)容如下：

在Weka中導(dǎo)入文件后，選取J48即C4.5決策樹算法，設(shè)定置信度閾C為0.25，分枝數(shù)M為15，并設(shè)定樣本的Cross-validation的交叉驗(yàn)證組別為10，有效提高分類器中的樣本的精確度，進(jìn)行數(shù)據(jù)挖掘。結(jié)果如圖4所示：

圖4 分類結(jié)果

由于可視化的模型不夠清晰，故手繪一個(gè)模型圖，如圖5所示：

圖5 決策樹模型

用J48算法交叉結(jié)果之一為Correctly Classified Instances143883.2176%，說(shuō)明這個(gè)模型的準(zhǔn)確度在83%左右。而選取分枝樹M為默認(rèn)值2時(shí)，準(zhǔn)確度達(dá)到96%，但是其可視化的決策樹可視化圖太過(guò)于密集，通過(guò)對(duì)復(fù)雜程度和準(zhǔn)確度的分析，在M為15時(shí)最合適。

對(duì)已有的數(shù)據(jù)集建立訓(xùn)練模型后，可以對(duì)一些待預(yù)測(cè)的數(shù)據(jù)集中相應(yīng)屬性值進(jìn)行預(yù)測(cè)，待預(yù)測(cè)數(shù)據(jù)集和訓(xùn)練數(shù)據(jù)集各個(gè)屬性的設(shè)置需一致。對(duì)car-new.arff數(shù)據(jù)集進(jìn)行分類和預(yù)測(cè)，文件部分如下：

通過(guò)已有的分類器對(duì)此文件的最后一個(gè)屬性值進(jìn)行預(yù)測(cè)。經(jīng)過(guò)在Weka里分類預(yù)測(cè)后生成新文件car-predicted.arff，變化的部分如下：

有兩個(gè)新的屬性被添加到文件中，其中Predictedclass的值就是對(duì)原class屬性值的預(yù)測(cè)。

4 總結(jié)

決策樹是一種常用于預(yù)測(cè)模型的算法，Weka工具可以高效的進(jìn)行數(shù)據(jù)挖掘，并提供了分類、聚類、關(guān)聯(lián)規(guī)則等多種方法，為數(shù)據(jù)挖掘提供了一個(gè)方便快捷的平臺(tái)。本文針對(duì)二手車數(shù)據(jù)庫(kù)，通過(guò)使用Weka數(shù)據(jù)挖掘工具及決策樹分類算法C4.5，對(duì)汽車信息庫(kù)中各類標(biāo)號(hào)屬性值進(jìn)行分類和預(yù)測(cè)。結(jié)果表明C4.5算法可以快速準(zhǔn)確的對(duì)屬性明確的數(shù)據(jù)進(jìn)行分類和預(yù)測(cè)。如何把決策樹其它算法更好的應(yīng)用于Weka平臺(tái)是筆者需要進(jìn)一步研究的工作。

[1]Jiawei Han,Michwline Kamber,Jian Pei.Data Mining Conceptsand Techniques[M].3nded.Beijing:China Machine Press,2012.

[2]IanH.Witten,Eibe Frank.Data Mining Practical Machine Learning Tools and Techniques Second Edition[M].3nd ed.Beijing:China Machine Press,2006.

[3]王繼魁,呂凱,李虹.基于決策樹分類的Weka平臺(tái)上數(shù)據(jù)挖掘應(yīng)用[J].白城師范學(xué)院學(xué)報(bào),2013,27(5):36-40.

[4]戴南.基于決策樹的分類方法研究[D].南京:南京師范大學(xué),2003.

[5]趙蕊.基于WEKA平臺(tái)的決策樹算法設(shè)計(jì)與實(shí)現(xiàn)[D].武漢:中南大學(xué),2007.

[6]王黎明.決策樹學(xué)習(xí)及其剪枝算法研究[D].武漢:武漢理工大學(xué),2007.

[7]馮少榮.決策樹算法的研究與改進(jìn)[J].廈門大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,46(4):496-500.

[8]鄒媛.基于決策樹的數(shù)據(jù)挖掘算法的應(yīng)用與研究[J].科學(xué)技術(shù)與工程,2010,10(18):4510-4515.

[9]李如平.數(shù)據(jù)挖掘中決策樹分類算法的研究[J].東華理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,33(2):192-196.

[10]但小容,陳軒恕,劉飛,柳德偉.數(shù)據(jù)挖掘中決策樹分類算法的研究與改進(jìn)[J].軟件導(dǎo)刊,2009,8(2):41-43.

[11]胡江洪.基于決策樹的分類算法研究[D].武漢：武漢理工大學(xué),2006.

[12]楊學(xué)兵,張俊.決策樹算法及其核心技術(shù)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(1):43-45.

[13]唐華松,姚耀文.數(shù)據(jù)挖掘中決策樹算法的探討[J]計(jì)算機(jī)應(yīng)用研究,2001,18(8):19-22.

Data Mining Application in Weka Platform Based on Decision Tree Classification

Cheng Feifei,Wang Ziniu,Hou Liduo
(College of Big Data and Information Engineering,Guizhou University,Guiyang 550025,China)

Decision tree algorithm can do effective training and learning as well as fast accurate classification to dataset.ID3 algorithm is the earliest decision tree algorithm.But this algorithm can only be applied to handle more attribute data values,and continuous data can’t be solved efficiently.It is also sensitive to noise.C4.5 algorithm is the optimization of ID3 algorithm.It can not only solve the continuous attribute values,but also increase the function of empty data.This paper mainly uses Weka data mining tools to do the design and realization of C4.5 algorithm,which is based on an example of Second-hand car database.This experiment indicates that those concentrated values can be predicted accurately by this algorithm.

Decision Tree Algorithm;ID3;C4.5;Weka

TP302

A

1007-757X(2015)06-0063-03

2014.12.16）

程斐斐（1988-），女，貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，碩士研究生，研究方向?yàn)橛脩羯暇W(wǎng)行為的數(shù)據(jù)挖掘，貴陽(yáng)，550025

王子牛（1961-），男，貴州大學(xué)網(wǎng)絡(luò)與信息化管理中心，副教授，本科，主要研究方向?yàn)閿?shù)據(jù)挖掘，貴陽(yáng)，550025

侯立鐸（1988-），男，貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘，貴陽(yáng)，550025