一種特征值區(qū)間劃分的模型決策樹(shù)加速算法

高虹雷，門(mén)昌騫，王文劍,2

1(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006)2(山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006)

E-mail：wjwang@sxu.edu.cn

1 引 言

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

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

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

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

本文在文獻(xiàn)[21]基礎(chǔ)上提出一種基于特征值區(qū)間劃分的模型決策樹(shù)加速算法，算法根據(jù)數(shù)據(jù)的不同分布給出兩種特征值區(qū)間的分割方法，通過(guò)計(jì)算各選定區(qū)間的基尼指數(shù)，尋找最優(yōu)特征及最優(yōu)切分點(diǎn)，最后遞歸生成模型決策樹(shù).所提出的算法可在保證分類(lèi)精度的前提下加快決策樹(shù)的構(gòu)建.

2 基于特征值區(qū)間劃分的模型決策樹(shù)加速算法

2.1 特征值區(qū)間劃分

模型決策樹(shù)[21]在處理二分類(lèi)問(wèn)題時(shí)通過(guò)對(duì)每一特征維度上的所有特征值分別計(jì)算其Gini指數(shù)并以此逐層構(gòu)建二叉樹(shù)，直到樹(shù)深度或葉子節(jié)點(diǎn)滿足某一條件時(shí)停止，此時(shí)構(gòu)建的二叉決策樹(shù)可以較好地對(duì)數(shù)據(jù)進(jìn)行分類(lèi)，但當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，用全部樣本每一特征維度上所有取值來(lái)構(gòu)建決策樹(shù)會(huì)耗費(fèi)大量的時(shí)間及計(jì)算資源.本文提出兩種面向不同類(lèi)型特征值分布的特征值區(qū)間劃分方法，用以加速?zèng)Q策樹(shù)的構(gòu)建過(guò)程.

2.1.1 等精度特征值區(qū)間劃分

當(dāng)數(shù)據(jù)集中所有樣本每一特征維度上取值分布較為均勻時(shí)，特征取值差異較小，此時(shí)將特征取值劃分為多個(gè)等精度區(qū)間并用每一區(qū)間所含特征值的平均值代表各區(qū)間的值，之后對(duì)每一區(qū)間平均值計(jì)算其Gini指數(shù)進(jìn)而構(gòu)建決策樹(shù)，此時(shí)決策樹(shù)構(gòu)建所需時(shí)間及計(jì)算代價(jià)將大大降低.等精度特征值區(qū)間劃分的詳細(xì)過(guò)程如下.

…

之后計(jì)算每一區(qū)間特征取值平均值：

…

此時(shí)等精度特征值區(qū)間劃分完成.圖1是在Magic Gamma Telescope數(shù)據(jù)集(說(shuō)明見(jiàn)表1)上進(jìn)行等精度特征值區(qū)間劃分的結(jié)果，在數(shù)據(jù)集中隨機(jī)挑選一個(gè)特征，利用等精度特征值區(qū)間劃分方法將其劃分成10個(gè)區(qū)間，每個(gè)區(qū)間樣本個(gè)數(shù)為902個(gè)，各分裂結(jié)點(diǎn)的位置即各區(qū)間內(nèi)包含的所有樣本特征值的平均值.

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

2.1.2 變精度特征值區(qū)間劃分

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

…

統(tǒng)計(jì)每一區(qū)間中包含的樣本數(shù)，對(duì)于樣本數(shù)小于給定閾值N*的區(qū)間，計(jì)算該區(qū)間內(nèi)所包含特征取值的平均值，此時(shí)變精度特征值區(qū)間劃分完成.圖2是在Cod_rna數(shù)據(jù)集(說(shuō)明見(jiàn)表1)上進(jìn)行變精度特征值區(qū)間劃分的結(jié)果.在數(shù)據(jù)集中隨機(jī)挑選一個(gè)特征，利用變精度特征值區(qū)間劃分方法將其劃分成20個(gè)區(qū)間，各樣本點(diǎn)依據(jù)特征值的大小落入不同區(qū)間內(nèi)，如給定閾值N*等于400，各分裂結(jié)點(diǎn)的位置就是樣本數(shù)小于400的區(qū)間內(nèi)所包含的所有樣本特征值的平均值.

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

2.2 尋找最優(yōu)特征及最優(yōu)切分點(diǎn)

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

在分類(lèi)問(wèn)題中，設(shè)給定的訓(xùn)練數(shù)據(jù)集為D，其樣本個(gè)數(shù)為|D|，假設(shè)有K個(gè)類(lèi)，Ck表示D中屬于第k類(lèi)的樣本子集，k=1，2，…，K，|Ck|表示屬于Ck類(lèi)樣本的個(gè)數(shù).定義樣本點(diǎn)屬于第k類(lèi)的概率為Pk，則該數(shù)據(jù)集在概率分布P下的Gini指數(shù):

(1)

給定訓(xùn)練數(shù)據(jù)集D的Gini指數(shù)為：

(2)

對(duì)于二分類(lèi)問(wèn)題，若要在訓(xùn)練集D中根據(jù)特征A的某一個(gè)取值a來(lái)計(jì)算基尼指數(shù)，則訓(xùn)練集D被劃分為D1和D2兩部分：

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

(3)

訓(xùn)練集D在特征A的條件下，Gini指數(shù)定義為：

(4)

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

2.3 模型決策樹(shù)加速算法

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

EPPMDT算法

輸入：訓(xùn)練數(shù)據(jù)集D，測(cè)試數(shù)據(jù)集S，劃分區(qū)間數(shù)Z，可辨識(shí)結(jié)點(diǎn)中樣本個(gè)數(shù)閾值V

輸出：EPPMDT決策樹(shù)

Step 1.對(duì)于訓(xùn)練數(shù)據(jù)集D，根據(jù)等精度特征值區(qū)間劃分方法將每維特征下的特征值劃分成H0,H1,…,Hz-1個(gè)區(qū)間，計(jì)算各區(qū)間特征取值的平均值M0,M1,…,Mz-1，將其作為當(dāng)前需要分裂結(jié)點(diǎn)上每一特征對(duì)應(yīng)的可能取值；

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

Step 3.對(duì)劃分之后得到的兩個(gè)子結(jié)點(diǎn)遞歸調(diào)用Step 1和Step 2，直至可辨識(shí)結(jié)點(diǎn)中樣本個(gè)數(shù)小于閾值V，這時(shí)中止決策樹(shù)的生長(zhǎng)；

Step 4.在所得到的可辨識(shí)結(jié)點(diǎn)上搭載分類(lèi)器，生成等精度特征值區(qū)間劃分的模型決策樹(shù)；

Step 5.算法結(jié)束.

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

VPPMDT算法

輸入：訓(xùn)練數(shù)據(jù)集D，測(cè)試數(shù)據(jù)集S，劃分區(qū)間數(shù)Z，區(qū)間中樣本個(gè)數(shù)閾值N*，可辨識(shí)結(jié)點(diǎn)中樣本個(gè)數(shù)閾值V

輸出：VPPMDT決策樹(shù)

Step 1.設(shè)根結(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為D，根據(jù)變精度特征值區(qū)間劃分方法將每維特征下的特征值劃分成H0,H1,…,Hz-1個(gè)區(qū)間，計(jì)算樣本數(shù)小于給定閾值N*的區(qū)間內(nèi)所包含的特征取值的平均值，將其作為當(dāng)前需要分裂結(jié)點(diǎn)上每一特征對(duì)應(yīng)的可能取值；

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

Step 3.對(duì)劃分之后得到的兩個(gè)子結(jié)點(diǎn)遞歸調(diào)用Step 1和Step 2，直至可辨識(shí)結(jié)點(diǎn)中樣本個(gè)數(shù)小于閾值V，中止決策樹(shù)的生長(zhǎng)；

Step 4.在所得到的可辨識(shí)結(jié)點(diǎn)上搭載分類(lèi)器，生成變精度特征值區(qū)間劃分的模型決策樹(shù)；

Step 5.算法結(jié)束.

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

3.1 實(shí)驗(yàn)設(shè)置及實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)使用UCI數(shù)據(jù)集中的9個(gè)典型二分類(lèi)數(shù)據(jù)集進(jìn)行測(cè)試，如表1所示.為消除實(shí)驗(yàn)的隨機(jī)性，每種算法在每個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果為運(yùn)行20次結(jié)果的均值.

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Datasets used in experiments

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

本實(shí)驗(yàn)首先將訓(xùn)練數(shù)據(jù)集按4∶1的比例隨機(jī)均勻抽樣得到驗(yàn)證集，通過(guò)實(shí)驗(yàn)得到對(duì)應(yīng)的最優(yōu)參數(shù).實(shí)驗(yàn)中可辨識(shí)結(jié)點(diǎn)樣本個(gè)數(shù)閾值V、LIBLINEAR中的類(lèi)型參數(shù)以及SVM中懲罰參數(shù)、高斯核參數(shù)均為不同實(shí)驗(yàn)數(shù)據(jù)集下在驗(yàn)證集上得到的最優(yōu)參數(shù).因部分?jǐn)?shù)據(jù)集訓(xùn)練樣本數(shù)較少，為保證合理劃分區(qū)間，EPPMDT 3種模型算法在Madelon數(shù)據(jù)集上可辨識(shí)結(jié)點(diǎn)規(guī)模V取訓(xùn)練樣本數(shù)的20%，VPPMDT 3種模型算法在Germen、Spambase和 Credit Card Cliet數(shù)據(jù)集上V取訓(xùn)練樣本數(shù)的30%，其余算法中V均為訓(xùn)練樣本數(shù)的10%.使用LIBLINEAR模型的算法類(lèi)型參數(shù)S取2，使用線性核SVM模型和高斯核SVM模型算法中的懲罰參數(shù)C除在Credit Card Cliet、Magic Gamma Telescope和Cod_rna數(shù)據(jù)集中為1以外，其余均為50，使用高斯核SVM模型算法中的高斯核參數(shù)γ除在Credit Card Cliet、Magic Gamma Telescope和Cod_rna數(shù)據(jù)集中為0.5，其余均為1.

3.2 EPPMDT和VPPMDT算法的參數(shù)實(shí)驗(yàn)設(shè)置

劃分區(qū)間數(shù)Z這一參數(shù)對(duì)EPPMDT算法和VPPMDT算法都有影響，除此之外，VPPMDT算法還受區(qū)間中樣本個(gè)數(shù)閾值N*的影響.

3.2.1 EPPMDT算法中劃分區(qū)間數(shù)Z的設(shè)置

模型的分類(lèi)錯(cuò)誤率及運(yùn)行時(shí)間在不同的劃分區(qū)間數(shù)下會(huì)有所不同，因此，在不同數(shù)據(jù)集下找到最優(yōu)的劃分區(qū)間個(gè)數(shù)至關(guān)重要.本文通過(guò)實(shí)驗(yàn)獲得各數(shù)據(jù)集上劃分區(qū)間數(shù)Z的較優(yōu)值，對(duì)于不同數(shù)據(jù)集，通過(guò)實(shí)驗(yàn)設(shè)置的參數(shù)如表2所示.

表2 EPPMDT算法參數(shù)設(shè)置Table 2 Parameter setting of EPPMDT

3.2.2 VPPMDT算法中劃分區(qū)間數(shù)Z及樣本個(gè)數(shù)閾值N*的設(shè)置

在VPPMDT算法中，劃分區(qū)間數(shù)Z以及區(qū)間中樣本個(gè)數(shù)閾值N*均會(huì)影響算法的分類(lèi)錯(cuò)誤率及運(yùn)行時(shí)間，因此，本節(jié)也是通過(guò)實(shí)驗(yàn)在不同數(shù)據(jù)集下設(shè)置較優(yōu)的Z和N*.對(duì)于不同數(shù)據(jù)集，通過(guò)實(shí)驗(yàn)設(shè)置的參數(shù)如表3所示.

表3 VPPMDT算法參數(shù)設(shè)置Table 3 Parameter setting of VPPMDT

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

本節(jié)將本文提出的兩種算法模型EPPMDT和VPPMDT分別與文獻(xiàn)[21]中的MDT算法進(jìn)行分類(lèi)性能及運(yùn)行時(shí)間的比較.MDT算法的實(shí)驗(yàn)結(jié)果來(lái)自于文獻(xiàn)[21].

本文提出的EPPMDT算法3種模型的分類(lèi)性能及運(yùn)行時(shí)間的實(shí)驗(yàn)結(jié)果見(jiàn)表4和表5.由表4和表5可知，EPPMDT_LIB算法和EPPMDT_SVM(linear)算法在相同數(shù)據(jù)集下的分類(lèi)錯(cuò)誤率及運(yùn)行時(shí)間均相似，因?yàn)槠湓诳杀孀R(shí)結(jié)點(diǎn)上使用的均為線性分類(lèi)器，但EPPMDT_LIB算法在運(yùn)行時(shí)間上還是要比EPPMDT_SVM(linear)算法快，因?yàn)長(zhǎng)IBLINEAR模型主要還是面向于大規(guī)模數(shù)據(jù)集的，分類(lèi)速度會(huì)更快一些.另外，當(dāng)數(shù)據(jù)集規(guī)模相對(duì)較大時(shí)，如數(shù)據(jù)集Credit Card Cliet、Magic Gamma Telescope，EPPMDT算法提速更為明顯.

表4 不同算法下分類(lèi)性能比較結(jié)果Table 4 Comparison results of classification performance under different algorithms

表5 不同算法下運(yùn)行時(shí)間比較結(jié)果Table 5 Comparison results of running time under different algorithms

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

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

圖3 EPPMDT與MDT分類(lèi)錯(cuò)誤率比較Fig.3 Comparison of classification error rate forEPPMDT and MDT

圖4 EPPMDT對(duì)MDT的加速結(jié)果Fig.4 Accelerating results of EPPMDT on MDT

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

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

圖5 VPPMDT與MDT分類(lèi)錯(cuò)誤率比較Fig.5 Comparison of classification error rate forVPPMDT and MDT

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

圖6 VPPMDT對(duì)MDT的加速結(jié)果Fig.6 Accelerating results of VPPMDT on MDT

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

3.4 EPPMDT算法與VPPMDT算法結(jié)果比較

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

3.5 算法抗過(guò)擬合性分析

在傳統(tǒng)決策樹(shù)算法中，過(guò)擬合現(xiàn)象一直都是普遍存在的一個(gè)問(wèn)題.由于決策樹(shù)過(guò)度生長(zhǎng)，導(dǎo)致葉節(jié)點(diǎn)樣本基本都是“純”的，雖然對(duì)于訓(xùn)練集分類(lèi)效果很好但在測(cè)試集上的分類(lèi)效果并不理想.本文提出的EPPMDT算法及VPPMDT算法，在區(qū)間劃分的過(guò)程和生成一顆不完全決策樹(shù)的終止條件時(shí)考慮了這一問(wèn)題，因而算法會(huì)在一定程度上避免過(guò)擬合現(xiàn)象的發(fā)生.

一般訓(xùn)練數(shù)據(jù)越多訓(xùn)練出的模型越復(fù)雜，后期出現(xiàn)過(guò)擬合的可能性越大.本節(jié)實(shí)驗(yàn)通過(guò)對(duì)比EPPMDT算法、VPPMDT算法和傳統(tǒng)決策樹(shù)算法DT在不同規(guī)模訓(xùn)練集下的訓(xùn)練誤差和測(cè)試誤差，進(jìn)一步分析本文提出算法的抗過(guò)擬合能力.訓(xùn)練集大小設(shè)定為初始訓(xùn)練集的10%到100%，各算法均在最優(yōu)參數(shù)下運(yùn)行.

圖7 EPPMDT與VPPMDT分類(lèi)錯(cuò)誤率比較Fig.7 Comparison of classification error rate for EPPMDT and VPPMDT

因?yàn)樵谒褂玫膶?shí)驗(yàn)數(shù)據(jù)集上可以得出類(lèi)似結(jié)論，所以本節(jié)以Credit Card Cliet數(shù)據(jù)集為例，比較幾種算法的抗過(guò)擬合性能.圖8給出了不同訓(xùn)練集規(guī)模下，幾種比較算法的訓(xùn)練誤差和測(cè)試誤差比較.從圖中可以看出，兩種誤差相差最大的是DT算法，EPPMDT相關(guān)算法的訓(xùn)練誤差及測(cè)試誤差相差相對(duì)較小，EPPMDT_SVM(linear)算法表現(xiàn)最好，其次為EPPMDT_LIB，EPPMDT_SVM(rbf)算法雖然表現(xiàn)不如以上兩種模型，但遠(yuǎn)好于DT算法，且測(cè)試誤差與以上兩種算法相差不多.總體來(lái)看，EPPMDT算法在基本保證分類(lèi)錯(cuò)誤率的基礎(chǔ)上，均有一定的抗過(guò)擬合的能力.

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

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

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

4 結(jié) 語(yǔ)

本文提出兩種面向不同類(lèi)型特征值分布的特征值區(qū)間劃分方法EPPMDT和VPPMDT，以加速?zèng)Q策樹(shù)的構(gòu)建過(guò)程.與MDT算法相比，本文提出的兩種算法可以保證在分類(lèi)錯(cuò)誤率相當(dāng)或更低的前提下加速構(gòu)建決策樹(shù).另外，本文提出的算法抗過(guò)擬合能力表現(xiàn)良好，性能也比較穩(wěn)定.未來(lái)將會(huì)重點(diǎn)考慮分布情況比較復(fù)雜的數(shù)據(jù)集，研究更加快速有效的決策樹(shù)分類(lèi)算法.