朱 瑛，謝 睿，鄭若池

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

0 引 言

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

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

1 決策樹的相似度

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

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

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

步驟2 對每個訓(xùn)練子集訓(xùn)練得出與之對應(yīng)的決策樹，并記錄下每個決策樹的根節(jié)點，內(nèi)部節(jié)點的位置以及其對應(yīng)的分裂節(jié)點屬性X和分裂值T。

步驟3 統(tǒng)計兩個決策樹中的分支節(jié)點數(shù)量為N1和N2，選取兩個決策樹中分支節(jié)點數(shù)量最大的值作為n。在兩個決策樹中任意選取兩個分支節(jié)點，構(gòu)建兩個決策樹節(jié)點間n×n維的代價矩陣Sim_node

(1)

節(jié)點間匹配代價的計算規(guī)則如下：

(1)當(dāng)決策樹Tree1的分支節(jié)點數(shù)N1

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

(2)

M=|Ttree1.node1-Ttree2.node2|

(3)

(4)

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

(5)

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

(6)

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

(7)

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

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

2 分類性能評估

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

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

圖1 混淆矩陣

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

(8)

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

(9)

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

(10)

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

3 隨機森林算法的改進

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

步驟1 對原始的訓(xùn)練數(shù)據(jù)進行劃分，隨機抽取80%的原始訓(xùn)練數(shù)據(jù)用作決策樹的訓(xùn)練數(shù)據(jù)，構(gòu)建隨機森林模型，20%的原始訓(xùn)練數(shù)據(jù)用于對隨機森林模型的檢驗。

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

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

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

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

4 實驗結(jié)果分析

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

表1 實驗數(shù)據(jù)集信息

實驗流程如圖2所示。

圖2 實驗流程

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

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

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

在原始隨機森林中，各個數(shù)據(jù)集對應(yīng)的最優(yōu)決策樹數(shù)量及分類精度見表2。

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

表2 各個數(shù)據(jù)集下最優(yōu)決策樹數(shù)量及分類精度

在優(yōu)化后的隨機森林中，各個數(shù)據(jù)集對應(yīng)的最優(yōu)聚類數(shù)量及分類精度見表3。

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

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

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

表3 改進后各數(shù)據(jù)集的最優(yōu)聚類數(shù)量及分類精度

5 結(jié)束語

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

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

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

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