焦亞男 馬杰

摘要?決策樹剪枝是將已生成的決策樹進行簡化的過程，包括預剪枝和后剪枝。為了提高后剪枝算法MEP的剪枝精度，防止因MEP影響因子選取不當造成決策樹修剪過度而丟失特征信息的問題，提出一種改進的MEP算法即IMEP方法。首先引入k-折交叉驗證（k-Fold?Cross-Validation）方法用于選取最優(yōu)的影響因子m，然后將m帶入到MEP算法，再對原始決策樹進行剪枝，可以得到最精確的決策樹，并保持決策樹的影響特征。其次，通過k次交叉驗證，可以避免產(chǎn)生過擬合問題，和單獨測試集方法相比，經(jīng)過k次交叉驗證后，已經(jīng)減弱了隨機性，防止出現(xiàn)“欠學習”問題。經(jīng)過驗證IMEP方法不僅提高了MEP的精度，能更精準簡化決策樹，并且保持決策樹的影響特征。相比于PEP算法，在數(shù)據(jù)集較小時有更好的適用性，表現(xiàn)更加穩(wěn)定。

關?鍵?詞?決策樹;剪枝;MEP;PEP?;?IMEP

中圖分類號?TP391.1?????文獻標志碼?A

An?improved?pruning?algorithm?for?MEP?decision?tree

JIAO?Ya′nan，MA?Jie

（School?of?Electronics?and?Information?Engineering，?Hebei?University?of?Technology，?Tianjin?300401，?China）

Abstract?Decision?tree?pruning?is?to?simplify?the?generated?decision?tree?both?in?the?pre-pruning?and?post-pruning.?In?order?to?improve?the?pruning?accuracy?of?post-pruning?algorithm?MEP?and?prevent?the?problems?of?excessive?pruning?of?decision?tree?and?loss?of?feature?information?caused?by?improper?selection?of?influence?factors?of?MEP，?an?improved?MEP?algorithm?called?IMEP?algorithm?is?proposed.?First，?the?k-Fold?Cross-Validation?method?is?introduced?to?select?the?optimal?impact?factor?m，?and?the?factor?m?is?introduced?into?MEP?algorithm.?By?pruning?the?original?decision?tree，?the?most?precise?decision?tree?can?be?obtained?and?the?impact?characteristics?of?the?decision?tree?can?be?maintained.?Secondly，?the?problem?of?over-fitting?can?be?avoided?by?k-times?cross-validation.?Compared?with?the?single?test?set，?after?k-times?cross-validation，?the?randomness?has?been?weakened?and?the?problem?of?under-learning?has?been?prevented.?After?verification，?IMEP?algorithm?not?only?improves?the?accuracy?of?MEP，?but?also?simplifies?the?decision?tree?more?precisely，?and?maintains?the?influence?characteristics?of?the?decision?tree.?Compared?with?PEP?algorithm，?it?has?better?applicability?and?more?stable?performance?when?the?data?set?is?small.

Key?words?decision?tree;?pruning;?MEP;?PEP;?IMEP

0?引言

隨著人工智能時代的到來和信息時代的深入，機器學習從起源到深入人心，如今已經(jīng)被應用到了諸多領域。同時，決策樹作為機器學習中一種基本的分類與回歸的方法受到普遍關注和廣泛研究[1-3]。決策樹算法通過學習給定的訓練集，學得分類或者回歸的規(guī)則，繼而用于新數(shù)據(jù)集的預測。決策樹模型由節(jié)點和有向邊構成，節(jié)點分為內(nèi)部節(jié)點和葉節(jié)點。內(nèi)部節(jié)點對應于一個屬性或特征，葉節(jié)點對應于一個類。決策樹的創(chuàng)建分3步：特征選擇、決策樹生成、決策樹修剪。建立決策樹是以自上而下遞歸的方式來實現(xiàn)的[4]。初始狀態(tài)時，所有的數(shù)據(jù)都在根節(jié)點，若樣本都屬于同一類，則該節(jié)點為葉節(jié)點，并用相應的類別標號標記;如若不是同一類，對當前數(shù)據(jù)集進行劃分，通過某種特征選取規(guī)則，對特征屬性的每一個取值創(chuàng)建分支;最后，根據(jù)相同的規(guī)則，對樣本進行劃分，依次遞歸形成決策樹，直到出現(xiàn)一種以下情況時決策樹停止生長[5-6]：1）當前節(jié)點上的數(shù)據(jù)類別都相同;2）沒有剩余的特征屬性可以劃分。

上述過程完成了決策樹的生成，但是在實際構造決策樹時，存在諸多的不確定性因素，例如孤立噪聲、樣本關聯(lián)性較差等。由于決策樹的生成并未考慮這些因素，會造成得到的樹結構變得很大很復雜。但是決策樹結構復雜，并不意味著能得到更準確的分類結果[7-8]。因此，需要對決策樹進行剪枝，目前的剪枝方法分為兩大類：預剪枝和后剪枝。預剪枝是指決策樹在成長完成前，通過某種規(guī)則停止其生長;后剪枝是對一個完整的決策樹，按照某種規(guī)則剪掉部分分支。因為后剪枝會考慮整個決策樹的信息，往往優(yōu)于預剪枝，所以在實際中應用最多[9]。常用的后剪枝算法有：錯誤率降低剪枝（Reduced-Error?Pruning？，?REP）、悲觀剪枝（Pessimistic?Error?Pruning，PEP）、最小錯誤剪枝（Minimum?Error?Pruning，MEP）和代價復雜度剪枝（Cost-Complexity?Pruning，CCP）[10-12]。REP算法是最簡單的后剪枝算法之一，采用自上而下的方式進行剪枝，裁剪過程中，非葉子節(jié)點只進行一次計算，計算復雜度為線性，但是預測精度取決于訓練集與測試集的相關性程度，若相關性較差，會造成決策樹的預測能力差。PEP算法是后剪枝算法中精度最高的算法之一，不需要區(qū)分測試集與訓練集，避免REP相關性的問題，同樣采用自上而下的方式剪枝，缺點是會造成決策樹過早停止生長。MEP算法主要依托于選取合適的影響因子[m]值，當[m]值過大時會使決策樹過于簡單，決策樹裁剪過度而導致丟失特征信息。因此必須選取合適的[m]值，當選取[m]值得當時，其精度僅次于PEP算法。CCP算法兼顧了預測精度和復雜度，故而時間相較于其他算法更長，但復雜度相較于MEP算法有所降低。

通過對剪枝算法的歸納和對比，PEP算法的精度最高，其次是MEP算法。但是，PEP算法是從上到下進行剪枝，容易造成部分特征屬性丟失。尤其是對于樣本數(shù)較小的數(shù)據(jù)集，PEP算法就會變得很不穩(wěn)定。對于MEP算法，[m]的選擇會影響剪枝精度。因此，防止因MEP影響因子選取不當造成決策樹修剪過度而丟失特征信息的問題，提出了一種基于MEP算法的改進方法，暫稱為Improved?Minimum?Error?Pruning（IMEP）方法。

1?傳統(tǒng)決策樹剪枝算法

MEP[13]是一種后剪枝算法，采用自下而上的方式進行。此方法的提出最初是為了改進ID3算法的缺陷[14-16]，改善數(shù)據(jù)中存在的噪聲問題。該剪枝算法利用了貝葉斯方法，考慮了分類問題中先驗概率和后驗概率，所以可以在數(shù)據(jù)集上產(chǎn)生最小的分類錯誤概率。亦可稱之為[m]-概率估計。可以認為通過調(diào)整[m]值來應對不同的問題。一般而言，決策樹的裁剪程度與[m]值成正比。

具體的剪枝方法為：如果樣本共有[k]類，那么在決策樹節(jié)點[t]的訓練樣本中，屬于類別[i]的概率如式（1）所示：

[Pi（t）=ni（t）+Pai（t）×mn（t）+m]， （1）

式中：[Pai]為[i]類樣本的先驗概率，即類別[i]的樣本在整個數(shù)據(jù)集的占比;[m]為[Pai]對后驗概率[Pi]的影響因子，所以[m]并不是定值。那么節(jié)點[t]的預測錯誤率[Er（t）]定義為如式（2）所示：

[Er（t）=min{1-Pi（t）}=minn（t）-ni（t）+（1+Pai（t））×mn（t）+m]。 （2）

如果所有類別的先驗概率都相同時，即[Pai=1/k]，（[i]=1，2，…，[k]），即[m=k]，此時的[Er（t）]可以表示為

[Er（t）=n（t）-ni（t）+（k-1）n（t）+k]， （3）

式中：[n（t）]為節(jié)點[t]的樣本總數(shù);[ni（t）]為節(jié)點[t]中主類的樣本數(shù)量。

最后，分別計算非葉節(jié)點的誤差[Er（t）]，然后計算每個分支的誤差[Er（Tt）]，再加權相加，權重為分支的樣本數(shù)量占比，如果[Er（t）]大于[Er（Tt）]，則保留該子樹，否則剪裁掉該子樹。

MEP算法的主要優(yōu)點是可變的影響因子[m]，[m]值決定了樹的剪裁程度，選擇適當?shù)腫m]值，就可以得到最優(yōu)決策樹。例如，當[m]取值很大時，決策樹會被剪裁成單個葉節(jié)點，從而具有最小分類錯誤率。但是，也因此造成了一個缺點，[m]值越大，訓練集的影響越小，決策樹結構越簡單;然而在這種情況下，并不能直接生成較小的樹。對于每一個[m]值，都必須從原始決策樹開始剪裁，所以這種非單調(diào)性會使計算度變得復雜。

剪枝算法還有諸如REP、PEP、CPP等，使用情況歸納如表1所示。不同的剪枝算法有不同的優(yōu)缺點，有不同的適用范圍。通過對比上述因素可以發(fā)現(xiàn)，剪枝算法最好不需要額外剪枝集，防止過剪枝問題;最好剪枝方式是自下而上，以免出現(xiàn)“視野效應”[17];誤差估計對于不同的數(shù)據(jù)集，有著不同的最優(yōu)情況，一般連續(xù)校正的精度最好;計算復雜度和節(jié)點數(shù)目最好是線性關系。PEP算法精度最高，其次為MEP算法，但對于數(shù)據(jù)集較小的樣本，PEP算法會不適用，反而不如MEP算法，為提升MEP算法的精度，應該選取合適的[m]值。

2?改進的決策樹剪枝算法IMEP

分析歸納現(xiàn)有的剪枝算法后，提出一種基于MEP算法的改進決策樹剪枝方法IMEP，以提高MEP剪枝算法的精度。

剪枝過程和CCP算法類似，分為2個步驟。1）剪枝規(guī)則和MEP基本相同，不同的是影響因子[m]不再是定值[k]，而是一系列的變值，需要選擇出最優(yōu)的[m]值。所以剪枝規(guī)則不再是式（3），而是原始規(guī)則式（2）。2）對于選擇最優(yōu)的[m]值，在這里采用[k]-折交叉驗證（K-Fold?Cross-Validation），和CCP算法中的交叉驗證類似，不同的是并不是采用單獨剪枝集驗證一次，而是驗證[k]次。

2.1?IMEP剪枝方法

輸入：生成算法產(chǎn)生的整個樹T;

輸出：修剪后子樹[Tm];

1）[k]-折交叉驗證得到最優(yōu)[m]值，求節(jié)點誤差[E（t）]，采用最優(yōu)[m]值，而非[k];

2）計算每個非葉節(jié)點誤差[Er（t）];

3）自下而上進行回縮;

4）?計算該節(jié)點每個分枝的誤差[Er（Tt）];

5）如果[Er（t）]<[Er（Tt）]，進行裁剪使父節(jié)點變?yōu)樾碌娜~節(jié)點，否則保留該子樹;

6）返回2），直到不能繼續(xù)為止，得到剪枝樹。

2.2?[k]-折交叉驗證方法

1）將訓練集D分為[k]個子集，[D1，D2，…，Dk]作為驗證集，對應訓練集為[D-Di?（i=1，2，…，k）];

2）利用[k]個訓練集生成[k]個決策樹[T1，T2，…，Tk];

3）選定一個[m]值，對[k]個決策樹進行與MEP剪枝規(guī)則相同的剪枝，[m]值為選定的值，并非[k];

4）用[k]個驗證集分別驗證剪枝后的決策樹，取所有驗證集的正確率的平均數(shù)，作為此K-CV分類器的性能評價指標，記錄當前指標;

5）改變[m]值，返回3），直到得到最優(yōu)的性能指標，此時的[m]值為最優(yōu)[m]值。

根據(jù)上述IMEP方法的剪枝過程，可以看出此算法的優(yōu)點。首先，提高了算法精度，不斷選擇最優(yōu)[m]值，得到最高精度的決策樹;其次，通過[k]次交叉驗證，可以避免產(chǎn)生過擬合問題。和單獨測試集方法相比，經(jīng)過[k]次交叉驗證后，已經(jīng)減弱了隨機性，防止出現(xiàn)“欠學習”問題。但是，IMEP方法的缺點也很明顯，就是計算復雜度。[k]次交叉驗證再加上重復剪枝選擇最優(yōu)[m]值，會大大增加計算的復雜度，從而剪枝時間也會變長。綜上所述，IMEP方法為了提高算法精度，導致計算復雜度增加，犧牲掉了剪枝時間。由于PEP算法對數(shù)據(jù)量較小時，剪枝效果并不穩(wěn)定，選取精度次之的MEP算法，因此IMEP處理的數(shù)據(jù)量較小，由犧牲剪枝時間換取來的精度度是值得的。

3?實驗結果與分析

本文實驗采用2個數(shù)據(jù)集分別是西瓜數(shù)據(jù)集2.0和“Nursery”數(shù)據(jù)集，來自加州大學歐文分校用于機器學習的“UCI數(shù)據(jù)庫”。對2個數(shù)據(jù)集分別用C4.5、CART[18-19]算法構建決策樹，然后用REP、PEP、MEP、IMEP、CCP剪枝算法進行剪枝，以此來分析IMEP剪枝的性能。

西瓜數(shù)據(jù)集2.0數(shù)據(jù)量較小，共有17條樣本，6個屬性，通過色澤、根蒂、敲聲、紋理、臍部、和觸感這6條屬性來判別西瓜是否為好瓜。如表2所示。

用C4.5算法構建的決策樹，PEP剪枝算法使決策樹丟失較多特征信息，MEP剪枝算法會改善PEP剪枝所出現(xiàn)的問題，IMEP剪枝方法保留了決策樹過多的的特征信息;通過表3可以發(fā)現(xiàn)，PEP算法沒有影響數(shù)據(jù)集精度，MEP和IMEP算法都提高了精度，IMEP甚至在這個例子中提高到100%。

用CART算法構建的決策樹，MEP剪枝算法裁掉決策樹大部分枝節(jié)，CCP剪枝算法只剪裁掉決策樹一部分枝節(jié)，IMEP剪枝方法結果和MEP算法相同;表4可以發(fā)現(xiàn)，只有CCP算法會造成數(shù)據(jù)集精度上升，MEP和IMEP方法的數(shù)據(jù)集精度均保持不變，而且均簡化了決策樹結構。

“Nursery”數(shù)據(jù)集有9個屬性，因為數(shù)據(jù)集的樣本數(shù)過多（超過1?000），所以構造的決策樹非常龐大，沒必要再以圖的形式展示，所以從3個角度分析：樹的復雜度（即深度和葉子數(shù)）、最多非葉節(jié)點（即影響特征屬性）和數(shù)據(jù)集精度[20]。

由表5可以看出，對于用C4.5算法構造的決策樹，對結果影響最大的特征屬性是“form”。剪枝后，只有IMEP方法的影響特征沒有變化;MEP算法不僅過多剪裁決策樹，而且精度下降，影響特征也和其它算法不同，所以MEP算法沒有正確剪裁決策樹;PEP算法保持剪枝前的精度，同時大大簡化了決策樹，可影響特征變成“housing”;IMEP方法不僅提高了精度，而且簡化了決策樹，影響特征屬性仍然是“form”。

由表6可以看出，對于用CART算法構造的決策樹，對結果影響最大的特征屬性是“parents”。剪枝后，只有CCP算法的精度變高了;MEP算法不僅過多剪裁決策樹，而且影響特征也發(fā)生變化，所以MEP算法誤差較大;用CCP算法對決策樹剪枝后，樹的結構沒有變化，影響特征保持不變，但數(shù)據(jù)精度有所提高;可是IMEP算法，已經(jīng)無法裁剪此決策樹，由此可見CCP算法對于CART決策樹的“專業(yè)性”，也體現(xiàn)了IMEP算法對于CART決策樹的不足。

綜上所述，對于不同的決策樹算法，影響數(shù)據(jù)集的特征屬性不同。根據(jù)剪枝前后的變化和數(shù)據(jù)集精度，IMEP在用C4.5的剪枝過程中表現(xiàn)出了優(yōu)秀的特性，不僅提高了數(shù)據(jù)精度，而且保持特征屬性不變，在性能提升面十分顯著，而相較于CCP剪枝CART決策樹表現(xiàn)不盡如人意，但每種剪枝算法都有自己的適用領域，IMEP相比于MEP已經(jīng)提升了很多。

4?結束語

對于決策樹生成算法，通過不同的數(shù)據(jù)集和不同決策樹之間對比，可以分別概括3種決策樹算法特點[21]：ID3算法適合處理特征屬性較少，特征取值也較少的數(shù)據(jù)集;CART算法適合處理特征屬性較多，但特征取值較少的數(shù)據(jù)集;而C4.5算法解決了ID3算法在特征取值較多時的問題，也能保持CART算法在特征屬性較多時的優(yōu)點，所以在復雜度簡單或復雜的情況下都有較好的表現(xiàn)。因此，C4.5算法在決策樹算法中，得到最廣泛的應用。

對于決策樹剪枝方法，通過對同一數(shù)據(jù)集采用不同剪枝算法剪枝，可以概括出以下剪枝方法特點[22]：預剪枝算法雖然算法簡單，但是會丟失很多重要信息;REP算法精度較預剪枝會提高，是最簡單的后剪枝算法，但需要額外的剪枝集，不適用于數(shù)據(jù)量少的數(shù)據(jù)集;PEP算法的精度很高，而且不需要額外剪枝集，適用范圍很廣，但對于數(shù)據(jù)量少的數(shù)據(jù)集可能不太穩(wěn)定;MEP算法精度僅次于PEP算法，而且也不需要額外剪枝集，但隨著數(shù)據(jù)量增多性能會下降，不適合數(shù)據(jù)量較多的數(shù)據(jù)集;CCP算法精度不如其它后剪枝算法，只適用于CART算法生成的決策樹，而且需要額外剪枝集，不過對于復雜的CART算法決策樹，其他剪枝算法效果比較差，CCP算法就會體現(xiàn)出優(yōu)點;對于改進的IMEP方法，體現(xiàn)出了極高的精度，但是計算時間比較長，而且和PEP算法類似，樹的結構也比較復雜，尤其是數(shù)據(jù)量多的數(shù)據(jù)集。因此，PEP剪枝算法的精度比較高，適用范圍廣，因此得到最廣泛的應用。不過對于數(shù)據(jù)量較少的數(shù)據(jù)集，PEP算法會表現(xiàn)不穩(wěn)定，那么IMEP算法可以填補這一缺點。

參考文獻：

[1]????HU?Q?H，CHE?X?J，ZHANG?L，et?al.?Rank?entropy-based?decision?trees?for?monotonic?classification[J].?IEEE?Transactions?on?Knowledge?and?Data?Engineering，2012，24（11）：2052-2064.

[2]????RIVERA-LOPEZ?R，CANUL-REICH?J.?Construction?of?near-optimal?axis-parallel?decision?trees?using?a?differential-evolution-based?approach[J].?IEEE?Access，2018，6（1）：5548-5563.

[3]????CHO?C，CHUNG?W，KUO?S.?Using?tree-based?approaches?to?analyze?dependability?and?security?on?I&C?systems?in?safety-critical?systems[J].?IEEE?Systems?Journal，2018，12（2）：1118-1128.

[4]????路翀，徐輝，楊永春.?基于決策樹分類算法的研究與應用[J].?電子設計工程，2016，24（18）：1-3.

[5]????鄭偉，馬楠.?一種改進的決策樹后剪枝算法[J].?計算機與數(shù)字工程，2015，43（6）：960-966，971.

[6]????李孝偉，陳福才，李邵梅.?基于分類規(guī)則的C4.?5決策樹改進算法[J].?計算機工程與設計，2013，34（12）：4321-4325，4330.

[7]????HASHIM?H，TALAB?A?A，SATTY?A，et?al.?Data?mining?methodologies?to?study?student's?academic?performance?using?the?C4.?5?algorithm[J].?International?Journal?on?Computational?Science?&?Applications，2015，5（2）：59-68.

[8]????MATTHEW?N，ANYANWU，SAJJAN?G，et?al.?Comparative?analysis?of?serial?decision?tree?classification?algorithms[J].?International?Journal?of?Computer?Science?and?Security，2009，3（3）：230-240.

[9]????LIM?H，CHOE?Y，SHIM?M，et?al.?A?quad-trie?conditionally?merged?with?a?decision?tree?for?packet?classification[J].?IEEE?Communications?Letters，2014，18（4）：676-679.

[10]??BARROS?R?C，BASGALUPP?M?P，F(xiàn)REITAS?A?A，et?al.?Evolutionary?design?of?decision-tree?algorithms?tailored?to?microarray?gene?expression?data?sets[J].?IEEE?Transactions?on?Evolutionary?Computation，2014，18（6）：873-892.

[11]??WANG?T，BI?T?S，WANG?H?F，et?al.?Decision?tree?based?online?stability?assessment?scheme?for?power?systems?with?renewable?generations[J].?CSEE?Journal?of?Power?and?Energy?Systems，2015，1（2）：53-61.

[12]??CHENG?Y，WANG?P.?Packet?classification?using?dynamically?generated?decision?trees[J].?IEEE?Transactions?on?Computers，2015，64（2）：582-586.

[13]??MA?B，WANG?D，CHENG?S?G，et?al.?Modeling?and?analysis?for?vertical?handoff?based?on?the?decision?tree?in?a?heterogeneous?vehicle?network[J].?IEEE?Access，2017，5：8812-8824.

[14]??王小巍，蔣玉明.?決策樹ID3算法的分析與改進[J].?計算機工程與設計，2011，32（9）：3069-3072，3076.

[15]??WANG?X?H，WANG?L?L，LI?N?F.?An?application?of?decision?tree?based?on?ID3?[J].?International?Conference?on?Solid?State?Devices?and?Materials?Sciencet，Physics?Procedia，2012，25（4）：1017-1021.

[16]??YANG?S，GUO?J?Z，JIN?J?W.?An?improved?Id3?algorithm?for?medical?data?classification[J].?Computers?and?Electrical?Engineering，2018，65：474-487.

[17]??TONG?D，QU?Y?R，PRASANNA?V?K.?Accelerating?decision?tree?based?traffic?classification?on?FPGA?and?multicore?platforms[J].?IEEE?Transactions?on?Parallel?and?Distributed?Systems，2017，28（11）：3046-3059.

[18]??趙建民，黃珊，王梅，等.?改進的C4.?5算法的研究與應用[J].?計算機與數(shù)字工程，2019，47（2）：261-265.

[19]??張亮，寧芊.?CART決策樹的兩種改進及應用[J].?計算機工程與設計，2015，36（5）：1209-1213.

[20]??MüHLBACHER?T，LINHARDT?L，M？LLER?T，et?al.?TreePOD：sensitivity-aware?selection?of?Pareto-optimal?decision?trees[J].?IEEE?Transactions?on?Visualization?and?Computer?Graphics，2018，24（1）：174-183.

[21]??JAWORSKI?M，DUDA?P，RUTKOWSKI?L.?New?splitting?criteria?for?decision?trees?in?stationary?data?streams[J].?IEEE?Transactions?on?Neural?Networks?and?Learning?Systems，2018，29（6）：2516-2529.

[22]??LIN?G?S，SHEN?C?H，VAN?DEN?HENGEL?A.?Supervised?hashing?using?graph?cuts?and?boosted?decision?trees[J].?IEEE?Transactions?on?Pattern?Analysis?and?Machine?Intelligence，2015，37（11）：2317-2331.

[責任編輯????田????豐]