決策樹C4.5連續屬性分割閾值算法改進及其應用

姚亞夫，邢留濤

(中南大學 機電工程學院，湖南 長沙，410083)

分類問題是數據挖掘領域中研究和應用最為廣泛的技術之一。近年來，分類問題在許多行業和領域都有廣泛的應用[1]，如何更精確、更有效地分類一直是廣大科研工作者的目標。決策樹以其預測準確率高、穩定性好、直觀易懂等特點[2-4]，得到廣泛的應用。目前，構造決策樹的算法比較多[5-6]，用不同的算法可以構造出不同的決策樹，其性能也不盡相同，決策樹的構造通常包含 2個重要步驟[7]：生成決策樹和決策樹的剪枝。每個步驟都有不同的方法，相應地就有各種不同的決策樹生成和剪枝算法，最早的決策樹算法是由 Hunt等[8]于 1966年提出的 CLS(concept learning system)。ID3算法[9]和C4.5算法[10]是目前最具影響的決策樹算法,已廣泛應用于數據分類領域。C4.5算法是在ID3算法的基礎上改進過來的，不僅可以處理離散型描述屬性，還可以處理連續性屬性。C4.5算法采用信息增益率作為選擇分枝屬性的標準，彌補了 ID3算法在使用信息增益選擇分枝屬性時偏向于取值較多的屬性的缺陷，但C4.5算法也有一些缺陷[11]。本文作者研究C4.5算法中的連續性屬性離散化技術，并提出了改進算法—局部擇優法。將改進C4.5算法應用于行人和車輛模式識別，并對改進C4.5分類器與K-均值分類器以及傳統C4.5分類器的分類性能進行比較。

1 C4.5算法

作為ID3算法的改進算法，C4.5算法克服了ID3算法的兩大缺點：(1) ID3算法使用信息增益作為評價標準來選擇根節點和各內部節點中的分枝屬性，信息增益的缺點是傾向于選擇取值較多的屬性，在某些情況下這類屬性可能不會提供太多有價值的信息，而C4.5算法采用信息增益率作為評價標準，克服了ID3算法的這點不足；(2) ID3算法只能處理描述屬性為離散型的數據集，而C4.5算法既可以處理離散型描述屬性，又可以處理連續型描述屬性。C4.5算法也是一種基于信息論[12]的機器學習方法，其核心思想是通過分析訓練數據集，在整個數據集上遞歸地建立一個決策樹，其詳細過程如下。

Step 1 對數據集進行預處理，若數據集為連續型描述屬性，需將數據集離散化，并計算所有屬性的信息增益率，選擇信息增益率最大的描述屬性作為根節點的分枝屬性。

(1) 設整個數據集為T，類別集為{C1，C2，…，Ck}，總共分為k個類，每個類對應 1個數據子集Ti(1≤i≤k)。令|T|為數據集T的樣本數，|Ci|為數據集T中屬于類別Ci的樣本數，則各類別的先驗概率為Pi=|Ci|/|T|，對數據集T進行分類所需要的信息熵[13]為：

(2) 設描述屬性Ak(k=1，2，…，m)有q個不同的取值{a1k，a2k，…，aqk}，用描述屬性Ak可將數據集T劃分為q個子集{T1，T2，…，Tq}，Tj(j=1，2，…，q)中的樣本在屬性Ak上具有相同的取值為子集Tj中的樣本數，為子集Tj中屬于類別Ci的樣本數，則由描述屬性Ak劃分數據集T所得信息熵為：

(3) 屬性Ak的信息熵為：

由式(4)和(5)可得信息增益率的計算公式：

式中：k=1，2，…，m，此式即為描述屬性Ak劃分數據集T的信息增益率。

Step 2 根據根節點屬性不同取值所對應的數據子集，采用與Step1相同的方法遞歸地建立樹的分枝，選擇分枝中信息增益率最大的屬性作為子節點，如此循環下去，直到所有分枝節點中的樣本屬于同一類別，即葉節點中所有樣本屬性取值相同時為止。

Step 3 對生成的決策樹進行剪枝，消除噪聲和孤立點等隨機因素的影響，以得到簡化的決策樹，C4.5采用的是后剪枝算法[14]。

Step 4 提取決策規則[15]。在C4.5算法中，對于生成的決策樹，可以直接獲得決策規則，無論是決策樹還是決策規則都可以對新的數據集進行分類預測。

C4.5算法在ID3算法的基礎上增加了處理連續型屬性的功能。在選擇某節點上的分枝屬性時，對于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個數進行計算；對于某一連續型的描述屬性Ak(本文所處理的屬性即為連續型屬性)，如果某節點中數據集的樣本數量為Tj，C4.5算法進行如下處理：

(1) 將該節點上的所有數據樣本按照連續型描述屬性的具體取值，由小到大進行排列，得到屬性值的取值序列 {A1k,A2k,…,ATjk}。

(2) 在描述屬性序列 {A1k,A2k,…,ATjk}中共生成Tj-1個分割點，共有Tj-1種對數據集的劃分方式。設第i(1≤i≤Tj)個分割點的取值為：

它將該節點上的數據集劃分為2個數據子集，可用區間[A1k,ai]，(ai,ATjk]的數據樣本來表示描述屬性Ak的取值。

(3) 屬性Ak的Tj-1種分割中的每一種情況，都可作為該屬性的2個離散取值，重新構造該屬性的離散值，按照上述公式計算每一種分割所對應的信息增益率Gain_Ratio(Ak)，選擇其中信息增益率最大的分割閾值作為屬性Ak的最佳分割閾值，即

Gain_Ratio(ak) = max{Gain_Ratio(ai)}，即ak是ai中信息增益率最大者。

2 C4.5算法的改進

作為ID3算法的改進算法，C4.5在算法功能上增強了不少，但也存在一些不足之處[11]：C4.5算法采用信息增益率作為最佳分裂屬性的評判標準，計算描述屬性的信息增益率，并選擇其中信息增益率最大的描述屬性作為節點分裂屬性。在連續型屬性離散化時，由上述C4.5算法連續型屬性離散化方法可知，算法要在任一屬性的不同取值中插入若干個分割點，再計算所有分割點的信息增益率，選擇其中信息增益率最大的分割閾值作為連續型屬性的最佳分割閾值。當決策樹的節點數量比較多、連續型屬性數量比較多、連續型屬性中任一屬性取值又比較多時，算法的計算量是相當大的，這將會在很大程度上影響決策樹的生成效率。本文針對C4.5算法中連續型屬性最佳分割閾值選擇算法的計算復雜性問題提出了一些改進，以提高決策樹的效率。

2.1 連續型屬性處理算法的改進

C4.5算法在連續屬性離散化過程中，要對所有劃分情況進行預測，這將占用很多時間。如何快速選擇一個最佳的劃分閾值已成為亟待解決的問題。Fayyad等[16]證明：無論用于學習的數據集有多少個類別，不管類別的分布如何，連續型屬性的最佳分割點總在邊界點處。

本文根據 Fayyad邊界點原理[16]將連續型描述屬性按升序排列，選取排序后某一連續型屬性的相鄰兩類邊界點處的 6個屬性取值ai-2，ai-1，ai，ai+1，ai+2和ai+3(ai-2＜ai-1＜ai＜ai+1＜ai+2＜ai+3)作為測試屬性值。其中：ai是類1中的最大值，ai+1是類2中的最小值。計算相應的信息增益率，選擇信息增益率最大的屬性值作為最佳分割閾值進行劃分。改進后的算法只需計算邊界點處6個屬性值的信息增益率，相對于傳統C4.5算法遍歷所有的屬性值的信息增益率，其計算復雜度降低了許多。當連續型屬性只有2個類別時，簡化后算法的計算效率則更高，本文的所要處理的應用對象的實驗數據就屬于這種情況；當遇到特殊情況即每個屬性值僅代表1個類別時，改進算法的計算復雜度與C4.5算法的相當。

2.2 改進決策樹C4.5算法描述

算法：決策樹 C4.5算法，Function Tree=Create_C4.5(T,A,target)。

輸入：訓練集T,描述屬性A,描述測試樣本的類標 target。

輸出：決策樹Tree，預測分類準確率。

步驟：

(1) 在訓練集T中創建根節點N；

(2) 若訓練集T中的樣本屬于同一類別C，則以C標記節點N，并以節點N作為葉節點，返回；

(3) 如果描述屬性為空，那么以數據集中占多數的描述類別C標記節點N并將N作為葉節點，返回；

(4) 從描述屬性A中選出信息增益率最大的描述屬性Ak作為節點N的分裂屬性，轉入下一步；

(5) 若描述屬性是離散型，設屬性Ak有v種取值a1，a2，…，av，則數據集T將被Ak分為v個樣本子集，每個子集都是由屬性取值相同的樣本組成的；

(6) 若描述屬性是連續型，則用改進的連續型屬性分割算法選擇最佳分割閾值，并對屬性集A進行劃分，用離散化后屬性集對數據集T進行步驟(5)同樣的操作，返回；

(7) 選擇剩余描述屬性中最佳分裂屬性在數據子集上創建子節點，返回；

(8) 對進一步劃分的數據子集，即新建各內部節點，遞歸調用步驟(2)～步驟(7)，繼續選擇最佳分枝屬性作為內部節點，直到所有的樣本都歸類于相應的葉節點為止。

3 實驗及結果分析

實驗數據由 2個部分組成：(1) 經處理的數字視頻圖像中行人和車輛的特征數據；(2) 從標準數據集UCI中采集的部分數據。

3.1 實驗Ⅰ及結果分析

實驗Ⅰ的內容是對改進C4.5算法與傳統C4.5算法的分類性能進行比較。實驗1所用的部分數據如表1所示。

為了降低分類器的誤判率，對部分人車特征數據進行了歸一化處理。實驗1主要在決策樹生成效率和預測能力方面對改進C4.5算法與傳統C4.5算法進行了比較。實驗數據由訓練數據和測試數據2部分組成。實驗采用10重交叉驗證決策樹的分類準確率，各組實驗數據的數量不同，逐組均勻增加。實驗數據(m,n)分別代表訓練集和測試集的樣本數量。在各組實驗數據上分別訓練測試10次，求其平均分類準確率作為本實驗的記錄值，結果如表2所示。分類準確率定義為測試集中被正確識別出類別的樣本數占總樣本數的比例。實驗結果表明：改進C4.5分類器與傳統C4.5分類器的平均分類準確率相當，但在決策樹生成時間方面，改進C4.5分類器有很大的改進，減少了很大一部分用時，在一定程度上提高了 C4.5分類器的生成效率。

表1 人車特征數據(部分訓練特征)Table 1 People and vehicle feature data(part of raining feature)

3.2 實驗Ⅱ及結果分析

實驗Ⅱ的內容是對改進C4.5分類器與K-均值分類器以及傳統C4.5分類器的分類性能比較。所采用的實驗數據如表3所示，數據取自標準數據集UCI，每組數據包含數據名稱、實例個數、類個數以及屬性個數等信息，共11組。實驗采用10重交叉驗證法在標準數據集上對改進C4.5分類器的預測能力進行測試。各分類器分別在每組數據上測試10次，每次測試采用不同的數據劃分方法，采用10次測試分類準確率的平均值作為實驗記錄結果，最終以各分類器在總數據集上的平均分類準確率為依據，進行分類性能比較。

由實驗Ⅱ的結果可知：改進C4.5分類器的平均分類準確率為85.011 0%，比傳統C4.5分類器的平均分類準確率高約2.4%，比K-均值分類器高約5.7%。實驗結果表明：無論是改進 C4.5分類器還是傳統C4.5分類器都有較強的穩定性；改進C4.5分類器和傳統 C4.5分類器均比 K-均值分類器的分類性能要好；在某些數據集上，改進C4.5分類器的分類準確率更高。

表2 實驗Ⅰ的結果Table 2 Results of experiment Ⅰ %

表3 實驗Ⅱ的數據集Table 3 Data set of experiment Ⅱ

實驗Ⅰ和實驗Ⅱ的結果表明；改進C4.5分類器比傳統C4.5 分類器的分類準確率略高，但改進C4.5分類器的計算量要比傳統 C4.5分類器的計算量減少近20%，大大提高了決策樹的生成效率。無論是改進C4.5分類器還是傳統C4.5分類器，都比K-均值分類器的分類準確率要高，在算法穩定性方面，前兩者也比K-均值分類器要好，由實驗結果可知：改進C4.5分類器和傳統 C4.5分類器的分類準確率對決策樹的節點容錯率(同一節點中允許存在的錯誤樣本數占總樣本數的比例)較穩定；當節點容錯率在0～8%的范圍內調整時，改進的與傳統的C4.5分類器的分類準確率不變；當容錯率繼續調大時，二者的分類準確率均緩慢下降；當容錯率超過12%時，分類準確率則大幅度下降。分類器的穩定性較差，而K-均值分類器其分類準確率受錯誤樣本的影響較大，如有少量錯誤樣本，K-均值分類器的分類準確率就會明顯降低。

表4 實驗Ⅱ的結果Table 4 Results of experiment Ⅱ %

4 結論

(1) 對傳統 C4.5分類器處理連續型屬性的算法進行改進，提出了一種局部最佳分割閾值選擇算法，該算法在很大程度上減少了原算法的計算量，提高了決策樹的生成效率，特別是當預測數據集的類別數目比較少時，改進算法的效果更明顯。改進的算法可行，決策樹的生成效率提高了近20%，改進C4.5分類器具有較好的應用價值。

(2) 在最佳分割閾值選擇算法中，如何確定邊界點處連續屬性的取值個數是關鍵，取不同的屬性個數對算法的計算量影響很大，是否有更好的方法確定邊界點處連續屬性的取值個數有待進一步研究。

[1]Haykin S. Neural networks and learning machines[M]. Beijing:China Machine Press,2009: 1-7.

[2]ZHU Xiao-liang,WANG Jian,YAN Hong-can,et al. Research and application of the improved algorithm C4.5 on decision tree[C]//IEEE International Conference on Test and Measurement,Hongkong,2009: 184-187.

[3]de Toledo P,Rios P M,Ledezma A,et al. Predicting the outcome of patients with subarachnoid hemorrhage using machine learning techniques[J]. IEEE Trans on Information Technology in Biomedicine,2009,13(5): 794-801.

[4]Tsang S,Kao B,Yip K Y et al. Decision trees for uncertain data[C]//IEEE International Conference on Data Engineering,Shanghai,2009: 441-444.

[5]LI Fa-chao,LI Ping,JIN Chen-xia. Summary of decision tree algorithm and its application in attribute reduction[R].Shijiazhuang: Hebei Univ of Sci and Technol,2009: 313-317.

[6]謝金梅,王艷妮. 決策樹算法綜述[J]. 軟件導報,2008,7(11):83-85.XIE Jin-mei,WANG Yan-ni. Summary of decision tree algorithms[J]. Software Guide,2008,7(11): 83-85.

[7]王闐,佘光輝. 決策樹 C4.5算法在森林資源二類調查中的應用[J]. 南京林業大學學報: 自然科學版,2007,31(3): 115-118.WANG Tian,SHE Guang-hui. Application of C4.5 based decision tree algorithm about investigation and analysis of forestry resources[J]. Journal of Nanjing Forestry University:Natural Sciences Edition,2007,31(3): 115-118.

[8]Hunt E B,Marin J,Stone P T. Experiments in induction[M]. San Diego: Academic Press,1966: 77-89.

[9]CHEN Jin,LUO De-Lin,MU Fen-xiang. An improved ID3 decision tree algorithm[C]//4th International Conference on IEEE Computer Science and Education. Chengdu,2009:127-130.

[10]Quinlan J R. C4.5: Programs for machine learning[M]. San Mateo: Morgan Kaufmann Publishers Inc,1993: 17-42.

[11]楊學兵,張俊. 決策樹算法及其核心技術[J]. 計算機技術與發展,2007,17(1): 44-46.YANG Xue-bing,ZHANG Jun. Decision tree algorithm and its key techniques[J]. Computer Technology and Development,2007,17(1): 44-46.

[12]Roiger R J,Geatz M W. 數據挖掘教程[M]. 翁敬農,譯. 北京:清華大學出版社,2008: 60-85.Roiger R J,Geatz M W. Data mining tutorial[M]. WENG Jing-mong,trans. Beijing: Tsinghua University Press,2008:60-85.

[13]Maszczyk T,Duch W. Comparison of Shannon,Renyi and Tsallis entropy used in decision trees[J]. Artificial Intelligence and Soft Computing,2008,5097: 643-651.

[14]Kantardzic M. Data mining: Concepts,models,and algorithms[M]. New York: John Wiley and IEEE Press,2003:139-164.

[15]ZHOU Chi,XIAO Wei-min,Tirpak T M,et al. Evolving accurate and compact classification rules with gene expression programming[J]. IEEE Transactions on Evolutionary Computation,2003,7(6): 519-531.

[16]Fayyad U M,Irani K B. On the handling of continuous-value attributes in decision tree generation[J]. Machine Learning,1992,8(1): 87-102.