基于空間變換的隨機(jī)森林算法

關(guān)曉薔 王文劍,2 龐繼芳 孟銀鳳

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

互聯(lián)網(wǎng)、大數(shù)據(jù)、云計(jì)算與物聯(lián)網(wǎng)等信息技術(shù)的快速發(fā)展和深度融合對(duì)機(jī)器學(xué)習(xí)提出了新的挑戰(zhàn)，如何對(duì)收集到的大量信息進(jìn)行快速準(zhǔn)確分類(lèi)，以便獲取有價(jià)值的知識(shí)，成為當(dāng)前機(jī)器學(xué)習(xí)領(lǐng)域關(guān)注的焦點(diǎn)之一.常用的分類(lèi)算法有隨機(jī)森林(random forest, RF)[1]、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)等.其中，隨機(jī)森林憑借其預(yù)測(cè)準(zhǔn)確度高、抗噪能力強(qiáng)、能夠處理高維數(shù)據(jù)、容易實(shí)現(xiàn)并行化等優(yōu)勢(shì)，在行為識(shí)別[2]、入侵檢測(cè)[3]、醫(yī)學(xué)研究[4]、圖像處理[5]、文本分類(lèi)[6]、情感識(shí)別[7]等實(shí)際問(wèn)題中得到了廣泛的應(yīng)用.

隨機(jī)森林是Breiman在2001年提出的一種機(jī)器學(xué)習(xí)算法[1].該算法在以決策樹(shù)[8-9]為基分類(lèi)器構(gòu)建Bagging[10]集成的基礎(chǔ)上，引入了訓(xùn)練數(shù)據(jù)集隨機(jī)化[11]和屬性集隨機(jī)化這2種隨機(jī)性，使得隨機(jī)森林不易陷入過(guò)擬合，且具有很好的抗噪能力.Fernandez-Delgado等人[12]對(duì)179種分類(lèi)算法在121個(gè)UCI數(shù)據(jù)集上的分類(lèi)性能進(jìn)行了實(shí)驗(yàn)分析，結(jié)果表明隨機(jī)森林是這179種分類(lèi)算法中表現(xiàn)最好的.由于隨機(jī)森林容易實(shí)現(xiàn)且性能優(yōu)越，近年來(lái)受到了學(xué)者們的廣泛關(guān)注[13-14].Abellán等人[15]將非精確信息增益作為屬性選擇的標(biāo)準(zhǔn)，建立了基于非精確概率理論的隨機(jī)森林算法(credal random forest, CRF).Wang等人[16]使用2個(gè)獨(dú)立的伯努利分布來(lái)簡(jiǎn)化決策樹(shù)的構(gòu)建，從而提出了伯努利隨機(jī)森林(Bernoulli random forest, BRF).Quadrianto等人[17]提出一種Safe-Bayesian隨機(jī)森林來(lái)提高隨機(jī)森林的準(zhǔn)確性和訓(xùn)練速度.Nadi等人[18]基于多視圖理論提出一種新的隨機(jī)森林算法IVRD(increase the views and reduce the depth approach in RF)，該算法通過(guò)增加決策樹(shù)的數(shù)量和限制每棵樹(shù)的層數(shù)來(lái)提高隨機(jī)森林的性能.Wang等人[19]提出了一種在隨機(jī)子空間上具有主方向的斜向森林(a forest of trees with principal direction specified oblique split on random subspace, FPDS)，其中每一棵樹(shù)的分裂在隨機(jī)子空間確定后都是唯一的，該算法通過(guò)啟發(fā)式的方法獲得超平面來(lái)保證最終森林的分類(lèi)性能，避免了搜索最優(yōu)分割或隨機(jī)地生成分割.此外，部分學(xué)者還將隨機(jī)森林算法擴(kuò)展到含有高維數(shù)據(jù)[20]、不完備數(shù)據(jù)[21]、單調(diào)數(shù)據(jù)[22-23]以及少量標(biāo)記樣本數(shù)據(jù)[24]等復(fù)雜數(shù)據(jù)的分類(lèi)任務(wù)中.

在隨機(jī)森林的相關(guān)研究中，分類(lèi)性能一直是一個(gè)備受關(guān)注的研究熱點(diǎn).Breiman[1]指出隨機(jī)森林的性能高度依賴(lài)于單棵決策樹(shù)的準(zhǔn)確性以及森林中決策樹(shù)的多樣性.也就是說(shuō)，單棵決策樹(shù)的分類(lèi)準(zhǔn)確性越高，且決策樹(shù)之間的多樣性越大，則集成分類(lèi)器的性能越好.若決策樹(shù)的個(gè)體分類(lèi)準(zhǔn)確性較高，而多樣性較小，那么集成分類(lèi)器的性能也會(huì)受到限制.為了提升隨機(jī)森林的性能，Geurts等人[25]提出了一種極端隨機(jī)樹(shù)算法(extremely randomized trees, ET)，通過(guò)隨機(jī)選擇分割測(cè)試的閾值來(lái)增加決策樹(shù)的多樣性.Menze等人[26]使用線(xiàn)性判別模型或嶺回歸來(lái)選擇結(jié)點(diǎn)的最佳分割方向，構(gòu)建了斜向隨機(jī)森林(oblique random forest, ORF).Rodríguez等人[27]在對(duì)樣本屬性集進(jìn)行隨機(jī)分割的基礎(chǔ)上，利用主成分分析法對(duì)分割后的數(shù)據(jù)進(jìn)行特征變換，提出了基于特征變換思想的旋轉(zhuǎn)森林算法(rotation forest, ROF).為了進(jìn)一步增強(qiáng)森林中決策樹(shù)的多樣性，Blaser等人[28]提出了隨機(jī)旋轉(zhuǎn)集成算法.Zhang等人[29]將基于主成分分析和線(xiàn)性判別分析的旋轉(zhuǎn)隨機(jī)森林與標(biāo)準(zhǔn)的隨機(jī)森林結(jié)合起來(lái)，形成了新的隨機(jī)森林算法RFE(random forests with ensemble of feature space).該算法通過(guò)豐富森林中決策樹(shù)的類(lèi)型，增大隨機(jī)森林的多樣性，盡管森林中單棵決策樹(shù)的準(zhǔn)確性相對(duì)較低，但由于多樣性增幅較大使得模型的整體性能得到有效提升.然而，該算法與其他算法相比，在構(gòu)建隨機(jī)森林時(shí)花費(fèi)時(shí)間較多.綜上可知，隨機(jī)森林中單棵決策樹(shù)的準(zhǔn)確性以及決策樹(shù)的多樣性是2個(gè)相互制約的因素，如何在二者之間取得良好的平衡對(duì)于隨機(jī)森林整體性能的提升起著至關(guān)重要的作用[30].

文獻(xiàn)[31]在隨機(jī)森林原有2種隨機(jī)化的基礎(chǔ)上加入了類(lèi)別隨機(jī)化，提出一種基于類(lèi)別隨機(jī)化的隨機(jī)森林算法(randomization of classes based random forest, RCRF)，該算法為增大隨機(jī)森林的多樣性提供了一種新的策略，并且能夠在增大隨機(jī)森林多樣性的同時(shí)減少對(duì)單棵決策樹(shù)準(zhǔn)確性的影響.RCRF算法從類(lèi)別的角度出發(fā)，為每一棵決策樹(shù)隨機(jī)選擇優(yōu)先分類(lèi)的類(lèi)別，在構(gòu)建森林過(guò)程中每一棵樹(shù)優(yōu)先對(duì)選中類(lèi)別的樣本進(jìn)行分類(lèi).由于不同的決策樹(shù)側(cè)重的類(lèi)別不同，所生成決策樹(shù)的結(jié)構(gòu)也不同，可有效增大基分類(lèi)器之間的多樣性.然而，利用該算法對(duì)某一類(lèi)樣本優(yōu)先分類(lèi)時(shí)，可能增大其他類(lèi)別樣本之間進(jìn)行區(qū)分的難度，從而使分類(lèi)準(zhǔn)確性得不到明顯改善.針對(duì)此問(wèn)題，本文首先提出一種考慮優(yōu)先類(lèi)別的線(xiàn)性判別分析方法(priority class based linear discriminant analysis, PCLDA)來(lái)增強(qiáng)投影矩陣的針對(duì)性.與傳統(tǒng)LDA方法的不同之處在于，PCLDA中的類(lèi)間散度矩陣反映的是優(yōu)先類(lèi)別與非優(yōu)先類(lèi)別之間的關(guān)系，而類(lèi)內(nèi)散度矩陣反映的是所有類(lèi)別之間的關(guān)系.因此，利用PCLDA方法對(duì)訓(xùn)練集進(jìn)行空間變換，可以使屬于優(yōu)先類(lèi)別的樣本更容易被區(qū)分，同時(shí)非優(yōu)先類(lèi)別樣本之間也盡量遠(yuǎn)離.進(jìn)而，將該方法引入隨機(jī)森林算法中，提出一種基于空間變換的隨機(jī)森林算法(space transformation based random forest algorithm, ST-RF).在隨機(jī)森林的構(gòu)建過(guò)程中，通過(guò)類(lèi)別隨機(jī)化為每棵決策樹(shù)指定一個(gè)優(yōu)先類(lèi)別來(lái)增加隨機(jī)森林的多樣性，針對(duì)包含優(yōu)先類(lèi)別的結(jié)點(diǎn)，運(yùn)用PCLDA方法對(duì)樣本進(jìn)行空間變換來(lái)提高單棵決策樹(shù)的準(zhǔn)確性，對(duì)于不包含優(yōu)先類(lèi)別的結(jié)點(diǎn)則直接選擇最優(yōu)屬性進(jìn)行結(jié)點(diǎn)分裂.通過(guò)2種結(jié)點(diǎn)處理方式的有機(jī)結(jié)合來(lái)進(jìn)一步保證森林中決策樹(shù)的多樣性.總之，本文所提算法ST-RF是通過(guò)在多樣性和準(zhǔn)確性之間尋求更好的平衡，來(lái)達(dá)到提升集成模型整體性能的目的.

本文的主要貢獻(xiàn)包括3個(gè)方面：

1) 給出一種考慮優(yōu)先類(lèi)別的線(xiàn)性判別分析方法(PCLDA).該方法通過(guò)定義針對(duì)多分類(lèi)問(wèn)題的類(lèi)間散度矩陣和類(lèi)內(nèi)散度矩陣，來(lái)得到更具針對(duì)性的投影矩陣.利用該方法對(duì)訓(xùn)練集進(jìn)行空間變換，可增強(qiáng)不同類(lèi)別的樣本之間的區(qū)分效果.

2) 提出一種基于空間變換的隨機(jī)森林算法.該算法能夠在保證森林中決策樹(shù)多樣性的同時(shí)，進(jìn)一步提高單棵決策樹(shù)的針對(duì)性和準(zhǔn)確性，有效提升隨機(jī)森林的整體性能.

3) 利用PCLDA方法對(duì)樣本進(jìn)行空間變換是本文所提算法的核心思想，也是一種通用的改進(jìn)策略，將該策略應(yīng)用到已有的隨機(jī)森林算法上，可以顯著提升原算法的分類(lèi)性能.

1 考慮優(yōu)先類(lèi)別的線(xiàn)性判別分析方法PCLDA

傳統(tǒng)的LDA方法在處理多分類(lèi)問(wèn)題時(shí)，將所有的類(lèi)別都同等對(duì)待，因此，所做的空間變換缺乏針對(duì)性.為了克服LDA的局限性，可以指定需要優(yōu)先考慮的類(lèi)別，并在投影時(shí)重點(diǎn)區(qū)分優(yōu)先考慮類(lèi)別的樣本與其他類(lèi)別樣本，以增強(qiáng)分類(lèi)的準(zhǔn)確性.假設(shè)ωz為優(yōu)先類(lèi)別，為了在分類(lèi)時(shí)對(duì)屬于ωz類(lèi)的樣本給予更多關(guān)注，可以把訓(xùn)練集投影到一個(gè)新的空間，使得屬于ωz類(lèi)的樣本和不屬于ωz類(lèi)的樣本在該空間下的投影點(diǎn)盡量遠(yuǎn)離；同時(shí)，對(duì)于所有不屬于ωz類(lèi)的樣本，使得在新空間中同類(lèi)樣本的投影點(diǎn)盡可能接近、不同類(lèi)樣本的投影點(diǎn)盡可能遠(yuǎn)離.為了得到具有針對(duì)性的投影矩陣，基于以上思想，在傳統(tǒng)LDA的基礎(chǔ)上，通過(guò)定義針對(duì)多分類(lèi)問(wèn)題的類(lèi)間散度矩陣和類(lèi)內(nèi)散度矩陣，給出一種考慮優(yōu)先類(lèi)別的線(xiàn)性判別分析方法(PCLDA).與傳統(tǒng)LDA方法的不同之處在于，PCLDA中的類(lèi)間散度矩陣反映的是優(yōu)先類(lèi)別與非優(yōu)先類(lèi)別之間的關(guān)系，而類(lèi)內(nèi)散度矩陣反映的是所有類(lèi)別之間的關(guān)系.因此，利用PCLDA方法對(duì)訓(xùn)練集進(jìn)行空間變換，可以使屬于優(yōu)先類(lèi)別的樣本更容易被區(qū)分，同時(shí)非優(yōu)先類(lèi)別樣本之間也盡量遠(yuǎn)離.

在多分類(lèi)任務(wù)中，給定一個(gè)包含n個(gè)樣本的訓(xùn)練集(X,Y)，X={x1,x2,…,xn}是樣本集合，其中xj∈M是樣本集中第j個(gè)樣本，Y={y1,y2,…,yn}是與X相對(duì)應(yīng)的類(lèi)別標(biāo)簽，其中yj∈{ω1,ω2,…,ωc}是第j個(gè)樣本的類(lèi)別標(biāo)簽.

定義1.給定一個(gè)優(yōu)先類(lèi)別ωz和一個(gè)訓(xùn)練集(X,Y).將屬于ωz類(lèi)的樣本視為正類(lèi)，不屬于ωz類(lèi)的樣本視為負(fù)類(lèi)，其2類(lèi)類(lèi)間散度矩陣Szb定義為

(1)

對(duì)于給定的c類(lèi)訓(xùn)練集(X,Y)，用類(lèi)內(nèi)散度矩陣Sw來(lái)衡量類(lèi)內(nèi)樣本的遠(yuǎn)近程度.

(2)

(3)

根據(jù)式(2)，可得投影后的類(lèi)內(nèi)散度矩陣為

(4)

欲使同類(lèi)樣本的投影點(diǎn)盡可能接近，可以讓同類(lèi)樣本的投影點(diǎn)的協(xié)方差盡可能??；欲使ωz類(lèi)樣本的投影點(diǎn)和其他類(lèi)別樣本的投影點(diǎn)盡可能遠(yuǎn)，可以使相應(yīng)類(lèi)中心的距離盡可能大，從而得到欲最大化的目標(biāo)函數(shù)：

(5)

不失一般性，令tr(WTSwW)=1，則式(5)等價(jià)于

min {-tr(WTSzbW)},

(6)

s.t. tr(WTSwW)=1.

由拉格朗日乘子法，得到優(yōu)化函數(shù)：

f(W)=-tr(WTSzbW)+λ[tr(WTSwW)-1],

(7)

將f(W)關(guān)于W求導(dǎo)，并令其為0，可得:

(8)

由于Szb與Sw均為對(duì)稱(chēng)陣，即：

WTSzb=λWTSw,

(9)

兩邊轉(zhuǎn)置，可得：

SzbW=λSwW,

(10)

(11)

即

由上式可得：

故有

則

r(Szb)=r((μz-μ)(μz-μ)T)=
r((μz-μ)T(μz-μ))=1.

利用PCLDA對(duì)訓(xùn)練集進(jìn)行投影時(shí)重點(diǎn)關(guān)注選定的優(yōu)先類(lèi)別，使得在投影后的新空間中屬于優(yōu)先類(lèi)別的樣本更容易被區(qū)分，同時(shí)不同類(lèi)別的樣本之間盡量遠(yuǎn)離.因此，將該方法引入隨機(jī)森林算法中，有助于提升算法的分類(lèi)性能.

2 基于空間變換的隨機(jī)森林算法ST-RF

由于隨機(jī)森林的分類(lèi)性能主要取決于單棵決策樹(shù)的準(zhǔn)確性和決策樹(shù)之間的多樣性這2個(gè)相互制約的因素，為了提高隨機(jī)森林的整體性能，本文將考慮優(yōu)先類(lèi)別的PCLDA方法引入隨機(jī)森林中，提出一種基于空間變換的隨機(jī)森林算法ST-RF，在多樣性和準(zhǔn)確性之間尋求更好的平衡.該算法在隨機(jī)森林的構(gòu)建過(guò)程中，首先通過(guò)類(lèi)別隨機(jī)化為每棵決策樹(shù)指定一個(gè)優(yōu)先類(lèi)別來(lái)增加隨機(jī)森林的多樣性，進(jìn)而針對(duì)包含優(yōu)先類(lèi)別的結(jié)點(diǎn)，運(yùn)用PCLDA方法對(duì)樣本進(jìn)行空間變換來(lái)提高單棵決策樹(shù)的準(zhǔn)確性，對(duì)于不包含優(yōu)先類(lèi)別的結(jié)點(diǎn)則直接選擇最優(yōu)屬性進(jìn)行結(jié)點(diǎn)分裂.可見(jiàn)，ST-RF算法既能夠保證隨機(jī)森林的多樣性，又能夠提高單棵決策樹(shù)的針對(duì)性和準(zhǔn)確性，有助于集成模型整體性能的有效提升.

2.1 ST-RF算法描述

ST-RF算法的基本思想為：假設(shè)隨機(jī)森林的集成規(guī)模為L(zhǎng)，對(duì)于森林中的第i棵決策樹(shù)Ti，從所有類(lèi)別{ω1,ω2,…,ωc}中隨機(jī)抽取一個(gè)類(lèi)別標(biāo)簽ωz(1≤z≤c)作為決策樹(shù)Ti的優(yōu)先類(lèi)別.決策樹(shù)Ti中每個(gè)結(jié)點(diǎn)的分裂方式分為2種情況：

1) 當(dāng)結(jié)點(diǎn)中包含屬于ωz類(lèi)的樣本時(shí)，運(yùn)用PCLDA方法對(duì)該結(jié)點(diǎn)中的訓(xùn)練樣本進(jìn)行空間變換，則數(shù)據(jù)表現(xiàn)形式由原來(lái)的M維降為1維，在變換后的1維空間只需根據(jù)基尼系數(shù)選擇最佳分裂閾值即可生成子結(jié)點(diǎn).為了充分利用訓(xùn)練樣本的原始信息，子結(jié)點(diǎn)中的樣本仍使用其在原始空間下的數(shù)據(jù)表示形式.

2) 當(dāng)結(jié)點(diǎn)中不包含屬于ωz類(lèi)的樣本時(shí)，從M個(gè)原始屬性中隨機(jī)選取m個(gè)屬性，在原始數(shù)據(jù)空間根據(jù)基尼系數(shù)從m個(gè)屬性中選擇最佳分裂屬性和分裂閾值生成子結(jié)點(diǎn).

也就是說(shuō)，ST-RF算法在訓(xùn)練階段需根據(jù)每個(gè)結(jié)點(diǎn)包含樣本所屬的不同類(lèi)別采用不同的分裂方式生成子結(jié)點(diǎn).這2種結(jié)點(diǎn)處理方式的有機(jī)結(jié)合進(jìn)一步保證了森林中決策樹(shù)的多樣性.

下面通過(guò)算法1對(duì)ST-RF算法的具體實(shí)現(xiàn)過(guò)程進(jìn)行詳細(xì)地闡述.

算法1.ST-RF算法.

輸入：訓(xùn)練集(X,Y)、候選屬性個(gè)數(shù)m、隨機(jī)森林的集成規(guī)模L；

輸出：包含L棵決策樹(shù)的隨機(jī)森林模型.

① fori=1,2,…,Ldo

③ 從類(lèi)別標(biāo)簽{ω1,ω2,…,ωc}中隨機(jī)抽取一個(gè)類(lèi)別ωz作為第i棵決策樹(shù)的優(yōu)先類(lèi)別；

④ 創(chuàng)建一個(gè)包含所有訓(xùn)練樣本的根結(jié)點(diǎn)；

⑤ if 結(jié)點(diǎn)滿(mǎn)足停止分裂條件 then

⑥ 將該結(jié)點(diǎn)標(biāo)記為葉子結(jié)點(diǎn)，其類(lèi)別標(biāo)記為該結(jié)點(diǎn)中樣本數(shù)最多的類(lèi)，轉(zhuǎn)至步驟；

⑦ else

⑧ if結(jié)點(diǎn)中包含屬于類(lèi)別ωz的樣本 then

⑨ 利用PCLDA方法對(duì)結(jié)點(diǎn)中的樣本進(jìn)行空間變換；

⑩ 在變換后的1維空間根據(jù)基尼系數(shù)選擇最佳分裂閾值生成子結(jié)點(diǎn)；

在算法1的步驟⑤中提到的結(jié)點(diǎn)停止分裂條件包含2種情形：1)當(dāng)前結(jié)點(diǎn)包含的樣本都屬于同一類(lèi)別；2)當(dāng)前屬性集為空，或所有樣本在所有屬性上取值相同.

在測(cè)試階段，對(duì)于測(cè)試樣本x分別利用生成的L棵決策樹(shù)進(jìn)行預(yù)測(cè).值得注意的是，測(cè)試樣本在每棵決策樹(shù)中的不同結(jié)點(diǎn)也要做相應(yīng)的空間變換，轉(zhuǎn)換到對(duì)應(yīng)空間再進(jìn)行屬性值的判斷.每棵決策樹(shù)Ti都會(huì)在測(cè)試中給出一個(gè)相應(yīng)的預(yù)測(cè)結(jié)果Ti(x)，L棵決策樹(shù)就對(duì)應(yīng)L個(gè)預(yù)測(cè)結(jié)果.隨機(jī)森林最終的輸出結(jié)果通過(guò)投票的方式給出，即測(cè)試樣本x最終的類(lèi)別標(biāo)簽y是得票最多的類(lèi)別，具體計(jì)算為

(12)

2.2 算法時(shí)間復(fù)雜度分析

通過(guò)計(jì)算決策樹(shù)中非葉結(jié)點(diǎn)的分裂代價(jià)對(duì)ST-RF算法的時(shí)間復(fù)雜度進(jìn)行分析.具體分析過(guò)程為：

1) 當(dāng)非葉結(jié)點(diǎn)中包含屬于優(yōu)先類(lèi)別ωz的樣本時(shí)，首先需對(duì)結(jié)點(diǎn)中的訓(xùn)練樣本進(jìn)行空間變換，將數(shù)據(jù)維度由M維降至1維，其計(jì)算代價(jià)為O(M3)；然后，在變換后的1維空間選擇最佳分裂閾值生成子結(jié)點(diǎn)，其計(jì)算代價(jià)為O(n).假設(shè)當(dāng)前決策樹(shù)中此類(lèi)結(jié)點(diǎn)個(gè)數(shù)為k1，則分裂代價(jià)為O(k1M3+nlb(k1)).

2) 當(dāng)非葉結(jié)點(diǎn)中不包含屬于優(yōu)先類(lèi)別ωz的樣本時(shí)，則從屬性集中隨機(jī)選取m個(gè)屬性，從m個(gè)屬性中選擇最佳分裂屬性和分裂閾值生成子結(jié)點(diǎn)，其計(jì)算代價(jià)為O(mn).假設(shè)單棵決策樹(shù)中此類(lèi)結(jié)點(diǎn)的個(gè)數(shù)為k2，則分裂代價(jià)為O(mnlb(k2)).

由算法1可知，ST-RF算法中的單棵決策樹(shù)是一棵二叉樹(shù)，其結(jié)點(diǎn)包含2種類(lèi)型：1)葉結(jié)點(diǎn);2)具有2個(gè)分支的非葉結(jié)點(diǎn).由于葉結(jié)點(diǎn)的數(shù)目至多為樣本數(shù)n(即每個(gè)葉結(jié)點(diǎn)包含1個(gè)樣本)，因此，非葉結(jié)點(diǎn)數(shù)至多為n-1，即有k1+k2≤n-1.綜上可知，單棵決策樹(shù)中所有非葉結(jié)點(diǎn)的總分裂代價(jià)為O(k1M3+nlb(k1)+mnlb(k2)).

由于ST-RF算法最終生成的是包含L棵決策樹(shù)的隨機(jī)森林，因此，本文所提算法在訓(xùn)練階段的總時(shí)間復(fù)雜度為O(Lk1M3+Lnlb(k1)+Lmnlb(k2)).

2.3 空間變換策略在其他隨機(jī)森林算法中的應(yīng)用

利用考慮優(yōu)先類(lèi)別的線(xiàn)性判別分析方法PCLDA對(duì)樣本進(jìn)行空間變換是本文所提算法的核心思想，這種基于PCLDA的空間變換策略具有較好的普適性，可以將其應(yīng)用到已有的隨機(jī)森林算法中來(lái)提升原算法的分類(lèi)性能.當(dāng)在隨機(jī)森林算法A上應(yīng)用該策略時(shí)，首先，需為每棵決策樹(shù)隨機(jī)選擇優(yōu)先類(lèi)別，進(jìn)而，根據(jù)決策樹(shù)結(jié)點(diǎn)分裂時(shí)的具體情況有針對(duì)性地進(jìn)行處理：

1) 當(dāng)結(jié)點(diǎn)中包含屬于優(yōu)先類(lèi)別的樣本時(shí)，運(yùn)用PCLDA方法對(duì)該結(jié)點(diǎn)中的訓(xùn)練樣本進(jìn)行空間變換，在變換后的新空間根據(jù)原算法A中的閾值選擇標(biāo)準(zhǔn)直接選擇最佳分裂閾值即可生成子結(jié)點(diǎn).

2) 當(dāng)結(jié)點(diǎn)中不包含屬于優(yōu)先類(lèi)別的樣本時(shí)，則根據(jù)原算法A中的相應(yīng)策略生成子結(jié)點(diǎn).

在隨機(jī)森林算法A上應(yīng)用基于PCLDA的空間變換策略后，每棵決策樹(shù)更具針對(duì)性，從而使得其對(duì)屬于優(yōu)先類(lèi)別樣本的區(qū)分能力增強(qiáng)，單棵決策樹(shù)的準(zhǔn)確性得以提升.同時(shí)，由于不同決策樹(shù)隨機(jī)選擇的優(yōu)先類(lèi)別不同，保證了決策樹(shù)之間的多樣性，使得改進(jìn)后的隨機(jī)森林算法性能得到進(jìn)一步提升.

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

本節(jié)通過(guò)實(shí)驗(yàn)對(duì)所提算法的有效性進(jìn)行驗(yàn)證.實(shí)驗(yàn)環(huán)境為：處理器Intel Core i7-4790 3.60 GHz，內(nèi)存8 GB，操作系統(tǒng)Windows 7 64位，實(shí)驗(yàn)中所有的算法均使用Matlab2013實(shí)現(xiàn).

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文選取了UCI和KEEL數(shù)據(jù)庫(kù)中的10個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析.表1簡(jiǎn)要描述了這10個(gè)數(shù)據(jù)集，包括樣本個(gè)數(shù)、屬性個(gè)數(shù)和類(lèi)別個(gè)數(shù).

Table1 Data Sets Used in the Experiments

3.2 度量指標(biāo)

實(shí)驗(yàn)中分別用準(zhǔn)確率(Accuracy)、F1度量和Kappa系數(shù)κ來(lái)度量算法的性能.其中，準(zhǔn)確率(Accuracy)表示分類(lèi)器對(duì)測(cè)試集樣本正確分類(lèi)的數(shù)量占測(cè)試集樣本總數(shù)的比例，是分類(lèi)任務(wù)中最常用的性能評(píng)價(jià)指標(biāo)，計(jì)算方式為

(13)

F1度量也是一種常用的分類(lèi)評(píng)價(jià)指標(biāo)，是查準(zhǔn)率(precision,P)和查全率(recall,R)具有相同權(quán)重時(shí)的加權(quán)調(diào)和平均，計(jì)算方式為

(14)

Kappa系數(shù)κ用來(lái)評(píng)估模型的分類(lèi)結(jié)果與實(shí)際結(jié)果的一致性程度，也常作為分類(lèi)任務(wù)的評(píng)價(jià)指標(biāo)，計(jì)算方法為

(15)

其中，PA是2個(gè)分類(lèi)器取得一致的概率，Pe是2個(gè)分類(lèi)器偶然達(dá)成一致的概率.

3.3 分類(lèi)性能比較

為了驗(yàn)證所提算法的分類(lèi)性能，本文將ST-RF算法與7種典型的隨機(jī)森林算法RF[1]，RCRF[31]，CRF[15]，RFE[29]，BRF[16]，IVRD[18]，F(xiàn)PDS[19]進(jìn)行對(duì)比分析.在實(shí)驗(yàn)過(guò)程中，各種算法的集成規(guī)模L均為100，候選屬性集m=lbM.其中，BRF算法中伯努利分布參數(shù)p1=p2=0.05，結(jié)點(diǎn)中估計(jì)樣本的最小值kn=5；FPDS算法中純度閾值δ=1；RFE和ST-RF算法中，當(dāng)類(lèi)內(nèi)散度矩陣Sw不可逆時(shí)，Sw=Sw+λE，λ=0.1.需要說(shuō)明的是，IVRD算法是通過(guò)減少單棵決策樹(shù)的深度同時(shí)增加決策樹(shù)的數(shù)量來(lái)提升整體性能的，由于實(shí)驗(yàn)部分其他算法的集成規(guī)模都是100，為了公平起見(jiàn)，將IVRD算法的集成規(guī)模也定為100，并不再增加.實(shí)驗(yàn)采用10折交叉驗(yàn)證來(lái)估計(jì)算法的泛化能力，為了保證算法的穩(wěn)定性，在所有數(shù)據(jù)集上將算法重復(fù)執(zhí)行10次，在10個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表2～4所示.為了進(jìn)一步驗(yàn)證ST-RF算法的性能提升是否在統(tǒng)計(jì)學(xué)上具有顯著性，本文使用t檢驗(yàn)對(duì)8種算法的實(shí)驗(yàn)結(jié)果進(jìn)行了比較，并列出在顯著性水平α=0.05下的顯著性分析結(jié)果，其中，Win表示ST-RF算法比其他算法性能顯著提升的數(shù)據(jù)集個(gè)數(shù)，Tie表示結(jié)果不具有顯著性的數(shù)據(jù)集個(gè)數(shù)，Loss表示ST-RF算法性能顯著不好的數(shù)據(jù)集個(gè)數(shù).

Table 2 Accuracy Comparison for Eight Algorithms

Table 3 F1 Value Comparison for Eight Algorithms

Table 4 Kappa Coefficient Comparison for Eight Algorithms

從表2～4的實(shí)驗(yàn)數(shù)據(jù)可以看出，ST-RF算法對(duì)所有數(shù)據(jù)集在3種評(píng)價(jià)指標(biāo)上的實(shí)驗(yàn)結(jié)果均顯著優(yōu)于RF，RCRF，BRF，IVRD算法.與CRF算法相比，ST-RF算法雖然在所有數(shù)據(jù)集上性能都更優(yōu)，但在segment數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果不具有顯著性.與FPDS算法相比，ST-RF算法的性能在除mfeat-fou和mfeat-kar以外的8個(gè)數(shù)據(jù)集上均有顯著性?xún)?yōu)勢(shì)，在mfeat-fou和mfeat-kar數(shù)據(jù)集上性能優(yōu)勢(shì)不具有顯著性.與RFE算法相比，ST-RF算法的性能在7個(gè)數(shù)據(jù)集上均優(yōu)于RFE算法，且在其中除segment和zip以外的5個(gè)數(shù)據(jù)集上有顯著性?xún)?yōu)勢(shì)，在letter，pendigits，texture數(shù)據(jù)集上性能略低于RFE算法，但在letter和pendigits數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果不具有顯著性.綜上所述，ST-RF算法相比其他7種算法具有更好的分類(lèi)性能.

在收斂性方面，文獻(xiàn)[1]對(duì)隨機(jī)森林的收斂性進(jìn)行了證明，指出隨著決策樹(shù)數(shù)目的逐漸增多，隨機(jī)森林的誤差會(huì)逐步收斂.由于本文所提算法ST-RF保留了傳統(tǒng)隨機(jī)森林的基本結(jié)構(gòu)，因此也具有類(lèi)似的收斂性質(zhì).本文還通過(guò)實(shí)驗(yàn)進(jìn)一步分析了隨機(jī)森林中決策樹(shù)的數(shù)量對(duì)算法性能的影響.以10為步長(zhǎng)將8種算法中決策樹(shù)的數(shù)量L依次從10取到100進(jìn)行實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果如圖1所示.由圖1可以看出隨著決策樹(shù)數(shù)量的增加，各種隨機(jī)森林的性能均趨向于穩(wěn)定.在森林中決策樹(shù)的數(shù)量較小時(shí)，ST-RF算法依然具有較好的分類(lèi)準(zhǔn)確性.

Fig.1 Influence of the number of decision trees in radom forest on the algorithms圖1 隨機(jī)森林中決策樹(shù)的數(shù)量對(duì)算法的影響

3.4 多樣性與準(zhǔn)確性分析

通過(guò)分析ST-RF算法在多樣性和準(zhǔn)確性上的具體表現(xiàn)，進(jìn)一步驗(yàn)證ST-RF算法在提高隨機(jī)森林整體性能方面的有效性.首先，利用κ-誤差圖[27]對(duì)隨機(jī)森林中的決策樹(shù)進(jìn)行“成對(duì)型”多樣性度量.κ-誤差圖主要用來(lái)度量2棵決策樹(shù)的差異性以及它們的平均誤差，其中差異性通過(guò)Kappa系數(shù)(κ)來(lái)度量.當(dāng)隨機(jī)森林中決策樹(shù)數(shù)量為L(zhǎng)時(shí)，將產(chǎn)生L(L-1)/2對(duì)決策樹(shù)，每一對(duì)決策樹(shù)的度量值構(gòu)成圖中的1個(gè)點(diǎn)，點(diǎn)的橫坐標(biāo)是這對(duì)決策樹(shù)的κ值，縱坐標(biāo)是這對(duì)決策樹(shù)的平均誤差.限于篇幅本文選取了3個(gè)代表性的數(shù)據(jù)集mfeat-zer，waveform，zip，展示了8種算法在這3個(gè)數(shù)據(jù)集上的κ-誤差圖，如圖2所示.8種集成分類(lèi)器中決策樹(shù)的數(shù)目L均為100，圖2中每種算法的數(shù)據(jù)點(diǎn)云都有4 950個(gè)點(diǎn).在κ-誤差圖中數(shù)據(jù)點(diǎn)云的位置越靠上，單棵決策樹(shù)的誤差越大，準(zhǔn)確性越差；數(shù)據(jù)點(diǎn)云的位置越靠右，κ值越大，表明成對(duì)決策樹(shù)的一致性程度越高，即決策樹(shù)之間的多樣性越小.

由圖2的數(shù)據(jù)點(diǎn)云分布可以看出，對(duì)于數(shù)據(jù)集mfeat-zer和zip來(lái)說(shuō)，RFE算法的多樣性最大，但單棵決策樹(shù)分類(lèi)準(zhǔn)確性卻相對(duì)較低；CRF算法單棵決策樹(shù)分類(lèi)準(zhǔn)確性最高，但決策樹(shù)間的多樣性較?。籗T-RF算法雖然在多樣性上略遜色于RFE，RCRF，BRF算法，但其在單棵決策樹(shù)分類(lèi)準(zhǔn)確性上有了顯著提高，且在與RF，CRF算法單棵決策樹(shù)分類(lèi)準(zhǔn)確性相近的情況下，ST-RF算法的多樣性更大.對(duì)于數(shù)據(jù)集waveform來(lái)說(shuō)，ST-RF算法雖然在多樣性上比其他算法小，但準(zhǔn)確性卻是最好的.由此可知，ST-RF算法相較于其他7種算法能夠更好地兼顧準(zhǔn)確性和多樣性，進(jìn)而實(shí)現(xiàn)整體性能的優(yōu)化.

為了更全面地比較8種算法在準(zhǔn)確性及多樣性上的表現(xiàn)，表5給出了10個(gè)數(shù)據(jù)集κ-誤差的均值數(shù)據(jù).為了保證結(jié)果的穩(wěn)定性，實(shí)驗(yàn)采用10次10折交叉驗(yàn)證，取10次10折交叉驗(yàn)證100次運(yùn)算結(jié)果的均值作為實(shí)驗(yàn)結(jié)果.從表5的數(shù)據(jù)可以看出，在準(zhǔn)確性方面，ST-RF和CRF算法的單棵決策樹(shù)準(zhǔn)確性比其他算法要高，其中，ST-RF算法單棵決策樹(shù)錯(cuò)誤率在5個(gè)數(shù)據(jù)集上都是最小的，CRF算法單棵決策樹(shù)的錯(cuò)誤率在4個(gè)數(shù)據(jù)集上最小.在多樣性方面，RFE算法的多樣性最好，其多樣性在5個(gè)數(shù)據(jù)集上是最大的，RCRF和FPDS算法分別在2個(gè)數(shù)據(jù)集上多樣性最大，而ST-RF算法在多樣性上比其余算法要好.綜合2方面來(lái)看，CRF算法單棵決策樹(shù)的錯(cuò)誤率最小，但其決策樹(shù)之間的多樣性也較小；RCRF算法、RFE算法和FPDS算法雖然多樣性較大，但錯(cuò)誤率相對(duì)較高.相比之下，ST-RF算法在準(zhǔn)確性上明顯更優(yōu)，同時(shí)又在多樣性方面比具有較高準(zhǔn)確性的CRF算法表現(xiàn)更好，即ST-RF算法在多樣性和準(zhǔn)確性之間做到了較好的平衡.由此可以看出，與其他7種算法相比，ST-RF算法不僅在準(zhǔn)確性上有較大提高，在多樣性和準(zhǔn)確性2方面的綜合表現(xiàn)也更優(yōu)，從而實(shí)現(xiàn)了集成模型整體性能的有效提升.

Fig.2 κ-error diagram圖2 κ-誤差圖

Table 5 κ-error Mean for Eight Algorithms

3.5 運(yùn)行時(shí)間比較

本文還將所提算法ST-RF與其他算法從建立集成分類(lèi)器所需時(shí)間和單棵決策樹(shù)的結(jié)點(diǎn)數(shù)量2方面進(jìn)行比較分析.

利用上述8種算法在10個(gè)數(shù)據(jù)集上分別構(gòu)建集成分類(lèi)器，集成分類(lèi)器中單棵決策樹(shù)的平均結(jié)點(diǎn)數(shù)比較結(jié)果如圖3所示.從圖3可以看出，IVRD算法由于深度較小，其生成的單棵決策樹(shù)的結(jié)點(diǎn)數(shù)最少；FPDS算法生成的單棵決策樹(shù)結(jié)點(diǎn)數(shù)最多.ST-RF算法生成的單棵決策樹(shù)的結(jié)點(diǎn)數(shù)，在大多數(shù)數(shù)據(jù)集上和其余算法相當(dāng)甚至要少.本文進(jìn)一步比較了8種算法構(gòu)建隨機(jī)森林的時(shí)間開(kāi)銷(xiāo).IVRD算法在構(gòu)建隨機(jī)森林時(shí)，每棵決策樹(shù)的最大深度都要從1開(kāi)始逐漸遞加，直到隨機(jī)森林的性能不再提升為止，因此構(gòu)建隨機(jī)森林的時(shí)間大大超過(guò)了其他算法，為了比較的可視化，圖4僅列出了其余7種算法構(gòu)建集成分類(lèi)器所需時(shí)間的比較結(jié)果.從圖4可以看出，F(xiàn)PDS算法利用PCA直接得到分裂屬性，減少了屬性選擇的時(shí)間，因而其在大多數(shù)數(shù)據(jù)集上構(gòu)建集成分類(lèi)器所需時(shí)間最少.RFE算法對(duì)3種隨機(jī)森林算法進(jìn)行融合，構(gòu)建隨機(jī)森林的時(shí)間開(kāi)銷(xiāo)最大.利用ST-RF算法構(gòu)建集成分類(lèi)器所需時(shí)間僅在letter和pendigits這2個(gè)數(shù)據(jù)集上比RF，CRF，RCRF算法略長(zhǎng)，但比RFE所需時(shí)間要少，而在其他數(shù)據(jù)集上建立分類(lèi)器所需時(shí)間和BRF相當(dāng)且遠(yuǎn)小于其他幾種算法.

Fig.3 Comparison of node number of single decision tree圖3 單棵決策樹(shù)的結(jié)點(diǎn)數(shù)比較

Fig.4 Comparison of the time on classifier construction for seven algorithms圖4 7種算法構(gòu)建分類(lèi)器的時(shí)間比較

由圖3和圖4的實(shí)驗(yàn)數(shù)據(jù)可知，雖然所提算法ST-RF在結(jié)點(diǎn)分裂過(guò)程中引入了PCLDA方法，需要花費(fèi)一定的時(shí)間計(jì)算投影矩陣，但是由于最佳投影是一條直線(xiàn)，投影后直接選擇分裂點(diǎn)生成子結(jié)點(diǎn)，無(wú)需再?gòu)亩鄠€(gè)候選屬性中選擇最佳分裂屬性，減少了選擇分裂屬性所需的時(shí)間，且投影后的樣本更容易區(qū)分，從而使得單棵決策樹(shù)的結(jié)點(diǎn)數(shù)變少，縮短了建立整個(gè)模型所需的時(shí)間.

3.6 算法普適性分析

利用PCLDA方法對(duì)樣本進(jìn)行空間變換是本文所提算法ST-RF的核心思想，也是一種通用的改進(jìn)策略.為了驗(yàn)證該策略的普適性和有效性，將其應(yīng)用到已有的隨機(jī)森林算法上，與原算法進(jìn)行對(duì)比分析.由于RF算法即是本文所提算法ST-RF的原算法，RCRF算法是在RF算法之上引入類(lèi)別隨機(jī)化得到的，ST-RF算法是在類(lèi)別隨機(jī)化的基礎(chǔ)上又引入空間變換策略得到的，因此，在RCRF算法中引入空間變換策略得到的ST-RCRF算法即為ST-RF算法.通過(guò)表2～4可以看出ST-RF相比于原算法RF和RCRF在性能上均有明顯的改善.進(jìn)一步將基于PCLDA的空間變換策略分別應(yīng)用到其余5種隨機(jī)森林算法CRF，RFE，BRF，IVRD，F(xiàn)PDS算法之上，分別得到5種改進(jìn)的隨機(jī)森林算法，分別記為ST-CRF，ST-RFE，ST-BRF，ST-IVRD，ST-FPDS，其中，ST-FPDS算法在每一棵決策樹(shù)建樹(shù)之前對(duì)樣本進(jìn)行可放回抽樣.此處仍然使用準(zhǔn)確率(Accuracy)、F1度量和Kappa系數(shù)κ這3種評(píng)價(jià)指標(biāo)對(duì)改進(jìn)后的算法與原算法分別進(jìn)行比較分析.實(shí)驗(yàn)分5組進(jìn)行，改進(jìn)前后的實(shí)驗(yàn)結(jié)果分別如表6～10所示.從5張表中的實(shí)驗(yàn)數(shù)據(jù)可以看出，加入基于PCLDA的空間變換策略后的改進(jìn)算法在準(zhǔn)確率(Accuracy)、F1度量、Kappa系數(shù)κ這3個(gè)指標(biāo)上的性能均明顯優(yōu)于原算法.由此可見(jiàn)，基于PCLDA的空間變換策略可以作為一種通用的改進(jìn)策略，來(lái)提升已有隨機(jī)森林算法的分類(lèi)性能.

Table 6 Performance Comparison of CRF and ST-CRF

Table 7 Performance Comparison of RFE and ST-RFE

Table 8 Performance Comparison of BRF and ST-BRF

Table 9 Performance Comparison of IVRD and ST-IVRD

Table 10 Performance Comparison of FPDS and ST-FPDS

續(xù)表10

4 總 結(jié)

為了提高隨機(jī)森林在處理多分類(lèi)問(wèn)題上的性能，本文提出一種基于空間變換的隨機(jī)森林算法.該算法利用考慮優(yōu)先類(lèi)別的線(xiàn)性判別分析方法PCLDA得到具有針對(duì)性的投影矩陣，并通過(guò)空間變換提高單棵決策樹(shù)的分類(lèi)準(zhǔn)確性；進(jìn)而，引入類(lèi)別隨機(jī)化為每棵決策樹(shù)指定一個(gè)優(yōu)先類(lèi)別，并利用PCLDA方法創(chuàng)建一組側(cè)重于不同類(lèi)別的決策樹(shù)，達(dá)到增加隨機(jī)森林多樣性的目的，從而實(shí)現(xiàn)集成模型整體分類(lèi)性能的有效提升.基于PCLDA的空間變換方法是一種通用的改進(jìn)策略，將其應(yīng)用到已有的隨機(jī)森林算法上能夠增強(qiáng)原算法的分類(lèi)性能.未來(lái)研究將會(huì)圍繞包含復(fù)雜數(shù)據(jù)類(lèi)型的分類(lèi)問(wèn)題展開(kāi)，在保證基分類(lèi)器多樣性的同時(shí)，提高集成模型的魯棒性和靈活性，進(jìn)一步擴(kuò)大隨機(jī)森林的適用范圍.