史金余，楊澤宇，謝 兄

(大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026)

0 引 言

隨機(jī)森林[1]組合了Bagging和隨機(jī)子空間兩種技術(shù)，為了獲得更好的組合正確性，需要保證單棵決策樹(shù)的正確性和多樣性[2]。許多學(xué)者對(duì)隨機(jī)森林算法進(jìn)行了廣泛的研究，劉晙提出一種基于多模糊核約束的隨機(jī)森林算法，主要解決了超分辨率圖像的魯棒性問(wèn)題[3]。吳辰文等利用變量預(yù)測(cè)和選擇的方法來(lái)提高隨機(jī)森林的預(yù)測(cè)精度[4]。Abellán等利用不精確概率和一般不確定度量的標(biāo)準(zhǔn)，改進(jìn)隨機(jī)森林的基分類器，提出基于不精確概率理論的隨機(jī)森林算法(CRF)[5]。Xia等通過(guò)屬性強(qiáng)度來(lái)調(diào)整投票權(quán)重，提出一種加權(quán)投票隨機(jī)森林算法，能夠成功地處理不完整數(shù)據(jù)的分類任務(wù)[6]?，F(xiàn)有的隨機(jī)森林算法沒(méi)有考慮屬性重要度與結(jié)點(diǎn)分裂的關(guān)聯(lián)性，忽略了重要度低的屬性對(duì)分類結(jié)果的影響，導(dǎo)致隨機(jī)森林在處理分類問(wèn)題時(shí)的正確率受到限制。傳統(tǒng)的隨機(jī)森林算法選擇屬性是完全隨機(jī)的，這就說(shuō)明每一個(gè)屬性被選擇的概率是相等的[7]。事實(shí)上，屬性重要度低的屬性應(yīng)該對(duì)最后的分類結(jié)果影響小。為了更好地解決這一問(wèn)題，本文研究了一種基于模糊決策的隨機(jī)森林算法，利用屬性重要度生成決策樹(shù)，舍棄部分重要度較低的屬性，從而減小了重要度低的屬性對(duì)最后分類結(jié)果的負(fù)面影響。同時(shí)利用葉子結(jié)點(diǎn)被賦予的權(quán)重和類別分布情況得到?jīng)Q策樹(shù)的判定結(jié)果。最后在UCI數(shù)據(jù)集上驗(yàn)證算法的有效性。

1 隨機(jī)森林相關(guān)理論

1.1 屬性重要度

眾所周知，決策樹(shù)中的屬性為條件屬性，屬性的重要性對(duì)最終的決策結(jié)果有一定的影響[8]。屬性重要度概念是指所有條件屬性集中，屬性對(duì)信息增益貢獻(xiàn)的重要性對(duì)比結(jié)果。

傳統(tǒng)的信息增益公式中，分支結(jié)點(diǎn)中包含的樣本數(shù)越多，則給分支結(jié)點(diǎn)賦予的權(quán)重越大[9]。針對(duì)此種情況，本文定義屬性重要度的計(jì)算公式如下

(1)

其中，訓(xùn)練集D={(x1,y1),…,(xi,yi),…,(xm,ym)}，xi為一個(gè)樣本，yi為xi所對(duì)應(yīng)的類別，總類別數(shù)為m。Dv為屬性a的V個(gè)可能取值{a1,a2,…,aV}中，第v個(gè)分支結(jié)點(diǎn)包含在D中的取值為av的樣本。|D|為訓(xùn)練集D中數(shù)據(jù)的個(gè)數(shù)，|Dv|為數(shù)據(jù)集Dv中數(shù)據(jù)的個(gè)數(shù)。L(a)為屬性a具有的不同屬性值的個(gè)數(shù)。而Ent(D)為信息熵，文獻(xiàn)[10]已給出信息熵的定義[10]。

1.2 隨機(jī)森林算法

隨機(jī)森林是一種以決策樹(shù)為基學(xué)習(xí)器的集成學(xué)習(xí)算法，它的特點(diǎn)之一就是在決策樹(shù)的訓(xùn)練過(guò)程中利用了隨機(jī)屬性選擇[11]。文獻(xiàn)[12]表明隨機(jī)森林的分類錯(cuò)誤率與任意兩棵決策樹(shù)的相關(guān)性和每棵決策樹(shù)的分類能力是密切關(guān)聯(lián)的[12]。文獻(xiàn)[12]也指出到目前為止，關(guān)于兩者關(guān)系對(duì)隨機(jī)森林性能影響的研究很少。

隨機(jī)森林中每棵決策樹(shù)的生成過(guò)程都有兩個(gè)特點(diǎn)：隨機(jī)且有放回地從訓(xùn)練集中選擇訓(xùn)練樣本作為訓(xùn)練集和隨機(jī)地從屬性特征中選擇特征子集，并且生成的每棵決策樹(shù)都完全生長(zhǎng)，沒(méi)有剪枝過(guò)程。

決策樹(shù)通過(guò)將數(shù)據(jù)集劃分為更小和更同質(zhì)的子集，以分而治之的方式工作。屬性的選擇是完全隨機(jī)的，這就說(shuō)明每一個(gè)屬性被選擇的概率是相等的。事實(shí)上，數(shù)據(jù)集的遞歸劃分意味著較低級(jí)別的子集具有非常少的實(shí)例。在某些數(shù)據(jù)集中，特定節(jié)點(diǎn)上的實(shí)例可以低至2-5個(gè)實(shí)例[13]，用這么少的無(wú)關(guān)緊要的數(shù)據(jù)做出可靠的決定是不可能的。

2 基于模糊決策的隨機(jī)森林算法

2.1 基本思路

隨機(jī)森林中每一個(gè)屬性的重要程度不同，對(duì)結(jié)點(diǎn)的分裂影響也不同。為了減小屬性重要度低的屬性對(duì)分類結(jié)果產(chǎn)生的消極影響，避免傳統(tǒng)的隨機(jī)森林算法中偏向選擇屬性取值多的屬性作為分裂結(jié)點(diǎn)，本文利用屬性重要度的概念，把屬性重要度作為選擇最優(yōu)劃分屬性的準(zhǔn)則，但每棵決策樹(shù)無(wú)論重要度大小，在投票時(shí)權(quán)重都相等，某些節(jié)點(diǎn)上的實(shí)例存在數(shù)量極低的情況，即屬性重要度極小的屬性。屬性重要度小的結(jié)點(diǎn)存在無(wú)法繼續(xù)分裂下去的情況，這樣就會(huì)造成此結(jié)點(diǎn)分裂不純，在這種情況下會(huì)選取數(shù)量最多的類別作為當(dāng)前葉結(jié)點(diǎn)的分類結(jié)果，而這與實(shí)際情況往往不符，影響隨機(jī)森林的分類正確率。

為了降低上述情況構(gòu)建出的決策樹(shù)對(duì)整個(gè)模型的影響，本文結(jié)合屬性重要性的計(jì)算方式，對(duì)屬性重要度值排序，設(shè)置屬性重要度的閾值，舍去部分重要度較低的屬性，把明確決策樹(shù)(即完全生長(zhǎng)的決策樹(shù))轉(zhuǎn)化為模糊決策樹(shù)。由此去掉了無(wú)法繼續(xù)分裂的不純?nèi)~結(jié)點(diǎn)，減小了重要度低的屬性對(duì)最后分類結(jié)果的干擾，使其父結(jié)點(diǎn)變?yōu)槿~子結(jié)點(diǎn)，得到一棵新的決策樹(shù)。在新的決策樹(shù)中，對(duì)葉子結(jié)點(diǎn)中的各個(gè)類別賦予相應(yīng)的權(quán)重，根據(jù)權(quán)重和此葉子結(jié)點(diǎn)上的類別分布情況，計(jì)算得到能夠判定樣本類別的模糊概率。由此遞歸地構(gòu)造多棵決策樹(shù)，根據(jù)這些決策樹(shù)的投票結(jié)果，得到最后的分類結(jié)果，進(jìn)行隨機(jī)森林算法的優(yōu)化，提高分類正確率。

2.2 具體步驟

基于模糊決策的隨機(jī)森林優(yōu)化算法的核心分為兩部分，類別分布矩陣和模糊概率。

(1)類別分布矩陣

(2)模糊概率p(x)

p(x)=w(yi)·X

(2)

最大模糊概率P(x)為

P(x)=argmax{p(x)}

(3)

(3)算法的具體步驟

輸入：

訓(xùn)練集D={(x1,y1),…,(xi,yi),…,(xm,ym)}，迭代次數(shù)為B

輸出：優(yōu)化后的隨機(jī)森林分類器F′(x)

步驟1 利用bootstrap方法從訓(xùn)練集中重采樣隨機(jī)選出n個(gè)樣本；

步驟2 在所有樣本上，通過(guò)調(diào)用以下步驟遞歸地構(gòu)造模糊決策樹(shù)。當(dāng)達(dá)到預(yù)設(shè)閾值或葉子結(jié)點(diǎn)內(nèi)只包含同一類別時(shí)停止生長(zhǎng)，生成模糊決策樹(shù)Tb(1≤b≤B)：

(1)從所有屬性中隨機(jī)選擇出p個(gè)屬性；

(2)根據(jù)屬性重要度式(1)計(jì)算出屬性重要度值，從而在p個(gè)屬性中選擇具有最大屬性重要度值的屬性作為最佳屬性/分裂點(diǎn)；

(3)根據(jù)最佳屬性/分裂點(diǎn)，將結(jié)點(diǎn)拆分成子結(jié)點(diǎn)；

(4)計(jì)算所有屬性重要度值的均值，將其設(shè)為閾值，對(duì)比屬性重要度的值與閾值的大小，去掉屬性重要度低的結(jié)點(diǎn)，得到模糊決策樹(shù)；

(5)計(jì)算模糊決策樹(shù)中葉子結(jié)點(diǎn)的類別分布矩陣X；

(6)計(jì)算類別占比，得到權(quán)重w(yi)(1≤i≤m)，根據(jù)式(2)，計(jì)算出模糊概率p(x)；

(7)根據(jù)式(3)得到最大模糊概率P(x)，進(jìn)行此棵模糊決策樹(shù)的類別判定。

(4)

其中，F(xiàn)b(x)為第b個(gè)決策樹(shù)的類預(yù)測(cè)，majorityvote為投票結(jié)果的最大值。

(4)算法代碼描述

Input: 訓(xùn)練集D={(x1,y1),…,(xm,ym)}，決策樹(shù)棵樹(shù)B

Output: FRF分類器F′(x)

步驟1 計(jì)算屬性重要度gain*。

def gain*(D):

return gain_node;

步驟2 決策樹(shù)Fb(x)。

def decision_tree(D)：

if len(set (classList)) == 1:

return classList[0];

bestFeat = gain*(D);

threshold = average(bestFeat);

if bestFeat < threshold：

del(sub_names[ bestFeat ]);

length = len(y);

class_1 = y.tolist().count(class_type[ 0 ]);

class_2 = y.tolist().count(class_type[ 1 ]);

class_1_ratio = class_1/length；

class_2_ratio = class_2/length；

class_1_proba =

class_2_ratio*y_pred_proba[：， 0 ];

class_2_proba =

class_1_ratio*y_pred_proba[：， 1 ];

result=np.column_stack((

class_1_proba,class_2_proba));

Fb(x)= { result:{}};

return Fb(x);

步驟3 FRF分類器。

def random_forest(count)：

for i in range(count)：

decision_tree(x,y,X_test);

return F’(x);

從以上偽代碼中可以看出時(shí)間復(fù)雜度為o(n)，算法的改進(jìn)并沒(méi)有增加傳統(tǒng)隨機(jī)森林算法的時(shí)間復(fù)雜度。

2.3 實(shí)例分析

在對(duì)隨機(jī)森林算法進(jìn)行優(yōu)化后，以“影響去打網(wǎng)球的因素”為例對(duì)其進(jìn)行分析，對(duì)優(yōu)化后的算法過(guò)程做進(jìn)一步的闡述。其中，采用表1數(shù)據(jù)集：氣象數(shù)據(jù)集，都是標(biāo)稱屬性(outlook、temperature、humidity、windy、play)[14]。

表1 氣象數(shù)據(jù)集

下面利用屬性重要度作為最佳屬性/分裂點(diǎn)構(gòu)建決策樹(shù)，對(duì)優(yōu)化后的隨機(jī)森林算法步驟進(jìn)行簡(jiǎn)析：

(1)根據(jù)式(1)計(jì)算屬性重要度，對(duì)屬性重要度的值進(jìn)行排序，找到最佳屬性/分裂點(diǎn)，每次選擇分裂結(jié)點(diǎn)的屬性重要度值gain*見(jiàn)表2，遞歸地執(zhí)行此步驟，直到葉結(jié)點(diǎn)不能繼續(xù)分裂，進(jìn)而構(gòu)建一棵完全生長(zhǎng)的決策樹(shù)；

表2 最佳分裂屬性選擇gain*值

(2)設(shè)置屬性重要度閾值，此例中為-0.5，根據(jù)閾值，去掉重要度小于此值的結(jié)點(diǎn)，得到一棵模糊決策樹(shù)，如圖1所示，為了便于敘述，設(shè)置編號(hào)結(jié)點(diǎn)Node，其中samples代表樣本數(shù)量，value代表分類結(jié)果；

圖1 模糊決策樹(shù)

(6)將每棵模糊決策樹(shù)的對(duì)應(yīng)類別的模糊概率相加，根據(jù)式(3)得到最大模糊概率；

(7)最后由式(4)得到最后決策結(jié)果。

圖1是通過(guò)屬性重要度得到的結(jié)果，圖1的overlook屬性更遠(yuǎn)離根結(jié)點(diǎn)，從而彌補(bǔ)了原始算法偏向選擇屬性值較多的屬性的不足，并且根據(jù)設(shè)置的屬性重要度的閾值，降低了屬性重要度低的屬性對(duì)分類結(jié)果的影響。

3 實(shí)驗(yàn)驗(yàn)證及分析

3.1 實(shí)驗(yàn)描述

本文實(shí)驗(yàn)硬件平臺(tái)采用Intel(R) Core(TM) i5-6200U型號(hào)CPU和8 GB內(nèi)存的PC機(jī)；代碼執(zhí)行平臺(tái)為Windows 10，Python 3.6，算法實(shí)現(xiàn)采用Python語(yǔ)言。在本次實(shí)驗(yàn)中，設(shè)置決策樹(shù)的棵數(shù)的參數(shù)值為100，屬性重要度的閾值為計(jì)算出的屬性重要度的均值。

為了方便比較和分析，在UCI數(shù)據(jù)集中選取了6個(gè)不同數(shù)量、不同屬性個(gè)數(shù)的二分類數(shù)據(jù)集，表3中列出了這些數(shù)據(jù)集的分布情況。

表3 取自UCI的實(shí)驗(yàn)數(shù)據(jù)匯總

為了說(shuō)明FRF算法的改進(jìn)效果，本文實(shí)驗(yàn)分別驗(yàn)證傳統(tǒng)的RF算法，文獻(xiàn)[5]提出的CRF算法與本文提出的FRF算法。

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

在每個(gè)數(shù)據(jù)集上，為了增加實(shí)驗(yàn)結(jié)果的可信度，采用交叉驗(yàn)證的方法，將數(shù)據(jù)平均分成9份，每次用其中8份做訓(xùn)練，1份做測(cè)試，循環(huán)8次，統(tǒng)計(jì)平均正確率，結(jié)果見(jiàn)表4，表5和表6。

表4 傳統(tǒng)RF算法正確率結(jié)果

3組實(shí)驗(yàn)下的平均正確率折線圖比較如圖2所示。

從圖2中可以看出，通過(guò)類別分布得到權(quán)重，再根據(jù)普通決策樹(shù)的屬性重要度設(shè)置閾值，去掉了重要度低的屬性，從而將決策樹(shù)的單一決策結(jié)果轉(zhuǎn)化為多類分布結(jié)果。進(jìn)而改善了分裂不純的葉節(jié)只選擇數(shù)量多的類別作為分類結(jié)果的情況，修正決策樹(shù)誤判的結(jié)果，消除了屬性重要度較低的屬性對(duì)決策樹(shù)分類造成的負(fù)面影響，使改進(jìn)后的隨機(jī)森林算法的測(cè)試結(jié)果正確率高于傳統(tǒng)的隨機(jī)森林產(chǎn)生的測(cè)試結(jié)果。

表5 CRF算法正確率結(jié)果

表6 FRF算法正確率結(jié)果

圖2 實(shí)驗(yàn)平均正確率對(duì)比

為了驗(yàn)證FRF算法的有效性，計(jì)算出測(cè)試集數(shù)據(jù)的查準(zhǔn)率、查全率，公式如下。其中，TP為真正例，F(xiàn)P為假正例，TN為真反例，F(xiàn)N為假反例。

查準(zhǔn)率

(5)

查全率

(6)

利用式(5)和式(6)計(jì)算查準(zhǔn)率和查全率的數(shù)據(jù)見(jiàn)表7。

表7 查準(zhǔn)率和查全率結(jié)果

以查準(zhǔn)率為縱軸、查全率為橫軸，得到的“P-R曲線”，如圖3所示?！癙-R曲線”圖的定義請(qǐng)參見(jiàn)文獻(xiàn)[10]。

圖3 P-R曲線

由P-R圖可直觀地看出各算法在總體樣本上的查準(zhǔn)率、查全率。文獻(xiàn)[10]指出進(jìn)行比較的學(xué)習(xí)器，性能優(yōu)的學(xué)習(xí)器的P-R曲線會(huì)“包住”另一個(gè)學(xué)習(xí)器的曲線[10]。由圖3可以看出本文提出的FRF算法總體上有了一定的性能提升。對(duì)于查全率而言，性能指標(biāo)有了一定的下降，但這是一個(gè)正常的情況。在一個(gè)分類器中，想要更高的查準(zhǔn)率，那么閾值要設(shè)置的更高，只有這樣才能有較高的把握確定預(yù)測(cè)的正例是真正例。一旦把閾值設(shè)置高了，則預(yù)測(cè)出正例的樣本數(shù)就少了，那真正例數(shù)就更少了，查不全所有的正樣例，這就導(dǎo)致了查準(zhǔn)率較高的情況下，查全率會(huì)較低一些。

根據(jù)以上圖表數(shù)據(jù)可以得到，優(yōu)化后的隨機(jī)森林算法相比較于文獻(xiàn)[5]中提出的CRF算法和傳統(tǒng)的隨機(jī)森林算法在Breast、Ecoli、Bupa、Heart、IonoSphere及Spect這6個(gè)數(shù)據(jù)集上均取得了最優(yōu)分類正確率，充分展示了FRF算法對(duì)高維數(shù)據(jù)集的分類能力。實(shí)驗(yàn)結(jié)果表明，本文提出的基于模糊決策的隨機(jī)森林算法較好提高了隨機(jī)森林分類正確率，在性能評(píng)價(jià)指標(biāo)查準(zhǔn)率和查全率的結(jié)果分析圖中也得出了優(yōu)化后的隨機(jī)森林算法性能有了一定的提高。

4 結(jié)束語(yǔ)

為了使隨機(jī)森林算法具有更高的分類正確率，降低重要度低的屬性對(duì)整個(gè)模型的影響，本文在屬性重要度構(gòu)建決策樹(shù)的基礎(chǔ)上，對(duì)屬性重要度設(shè)置了閾值，由此得到一棵模糊決策樹(shù)。又根據(jù)類別占比得到的權(quán)重，修正決策樹(shù)誤判的結(jié)果，降低了重要度低的屬性對(duì)決策樹(shù)分類結(jié)果的影響，提高了傳統(tǒng)隨機(jī)森林算法的分類正確率。本文提出的優(yōu)化算法較好適用于樣本數(shù)據(jù)分布不均勻的分類問(wèn)題，該算法在實(shí)驗(yàn)中取得了較好的結(jié)果。雖然優(yōu)化后的隨機(jī)森林算法在正確率上有了一定的提升，但在研究中我們也發(fā)現(xiàn)屬性重要度閾值對(duì)隨機(jī)森林性能的優(yōu)化有一定的影響，在今后的工作中，我們會(huì)對(duì)上述參數(shù)繼續(xù)進(jìn)行研究，以達(dá)到更好的優(yōu)化效果。