陳杰 鄔春學(xué)

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

關(guān)鍵詞：C4.5；TM-C4.5算法；CCP；貝葉斯分類器；剪枝策略；評(píng)價(jià)標(biāo)準(zhǔn)

DOIDOI：10.11907/rjdk.181302

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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.

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

0 引言

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

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

綜合上述學(xué)者的研究成果，為了獲取更加高效和精確的決策樹模型，本文結(jié)合邊界定理和貝葉斯分類器，獲得更為精確的分割切點(diǎn)，使用簡化的CCP方法和評(píng)價(jià)標(biāo)準(zhǔn)對決策樹進(jìn)行修剪以提高分類效率。

1 決策樹C4.5算法

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

C4.5算法流程見圖1。

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

[5] 邱磊.基于決策樹C4.5算法剪枝策略的改進(jìn)研究[D].武漢：華中師范大學(xué)，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]. 計(jì)算機(jī)工程與軟件，2016，37（12）： 155-161.

[9] 譚俊璐，武建華.基于決策樹規(guī)則的分類算法研究[J].計(jì)算機(jī)工程與設(shè)計(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)化與應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用，2015，51（13）： 255-258.

[13] 李瑞，程亞楠.一種改進(jìn)的C4.5算法[J].科學(xué)技術(shù)與工程，2010，10（27）：6670-6674.

（責(zé)任編輯：杜能鋼）