基于深度隨機(jī)森林的新型組合分類算法*

任志偉，王玉德，陳 婷

（曲阜師范大學(xué)，山東 曲阜 273165）

0 引言

機(jī)器學(xué)習(xí)作為一個重要的分支在很多領(lǐng)域，如醫(yī)療、環(huán)境、地理等領(lǐng)域，得到了快速的發(fā)展[1-3]。為了利用諸如支持向量機(jī)（Support Vector Machine，SVM）的單分類器實(shí)現(xiàn)樣本的分類，孔德峰通過訓(xùn)練多種常規(guī)單分類器模型對乳腺癌腫瘤進(jìn)行分類研究，得出的K 最鄰近分類算法（K-NearestNeighbor，KNN）模型具有較好的分類效果[4]。劉蕾通過采用一種logistic 方程歸一化后的線性回歸分類方法，得出的基于兩個特征的邏輯回歸模型具有較好的性能[5]。為了利用多個單分類器組合的方式進(jìn)一步提升分類性能，張曉等人利用SVM、反向傳遞（Back Propagation，BP）神經(jīng)網(wǎng)絡(luò)和AdaBoost 算法的加權(quán)投票的方式來彌補(bǔ)單分類器性能不足的問題，實(shí)現(xiàn)了更高的目標(biāo)識別準(zhǔn)確度[6]。李曉麗等人通過融合SVM、徑向基函數(shù)（Radial Basis Function，RBF）神經(jīng)網(wǎng)絡(luò)和貝葉斯網(wǎng)絡(luò)，實(shí)現(xiàn)更好的科普知識文本分類效果[7]。但是目前大多數(shù)單分類器融合方法不能很好地解決不同數(shù)據(jù)集下單個分類器最優(yōu)性能的問題，使得算法的魯棒性較差。

鑒于上述問題，本文提出了基于深度隨機(jī)森林的新型組合分類算法，訓(xùn)練建立不同深度隨機(jī)森林組合的模型，以實(shí)現(xiàn)在不同數(shù)據(jù)集下均有較好性能的分類算法。

1 數(shù)學(xué)基礎(chǔ)

1.1 決策樹

決策樹是基于樹結(jié)構(gòu)進(jìn)行決策的，可以將其認(rèn)為是if-then 規(guī)則的集合。一顆決策樹包含一個根節(jié)點(diǎn)、若干內(nèi)部節(jié)點(diǎn)和若干葉節(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)作為劃分節(jié)點(diǎn)，葉節(jié)點(diǎn)對應(yīng)決策結(jié)果。用決策樹進(jìn)行分類，是從根節(jié)點(diǎn)開始，利用劃分準(zhǔn)則將實(shí)例分配到其子節(jié)點(diǎn)，若該節(jié)點(diǎn)仍為劃分節(jié)點(diǎn)，則繼續(xù)進(jìn)行判斷與分配，直至將全部樣本分到葉節(jié)點(diǎn)的類中，這一訓(xùn)練過程中只涉及少量的參數(shù)調(diào)整[8]。常用的決策樹劃分準(zhǔn)則有第三代迭代二叉樹（Iterative Dichotomiser 3，ID3）、ID3的改進(jìn)算法（C4.5）和分類回歸樹（Classification and Regression Tree，CART）等算法[9]?；贑ART 算法的決策樹生成的二叉樹是以基尼指數(shù)（Gini's diversity index）作為劃分準(zhǔn)則?；嶂笖?shù)代表了特征數(shù)據(jù)的純度情況與信息增益（ID3）或信息增益比（C4.5）相反，基尼指數(shù)越小代表特征數(shù)據(jù)的純度越高，把基尼指數(shù)最小的一個特征作為當(dāng)前節(jié)點(diǎn)的劃分特征[10-12]。基尼指數(shù)的計算公式為：

式中：D為樣本總數(shù)；K為類別數(shù)；Ck為樣本中屬于K類的個數(shù)。

基于特征A劃分后的基尼指數(shù)計算公式為：

式中：D1，D2為樣本D根據(jù)特征A所劃分的兩個部分。

1.2 隨機(jī)森林

隨機(jī)森林是Breiman 在2001 年提出的一種組合分割算法，其本質(zhì)是包含了若干個隨機(jī)決策樹，將每一個隨機(jī)決策樹的結(jié)果組合起來決定待分類樣本的歸屬類別[13]。當(dāng)輸入待測樣本之后，隨機(jī)森林會根據(jù)每個隨機(jī)決策樹的輸出結(jié)果進(jìn)行統(tǒng)計，將最多劃分的類別作為該輸入樣本最終確定的劃分類別。隨機(jī)森林較其它分類器具有很好的泛化能力并且不需要復(fù)雜的參數(shù)，在小樣本背景下具有很好的性能[14]。同時隨機(jī)森林在較高準(zhǔn)確度的前提下具有很好的可解釋性，能更好地避免過擬合且具有很強(qiáng)的魯棒性[15-16]。

隨機(jī)森林具有樣本隨機(jī)和特征隨機(jī)的特點(diǎn)。假設(shè)有N個樣本，隨機(jī)有放回的從這N個樣本中選取n個樣本作為訓(xùn)練集（這種方法稱為bootstrap sample），即樣本隨機(jī)，同時從樣本特征（假設(shè)有M個特征）中隨機(jī)選取k個屬性（k＜M），從這k個特征中選取最佳分割屬性作為節(jié)點(diǎn)建立隨機(jī)決策樹，即特征隨機(jī)[17-19]。重復(fù)以上兩個隨機(jī)步驟m次就可以得到m顆獨(dú)立的隨機(jī)決策樹，這樣就建立了深度為m的隨機(jī)森林，然后依據(jù)每棵樹的投票情況來確定樣本所屬類別。

1.3 模型評價標(biāo)準(zhǔn)

分類器性能評價指標(biāo)主要有：混淆矩陣（confusion matrix），準(zhǔn)確度（accuracy），靈敏度（sensitivity），特異性（specificity）。

混淆矩陣（confusion matrix）用來記錄一個分類器所有的分類情況，這里以二分類說明，如表1所示。

表1 二分類混淆矩陣

實(shí)驗(yàn)二分類的混淆矩陣，TP（True Positive）代表真陽性，NTP即實(shí)際為正樣本預(yù)測為正樣本的個數(shù)；FP（False Positive）代表假陽性，NFP即實(shí)際為負(fù)樣本預(yù)測為正樣本的個數(shù)；FN（False Negative）代表假陰性，NFN即實(shí)際為正樣本預(yù)測為負(fù)樣本的個數(shù)；TN（True Negative）代表真陰性，NTN即實(shí)際為負(fù)樣本預(yù)測為負(fù)樣本的個數(shù)。

準(zhǔn)確度（Accuracy）是對分類器的整體分類預(yù)測能力的評價，計算方式為：

準(zhǔn)確度越高代表分類器的分類預(yù)測能力越好，正確分類的數(shù)量占整個樣本數(shù)量的比例也就越高。

靈敏度（sensitivity）代表了模型對正樣本預(yù)測的準(zhǔn)確度，指標(biāo)均越高越好。特異性（specificity）代表了模型對負(fù)樣本的預(yù)測精度，指標(biāo)均越高越好，如式（4）、式（5）所示。

式中：Se代表靈敏度；Sp代表特異性。

2 算法實(shí)現(xiàn)步驟

組合分類算法的實(shí)現(xiàn)主要有以下幾個步驟：

（1）樣本數(shù)據(jù)的預(yù)處理，數(shù)據(jù)歸一化；

（2）設(shè)定隨機(jī)森林模型的深度范圍從50 到400，間隔為5，重復(fù)訓(xùn)練5 次并綜合每個深度模型的結(jié)果；

（3）根據(jù)步驟（2）的訓(xùn)練和綜合結(jié)果，組合前5 個平均準(zhǔn)確度最高（最優(yōu)）的隨機(jī)森林模型的綜合結(jié)果，通過投票確定最終的分類器結(jié)果；

（4）對模型進(jìn)行十折交叉檢驗(yàn)，評價最優(yōu)組合模型的分類效果；

（5）與常規(guī)的分類算法進(jìn)行實(shí)驗(yàn)對比，檢驗(yàn)論文提出算法的有效性。

算法流程如圖1 所示。

圖1 算法實(shí)現(xiàn)過程

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)使用的平臺為Matlab2016b，實(shí)驗(yàn)數(shù)據(jù)為威斯康辛州（診斷）乳腺癌數(shù)據(jù)集、無線定位數(shù)據(jù)集和汽車評估數(shù)據(jù)集。該乳腺癌數(shù)據(jù)集共有683 個樣本，本文抽取其中100 個數(shù)據(jù)用于最終的模型驗(yàn)證），如表2 所示。每個樣本具有9 個特征。“-1”代表良性，實(shí)驗(yàn)中將“-1”類定義為正類；“1”代表惡性，實(shí)驗(yàn)中將“1”類定義為負(fù)類。該樣本中良性與惡性所占比例如圖2 所示。

表2 乳腺癌數(shù)據(jù)集特征與取值范圍

圖2 乳腺癌數(shù)據(jù)集訓(xùn)練樣本的占比

無線定位數(shù)據(jù)集中包含了2 000 個樣本，本文抽取其中400 個樣本用于最終的模型驗(yàn)證，每個樣本包含7 個特征，表示用戶端分別與7 個不同WiFi發(fā)射端之間的信號強(qiáng)度大小，分類結(jié)果為用戶端所在樓層的ID，如表3 所示。該樣本中類別所占比例如圖3 所示。

圖3 無線定位數(shù)據(jù)集訓(xùn)練樣本的占比

表3 無線定位數(shù)據(jù)集特征與取值范圍

汽車評估數(shù)據(jù)集包含1 728 個樣本，本文抽取其中500 個用于最終的模型驗(yàn)證，每個樣本具有6個特征。分類結(jié)果為“unacc”和“acc”如表4 所示。該樣本中類別所占比例如圖4 所示。

表4 汽車評估數(shù)據(jù)集特征與取值范圍

圖4 汽車評估數(shù)據(jù)集訓(xùn)練樣本的占比

對數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化處理，將每個樣本的特征值映射到[0,1]之間，從而去除單位限制，將原數(shù)據(jù)轉(zhuǎn)為無量綱的純數(shù)值，計算方式為：

式中：Xmin為序列的最小值；Xmax為序列的最大值。

3.2 實(shí)驗(yàn)過程與結(jié)果分析

在乳腺癌數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中，模型深度范圍50～400，間隔為5，訓(xùn)練得到不同隨機(jī)森林模型71 個。通過十折交叉檢驗(yàn)獲取這71 個模型在訓(xùn)練樣本上的準(zhǔn)確度，然后重復(fù)5 次并計算每個模型的平均準(zhǔn)確度，同時將這5 次的結(jié)果進(jìn)行投票生成這71 個單隨機(jī)森林模型的綜合結(jié)果。由于當(dāng)平均準(zhǔn)確度接近時，組合更多的模型并不能提高最終組合算法的準(zhǔn)確度，同時考慮到參與投票的單模型的個數(shù)應(yīng)為奇數(shù)，因此本實(shí)驗(yàn)選取平均準(zhǔn)確度最高的前5 個單模型參與組合。根據(jù)平均準(zhǔn)確度最高的前5 個單隨機(jī)森林模型的綜合結(jié)果，再次進(jìn)行投票確定最終的分類結(jié)果。如圖5 所示，平均準(zhǔn)確度最高的前5 個隨機(jī)森林模型的深度分別為295、325、360、365 和380。

圖5 不同深度的隨機(jī)森林模型準(zhǔn)確度

將這5 個不同深度的隨機(jī)森林模型單獨(dú)進(jìn)行全部樣本的預(yù)測，然后統(tǒng)計這5 個隨機(jī)森林模型對每一個樣本的預(yù)測情況，預(yù)測結(jié)果達(dá)到半數(shù)以上則為組合模型對樣本的最終預(yù)測結(jié)果，即組合模型對樣本x的預(yù)測結(jié)果運(yùn)用投票規(guī)則C(x)可以表示為：

式中：y-1為正類；y1為負(fù)類；i為對正類的投票數(shù)。

實(shí)驗(yàn)中KNN 表示最近鄰算法模型；以SVM 表示支持向量機(jī)模型；以TREE 表示決策樹模型；以FOREST 表示最高性能的單隨機(jī)森林模型；以C-FOREST 表示本文提出的算法模型。

分析圖6、圖7、圖8、圖9、圖10，得出各分類器的靈敏度（sensitivity）、特異性（specificity）和準(zhǔn)確度（accuracy），如表5 所示。

圖6 KNN 混淆矩陣

圖7 SVM 混淆矩陣

圖8 TREE 混淆矩陣

圖9 FOREST 混淆矩陣

圖10 C-FOREST 算法混淆矩陣

表5 各模型交叉檢驗(yàn)的靈敏度、特異性和準(zhǔn)確度 %

從表5 可以得出組合隨機(jī)森林模型較其他分類器模型的靈敏度最大提高了3.8%，特異性最大提高了2.9%，準(zhǔn)確度最大提高了3.4%。論文提出的深度組合隨機(jī)森林算法的分類識別效果好。

為進(jìn)一步驗(yàn)證本文提出算法的可靠性，將訓(xùn)練好的全部分類器對100 個驗(yàn)證病例樣本進(jìn)行預(yù)測。該病例樣本的組成如圖11 所示，各分類器對新樣本預(yù)測結(jié)果的評價指標(biāo)如表6 所示。

表6 各模型測試的靈敏度、特異性和準(zhǔn)確度 %

圖11 新病例樣本的占比

從表6 可以得出組合隨機(jī)森林模型對新病例樣本的預(yù)測準(zhǔn)確度較其他分類器模型更高，同時具有最優(yōu)的靈敏度和特異性。

為了進(jìn)一步驗(yàn)證本文算法的魯棒性，將該算法應(yīng)用于無線定位數(shù)據(jù)集（Wireless Localization Data Set）和汽車評估數(shù)據(jù)集（Car Evaluation Data Set）中，實(shí)驗(yàn)過程同乳腺癌數(shù)據(jù)集一致。將模型在訓(xùn)練數(shù)據(jù)集中進(jìn)行訓(xùn)練后在驗(yàn)證樣本中進(jìn)行驗(yàn)證，得出的結(jié)果如表7、表8 所示。由于無線定位數(shù)據(jù)集涉及4個類別，而靈敏度和特異性表示的正類和負(fù)類的分類情況，同時準(zhǔn)確度依然作為分類器最重要的性能指標(biāo)，因此在表7 中只展示了準(zhǔn)確度。

表7 在無線定位數(shù)據(jù)集上的驗(yàn)證結(jié)果 %

表8 在汽車評估數(shù)據(jù)集上的驗(yàn)證結(jié)果 %

從表7 中可以看出組合模型較其他分類器模型的準(zhǔn)確度最大提高了3.7%。從表8 中可以看出組合模型較其他分類器模型的靈敏度最大提高了6.6%，特異性最大提高了14.6%，準(zhǔn)確度最大提高了9.0%。論文提出的深度組合隨機(jī)森林算法的分類識別效果最好，分類準(zhǔn)確度達(dá)到97.6%。

4 結(jié)語

本文針對當(dāng)前基于單分類器的組合方式不靈活且魯棒性差的問題，提出了基于深度隨機(jī)森林的新型組合分類算法。該組合算法結(jié)合了隨機(jī)森林的深度靈活性優(yōu)點(diǎn)，能夠基于不同的數(shù)據(jù)集找到最優(yōu)的組合方式，并通過投票方式完成樣本類別的預(yù)測。在威斯康辛州（診斷）乳腺癌數(shù)據(jù)集、無線定位數(shù)據(jù)集和汽車評估數(shù)據(jù)集上進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果在靈敏度、特異性和準(zhǔn)確度這三個方面表明了本文算法不僅有較好的分類效果，還具有較強(qiáng)的魯棒性。