基于屬性相容性的隨機森林算法

劉 毓, 劉 陸, 高 尹, 楊 柳

(西安郵電大學 通信與信息工程學院, 陜西 西安 710121)

隨機森林算法[1]具有較低泛化誤差和較好收斂性，可解決決策樹的局部最優(yōu)解和過度擬合問題，已成為數(shù)據(jù)分析、圖像處理、知識管理等眾多領域的研究熱點之一。

隨機森林算法的基分類器為決策樹[2]，改進單個基分類器的分類準確率可以提高整個隨機森林算法的分類準確率。通過遺傳算法尋找參數(shù)最優(yōu)組合的方法，提高了算法的分類性能，但算法的收斂速度依賴于初值設定[3-4]。給抽樣結(jié)果增加約束條件，非平衡數(shù)據(jù)的分類性能有所提高，但是算法訓練速度較慢[5]。采用決策協(xié)調(diào)度作為劃分規(guī)則分裂節(jié)點，根據(jù)條件屬性與目標屬性等價類模的比值衡量該屬性的分類能力，雖然基分類器的性能有一定的提升，但仍然存在模糊問題[6]。因此，針對上述問題，本文以決策協(xié)調(diào)度為基礎，從條件屬性與目標屬性間的邏輯關系入手，引入粗糙集理論[7]中屬性相容性[8]，以條件屬性的相容度作為基分類器分裂節(jié)點的準則，用寬相容度輔助嚴相容度構(gòu)建基分類器，以期提高基分類性能，進而改善隨機森林算法性能。

1 隨機森林算法基本原理

隨機森林算法根據(jù)Bagging抽樣模型[9]，采用有放回的隨機采樣方式進行采樣，生成K個子訓練集，再從每個子訓練集的所有屬性中選取特征子空間[10]。特征子空間的大小影響了隨機性的引入程度，一般取值為 log2M+1，M為特征總數(shù)。將選取特征子空間后的K個子訓練集建立K個基分類器，從而形成隨機森林，如圖1所示。每個基分類器任其生長，不需要剪枝[11]。基分類器一般采用ID3[12]或C4.5[13]算法。當輸入測試樣本時，隨機森林輸出的分類結(jié)果由每個基分類器的輸出結(jié)果進行簡單投票決定。

圖1 隨機森林示意圖

設隨機森林模型為{h(X,θk),k=1,2,…,K}，其中，h(·)為單個基分類器，K為基分類器的總個數(shù)，X為樣本條件屬性集，θk為基分類器參數(shù)。樣本集為T={(xi,yi):xi∈X,yi∈Y,i=1,2,…,N}，其中N為樣本容量，Y為決策屬性。

輸入樣本X對應的正確分類結(jié)果Y的得票數(shù)，超過其他錯誤分類別中得票數(shù)最多者的程度可用余量函數(shù)表示為

(1)

其中，I(·)為指示函數(shù)，當·為真時，取值為1;當·為假時，取值為0。

根據(jù)隨機森林投票的特點，對給定樣本分類的錯誤率的度量，利用泛化誤差[14]表示為

e=P[m(X,Y)<0]。

(2)

其中，P(·)為概率質(zhì)量函數(shù)。

式(2)結(jié)合Hoeffding不等式[15]與Chebyshev不等式[16]，得到隨機森林的泛化誤差界[13]

(3)

2 屬性相容度基礎理論

對于基分類器偏向選擇多值屬性的問題，可根據(jù)屬性相容度進行改進，屬性相容度以決策協(xié)調(diào)度為基礎。

2.1 信息系統(tǒng)

決策表{U,A∪D,V,f}為一個信息系統(tǒng)[17]，其中U為全部對象的集合，為論域；A為條件屬性集合；D為目標屬性集合；V=∪a∈AVa是屬性a的值域，即條件屬性所有取值的集合；f:U×A→V為信息函數(shù)，它的作用是將U中所有對象的每個元素都映射為屬性值，即?a∈A,x∈U,f(x,a)∈Va。

2.2 等價關系與不可區(qū)分關系

信息系統(tǒng)可以簡化表示為(U,R)，R為等價關系[18]，一個屬性可以作為一個等價關系，信息系統(tǒng)可以看作是一個等價關系族。U/R表示一個等價類集，即所有元素在等價關系構(gòu)成的集合。

設存在非空等價關系Z，Z是等價關系R的子集，各個子集Z的交集也是等價關系，此關系為不可區(qū)分關系，用O(Z)表示。在O(Z)下的等價類是信息系統(tǒng)中最小的單元。

2.3 決策協(xié)調(diào)度

等價類U/(A,D)表示條件屬性集與目標屬性集的交集，它的模用|A∪D|表示，作為一個測度顯示A→D的邏輯關系強弱，也是決策規(guī)則出現(xiàn)的次數(shù)，即頻度。決策協(xié)調(diào)度[17]的表達式為

(4)

其中，X是A的非空屬性子集，|·|是求模運算。

屬性決策協(xié)調(diào)度的值越大，則表示該屬性重要程度越高。

3 基于屬性相容度的改進算法

隨機森林的性能取決于基分類器性能，基分類器的性能越高，隨機森林的性能越強。改進算法以決策協(xié)調(diào)度為基礎，從隨機森林的基分類器入手。決策協(xié)調(diào)度只在宏觀上做了處理，各個決策規(guī)則在相容關系上還有待提高，當各個條件屬性間的協(xié)調(diào)度距離較小時，決策依據(jù)不足。因此，需先計算主決策集與次決策集，再構(gòu)建屬性相容度[18]，利用屬性相容度作為劃分規(guī)則。

3.1 主決策集與次決策集

設在決策表中存在條件屬性集C∈A,O(C)={c1,c2,…,cm}與決策屬性集D，O(D)={d1,d2,…,dL}，則在O(C,D)中，與決策規(guī)則C→di矛盾的集合是∪i≠jC→dj。依次對O(C,D)下的集合求模運算，模值最大集合為主決策集，記作W；模值次大的集合為次決策集，記作B。

3.2 屬性相容度

設主決策集的模為|W|，次決策集的模為|B|，定義屬性相容度的表達式為

(5)

其中，X為C的非空子集。B對W的影響為嚴相容度。

W與B間呈矛盾關系。當|W|與|B|的值相等時，將式(5)中次決策集舍去，屬性相容度又可表示為

(6)

將次決策集舍去，只考慮主決策集的影響，則為寬相容度。

在比較屬性相容度時，若嚴相容度相同且同為最大值，則需要進一步計算寬相容度并進行比較，從而將條件屬性的性能嚴格區(qū)分。屬性相容度也可以用決策規(guī)則出現(xiàn)的概率度量該規(guī)則邏輯關系的強弱，概率值越大，表示該條件屬性與目標屬性間的邏輯關系就越強，則該屬性就越重要。主決策集與次決策集的定義都是與一個條件屬性下的某個決策規(guī)則出現(xiàn)的頻度有關。然而，這兩個決策相互矛盾。在度量條件屬性與目標屬性邏輯關系強弱時，有必要將矛盾的規(guī)則剔除或是計算兩者之差。對于一個條件屬性而言，屬性相容度越大，決策規(guī)則邏輯關系越強，分類能力越好。

3.3 改進算法步驟

通過嚴相容度與寬相容度的計算，能夠區(qū)分不同條件屬性，從而提高基分類器的分類能力。通過嚴相容度計算條件屬性的分類能力就可以選擇分裂節(jié)點。在特殊情況下，會出現(xiàn)條件屬性嚴相容度相同的情形，且這些條件屬性的相容度都大于其他條件屬性相容度，此時計算寬相容度可將其區(qū)分。

算法的具體步驟如下。

步驟1 采用有放回的隨機采樣方式進行訓練集采樣，生成K個子訓練集。

步驟2 取出1個子訓練集，對該子集選取特征子空間，以此作為1個基分類器的訓練集。

步驟3 基分類器訓練開始，對訓練集的數(shù)據(jù)初始化操作，將所有條件屬性進行標記。

步驟4 分別計算出各個條件屬性的主決策集的模值與次決策集的模值。

步驟5 利用式(5)計算所有條件屬性的相容度。若存在兩個的屬性相容度的值近似且為最大值，則利用式(6)進行計算。

步驟6 選出分類性能最強的條件屬性，并將該屬性的標記去除，將該屬性作為分裂節(jié)點加入生成模型來分隔樣本集。

步驟7 重復步驟5和步驟6，直到所有屬性都去除標記或達到葉子節(jié)點。

步驟8 生成并存儲該基分類器模型。

步驟9 重復步驟2～步驟8，直至K個基分類器全部生成完畢，結(jié)束。

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

4.1 數(shù)據(jù)集選取

選取UCI公開數(shù)據(jù)集[19]中的Monks數(shù)據(jù)集、House-votes-84數(shù)據(jù)集、Credit-A數(shù)據(jù)集、Tic-tac-toe數(shù)據(jù)集和Kr-vs-kp數(shù)據(jù)集作為實驗數(shù)據(jù)。其中，Monks數(shù)據(jù)集的樣本數(shù)為432個，條件屬性個數(shù)為6個。House-votes-84數(shù)據(jù)集的樣本數(shù)為435個，條件屬性個數(shù)為16個。Credit-A數(shù)據(jù)集的樣本數(shù)為690個，條件屬性個數(shù)為15個。Tic-tac-toe數(shù)據(jù)集的樣本數(shù)為958個，條件屬性個數(shù)為9個。Kr-vs-kp數(shù)據(jù)集的樣本數(shù)為3 196個，條件屬性個數(shù)為36個。以上5個數(shù)據(jù)集所有屬性的取值均為離散值。

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

實驗運行環(huán)境為中央處理器Intel (R) Core (TM) i3-3217U,主頻1.8 GHz,內(nèi)存4 GB的PC機, Win7 64位操作系統(tǒng), Matlab版本9.0 (R2016b)。根據(jù)上述5種數(shù)據(jù)集，分別對比改進算法、隨機森林算法[1]與文獻[5]算法的準確率和運行時間，準確率對比結(jié)果如表1所示，運行時間對比結(jié)果如表2所示。

表1 準確率對比結(jié)果/%

從表1可以看出，改進算法對5種數(shù)據(jù)集的決策準確率均高于其他兩種算法。在Monks數(shù)據(jù)集上，改進算法提高了近11%，比文獻[5]算法提高了3.2%；在House-votes-84數(shù)據(jù)集上，改進算法提高5.5%，比文獻[5]算法提高了2.7%。表明在訓練數(shù)據(jù)量較少時，改進算法有明顯的優(yōu)勢。這是由于改進算法充分利用了條件屬性與目標屬性的邏輯關系，采用屬性的相容度作為分裂節(jié)點判決依據(jù)，從而得到更高的準確率。對于大數(shù)據(jù)集，改進算法的準確率也有所提高。

表2 運行時間對比結(jié)果/s

從表2可以看出，改進算法的計算復雜度均低于其它兩種算法。改進算法繼承了隨機森林處理高維數(shù)據(jù)、特征遺失數(shù)據(jù)和不平衡數(shù)據(jù)的優(yōu)點。

除了準確率外，查準率、查全率以及綜合分類率以也是衡量算法性能的重要指標[20]。計算以上性能指標需要將樣例的真實類別與預測類別的組合劃分為真正例、假正例、真反例和假反例等4種情形[21]。

以Monks數(shù)據(jù)為例，3種算法對真實類別與預測類別組合劃分的統(tǒng)計結(jié)果如表3所示。

表3 3種算法統(tǒng)計結(jié)果

真正例與假反例的數(shù)量越多，算法的性能越好，從表3中可以看出不同算法分類結(jié)果的個數(shù)。但僅憑個數(shù)，無法準確描述算法的優(yōu)劣，還需要進一步對比查準率、查全率和綜合分類率等3種性能，結(jié)果如表4所示。

表4 3種算法性能對比結(jié)

從表4可以看出，改進算法綜合性能最好，在查準率保持一定的情況下，查全率得到很大的提升，95%有用信息被留下。對于處理海量數(shù)據(jù)時，引入粗糙集的改進隨機森林算法只需要計算各個等價類交集的模值，省去大量對數(shù)運算，降低計算的復雜度，提高訓練速度，從而提高學習效率。

5 結(jié)語

基于屬性相容度的隨機森林算法，重新構(gòu)建了用以度量條件屬性的重要程度數(shù)學表達式，引入了屬性相容性，并用屬性的相容度代替?zhèn)鹘y(tǒng)算法中的信息增益作為新的劃分規(guī)則，從而提高了基分類性能，改善了隨機森林算法性能。實驗結(jié)果表明，改進算法對數(shù)據(jù)量較少時具有更高的準確率，并且弱化了多值偏向問題，此外也不需要進行對數(shù)運算；在處理海量數(shù)據(jù)時，具有更快的訓練速度。改進算法在繼承了隨機森林優(yōu)點的前提下，不僅提高了預測準確率而且降低了計算復雜度。