基于隨機(jī)森林的文本分類研究

摘 要：文本分類是處理和組織大量文本數(shù)據(jù)的關(guān)鍵技術(shù)，它一直是信息檢索領(lǐng)域中的一個研究熱點(diǎn)。文本分類旨在將大量文本劃分到若干子類，使得各文本子類代表不同的概念主題。文章采用了一種基于隨機(jī)森林的文本分類方法。該方法來源于基于決策樹的機(jī)器學(xué)習(xí)，依據(jù)文本內(nèi)容的分詞結(jié)果進(jìn)行機(jī)器學(xué)習(xí)，將文本中信息量高的詞匯提取出來作為學(xué)習(xí)維度，可以準(zhǔn)確地對文本進(jìn)行分類。由于隨機(jī)森林算法[1]具有高并發(fā)，快速收斂的優(yōu)點(diǎn)，非常適合海量數(shù)據(jù)的處理。

關(guān)鍵詞：決策樹分類；機(jī)器學(xué)習(xí)；森林

1 問題分析和算法描述

隨機(jī)森林可以看成是Bagging和隨機(jī)子空間的結(jié)合。隨機(jī)森林是由一系列的分類器組合在一起進(jìn)行決策[2]，期望得到一個最“公平”的學(xué)習(xí)方法。如圖1所示，構(gòu)造每一個分類器需要從原數(shù)據(jù)集中隨機(jī)抽取出一部分樣本作為樣本子空間，然后再從樣本子空間中隨機(jī)的選取一個新的特征子空間[4]，在這個新空間中建立決策樹作為分類器，最后通過投票的方法得到最終決（如圖1）。

圖1

1.1 構(gòu)建單棵決策樹

（1）對于訓(xùn)練集S，如果訓(xùn)練集數(shù)據(jù)都屬于一個類標(biāo)簽C，或S足夠純凈（85%以上的數(shù)據(jù)都屬于類標(biāo)簽C時），否則創(chuàng)建葉子節(jié)點(diǎn)，表明類標(biāo)簽C。

（2）否則，

·選擇“最具有信息”的屬性A：

·依據(jù)A來劃分訓(xùn)練集S；

·遞歸的劃分訓(xùn)練集來構(gòu)造子樹。

1.2 構(gòu)建隨機(jī)森林

·從原始數(shù)據(jù)中產(chǎn)生n個隨機(jī)抽樣。

·對于每一個抽樣，訓(xùn)練一個未剪枝的決策樹，對于每個節(jié)點(diǎn)，不是在所有屬性中挑選分割最好的決策樹，而是在m個抽樣出來的屬性中挑選最好的那個。

·對數(shù)據(jù)集進(jìn)行預(yù)測，并搜集各個樹的預(yù)測結(jié)果，以眾數(shù)（出現(xiàn)最多的值）給出最后的預(yù)測結(jié)果。

1.3 說明

一個單詞包含的信息量，用特征單詞在文檔中出現(xiàn)的頻率p，和該詞的反文檔頻率q來表示（如果一個單詞在很多文檔中出現(xiàn)的頻率都很高，那么這個單詞過于普遍，不足以用來表征一篇文檔）。文本中詞匯信息量的維度可以采“熵”來衡量，設(shè)D為用類別對訓(xùn)練元組進(jìn)行的劃分，則D的熵（entropy）表示為：

其中pi表示第i個類別在整個訓(xùn)練元組中出現(xiàn)的概率，可以用屬于此類別元素的數(shù)量除以訓(xùn)練元組元素總數(shù)量作為估計。熵的實(shí)際意義是D中元組的類標(biāo)號所需要的平均信息量?，F(xiàn)在我們假設(shè)將訓(xùn)練元組D按屬性A進(jìn)行劃分，則A對D劃分的期望信息為：

在選取信息量最大的屬性是我們依照公式[3]選取對樣本及最大的屬性A。

2 實(shí)驗(yàn)步驟

2.1 提取實(shí)驗(yàn)文檔

實(shí)驗(yàn)采用搜狗語料庫精簡版，其分類體系包括幾十個分類節(jié)點(diǎn)，網(wǎng)頁規(guī)模約為十萬篇文檔。

2.2 文本特征提取、降維

采用前面提到的信息增量的辦法來衡量信息的有效性，分別計算分詞后各詞的信息增量gain（A），對語料庫中1791篇短文分詞，共得到共有前4685個不同的詞組，如果全部計算，則運(yùn)算矩陣維數(shù)過高，需要依據(jù)gain（A）選取區(qū)分度高的詞匯作為候選特征。

2.3 文本向量化

依據(jù)詞在文本中出現(xiàn)的頻率，采用tf*idf向量化對文本進(jìn)行向量化。向量化結(jié)果如表1所示：

表1

按照上面描述的算法對文檔進(jìn)行分類。如果原始訓(xùn)練集S中有N篇文本，使用有放回抽樣，從S中抽出N篇文本作為建立第i棵樹的訓(xùn)練集Si，調(diào)用建立決策樹過程，訓(xùn)練單個文本分類器。其中，如果Si有mall維特征，則隨機(jī)地選取mtry維特征，并且在這mtry維特征中選取分類效果最好的一個特征A作為該結(jié)點(diǎn)的分裂屬性。

2.4 試驗(yàn)結(jié)果分析及解釋（表2）：

表2

3 試驗(yàn)結(jié)果分析

依據(jù)實(shí)驗(yàn)結(jié)果，隨機(jī)森林方法分類的平均準(zhǔn)確率和平均查全率要優(yōu)于貝葉斯方法，主要原因是排除了貝葉斯方法中特征互相獨(dú)立的不合理假設(shè)，將對文檔區(qū)分度貢獻(xiàn)大的詞（在本文中多次出現(xiàn)，而在其他文章中出現(xiàn)次數(shù)較少）提取出來作為特征，對系統(tǒng)進(jìn)行無監(jiān)督分類訓(xùn)練。

參考文獻(xiàn)

[1]Svetnik V，Liaw A，Tong C，et al. Random forest： a classification and regression tool for compound classification and QSAR modeling[J].Journal of chemical information and computer sciences，2003，43（6）： 1947-1958.

[2]張華偉，王明文，甘麗新.基于隨機(jī)森林的文本分類模型研究[J].山東大學(xué)學(xué)報：理學(xué)版，2006，41（3）：139-143.

[3]張建兵，戴新宇，陳家駿.文檔分類之特征選擇方法的實(shí)驗(yàn)比較[J].廣西師范大學(xué)學(xué)報：自然科學(xué)版，2008，26（3）：181-185.

[4]張海龍，王蓮芝.自動文本分類特征選擇方法研究[J][J].計算機(jī)工程與設(shè)計，2006，27（20）：3838-3841.

作者簡介：陳海利（1987-），男，河北省滄州市，同濟(jì)大學(xué)軟件工程專業(yè)，碩士，研究方向：數(shù)據(jù)挖掘。

孫志偉（1958-），男，遼寧省沈陽市，沈陽機(jī)床股份有限公司高級工程師，本科，研究方向：數(shù)據(jù)庫優(yōu)化。

龐龍（1981-），男，遼寧省沈陽市，沈陽機(jī)床股份有限公司中級工程師本科，研究方向：數(shù)據(jù)庫優(yōu)化。