基于節點匹配代價優化的隨機森林算法

朱 瑛，謝 睿，鄭若池

(沈陽航空航天大學 機電工程學院，遼寧 沈陽 110136)

0 引 言

近年來，隨著隨機森林算法的研究和應用越來越多，如何提高隨機森林的分類精度已然成為了研究的熱點。作為一種以決策樹為基學習器的有監督的集成學習算法[1]，決策樹的數量和決策樹間的多樣性對隨機森林的分類精度有著重大影響[2]。研究過程中發現，過多的決策樹，不僅不能有效地提升分類精度，反而會增加隨機森林訓練的時間，因此越來越多的學者開始圍繞如何提升隨機森林中決策樹的多樣性進行研究。薛銘龍等[3]通過設置不同的懲罰項因子來保證在訓練隨機森林中生成結構不同的決策樹。關曉薔等[4]通過為不同的類別設置不同側重的基分類器，使產生的決策樹結構盡可能的不同。王誠等[5]以Kappa的統計量作為決策樹間相似度的判別依據，對隨機森林中的決策樹進行有選擇的保留。Mashayekhi等[6]基于爬山策略的貪婪方法，增刪若干決策樹來確保隨機森林的多樣性。上述改進算法均能有效增加隨機森林的多樣性，提升隨機森林的分類精度，但是在隨機森林的訓練中改變決策樹的結構，會增加算法的復雜性。增刪決策樹，雖然計算簡單，但會導致隨機森林陷入局部最優。因此在實際應用中，需要一種簡單高效的方法來計算出決策樹間的相關性，豐富隨機森林的多樣性，進而提升隨機森林的分類精度。

本文基于決策樹的分支節點信息，以決策樹節點間的最高匹配代價作為兩個決策樹間的相似度，構建決策樹間的相似度矩陣，結合相似度矩陣對隨機森林中的決策樹進行聚類分析，保留每類中Kappa系數最高的決策樹構建新的隨機森林，并利用Kappa系數對保留的決策樹進行加權處理，進一步弱化分類精度差的決策樹對分類結果的影響。

1 決策樹的相似度

隨機森林是以決策樹為基分類器，通過統計每個決策樹分類輸出結果的眾數來得出隨機森林的分類結果，因此決策樹之間的相似度對隨機森林的分類精度有著巨大的影響[7]。隨機森林的多樣性越豐富，分類結果的可信度越高，在一定程度上增加隨機森林中決策樹的數量能有效地豐富隨機森林的多樣性，提高隨機森林分類的精度，但是過多的決策樹數量，會增加算法計算的時間，同時增加過多的決策樹會隨機引入更多分類精度差的決策樹，影響隨機森林的分類性能。因此，通過對隨機森林中決策樹之間的相關性進行分析，增加隨機森林的多樣性，能有效地提升隨機森林的分類精度。

本文在Perner[8]所提出的對比決策樹分支結構來計算相似度的基礎上進行研究。在隨機森林中決策樹均為自由生長，不剪枝，若匹配決策樹的分支結構會增大計算負擔，且會弱化兩個子規則相似，結構不同的決策樹之間的相似度。為此本文提出通過計算節點間的匹配代價來評估兩個決策樹之間的相似度。相對于計算分支結構，通過比對節點屬性信息的方法計算量更小，方法更簡單，通過形成決策樹節點間代價矩陣，以最高總匹配代價的均值作為決策樹之間的相似度能更好評估出具有相同結構或相同節點的兩棵決策樹之間的相似度。決策樹之間相似度的計算步驟如下：

步驟1 通過Bootstrap法對原訓練集進行重采樣，建立與原訓練集大小一致的新訓練集，并對新生成的訓練集每一列單獨進行歸一化處理。

步驟2 對每個訓練子集訓練得出與之對應的決策樹，并記錄下每個決策樹的根節點，內部節點的位置以及其對應的分裂節點屬性X和分裂值T。

步驟3 統計兩個決策樹中的分支節點數量為N1和N2，選取兩個決策樹中分支節點數量最大的值作為n。在兩個決策樹中任意選取兩個分支節點，構建兩個決策樹節點間n×n維的代價矩陣Sim_node

(1)

節點間匹配代價的計算規則如下：

(1)當決策樹Tree1的分支節點數N1

(2)當決策樹節點屬性為離散屬性時，先判斷決策樹Tree1中的分裂節點與決策樹Tree2中分裂節點的屬性值是否一致。若屬性值不一致，Sim.n=0。若屬性值一致，Sim.n=1

(2)

M=|Ttree1.node1-Ttree2.node2|

(3)

(4)

步驟4 通過分裂節點的相似度矩陣Sim_node，計算出兩個決策樹中任意兩節點間匹配代價之和最高的組合，即在每一行(列)中找出一個值，Sim(k)=Sim.n(i,j)(i,j,k∈(1,2,3…n))，其中i和j的取值均不重復，從所有組合中通過匈牙利匹配算法找出使Sim(k) 之和最大的組合，即找出兩個決策樹節點間匹配的最大值，使總匹配代價最高，并將得到的總的匹配代價均分到n個節點上，即得出兩個決策樹之間的相似度Sim.t

(5)

步驟5 在隨機森林中任意選取兩個決策樹Tree1和Tree2。通過上述方法，計算兩個決策樹之間的相似度，構建決策樹間的相似度矩陣Sim_tree

(6)

決策樹的多樣性可由相似度矩陣的統計量V來判定，當V的值越大時，決策樹的多樣性越大，分類的精度也越高，分類結果的可信度越高；反之，當V的值越小時，決策樹的多樣性越小，分類的精度越小，分類結果的可信度也就越低

(7)

式中：N——決策樹相似度矩陣中元素的總個數；S——決策樹相似度矩陣中最多的同值元素個數。

通過比較決策樹的節點信息，獲得節點間匹配代價最高值來計算決策樹間的相似度，相對于通過比較決策樹的分支規則來建立相似度的方法而言，不僅計算量更小，同時還能減小決策樹之間的類內差異度，增大決策樹之間的類間差異度，更利于對決策樹進行分類。

2 分類性能評估

分類器的性能評價準則多種多樣，常用的二分類模型的評價準則有AUC(area under curve)指標、準確率(precision)、召回率(recall)和F1分數(F1-score)等[9]，但是對于多分類問題而言，二分類模型的評價準則指標難以滿足評價要求，因此本文采用Kappa系數作為分類器性能的評價準則，來評價分類器的分類精度[10]。

計算Kappa系數，首先建立混淆矩陣(如圖1所示)，在混淆矩陣中Tn表示分類器預測值屬性與真實值屬性一致的樣本個數；Ei,j表示真實值類別屬性為類別i，而分類器的預測值類別屬性為類別j的樣本個數；sum_t(s)(s∈[1,n]) 表示各個類別真實值的樣本個數總和；sum_p(s)(s∈[1,n]) 表示各個類別預測值的樣本個數總和。

圖1 混淆矩陣

Kappa系數的計算方法如下式(8)所示

(8)

其中，Po為總體分類精度，即預測值類別與真實值類別一致的樣本數之和與樣本總數N的比值

(9)

Pe表示各預測值類別樣本數與真實值類別樣本數的乘積之和與樣本數的平方N2之間的比值

(10)

根據Kappa系數的一致性檢驗等級標準，Kappa系數的取值在[-1,1]之間，在計算過程中K取值通常在[0,1] 范圍內，當K的取值越大，一致性越高，分類精度越高，當K=1時，一致性最強，分類精度最高，K=0時，一致性與偶然誤差相同，分類精度差[11]，當K<0時，此時建立的分類模型精度最差，可舍去此類模型。

3 隨機森林算法的改進

目前決策樹常用的生成方法有ID3、C4.5、CART(classification and regression tree)等，本文中的隨機森林算法的子分類器決策樹由CART分類回歸樹構建，CART算法采用的是一種二分遞歸分割，將當前的樣本集分為兩個子樣本集，使得生成的每個非葉子節點都有兩個分支[12]，且在構建決策樹的過程中讓決策樹自由生長，不進行剪枝操作。本文采用的聚類加權隨機森林算法，通過對隨機森林中的子分類器進行聚類，以Kappa系數衡量每一個子分類器的分類精度，選出每一類中最高Kappa系數的決策樹為該類決策樹的代表，構建新的隨機森林，并以Kappa系數對每一類中決策樹的代表進行加權處理。改進的聚類加權優化隨機森林算法流程如下所示：

步驟1 對原始的訓練數據進行劃分，隨機抽取80%的原始訓練數據用作決策樹的訓練數據，構建隨機森林模型，20%的原始訓練數據用于對隨機森林模型的檢驗。

步驟2 預設決策樹數量m，利用Booststrap算法對訓練數據采樣得到的訓練集，生成決策樹，并記錄每個決策樹的分支節點位置、節點的屬性和分裂值，組合這些決策樹構建出隨機森林模型。

步驟3 計算任意兩決策樹中任意兩節點的相似度Sim.n，構建兩決策樹節點間的代價矩陣Sim_node。通過匈牙利算法，計算得出兩節點間匹配代價最高的組合。構建任意兩決策樹間的相似度矩陣Sim_tree。

步驟4 預設決策樹聚類數量Q，根據決策樹間的相似度矩陣Sim_tree，構建鄰接矩陣W、度矩陣D和拉普拉斯矩陣L，得出標準化后的拉普拉斯矩陣D-1/2*L*D-1/2。尋找出D-1/2*L*D-1/2最小的k個特征值，并計算出其特征向量f，構建出特征向量空間，利用K-means對特征向量f進行聚類。

步驟5 利用檢驗數據，得出聚類后每個類別中決策樹的Kappa系數，選取每個類別中Kappa系數最高的決策樹重新組建新的隨機森林模型，并以Kappa系數為權重對新隨機森林中每棵決策樹進行加權處理。

4 實驗結果分析

本文實驗所采用的軟件為MATLAB R2014，處理器為Intel(R) Xeon(R) CPU E5-1607 V2 @3.GHz，實驗所采用的數據集從加州大學歐文分校(University of California Irvine，UCI)的機器學習數據庫中選取。包括Gazi大學醫學院博士Nilsel Ilter 提供的皮膚病學數據庫(Dermatology Database)：利用臨床數據和組織病理學屬性用于對皮膚病進行分類；威斯康星大學提供的乳腺腫瘤診斷數據集(Breast Cancer Wisconsin (Diagnostic) Data Set)：通過對病灶組織的細胞核量化特征識別，分析對乳腺癌進行診斷；葡萄牙波爾圖大學醫學院提供的胎兒心臟圖(CTG)并通過產科專家的診斷得到的特征數據集(Cardiotocography Data Set)：通過對胎兒心率(FHR)和子宮收縮(UC)特征等形態學模式分析，判斷胎兒的狀態。實驗數據集的信息見表1。

表1 實驗數據集信息

實驗流程如圖2所示。

圖2 實驗流程

本文實驗利用上述3個數據集來對比聚類加權改進后的隨機森林算法模型與原始的隨機森林算法模型的分類精確度，分析改進后隨機森林算法模型的分類性能。實驗數據集Dermatology為不平衡數據集，由于隨機森林在處理不平衡數據時的性能表現較差，分類誤差大，分類的結果不穩定，為此在處理該類不平衡數據時，對實驗數據集進行SMOTE過采樣的方法[13]，來消除不平衡數據集對實驗結果的影響。

在根據Kappa系數構建新的隨機森林時，若某一類保留下來的決策樹的Kappa系數小于0時，就舍棄該類決策樹，避免在新的隨機森林中引入分類能力差的決策樹。由于決策樹的棵數對隨機森林的泛化性能有一定的影響，先設置原始森林中決策樹的棵數m∈[10,20,30,40,50…240,250]，進行分類仿真實驗，根據仿真結果，選擇分類精度最高時所對應的決策樹棵數m作為原始森林決策樹的數量。再依次選取聚類數量Q(Q≤m)，得出不同聚類數量下優化后隨機森林的分類精度，根據實驗結果分析優化后隨機森林模型的性能。為了避免隨機性對分類精度的影響，確定決策樹數量或聚類數量后，構建100個隨機森林模型，以這100個隨機森林分類精度的平均值作為當前決策樹棵數或聚類數量下隨機森林的分類精度。

在原始隨機森林算法中選取不同的決策樹數量，仿真實驗得到的分類精度如圖3所示。

在原始隨機森林中，各個數據集對應的最優決策樹數量及分類精度見表2。

由圖3可以看出在測試3組樣本數據時，在不同決策樹的數量m下，原始隨機森林的分類精度不同。在尋找聚類數量Q時，選取在原始森林中分類精度最高，決策樹數量相對最小所對應的決策樹的棵數(見表2)構建原始隨機森林，再依次迭代Q值，得出優化后隨機森林的分類精度，繪制出不同聚類數量Q下，各個數據集在優化后的隨機森林中分類精度如圖4所示。

表2 各個數據集下最優決策樹數量及分類精度

在優化后的隨機森林中，各個數據集對應的最優聚類數量及分類精度見表3。

在圖3和圖4中，隨著決策樹數量和聚類數量的增多，預測分類精度出現較大的曲折變化，這是由于隨機森林的隨機性導致。通過圖4和表3中可以看出改進后的隨機森林與原始隨機森林中的最高預測分類精度相比較，優化后的隨機森林對樣本分類的分類精度更高，表明該種聚類加權的方法能有效地提升了隨機森林分類器的分類性能。通過分析圖4中3個樣本預測分類精度曲線趨勢，在聚類數量低時，優化后的隨機森林分類的分類精度低于原始森林的分類精度，這是因為在聚類數量低時，隨機森林的多樣性較小，分類精度較低。隨著聚類數量的增多，優化后的隨機森林的分類精度高于原始的隨機森林，此時隨機森林的多樣性大于原始森林的多樣性，每棵決策樹投票的可信度也更高。當聚類數量與原始森林中決策樹的數量一致時，優化后的隨機森林的多樣性再次降低，分類精度也與原始森林基本一致。

圖3 不同決策樹數目下原始森林的分類精度

圖4 不同聚類數量下改進森林的分類精度

表3 改進后各數據集的最優聚類數量及分類精度

5 結束語

本文通過比對任意兩決策樹中節點屬性值和分裂屬性來構建節點間的代價矩陣，以節點間匹配代價最高的均值作為決策樹間的相似度，基于相似度矩陣利用譜聚類算法對原始隨機森林進行分類，構建新的隨機森林，在新的隨機森林中單棵決策樹以自身的Kappa系數進行加權投票，使得在增加隨機森林的多樣性的同時也增加了單棵決策樹投票的可信度，提升隨機森林的分類精度。通過UCI的3個樣本數據集來測試聚類加權后新隨機森林算法的性能，實驗結果表明：

(1)通過計算隨機森林中決策樹節點匹配代價構造節點代價矩陣來得出決策樹間相似度的方法簡單可行，能有效評估出隨機森林中決策樹之間的相關性。

(2)在合適的聚類數量下，優化后的隨機森林的分類精度高于原始隨機森林的分類精度。

接下來對本文算法的改進工作是尋找出原始森林中最優決策樹數量與聚類數量之間的聯系，以便于快速找出最優的聚類數量，更進一步地提升優化后隨機森林算法的性能。