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

史金余，楊澤宇，謝 兄

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

0 引 言

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

1 隨機森林相關理論

1.1 屬性重要度

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

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

(1)

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

1.2 隨機森林算法

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

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

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

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

2.1 基本思路

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

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

2.2 具體步驟

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

(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)}，迭代次數為B

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

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

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

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

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

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

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

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

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

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

(4)

其中，Fb(x)為第b個決策樹的類預測，majorityvote為投票結果的最大值。

(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)，算法的改進并沒有增加傳統隨機森林算法的時間復雜度。

2.3 實例分析

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

表1 氣象數據集

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

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

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

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

圖1 模糊決策樹

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

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

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

3 實驗驗證及分析

3.1 實驗描述

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

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

表3 取自UCI的實驗數據匯總

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

3.2 實驗結果及分析

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

表4 傳統RF算法正確率結果

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

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

表5 CRF算法正確率結果

表6 FRF算法正確率結果

圖2 實驗平均正確率對比

為了驗證FRF算法的有效性，計算出測試集數據的查準率、查全率，公式如下。其中，TP為真正例，FP為假正例，TN為真反例，FN為假反例。

查準率

(5)

查全率

(6)

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

表7 查準率和查全率結果

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

圖3 P-R曲線

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

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

4 結束語

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