周凌云

( 中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

決策樹(shù)是1986年由Quinlan提出的，它是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，它從一個(gè)無(wú)次序、無(wú)規(guī)則的實(shí)例集合中歸納出一組采用屬性結(jié)構(gòu)表示的分類(lèi)規(guī)則.決策樹(shù)學(xué)習(xí)算法是最流行的歸納推理算法之一，已經(jīng)被成功地應(yīng)用到從學(xué)習(xí)醫(yī)療診斷到學(xué)習(xí)評(píng)估貸款申請(qǐng)的信用風(fēng)險(xiǎn)等廣闊領(lǐng)域[1,2].隨著中國(guó)經(jīng)濟(jì)的發(fā)展，購(gòu)車(chē)人群增加，對(duì)汽車(chē)進(jìn)行評(píng)測(cè)，給消費(fèi)者在購(gòu)車(chē)決策過(guò)程中提供參考顯得十分必要[3].汽車(chē)評(píng)測(cè)是指根據(jù)汽車(chē)的性能、購(gòu)買(mǎi)價(jià)格、保養(yǎng)費(fèi)、安全性能、操控性、行李箱大小等指標(biāo)來(lái)評(píng)價(jià)和預(yù)測(cè)它的購(gòu)買(mǎi)指數(shù)，從而給消費(fèi)者提供購(gòu)車(chē)參考.

通過(guò)分析研究，本文提出應(yīng)用決策樹(shù)的經(jīng)典算法——ID3算法進(jìn)行汽車(chē)評(píng)測(cè).ID3算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的歸納分類(lèi)，以此達(dá)到預(yù)測(cè)的目的[4].本文根據(jù)汽車(chē)各項(xiàng)性能指標(biāo)，將ID3算法應(yīng)用于汽車(chē)評(píng)測(cè)中,為深入開(kāi)發(fā)汽車(chē)購(gòu)買(mǎi)決策支持系統(tǒng)提供研究基礎(chǔ).

1 ID3決策樹(shù)算法原理

ID3算法是一種由訓(xùn)練樣例構(gòu)造決策樹(shù)的遞歸算法.該算法首先選擇一個(gè)屬性作為決策樹(shù)的根結(jié)點(diǎn)，并對(duì)該屬性的每一個(gè)值產(chǎn)生一個(gè)分支.然后，劃分該結(jié)點(diǎn)上的數(shù)據(jù)集，并移到子女結(jié)點(diǎn)，產(chǎn)生一個(gè)局部樹(shù).對(duì)其他屬性重復(fù)該過(guò)程[5-9].ID3算法的關(guān)鍵在于：1)生成決策樹(shù)時(shí)，對(duì)于決策樹(shù)的每一個(gè)結(jié)點(diǎn)選擇屬性的方法；2)確定停止樹(shù)的生長(zhǎng)的條件.

對(duì)于第一個(gè)關(guān)鍵問(wèn)題，ID3 算法使用信息增益作為訓(xùn)練樣本集合的劃分度量標(biāo)準(zhǔn).計(jì)算信息增益的具體方法可以分為以下3步.

(1) 計(jì)算目標(biāo)屬性的熵.目標(biāo)屬性也就是樣例的分類(lèi)，它不必被選作決策樹(shù)路徑上的結(jié)點(diǎn)，但它的值要作為決策樹(shù)葉子結(jié)點(diǎn)的值.目標(biāo)屬性的熵根據(jù)以下公式計(jì)算:

(1)

其中，S是訓(xùn)練樣例的集合，pi是S中屬于類(lèi)別i的比例，Σ 是對(duì)c求和.Entropy(S)反映了訓(xùn)練樣例的純度，當(dāng)它的值為0時(shí)訓(xùn)練樣例集合最純，也就是此時(shí)訓(xùn)練樣例集合中的所有樣例屬于同一分類(lèi).

(2) 計(jì)算候選屬性的熵.計(jì)算候選屬性的熵是為了選擇當(dāng)前決策屬性，也就是選作為當(dāng)前決策樹(shù)的一個(gè)結(jié)點(diǎn)的屬性.對(duì)于每一個(gè)候選屬性A的熵可以根據(jù)以下公式計(jì)算:

(2)

其中，Values(A)是屬性A所有可能值得集合，Sv是訓(xùn)練樣例集合中候選屬性A的值為v的子集,|Sv| 是Sv中樣例個(gè)數(shù)，|S|是S中樣例的個(gè)數(shù) .Entropy(Sv)是訓(xùn)練樣例集合中候選屬性A的值為v時(shí)訓(xùn)練樣例集合的熵，它可以根據(jù)公式(1)求得.

(3) 計(jì)算候選屬性的信息增益.信息增益反映了候選屬性分類(lèi)訓(xùn)練數(shù)據(jù)的能力.一個(gè)候選屬性的信息增益越大，那么它對(duì)訓(xùn)練樣例的分類(lèi)能力越強(qiáng).信息增益的計(jì)算公式為：

Gain(S,A)= Entropy(S)-Entropy(S,A)，

(3)

算法的具體方法為：首先計(jì)算訓(xùn)練樣本集合中所有屬性的信息增益，選擇取值最大的屬性作為判斷屬性劃分當(dāng)前樣本集，創(chuàng)建與判斷屬性值一一對(duì)應(yīng)的各個(gè)分枝，得到代表各分支的訓(xùn)練樣本子集，然后遞歸調(diào)用同樣的方法繼續(xù)劃分.

ID3算法的第二個(gè)關(guān)鍵問(wèn)題是確定停止樹(shù)生長(zhǎng)的條件.當(dāng)決策樹(shù)的某個(gè)分支下的樣例都屬于一分類(lèi)時(shí)，這一個(gè)分支上樣例的劃分就結(jié)束了.另外，當(dāng)所有的候選屬性已經(jīng)被這條路徑包括時(shí)決策樹(shù)的生長(zhǎng)也結(jié)束了，因?yàn)槿魏魏蜻x屬性在決策樹(shù)的任意路徑上最多只能出現(xiàn)一次.

2 建立汽車(chē)評(píng)測(cè)模型

本文根據(jù)汽車(chē)的特定屬性來(lái)進(jìn)行評(píng)測(cè)，預(yù)測(cè)它的購(gòu)買(mǎi)指數(shù).該應(yīng)用的數(shù)據(jù)來(lái)源于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的標(biāo)準(zhǔn)數(shù)據(jù)集Car Evaluation Database，該數(shù)據(jù)集無(wú)缺失數(shù)據(jù)，并且各屬性取值均為離散值，各屬性取值個(gè)數(shù)分布均勻，都是3或4個(gè)，樣本分類(lèi)個(gè)數(shù)為4類(lèi).具備這樣特征的數(shù)據(jù)集特別適合采用ID3決策樹(shù)算法建立預(yù)測(cè)模型.

2.1 訓(xùn)練樣本描述

評(píng)測(cè)汽車(chē)的屬性也就是對(duì)分類(lèi)結(jié)果有影響作用的屬性有6 個(gè)，分別是購(gòu)買(mǎi)價(jià)格(buying)、保養(yǎng)費(fèi)(maint )、門(mén)的個(gè)數(shù)(doors)、座位數(shù)(persons)、行李箱容量(lug_boot)和安全性能(safety)，它們的取值描述如下.

buying = { v-high,high,med,low }

maint = { v-high,high,med,low }

doors = { 2,3,4,5-more }

persons = { 2,4,more }

lug_boot = { small,med,big }

safety = { low,med,high }

這6個(gè)屬性對(duì)分類(lèi)結(jié)果有影響作用，也就是生成汽車(chē)評(píng)測(cè)決策樹(shù)的候選屬性.汽車(chē)的購(gòu)買(mǎi)指數(shù)通過(guò)汽車(chē)的目標(biāo)屬性也就是決策屬性來(lái)描述.目標(biāo)屬性class描述如下.

class = { unacc,acc,good,vgood }

評(píng)測(cè)汽車(chē)的結(jié)果分為4類(lèi)：不可接受(unacc)，可接受(acc)，比較好(good)，很好(vgood)，也就是訓(xùn)練樣本集被分為4 個(gè)類(lèi)別.表1給出了一個(gè)關(guān)于汽車(chē)評(píng)測(cè)的部分訓(xùn)練樣本.

2.2 詳細(xì)算法

建立汽車(chē)評(píng)測(cè)模型的決策樹(shù)算法流程[10]描述如下.

算法：Generate_CarEvaluationTree(samples,attribute_list)

輸入：samples為訓(xùn)練樣本；attribute_list為候選屬性的集合.

輸出：一棵汽車(chē)評(píng)測(cè)決策樹(shù).

偽代碼：

Generate_CarEvaluationTree(samples,attribute_list)

{

N = Create_Node(); //創(chuàng)建汽車(chē)評(píng)測(cè)決策樹(shù)的一個(gè)結(jié)點(diǎn)

if( samples 都在同一個(gè)類(lèi)C )

{ return N 作為葉結(jié)點(diǎn)，以類(lèi)C 標(biāo)記; }

if( attribut_list 為空 )

{ return N 作為葉結(jié)點(diǎn)，標(biāo)記為 samples 中最普通的類(lèi); }

N = Choose_best_attribute( attribute_list );

//選擇當(dāng)前最高信息增益屬性作為當(dāng)前汽車(chē)評(píng)測(cè)決策樹(shù)的結(jié)點(diǎn)

表1 汽車(chē)評(píng)測(cè)的部分訓(xùn)練樣本

for best_attribute 的每一個(gè)取值ai

{

Create_branch(); //每一個(gè)取值ai都建立一個(gè)新的分支；

Divide(); //在每一個(gè)分支上劃分當(dāng)前汽車(chē)訓(xùn)練樣本集

if( 如果新分支下的汽車(chē)訓(xùn)練樣本集為空 )

Create_LeafNode();

//建立葉子結(jié)點(diǎn)，以當(dāng)前樣本中類(lèi)別個(gè)數(shù)最多的類(lèi)別標(biāo)記；該分支生長(zhǎng)結(jié)束

else

Generate_CarEvaluationTree(si,attribute_list-best_attribute) //遞歸

}

}

2.3 汽車(chē)評(píng)測(cè)模型測(cè)試

建立好汽車(chē)評(píng)測(cè)決策樹(shù)后就可以用該模型對(duì)未分類(lèi)的汽車(chē)樣例進(jìn)行分類(lèi)預(yù)測(cè)了.為了測(cè)試該模型分類(lèi)預(yù)測(cè)的準(zhǔn)確率，本文將已知樣例分為兩個(gè)部分，一部分作為訓(xùn)練樣例，用來(lái)生成汽車(chē)評(píng)測(cè)決策樹(shù)模型.另一部分作為測(cè)試樣例，用來(lái)測(cè)試生成的模型對(duì)樣例分類(lèi)預(yù)測(cè)的準(zhǔn)確率.在測(cè)試的過(guò)程中，記錄分類(lèi)正確的樣例的個(gè)數(shù)，與預(yù)測(cè)樣例的個(gè)數(shù)相除計(jì)算出分類(lèi)預(yù)測(cè)的準(zhǔn)備率.考慮到保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，該實(shí)驗(yàn)在相同的軟硬件平臺(tái)下測(cè)試多次，取其平均值作為最后結(jié)果.

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用的數(shù)據(jù)集為UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的標(biāo)準(zhǔn)數(shù)據(jù)集Car Evaluation Database.該數(shù)據(jù)集中一共有1728個(gè)實(shí)例.本實(shí)驗(yàn)方案從中選取10%、20%、40%、50%、60%，以及70%的樣例分別作為訓(xùn)練數(shù)據(jù)集，而對(duì)應(yīng)的剩余部分樣例作為測(cè)試數(shù)據(jù)集，在相同的軟、硬件平臺(tái)下進(jìn)行多次實(shí)驗(yàn)，得出的實(shí)驗(yàn)數(shù)據(jù)如表2所示.

表2 實(shí)驗(yàn)結(jié)果數(shù)據(jù)

從表2的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)訓(xùn)練樣例在20%以上時(shí)，預(yù)測(cè)的準(zhǔn)備率較好，均能達(dá)到80%以上，當(dāng)訓(xùn)練樣例所占比例更大時(shí)，分類(lèi)預(yù)測(cè)的準(zhǔn)備率相對(duì)更高.

4 結(jié)束語(yǔ)

利用機(jī)器學(xué)習(xí)方法處理分類(lèi)預(yù)測(cè)問(wèn)題是近年來(lái)分類(lèi)領(lǐng)域一個(gè)新興的研究熱點(diǎn).決策樹(shù)是一種機(jī)器學(xué)習(xí)常用的分類(lèi)方法.本文通過(guò)系統(tǒng)闡述決策樹(shù)方法的原理和適合范圍,并分析了汽車(chē)評(píng)測(cè)數(shù)據(jù)適合決策樹(shù)ID3算法,所以利用ID3決策樹(shù)方法來(lái)建立汽車(chē)評(píng)測(cè)模型，并給出詳細(xì)的步驟.最后在Car Evaluation Database數(shù)據(jù)集上對(duì)該模型進(jìn)行實(shí)驗(yàn)測(cè)試，可以看出此方法是比較有效的，并能證實(shí)該模型獲得較好的分類(lèi)預(yù)測(cè)準(zhǔn)確率.

[1]Quinlan J R.Induction of decision trees[J].Machine Learning,1986(1): 81-106.

[2]米切爾.機(jī)器學(xué)習(xí)[M].曾華軍,張銀奎,譯.北京:機(jī)械工業(yè)出版社,2003：38-43.

[3]朱鋐瑛,郭乃幸.能源約束下中國(guó)新能源汽車(chē)的發(fā)展及政策建議[J].陜西科技大學(xué)學(xué)報(bào),2012,30(1):131-134.

[4]黃愛(ài)輝，陳湘濤.決策樹(shù)ID3算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，2009，31(6)：109-111.

[5]徐 鵬,林 森.基于C4.5決策樹(shù)的流量分類(lèi)方法[J].軟件學(xué)報(bào),2009,20(10):2692-2704.

[6]張 琳，陳 燕，李桃迎，等.決策樹(shù)分類(lèi)算法研究[J].計(jì)算機(jī)工程,2011,37(13):66-70.

[7]丁智斌,袁 方，董賀偉.數(shù)據(jù)挖掘在高校學(xué)生學(xué)習(xí)成績(jī)分析中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2006,27(4):590-592.

[8]Long Xiaojian,Wu Yuchun.Application of decision tree in student achievement evaluation[C]//ICCSEE.2012 International Conference on Computer Science and Electronics Engineering.Hangzhou:Missouri Western State University,2012:243- 247.

[9]安立奎，錢(qián)偉懿，韓麗艷.集群系統(tǒng)中基于MPI的關(guān)聯(lián)規(guī)則快速挖掘算法[J].三峽大學(xué)學(xué)報(bào)：自然科學(xué)版，2010(1)：95-97.

[10]王 苗，柴 瑞.一種改進(jìn)的決策樹(shù)分類(lèi)屬性選擇方法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(8):127-129.