基于模糊決策的隨機森林算法

史金余，楊澤宇，謝 兄

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

0 引 言

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

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

1.1 屬性重要度

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

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

(1)

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

1.2 隨機森林算法

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

隨機森林中每棵決策樹的生成過程都有兩個特點：隨機且有放回地從訓練集中選擇訓練樣本作為訓練集和隨機地從屬性特征中選擇特征子集，并且生成的每棵決策樹都完全生長，沒有剪枝過程。

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

2 基于模糊決策的隨機森林算法

2.1 基本思路

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

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

2.2 具體步驟

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

(1)類別分布矩陣

(2)模糊概率p(x)

p(x)=w(yi)·X

(2)

最大模糊概率P(x)為

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

(3)

(3)算法的具體步驟

輸入：

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

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

步驟1 利用bootstrap方法從訓練集中重采樣隨機選出n個樣本；

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

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

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

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

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

(5)計算模糊決策樹中葉子結(jié)點的類別分布矩陣X；

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

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

(4)

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

(4)算法代碼描述

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

Output: FRF分類器F′(x)

步驟1 計算屬性重要度gain*。

def gain*(D):

return gain_node;

步驟2 決策樹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);

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

2.3 實例分析

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

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

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

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

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

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

圖1 模糊決策樹

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

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

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

3 實驗驗證及分析

3.1 實驗描述

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

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

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

為了說明FRF算法的改進效果，本文實驗分別驗證傳統(tǒng)的RF算法，文獻[5]提出的CRF算法與本文提出的FRF算法。

3.2 實驗結(jié)果及分析

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

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

3組實驗下的平均正確率折線圖比較如圖2所示。

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

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

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

圖2 實驗平均正確率對比

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

查準率

(5)

查全率

(6)

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

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

以查準率為縱軸、查全率為橫軸，得到的“P-R曲線”，如圖3所示?！癙-R曲線”圖的定義請參見文獻[10]。

圖3 P-R曲線

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

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

4 結(jié)束語

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