劉 勇，興艷云

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院，青島 266061)

1 引言

目前，隨機(jī)森林算法是常用的機(jī)器學(xué)習(xí)方法，在新聞分類、入侵檢測(cè)[1]、內(nèi)容信息過濾[2]、情感分析[3]、圖像處理[4，5]等領(lǐng)域都有著廣泛的應(yīng)用，具有很高的研究?jī)r(jià)值.許多學(xué)者提出了隨機(jī)森林的改進(jìn)方法，楊宏宇等采用IG 算法和ReliefF 算法對(duì)特征屬性選擇進(jìn)行優(yōu)化，提出改進(jìn)隨機(jī)森林(IRF，Improved Random Forest)算法[6].Abellán J 等提出基于不精確的信息增益分裂規(guī)則的信用隨機(jī)森林(CRF，Credal Random Forest)算法[7].Paul A 等提出一種迭代減少不重要特征和減少?zèng)Q策樹數(shù)量的隨機(jī)森林改進(jìn)方法[8].對(duì)于隨機(jī)森林在文本分類上的應(yīng)用，何瓏針對(duì)數(shù)據(jù)集的不平衡問題，通過改變樣本抽樣和賦予權(quán)重來改進(jìn)算法[9].賀捷從加權(quán)投票和解決平局現(xiàn)象兩方面進(jìn)行隨機(jī)森林分類算法改進(jìn)[10].田寶明等結(jié)合基于詞的和基于LDA 主題的兩種文本表示方法改進(jìn)隨機(jī)森林，提高文本分類的性能[11].

隨機(jī)森林忽視強(qiáng)弱分類器的差異以及超參數(shù)的優(yōu)化是被廣泛討論和需要更好解決的兩個(gè)問題.本文采用基于決策樹分類效果和預(yù)測(cè)概率的加權(quán)投票機(jī)制以及結(jié)合隨機(jī)搜索和網(wǎng)格搜索的超參數(shù)優(yōu)化算法對(duì)隨機(jī)森林算法進(jìn)行改進(jìn)，提出用于文本分類的改進(jìn)隨機(jī)森林分類模型，首先對(duì)文本進(jìn)行空間向量表示和特征提取，之后使用加權(quán)的隨機(jī)森林進(jìn)行分類，并且對(duì)超參數(shù)進(jìn)行調(diào)節(jié)優(yōu)化，最后對(duì)分類效果進(jìn)行評(píng)估.

2 隨機(jī)森林算法

2.1 算法介紹

隨機(jī)森林算法[12]是一種基于Bagging的集成學(xué)習(xí)方法，可以用于解決分類和回歸問題，本文就隨機(jī)森林算法用于分類問題進(jìn)行研究.隨機(jī)森林算法的基本構(gòu)成單元是充分生長(zhǎng)、沒有剪枝的決策樹.算法流程包括生成隨機(jī)森林和進(jìn)行決策兩部分，如圖1所示.

圖1 隨機(jī)森林的算法流程

具體的算法步驟如下:

(1)記給定原始訓(xùn)練集中的樣本數(shù)量為N，特征屬性數(shù)量為M.采用bootstrap 抽樣技術(shù)從原始訓(xùn)練集中抽取N個(gè)樣本形成訓(xùn)練子集.

(2)從M個(gè)特征屬性中隨機(jī)選擇m個(gè)特征作為候

選特征(m≤M)，在決策樹的每個(gè)節(jié)點(diǎn)按照某種規(guī)則(基尼指數(shù)、信息增益率等)選擇最優(yōu)屬性進(jìn)行分裂，直到該節(jié)點(diǎn)的所有訓(xùn)練樣例都屬于同一類，過程中完全分裂不剪枝.

(3)重復(fù)上述兩個(gè)步驟k次，構(gòu)建k棵決策樹，生成隨機(jī)森林.

(4)使用隨機(jī)森林進(jìn)行決策，設(shè)x代表測(cè)試樣本，hi代表單棵決策樹，Y代表輸出變量即分類標(biāo)簽，I為指示性函數(shù)，H為隨機(jī)森林模型，決策公式為:

即匯總每棵決策樹對(duì)測(cè)試樣本的分類結(jié)果，得票數(shù)最多的類為最后的分類結(jié)果.

上述例子當(dāng)中的“得得嗖嗖”、“躥噠躥噠”表現(xiàn)出來的都是一種反復(fù)的、持續(xù)的動(dòng)作，而不是得嗖一下或者躥一下就停止的。這種動(dòng)作本身已經(jīng)帶有持續(xù)意義了，后面就不能再加“著”了，通常是不會(huì)說“躥噠躥噠著”、“得得嗖嗖著”的。兩個(gè)詞重疊表現(xiàn)出反復(fù)和持續(xù)，而這種反復(fù)和持續(xù)同時(shí)也增長(zhǎng)了時(shí)量，增加了動(dòng)量。

2.2 算法分析

隨機(jī)森林算法采用的抽樣方法bootstrap 是一種有放回的簡(jiǎn)單隨機(jī)抽樣，每個(gè)訓(xùn)練子集的抽取過程中都有約37%樣本沒有被抽中，這些樣本被稱為袋外數(shù)據(jù).袋外數(shù)據(jù)具有很高的研究?jī)r(jià)值，Breiman 指出袋外數(shù)據(jù)估計(jì)是隨機(jī)森林泛化誤差的無偏估計(jì)，可以替代數(shù)據(jù)集的交叉驗(yàn)證法.袋外數(shù)據(jù)還可以用于檢驗(yàn)每棵樹分類效果的好壞[13]和估計(jì)隨機(jī)森林算法中的超參數(shù)[14].

隨機(jī)森林算法具有很多優(yōu)點(diǎn).作為一種分類器組合算法，其通過覆蓋優(yōu)化手段將若干弱分類器的能力進(jìn)行綜合，使分類系統(tǒng)的總體性能得到優(yōu)化，比單個(gè)算法要好[15].在生成隨機(jī)森林時(shí)，每棵決策樹相互獨(dú)立、同時(shí)生成，訓(xùn)練速度快并且容易做成并行化方法.在選擇樣本時(shí)隨機(jī)抽樣以及在構(gòu)建決策樹時(shí)隨機(jī)選擇特征，算法不容易陷入過擬合，并且具有一定的抗噪能力.

與此同時(shí)，隨機(jī)森林算法也存在著不足之處.隨機(jī)森林算法在進(jìn)行決策時(shí)采用多數(shù)投票算法，不考慮強(qiáng)分類器和弱分類器的差異，對(duì)于整體的分類結(jié)果有所影響.算法中有很多超參數(shù)，如決策樹的棵數(shù)、節(jié)點(diǎn)分裂時(shí)參與判斷的最大特征數(shù)、樹的最大深度以及葉節(jié)點(diǎn)的最小樣本數(shù)等.它們需要在訓(xùn)練開始之前設(shè)置值，但使用者無法控制模型內(nèi)部的運(yùn)行，只能在不同的參數(shù)之間進(jìn)行嘗試，如何對(duì)超參數(shù)進(jìn)行調(diào)節(jié)取值對(duì)隨機(jī)森林算法的性能有著很大的影響.

3 隨機(jī)森林算法的改進(jìn)

投票決策過程決定了最終的分類結(jié)果，超參數(shù)的設(shè)置對(duì)于算法性能也至關(guān)重要.本文在這兩個(gè)方面提出以下改進(jìn).

3.1 加權(quán)投票方法

傳統(tǒng)隨機(jī)森林算法進(jìn)行分類決策時(shí)，采用平均多數(shù)投票法，每一棵決策樹輸出自己的分類標(biāo)簽，最終的分類結(jié)果為輸出最多的類.但是隨機(jī)森林中的決策樹分類效果不同，有的決策樹分類效果好，有的決策樹分類效果差.按照平均多數(shù)投票法，每棵決策樹具有相同的投票權(quán)重，不能充分利用分類效果好的決策樹的能力以及減少分類效果差的決策樹對(duì)分類結(jié)果的負(fù)面影響.

本文設(shè)計(jì)一種結(jié)合決策樹分類效果和類概率的加權(quán)投票方法用于隨機(jī)森林的決策階段.決策樹的分類效果通過袋外數(shù)據(jù)的分類正確率來體現(xiàn)，分類正確率高的決策樹分類效果好，賦予的權(quán)重高.設(shè)總樣本數(shù)為X，正確分類的樣本數(shù)為Xcorrect，隨機(jī)森林中決策樹i的權(quán)重為:

對(duì)于每一個(gè)測(cè)試樣本，決策樹輸出樣本屬于各個(gè)類的預(yù)測(cè)概率p.在投票階段結(jié)合決策樹的權(quán)重，得到樣本屬于類Y的加權(quán)值:

之后選擇值最大的類為分類結(jié)果.

改進(jìn)后的隨機(jī)森林分類算法模型包括訓(xùn)練模塊和檢測(cè)模塊兩部分，算法流程如圖2所示.

圖2 改進(jìn)后的隨機(jī)森林算法流程

3.2 隨機(jī)森林算法超參數(shù)優(yōu)化

隨機(jī)森林中超參數(shù)的取值對(duì)于算法性能有很大的影響，通常根據(jù)經(jīng)驗(yàn)設(shè)置，但是不同分類問題的最優(yōu)參數(shù)具有較大差異，經(jīng)驗(yàn)取值不能取得良好的結(jié)果.若通過在不同的參數(shù)之間進(jìn)行嘗試得到最優(yōu)值需要大量的人力和時(shí)間.對(duì)于數(shù)據(jù)量和超參數(shù)范圍較大的隨機(jī)森林應(yīng)用場(chǎng)景，經(jīng)驗(yàn)取值和逐一人工嘗試的方法更加不可取.此外，隨機(jī)森林中需要設(shè)置的參數(shù)較多，需要得到最優(yōu)的參數(shù)組合.本文對(duì)于數(shù)據(jù)量和超參數(shù)范圍較大的隨機(jī)森林應(yīng)用場(chǎng)景，采用隨機(jī)搜索和網(wǎng)格搜索結(jié)合的算法對(duì)超參數(shù)進(jìn)行優(yōu)化，能夠高效的得到超參數(shù)的最優(yōu)值.

網(wǎng)格搜索算法是在所有候選的參數(shù)選擇中，通過循環(huán)遍歷，嘗試每一種可能性，選擇出表現(xiàn)最好的參數(shù)作為最終的結(jié)果.由于要嘗試每一種可能，這種算法在數(shù)據(jù)量、超參數(shù)數(shù)量和范圍較大的情況下需要很長(zhǎng)的時(shí)間，性能較差.隨機(jī)搜索算法區(qū)別于網(wǎng)格搜索的暴力搜索方式，利用隨機(jī)數(shù)去求函數(shù)近似的最優(yōu)解.這種算法找到近似最優(yōu)解的效率高于網(wǎng)格搜索[16]，但可能出現(xiàn)局部最優(yōu)解的情況.本文提出隨機(jī)搜索和網(wǎng)格搜索結(jié)合的超參數(shù)調(diào)優(yōu)算法，首先使用隨機(jī)搜索進(jìn)行粗選縮小超參數(shù)范圍，然后使用網(wǎng)格搜索得到超參數(shù)的最優(yōu)值.

本文選擇隨機(jī)森林算法中較為重要的兩個(gè)超參數(shù):決策樹棵數(shù)k和候選特征數(shù)m進(jìn)行調(diào)節(jié)優(yōu)化，使用交叉驗(yàn)證的平均預(yù)測(cè)準(zhǔn)確率作為算法性能的評(píng)價(jià)指標(biāo).超參數(shù)優(yōu)化算法的流程如圖3所示.

具體步驟如下:

(1)確定決策樹棵數(shù)k和候選特征數(shù)量m的范圍.

(2)進(jìn)行隨機(jī)搜索，以模型預(yù)測(cè)準(zhǔn)確率作為算法性能的評(píng)價(jià)指標(biāo)，得到搜索結(jié)果.

(3)對(duì)搜索結(jié)果進(jìn)行分析，考慮性能最好的五組超參數(shù)取值.如果五組結(jié)果的超參數(shù)取值相近或者性能差距較大，以最優(yōu)值附近為范圍進(jìn)行一次網(wǎng)格搜索.如果五組結(jié)果的超參數(shù)取值差距較大且性能差距較小，則在多個(gè)小范圍內(nèi)進(jìn)行網(wǎng)格搜索.

(4)得到最終的超參數(shù)取值.

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

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

本文使用Python 進(jìn)行算法實(shí)現(xiàn)，借助scikitlearn 工具包構(gòu)建代碼[17].實(shí)驗(yàn)環(huán)境:操作系統(tǒng)為64 位的Windows 10 系統(tǒng)，處理器為Intel Core i5，內(nèi)存為8G，CPU 為2.60 GHz，開發(fā)工具為PyCharm Community Edition 2017.3.3.

圖3 超參數(shù)優(yōu)化算法流程

20 Newsgroups 數(shù)據(jù)集是用于文本分類、文本挖據(jù)和信息檢索研究的國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集之一.該數(shù)據(jù)集有約20 000個(gè)新聞文檔，包括20個(gè)類，每個(gè)類分為訓(xùn)練集和測(cè)試集兩部分，數(shù)據(jù)集的文檔分布情況如圖4所示.

圖4 20 Newsgroups 數(shù)據(jù)集文檔分布情況

4.2 文本分類實(shí)驗(yàn)及結(jié)果分析

分類前需要對(duì)文本語(yǔ)料進(jìn)行處理，將其轉(zhuǎn)換為計(jì)算機(jī)可以處理的數(shù)據(jù)類型，本文采用向量空間模型的文本表示方法.由于數(shù)據(jù)集是新聞數(shù)據(jù)，有大量與類別相關(guān)的信息，分類器不需要從文本中挖掘識(shí)別主題就可以獲得很好的性能，所以需要去除這些信息，然后進(jìn)行詞頻統(tǒng)計(jì)并使用TF-IDF 技術(shù)處理將文本進(jìn)行向量化表示.因?yàn)槲谋局性~語(yǔ)較多，上述處理中使用全部文檔中的每一個(gè)詞作為一個(gè)特征形成了高維矩陣，需要較長(zhǎng)的訓(xùn)練和處理時(shí)間，所以使用具有較高性能的χ2統(tǒng)計(jì)方法[18]進(jìn)行特征選取，最終得到用于實(shí)驗(yàn)的數(shù)據(jù)集.

實(shí)驗(yàn)分為兩方面，一方面是改進(jìn)投票方法的隨機(jī)森林算法效果分析實(shí)驗(yàn)，對(duì)比傳統(tǒng)的隨機(jī)森林算法和改進(jìn)隨機(jī)森林算法的性能.另一方面是隨機(jī)森林的超參數(shù)優(yōu)化，證明文中超參數(shù)優(yōu)化算法的可行性同時(shí)確定超參數(shù)的取值，比較優(yōu)化前后算法的性能.

4.2.1 改進(jìn)隨機(jī)森林算法效果分析實(shí)驗(yàn)

使用傳統(tǒng)隨機(jī)森林算法和改進(jìn)算法進(jìn)行文本分類實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)為數(shù)據(jù)集中的所有類別.分類性能的評(píng)價(jià)指標(biāo)為時(shí)間和模型預(yù)測(cè)準(zhǔn)確率.其中模型預(yù)測(cè)準(zhǔn)確率為測(cè)試樣本中分類正確的樣本數(shù)占總樣本數(shù)的比例.為消除隨機(jī)性的影響，分別在決策樹棵數(shù)為10、30、50、100、200、300、400時(shí)進(jìn)行對(duì)比實(shí)驗(yàn)，并且每組實(shí)驗(yàn)結(jié)果都取10 次運(yùn)行結(jié)果的平均值.

實(shí)驗(yàn)結(jié)果如表1所示.可以看出，在不同決策樹棵數(shù)情況下改進(jìn)算法在時(shí)間上與傳統(tǒng)隨機(jī)森林算法差異不大，但是模型預(yù)測(cè)準(zhǔn)確率有了一定程度的提高.本文提出的基于加權(quán)投票的改進(jìn)隨機(jī)森林算法比傳統(tǒng)隨機(jī)森林算法具有更高的性能.

表1 改進(jìn)隨機(jī)森林算法實(shí)驗(yàn)結(jié)果

4.2.2 隨機(jī)森林的超參數(shù)優(yōu)化實(shí)驗(yàn)

對(duì)隨機(jī)森林算法進(jìn)行超參數(shù)調(diào)優(yōu)，實(shí)驗(yàn)數(shù)據(jù)為20 Newsgroups 數(shù)據(jù)集中的rec.autos、rec.motorcycles、rec.sport.baseball、rec.sport.hockey、sci.crypt、sci.electronics、sci.med 和sci.space 八個(gè)類.為了減少隨機(jī)性對(duì)實(shí)驗(yàn)結(jié)果的影響，使用交叉驗(yàn)證的規(guī)則，并取測(cè)試集上得分的平均值作為評(píng)估指標(biāo)，得分越高效果越好.在隨機(jī)搜索時(shí)設(shè)置決策樹k的范圍為1＜k≤600，候選特征數(shù)量m的范圍為1＜m≤146.圖5 為隨機(jī)搜索的實(shí)驗(yàn)結(jié)果，根據(jù)結(jié)果得到最好的五組實(shí)驗(yàn)超參數(shù)取值如表2所示.

圖5 隨機(jī)搜索結(jié)果

表2 最好的五組實(shí)驗(yàn)

可以看出，第一組實(shí)驗(yàn)結(jié)果明顯優(yōu)于其他四組，按照前文提出的算法，只需要在k=279，m=3 附近進(jìn)行一次網(wǎng)格搜索.設(shè)置網(wǎng)格搜索的超參數(shù)范圍，k的范圍為250≤k≤340，步長(zhǎng)為10，m的范圍為2≤m≤6，步長(zhǎng)為1.圖6 為網(wǎng)格搜索的結(jié)果，可以得出最優(yōu)參數(shù)取值，k=270，m=2，此時(shí)score 值最高，為0.7898.

圖6 網(wǎng)格搜索結(jié)果

保持其他變量相同，超參數(shù)k、m分別為默認(rèn)值和優(yōu)化值進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果見表3，可以看出優(yōu)化后的超參數(shù)使得隨機(jī)森林算法分類能力大大提高.

表3 超參數(shù)調(diào)優(yōu)前后實(shí)驗(yàn)結(jié)果對(duì)比

5 結(jié)論與展望

針對(duì)隨機(jī)森林分類算法的不足以及文本分類問題中數(shù)據(jù)量和超參數(shù)范圍較大等問題，提出算法改進(jìn)方案和用于文本分類的分類模型.一方面使用結(jié)合決策樹分類效果和類概率的加權(quán)投票機(jī)制代替?zhèn)鹘y(tǒng)的投票機(jī)制，提高分類算法性能，另一方面提出隨機(jī)搜索和網(wǎng)格搜索結(jié)合的算法，簡(jiǎn)單高效地實(shí)現(xiàn)超參數(shù)優(yōu)化調(diào)節(jié).本文實(shí)驗(yàn)在平衡數(shù)據(jù)集上進(jìn)行，具有良好的性能，在不平衡數(shù)據(jù)上是否有效需要進(jìn)一步的研究，此外為了更好地提高處理大量數(shù)據(jù)的效率，今后研究可以考慮結(jié)合并行化方法.