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

王志春 劉麗娜

【關鍵詞】數據挖掘 決策樹 C4.5算法 信息增益率

1 引言

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

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

2 C4.5算法

2.1 信息增益和信息增益率

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

2.1.1 信息增益

ID3算法中選擇具有最高信息增益的屬性作為節點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 信息增益率

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

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

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

2.2 C4.5算法實現

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

3 C4.5算法的改進

3.1 C4.5算法改進原理

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

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

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

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

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

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

3.2 實驗及結果分析

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

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

4 結束語

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

參考文獻

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

[2]陳青山.決策樹算法在高校教學質量評價系統中的應用研究[C].西南交通大學碩士論文，2010.

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

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

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