一種改進(jìn)的隨機(jī)森林Boost多標(biāo)簽文本分類(lèi)算法

邵孟良 齊德昱

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

0 引 言

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

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

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

1 Boosting算法

1.1 AdaBoost.MH

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

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

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

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

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

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

(5)

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

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

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

(7)

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

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

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

1.2 RF-Boost

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

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

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

begin

2.H*←()；

3.W(1)←W；

5.forr←1至Rdo

//對(duì)于每次迭代r

6.H(r)←()；

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

7.fori←1至kdo

//對(duì)于RF中的每個(gè)排序特征

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

//序特征和權(quán)重分布傳入基礎(chǔ)學(xué)習(xí)器，并得到一個(gè)新的弱假設(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在每個(gè)Boosting輪中，將排序特征的較小子集傳入基礎(chǔ)學(xué)習(xí)器，用以選擇弱假設(shè)；而本文方法則僅選擇一個(gè)排序特征。因此，弱假設(shè)搜索空間的大小從k(RF-Boost中排序特征數(shù)量)降低至1(本文方法)。

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

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

begin

2.Η*←()；

3.W(1)←W；

4.forr←1至Rdo

//對(duì)于每次迭代r

7.fori←1至|×|do

//對(duì)于S中的每個(gè)樣本

8.forl←1至|×|do

//對(duì)于S中的每個(gè)標(biāo)簽

10.endfor

11.endfor

12.endfor

end

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

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

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

2.1 特征排序法

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

對(duì)于T中的每個(gè)標(biāo)簽l和特征詞項(xiàng)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ù)量。將以下每個(gè)特征加權(quán)(選擇)度量的得分，作為詞項(xiàng)t被分入標(biāo)簽l的權(quán)重。

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

卡方(CHI)測(cè)量?jī)蓚€(gè)變量之間的相關(guān)性，并評(píng)估其獨(dú)立性。利用卡方定義詞項(xiàng)t和分類(lèi)l的獨(dú)立性：

互信息(MI)是廣泛使用的特征加權(quán)方法，測(cè)量?jī)蓚€(gè)變量X和Y所共享的信息程度：

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

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

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

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

對(duì)于數(shù)據(jù)集的每個(gè)分類(lèi)c：

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

保存分類(lèi)c的特征排序；

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

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

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

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

2.2 BoWT文本表征模型

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

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

圖1 BoWT文本表征模型

3 實(shí) 驗(yàn)

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

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

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

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

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

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

3.2 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

3.3 結(jié)果分析

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

3.3.1特征排序法的評(píng)價(jià)

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

(a) 20NG (b) OHSUMED

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

表1給出了對(duì)于所有排序方法和所有數(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算法的比較評(píng)價(jià)

本文通過(guò)實(shí)驗(yàn)證明MI的性能最佳，所以將其作為特征排序和選擇方法，對(duì)所有Boosting算法進(jìn)行評(píng)價(jià)。圖3給出了在使用不同Boosting輪數(shù)時(shí)，所有Boosting算法在4個(gè)數(shù)據(jù)集上的MacroF1結(jié)果。當(dāng)Boosting輪數(shù)超過(guò)400時(shí)，AdaBoost.MH的性能稍?xún)?yōu)于RF-Boost。但在Boosting輪數(shù)為200至400之間時(shí)，本文方法取得了最優(yōu)性能。本文方法在除TMC2007之外的所有數(shù)據(jù)集上的性能均優(yōu)于AdaBoost.MH。圖4給出了MicroF1結(jié)果?？梢?jiàn)本文方法在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ù)時(shí)Boosting算法的MacroF1數(shù)值

(a) 20NG (b) OHSUMED

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

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

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

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

表3 不同算法之間的逐對(duì)比較

3.4 計(jì)算成本

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

圖5給出了在Reuters數(shù)據(jù)集上，不同輪數(shù)的Boosting算法的學(xué)習(xí)成本。測(cè)試系統(tǒng)使用Java開(kāi)發(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í)時(shí)間要求較高的文本分類(lèi)任務(wù)。

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

4 結(jié) 語(yǔ)

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

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