一種改進的隨機森林Boost多標簽文本分類算法

邵孟良 齊德昱

1(廣州軟件學院計算機系 廣東 廣州 510990)2(華南理工大學計算機科學與工程學院 廣東 廣州 510006)

0 引 言

互聯網上海量的數據通常以非結構化的形式表示和存儲，需要通過高效的自動文本分類[1]系統來管理和組織這些數據。因此，文本分類是非常重要的研究領域。

文本分類指從一組預定義類別中自動指定文本的合適分類。研究人員提出了很多用于文本分類的分類算法，如支持向量機[2]、決策樹[3]等。但這些算法僅限于單標簽分類問題。然而，文本可能屬于多種分類。為此，研究人員提出了一些多標簽分類算法，例如二進制相關算法和分類器鏈算法等。AdaBoost.MH[4]是Adaboost的多標簽形式，其準確性較高，是當前性能領先的多標簽分類算法之一。與Boosting算法類似，AdaBoost.MH迭代構建弱假設集合，然后將其合并為一個能夠估計給定實例的多個標簽的分類器。當數據集較大時，AdaBoost.MH在弱監督學習過程中迭代地檢驗所有訓練特征，其耗時較長[5]。文獻[6]使用了一種長短期記憶模型，即一種機器學習的方法進行文本分類學習，并使用注意力機制對詞匯文本的貢獻程度進行度量。文獻[7]提出了AdaBoost.MH的改進算法隨機森林提升(RF-Boost)，其首先對訓練特征進行排序，然后在每個Boosting輪過濾并使用排序靠前特征的較小子集，生成新的弱假設。實驗結果表明，RF-Boost是一種快速準確的多標簽文本分類算法。但作為一個話題模型，要求對話題估計進行重采樣，當數據量較大時，兩種用于RF-Boost的特征排序方法可能會增加計算時間。文獻[8]提出一種非獨立同分布的多實例多標簽分類算法，在圖像和文本數據集上的實驗結果表明，該算法大大提高了多標簽分類的準確性。

本文分析了現有的特征加權方法，即信息增益、卡方、GSS系數、互信息、優勢比、F1得分和準確度[9]，并提出改進的RF-Boost(IRF-Boost)。本文方法基于權重選擇單個排序特征，傳遞到基礎學習器生成一個新假設，因此不需要檢查所有的訓練特征，甚至不需要檢查排序特征子集。通過實證分析表明，本文方法能夠快速準確地進行多標簽文本分類。

1 Boosting算法

1.1 AdaBoost.MH

AdaBoost.MH算法中，通過將指數誤差最小化來實現最大限度降低漢明損失：

式中：α(r)為基礎系數，取正實值。

在選擇Z的最小弱假設h(r)后，對下一個Boosting輪(r+1)的分布W(r+1)進行更新和歸一化：

在后續迭代中重復相同過程，直至所有Boosting輪執行完畢。完成所有Boosting輪之后，AdaBoost.MH將選定的弱假設組成最終分類器：

因此，正值表示要分配給給定文本x的正確標簽，負值則表示錯誤標簽：

lH(x)=sign(H(x,l))l=1,2，…,m

(5)

為使用AdaBoost.MH進行文本分類，利用代表訓練文檔的單個詞(詞項)構建弱假設。設T={t1,t2,…,tv}為所有訓練詞項的集合。每個文檔xj表示為包含v個二進制權值的向量x=(x1,x2,…,xv)，其中若ti出現在x中，則xi值為1；否則，xi值為0。

式中：c01和c1l為第r次迭代過程中，根據基礎目標Z(r)的最小化策略選出的常數。為得到詞項ti的c01和c1l值，先將訓練文檔集合分割為兩個子集(X0,X1)：

Xu={x:xi=u}u=0,1

(7)

式中:ti出現在X1中的每個文檔中，且未出現在X0中的任何文檔。

式中：u=0,1;φ(xi,l)為目標函數；p=1或-1。

式(9)和式(10)均加入了較小的值ε，以避免除零。根據文獻[10]，取ε=1/mn。通過選擇α(r)=1，利用式(11)得出Z(r)：

1.2 RF-Boost

在RF-Boost中，首先對訓練特征進行排序，接著在每個Boosting輪中僅利用排序特征的較小子集得到與樞紐詞項相對應的弱假設。在當前Boosting輪選定后，在其后的Boosting輪移除樞紐詞項，并替換為排序特征索引中下一個排序特征。

算法1RF-Boost弱監督學習算入：訓練集S，均勻分布W，Boosting輪數R，訓練特征索引T，特征排序法F，排序特征數k。

輸出：最終分類器H(x,l)。

begin

2.H*←()；

3.W(1)←W；

5.forr←1至Rdo

//對于每次迭代r

6.H(r)←()；

//生成一組弱假設Η(r)，每個弱假設對應一個特征

7.fori←1至kdo

//對于RF中的每個排序特征

//將訓練樣本，當前排

//序特征和權重分布傳入基礎學習器，并得到一個新的弱假設

10.endfor

//選擇最優弱假設

12.forj←1至kdo

16.endif

17.endfor

19.更新W(r +1)；

21.endfor

end

1.3 本文方法

RF-Boost和本文方法之間的差異在于，RF-Boost在每個Boosting輪中，將排序特征的較小子集傳入基礎學習器，用以選擇弱假設；而本文方法則僅選擇一個排序特征。因此，弱假設搜索空間的大小從k(RF-Boost中排序特征數量)降低至1(本文方法)。

算法2本文IRF-Boost的弱監督學習算入：訓練集S，均勻分布W，Boosting輪數R，訓練特征索引T，特征排序法F。

輸出：最終分類器H(x,l)。

begin

2.Η*←()；

3.W(1)←W；

4.forr←1至Rdo

//對于每次迭代r

7.fori←1至|×|do

//對于S中的每個樣本

8.forl←1至|×|do

//對于S中的每個標簽

10.endfor

11.endfor

12.endfor

end

本文方法IRF-Boost可視為RF-Boost的特殊形式，其選定特征數量為1。雖然本文僅將一個特征選擇為樞紐詞項并傳入基礎學習器，但通過本文的實證驗證，確定本文方法能夠如AdaBoost.MH一樣，將弱假設的漢明損失最小化。AdaBoost.MH的最終分類器的漢明損失最大為：

假定訓練特征的數量為2 000個。AdaBoost.MH構建2 000個弱假設，每個假設對應一個特征。對于2 000個弱假設h1,h2,…,h2 000，僅返回特定特征t*上的一個弱假設，該弱假設能夠最小化基礎目標函數Z*的值。假定選定要進入RF-Boost中弱監督學習程序的排序特征的數量為100(k=100，作為用戶的輸入)，則RF-Boost將弱假設的搜索空間從2 000(AdaBoost.MH)降至100。由此，生成的弱假設數量也降至100。在這100個弱假設中，僅選擇一個能夠最小化Z*的弱假設h*用于最終分類器。與之相比，本文方法則將生成的弱假設數量降至1個，對應于傳入基礎學習器的特征(t1)。因此，本文方法中無須執行弱假設選擇，因此加速了弱監督學習過程。

2 特征排序法和BoWT文本表征模型

2.1 特征排序法

用于特征排序的特征加權方法有很多，RF-Boost和本文方法基于通過不同的指標進行特征加權排序，這些指標分別為信息增益、卡方、互信息、優勢比、GSS系數、F1得分和準確度。

對于T中的每個標簽l和特征詞項t，假定tp為l中且包含t的文檔數量，fp為不在l中且包含t的文檔數量，fn為l中且不包含t的文檔數量，tn為不在l中且不包含t的文檔數量。設gPos=tp+fn，gNeg=fp+tn，fPos=tp+fp，fNeg=tn+fn，并設n為訓練集中文檔總數量。將以下每個特征加權(選擇)度量的得分，作為詞項t被分入標簽l的權重。

信息增益(IG)是廣泛使用的詞項重要性度量，以信息理論為基礎[11]。將詞項t分入標簽l的近似信息增益為：

卡方(CHI)測量兩個變量之間的相關性，并評估其獨立性。利用卡方定義詞項t和分類l的獨立性：

互信息(MI)是廣泛使用的特征加權方法，測量兩個變量X和Y所共享的信息程度：

優勢比(OR)測量詞項t出現在類別l中的概率比詞項t不出現在類別l中的概率大多少：

GSS系數(GSS)是一種簡化卡方法，是一種特征選擇法。將詞項t分入標簽l的GSS系數定義為：

F1得分(F1)和準確度(ACC)用于評價分類算法的性能。對于詞項t和分類l，F1得分和準確度的定義分別為：

特征排序法的函數表示為Sort-F[Sc,M]。其中，第1個參數Sc表示所有分類之間的動態調度策略。如輪詢策略，即選取每個分類輪流提出的最優特征；或者均勻隨機策略，以隨機化觀察為基礎，根據分布概率，隨機選擇下一個分類。若已知分類的重要性不平等(例如分類成本等)，則使用該信息對選擇概率分布進行偏移。第2個參數M是分類任務的特征排序指標，可包括特征評分度量，例如信息增益或卡方檢驗等。本文特征排序法的偽代碼如下：

對于數據集的每個分類c：

對于在分類c和所有其他分類之間進行二元子任務區分，根據參數M對所有特征進行排序；

保存分類c的特征排序；

當輸出未完成時：

利用動態調度策略Sc，選擇下一個分類cn；

從排序表中，選出cn的下一個特征fn。

若該fn不在輸出中，則將其添加到輸出中。

2.2 BoWT文本表征模型

BoW(詞袋)是典型的文本表征模型，其使用單個詞在向量空間中表征文本[13]。但BoW會忽略詞的順序及其在文本中的關系，而且BoW會生成高維空間，增加分類算法的訓練時長。文獻[14]的實驗結果表明，基于話題的表征法不適用于不平衡數據。這是因為與樣本較少的分類相關聯的話題數量很少，因此無法完全表現這些類別的特征。文獻[7]提出了BoWT混合式表征法，通過將排序靠前的詞和話題合并到一個表征模型中，解決了較少樣本話題的表征問題。

BoWT如圖1所示，首先使用LDA估計訓練文檔間的話題，然后基于其概率選擇話題，并將話題與排序靠前的詞相結合，生成新的合并表征模型。在評價階段，基于話題估計階段中的LDA輸出，推導出測試文本的話題，并與選定的訓練特征結合，以表征用于評價分類性能的測試文檔。

圖1 BoWT文本表征模型

3 實 驗

3.1 數據集

本文使用文本分類系統評價中常用的四個多標簽數據集：

(1) Reuters-21578，包含135個類別的新聞集合，共包含12 902個文檔，其中9 603個文檔用于訓練，3 299個文檔用于測試。本文在135個類別中，僅使用了包含文本數量較大的10個類別。

(2) 20-Newsgroups(20NG)，一個多標簽文本數據集，包含分布在20個不同新聞組(類別)上的20 000個文檔。本文使用的20NG版本中包含18 846個文檔，分為11 314個訓練文檔和7 532個測試文檔。

(3) OHSUMED，1991年醫學主題(MeSH)摘要集合，目標是將摘要分為23種心血管疾病類別。該數據包含13 929個摘要，分為6 286個訓練摘要和7 643個測試摘要。

(4) TMC2007，為2007年SIAM文本挖掘競賽而開發的多標簽文本數據集，包含22個類別上的28 596個測試樣本，分為21 519篇訓練文本和7 077篇測試文本。

3.2 實驗設置

對每個數據集進行預處理，即詞語切分、標準化、詞干提取、停用詞移除。使用BoWT表征模型表示特征，將每個數據集的估計話題數量設為200個[15]。對于所有的特征排序法，選擇每個數據集的前3 500個權重最高的特征(詞和話題)。利用不同Boosting輪數(從200至2000輪遞增，增量為200輪)對Boosting算法進行評價。使用宏觀平均F1(MacroF1)和微觀平均F1(MicroF1)評價分類性能。

實驗分為兩個步驟：(1) 評價用于RF-Boost的特征排序法；(2) 使用在RF-Boost中性能最優的排序法，對AdaBoost.MH、RF-Boost和本文方法進行比較分析。

本文使用秩和檢驗[16]驗證Boosting算法的統計顯著性。秩和檢驗定義為：

式中：Nd為數據集數量；k為評價的方法的數量；Rj為每個方法的平均秩次。

通過對Boosting算法在不同數據集上的性能秩次進行秩和檢驗，利用式(20)與k-1自由度得到分布，并計算在5%顯著水平下的p值。本文在秩和檢驗后還進行了雙尾Bonferroni-Dunn檢驗，對各方法進行逐對比較。

3.3 結果分析

本文將評價分為兩部分：① 特征排序法在RF-Boost中的性能；② 各Boosting算法的實證比較和統計分析。

3.3.1特征排序法的評價

圖2給出了對于不同的特征排序法，在所有數據集上RF-Boost在MacroF1方面的性能。可以看出，MI特征在除OHSUMED數據集之外的所有數據集上得到了最優性能。這是因為MI計算每個訓練詞項與類別之間的相依性，衡量出現的詞項的信息量，準確地分配標簽。但MI在OHSUMED數據集上體現的性能較差，這是因為該數據集的性質和結構。

(a) 20NG (b) OHSUMED

(c) Reuster (d) TMC2007圖2 RF-Boost的MacroF1在使用不同的特征選擇法的得分

表1給出了對于所有排序方法和所有數據集，在MacroF1和MicroF1上的RF-Boost的最優結果。從表1可知，MI在除OHSUMED數據集之外的所有數據集上均取得了最優MacroF1和MicroF1值；OR特征排序法的平均秩次僅次于MI；OR在OHSUMED數據集上取得了最優MacroF1值；GSS排序法在整體上性能最差。

表1 RF-Boost的最優MacroF1和MicroF1數值(%)

續表1

3.3.2Boosting算法的比較評價

本文通過實驗證明MI的性能最佳，所以將其作為特征排序和選擇方法，對所有Boosting算法進行評價。圖3給出了在使用不同Boosting輪數時，所有Boosting算法在4個數據集上的MacroF1結果。當Boosting輪數超過400時，AdaBoost.MH的性能稍優于RF-Boost。但在Boosting輪數為200至400之間時，本文方法取得了最優性能。本文方法在除TMC2007之外的所有數據集上的性能均優于AdaBoost.MH。圖4給出了MicroF1結果。可見本文方法在20NG和OHSUMED數據集上性能優于AdaBoost.MH，后者在Reuters和RMC2007數據集上性能更好。此外，RF-Boost在除OHSUMED之外的所有數據集上均優于AdaBoost.MH和本文方法。

(a) 20NG (b) OHSUMED

(c) Reuters (d) TMC2007圖3 不同輪數時Boosting算法的MacroF1數值

(a) 20NG (b) OHSUMED

(c) Reuters (d) TMC2007圖4 不同輪數時Boosting算法的MicroF1數值

表2給出了所有數據集上，所有Boosting算法的最優MacroF1和MicroF1數值。為了驗證Boosting算法之間差異的統計顯著性，本文使用5%顯著水平下的秩和檢驗，并進行雙尾Bonferroni-Dunn檢驗，以逐對的方法進行比較。但Boosting算法的最優實驗結果不能用于分析該算法在所有Boosting輪的整體性能，將使用特定Boosting輪數取得的每個分類結果作為驗證統計顯著性的獨立觀察。

表2 所有Boosting算法的最優MacroF1和MicroF1結果(%)

為了驗證Boosting算法之間的差異顯著性，首先基于MacroF1度量，對每個Boosting輪數和所有數據集上的分類性能進行排序。然后，進行秩和檢驗，并根據式(20)得到分布。得出的p值為0.000 1，低于顯著水平(0.05)。這表明方法性能之間存在顯著差異，且剔除具有相同性能的弱假設。在剔除了弱假設后，本文進行雙尾Bonferroni-Dunn檢驗。表3給出了Boosting算法之間的逐對比較，其中秩和檢驗之后進行的雙尾Bonferroni-Dunn檢驗，α=0.5，臨界值為5.991，p值(雙尾)為0.000 1，Bonferroni糾正顯著水平為0.016 7。由表可知，RF-Boost顯著優于本文方法和AdaBoost.MH。此外，本文方法和AdaBoost.MH的性能之間無顯著差異，但本文方法的訓練比AdaBoost.MH要快得多，是比AdaBoost.MH更優秀的分類器。

表3 不同算法之間的逐對比較

3.4 計算成本

假定訓練樣本數為n，分類數為m，訓練特征數(特征選擇之后)為v。AdaBoost.MH中執行一次Boosting迭代的時長與n、m和v為線性關系，即時間復雜度為O(mnv)。RF-Boost將v減少至較少數量k。因此，RF-Boost中一輪Boosting的時間復雜度為O(mnk)。本文方法僅將一個特征傳入基礎學習器，即k=1。因此，本文方法的時間復雜度為O(mn)，即本文方法計算時間與分類數量和訓練集大小是線性相關的。

圖5給出了在Reuters數據集上，不同輪數的Boosting算法的學習成本。測試系統使用Java開發，PC配置了3.00 GHz Inter CORE-i5處理器，8.00 GB RAM，使用Windows 10 64位操作系統。從圖5可知，本文方法在所有案例中速度均最快，其次為RF-Boost，AdaBoost.MH速度最慢。本文方法比AdaBoost.MH快約4倍，因此適用于學習時間要求較高的文本分類任務。

圖5 不同Boosting算法的學習時間

4 結 語

特征排序對RF-Boost的準確度和速度至關重要，本文通過實驗證明，在眾多特征排序法中，MI能夠改進RF-Boost的性能。但由于特征排序法的性能基本上取決于數據集的性質，所以不存在整體上的最優特征選排序法。

本文提出了改進的RF-Boost方法，即IRF-Boost，從排序靠前的特征中選擇一個特征進入基礎學習器，用以生成新的弱假設。實驗結果證明，本文方法能夠加速了學習的過程，且不會降低分類性能。本文方法的性能與AdaBoost.MH無顯著差異，但本文方法的主要特點是快速性，其速度比AdaBoost.MH約快4倍。