常 碩，張彥春

（1.復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 200082；2.廣州大學(xué) 網(wǎng)絡(luò)空間先進(jìn)技術(shù)研究院，廣州 510006）

0 概述

隨機(jī)森林具有良好的準(zhǔn)確性和高效性，被認(rèn)為是性能最優(yōu)的分類算法之一。文獻(xiàn)［1］在121 個(gè)數(shù)據(jù)集上對(duì)179 個(gè)分類器進(jìn)行評(píng)估，在所得實(shí)驗(yàn)結(jié)果中隨機(jī)森林表現(xiàn)最好。然而，這121 個(gè)數(shù)據(jù)集中大多數(shù)據(jù)規(guī)模較小，在數(shù)據(jù)規(guī)模較大的數(shù)據(jù)集上，隨機(jī)森林的表現(xiàn)一般不如AdaBoost（Adaptive Boosting）等boost 算法［2］。雖然存在上述問題，但是隨機(jī)森林算法十分簡(jiǎn)單，可并行化，訓(xùn)練時(shí)間遠(yuǎn)低于boost 算法且不容易過擬合［3］，因此，其仍是當(dāng)今最流行的分類算法之一。

文獻(xiàn)［4］通過使用多個(gè)特征評(píng)估度量來降低決策樹間的相關(guān)性而非決策樹的準(zhǔn)確性，同時(shí)使用加權(quán)平均進(jìn)行預(yù)測(cè)，在分類數(shù)據(jù)集上其預(yù)測(cè)結(jié)果較好。文獻(xiàn)［5］通過復(fù)雜的動(dòng)態(tài)集成方法進(jìn)行預(yù)測(cè)，設(shè)計(jì)一種提高隨機(jī)森林在某些數(shù)據(jù)集上預(yù)測(cè)性能的方法，實(shí)驗(yàn)結(jié)果表明，在27 個(gè)分類數(shù)據(jù)集中，該方法能改善12 個(gè)數(shù)據(jù)集中隨機(jī)森林的預(yù)測(cè)表現(xiàn)。文獻(xiàn)［6］在隨機(jī)選擇K個(gè)劃分特征的基礎(chǔ)上，通過隨機(jī)選擇劃分結(jié)點(diǎn)來進(jìn)一步降低決策樹間的相關(guān)性并提高隨機(jī)森林的預(yù)測(cè)表現(xiàn)，實(shí)驗(yàn)結(jié)果表明，在12 個(gè)分類數(shù)據(jù)集中，該方法能夠顯著改善5 個(gè)數(shù)據(jù)集中隨機(jī)森林的預(yù)測(cè)表現(xiàn)。文獻(xiàn)［7］通過袋外（out-of-bag）預(yù)測(cè)誤差對(duì)決策樹的預(yù)測(cè)進(jìn)行加權(quán)，在10 個(gè)噪聲數(shù)據(jù)集上該方法取得了較好的性能表現(xiàn)。文獻(xiàn)［8］提出一種不放回的抽樣方法，其提高了算法效率，并在7 個(gè)數(shù)據(jù)集上提高了預(yù)測(cè)準(zhǔn)確性。文獻(xiàn)［9］提出一種對(duì)特征子集加權(quán)抽樣的方法，該方法提高了與分類相關(guān)的屬性的抽樣概率，在高維數(shù)據(jù)上取得了較好的性能表現(xiàn)。文獻(xiàn)［10］通過PCA（Principle Component Analysis）對(duì)每個(gè)決策樹的輸入特征隨機(jī)分組進(jìn)行旋轉(zhuǎn)預(yù)處理，以降低決策樹間的相關(guān)性并提高隨機(jī)森林的性能，實(shí)驗(yàn)結(jié)果表明，在33 個(gè)分類數(shù)據(jù)集中，該方法能夠顯著改善10 個(gè)數(shù)據(jù)集中隨機(jī)森林的預(yù)測(cè)表現(xiàn)。文獻(xiàn)［11］通 過LDA（Linear Discriminative Analysis）為每個(gè)分裂結(jié)點(diǎn)選擇傾斜的分裂方向，使決策樹的決策邊界傾向坐標(biāo)軸，該方法同樣降低了決策樹間的相關(guān)性，在一些數(shù)據(jù)集上取得了更好的表現(xiàn)。文獻(xiàn)［12］通過Householder QR 分解對(duì)每個(gè)決策樹的輸入特征進(jìn)行隨機(jī)旋轉(zhuǎn)，類似于文獻(xiàn)［10］，其提高了隨機(jī)森林的性能表現(xiàn)。文獻(xiàn)［13］通過在每個(gè)分裂結(jié)點(diǎn)隨機(jī)抽樣一個(gè)稀疏矩陣，利用該矩陣對(duì)結(jié)點(diǎn)的輸入特征進(jìn)行旋轉(zhuǎn)，在旋轉(zhuǎn)后的稀疏特征空間中搜索最佳劃分結(jié)點(diǎn)，該方法提高了隨機(jī)森林的準(zhǔn)確性。文獻(xiàn)［14］通過拓展特征空間的方式，為每個(gè)決策樹的輸入特征隨機(jī)生成部分新特征，其能降低決策樹間的相關(guān)性，且未顯著降低決策樹的準(zhǔn)確性，實(shí)驗(yàn)結(jié)果表明，在36 個(gè)分類數(shù)據(jù)集中，該方法能夠明顯改善8 個(gè)數(shù)據(jù)集中隨機(jī)森林的預(yù)測(cè)表現(xiàn)。

上述方法大多在構(gòu)建決策樹時(shí)通過某些方式注入隨機(jī)性，這會(huì)降低決策樹間的相關(guān)性，從而提高隨機(jī)森林的預(yù)測(cè)表現(xiàn)。在數(shù)據(jù)規(guī)模較大時(shí)，注入隨機(jī)性的方式并不能顯著降低決策樹間的相關(guān)性，同時(shí)又因?yàn)闋奚藳Q策樹的準(zhǔn)確性，使得隨機(jī)森林及其改進(jìn)算法的性能改善效果有限，其預(yù)測(cè)表現(xiàn)一般不如AdaBoost 等boost 算法。因此，本文提出一種基于out-of-bag 預(yù)測(cè)的改進(jìn)算法，將隨機(jī)森林的out-of-bag預(yù)測(cè)概率視為特征，將其與原始特征相結(jié)合，重新訓(xùn)練隨機(jī)森林。out-of-bag 預(yù)測(cè)概率能夠改善決策樹的劃分，有效提高決策樹的準(zhǔn)確性，從而提升隨機(jī)森林的預(yù)測(cè)準(zhǔn)確性。由于out-of-bag 預(yù)測(cè)概率會(huì)增大決策樹間的相關(guān)性，因此本文利用文獻(xiàn)［14］所提方法來降低由out-of-bag 預(yù)測(cè)帶來的決策樹相關(guān)性，且不顯著降低決策樹的準(zhǔn)確性，從而保證隨機(jī)森林的預(yù)測(cè)性能。

1 相關(guān)工作

1.1 隨機(jī)森林

隨機(jī)森林是當(dāng)今最流行的分類器之一［1］，其在bootstrap 的基礎(chǔ)上，通過隨機(jī)選擇特征子集來分裂決策樹的結(jié)點(diǎn)，進(jìn)一步為決策樹注入隨機(jī)性，從而降低決策樹間的相關(guān)性，提高預(yù)測(cè)的準(zhǔn)確性［15］。

對(duì)于數(shù)據(jù)集D=｛（xi，yi），i=1，2，…，m｝，其中，xi和yi分別表示第i個(gè)樣本的特征向量和類別，隨機(jī)森林的訓(xùn)練過程如下（其中，T和k均為預(yù)先設(shè)定好的超參數(shù)）：

t從1 到T：

1）從數(shù)據(jù)集D中有放回地抽樣得到m個(gè)樣本的數(shù)據(jù)集Dt，未被抽樣到的樣本組成數(shù)據(jù)集Dt-oob。

2）在數(shù)據(jù)集Dt上，訓(xùn)練一棵無剪枝的決策樹ft。在訓(xùn)練過程中，對(duì)于決策樹中的每個(gè)結(jié)點(diǎn)，通過隨機(jī)選擇k個(gè)特征來對(duì)結(jié)點(diǎn)進(jìn)行劃分，直到結(jié)點(diǎn)內(nèi)的樣本類別都相同或只有一個(gè)樣本為止。

最終，隨機(jī)森林通過平均所有決策樹的輸出來獲得最終輸出，即：

在抽樣得到的數(shù)據(jù)集Dt中，不重復(fù)的樣本大約占63.2%，剩下大約占36.8%的Dt-oob被稱為out-of-bag樣本。顯然以ft預(yù)測(cè)Dt-oob是無偏的，因此可以用ft對(duì)Dt-oob預(yù)測(cè)的平均結(jié)果作為對(duì)Dt的預(yù)測(cè)。對(duì)于Dt中的樣本x，其預(yù)測(cè)為：

其中：I為指示函數(shù)。

1.2 空間擴(kuò)展

文獻(xiàn)［14］為了降低決策樹間的相關(guān)性，提出一種隨機(jī)組合的特征空間擴(kuò)展方法。對(duì)于每個(gè)決策樹，其輸入特征由特征本身加上特征的隨機(jī)組合，每個(gè)決策樹的輸入特征都不相同，從而降低了決策樹間的相關(guān)性。同時(shí)，由于特征的量綱不同且一些特征間存在相關(guān)性，生成的特征中會(huì)有部分特征對(duì)決策樹的貢獻(xiàn)和原特征相同，甚至表現(xiàn)更好，因此擴(kuò)展空間方法不會(huì)顯著降低決策樹的準(zhǔn)確性。

1.3 AdaBoost

AdaBoost 以其優(yōu)秀的泛化性能而受到學(xué)術(shù)界的關(guān)注［16-17］。AdaBoost 通過確定性的方式更新樣本的權(quán)重，使新的決策樹更加關(guān)注之前分類錯(cuò)誤的樣本，從而提高了最終的泛化能力。AdaBoost 的輸出由T個(gè)決策樹的輸出加權(quán)組成，即：

其中：αt為每輪迭代產(chǎn)生的權(quán)重。

假設(shè)經(jīng)過t-1 輪迭代，F(xiàn)t-1（x）是經(jīng)過t-1 輪迭代得到的結(jié)果模型：

則在第t輪迭代中，需要得到αt、ft（x）和Ft（x）：

為了能夠進(jìn)一步提高泛化性能，需要使Ft（x）在損失函數(shù)L上最小，即聯(lián)合優(yōu)化αt和ft（x）使損失函數(shù)L最?。?/p>

其中：L為度量類別y和模型Ft（x）之間差異的損失函數(shù)。

2 隨機(jī)森林改進(jìn)算法

2.1 改進(jìn)理論

理論1隨機(jī)森林的泛化誤差上界為：

其中：PPE*為泛化誤差為決策樹間相關(guān)系數(shù)的平均；s為單個(gè)決策樹泛化性能的期望［15］。

為了提高隨機(jī)森林的預(yù)測(cè)表現(xiàn)，大多數(shù)改進(jìn)方法通過犧牲單個(gè)決策樹的準(zhǔn)確性來降低決策樹間的相關(guān)性，即以降低s為代價(jià)來降低，從而減小隨機(jī)森林的泛化誤差上界，提高其預(yù)測(cè)表現(xiàn)。這在數(shù)據(jù)規(guī)模較小時(shí)有效，但在數(shù)據(jù)規(guī)模較大時(shí)，決策樹間的相關(guān)性還是較高，泛化誤差不能得到顯著降低，因此，隨機(jī)森林及其改進(jìn)算法性能改善有限。針對(duì)該問題，本文通過提高s而非降低s來提高隨機(jī)森林的預(yù)測(cè)表現(xiàn)。

理論2令T為一個(gè)在有l(wèi)個(gè)實(shí)數(shù)值特征的數(shù)據(jù)的基礎(chǔ)上構(gòu)建的二元決策樹，共有N個(gè)內(nèi)部結(jié)點(diǎn)，則有VC-dimension(T)∈O(Nlb(Nl))［18］。

理論3令H是一組函數(shù)，其取值在｛-1，1｝范圍，其VC-dimension 為d，則對(duì)于任意δ，至少有1-δ的概率，式（8）對(duì)所有h∈H成立。

其中：S為m個(gè)樣本的訓(xùn)練集；R（h）表示泛化風(fēng)險(xiǎn)；(h)表示經(jīng)驗(yàn)風(fēng)險(xiǎn)［19］。

在決策樹的構(gòu)建過程中，同目標(biāo)類別y較相關(guān)的特征會(huì)產(chǎn)生較少的葉子結(jié)點(diǎn)，不太相關(guān)的特征會(huì)產(chǎn)生較多的葉子結(jié)點(diǎn)，而且較相關(guān)的特征產(chǎn)生的葉子結(jié)點(diǎn)能夠得到更小的經(jīng)驗(yàn)風(fēng)險(xiǎn)。如圖1 所示，決策樹在特征x2上只會(huì)產(chǎn)生2 個(gè)葉子結(jié)點(diǎn)，而在特征x1上會(huì)產(chǎn)生8 個(gè)葉子結(jié)點(diǎn)，且特征x2上的經(jīng)驗(yàn)風(fēng)險(xiǎn)明顯小于x1。由于決策樹中只有度為0 和度為2 的結(jié)點(diǎn)，因此決策樹內(nèi)部結(jié)點(diǎn)的數(shù)量N2與葉子結(jié)點(diǎn)的數(shù)量N0的關(guān)系為N2=N0-1。受此啟發(fā)，如果能夠構(gòu)造一些較相關(guān)的特征來幫助構(gòu)建決策樹，那么不僅能夠降低決策樹的經(jīng)驗(yàn)風(fēng)險(xiǎn)，還能降低決策樹的VC-dimension，從而提高決策樹的準(zhǔn)確性。

圖1 特征與目標(biāo)間相關(guān)性的直觀表示Fig.1 Visual representation of the correlation between features and targets

以隨機(jī)森林的out-of-bag 預(yù)測(cè)概率作為特征有以下2 個(gè)優(yōu)點(diǎn)：

1）隨機(jī)森林的準(zhǔn)確率高于單個(gè)決策樹，對(duì)于二分類問題，僅使用預(yù)測(cè)概率就能使決策樹的經(jīng)驗(yàn)風(fēng)險(xiǎn)接近隨機(jī)森林的經(jīng)驗(yàn)風(fēng)險(xiǎn)，對(duì)于多分類問題，預(yù)測(cè)概率也能有效降低決策樹的經(jīng)驗(yàn)風(fēng)險(xiǎn)，同時(shí)有效減少?zèng)Q策樹的內(nèi)部結(jié)點(diǎn)。

2）通過out-of-bag 估計(jì)得到預(yù)測(cè)概率僅需非常小的代價(jià)，在隨機(jī)森林的訓(xùn)練階段即可得到預(yù)測(cè)概率且其是無偏的，而通過交叉預(yù)測(cè)得到預(yù)測(cè)概率不僅十分耗時(shí)，得到的結(jié)果也是有偏的。

以隨機(jī)森林的out-of-bag 預(yù)測(cè)概率作為構(gòu)造的特征，與原始特征相結(jié)合并重新訓(xùn)練隨機(jī)森林，能夠顯著提高單個(gè)決策樹的準(zhǔn)確性s，從而提高隨機(jī)森林的準(zhǔn)確性。但是不可避免的，準(zhǔn)確性的提升會(huì)提高決策樹間的相關(guān)性，即提高了的值，甚至可能大幅提高的值，從而僅能略微提高甚至降低隨機(jī)森林的準(zhǔn)確性。

為了解決上述問題，本文通過文獻(xiàn)［14］提出的擴(kuò)展空間算法，使隨機(jī)森林中的每個(gè)決策樹構(gòu)建在不同的訓(xùn)練數(shù)據(jù)上，從而在不顯著降低決策樹準(zhǔn)確性s的情況下，降低決策樹間的相關(guān)性。

2.2 改進(jìn)算法描述

本文利用out-of-bag 預(yù)測(cè)概率作為新的特征來構(gòu)建決策樹，從而降低決策樹的VC-dimension 以及經(jīng)驗(yàn)風(fēng)險(xiǎn)和泛化風(fēng)險(xiǎn)，最終提高決策樹的準(zhǔn)確性s和隨機(jī)森林的預(yù)測(cè)性能?；趏ut-of-bag 預(yù)測(cè)的改進(jìn)算法描述如下所示：

為了深入了解2018年高考中數(shù)學(xué)學(xué)科核心素養(yǎng)的考查情況，下面以全國(guó)I卷試題為例，基于《普通高中數(shù)學(xué)課程標(biāo)準(zhǔn)（2017年版）》中對(duì)數(shù)學(xué)學(xué)科核心素養(yǎng)的界定和水平劃分，參考喻平的“核心素養(yǎng)評(píng)價(jià)框架”[17]，對(duì)高考數(shù)學(xué)試題素養(yǎng)考查情況作出分析．

算法1基于out-of-bag 預(yù)測(cè)的改進(jìn)算法

由于決策樹準(zhǔn)確性s的提高，會(huì)使決策樹間的預(yù)測(cè)更加相同，從而提高決策樹間的相關(guān)性，影響了算法1 對(duì)隨機(jī)森林的改善效果。為此，本文通過文獻(xiàn)［14］提出的擴(kuò)展空間算法，對(duì)算法1 進(jìn)行改進(jìn)，改進(jìn)算法描述如下：

算法2基于out-of-bag 預(yù)測(cè)和擴(kuò)展空間的改進(jìn)算法1

算法3擴(kuò)展特征空間算法E

算法3 即為文獻(xiàn)［14］提出的擴(kuò)展特征空間算法，本文使用文獻(xiàn)［14］中表現(xiàn)最好的相減操作。擴(kuò)展空間算法等價(jià)于通過以2 個(gè)特征為1 組的方式，將n個(gè)特征隨機(jī)劃分為組，從而生成個(gè)特征，該過程可以產(chǎn)生許多不同的劃分，其總量為：

其中：K=。例如，當(dāng)n=10 時(shí)，K=5，M=945。算法3 為使生成的特征數(shù)量為n，對(duì)其做了2 次上述操作，在n為奇數(shù)時(shí)，將2 次操作各自多出的1 個(gè)特征劃分為1 組，從而生成n個(gè)特征。

在算法1 和算法2 的訓(xùn)練過程中，out-of-bag 預(yù)測(cè)概率的準(zhǔn)確性越高，對(duì)隨機(jī)森林的提升效果就越好。out-of-bag 預(yù)測(cè)雖然是無偏的，但對(duì)于其中的每個(gè)樣本，大約只有37.8%的決策樹會(huì)對(duì)其作出預(yù)測(cè)。相比于測(cè)試集的全部決策樹預(yù)測(cè)，兩者之間的準(zhǔn)確性會(huì)有所差異。為了降低這部分差異，本文將算法1和算法2 產(chǎn)生的out-of-bag 預(yù)測(cè)概率相結(jié)合，通過加法融合來提高out-of-bag 預(yù)測(cè)概率的準(zhǔn)確性，減少其與測(cè)試集預(yù)測(cè)之間的差異。上述過程的算法描述如下：

算法4基于out-of-bag 預(yù)測(cè)和擴(kuò)展空間的改進(jìn)算法2

算法4 相比算法2 又需要額外訓(xùn)練一個(gè)隨機(jī)森林，其時(shí)間復(fù)雜度為，該隨機(jī)森林就是文獻(xiàn)［14］中的擴(kuò)展空間隨機(jī)森林。通過再額外訓(xùn)練一個(gè)隨機(jī)森林，將得到的預(yù)測(cè)概率分別同原隨機(jī)森林的預(yù)測(cè)概率做平均，能夠提高out-of-bag 預(yù)測(cè)的準(zhǔn)確性，減少其與測(cè)試集預(yù)測(cè)之間的差異，從而進(jìn)一步提高隨機(jī)森林的預(yù)測(cè)表現(xiàn)。

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

3.1 數(shù)據(jù)集

本文收集32 個(gè)分類數(shù)據(jù)集，這些數(shù)據(jù)集全都來自UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫［20］，數(shù)據(jù)集的統(tǒng)計(jì)特性如表1所示。其中：Nint 表示樣本的數(shù)量；Nnum 表示數(shù)值特征數(shù)量；Ncat 表示類別特征數(shù)量；Ncls 表示類別數(shù)量。這些數(shù)據(jù)集的樣本數(shù)量在329～67 557 之間，特征數(shù)量在4～90 之間，類別數(shù)量在2～26 之間。每個(gè)數(shù)據(jù)集都只含數(shù)值特征或類別特征，表中的“—”表示沒有該類型的特征。有些數(shù)據(jù)集存在缺失值，需要對(duì)其進(jìn)行填充：對(duì)于類別特征的缺失，本文使用最常見的特征值對(duì)其進(jìn)行填充；對(duì)于數(shù)值特征的缺失，本文使用文獻(xiàn)［21］提出的序列回歸填充方法對(duì)其進(jìn)行填充。

表1 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息Table 1 Experimental datasets statistics

3.2 模型選擇和超參數(shù)搜索

本文以RF 表示原始隨機(jī)森林，以oRF 表示算法1 改進(jìn)的隨機(jī)森林，以eRF 表示文獻(xiàn)［14］提出的擴(kuò)展隨機(jī)森林，以oeRF 表示算法2 改進(jìn)的隨機(jī)森林，以oe2RF 表示算法4 改進(jìn)的隨機(jī)森林。同時(shí)還將本文算法與AdaBoost 類算法，具體為文獻(xiàn)［22］提出的Multi-AdaBoost 算法（以BT 表示）進(jìn)行對(duì)比。

對(duì)于超參數(shù)，由于隨機(jī)森林和AdaBoost 都是樹模型，本文將兩者的決策樹數(shù)量都設(shè)為100，只調(diào)整決策樹的深度，以5 折交叉驗(yàn)證網(wǎng)格搜索的方式選擇最佳的樹深。上述模型均使用文獻(xiàn)［23］中的scikit-learn 機(jī)器學(xué)習(xí)庫。

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

4.1 實(shí)驗(yàn)度量

本文使用準(zhǔn)確率（acc）作為模型性能的評(píng)估度量。除此之外，由于隨機(jī)森林的性能與s、有關(guān)，即與單個(gè)決策樹的準(zhǔn)確性和決策樹之間的相關(guān)性有關(guān)，而單個(gè)決策樹的準(zhǔn)確性又與決策樹的經(jīng)驗(yàn)風(fēng)險(xiǎn)、VC-dimension 有關(guān)，因此，本文還使用如下度量：

1）決策樹準(zhǔn)確率的平均值（atc）。以單個(gè)決策樹對(duì)測(cè)試集預(yù)測(cè)準(zhǔn)確率的平均來表示單個(gè)決策樹的準(zhǔn)確性。

2）決策樹kappa 的平均值（kapp）。文獻(xiàn)［24］以kappa 值來度量2 個(gè)分類器預(yù)測(cè)之間的一致性，顯然其還可以用來度量決策樹間的相關(guān)性。對(duì)于c個(gè)類，kappa 定義在2 個(gè)分類器預(yù)測(cè)的c×c混淆矩陣M上［10］。以N表示樣本的總數(shù)量，則2 個(gè)分類器之間的kappa 值為：

其中：Mks表示其中一個(gè)分類器預(yù)測(cè)樣本為k而另一個(gè)分類器預(yù)測(cè)樣本為s的數(shù)量。在隨機(jī)森林中共有T個(gè)決策樹，因此，需要度量T（T-1）/2 次kappa 的值并對(duì)其做平均。

3）決策樹out-of-bag 準(zhǔn)確率的平均值（abc）。以單個(gè)決策樹對(duì)out-of-bag 樣本預(yù)測(cè)準(zhǔn)確率的平均來近似表示決策樹的經(jīng)驗(yàn)風(fēng)險(xiǎn)。

4）決策樹中葉子結(jié)點(diǎn)數(shù)量的平均值（node）。由理論2 可知，決策樹的VC-dimension 與實(shí)值特征數(shù)量、內(nèi)部結(jié)點(diǎn)數(shù)量有關(guān)，但實(shí)值特征數(shù)量要經(jīng)過log處理，因此，決策樹的VC-dimension 主要受內(nèi)部結(jié)點(diǎn)數(shù)量影響，而決策樹內(nèi)部結(jié)點(diǎn)數(shù)量又與葉子結(jié)點(diǎn)數(shù)量有關(guān)，因此，本文以決策樹葉子結(jié)點(diǎn)數(shù)量來近似表示決策樹的VC-dimension。

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

本文隨機(jī)地將80%的樣本劃分為訓(xùn)練集，將剩下的20%樣本劃分為測(cè)試集。由于數(shù)據(jù)集規(guī)模的不同，該劃分過程重復(fù)的次數(shù)也不同。對(duì)于樣本數(shù)量小于1 500 的數(shù)據(jù)集，該劃分重復(fù)30 次；對(duì)于樣本數(shù)量大于等于1 500 而小于8 000 的數(shù)據(jù)集，該劃分重復(fù)20 次；對(duì)于樣本數(shù)量大于等于8 000 的數(shù)據(jù)集，該劃分重復(fù)10 次。本文使用校正的paired t-test 對(duì)實(shí)驗(yàn)結(jié)果做顯著性檢驗(yàn)［25］。對(duì)于2 個(gè)不同的數(shù)據(jù)集劃分，2 個(gè)訓(xùn)練集之間至少有75%的部分相同，容易出現(xiàn)Type I 類錯(cuò)誤［26］。因此，本文使用校正的paired ttest，將顯著性水平設(shè)為95%。

實(shí)驗(yàn)結(jié)果如表2 所示，其中，加粗表示該模型的預(yù)測(cè)acc 最高，下劃線表示該模型的預(yù)測(cè)結(jié)果顯著優(yōu)于RF，“×”表示該模型的預(yù)測(cè)結(jié)果顯著劣于RF，表格倒數(shù)第3 行表示模型的平均acc，倒數(shù)第2 行表示模型的平均rank，倒數(shù)第1 行表示模型相較于RF 的顯著性win-tie-loss 記錄。從表2 可以看出，本文方法和文獻(xiàn)［14］方法都能提高RF 的預(yù)測(cè)性能，其中表現(xiàn)最好的是本文提出的oe2RF 模型，在32 個(gè)數(shù)據(jù)集中，oe2RF 能夠獲得最高的平均acc 以及最低的平均rank，能夠在19 個(gè)數(shù)據(jù)集上顯著優(yōu)于RF。

表2 模型預(yù)測(cè)性能比較Table 2 Comparison of prediction performance of models

本文還對(duì)比了oe2RF 與RF、BT 的性能差異，對(duì)比結(jié)果如圖2 所示。從圖2 可以看出，BT 性能優(yōu)于RF，而oe2RF 能獲得比BT 更優(yōu)的性能表現(xiàn)。

圖2 oe2RF 與RF、BT 的性能對(duì)比Fig.2 Performance comparison of oe2RF with RF and BT

各模型的平均訓(xùn)練時(shí)間如表3 所示，其中訓(xùn)練時(shí)間指各模型最終額外訓(xùn)練的隨機(jī)森林的訓(xùn)練時(shí)間，總訓(xùn)練時(shí)間可由表中數(shù)據(jù)相加得到。例如，oRF總訓(xùn)練時(shí)間=RF 訓(xùn)練時(shí)間+oRF 訓(xùn)練時(shí)間，eRF 總訓(xùn)練時(shí)間=eRF 訓(xùn)練時(shí)間。顯然，各個(gè)模型最終額外的訓(xùn)練時(shí)間開銷大致符合2.2 節(jié)中額外訓(xùn)練的隨機(jī)森林的算法時(shí)間復(fù)雜度分析，其中部分波動(dòng)是由于：1）out-of-bag 預(yù)測(cè)有效減少了決策樹中葉子結(jié)點(diǎn)的數(shù)量，這會(huì)降低訓(xùn)練時(shí)間，例如，在ID 為10 和21 的數(shù)據(jù)集上，oRF 的訓(xùn)練時(shí)間小于RF；2）在擴(kuò)展特征空間時(shí)，每次生成n個(gè)特征需要時(shí)間復(fù)雜度為O（mn）的時(shí)間開銷，這會(huì)提高訓(xùn)練時(shí)間，例如，在ID 為26 和32 的數(shù)據(jù)集上，由于2 個(gè)數(shù)據(jù)集的特征均為類別特征，訓(xùn)練時(shí)需要對(duì)其進(jìn)行one-hot 編碼，編碼后的特征數(shù)量較多，對(duì)其進(jìn)行空間擴(kuò)展會(huì)帶來較多的額外時(shí)間開銷。

表3 模型平均訓(xùn)練時(shí)間Table 3 Models average training time s

4.3 結(jié)果分析

本文方法對(duì)RF 的性能提升在于提高了單個(gè)決策樹的準(zhǔn)確性，同時(shí)由于提高決策樹的準(zhǔn)確性會(huì)使決策樹間的相關(guān)性提高，因此本文借助文獻(xiàn)［14］方法降低決策樹間的相關(guān)性，且不顯著降低決策樹的準(zhǔn)確性，從而較好地改善了RF 的預(yù)測(cè)性能。

如圖3 所示，圖中的每個(gè)點(diǎn)代表一個(gè)數(shù)據(jù)集，橫坐標(biāo)表示各模型與RF 在kapp 上的差異，縱坐標(biāo)表示各模型與RF 在atc 上的差異。從圖3 可以看出：oRF 能夠大幅提高決策樹的atc，但也會(huì)大幅提高決策樹間的kapp；eRF 能夠在不顯著降低決策樹atc的情況下降低決策樹間的kapp，圖中部分atc 和kapp 提高的原因在于劃分結(jié)點(diǎn)時(shí)特征子集的選擇正比于特征數(shù)量，如果將特征子集數(shù)量設(shè)為固定值，將不會(huì)出現(xiàn)該情況；oeRF 相比于oRF 降低了kapp，也降低了atc，但相比于RF 的kapp 和atc 提高了很多；oe2RF 相比于oeRF 提高了atc，略微提高了kapp，因此，其能夠獲得最好的性能表現(xiàn)。由圖3可知，本文方法能大幅提高單個(gè)決策樹的準(zhǔn)確性，符合理論2 和理論3，其實(shí)驗(yàn)驗(yàn)證如圖4 所示，橫坐標(biāo)表示各模型與RF 在node 上的差異，縱坐標(biāo)表示各模型與RF在abc 上的差異。從圖4 可以看出：oRF、oeRF 和oe2RF均能大幅提高決策樹的abc，且同時(shí)降低決策樹的node，從而提高了決策樹的atc；eRF略微提高了決策樹的abc，同時(shí)降低了決策樹的node，其原因在于特征子集正比于特征數(shù)量，而且特征量綱的不同和特征間存在相關(guān)性，擴(kuò)展特征空間時(shí)可能會(huì)產(chǎn)生部分較好的特征，有利于決策樹劃分，在固定特征子集大小時(shí)，這種情況很少發(fā)生。

圖3 各模型與RF 在atc 和kapp 上的性能差異Fig.3 Performance difference between each model and RF on atc and kapp

圖4 各模型與RF 在決策樹abc 和node 上的性能差異Fig.4 Performance difference between each model and RF on decision tree abc and node

5 結(jié)束語

多數(shù)已有預(yù)測(cè)方法犧牲單個(gè)決策樹的準(zhǔn)確性來提高隨機(jī)森林的性能，本文通過out-of-bag 預(yù)測(cè)概率提高單個(gè)決策樹的準(zhǔn)確性，同時(shí)利用文獻(xiàn)［14］所提擴(kuò)展空間方法降低決策樹間的相關(guān)性，以有效改善隨機(jī)森林的預(yù)測(cè)性能。在32 個(gè)UCI 分類數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的有效性。后續(xù)將進(jìn)一步提升決策樹的準(zhǔn)確性，同時(shí)利用數(shù)據(jù)旋轉(zhuǎn)技術(shù)來降低決策樹間的相關(guān)性，從而提高隨機(jī)森林的準(zhǔn)確性。