邵孟良 齊德昱

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

0 引 言

互聯(lián)網(wǎng)上海量的數(shù)據(jù)通常以非結(jié)構(gòu)化的形式表示和存儲，需要通過高效的自動文本分類[1]系統(tǒng)來管理和組織這些數(shù)據(jù)。因此，文本分類是非常重要的研究領(lǐng)域。

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

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

1 Boosting算法

1.1 AdaBoost.MH

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

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

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

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

因此，正值表示要分配給給定文本x的正確標(biāo)簽，負(fù)值則表示錯誤標(biāo)簽：

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

(5)

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

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

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

(7)

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

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

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

1.2 RF-Boost

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

算法1RF-Boost弱監(jiān)督學(xué)習(xí)算入：訓(xùn)練集S，均勻分布W，Boosting輪數(shù)R，訓(xùn)練特征索引T，特征排序法F，排序特征數(shù)k。

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

begin

2.H*←()；

3.W(1)←W；

5.forr←1至Rdo

//對于每次迭代r

6.H(r)←()；

//生成一組弱假設(shè)Η(r)，每個弱假設(shè)對應(yīng)一個特征

7.fori←1至kdo

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

//將訓(xùn)練樣本，當(dāng)前排

//序特征和權(quán)重分布傳入基礎(chǔ)學(xué)習(xí)器，并得到一個新的弱假設(shè)

10.endfor

//選擇最優(yōu)弱假設(shè)

12.forj←1至kdo

16.endif

17.endfor

19.更新W(r +1)；

21.endfor

end

1.3 本文方法

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

算法2本文IRF-Boost的弱監(jiān)督學(xué)習(xí)算入：訓(xùn)練集S，均勻分布W，Boosting輪數(shù)R，訓(xùn)練特征索引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中的每個標(biāo)簽

10.endfor

11.endfor

12.endfor

end

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

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

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

2.1 特征排序法

用于特征排序的特征加權(quán)方法有很多，RF-Boost和本文方法基于通過不同的指標(biāo)進(jìn)行特征加權(quán)排序，這些指標(biāo)分別為信息增益、卡方、互信息、優(yōu)勢比、GSS系數(shù)、F1得分和準(zhǔn)確度。

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

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

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

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

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

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

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

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

對于數(shù)據(jù)集的每個分類c：

對于在分類c和所有其他分類之間進(jìn)行二元子任務(wù)區(qū)分，根據(jù)參數(shù)M對所有特征進(jìn)行排序；

保存分類c的特征排序；

當(dāng)輸出未完成時：

利用動態(tài)調(diào)度策略Sc，選擇下一個分類cn；

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

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

2.2 BoWT文本表征模型

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

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

圖1 BoWT文本表征模型

3 實 驗

3.1 數(shù)據(jù)集

本文使用文本分類系統(tǒng)評價中常用的四個多標(biāo)簽數(shù)據(jù)集：

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

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

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

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

3.2 實驗設(shè)置

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

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

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

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

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

3.3 結(jié)果分析

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

3.3.1特征排序法的評價

圖2給出了對于不同的特征排序法，在所有數(shù)據(jù)集上RF-Boost在MacroF1方面的性能。可以看出，MI特征在除OHSUMED數(shù)據(jù)集之外的所有數(shù)據(jù)集上得到了最優(yōu)性能。這是因為MI計算每個訓(xùn)練詞項與類別之間的相依性，衡量出現(xiàn)的詞項的信息量，準(zhǔn)確地分配標(biāo)簽。但MI在OHSUMED數(shù)據(jù)集上體現(xiàn)的性能較差，這是因為該數(shù)據(jù)集的性質(zhì)和結(jié)構(gòu)。

(a) 20NG (b) OHSUMED

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

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

表1 RF-Boost的最優(yōu)MacroF1和MicroF1數(shù)值(%)

續(xù)表1

3.3.2Boosting算法的比較評價

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

(a) 20NG (b) OHSUMED

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

(a) 20NG (b) OHSUMED

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

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

表2 所有Boosting算法的最優(yōu)MacroF1和MicroF1結(jié)果(%)

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

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

3.4 計算成本

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

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

圖5 不同Boosting算法的學(xué)習(xí)時間

4 結(jié) 語

特征排序?qū)F-Boost的準(zhǔn)確度和速度至關(guān)重要，本文通過實驗證明，在眾多特征排序法中，MI能夠改進(jìn)RF-Boost的性能。但由于特征排序法的性能基本上取決于數(shù)據(jù)集的性質(zhì)，所以不存在整體上的最優(yōu)特征選排序法。

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