一種改進的C4.5決策樹算法

王志春 劉麗娜

【關(guān)鍵詞】數(shù)據(jù)挖掘 決策樹 C4.5算法 信息增益率

1 引言

數(shù)據(jù)挖掘中決策樹是解決分類問題的方法之一，是一種歸納學(xué)習(xí)算法。通過一組屬性值向量和相應(yīng)的類，采用歸納學(xué)習(xí)算法構(gòu)造分類器和預(yù)測模型，能夠從一組無序和無規(guī)則的數(shù)據(jù)中生成決策樹形式的分類規(guī)則。決策樹基本不依賴于任何專業(yè)領(lǐng)域的知識，所以在分類，預(yù)測和規(guī)則提取等領(lǐng)域都被廣泛的應(yīng)用。70 年代末，J.ROSS Quinlan提出了ID3算法后，在機器學(xué)習(xí)和知識發(fā)現(xiàn)領(lǐng)域決策樹算法都得到了進一步應(yīng)用和發(fā)展。

ID3算法的核心是選擇屬性時，用信息增益（information gain）作為選擇屬性的度量標(biāo)準(zhǔn)，在測試每一個非葉子結(jié)點時，能獲得關(guān)于被測試記錄最大的類別信息。雖然ID3算法具有算法清晰，方法簡單和學(xué)習(xí)能力較強的優(yōu)點，但是ID3算法不能處理連續(xù)的屬性值，并且依賴于訓(xùn)練數(shù)據(jù)集的質(zhì)量，只對數(shù)據(jù)集較小的情況有效，訓(xùn)練數(shù)據(jù)集在逐漸變大時，決策樹可能會隨之改變。由于ID3算法存在著許多需要改進的地方，為此，J.ROSS.Quinlan于1993提出了C4.5算法，對ID3算法進行了補充和改進。C4.5 算法具有ID3 算法優(yōu)點的同時也改進和擴展了算法，使其產(chǎn)生易于理解和準(zhǔn)確率較高的分類規(guī)則。相比于ID3算法，C4.5算法用信息增益率來選擇屬性，而不是ID3算法所用的信息增益；在ID3算法的基礎(chǔ)上還增加了對連續(xù)屬性的離散化、對不完整屬性的處理能力和產(chǎn)生規(guī)則等功能。

2 C4.5算法

2.1 信息增益和信息增益率

設(shè)D是m個不同值的訓(xùn)練集有m個不同類Ci （i=1，2，…，m），設(shè)Ci， d是元組的集合，D和Ci， d中的元組個數(shù)是|D|和|Ci， d|。

2.1.1 信息增益

ID3算法中選擇具有最高信息增益的屬性作為節(jié)點N的分裂屬性，使元組分類的信息量最小。期望信息為：

用|Ci， d|/|D|估計D中任意元組屬于類Ci的概率Pi。Info（D）為D的熵。

若D的元組用屬性A可分成v個不同的類{D1， D2，…，Dn}， Dj包含D中的元組且在A上有值aj，則屬性A的信息熵為：

A屬性上該劃分的獲得的信息增益為：

2.1.2 信息增益率

信息增益率用“分裂信息”值將信息增益規(guī)范化，假設(shè)以屬性A的值為基準(zhǔn)對樣本進行分割，訓(xùn)練數(shù)據(jù)集D用分類信息SplitInfoA作為初始信息量劃分成對應(yīng)于屬性A的有v個輸出的v 個劃分信息。定義如下：

信息增益率定義為信息增益與初始信息量的比值：

C4.5算法選取信息增益比最高的屬性為集合D的測試屬性，創(chuàng)建一個節(jié)點并為每個屬性創(chuàng)建分支劃分樣本。

2.2 C4.5算法實現(xiàn)

假設(shè)用D代表當(dāng)前樣本集，當(dāng)前候選屬性集用A表示，則C4.5算法的流程圖如圖1所示。

3 C4.5算法的改進

3.1 C4.5算法改進原理

C4.5算法得到很好的應(yīng)用，但是還存在一些不足，C4.5 算法因為要對數(shù)據(jù)集進行多次的掃描和排序所以算法的效率降低。根據(jù)信息量計算公式的特點，改進劃分函數(shù)的屬性選擇度量計算公式和連續(xù)屬性處理方法，簡化信息量的計算復(fù)雜度，提高C4.5算法的執(zhí)行效率。

C4.5算法由于大量使用了對數(shù)函數(shù)進行熵值運算，增加了計算機的運算時間，降低了每一次屬性選擇時算法的運算效率，所以為了解決這個問題，引入泰勒中值定理和麥克勞林展開式，對熵值中的對數(shù)運算進行變換，優(yōu)化熵值運算，縮短其運算時間。

C4.5 算法對每個分割點都要計算相應(yīng)的熵值，才能得到最優(yōu)的分割點，所以在選擇最佳的屬性分割點時效率較低。為了解決這個問題，引入邊界點定義和Fayyad 定理。

邊界點定義：設(shè)序列L={x1， x2，…， xn}為升序排列的有序序列，實例X所屬的類為Cx。如果有實例xi和xj（其中j=i+1），且Cxi≠Cxj，則邊界點Bp =（xi +xj）/2。

Fayyad 定理：連續(xù)屬性 X 各個候選分割點對應(yīng)的信息熵值的最小值一定在邊界點 Bp上取得。

由以上定理可知，連續(xù)屬性的最優(yōu)分割點在計算時，只需要通過比較屬性值序列在邊界點的最小信息熵值，就可以計算出該屬性的最大修正信息增益率，減少了候補分割點，因此可以大大提高了計算的效率。

3.2 實驗及結(jié)果分析

使用Weka 作為數(shù)據(jù)挖掘平臺，對改進C4.5算法與傳統(tǒng)C4.5算法的分類性能進行比較。實驗所需數(shù)據(jù)來自于UCI數(shù)據(jù)集中IRIS的樣本實例。算法執(zhí)行效率及分類正確率實驗結(jié)果如圖2、3所示。

隨著樣本實例數(shù)的增加，改進算法的執(zhí)行效率得到提高的同時分類的正確率也有一定的提升，因此改進的 C4.5 算法縮短了數(shù)據(jù)分析的等待時間，提高工作效率，保障了分類正確率。

4 結(jié)束語

本文通過對決策樹分類算法C4.5的分析，在此基礎(chǔ)上，針對該算法所存在的不足之處，改進了熵值的計算和連續(xù)屬性最優(yōu)分割點的計算，并用實驗驗證，得到較好的驗證結(jié)果。

參考文獻

[1]Quialan J R.hduetion ofdecision trees[M].Machine Learning，1986，（1）： 81-106.

[2]陳青山.決策樹算法在高校教學(xué)質(zhì)量評價系統(tǒng)中的應(yīng)用研究[C].西南交通大學(xué)碩士論文，2010.

[3]Quialan J R.C4.5：Programs for Machine Learning[M].NewYork：Morgan Kaufnan， 1993.

[4]黃愛輝.決策樹C4.5算法的改進及應(yīng)用[J].科學(xué)技術(shù)與工程.2009，9（1）：34-36.

[5]楊學(xué)兵，張俊.決策樹算法及其核心技術(shù)[J].計算機技術(shù)與發(fā)展，2007，17（1）：44-46.