一種基于集成學習與類指示器的文本分類方法

蔣宗禮,徐學可

(北京工業(yè)大學計算機學院,北京 100124)

一種基于集成學習與類指示器的文本分類方法

蔣宗禮,徐學可

(北京工業(yè)大學計算機學院,北京 100124)

提出了一種基于集成學習機制與類指示器的文本分類方法.該方法利用 AdaBoost.MH算法框架,在每一輪次中,自適應地計算類指示度,通過加權組合所有成員類指示度,獲得對理想類指示度的一種逼近.利用最終的類指示度所得到的分類器不僅簡單、易于更新,而且泛化能力強.在標準語料集TanCorp-12上的實驗表明,該方法適用于對分類效率要求較高的實時應用,同時可以利用集成學習進行某些知識的精確學習,并將這些知識用于弱分類器,從而實現(xiàn)簡單高效的分類.

機器學習;集成學習;AdaBoost.MH;文本分類;類指示器

大規(guī)模在線文本分類、文本信息檢索、過濾等實時性要求強的應用往往需要泛化能力很強,簡單、快速、高效、易于更新的文本分類方法,目前很少有符合要求的.支持向量機(supportvectormachine,SVM)雖然具備較高的泛化能力,但訓練與分類的過程過于復雜,而基于向量空間模型(vector space model,VSM)[3]相似度的分類器雖然簡單,但分類性能往往達不到實際需求.雖然集成學習技術可以將弱分類器提升為泛化能力很強的強分類器,但大大提高了計算復雜性.作者首先將文本特征視為類指示器,相應定義了類指示度函數(shù)并提出一種基于類指示器的文本分類方法,然后利用集成學習的方法,獲取更精確的類指示度函數(shù),在此基礎上構造等價于集成分類器的分類系統(tǒng),使其既具備集成分類器泛化能力高的特點,又保持簡單、快速易于更新的優(yōu)點.

1 集成學習相關介紹

集成分類器可分為使用同類型單分類器的集成分類器和使用不同類型單分類器的集成分類器.使用同類型單分類器的集成分類器根據(jù)成員分類器生成方式的不同,大致分為 2類.一類以 AdaBoost[4]為代表,在這一類算法中,成員分類器順序生成和執(zhí)行,一個分類器的結(jié)果對下一個分類器產(chǎn)生影響.另一類以 Bagging[5]為代表,成員分類器可以并行生成和執(zhí)行,算法用可重復取樣技術(bootstrap samp ling)生成與原來樣本集中的樣本個數(shù)相同的新樣本集.

Boosting、AdaBoost與 AdaBoost.MH是一類集成學習器.Boosting包括了一系列算法,其基本策略是將一個比隨機猜測略好的弱學習算法提升為強學習算法,不必直接去找通常情況下很難獲得的強學習算法.Adaboost[4]是其中最具代表性的一種,AdaBoost將樣本集{(x1,y1),…,(xm,ym)}作為訓練數(shù)據(jù),其中 xi是問題空間 X中的實例,yi∈{-1,+1}是 xi的類別標簽.AdaBoost在訓練實例空間 X上維護一個權重分布,在初始化時對每個樣本賦相等的權重 1/m,然后用樣本集對成員分類器進行訓練,每次訓練后,對訓練失敗的樣本賦以較大的權重,以便在后面對比較難的樣本集中學習,從而得到一個預測函數(shù)序列 h1,…,hT,其中 hj也有一定的權重.預測效果好的預測函數(shù)權重較大,反之較小.最終的預測函數(shù) h采用有權重的投票方式對新實例進行類屬判別.

AdaBoost.MH[2]將成員分類器定義成 h∶X×Y→R形式,并在 X×Y上維持一個 |X|×|Y|的權重分布.推廣 AdaBoost使它能處理多類多標簽分類問題,實際上是將 X×Y的成員作為推廣的實例形式,在推廣實例(xi,yi)上,成員分類器的輸出是對訓練實例 xi屬于 yi類的支持度的判斷.若輸出值大于 0,表示支持xi屬于 yi類;若輸出值小于 0表示支持 xi不屬于 yi類.輸出值的絕對值越大則可信度越高.它在推廣實例集上維護權重分布,這樣就將多類多標簽化為二類單標簽問題.AdaBoost.MH在 AdaBoost框架下運行,可以看成 AdaBoost的推廣形式,AdaBoost中的一些結(jié)論也適用于 AdaBoost.MH.

Schapire等[2]將基于決策樹樁 (decision stump)的 AdaBoost.MH集成算法用于文本分類系統(tǒng)BoosTexte.它的成員分類器根據(jù)某個單詞出現(xiàn)與否給當前文本賦予一實數(shù)值,用于進行文本的類別可信度預測.文獻[6]對此做了改進,將詞頻分類器集成應用于文本分類.

2 基于類指示器的文本分類方法

進行文本分類往往需要抽取一系列特征來表示文本.這些特征往往跟類別存在一定關聯(lián),起著類指示器作用.設文檔集 D,特征集 F,類別標簽集 C,定義類指示度函數(shù) I∶F×C→(-1,1)用于度量這種關聯(lián),I(f,c)＞0時表示特征 f與類 c正關聯(lián),即表示特征 f在文檔 d中的出現(xiàn)對 d為 c類起支持作用;反之特征 f與類 c負關聯(lián),表示特征 f在文檔 d中的出現(xiàn)對 d為 c類起反對作用.分類器 h∶D×C→R,h(d,c)為文檔 d包含的所有特征的關于類 c的指示度的加權和,表示 d為 c類的可信度,取可信度最高的 c作為d的類標簽.定義權重函數(shù),其值由特征在文檔中的重要程度及特征本身的類區(qū)分度決定 w∶D×F→[0,1],w(d,f)表示文本 d關于特征 f的權重.值得說明的是本文采用詞作為其特征,實際上,特征可以是關鍵短語、n-gram、詞組、領域詞典中的領域關聯(lián)詞等,他們具備一定類指示作用.

算法 1 基于類指示器的分類方法(category indicator based method,CIM)

假設?〈f,c〉∈F×C,I(f,c)已經(jīng)事先計算

初始化:h(d,c)=0

輸入:d∈D

顯然這是一種相當簡單、快速、高效的分類方法,同時也易于更新,只要提取對新特征的類指示度,并添加到特征庫中,便可完成對分類模型的更新,這在網(wǎng)絡時代中新詞不斷出現(xiàn)的情況下尤其重要.但該方法中類指示度的學習過于依賴訓練集的規(guī)模與質(zhì)量,可能難以有效處理新例,泛化性能低.本文期望利用集成學習的方法,獲取更精確的類指示度,在此基礎上構造等價于集成分類器的分類系統(tǒng),使其既具備集成分類器泛化能力高的特點,又能保持簡單、快速易于更新的優(yōu)點.

3 算法框架

本文的工作以 AdaBoost.MH作為集成學習的框架,不同于 Schapire,這里的成員分類器采用綜合考慮文本所有特征的基于類指示器的方法,來獲得更精確的類指示度函數(shù),并以此構造最終的分類器,與一般集成分類器相比,它不需要在執(zhí)行過程中對各成員分類器的加權融合.基于 AdaBoost.MH框架,隨著權重分布的自適應更新,每一輪的類指示度函數(shù)的學習重點考慮那些權重較大的文檔,相應的分類器更多體現(xiàn)這些樣本的特性,各輪的類指示度函數(shù)及相應分類器側(cè)重不同訓練空間的特性,具備一定的差異性,將各輪的類指示度函數(shù)加權融合,得到的分類器具有較高的穩(wěn)定性與泛化能力.

3.1 主要思路

3.2 算法

算法 2 基于集成學習的 CIM

for t=1,…,T;T為事先確定的迭代次數(shù)

1)基于權重分布 Wt(di,cj)(i=1,…,g,j=1,…,m)學習類指示度函數(shù),It∶F×C→(-1,1)

2)基于類指示度函數(shù),得到成員分類器 ht∶D×C→R

3)評估成員分類器 ht

若 cj∈ Ci返回 Ci[cj]=1否則 Ci[cj]=-1

4)更新權重分布

因此,這 2種分類器是等價的,而利用 h分類時需要存儲 T個分類模型,分類時需用每個成員分類器進行分類并對其結(jié)果加權融合,時間與空間開銷大,利用 h′分類時,只需存儲一個分類模型(特征的類指示度可以事先計算并存儲),進行一次分類過程,時間與空間開銷大為減少,同時具備集成分類器泛化性能高的優(yōu)點.

3.3 權重函數(shù)及類指示度函數(shù)

3.3.1 權重函數(shù)

在向量空間模型(vector space model,VSM)[3]中,用向量表示文檔,它的每一維對應于文檔的一個特征項,特征項的權重一般與特征項在文檔中的重要程度以及特征項的類區(qū)分能力有關,一般采用 TF-IDF方法計算,該方法簡單地認為文本頻數(shù)少的特征項重要顯然過于武斷.如果以特征選擇中的評估函數(shù)代替 IDF函數(shù),對特征項進行權值調(diào)整,就有希望得到高質(zhì)量的向量空間法[7],本文采用互信息(mutual information,MI),以文檔 d改進的 VSM中表示特征 f的權重作為 w(f,d)的值

式中,tf(fi,d)定義為 fi在 d中出現(xiàn)頻率;m(fi)為 fi的互信息評估函數(shù)值;f1,…,fn為 d包含的特征.另外,本文的特征選擇也采用互信息.

3.3.2 類指示度函數(shù)

方法1

該方法受特征選擇中的互信息方法啟發(fā),設

式中,Pr(f)表示特征 f在訓練文本集合中出現(xiàn)的概率;Pr(f|c)表示在 c類的文本中 f出現(xiàn)的條件概率,當Pr(f|c)＞Pr(f)時 Pr(f|c)＞0,表示特征 f與類別 c正關聯(lián),反之表示負關聯(lián).采用比值的方式可以比較純粹的學習特征的類關聯(lián)性,而與特征的頻度無關.

類指示度函數(shù)為

式(4)將 m(f,c)映射到(-1,1),避免 m(f,c)值之間的過大差異,防止個別特征對分類結(jié)果影響過大,保證分類器的穩(wěn)定性.

在 AdaBoost.MH每一輪次中,都要根據(jù)新的權重分布,重新計算 Pf(f|c)與 Pr(f),從而實現(xiàn)類指示度的自適應調(diào)整.

式中,Wt表示第 t輪次的權重分布;n(d,f)為 f在文檔 d中出現(xiàn)次數(shù).

方法2

文獻[2]中的決策樹樁分類器按一定標準選擇某個詞,分類器以該詞的出現(xiàn)與否給當前文本賦予實數(shù)值,實現(xiàn)文本的判別,受其賦值公式啟發(fā),設計了類指示度函數(shù)

設 Df={d|d∈ D,f∈ d},令

式中,Cd表示文檔 d的類標簽集;(f)表示子集 Df中標記為 c類的文檔權重之和(f)表示子集 Df中不被標記為 c類的文檔權重之和;Wc為在權重分布 W基礎上調(diào)整所得,滿足,其中表明 c類文檔的權重和與其他文檔相同.可以對 c類文檔進行如下調(diào)整

3.4 分類的時間復雜度

該方法利用特征類指示度構造最終的分類器,與集成分類器相比,它不需要在分類過程中對各成員分類器的加權融合.

總的分類過程步驟為:1)檢索到每個文檔特征相應的類指示度;2)對每個類別把所有特征關于該類的指示度加權和作為文檔為該類的可信度;3)取可信度的類作為文檔的類標簽.利用 Trie樹等高效的檢索數(shù)據(jù)結(jié)構,可以在常數(shù)時間找到某特征的指示度,因此步驟 1)時間復雜度為 O(|Fd|)(Fd為文檔 d的特征集),總時間復雜度為 O(|Fd|×|C|).考慮類別數(shù)固定,總時間復雜度可為 O(|Fd|),表明這是一種線性分類器,適用于在線分類.

3.5 算法的進一步改進

值得注意的是,Boosting和 Bagging的迭代輪次數(shù)并非越多越好,學習系統(tǒng)性能的改善主要發(fā)生在最初的若干輪次中.Schapire和 Singer指出,迭代次數(shù)過多,AdaBoost.MH有可能發(fā)生過適應[8].實驗過程中也發(fā)現(xiàn)文本的方法迭代次數(shù)較少時,性能提升明顯,隨著迭代次數(shù)進一步增加,性能反而下降.通常可以構建驗證數(shù)據(jù)集,取驗證數(shù)據(jù)集性能最優(yōu)的迭代次數(shù)作為最終參數(shù).

這是由于 AdaBoost算法存在類權重分布扭曲的現(xiàn)象,導致對個別類的過度重視以及對其他若干類的偏見,生成的預測規(guī)則在測試集上的分類錯誤急劇增加,發(fā)生退化現(xiàn)象[9].本文的訓練過程中也出現(xiàn)了該現(xiàn)象,作者對 AdaBoost.MH進行改進,在一定程度上緩解了該問題,方法是經(jīng)過若干輪次迭代后調(diào)整權重分布,然后對分布進行歸一化.調(diào)整公式為

4 實驗和討論

實驗采用 TanCorp-12語料集[10-11].該語料包含 12類,共有 14 150篇文檔.12類分別為財經(jīng)、地域、電腦 、房產(chǎn) 、教育 、科技 、汽車 、人才 、體育 、衛(wèi)生 、藝術與娛樂 .

作者利用經(jīng)典集成學習技術,目標是獲取既有較高分類性能又有較高分類效率的文本分類方法.首先,將本文的方法跟目前主流分類方法做性能比較.作者用精度(precision)考查分類器在各個類別上的性能,并用微 F1值(Micro-F1)考查綜合性能[12].將本文方法與常見的中心法(centroid)[13],Rocchio法[14],K-最近鄰法 (k-nearest neighbors,KNN)[15],樸素貝葉斯法 (na?ve bayes,NB)[16],支持向量機法(supportvector machine,SVM)[17],決策樹法(decision tree,DT)(具體采用 SPRINT決策樹算法[18])等進行比較.其中 KNN方法參數(shù) K的取值為 15,SVM方法采用開源工具 LibSVM[19],核函數(shù)采用 linear kernel,其他參數(shù)取默認值.將采用方法 1作為類指示度計算方法的分類方法記為 CIM1,采用方法 2的記為CIM2,把整個語料隨機分成 5份,然后取其中的 2份進行訓練,剩余取1份作測試.采用 MI方法進行特征選擇,具體的評估函數(shù)為

式中,Pr(f)表示特征 f在訓練文本集合中出現(xiàn)的概率;Pf(f|c)表示在 c類的文本中 f出現(xiàn)的條件概率,取詞頻超過 15的前 5 000個詞作為候選特征.CIM 1與 CIM 2的迭代次數(shù)為 100.

從結(jié)果看出 CIM1,CIM 2都表現(xiàn)出較高的性能,其中 CIM1的 Micro-F1指標僅次于 SVM和 Rocchio,而CIM2甚至接近目前公認文本分類性能較好的 SVM,見表 1.此外 CIM2方法性能好于 CIM 1,是本文推薦的方法.

表 1 本文方法與經(jīng)典文本分類方法性能比較Table 1 The com parison of the p roposed methods and traditionalmethods

CIM2方法性能略低于 SVM,但該方法的最大優(yōu)勢在于分類效率,是一種線性分類器,適用于在線分類.3.4節(jié)給出其算法時間復雜度分析,此外還記錄了 CIM 2與 SVM算法測試時間(這里時間開銷為分類過程開銷,不包括算法無關的文本預處理時間,實驗機器配置為 Pentium-4,2.3GHz CPU及 1 024M內(nèi)存的機器上,開發(fā)環(huán)境為 Java JDK1.6)分別為 78和 116032ms,可以明顯看出 CIM2時間開銷遠小于 SVM.此外,本文的方法僅是一種框架性方法,其中類指示度函數(shù)的計算方法是開放,選取更合理的類指示度函數(shù)及權重函數(shù)還可以進一步提升分類性能.

基于改進的 AdaBoost.MH的 CIM2,記為 CIM2-Adv,與 CIM2方法相比,CIM2-Adv每經(jīng)過 40輪次迭代后用式(8)調(diào)整權重分布.圖 1給出了 CIM2-Adv與 CIM2方法取不同迭代次數(shù) T時 Micro-F1指標變化情況.

從圖 1可以發(fā)現(xiàn):1)迭代次數(shù)較少時,CIM2-Adv性能不如 CIM2,表明原有的權重自適應更新機制更加有效,式(8)在一定程度上破壞了原有的Boosting機制,導致性能不理想;2)隨著迭代次數(shù)增加,CIM2出現(xiàn)性能退化現(xiàn)象,而 CIM2-Adv性能依然保持上升趨勢,最終 CIM 2-Adv的性能超過 CIM2最佳性能,表明本文提出的方法在一定程度上緩解了經(jīng)典方法權重扭曲問題.

圖1 CIM 2-Adv與 CIM 2方法 Micro-F1指標依迭代次數(shù) T變化Fig.1 The Micro-F1 values of CIM 2.Adv and CIM 2 with different iteration count T

5 結(jié)束語

集成學習的動機就是將弱分類器提升為高泛化性能的強分類器,但大大增加了計算復雜性.為了解決該矛盾,本文提出基于集成學習機制與類指示器的文本分類方法.該方法利用 AdaBoost.MH算法框架,在每一輪次中,自適應地計算類指示度.通過加權組合所有成員類指示度,獲得對理想類指示度的一種逼近.基于最終的類指示度,得到的分類器不僅簡單易于更新,同時也獲得了集成分類器泛化能力強的優(yōu)點.考慮到它的簡單性,適用于對分類效率要求較高的實時應用.針對 AdaBoost權重分布扭曲現(xiàn)象本文對 AdaBoost.MH進行改進,取得初步效果.結(jié)果也表明,利用集成學習進行某些知識的精確學習,并將這些知識應用于弱分類器,可以獲得簡單高效的分類模型.本文的方法是僅僅一種框架性方法,類指示度函數(shù)的定義是開放,如何定義更加合理的類指示度函數(shù)是進一步研究的內(nèi)容.

[1]DIETTERICHL TG.Machine learning research:four current directions[J].AIMagazine,1997,18(4):97-136.

[2]SCHAPIRE R,SINGER Y.BoosTexter:a boosting based system for text categorization[J].Machine Learning,2000,39(203):135-168.

[3]SALTON G,WONG A,YANG C.A vector spacemodel for automatic indexing[J].Commu of ACM,1995,18:613-620.

[4]FREUND Y,SCHAPIRE R E.A decision-theoretic generalization of on-line learning and an app lication to boosting[J].Journalof Computer and System Sciences,1997,55(1):119-139.

[5]BREIMAN L.Bagging p redictors[J].Machine Learning,1996,24(2):123-140.

[6]姜遠,周志華.基于詞頻分類器集成的文本分類方法[J].計算機研究與發(fā)展,2006,43(10):1681-1687.JIANG Yuan,ZHOU Zhi-hua.A text classification method based on term frequency classifier ensemb le[J].Journal of Computer Research and Development,2006,43(10):1681-1687.(in Chinese)

[7]FRANCA D,FABRIZIO S.Supervised term weighting for automated text categorization[C]∥Proceedings of the 2003 ACM Symposium on Applied Computing.Melbourne,Florida:ACM Press,2003:784-788.

[8]SCHAPIRE RE,SINGER Y.Improved boosting algorithms using confidence-rated predictions[J].Machine Learning,1999,38:297-336.

[9]GUINLAN J R.Bagging,boosting,and C4.5[C]∥Proceedings of the Thirteenth National Conference on Artificial Intelligence.Portland,Oregon:AAAI Press and the MIT Press,1996:725-730.

[10]譚松波,王月粉.中文文本分類語料庫-TanCorpV 1.0[DB/OL].http:∥www.searchforum.org.cn/tansongbo/corpus1.php TANSong-bo,WANGYue-fen.A corpus for Chinese text categorization-TanCorpV1.0[DB/OL].http:∥www.searchforum.org.cn/tansongbo/corpus1.php(in Chinese)

[11]TAN Song-bo.A novel refinement approach for text categorization[C]∥ACM CIKM 2005.Bremen,Germany:ACM Press,2005:469-476.

[12]SEBASTIAN F.Machine learning in automated text categorization[J].ACM Computing Surveys,2002,34(1):1-47.

[13]HAN E,KARYPISG.Centroid-based document classification analysis＆ experimental result[C]∥PKDD 2000.Lyon,France:Springer Berlin/Heidelberg,2000:116-123.

[14]JOACHIMS T.A probabilistic analysis of the rocchio algorithm with TFIDF for text categorization[C]∥Proceedings of International Conference on Machine Learning(ICML).Nashville,Tennessee,USA:Morgan Kau fmann Publishers Inc,1997:143-151.

[15]YANG Y,LIU X.A re-examination of text categorizationmethods[C]∥Proceedings of ACM SIGIR Conference on Research and Development in In formation Retrieval(SIGIR'99).Berkley,USA:ACM Press,1999:42-49.

[16]MLADENICD,GROBELNIK M.Word sequences as features in text-learning[. C]∥Proceedings of ERK-98,the Seventh Electrotechnical and Computer Science Con ference.Ljubljana,Slovenia:IEEE Press,1998:145-148.

[17]JOACHIMST.Text categorization with support vector machines:learning with any relevant features[C]∥Proceedings of CML-98,10th European Conference on Machine Learning.Chemnitz,Germany:Springer Berlin/Heidelberg,1998:137-142.

[18]SHAFER JC,AGRAWAL R,MEHTAM.SPRINT:a scalab le parallel classifier for datamining[C]∥Proc of the 1996 Int Conf Very Large Data Bases.Bombay,India:ACM Press,1996:544-555.

[19]CHANG C,LIN C.LIBSVM:a library for support vector machines[CP/OL].2001.http:∥www.csie.ntu.edu.tw/～cjlin/libsvm/.

(責任編輯 鄭筱梅)

An Ensemble Learning and Category Indicator Based Text Categorizing Method

JIANG Zong-li,XU Xue-ke
(College of Computer Science,Beijing University of Technology,Beijing 100124,China)

As it is well known that the motivation of ensemble learning is to boost a strong classifier with high generalization ability from aweak classifier.However,the achievement of generalization ability isoften at great cost of complexity and intense computation.In this paper an ensemble learning and category indicator based categorizing method is proposed and Adaboost.MH based mechanism is developed to adaptively compute the category indicating function at every step.Then all individual category indicating functions are combined with weightand an approximation to the expected category indicating function is obtained.Based on the combined category indicating function,a classifier,which has low computational cost,flexibility in updating with new features and suitable for real-time applications has been obtained.Furthermore it is proved that the proposed method is equivalence to ensemble classifier and thereby it has high generalization ability.Experiments on the corpus of Tan Corp-12 show that the proposed method can achieve good performance in text categorizing tasks and outperform many text categorizing methods.

machine learning;ensemble learning;Ada Boost.MH;text categorization;category indicator

TP 181

A

0254-0037(2010)04-0546-08

2008-05-08.

蔣宗禮(1956—),男,河南南陽人,教授.

文本分類是在給定分類體系下,根據(jù)內(nèi)容對未知類別文本進行歸類.文本分類是處理和組織大規(guī)模文本信息的關鍵,能使信息資源得以合理有效組織,是信息處理領域最重要的研究方向之一.文本分類技術也是主題搜索、個性化信息檢索、搜索引擎目錄導航、信息過濾等的核心技術,對于解決有效獲取有效網(wǎng)絡信息,研究新一代搜索引擎有著重要意義.

集成學習為解決同一個問題訓練出多個分類器,在對新的數(shù)據(jù)進行處理時,將各個分類器的結(jié)論以某種方式進行綜合.這種方法能克服各個分類器對訓練集的過擬合問題,提高泛化能力,從而盡可能好地處理新數(shù)據(jù),因此集成學習受到國際機器學習界的廣泛重視,被機器學習權威專家 Dietterich認為是當前機器學習的四大研究方向之首[1],在包括文本分類的多個領域得到廣泛應用[2].