基于改進隨機森林算法的文本分類研究與應用①

劉 勇，興艷云

(青島科技大學 信息科學技術學院，青島 266061)

1 引言

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

隨機森林忽視強弱分類器的差異以及超參數的優化是被廣泛討論和需要更好解決的兩個問題.本文采用基于決策樹分類效果和預測概率的加權投票機制以及結合隨機搜索和網格搜索的超參數優化算法對隨機森林算法進行改進，提出用于文本分類的改進隨機森林分類模型，首先對文本進行空間向量表示和特征提取，之后使用加權的隨機森林進行分類，并且對超參數進行調節優化，最后對分類效果進行評估.

2 隨機森林算法

2.1 算法介紹

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

圖1 隨機森林的算法流程

具體的算法步驟如下:

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

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

選特征(m≤M)，在決策樹的每個節點按照某種規則(基尼指數、信息增益率等)選擇最優屬性進行分裂，直到該節點的所有訓練樣例都屬于同一類，過程中完全分裂不剪枝.

(3)重復上述兩個步驟k次，構建k棵決策樹，生成隨機森林.

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

即匯總每棵決策樹對測試樣本的分類結果，得票數最多的類為最后的分類結果.

上述例子當中的“得得嗖嗖”、“躥噠躥噠”表現出來的都是一種反復的、持續的動作，而不是得嗖一下或者躥一下就停止的。這種動作本身已經帶有持續意義了，后面就不能再加“著”了，通常是不會說“躥噠躥噠著”、“得得嗖嗖著”的。兩個詞重疊表現出反復和持續，而這種反復和持續同時也增長了時量，增加了動量。

2.2 算法分析

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

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

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

3 隨機森林算法的改進

投票決策過程決定了最終的分類結果，超參數的設置對于算法性能也至關重要.本文在這兩個方面提出以下改進.

3.1 加權投票方法

傳統隨機森林算法進行分類決策時，采用平均多數投票法，每一棵決策樹輸出自己的分類標簽，最終的分類結果為輸出最多的類.但是隨機森林中的決策樹分類效果不同，有的決策樹分類效果好，有的決策樹分類效果差.按照平均多數投票法，每棵決策樹具有相同的投票權重，不能充分利用分類效果好的決策樹的能力以及減少分類效果差的決策樹對分類結果的負面影響.

本文設計一種結合決策樹分類效果和類概率的加權投票方法用于隨機森林的決策階段.決策樹的分類效果通過袋外數據的分類正確率來體現，分類正確率高的決策樹分類效果好，賦予的權重高.設總樣本數為X，正確分類的樣本數為Xcorrect，隨機森林中決策樹i的權重為:

對于每一個測試樣本，決策樹輸出樣本屬于各個類的預測概率p.在投票階段結合決策樹的權重，得到樣本屬于類Y的加權值:

之后選擇值最大的類為分類結果.

改進后的隨機森林分類算法模型包括訓練模塊和檢測模塊兩部分，算法流程如圖2所示.

圖2 改進后的隨機森林算法流程

3.2 隨機森林算法超參數優化

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

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

本文選擇隨機森林算法中較為重要的兩個超參數:決策樹棵數k和候選特征數m進行調節優化，使用交叉驗證的平均預測準確率作為算法性能的評價指標.超參數優化算法的流程如圖3所示.

具體步驟如下:

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

(2)進行隨機搜索，以模型預測準確率作為算法性能的評價指標，得到搜索結果.

(3)對搜索結果進行分析，考慮性能最好的五組超參數取值.如果五組結果的超參數取值相近或者性能差距較大，以最優值附近為范圍進行一次網格搜索.如果五組結果的超參數取值差距較大且性能差距較小，則在多個小范圍內進行網格搜索.

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

4 實驗結果與分析

4.1 實驗數據

本文使用Python 進行算法實現，借助scikitlearn 工具包構建代碼[17].實驗環境:操作系統為64 位的Windows 10 系統，處理器為Intel Core i5，內存為8G，CPU 為2.60 GHz，開發工具為PyCharm Community Edition 2017.3.3.

圖3 超參數優化算法流程

20 Newsgroups 數據集是用于文本分類、文本挖據和信息檢索研究的國際標準數據集之一.該數據集有約20 000個新聞文檔，包括20個類，每個類分為訓練集和測試集兩部分，數據集的文檔分布情況如圖4所示.

圖4 20 Newsgroups 數據集文檔分布情況

4.2 文本分類實驗及結果分析

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

實驗分為兩方面，一方面是改進投票方法的隨機森林算法效果分析實驗，對比傳統的隨機森林算法和改進隨機森林算法的性能.另一方面是隨機森林的超參數優化，證明文中超參數優化算法的可行性同時確定超參數的取值，比較優化前后算法的性能.

4.2.1 改進隨機森林算法效果分析實驗

使用傳統隨機森林算法和改進算法進行文本分類實驗，實驗數據為數據集中的所有類別.分類性能的評價指標為時間和模型預測準確率.其中模型預測準確率為測試樣本中分類正確的樣本數占總樣本數的比例.為消除隨機性的影響，分別在決策樹棵數為10、30、50、100、200、300、400時進行對比實驗，并且每組實驗結果都取10 次運行結果的平均值.

實驗結果如表1所示.可以看出，在不同決策樹棵數情況下改進算法在時間上與傳統隨機森林算法差異不大，但是模型預測準確率有了一定程度的提高.本文提出的基于加權投票的改進隨機森林算法比傳統隨機森林算法具有更高的性能.

表1 改進隨機森林算法實驗結果

4.2.2 隨機森林的超參數優化實驗

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

圖5 隨機搜索結果

表2 最好的五組實驗

可以看出，第一組實驗結果明顯優于其他四組，按照前文提出的算法，只需要在k=279，m=3 附近進行一次網格搜索.設置網格搜索的超參數范圍，k的范圍為250≤k≤340，步長為10，m的范圍為2≤m≤6，步長為1.圖6 為網格搜索的結果，可以得出最優參數取值，k=270，m=2，此時score 值最高，為0.7898.

圖6 網格搜索結果

保持其他變量相同，超參數k、m分別為默認值和優化值進行對比，實驗結果見表3，可以看出優化后的超參數使得隨機森林算法分類能力大大提高.

表3 超參數調優前后實驗結果對比

5 結論與展望

針對隨機森林分類算法的不足以及文本分類問題中數據量和超參數范圍較大等問題，提出算法改進方案和用于文本分類的分類模型.一方面使用結合決策樹分類效果和類概率的加權投票機制代替傳統的投票機制，提高分類算法性能，另一方面提出隨機搜索和網格搜索結合的算法，簡單高效地實現超參數優化調節.本文實驗在平衡數據集上進行，具有良好的性能，在不平衡數據上是否有效需要進一步的研究，此外為了更好地提高處理大量數據的效率，今后研究可以考慮結合并行化方法.