決策樹C4.5算法改進與應用

陳杰 鄔春學

摘要：針對決策樹算法C4.5在處理數(shù)據(jù)挖掘分類問題中出現(xiàn)的算法低效以及過擬合問題，提出一種改進的TM-C4.5算法。該算法主要改進了C4.5算法的分支和剪枝策略。首先，將升序排序后的屬性按照邊界定理，得出分割類別可能分布的切點，比較各點的信息增益和通過貝葉斯分類器得到的概率，使用條件判斷確定最佳分割閾值；其次，使用簡化的CCP（Cost-Complexity Pruning）方法和評價標準，對已生成決策樹的子樹根節(jié)點計算其表面誤差率增益值和S值，從而判斷是否刪除決策樹節(jié)點和分支。實驗結果表明，用該算法生成的決策樹進行分類更為精確、合理，表明TM-C4.5算法有效。

關鍵詞：C4.5；TM-C4.5算法；CCP；貝葉斯分類器；剪枝策略；評價標準

DOIDOI：10.11907/rjdk.181302

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）010-0088-05

英文摘要Abstract：Aiming at the inefficiency and over-fitting problem of decision tree algorithm C4.5 in the classification of data mining problems， an improved TM-C4.5 algorithm is proposed. The algorithm mainly improves the branching and pruning strategy of C4.5 algorithm. First， the ascending ordered attribute values are combined with the boundary theorem to get the cut points of the possible segmentation classifications. The information gain rate of each point and the probability obtained by the Bayesian classifier are compared， and the optimal segmentation threshold is determined according to the rules. Secondly， the simplified algorithm of CCP （Cost-Complexity Pruning） and evaluation criteria were used to calculate the surface error rate gain and S value of the subtree root node of the generated decision tree to judge whether to delete the decision tree node and branch. The analysis of the experimental results shows that the classification of the decision tree made by this algorithm is more accurate and reasonable， indicating the validity of TM-C4.5 algorithm.

英文關鍵詞Key Words：C4.5；TM-C4.5 algorithm；CCP；Bayesian classifier；pruning strategy；evaluation standard

0 引言

分類技術是數(shù)據(jù)挖掘領域中一種非常重要的研究方法[1]。目前解決分類問題應用較廣泛的算法有決策樹算法、貝葉斯分類、人工神經(jīng)網(wǎng)絡算法、K鄰近算法、支持向量機算法等，而決策樹學習是以實例為基礎的歸納學習算法[2]，在數(shù)據(jù)挖掘領域?qū)儆谝环N常用、簡單有效的快速分類算法[3]。

本文對決策樹C4.5算法的分支和剪枝策略進行改進，旨在獲得更加高效、明確以及合理的分類效果。為提高算法的計算效率，文獻[4]提出利用等價無窮小性質(zhì)改變C4.5算法中的熵、信息增益和信息增益率[4]，雖然計算過程中減少了對數(shù)運算函數(shù)的調(diào)用次數(shù)，但由于忽略了常量值的計算，使得誤差值變大，導致分類結果準確率下降。針對缺失屬性值導致分類準確率下降的問題，文獻[5]提出在決策樹生成過程中，當分支的子集中屬性值未知時，返回葉子節(jié)點，標記為unknown，并在之后的剪枝中將比例超過1/3（unknown節(jié)點與葉子節(jié)點之比）的unknown節(jié)點刪除[5]。與傳統(tǒng)的C4.5算法相比，該算法的時間復雜度在屬性缺失率較高時能提高很多，但在數(shù)據(jù)集缺失率較低甚至沒有缺失率情況下，該算法的時間復雜度相比傳統(tǒng)的C4.5算法沒有明顯提升。另外，該算法對于屬性缺失率閾值的設置缺乏合理的計算方法。文獻[6]提出在實驗中加入風險評估機制，并增添了覆蓋率和高風險率作為該機制的評價標準，通過將其與樸素貝葉斯和決策樹的分類結果對比，得出決策樹的覆蓋率優(yōu)于另外兩種分類器的結論[6]。

綜合上述學者的研究成果，為了獲取更加高效和精確的決策樹模型，本文結合邊界定理和貝葉斯分類器，獲得更為精確的分割切點，使用簡化的CCP方法和評價標準對決策樹進行修剪以提高分類效率。

1 決策樹C4.5算法

ID3算法和C4.5都是由QUINLAN提出的，后者是基于前者的改進算法。ID3算法雖然可以有效處理離散型屬性，但對于連續(xù)型屬性卻難以處理。連續(xù)型屬性的處理是數(shù)據(jù)挖掘領域熱門問題之一，影響著數(shù)據(jù)挖掘算法的準確性、復雜性和可理解性[7]。同時，ID3算法容易產(chǎn)生過度擬合現(xiàn)象[8]。C4.5算法解決了ID3算法產(chǎn)生過度擬合的缺點，并增加了一些功能，如未知屬性的處理、連續(xù)屬性的離散化和規(guī)則的產(chǎn)生等[9]，具體改進如下：①在ID3的基礎上，為避免用信息增益Gain選擇屬性時偏向選擇取值多的屬性之不足，C4.5選擇用信息增益率GainRatio選擇屬性作為樹的節(jié)點；②對構造的樹進行剪枝，防止過度擬合；③完成對連續(xù)屬性的離散化處理；④對不完整數(shù)據(jù)進行處理。

C4.5算法流程見圖1。

3 實驗結果

3.1 數(shù)據(jù)預處理

實驗系統(tǒng)環(huán)境為：Windows7；編程工具：PyCharm； 編程語言：python。實驗數(shù)據(jù)來自UCI數(shù)據(jù)集，一共768條記錄，數(shù)據(jù)集劃分為11組，將其中10組600條記錄用作訓練集。采用隨機抽取方法抽取訓練集；抽取訓練集之后，將實驗室數(shù)據(jù)集剩余的168條記錄作為測試集數(shù)據(jù)。實驗數(shù)據(jù)集樣本包含9種屬性，分別為：①number of time pregnant（懷孕次數(shù)）；②Plasma glucose concentration a 2 hours in an oral glucose tolerance test（口服葡萄糖耐量試驗中血漿葡萄糖濃度為2小時）；③Diastolic blood pressure （mm Hg）（舒張壓）；④Triceps skin fold thickness （mm） 三頭肌皮褶皺厚度 ；⑤2-Hour serum insulin （mu U/ml） （2小時血清胰島素）；⑥Body mass index（BMI）；⑦Diabetes pedigree function（糖尿病譜系功能）；⑧Age （年齡）；⑨類Class（0 or 1）。

其中，將懷孕次數(shù)在0～1之間標記為Low，將2～5之間標記為Medium，大于等于6則標記為High[13]；屬性BMI（體質(zhì)指數(shù)）=體重（kg）/身高（m）。根據(jù)WHO標準劃分等級為：BMI數(shù)值小于18.5設為偏瘦， 18.5～24.9之間設為正常，大于等于25設為超重。由于實驗數(shù)據(jù)采樣范圍過于寬泛，并不能代表某一個國家或地區(qū)的典型劃分依據(jù)，因此在本實驗數(shù)據(jù)集基礎上，通過計算屬性BMI的信息增益率獲取一個節(jié)點閾值，將小于該值的屬性值標記為Light，大于該值的則為Overweight。屬性AGE的處理與屬性BMI的計算方式相似，其值分別標記為Young、Elderly。為使生成的決策樹簡明，方便后續(xù)算法進行，將數(shù)據(jù)集屬性名分別縮寫為NTP、PG、DBP、TSF、HSI、BMI、DPF、AGE。根據(jù)統(tǒng)計得出各屬性缺失值數(shù)據(jù)及所占比例，將數(shù)據(jù)以圖表展示，分別如圖3和圖4所示。

從圖3和圖4可以看出，屬性NTP的缺失值記錄數(shù)比例雖然達到了14.5%，但由于屬性的現(xiàn)實參考意義很大，因此不能作為缺失值處理；屬性TSF和HSI的缺失值分別達到了227個和374個，占據(jù)了總記錄數(shù)的29.6%和48.7%，將該屬性刪除而不是刪除包含這些缺失值的記錄，以得到更多記錄值。

通過以上分析，獲得被處理分析的數(shù)據(jù)集屬性取值如表1所示。

從表1可以看出，除了Class之外的6個屬性中，有5個都是連續(xù)屬性。在數(shù)據(jù)量較大以及連續(xù)屬性過多時，若不對離散化方法進行改進，則算法效率必受到較大影響。

3.2 實驗結果

通過結合邊界定理和貝葉斯分類器得到的屬性各切點的信息增益和概率值如表2所示。

從表2中選擇具有最大信息增益和最大概率值的切點值作為最佳分割閾值，由此得到最佳分割閾值，如表3所示。

從表3可以看出，PG的最佳分割閾值為145.5mg/dl（8.08mmol/l），這與目前醫(yī)學上口服葡萄糖耐量實驗中2小時的正常值水平7.8mmol/l很接近，反映了對連續(xù)屬性離散化的改進是有效的。其余屬性如DBP、BMI、DPF、AGE的最佳分割閾值分別為72mmHg、27.5kg/m2、1.208 5和37。

此外，改進后的方法與原方法的執(zhí)行時間分別為855ms和937ms，時間縮短了8.75%。由于數(shù)據(jù)集的數(shù)據(jù)量有限，因而效率提高不大，但相比原算法已經(jīng)有了明顯提升。

圖5是屬性AGE和BMI下的各節(jié)點表面誤差率增益值和S值情況，通過改進方法選擇刪除兩者值都較小的節(jié)點。

由圖5可以看出，BMI下的子樹AGE的表面誤差率增益值為0.014 3，為最小值，其S值0.442也最小，表明該節(jié)點的分類精度和覆蓋率都比較差，因此刪除該節(jié)點改為用葉子節(jié)點替代。若沒有引入評價標準S作為CCP方法的補充，在表面誤差率增益值相差千分之幾的情況下就很難抉擇應該刪除哪個節(jié)點。

表4所示為當測試集Ti （i=1，2，3，4，5）的實例數(shù)目分別為100、200、300、400、500時，C4.5算法和改進后的TM-C4.5算法的分類精度比較結果。

從表4可以看出，TM-C4.5算法的分類精度在不同的測試集下普遍高于原C4.5算法的分類精度。測試集實例數(shù)目遞增時，改進后的算法準確率也逐步上升，證明了TM-C4.5算法的有效性。

4 結語

本文引用邊界定理作為基礎，進行節(jié)點貝葉斯概率計算，在決策樹生成過程中提高了對子樹根節(jié)點為連續(xù)屬性時的離散化效率；在對決策樹后剪枝時，在原來的CCP方法上添加了評價標準，使得在刪除子樹根節(jié)點時，確保該節(jié)點相比于其它節(jié)點，在分類過程中對整個決策樹影響較小。但是在處理數(shù)據(jù)集的缺失屬性值時，對于占比較大的屬性直接刪除，雖然省去了處理這些缺失值的麻煩，但是對最后生成的決策樹會有一定影響。目前對缺失值的處理方法有刪除法、插補法（均值插補、回歸插補）等。因此，如何處理那些有較大數(shù)量缺失值的屬性是下一步研究方向。

參考文獻：

[1] 徐洪偉.數(shù)據(jù)挖掘中決策樹分類算法的研究與改進[D]. 哈爾濱： 哈爾濱工程大學， 2010.

[2] 王源，王甜甜.改進決策樹算法的應用研究[J].電子科技，2010，23（9）：89-91.

[3] 張琳，陳燕，李桃迎，等.決策樹分類算法研究[J].計算機工程，2011，37（13）：66-67.

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

[5] 邱磊.基于決策樹C4.5算法剪枝策略的改進研究[D].武漢：華中師范大學，2016.

[6] SONGTHUNG D， SRIPANIDKULHAI K. Improving type 2 diabetes mellitus risk prediction[C].International Joint Conferenceon Computer Science and Software Engineering （JCSSE），2016.

[7] DEWAN MD，F(xiàn)ARID. Improve the quality of supervised discretization of continuous valued attributes in dataMining[C]. Proceedings of 14th International Conference on Computer and Information Technology （ICCIT 2011）， 2011.

[8] 朱琳， 楊楊. ID3算法的優(yōu)化 [J]. 計算機工程與軟件，2016，37（12）： 155-161.

[9] 譚俊璐，武建華.基于決策樹規(guī)則的分類算法研究[J].計算機工程與設計，2010，31 （5）：354-358.

[10] BOVIC KILUNDU， CHRISTOPHE LETOT， PIERRE DEHOMBREUX， et al. Early detection of bearing damage by means of decisiontrees[C]. IFAC Proceedings Volumes，2008.

[11] HAN J C， RODRIGUEZ， BEHESHTI J C M.Diabetes data analysis and prediction model discovery using rapid miner [J]. International Conference on Future GenerationCommunication and Networking， 2008（3）：9-99.

[12] 苗煜飛，張霄宏.決策樹C4.5 算法的優(yōu)化與應用[J]. 計算機工程與應用，2015，51（13）： 255-258.

[13] 李瑞，程亞楠.一種改進的C4.5算法[J].科學技術與工程，2010，10（27）：6670-6674.

（責任編輯：杜能鋼）