面向圖書主題分類的隨機森林算法的應用研究

孫彥雄，李業麗，邊玉寧

(北京印刷學院，北京 102600)

0 引 言

隨著科技的快速發展，自從20世紀90年代以來，產生的數據信息越來越多，其中80%的信息是以文本存儲的[1]。因此，人們對巨量的文本信息，不能采用之前傳統的人工篩選。基于自然語言處理的文本處理應運而生，近年來對文本分類的研究也越來越多，主要集中在樸素貝葉斯、K-means聚類、SVM等算法。隨機森林算法(random forest，RF)由于其具有訓練速度快、對于大數據時代易于進行并行計算、具有很強的抗干擾能力且抗過擬合能力優秀的優點，被應用在各行各業中，并取得了優于傳統方法的效果。

對于文本分類的研究，已有大量的研究成果。比如，周慶平提出了一種基于聚類的改進KNN算法[2]；Yang對特征選擇函數進行了改進，將幾種特征選擇函數的準確系數連接起來構成一種新的特征選擇函數，最后再使用SVM進行分類[3]；張翔提出了使用Bagging的中文文本分類器的改進算法[4]。基于文本信息的增加和文本處理技術的發展，對于文本分類的應用也越來越多。例如輿情監測、情感分析、商品分類、新聞分類等等。

由于隨機森林算法的諸多優勢，使得專家學者對RF進行了許多改進應用研究。1995年Tinkam-ho首次提出隨機森林的概念[5]。之后Leo Boeiman提出RF是一種分類和預測模型[6]。M P Perrone等人提出在分類階段，RF類標簽是由所有決策樹的分類結果綜合而成，并在投票[7]跟概率平均[8]兩個方面是使用最多的方法。在應用方面，在生物信息學中，EI-Atta提出了一種使用RF預測大麻素受體(CB2)激動劑活性的方法[9]；生態學中，Eruan等人使用RF對空氣預測進行了研究；在遺傳學中，Retralia在基因識別上使用了RF。并且，RF在生物芯片、信息抽取等領域，均取得了不錯的效果。

1 算法介紹

隨機森林算法是由許多決策樹構成，通過每個決策樹的決策結果進行投票，獲得票數最多的類別就是隨機森林算法的結果。由于隨機森林算法的可并行計算[10]，容易泛化應用，不易過擬合等優點，其在生物[11]、醫學[12]、信息檢索等多個領域得到了廣泛的應用。文中主要內容是講解RF的基本構建流程，決策樹的基礎知識，為后續對RF的優化做好鋪墊工作。

1.1 隨機森林算法

要了解隨機森林算法，首先就要明白決策樹的由來。因為C4.5是決策樹的經典算法結構，因此首先分析解釋C4.5。雖然決策樹有很多變種，但是其核心主函數類似，不同點在于最優特征標準的選擇上。

首先了解信息熵，信息熵是香農在1948年提出的概念，用來解決信息的量化度量問題，如式(1)所示。

(1)

其中，i為每個消息，r為消息的個數。

為了便于后面的計算，文中提出將累加符號前面的負號刪掉，定義為純度。相應的信息熵越低，對應數據集的純度越高。

(2)

式(2)就是文中定義的純度計算公式，D表示某個數據集，k表示由于某種屬性導致的分類，總共分為y類。假設由于屬性t導致數據集U分為若干類，由此計算屬性t的信息增益，如下式：

(3)

由此，可以使用式(3)作為最優特征標準，得到的是ID3算法，但是由于ID3算法不能處理連續型的變量屬性，并且在屬性偏好上偏向于屬性分類多的屬性，影響決策。故而，1993年Quinlan提出了C4.5算法，使用信息增益率作為最優特征標準，從而解決了ID3的屬性偏好等問題。信息增益率計算公式如下：

(4)

(5)

C4.5算法的算法步驟如下：

(1)對數據集進行預處理，將連續變量離散化或對缺失的數據進行補充，進行預處理驗證結束之后，進行下一步；

(2)判斷本訓練集中是否已經生成葉子節點，如果已經全部生成，結束算法，進行下一步；

(3)使用式(4)計算葉子節點的信息增益率，進行下一步；

(4)比較得出使信息增益率最大的屬性，作為分裂節點，再使用所選屬性分割訓練集為一個個的子訓練集，轉為第二步。

由此，可以得到一棵棵的決策樹，隨機森林算法利用多棵單決策分類器組合而成多分類器的思想，克服了單分類器決策樹的種種缺點。通過每棵決策樹的結果進行投票，得到最終的分類結果。這就是RF的主要思路，構建過程是，首先利用bootstrap對訓練集進行抽樣生成多個新的訓練集；其次利用生成的訓練集產生一棵棵決策樹；最后通過每棵決策樹的投票得出最終的分類結果。

RF的主要關鍵點在于兩次隨機抽樣，一次是使用bootstrap有放回抽樣，會使得新的數據集中包含2/3舊數據集的內容，從而產生袋外數據，為文中的改進優化提供了數據源。另一次是隨機抽樣，產生在對特征的選擇上，每次生成決策樹時，使用的特征并不是完全相同的。從給出的特征中隨機抽取少于總特征數的特征進行決策樹的生成。將前面生成的決策樹，一棵棵的連起來就成為了隨機森林。

1.2 RF算法步驟

隨機森林算法在文本分類中的算法步驟如下：

(1)文本預處理。首先去除文本中的停用詞、符號等“噪聲”。然后使用word2vec詞嵌入模型，對文本信息進行向量化，生成訓練集。

(2)假設訓練集中包含有N個樣本，T種分類屬性。采用bootstrap抽樣方法，抽取出樣本N個，得到新的樣本集。

(3)在給出的T種分類屬性中，隨機抽取t(t≤T)種屬性。使用某種決策樹最優特征標準，選擇最優分類節點，使得在子樣本集中均為葉子節點。

(4)重復進行K次第三步，生成決策樹K棵，得到最終的隨機森林。

(5)H(x)是分類器的函數模型，決策樹用hi表示，Y表示目標變量(分類標簽)，I(*)表示函數。隨機森林的決策公式如式(6)。

(6)

傳統隨機森林流程如圖1所示。

圖1 隨機森林算法流程

1.3 RF優缺點分析

隨機森林算法采用的是bootstrap抽樣，對數據集進行有放回抽樣生成子數據集。正是如此，會產生大約1/3的袋外數據，這些袋外數據對分析隨機森林算法的性能具有很高的研究價值。Breiman指出，袋外數據可以替換數據集的交叉驗證法，并且袋外數據的估計就是RF泛化誤差的無偏估計。文中正是利用袋外數據，對RF的決策樹在相似程度高的情況下會掩蓋真實分類的缺點進行了改進。

隨機森林算法是一種集成學習算法，將多個弱分類器組合使用，得到一個分類性能更強的強分類器。RF正是因為分開生成決策樹，所以便于并行化處理數據[13-14]。在大數據時代，可以并行化處理數據的優勢，使得該算法極具誘惑力。

2 改進的RF算法

首先傳統的隨機森林算法沒有考慮文本數據的特殊性，進而在處理文本數據時，往往由于特征提取質量差，不能提高文本分類的水平[15-16]。其次，隨機森林算法本身存在著相似決策樹會掩蓋真實分類決策的問題。文中針對以上兩個方面進行改進。

2.1 提高文本特征質量的Tr-K方法

傳統的隨機森林算法在進行分類決策時，特征選擇個數、質量的問題并不突出。但是對于圖書等大容量的文本進行分類的問題來說，文本特征(分類決策樹屬性)數量越多、質量越高，得到的分類效果就會越好。為此，文中提出一種TF-IDF、TextRank、K-means三種方式結合的Tr-K方法，以提高文本分類效果。

TF-IDF方法的全稱是term frequency-inverse document frequency，是用來進行信息檢索和數據挖掘的常用技術。TF值是指在文件j中，第i個詞的重要程度。

(7)

其中，分子表示第i個詞在文件j中的出現頻數，分母表示文件j中包含有k個單詞出現的總頻數。

(8)

其中，|D|表示語料庫中的文件總數，ti表示要檢驗的第i個詞，dj表示文件j包含的詞匯集合，|{j:ti∈dj}|表示包含ti的所有文件頻數。之所以在分母需要加1操作，是為了避免出現無意義的除零情況的發生。

TFIDFij=TFij×IDFij

(9)

通過式(8)、式(9)，對某一文件內的高詞語頻率和在文件集中的低文件頻率，產生權重高的TF-IDF。從結論可以看出，該算法傾向于過濾掉常見的詞語，保留重要的詞語。缺點是，文本的開頭跟結尾對于語義具有不同的重要性，不能體現詞語的位置信息。

TextRank算法來源于Google的PageRank算法，PageRank算法是用來評判一個網頁的重要程度，采用有向無權圖進行打分[17-18]。設定Vj表示網頁j的節點，In(Vj)表示指向網頁j的節點集合，Out(Vj)表示網頁j指向其他網頁節點的集合。|In(Vj)|表示集合的節點數量。對網頁重要性的打分如式(10)。

(10)

d表示阻尼系數，當極端情況下沒有人訪問的網頁，會使公式無意義，因此加入阻尼系數，避免此情況的發生。

TextRank是針對文本關鍵詞的提取方法，相對于網頁，最大的不同在于生成的是有向有權圖。使用一個可變窗口對文章句子進行掃描，去掉停用詞之后，認定窗口內的每個詞之間都是互相聯系的，并計算相鄰詞語之間的余弦相似性，計算每個詞匯之間的權重。由此，計算公式如下：

WS(Vj)

(11)

其中，WS(Vi)表示節點Vi的得分，Wji是指用余弦相似度計算的節點Vj對Vi的權重。此種關鍵詞的提取方法的優點在于計算復雜度小，容易處理。

K-mean算法是無監督分類算法，因為其計算簡單聚類效果優，故而應用廣泛。但是使用K-means算法，關鍵在于找到合適的k值，即初始化質心。選擇的恰到好處，會明顯提高算法的效率和準確度。為此，文中采用TF-IDF與TextRank提取出的特征集作為K-means算法的k值輸入，再進行聚類分析。綜上所述，提出的Tr-K文本特征抽取模塊的流程如圖2所示。

圖2 特征提取Tr-K方法的結構

2.2 加權投票提高決策樹質量的機制

文中使用Tr-K得到子特征集，采用C4.5算法得到決策樹節點集合。基于投票與余弦相似性原理提出優化隨機森林機制，改進內容主要包括如下兩點：一方面，對訓練集通過word2vec訓練為詞向量，再將得到的決策樹節點集合轉換為詞向量，通過使用余弦相似性公式，判定出各個決策樹的相似性；另一方面，由于隨機森林算法在對訓練文本集進行bootstrap抽樣時，會遺留1/3的袋外數據，故而使用袋外數據對決策樹節點集合生成的決策樹進行準確率測試。

相似度的計算公式如式(12)：

(12)

其中，A與B分別表示兩個節點集合詞向量組合，n表示詞向量的維數。通過計算各個節點集合的相似性，選擇最優參數d進行比較，抽取出相似性較小的節點集合作為備選決策樹集合。

當使用訓練集bootstrap抽取子文本集合時，隨之生成袋外數據，因此使用這部分袋外數據，對決策樹進行準確率測試，從而找出最優的決策樹作為備選。公式如下：

(13)

其中，N是總體樣本數(袋外樣本數)，Ncor是正確分類數，Weight(i)表示決策樹i的正確率，e是用于判定決策樹優劣的閾值。

實現流程如圖3所示。

3 實驗仿真及分析

3.1 實驗環境

算法性能分析的實驗環境以Windows 7操作系統作為整個實驗的支撐，使用Python語言作為程序設計的編譯語言。相關配置：Intel(R)Core(TM)i5-3470 CPU處理器，處理器為3.20 GHz，內存為8 G，開發工具為PyCharm Community Edition 2017.5.1。

3.2 實驗數據集

文中共使用了兩種數據集，為驗證文中算法在不同文本中的分類能力，特選取中英文兩種不同的數據集。20 Newsgroups數據集共有18 000篇文章，涉及到20種主題，分為訓練集和測試集，兩者無交叉。通常是用來進行文本分類、信息檢索和文本挖掘相關研究的國際通用標準數據集。20 Newsgroups數據集文檔分布如圖4所示。

圖3 加權投票模塊

圖4 20 Newsgroups數據集分布

中文數據集來自搜狗實驗室提供的中文分類語料庫，隨機選取部分語料作為訓練集跟測試集。中文數據集包含體育、財經、娛樂等八類新聞文檔，共計四萬篇。各個類別的數量分布較均勻，大約每類5 000篇文檔。圖4橫坐標表示20個主題的分類名稱，縱坐標表示每類主題所包含的文檔個數。

3.3 實驗設計與分析

利用傳統隨機森林算法、僅采用TF-IDF進行文本特征提取的TF-RF算法，與文中設計的TRk-SW-RF模型進行對比實驗分析。實驗對比主要分為以下幾個方面：運行時間、分類準確率和F1值。并且為保證實驗數據的穩定性，在決策樹數量分別是50、70、100、200、300、400時進行對比實驗，并且在實驗環境不變的前提下運行10次，取平均值作為最終的實驗結果。

如表1所示，當控制決策樹的個數時，記錄20 Newsgroups數據集在不同模型上的訓練時長，可以看到，雖然TRk-SW-RF模型的訓練時長跟傳統隨機森林的訓練時長相差不大，雖然增加了特征選擇跟投票的時間，但是由于縮小了文本長度從而使得總的訓練時長增長并不明顯。并且當決策樹的數量增長到一定量時，訓練時長的增長速度明顯小于決策樹的增長速度。

表1 20 Newsgroups數據集下各模型運行時長

同時計算了20 Newsgroups數據集在三種有效模型下的準確率，如圖5所示。從圖上可以清楚地看到，使用TRk-SW-RF模型的準確率明顯高于傳統隨機森林算法和IDF-RF算法。

圖5 不同模型下的文本分類準確率

同時，為豐富文中模型在不同數據集上的泛化性，對搜狗實驗室提供的中文文本分類語料庫，使用F1值的評價標準對三種模型進行評測。結果如圖6所示，可以看出在中文語料庫中文中模型的分類能力仍然高于其他兩種算法。

圖6 不同RF模型在中文數據庫下的F1值

4 結束語

通過對隨機森林算法的輸入文本數據集進行處理，從而提高分類效果。并使用剩余的袋外數據，對得到的決策樹做進一步的檢測提取，從而提高了決策樹的質量，進而提高了最終生成的隨機森林的分類準確率。通過中外兩種不同的數據集，驗證了該模型在沒有明顯提高訓練時間的前提下，有效地提高了分類準確率和F1值。

下一步的研究可以在計算文本相似度方面引入目前很熱門的深度學習算法，雖然會延長訓練時間，但是從傳統機器學習的分類效果上看，如果能夠有較大的提高，還是很有必要的。