一種改進(jìn)的MEP決策樹剪枝算法

焦亞男 馬杰

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

關(guān)?鍵?詞?決策樹;剪枝;MEP;PEP?;?IMEP

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

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

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

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

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

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

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

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

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

如果所有類別的先驗(yàn)概率都相同時，即[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é)點(diǎn)[t]的樣本總數(shù);[ni（t）]為節(jié)點(diǎn)[t]中主類的樣本數(shù)量。

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

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

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

2?改進(jìn)的決策樹剪枝算法IMEP

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

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

2.1?IMEP剪枝方法

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

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

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

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

3）自下而上進(jìn)行回縮;

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

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

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

2.2?[k]-折交叉驗(yàn)證方法

1）將訓(xùn)練集D分為[k]個子集，[D1，D2，…，Dk]作為驗(yàn)證集，對應(yīng)訓(xùn)練集為[D-Di?（i=1，2，…，k）];

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

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

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

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

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

3?實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

由表6可以看出，對于用CART算法構(gòu)造的決策樹，對結(jié)果影響最大的特征屬性是“parents”。剪枝后，只有CCP算法的精度變高了;MEP算法不僅過多剪裁決策樹，而且影響特征也發(fā)生變化，所以MEP算法誤差較大;用CCP算法對決策樹剪枝后，樹的結(jié)構(gòu)沒有變化，影響特征保持不變，但數(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)不盡如人意，但每種剪枝算法都有自己的適用領(lǐng)域，IMEP相比于MEP已經(jīng)提升了很多。

4?結(jié)束語

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

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

參考文獻(xiàn)：

[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]????路翀，徐輝，楊永春.?基于決策樹分類算法的研究與應(yīng)用[J].?電子設(shè)計(jì)工程，2016，24（18）：1-3.

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

[6]????李孝偉，陳福才，李邵梅.?基于分類規(guī)則的C4.?5決策樹改進(jìn)算法[J].?計(jì)算機(jī)工程與設(shè)計(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ìn)[J].?計(jì)算機(jī)工程與設(shè)計(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]??趙建民，黃珊，王梅，等.?改進(jìn)的C4.?5算法的研究與應(yīng)用[J].?計(jì)算機(jī)與數(shù)字工程，2019，47（2）：261-265.

[19]??張亮，寧芊.?CART決策樹的兩種改進(jìn)及應(yīng)用[J].?計(jì)算機(jī)工程與設(shè)計(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.

[責(zé)任編輯????田????豐]