基于決策邊界的傾斜森林分類算法

闞學(xué)達(dá)，桂 瓊，張攀峰

(桂林理工大學(xué) 信息科學(xué)與工程學(xué)院，廣西 桂林 541004)

0 引 言

作為多分類器的代表，由Leo Breiman提出的隨機(jī)森林(random forests，RF)是分類算法的重要技術(shù)之一[1]。該算法被廣泛應(yīng)用于電力系統(tǒng)電荷預(yù)測(cè)[2，3]、入侵檢測(cè)[4]、密碼體制識(shí)別[5]以及圖像分割[6]等方面。然而，該算法分類準(zhǔn)確率還有待進(jìn)一步提高[7]。此外，隨機(jī)森林算法在分類不平衡數(shù)據(jù)集時(shí)，對(duì)少數(shù)類分類準(zhǔn)確率過低，導(dǎo)致整體分類準(zhǔn)確率下降[8]。因此，提高其對(duì)不平衡數(shù)據(jù)的分類準(zhǔn)確率非常重要。對(duì)于處理不平衡數(shù)據(jù)方面，現(xiàn)有研究主要從數(shù)據(jù)集出發(fā)，將數(shù)據(jù)預(yù)處理融入到分類算法中[9]。文獻(xiàn)[10]、文獻(xiàn)[11]通過對(duì)抽樣與投票的過程進(jìn)行加權(quán)，使少數(shù)類有更高概率被抽樣，并且對(duì)分類結(jié)果較好的決策樹賦予更高的投票權(quán)重，有效提高隨機(jī)森林對(duì)于不平衡數(shù)據(jù)的分類能力。在提高隨機(jī)森林算法的分類準(zhǔn)確率方面，文獻(xiàn)[12]提出基于改進(jìn)網(wǎng)格搜索的隨機(jī)森林參數(shù)優(yōu)化算法，通過尋找最優(yōu)參數(shù)使得隨機(jī)森林算法分類準(zhǔn)確率有所提高。文獻(xiàn)[13]將雙邊界支持向量機(jī)替代決策樹的分裂準(zhǔn)則，取得不錯(cuò)的效果。然而支持向量機(jī)的求解時(shí)間較長(zhǎng)，增加每個(gè)結(jié)點(diǎn)求解分裂準(zhǔn)則時(shí)間。針對(duì)進(jìn)一步提高隨機(jī)森林分類準(zhǔn)確率并且使其適應(yīng)不平衡數(shù)據(jù)分類，本文提出一種基于決策邊界的傾斜森林(oblique forests based on decision boundary，OFDB)分類算法。OFDB算法把傾斜分裂超平面這一概念引入隨機(jī)森林的分裂準(zhǔn)則中。通過賦予各個(gè)類自適應(yīng)權(quán)重，提高OFDB算法不平衡數(shù)據(jù)分類能力。為使算法可以解決多類分類問題，本文在單個(gè)結(jié)點(diǎn)分裂過程中采用“一對(duì)多”的策略。實(shí)驗(yàn)結(jié)果表明，OFDB算法分類準(zhǔn)確率相比于的隨機(jī)森林算法有較大提升，并且OFDB算法在處理不平衡數(shù)據(jù)集方面，比隨機(jī)森林算法有更好的表現(xiàn)。

1 隨機(jī)森林與決策邊界

隨機(jī)森林是由決策樹組成的組合分類器，由裝袋、決策樹構(gòu)建、袋外估計(jì)組成。

對(duì)于給定的n個(gè)元組m個(gè)屬性的分類數(shù)據(jù)集

(1)

假設(shè)隨機(jī)森林擁有k個(gè)單分類器，裝袋的基本思想是，對(duì)于循環(huán)i(i=1,2，…，k)， 第i個(gè)決策樹從訓(xùn)練數(shù)據(jù)集D中有放回地抽取n個(gè)元組，并且對(duì)被抽取的元組進(jìn)行標(biāo)記。

隨機(jī)森林構(gòu)建決策樹常使用Gini指數(shù)作為分裂準(zhǔn)則，用于衡量數(shù)據(jù)分區(qū)D的不純度?；嶂笖?shù)定義如式(2)所示[14]

(2)

pi表示D中元組屬于Ci類的概率?？紤]確定分裂屬性A與確定分裂點(diǎn)的情況下，數(shù)據(jù)集D被該規(guī)則劃分為D1、D2，該分裂準(zhǔn)則的基尼指數(shù)計(jì)算公式如式(3)[14]

(3)

通過求解每個(gè)結(jié)點(diǎn)基尼指數(shù)GiniA(D)最小值得到每個(gè)結(jié)點(diǎn)最優(yōu)分裂準(zhǔn)則。最終得到k個(gè)決策樹的分類模型序列 {h1(X),h2(X),…,hk(X)}。

隨機(jī)森林預(yù)測(cè)采用多數(shù)投票法如式(4)所示[1]

(4)

其中，H(X)表示組合分類模型，hi是單個(gè)決策樹分類模型。在預(yù)測(cè)中以多數(shù)表決的方法，得到隨機(jī)森林總體的分類結(jié)果。袋外估計(jì)(out of bag estimation，OOBE)用來估計(jì)隨機(jī)森林的分類能力，其使用每個(gè)決策樹訓(xùn)練子集中沒有被抽樣的元組來對(duì)這個(gè)決策樹進(jìn)行測(cè)試。

邏輯回歸是解決分類問題的一種常見算法。對(duì)于給定的樣本屬性X，y的取值如式(5)

hθ(X)=g(θTX)

(5)

其中，θ為權(quán)重參數(shù)，函數(shù)g如式(6)所示[15]

(6)

由式(5)、式(6)可知，當(dāng)函數(shù)g(z)中z>0時(shí)，g(z)>0.5，此時(shí)預(yù)測(cè)該樣本類別y取值為1。反之，當(dāng)函數(shù)g(z)中z<0時(shí)，g(z)<0.5，此時(shí)預(yù)測(cè)該樣本類別y取值為0。對(duì)于一個(gè)訓(xùn)練完成的邏輯回歸模型hθ(X)=g(θTX)， 將樣本Xi帶入決策邊界θTX計(jì)算該式是否大于0來判斷該樣本屬于某一類。θTX=0被稱之為該模型的決策邊界。邏輯回歸的代價(jià)函數(shù)如式(7)所示[16]

(7)

代價(jià)函數(shù)表示對(duì)于確定的θ模型對(duì)數(shù)據(jù)集X分類錯(cuò)誤程度。對(duì)于給定數(shù)據(jù)集，X與y的值是確定的，θ為自變量，求解代價(jià)函數(shù)的最小值，即可求得分類錯(cuò)誤程度最低時(shí)θ取值，確定決策邊界。

2 OFDB算法

2.1 基本概念

定義1 傾斜決策樹(Oblique Decision Tree)：傾斜決策樹是以決策邊界作為樹中每個(gè)結(jié)點(diǎn)的分裂準(zhǔn)則的決策樹。假設(shè)類obliqueDecisionTree，對(duì)于該類的每個(gè)實(shí)例對(duì)象Node，變量classLabel表示當(dāng)前結(jié)點(diǎn)的類標(biāo)號(hào)；變量dataset表示當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)分區(qū)；變量leftChildTree與rightChildTree分別指向其左子樹右子樹；變量obliqueSplitHyperplane表示當(dāng)前結(jié)點(diǎn)分裂超平面的θ值。

定義2 傾斜分裂超平面(Oblique Split Hyperplane)：OFDB算法中每個(gè)傾斜決策樹結(jié)點(diǎn)Node的傾斜分裂超平面如式(8)所示

θT·X+θ0=0

(8)

傳統(tǒng)隨機(jī)森林算法分裂準(zhǔn)則可表示為式(9)

x=b

(9)

其中，x表示某一確定屬性，b表示確定常數(shù)。式(9)可由式(8)表示，即傳統(tǒng)分裂準(zhǔn)則為傾斜分裂超平的一種特例，傾斜分裂超平面考慮更為廣泛的情況。在預(yù)測(cè)過程中，將新的樣本元組X帶入式obliqueSplitHyperplane·X中，以判斷該樣本位于傾斜分裂超平面的某一側(cè)，進(jìn)而被劃分至左子樹或右子樹的數(shù)據(jù)分區(qū)中。對(duì)于特定的樣本元組，計(jì)算如式(10)所示

obliqueSplitHyperplane·X= (θ0,θ1,…,θm)T·(1,x1,…,xm)

(10)

定義3 葉子結(jié)點(diǎn)標(biāo)記自適應(yīng)權(quán)重(leaf node labeling adaptive weights)：在決策樹結(jié)點(diǎn)轉(zhuǎn)化為葉子結(jié)點(diǎn)時(shí)，使用加權(quán)后的多數(shù)類標(biāo)記該結(jié)點(diǎn)。葉子結(jié)點(diǎn)標(biāo)記結(jié)果為式(11)

(11)

(12)

|D| 表示數(shù)據(jù)集D的樣本個(gè)數(shù)， |DC| 表示數(shù)據(jù)集D中屬于C類的樣本個(gè)數(shù)。

2.2 基本思想

基于決策邊界的傾斜森林分類算法是一種以隨機(jī)森林作為框架，以傾斜分裂超平面作為決策樹結(jié)點(diǎn)分裂準(zhǔn)則的分類算法。其主要針對(duì)隨機(jī)森林算法中的分裂過程做出改進(jìn)，以此提高分類準(zhǔn)確率。

在隨機(jī)森林模型的框架下，構(gòu)建k個(gè)傾斜決策樹，并且為k個(gè)傾斜決策樹進(jìn)行有放回抽樣并且舍棄重復(fù)元組作為訓(xùn)練子集。每個(gè)傾斜決策樹遞歸地對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行分裂直至滿足終止條件，之后將根據(jù)式(11)將對(duì)葉子結(jié)點(diǎn)進(jìn)行類標(biāo)記。

在傳統(tǒng)隨機(jī)森林算法中為求得最優(yōu)分裂準(zhǔn)則，通常會(huì)以最小化該結(jié)點(diǎn)Gini指數(shù)為目標(biāo)。假設(shè)，求解得分裂準(zhǔn)則為在屬性ai(i=1,2,…,m) 上分裂點(diǎn)為常數(shù)b，即分裂準(zhǔn)則為垂直于數(shù)據(jù)空間某一維度的超平面。但是這樣的分裂方式不能很好抓住數(shù)據(jù)空間中的幾何結(jié)構(gòu)，文獻(xiàn)[13]提出基于雙邊界支持向量機(jī)的傾斜決策樹，但是由于支持向量機(jī)的求解時(shí)間過長(zhǎng)，該方法僅在小數(shù)據(jù)集上具有較好表現(xiàn)。為保證構(gòu)建傾斜分裂超平面的基礎(chǔ)上提升運(yùn)算性能，本文使用式(7)作為代價(jià)函數(shù)以求解超平面的θ參數(shù)作為傾斜分裂超平面。

考慮代價(jià)函數(shù)為凸函數(shù)，即函數(shù)局部最小值即是全局最小值，本文使用梯度下降法求解代價(jià)函數(shù)最小值。參數(shù)θ更新規(guī)則如式(13)

(13)

為保證梯度下降法迅速收斂，本文在訓(xùn)練之前使用式(14)對(duì)數(shù)據(jù)集進(jìn)行規(guī)范化處理，將其取值映射至區(qū)間[0,1]之間

(14)

考慮在單個(gè)結(jié)點(diǎn)上通過一個(gè)超平面只能解決二分類的問題。為使算法可以解決多分類問題，本文使用“一對(duì)多”的策略，在單個(gè)結(jié)點(diǎn)使用最多類與其它類進(jìn)行二分類，使算法適用于多分類問題。

考慮到正負(fù)類樣本比例不同而對(duì)分類算法效果產(chǎn)生的影響，本文在葉子結(jié)點(diǎn)上設(shè)置如式(11)所示的類標(biāo)簽計(jì)算方法，按照樣本中類的比例對(duì)葉子結(jié)點(diǎn)標(biāo)記方法做出改進(jìn)。

2.3 OFDB算法描述

算法1： OFDB分類算法

Input:dataset,targetattribute,maxDepth,estimators

Output: oblique forests.

(1)forT=1 toestimatorsdo

/*T表示每個(gè)決策樹， 隨機(jī)森林共有estimators個(gè)決策樹*/

(2) call FIT function on randomly sampleddataset;

/*調(diào)用算法2， 遞歸地訓(xùn)練每個(gè)決策樹*/

(3) save out-of-bag estimation result ofT;

(4)endfor

算法2： OFDB決策樹結(jié)點(diǎn)訓(xùn)練算法FIT

Input:dataset,targetattribute,maxDepth

Output: oblique decision tree.

(1)ifdatasetis nullthen;

/*數(shù)據(jù)集為空， 則將當(dāng)前結(jié)點(diǎn)轉(zhuǎn)化為葉子結(jié)點(diǎn)*/

(2) Node convert to leaf;

(3)return0;

(4)endif

(6)ifNode.depth==maxDepththen

/*達(dá)到最大深度， 則將當(dāng)前結(jié)點(diǎn)轉(zhuǎn)化為葉子結(jié)點(diǎn)*/

(7) Node convert to leaf;

(8)return0;

(9)endif

(10)ifthe class of sample is purethen

/*數(shù)據(jù)集類純粹， 則將當(dāng)前結(jié)點(diǎn)轉(zhuǎn)化為葉子結(jié)點(diǎn)*/

(11) Node convert to leaf;

(12)return0;

(13)endif

(14)fori=1 tondo

/*采用“一對(duì)多”的策略， 使算法適用于多分類問題。遍歷n個(gè)元組的數(shù)據(jù)集， 將元組個(gè)數(shù)最多的類作為正類， 其余作為負(fù)類*/

(15)ifX[targetattribute][i]==majority class of Nodethen

(16) X[targetattribute][i]=1;

(17)else

(18) X[targetattibute][i]=0;

(19)endif

(20)endfor

(21) get obliqueSplitHyperplaneof Node fromdataset;

/*按照式(13)的更新規(guī)則， 求解式(8)傾斜分裂超平面， 保存為當(dāng)前結(jié)點(diǎn)的分裂超平面*/

(22)fori=1 tondo

/*按照式(10)將當(dāng)前數(shù)據(jù)元組按照分裂超平面繼續(xù)劃分給左右子樹*/

(23)ifX[i]·splitCriterion≥0then

(24) divide X[i] into left child tree;

(25)else

(26) divide X[i] into right child tree;

(27)endif

(28)endfor

(29) create left child tree and call FIT function;

(30) create right child tree and call FIT function;

步驟1 OFDB算法中每個(gè)傾斜決策樹進(jìn)行訓(xùn)練子集抽樣，舍棄每個(gè)子集中的重復(fù)抽樣元組。

步驟2 遞歸地訓(xùn)練每個(gè)傾斜決策樹。如果滿足結(jié)束條件，則將當(dāng)前結(jié)點(diǎn)轉(zhuǎn)化為葉子結(jié)點(diǎn)。以加權(quán)的多數(shù)類賦值給當(dāng)前結(jié)點(diǎn)的classLabel。將當(dāng)前數(shù)據(jù)分區(qū)作為訓(xùn)練集，求解出傾斜分裂超平面θTX+θ0=0。 根據(jù)求解出的傾斜分裂超平面，計(jì)算式(10)obliqueSplitHyperplane·X的取值，將每個(gè)元組劃分至左子樹或右子樹中繼續(xù)訓(xùn)練。

步驟3 統(tǒng)計(jì)袋外估計(jì)結(jié)果，返回一個(gè)OFDB分類器。

2.4 算法分析與評(píng)價(jià)

2.4.1 算法正確性分析

對(duì)于給定的輸入數(shù)據(jù)集，OFDB算法首先劃分多個(gè)數(shù)據(jù)子集，分別用于訓(xùn)練每個(gè)傾斜決策樹。對(duì)于給定的最大深度與決策樹個(gè)數(shù)參數(shù)，決策樹總會(huì)在滿足條件時(shí)停止遞歸，并且標(biāo)記該葉子結(jié)點(diǎn)。最終返回一個(gè)OFDB分類模型。在每個(gè)非葉子結(jié)點(diǎn)上保存傾斜分裂超平面θTX+θ0=0。 因此，每個(gè)預(yù)測(cè)元組總能通過傾斜分裂超平面被劃分至子樹中，最終到達(dá)葉子結(jié)點(diǎn)，返回葉子結(jié)點(diǎn)類標(biāo)號(hào)作為該元組的預(yù)測(cè)值。

2.4.2 時(shí)間復(fù)雜度分析

假設(shè)OFDB算法決策樹個(gè)數(shù)為e，最大深度為d。訓(xùn)練決策樹均為滿二叉樹。對(duì)于一個(gè)深度為m遞歸生成的滿二叉樹，則遞歸時(shí)間復(fù)雜度為O(d2)。對(duì)于一個(gè)傾斜森林有e個(gè)傾斜決策樹，則循環(huán)e次訓(xùn)練每個(gè)決策樹時(shí)間復(fù)雜度為O(e)。假設(shè)數(shù)據(jù)集樣本個(gè)數(shù)為n，屬性個(gè)數(shù)為m，對(duì)于每個(gè)結(jié)點(diǎn)分裂過程，首先遍歷數(shù)據(jù)分區(qū)，判斷是否滿足終止條件，時(shí)間復(fù)雜度為O(n)求解決策邊界使用梯度下降法，求解梯度方向需要O(mn)，再對(duì)每個(gè)參數(shù)進(jìn)行更新O(m)，迭代i次O(i)，則其時(shí)間復(fù)雜度不超過O(nm2i)。將數(shù)據(jù)分區(qū)劃分給左右子樹時(shí)間復(fù)雜度為O(n)。所以O(shè)FDB算法時(shí)間復(fù)雜度不超過O(ed2nm2i)。

2.4.3 分類性能分析

與RF算法的分裂準(zhǔn)則相對(duì)比，OFDB算法將一個(gè)傾斜分裂超平面θTX+θ0=0作為分裂準(zhǔn)則，而前者分裂準(zhǔn)則可以表示為在m維的空間中使用超平面0×x1+…+1×xi+…+0×xm-b=0來劃分所有的數(shù)據(jù)。RF算法分裂準(zhǔn)則可表示為垂直于數(shù)據(jù)集空間中的某個(gè)屬性軸的超平面，但是OFDB算法的分裂超平面不必垂直于某個(gè)屬性軸，而是相對(duì)于RF算法的分裂準(zhǔn)則是“傾斜”的，這使得OFDB算法分裂準(zhǔn)則可以更適應(yīng)數(shù)據(jù)集空間的幾何結(jié)構(gòu)。本文使用“傾斜”一詞表明OFDB算法與RF算法分裂準(zhǔn)則的區(qū)別。OFDB算法使用分裂超平面的同時(shí)也保留決策樹結(jié)點(diǎn)分裂的可解釋性。

2.4.4 評(píng)價(jià)指標(biāo)

在分類準(zhǔn)確性評(píng)價(jià)方面。以隨機(jī)森林的袋外估計(jì)結(jié)果作為計(jì)算評(píng)價(jià)指標(biāo)的依據(jù)，并使用混淆矩陣統(tǒng)計(jì)分類結(jié)果并且計(jì)算評(píng)價(jià)指標(biāo)。Leo Breiman已經(jīng)證明了隨機(jī)森林中袋外估計(jì)的無偏性[1]?；煜仃囈姳?。

表1 混淆矩陣

其中TP表示被正確分類為正類的正類樣本個(gè)數(shù)。FN表示被錯(cuò)誤分類為負(fù)類的正類樣本個(gè)數(shù)。FP表示被錯(cuò)誤分類為正類的負(fù)類樣本。TN表示被正確分類為負(fù)類的負(fù)類樣本。本文使用準(zhǔn)確率accuracy衡量分類器總體分類性能，使用TPR、FPR、F1-score來衡量分類器對(duì)不平衡數(shù)據(jù)的分類效果。

評(píng)價(jià)指標(biāo)計(jì)算如式(15)至式(18)

(15)

(16)

(17)

(18)

TPR表示正類中被正確分類為正類的比例，在本文中正類表示少數(shù)類。FPR表示被錯(cuò)誤分到正類樣本中的負(fù)類樣本所占比例。F1-score綜合考慮正類與負(fù)類的準(zhǔn)確率，是評(píng)價(jià)不平衡數(shù)據(jù)的良好指標(biāo)。TPR與F1-score取值越高說明分類器對(duì)于少數(shù)類的分類性能越優(yōu)。FPR取值高說明分類器對(duì)負(fù)類樣本并沒有很好的劃分。

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

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

實(shí)驗(yàn)主要分為2個(gè)部分：①通過人工數(shù)據(jù)集驗(yàn)證OFDB算法的可行性，并將傾斜分裂超平面可視化與RF算法的分裂準(zhǔn)則比較；②使用真實(shí)數(shù)據(jù)集橫向?qū)Ρ萇FDB算法與RF算法，以分類準(zhǔn)確率等評(píng)價(jià)指標(biāo)來衡量分類效果。真實(shí)數(shù)據(jù)集名稱、樣本個(gè)數(shù)、屬性個(gè)數(shù)以及樣本類分布情況見表2。所有數(shù)據(jù)集中的元組不含缺失值。在訓(xùn)練之前，對(duì)于數(shù)據(jù)集中離散的標(biāo)稱屬性，統(tǒng)一設(shè)置虛擬變量。

表2 數(shù)據(jù)集說明

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

實(shí)驗(yàn)1：OFDB算法與RF算法分裂準(zhǔn)則對(duì)比實(shí)驗(yàn)

為了將分裂準(zhǔn)則可視化，人工數(shù)據(jù)集維度為2維。使用互相獨(dú)立的正態(tài)分布隨機(jī)生成比例相同的正負(fù)類樣本點(diǎn)。實(shí)驗(yàn)直觀表示了OFDB算法與RF算法分類過程的區(qū)別。OFDB算法傾斜分裂超平面與RF算法分裂準(zhǔn)則如圖1、圖2所示。

圖1 OFDB算法傾斜分裂超平面

圖2 RF算法分裂準(zhǔn)則

圖中不同樣式的點(diǎn)代表兩類不同的元組，直線代表決策樹深度為0的根結(jié)點(diǎn)的劃分，每顆決策樹的根結(jié)點(diǎn)只有一個(gè)。而兩條虛線代表決策樹中深度為1的結(jié)點(diǎn)的劃分，深度為1的結(jié)點(diǎn)有兩個(gè)，分別是根結(jié)點(diǎn)的左子樹與右子樹結(jié)點(diǎn)。隨著決策樹深度的增加將會(huì)有更多的劃分對(duì)數(shù)據(jù)進(jìn)行分區(qū)，最終以每個(gè)區(qū)域的多數(shù)類標(biāo)記該區(qū)域，以此來進(jìn)行預(yù)測(cè)。由圖1、圖2可知，RF算法的分裂準(zhǔn)則必是垂直于數(shù)據(jù)集空間中的某個(gè)屬性軸的超平面，OFDB算法則是以一個(gè)“傾斜”的超平面對(duì)數(shù)據(jù)集進(jìn)行劃分，RF算法的分裂準(zhǔn)則可以由OFDB算法的傾斜分裂超平面所表示出來，因此OFDB算法傾斜分裂超平面可以考慮到RF算法分裂準(zhǔn)則的所有分裂情況。

實(shí)驗(yàn)2：OFDB算法與RF算法分類結(jié)果對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)2使用準(zhǔn)確率與其它不平衡數(shù)據(jù)評(píng)價(jià)指標(biāo)對(duì)OFDB算法與RF算法的分類結(jié)果進(jìn)行對(duì)比。以分類準(zhǔn)確率做為評(píng)價(jià)指標(biāo)。最大深度參數(shù)maxDepth分別取3，5，7；決策樹個(gè)數(shù)參數(shù)estimators分別取5，10，20。表3至表7

表3 Heart disease數(shù)據(jù)集分類準(zhǔn)確率對(duì)比

表4 Chess數(shù)據(jù)集分類準(zhǔn)確率對(duì)比

表5 Mushroom數(shù)據(jù)集分類準(zhǔn)確率對(duì)比

表6 Mammographic數(shù)據(jù)集分類準(zhǔn)確率對(duì)比

表7 Bupa數(shù)據(jù)集分類準(zhǔn)確率對(duì)比

展示5組實(shí)驗(yàn)，分別在5個(gè)數(shù)據(jù)集Heart disease、Chess、Mushroom、Mammographic、Bupa上，使用不同的參數(shù)，展示袋外估計(jì)分類結(jié)果的準(zhǔn)確率。其中較優(yōu)的實(shí)驗(yàn)數(shù)據(jù)使用粗體標(biāo)出。為減小隨機(jī)數(shù)所產(chǎn)生的單次實(shí)驗(yàn)結(jié)果不確定性，所以在本次實(shí)驗(yàn)中，實(shí)驗(yàn)結(jié)果取10次實(shí)驗(yàn)的平均值，并且計(jì)算標(biāo)準(zhǔn)差與運(yùn)行時(shí)間。

觀察表3至表7可以得出，對(duì)于Heart disease、Chess、Mushroom、Manmographic、Bupa數(shù)據(jù)集，OFDB算法分類準(zhǔn)確率高于RF算法。隨著estimators的增加，OFDB算法的分類準(zhǔn)確率有所提高。然而在estimators大于10后，總體的分類準(zhǔn)確率提高較少。對(duì)比estimators取值10和20的情況，多出一倍的決策樹個(gè)數(shù)卻只得到分類準(zhǔn)確率0.01左右的提升。隨著參數(shù)maxDepth的增加，OFDB算法的分類準(zhǔn)確率并沒有明顯的提升。這可能是因?yàn)橹饕姆诸惞ぷ魇窃谏疃容^低的結(jié)點(diǎn)中完成的，剩余少數(shù)樣本OFDB算法難以劃分。對(duì)比標(biāo)準(zhǔn)差，OFDB算法明顯具有優(yōu)勢(shì)，分類結(jié)果具有較高的穩(wěn)定性，這是由于使用決策邊界替代了原具有較高隨機(jī)性的結(jié)點(diǎn)分裂準(zhǔn)則。主要體現(xiàn)在候選分裂屬性隨機(jī)選取。運(yùn)行時(shí)間方面，OFDB運(yùn)行時(shí)間與RF運(yùn)行時(shí)間相差不大。

為表明OFDB算法相比于RF算法對(duì)于少數(shù)類分類有更優(yōu)異的性能，以不平衡數(shù)據(jù)評(píng)價(jià)指標(biāo)TPR、FPR以及F1-score衡量分類效果。如表8所示，針對(duì)參數(shù)maxDepth取值5，estimators取值10的情況，給出OFDB算法與RF算法在5個(gè)不平衡數(shù)據(jù)集Wisconsin、Nursery、Car、Pima、Yeast1上的對(duì)比結(jié)果。觀察表8可以得出，對(duì)不平衡數(shù)據(jù)集的分類OFDB算法相比RF算法具有更好的效果。

表8 不平衡數(shù)據(jù)集上OFDB算法與RF算法不平衡分類指標(biāo)對(duì)比

4 結(jié)束語

本文提出一種基于決策邊界的傾斜森林分類算法OFDB。OFDB算法使用傾斜分裂超平面來改進(jìn)RF算法中的結(jié)點(diǎn)分裂過程。針對(duì)不平衡數(shù)據(jù)處理分類問題，使用自適應(yīng)權(quán)重改進(jìn)葉子結(jié)點(diǎn)的類標(biāo)號(hào)。為使算法適用于多類分類問題，在結(jié)點(diǎn)分裂過程中采取“一對(duì)多”的策略。實(shí)驗(yàn)部分，使用人工數(shù)據(jù)集直觀對(duì)比OFDB算法與RF算法的分裂過程。通過真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果顯示，OFDB算法相較于RF算法具有更良好的分類性能，并且對(duì)不平衡數(shù)據(jù)分類能力有所提高。但對(duì)于極度不平衡數(shù)據(jù)集，OFDB算法分類效果仍較差。之后的研究中將側(cè)重于提高分類器對(duì)于不平衡數(shù)據(jù)集的分類能力，以及提高分類算法訓(xùn)練效率。