一種特征值區間劃分的模型決策樹加速算法

高虹雷，門昌騫，王文劍,2

1(山西大學 計算機與信息技術學院，太原 030006)2(山西大學 計算智能與中文信息處理教育部重點實驗室，太原 030006)

E-mail：wjwang@sxu.edu.cn

1 引 言

隨著大數據時代的來臨，合理高效地對海量數據進行分類從而得到隱藏的、有價值的、可理解的知識，將會對日常生活產生重要的影響.分類作為機器學習的一個核心任務，在數據的分析處理上發揮著重要的作用.常見的分類方法有神經網絡[1]、樸素貝葉斯法[2]、K最近鄰法[3]、決策樹[4]和支持向量機[5]、深度神經網絡[6]等.決策樹與其它分類算法相比，由于容易實現且易于理解，因而得到了廣泛地應用.目前決策樹的相關研究集中在決策樹改進方面.

傳統的決策樹算法主要有ID3算法[7]，C4.5算法[8]以及分類與回歸決策樹(classification and regression tree，CART)[9]等.ID3算法通過使用信息增益準則進行特征選擇，但不能處理連續特征值.Quinlan隨后將ID3算法進行了改進，提出C4.5算法，采用信息增益比來克服ID3算法的不足，但C4.5算法需要對數據集進行多次的順序掃描和排序，比較耗時.CART決策樹本質上是一棵二叉樹，使用Gini指數來進行特征選擇，既可以處理連續值也可以處理離散值，被稱為數據挖掘領域中里程碑式的算法.

Alsabti等人[10]從抽樣方法的角度上提出了一種新的決策樹分類器用于處理大規模數據集，在確定最優分裂結點上提供了兩種新的度量方法，縮小了搜索空間.此外，Mehta和Agrawal等人提出的一種快速可伸縮分類器SLIQ(Supervised Learning In Quest)[11]對C4.5算法進行了改進，該算法在決策樹構造過程中采用了預排序及廣度優先策略，縮短了學習的時間，提高了決策樹構建的效率，但它需將類別列表儲存在內存中，從而導致數據集的規模受到了限制.Shafer和Agrawal等人[12]對SLIQ算法進一步改進，提出了一種新的算法，該算法構建了一種可擴展、可并行的決策樹，解決了內存限制的問題.這兩種決策樹均能處理大規模數據集，且能處理連續特征值和離散特征值.Rastogi等人[13]提出了建樹和剪枝結合在一起的分類算法，用以提升決策樹構建的效率.隨著集成學習(Ensemble Learning)[14]在分類問題中的不斷推廣，越來越多的基于決策樹的集成學習方法應用而生.Breiman以決策樹為基本單元，運用Bagging方法提出的隨機森林RF(Random Forest)[15]可以有效避免過擬合問題，Friedman以決策樹為基礎，運用Boosting方法提出的GBDT(Gradient Boosting Decision Tree)[16]可以根據損失函數的不同靈活處理各種類型的數據，并在分類速度上得到了很大的提升.之后，華人科學家陳天奇和微軟公司分別開發出了GBDT的改進算法Xgboost(extreme Gradient Boosting)[17]和LightGBM(Light Gradient Boosting Machine)[18]，這兩種算法在保證分類精度的前提下，速度更快，被廣泛應用于工程領域之中.南京大學周志華教授類比深度神經網絡提出了一種新的決策樹集成方法Deep Forest[19]，使用樹集成來構建多層模型，該算法只需少量訓練數據以及參數優化就可以得到很好的性能.在2018年，周志華研究團隊又提出了多層梯度提升決策樹mGBDT(Multi-Layered Gradient Boosting Decision Trees)[20]，首次確認了可以使用決策樹來進行分布式表征，并取得了明顯的效果.

盡管對決策樹的研究已經取得了很多的成果，但仍存在一些問題，如決策樹在訓練集上的過度分類可能會導致過擬合現象的發生,從而影響分類預測的準確率.另外，在尋找最佳分裂點時需要遍歷特征的所有取值，當數據集規模較大時，遞歸構建決策樹所需時間將會很長.文獻[21]提出的模型決策樹(Model Decision Tree，MDT)相對于傳統決策樹來說加速了構建過程，在一定程度上具有抗過擬合作用.其主要思想為在分類樹葉子規模到達給定閾值時停止樹的構建，并在生成的不完全決策樹的可辨識結點(非葉結點且包含不同類別的樣本)上搭載分類器，通過分類器繼續進行分類.由于模型決策樹在可辨識結點上已經使用了比較強的分類器，但在選擇最優特征劃分和最優切分點時仍需要計算全部樣本每一特征維度上的所有取值，這樣會增加一些沒有必要的計算代價.

本文在文獻[21]基礎上提出一種基于特征值區間劃分的模型決策樹加速算法，算法根據數據的不同分布給出兩種特征值區間的分割方法，通過計算各選定區間的基尼指數，尋找最優特征及最優切分點，最后遞歸生成模型決策樹.所提出的算法可在保證分類精度的前提下加快決策樹的構建.

2 基于特征值區間劃分的模型決策樹加速算法

2.1 特征值區間劃分

模型決策樹[21]在處理二分類問題時通過對每一特征維度上的所有特征值分別計算其Gini指數并以此逐層構建二叉樹，直到樹深度或葉子節點滿足某一條件時停止，此時構建的二叉決策樹可以較好地對數據進行分類，但當數據規模較大時，用全部樣本每一特征維度上所有取值來構建決策樹會耗費大量的時間及計算資源.本文提出兩種面向不同類型特征值分布的特征值區間劃分方法，用以加速決策樹的構建過程.

2.1.1 等精度特征值區間劃分

當數據集中所有樣本每一特征維度上取值分布較為均勻時，特征取值差異較小，此時將特征取值劃分為多個等精度區間并用每一區間所含特征值的平均值代表各區間的值，之后對每一區間平均值計算其Gini指數進而構建決策樹，此時決策樹構建所需時間及計算代價將大大降低.等精度特征值區間劃分的詳細過程如下.

…

之后計算每一區間特征取值平均值：

…

此時等精度特征值區間劃分完成.圖1是在Magic Gamma Telescope數據集(說明見表1)上進行等精度特征值區間劃分的結果，在數據集中隨機挑選一個特征，利用等精度特征值區間劃分方法將其劃分成10個區間，每個區間樣本個數為902個，各分裂結點的位置即各區間內包含的所有樣本特征值的平均值.

圖1 等精度特征值區間劃分結果Fig.1 Result of equal-precision feature value interval partition

2.1.2 變精度特征值區間劃分

當數據集中所有樣本每一特征維度上取值分布波動較大時，特征取值差異較大，此時等精度特征值區間劃分無法充分表示特征取值特性，針對這種情況，本文提出變精度特征值區間劃分方法.該方法根據每一特征維度上特征取值的上界和下界將特征值取值空間等分為多個區間，之后統計每一區間中樣本個數，確定不足給定樣本個數閾值的區間，最后根據這些區間中所含樣本特征取值的平均值計算其各自Gini指數進而構建決策樹.

…

統計每一區間中包含的樣本數，對于樣本數小于給定閾值N*的區間，計算該區間內所包含特征取值的平均值，此時變精度特征值區間劃分完成.圖2是在Cod_rna數據集(說明見表1)上進行變精度特征值區間劃分的結果.在數據集中隨機挑選一個特征，利用變精度特征值區間劃分方法將其劃分成20個區間，各樣本點依據特征值的大小落入不同區間內，如給定閾值N*等于400，各分裂結點的位置就是樣本數小于400的區間內所包含的所有樣本特征值的平均值.

圖2 變精度特征值區間劃分結果Fig.2 Result of variable-precision feature value interval partition

2.2 尋找最優特征及最優切分點

特征選擇是對特征空間劃分及決策樹構建非常重要的一步，通過遞歸選擇最優特征并依據此特征計算的最優切分點對訓練數據進行劃分，從而保證各子數據集可以按照最好的分類標準去分開.一般而言，理論上希望在不斷劃分的過程中，各結點中所包含的樣本純度會不斷提高，不確定性會逐漸變小，即只包含同一類樣本.在這個過程中，有些特征并沒有分類能力，實際上舍去這些特征并不會影響分類的準確率，并且可以對決策樹分類的效率進行提高.因此，通常會使用信息增益、信息增益比、基尼指數等準則作為分類算法屬性選擇的度量標準，本文選擇Gini指數作為最優特征及最優切分點的度量.

在分類問題中，設給定的訓練數據集為D，其樣本個數為|D|，假設有K個類，Ck表示D中屬于第k類的樣本子集，k=1，2，…，K，|Ck|表示屬于Ck類樣本的個數.定義樣本點屬于第k類的概率為Pk，則該數據集在概率分布P下的Gini指數:

(1)

給定訓練數據集D的Gini指數為：

(2)

對于二分類問題，若要在訓練集D中根據特征A的某一個取值a來計算基尼指數，則訓練集D被劃分為D1和D2兩部分：

D1={(xi,yi)∈D|A(xi)=a},D2=D-D1

(3)

訓練集D在特征A的條件下，Gini指數定義為：

(4)

式(2)表示訓練集D抽取樣本類別標記不一致的概率，即Gini指數越小，純度越高，劃分越好；式(4)表示訓練集D在特征A下按特征值a劃分后的Gini指數，根據式(4)在候選屬性集合中找到使得劃分后Gini指數最小的屬性以及切分點，可以得到最優特征及最優切分點.

2.3 模型決策樹加速算法

本文提出的等精度特征值區間劃分模型決策樹算法EPPMDT(Model decision tree based on equal-precision feature value interval partition)的主要步驟總結如下.

EPPMDT算法

輸入：訓練數據集D，測試數據集S，劃分區間數Z，可辨識結點中樣本個數閾值V

輸出：EPPMDT決策樹

Step 1.對于訓練數據集D，根據等精度特征值區間劃分方法將每維特征下的特征值劃分成H0,H1,…,Hz-1個區間，計算各區間特征取值的平均值M0,M1,…,Mz-1，將其作為當前需要分裂結點上每一特征對應的可能取值；

Step 2.對每一特征A及其可能取的值a，根據樣本點對A=a將D劃分為D1和D2兩部分，通過式(4)計算所有可能的特征和所有的切分點對該數據集D的Gini指數，選擇Gini指數最小的特征和其對應的切分點進行劃分；

Step 3.對劃分之后得到的兩個子結點遞歸調用Step 1和Step 2，直至可辨識結點中樣本個數小于閾值V，這時中止決策樹的生長；

Step 4.在所得到的可辨識結點上搭載分類器，生成等精度特征值區間劃分的模型決策樹；

Step 5.算法結束.

EPPMDT算法適用于樣本每一特征維度上取值分布較為均勻，特征值差異較小的數據集.當數據集中所有樣本每一特征維度上取值分布波動較大時，特征取值差異較大時，可采用變精度特征值區間劃分模型決策樹算法VPPMDT(Model decision tree based on variable-precision feature value interval partition)，其主要步驟如下.

VPPMDT算法

輸入：訓練數據集D，測試數據集S，劃分區間數Z，區間中樣本個數閾值N*，可辨識結點中樣本個數閾值V

輸出：VPPMDT決策樹

Step 1.設根結點的訓練數據集為D，根據變精度特征值區間劃分方法將每維特征下的特征值劃分成H0,H1,…,Hz-1個區間，計算樣本數小于給定閾值N*的區間內所包含的特征取值的平均值，將其作為當前需要分裂結點上每一特征對應的可能取值；

Step 2.對每一特征A及其可能取的值a，根據樣本點對A=a將D劃分為D1和D2兩部分，通過式(4)計算所有可能的特征和所有的切分點對該數據集D的Gini指數，選擇Gini指數最小的特征和其對應的切分點進行劃分；

Step 3.對劃分之后得到的兩個子結點遞歸調用Step 1和Step 2，直至可辨識結點中樣本個數小于閾值V，中止決策樹的生長；

Step 4.在所得到的可辨識結點上搭載分類器，生成變精度特征值區間劃分的模型決策樹；

Step 5.算法結束.

3 實驗結果及分析

3.1 實驗設置及實驗數據集

實驗使用UCI數據集中的9個典型二分類數據集進行測試，如表1所示.為消除實驗的隨機性，每種算法在每個數據集上的實驗結果為運行20次結果的均值.

表1 實驗數據集Table 1 Datasets used in experiments

本文提出的EPPMDT算法及VPPMDT算法，在生成的不完全決策樹中可辨識結點上使用簡單的分類器繼續進行分類，分類器選用了軟件包LIBLINEAR模型和標準SVM模型，形成6種不同的模型，其中使用了LIBLINEAR模型的記為EPPMDT_LIB和VPPMDT_LIB，使用線性核的SVM模型記為EPPMDT_SVM(linear)和VPPMDT_SVM(linear)，使用高斯核的SVM模型記為EPPMDT_SVM(rbf)和VPPMDT_SVM(rbf).因文獻[21]中所提的算法已與常見的分類算法SVM、LIBLINEAR、邏輯回歸(Logistic Regression，LR)、KNN以及傳統決策樹DT進行了性能比較，且在分類錯誤率和運行時間方面均有提升，故本文提出的6種模型將直接與文獻[21]中提出的3種模型決策樹算法MDT_LIB、MDT_SVM(linear)和MDT_SVM(rbf)進行比較.

本實驗首先將訓練數據集按4∶1的比例隨機均勻抽樣得到驗證集，通過實驗得到對應的最優參數.實驗中可辨識結點樣本個數閾值V、LIBLINEAR中的類型參數以及SVM中懲罰參數、高斯核參數均為不同實驗數據集下在驗證集上得到的最優參數.因部分數據集訓練樣本數較少，為保證合理劃分區間，EPPMDT 3種模型算法在Madelon數據集上可辨識結點規模V取訓練樣本數的20%，VPPMDT 3種模型算法在Germen、Spambase和 Credit Card Cliet數據集上V取訓練樣本數的30%，其余算法中V均為訓練樣本數的10%.使用LIBLINEAR模型的算法類型參數S取2，使用線性核SVM模型和高斯核SVM模型算法中的懲罰參數C除在Credit Card Cliet、Magic Gamma Telescope和Cod_rna數據集中為1以外，其余均為50，使用高斯核SVM模型算法中的高斯核參數γ除在Credit Card Cliet、Magic Gamma Telescope和Cod_rna數據集中為0.5，其余均為1.

3.2 EPPMDT和VPPMDT算法的參數實驗設置

劃分區間數Z這一參數對EPPMDT算法和VPPMDT算法都有影響，除此之外，VPPMDT算法還受區間中樣本個數閾值N*的影響.

3.2.1 EPPMDT算法中劃分區間數Z的設置

模型的分類錯誤率及運行時間在不同的劃分區間數下會有所不同，因此，在不同數據集下找到最優的劃分區間個數至關重要.本文通過實驗獲得各數據集上劃分區間數Z的較優值，對于不同數據集，通過實驗設置的參數如表2所示.

表2 EPPMDT算法參數設置Table 2 Parameter setting of EPPMDT

3.2.2 VPPMDT算法中劃分區間數Z及樣本個數閾值N*的設置

在VPPMDT算法中，劃分區間數Z以及區間中樣本個數閾值N*均會影響算法的分類錯誤率及運行時間，因此，本節也是通過實驗在不同數據集下設置較優的Z和N*.對于不同數據集，通過實驗設置的參數如表3所示.

表3 VPPMDT算法參數設置Table 3 Parameter setting of VPPMDT

3.3 本文算法與MDT算法的比較

本節將本文提出的兩種算法模型EPPMDT和VPPMDT分別與文獻[21]中的MDT算法進行分類性能及運行時間的比較.MDT算法的實驗結果來自于文獻[21].

本文提出的EPPMDT算法3種模型的分類性能及運行時間的實驗結果見表4和表5.由表4和表5可知，EPPMDT_LIB算法和EPPMDT_SVM(linear)算法在相同數據集下的分類錯誤率及運行時間均相似，因為其在可辨識結點上使用的均為線性分類器，但EPPMDT_LIB算法在運行時間上還是要比EPPMDT_SVM(linear)算法快，因為LIBLINEAR模型主要還是面向于大規模數據集的，分類速度會更快一些.另外，當數據集規模相對較大時，如數據集Credit Card Cliet、Magic Gamma Telescope，EPPMDT算法提速更為明顯.

表4 不同算法下分類性能比較結果Table 4 Comparison results of classification performance under different algorithms

表5 不同算法下運行時間比較結果Table 5 Comparison results of running time under different algorithms

為更加直觀地解釋實驗結果，圖3給出EPPMDT算法與MDT算法采用3種不同分類器時分類錯誤率的大小關系比較.其中，黑點表示所用的9個數據集，橫坐標代表MDT算法的錯誤率，縱坐標代表EPPMDT算法的錯誤率.對角線上的黑點表示兩種算法錯誤率一致，在對角線上方的黑點表示在此數據集上EPPMDT算法錯誤率高于MDT算法錯誤率，對角線下方的黑點代表在此數據集上EPPMDT算法錯誤率低于MDT算法錯誤率.黑點到對角線的垂直距離越大，表示在此數據集上算法的分類錯誤率越大.由圖3可知，當采用LIBLINEAR模型時，在6個數據集上EPPMDT的錯誤率低于/相當MDT算法；當采用SVM(linear)模型時，在7個數據集上EPPMDT算法的錯誤率低于/相當MDT算法；當采用SVM(rbf)模型時，在8個數據集上EPPMDT算法的錯誤率低于/相當MDT算法.對于LIBLINEAR模型，EPPMDT算法只在2個數據集上的錯誤率略高于MDT算法；對于SVM(linear)模型，EPPMDT算法只在1個數據集上的錯誤率略高于MDT算法.特別地，在Image數據集上EPPMDT_SVM(rbf)算法的分類錯誤率比MDT_SVM(rbf)算法降低了近13倍.

圖4中是采用3種不同分類器時EPPMDT算法與MDT算法相比運行時間加速的結果.由圖4可以看出，EPPMDT相關算法在絕大部分數據集上相較MDT算法均有提升，且在部分數據集(Madelon、Spambase、Credit Card Cliet)上加速效果明顯，特別地，在Spambase數據集上EPPMDT_SVM(rbf)算法比MDT_SVM(rbf)算法運行時間快了近24倍.

圖3 EPPMDT與MDT分類錯誤率比較Fig.3 Comparison of classification error rate forEPPMDT and MDT

圖4 EPPMDT對MDT的加速結果Fig.4 Accelerating results of EPPMDT on MDT

綜上，EPPMDT算法可以在保證與MDT算法分類錯誤率相差不大或更低的條件下，使得分類效率得到有效提升.

對于VPPMDP模型，由表4和表5可知，VPPMDT_LIB算法和VPPMDT_SVM(linear)算法因在可辨識結點上均使用了線性分類器從而使得在相同數據集下的分類錯誤率及運行時間基本相似.類似地，為更加直觀地解釋實驗結果，圖5給出VPPMDT算法與MDT算法采用3種不同分類器時分類錯誤率的大小關系比較.同樣，黑點表示所用的9個數據集，橫坐標代表MDT算法的錯誤率，縱坐標代表VPPMDT算法的錯誤率.對角線上的黑點表示兩種算法錯誤率一致，在對角線上方的黑點表示在此數據集上VPPMDT算法錯誤率高于MDT算法錯誤率，對角線下方的黑點代表在此數據集上VPPMDT算法錯誤率低于MDT算法錯誤率.由圖5可知，當采用LIBLINEAR模型時，在7個數據集上VPPMDT算法的錯誤率低于/相當MDT算法；當采用SVM(linear)模型時，在7個數據集上VPPMDT算法的錯誤率低于/相當MDT算法；當采用SVM(rbf)模型時，在8個數據集上VPPMDT算法的錯誤率低于/相當MDT算法.另外， 對于LIBLINEAR和SVM(linear)模型VPPMDT算法只在2個數據集上的錯誤率略高于MDT算法；對于SVM(rbf)模型，VPPMDT算法只在1個數據集的錯誤率略高于MDT算法.特別地，在Image數據集下VPPMDT_SVM(rbf)算法的分類錯誤率比MDT_SVM(rbf)算法降低了近8倍.

圖5 VPPMDT與MDT分類錯誤率比較Fig.5 Comparison of classification error rate forVPPMDT and MDT

圖6中是采用3種不同分類器時VPPMDT算法與MDT算法相比運行時間加速的結果.由圖6可以看出，除采用SVM(linear)模型時在Germen數據集上VPPMDT算法的運行時間高于MDT算法，VPPMDT相關算法在其它數據集上相較MDT算法均有提升，且在5個數據集上加速效果明顯(Madelon、Spambase、Image、Credit Card Cliet、Magic Gamma Telescope)，特別在Credit Card Cliet數據集上，VPPMDT_SVM(rbf)算法比MDT_SVM(rbf)算法運行時間快了近10倍.

圖6 VPPMDT對MDT的加速結果Fig.6 Accelerating results of VPPMDT on MDT

綜上，VPPMDT算法可以在保證與MDT算法分類錯誤率相差不大或更低的條件下，分類效率不同程度得到有效提升.

3.4 EPPMDT算法與VPPMDT算法結果比較

由3.3節實驗可知，本文提出的EPPMDT算法與VPPMDT算法，在保證與MDT算法分類錯誤率相差不大或更低的條件下，分類時間均得到了大幅度降低.圖7是EPPMDT與VPPMDT分類性能的比較，從圖中可以看出，兩種算法在大部分數據集上的性能也大體相同.通過實驗可以看出，EPPMDT算法更適用于每一特征維度上取值分布較為均勻，特征值差異較小的數據集，比如在Madelon數據集上EPPMDT算法的分類性能比VPPMDT算法要好.當數據集中所有樣本每一特征維度上取值分布波動較大時，特征取值差異較大，如Credit Card Cliet數據集，這時VPPMDT算法分類性能要比EPPMDT算法好.

3.5 算法抗過擬合性分析

在傳統決策樹算法中，過擬合現象一直都是普遍存在的一個問題.由于決策樹過度生長，導致葉節點樣本基本都是“純”的，雖然對于訓練集分類效果很好但在測試集上的分類效果并不理想.本文提出的EPPMDT算法及VPPMDT算法，在區間劃分的過程和生成一顆不完全決策樹的終止條件時考慮了這一問題，因而算法會在一定程度上避免過擬合現象的發生.

一般訓練數據越多訓練出的模型越復雜，后期出現過擬合的可能性越大.本節實驗通過對比EPPMDT算法、VPPMDT算法和傳統決策樹算法DT在不同規模訓練集下的訓練誤差和測試誤差，進一步分析本文提出算法的抗過擬合能力.訓練集大小設定為初始訓練集的10%到100%，各算法均在最優參數下運行.

圖7 EPPMDT與VPPMDT分類錯誤率比較Fig.7 Comparison of classification error rate for EPPMDT and VPPMDT

因為在所使用的實驗數據集上可以得出類似結論，所以本節以Credit Card Cliet數據集為例，比較幾種算法的抗過擬合性能.圖8給出了不同訓練集規模下，幾種比較算法的訓練誤差和測試誤差比較.從圖中可以看出，兩種誤差相差最大的是DT算法，EPPMDT相關算法的訓練誤差及測試誤差相差相對較小，EPPMDT_SVM(linear)算法表現最好，其次為EPPMDT_LIB，EPPMDT_SVM(rbf)算法雖然表現不如以上兩種模型，但遠好于DT算法，且測試誤差與以上兩種算法相差不多.總體來看，EPPMDT算法在基本保證分類錯誤率的基礎上，均有一定的抗過擬合的能力.

圖8 Credit Card Cliet數據集上EPPMDT和DT抗過擬合性能比較Fig.8 Anti-overfitting performance comparison of EPPMDT and DT on Credit Card Cliet dataset

圖9為在Credit Card Cliet數據集上，VPPMDT相關算法與DT算法抗過擬合性能的比較.結合圖8來看，VPPMDT相關算法的抗過擬合能力比EPPMDT相關算法要更好一些，在VPPMDT相關算法中，抗過擬合能力最強的是VPPMDT_SVM(linear)算法， VPPMDT_LIB算法在訓練集規模小于30%時，訓練誤差和測試誤差較大，但訓練集規模大于30%后，性能很穩定，與VPPMDT_SVM(linear)算法相差不大.類似地，VPPMDT_SVM(rbf)算法的訓練誤差和測試誤差雖然相差較多，但其測試誤差與上述兩種模型相差不多，比DT算法要好得多.另外，模型的抗過擬合能力與可辨識結點使用的簡單分類器有關，本文實驗中，無論是EPPMDT還是VPPMDT，采用SVM(linear)作為分類器性能最好，而且更為穩定.

圖9 Credit Card Cliet數據集上VPPMDT和DT抗過擬合性能比較Fig.9 Anti-overfitting performance comparison of VPPMDT and DT on Credit Card Cliet dataset

4 結 語

本文提出兩種面向不同類型特征值分布的特征值區間劃分方法EPPMDT和VPPMDT，以加速決策樹的構建過程.與MDT算法相比，本文提出的兩種算法可以保證在分類錯誤率相當或更低的前提下加速構建決策樹.另外，本文提出的算法抗過擬合能力表現良好，性能也比較穩定.未來將會重點考慮分布情況比較復雜的數據集，研究更加快速有效的決策樹分類算法.