決策樹在汽車評測中的應用研究

周凌云

( 中南民族大學 計算機科學學院，武漢430074)

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

通過分析研究，本文提出應用決策樹的經典算法——ID3算法進行汽車評測.ID3算法是以信息論為基礎，以信息熵和信息增益度為衡量標準，從而實現對數據的歸納分類，以此達到預測的目的[4].本文根據汽車各項性能指標，將ID3算法應用于汽車評測中,為深入開發(fā)汽車購買決策支持系統提供研究基礎.

1 ID3決策樹算法原理

ID3算法是一種由訓練樣例構造決策樹的遞歸算法.該算法首先選擇一個屬性作為決策樹的根結點，并對該屬性的每一個值產生一個分支.然后，劃分該結點上的數據集，并移到子女結點，產生一個局部樹.對其他屬性重復該過程[5-9].ID3算法的關鍵在于：1)生成決策樹時，對于決策樹的每一個結點選擇屬性的方法；2)確定停止樹的生長的條件.

對于第一個關鍵問題，ID3 算法使用信息增益作為訓練樣本集合的劃分度量標準.計算信息增益的具體方法可以分為以下3步.

(1) 計算目標屬性的熵.目標屬性也就是樣例的分類，它不必被選作決策樹路徑上的結點，但它的值要作為決策樹葉子結點的值.目標屬性的熵根據以下公式計算:

(1)

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

(2) 計算候選屬性的熵.計算候選屬性的熵是為了選擇當前決策屬性，也就是選作為當前決策樹的一個結點的屬性.對于每一個候選屬性A的熵可以根據以下公式計算:

(2)

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

(3) 計算候選屬性的信息增益.信息增益反映了候選屬性分類訓練數據的能力.一個候選屬性的信息增益越大，那么它對訓練樣例的分類能力越強.信息增益的計算公式為：

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

(3)

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

ID3算法的第二個關鍵問題是確定停止樹生長的條件.當決策樹的某個分支下的樣例都屬于一分類時，這一個分支上樣例的劃分就結束了.另外，當所有的候選屬性已經被這條路徑包括時決策樹的生長也結束了，因為任何候選屬性在決策樹的任意路徑上最多只能出現一次.

2 建立汽車評測模型

本文根據汽車的特定屬性來進行評測，預測它的購買指數.該應用的數據來源于UCI機器學習數據庫中的標準數據集Car Evaluation Database，該數據集無缺失數據，并且各屬性取值均為離散值，各屬性取值個數分布均勻，都是3或4個，樣本分類個數為4類.具備這樣特征的數據集特別適合采用ID3決策樹算法建立預測模型.

2.1 訓練樣本描述

評測汽車的屬性也就是對分類結果有影響作用的屬性有6 個，分別是購買價格(buying)、保養(yǎng)費(maint )、門的個數(doors)、座位數(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個屬性對分類結果有影響作用，也就是生成汽車評測決策樹的候選屬性.汽車的購買指數通過汽車的目標屬性也就是決策屬性來描述.目標屬性class描述如下.

class = { unacc,acc,good,vgood }

評測汽車的結果分為4類：不可接受(unacc)，可接受(acc)，比較好(good)，很好(vgood)，也就是訓練樣本集被分為4 個類別.表1給出了一個關于汽車評測的部分訓練樣本.

2.2 詳細算法

建立汽車評測模型的決策樹算法流程[10]描述如下.

算法：Generate_CarEvaluationTree(samples,attribute_list)

輸入：samples為訓練樣本；attribute_list為候選屬性的集合.

輸出：一棵汽車評測決策樹.

偽代碼：

Generate_CarEvaluationTree(samples,attribute_list)

{

N = Create_Node(); //創(chuàng)建汽車評測決策樹的一個結點

if( samples 都在同一個類C )

{ return N 作為葉結點，以類C 標記; }

if( attribut_list 為空 )

{ return N 作為葉結點，標記為 samples 中最普通的類; }

N = Choose_best_attribute( attribute_list );

//選擇當前最高信息增益屬性作為當前汽車評測決策樹的結點

表1 汽車評測的部分訓練樣本

for best_attribute 的每一個取值ai

{

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

Divide(); //在每一個分支上劃分當前汽車訓練樣本集

if( 如果新分支下的汽車訓練樣本集為空 )

Create_LeafNode();

//建立葉子結點，以當前樣本中類別個數最多的類別標記；該分支生長結束

else

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

}

}

2.3 汽車評測模型測試

建立好汽車評測決策樹后就可以用該模型對未分類的汽車樣例進行分類預測了.為了測試該模型分類預測的準確率，本文將已知樣例分為兩個部分，一部分作為訓練樣例，用來生成汽車評測決策樹模型.另一部分作為測試樣例，用來測試生成的模型對樣例分類預測的準確率.在測試的過程中，記錄分類正確的樣例的個數，與預測樣例的個數相除計算出分類預測的準備率.考慮到保證實驗結果的準確性，該實驗在相同的軟硬件平臺下測試多次，取其平均值作為最后結果.

3 實驗結果

實驗采用的數據集為UCI機器學習數據庫中的標準數據集Car Evaluation Database.該數據集中一共有1728個實例.本實驗方案從中選取10%、20%、40%、50%、60%，以及70%的樣例分別作為訓練數據集，而對應的剩余部分樣例作為測試數據集，在相同的軟、硬件平臺下進行多次實驗，得出的實驗數據如表2所示.

表2 實驗結果數據

從表2的實驗結果可以看出，當訓練樣例在20%以上時，預測的準備率較好，均能達到80%以上，當訓練樣例所占比例更大時，分類預測的準備率相對更高.

4 結束語

利用機器學習方法處理分類預測問題是近年來分類領域一個新興的研究熱點.決策樹是一種機器學習常用的分類方法.本文通過系統闡述決策樹方法的原理和適合范圍,并分析了汽車評測數據適合決策樹ID3算法,所以利用ID3決策樹方法來建立汽車評測模型，并給出詳細的步驟.最后在Car Evaluation Database數據集上對該模型進行實驗測試，可以看出此方法是比較有效的，并能證實該模型獲得較好的分類預測準確率.

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

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

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

[4]黃愛輝，陳湘濤.決策樹ID3算法的改進[J].計算機工程與科學，2009，31(6)：109-111.

[5]徐 鵬,林 森.基于C4.5決策樹的流量分類方法[J].軟件學報,2009,20(10):2692-2704.

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

[7]丁智斌,袁 方，董賀偉.數據挖掘在高校學生學習成績分析中的應用[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]安立奎，錢偉懿，韓麗艷.集群系統中基于MPI的關聯規(guī)則快速挖掘算法[J].三峽大學學報：自然科學版，2010(1)：95-97.

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