多文本分類器組合方法

摘要：自由文本分類已經成為當前的研究熱點，目前存在的文本分類算法已經很多，分類精度大多在70%以上。顯然，研究存在哪些因素影響分類器的分類效果，并進一步提高當前分類算法的分類精度是十分有意義的。本文較全面地分析了分類器精度的影響因素，設計了幾種分類器選舉器，并給出了這些選舉器的實驗結果，結果表明，合理的選舉器設計能適當提高分類器精度。

關鍵詞：文本分類；分類選舉器；裝袋；推進

中圖分類號：TP751文獻標識碼：A文章編號：1674-7712 (2014) 08-0000-03

一、引言

眾所周知，因特網上的資源呈指數級增長，許多資料都需要分類，包括結構化和非結構化或半結構化的文檔資料，諸如：網頁、電子郵件、自由文本等等。近年來，文本分類技術已經逐漸與搜索引擎、信息過濾等信息處理技術相結合，有效地提高了信息服務的質量。文本分類指的是在給定的分類體系下，根據文本的內容自動地確定文本關聯的類別。

目前，在進行文本分類時，通常采用向量空間模型（VSM）表示文本，基于VSM的分類器有樸素貝葉斯、KNN、簡單向量距離分類法等，這些分類器的實現相對簡單，但實際應用中卻具有較高的分類精度。實現基于VSM的分類器，需要對訓練例集進行特征提取，得到特征集FS={f1，f2，…，fn}，所謂特征就是出現在文本中的詞或詞組；然后用FS去刻畫文本Dk，得Dk的權重向量DkW={w1，w2，…，wn}(i=1，2，…，n)，其中wi的值可能是fi在Dk中的詞頻，也可能是通過TF-IDF計算出來的值[1]（視分類器需要而定）。

對于分類器的性能測試，可采用開放測試和封閉測試兩種方式。開放測試指的是測試例集中不包含訓練例，而封閉測試則正好相反。對分類器性能好壞的評價，通常有兩個指標：查準率和查全率[1]。前者是所有判斷的文本中與人工分類結果吻合的文本所占的比例；后者是人工分類結果應有的文本中分類系統吻合的文本所占的比例。查全率和查準率反映了分類質量的兩個方面，兩者必須綜合考慮，故在實際應用中，人們通常還采用F1指標值來評價分類器的好壞，其數學公式如下：

F1=(查全率＊查準率＊2)/(查全率+查準率) （1）

二、影響分類器精度的因素

影響一個分類器性能的因素有很多。首先，特征子集提取方法對于分類器會產生一定影響。若一種方法對于各類別的訓練例提取出來的特征子集“最能”代表各個類別，顯然用于分類時會提高分類器的分類效果。這就要求提取方法：（1）對某類別訓練例，提取出在該類別訓練例中“頻繁”出現，而在其它類別訓練例中“基本不出現”的特征；（2）對在各個類別（或某向個類別）中“分布較均勻”的特征（顯然對于分類無意義），不進行選??；（3）對于在某類別中“出現次數較少”的特征也不應該入選特征子集。IG、MI和Odds Ratio等方法考慮了上述三個方面[5]，在實際使用中應用較多；而DF方法[5]沒有充分考慮到（2），但由于該方法實現起來相對簡單，提取效率較高，而且分類效果也非常不錯，甚至超過其它方法的分類表現，故不少分類器系統采用了該方法。

其次，訓練例的多少及分布會影響分類器性能。在訓練例少的情況下，特征子集提取的效率較高，特征子集維數相對較少，分類效率也較高，但在這種情況下，分類器效果卻不理想，原因在于很多本來最能代表某類別的特征，由于在該類別的訓練例中出現次數相對較少而不被入選到特征子集中，而出現次數較少的原因就在于訓練例太少了。訓練例分布不均勻，指的是某些類別的訓練例相對較少，但其它類別訓練例卻較多，這種情況造成特征子集中特征分布的不均勻，也無法使分類器具有較好表現。

再次，分類類別個數的多少也直接影響分類效果。道理很顯然，如果只有兩種類別，分類器對于一個新文本，待判定的情況只有兩種，而對于100種類別的情況，其判定可能卻有100種。我們在實驗中也驗證了這一點。

第四，訓練例集中存在著手工分類錯誤的訓練例，顯然會影響分類器的性能。

最為重要的影響因素是分類器算法的好壞。目前，普遍認為是支持向量機具有最好的分類表現，但實現相對復雜，且效率較低。較廣泛使用的是樸素貝葉斯[3]、KNN[4]、簡單向量距離[1]等分類法。

當然，還有其它的因素會影響分類器的精度。因此，研究如何提高分類精度，實際上就是研究如何避免這些影響因素，上述影響要素中有些是可以通過改進分類器算法和特征子集提取算法避免的，有些卻是可以人為避免的。本文主要討論的是對于分類器算法的改進。

三、裝袋和推進方法

裝袋和推進是兩種改進分類法準確率的技術，它們都是將T個學習得到的分類器C1，C2，…，CT組合起來，旨在創建一個改進的分類器C*。

裝袋過程如下[4]：

FOR i=1 TO T DO

從訓練例集S中隨機選取訓練例子集Si(Si采用放回選樣)

從Si中學習得到分類器Ci

ENDFOR

將C1，C2，…，CT裝袋得到C*。對于新文本，C1，C2，…，CT分別判定新文本最有可能的所屬類別，由C*統計哪個類別的得票數最高，將該類別輸出。

推進方法[2]的主要思想是從訓練例學習出一系列的分類器，每一個分類器根據前一個分類器錯誤分類的實例，對訓練集的權重進行修正，再學習新的分類器。其算法如下：

輸入：N個訓練例〈（d1，y1），…，(dn，yn)>

N個訓練例的權向量D，Di（i=1，2，…，n）的初始值為1/N

輸出：hT

算法：

FOR s=1 TO T DO

調用弱學習算法，得到一個假設hs

計算αs=1/2*ln( )，其中

IF hs(di)=yi THEN

D(s+1)(i)= ，Zs為使 的規范化因子，下同。

ELSE

D(s+1)(i)=

ENDIF

ENDFOR

裝袋和推進方法的時間復雜度為O(T*E*F)，其中T為趟數，E為訓練例個數，F為特征集中特征個數。

四、分類選舉器設計

就裝袋和推進方法而言，每一趟訓練過程中，使用的訓練例集不同。裝袋方法中，雖然得到多個分類器，但“袋”中的每一個分類器的分類模型相同；對于推進方法而言，最終只輸出一個分類器，該分類器具有較高的分類精度，但該方法的訓練時間太長。

我們在實現具體的分類系統的時候，利用裝袋和推進方法的思想，設計了如下的分類選舉器（以下簡稱為C_Voter），實驗結果表明，這樣的分類選舉器具有較好的分類性能。

設有類別集合C={c1，c2，…，c|C|}，Ci類別的訓練例集為Ei，Ci類別的測試例集為Ti（i=1，2，…，|c|）。C_Voter的設計思想如下：

（1）從訓練例集中學習出K個不同模型的分類器Classifier1，Classifier2，…，ClassifierK；

（2）用測試例對各個分類器進行測試，可以得出Classifieri在Tj上的查全率、查準率和F1指標值(i=1，2，…，K;j=1，2，…，|c|)；

（3）對于新文本，K個分類器分別可得出K個分類結果，設Classifieri對于新文本的輸出結果為Classj (i=1，…，K;j=1，…，|c|)，Classifierm對于新文本的輸出結果為Classn(m=1，…，K;n=1，…，|c|)，我們相信Classj還是Classn？如果Classifieri在Classj對應的Tj測試例上的查全率(或查準率、或F1指標)高于Classifierm在Classn對應的測試例Tn上的查全率（或查準率、或F1指標），則我們相信Classj ，否則相信Classn；為了下面的描述方便，我們稱依據查全率來決定輸出結果的選舉器為“RC_Voter”，稱依據查準率來決定輸出結果的選舉器為“PC_Voter”，稱依據F1來決定輸出結果的選舉器為“F1 C_Voter”。

對于從訓練例集中學習出K個不同模型的分類器，我們還實驗了下面兩種選舉器：

Voter_1：判定新文本類類別采用投票法，其基本思想是：如果多數分類器都認為新文本的類別為Cj，則輸出Cj(j=1，…，|c|)。

Voter_2：設Classifieri采用公式formula(i)（i=1，2，..，K）計算新文本屬于各個類別的概率值（或相似性值），取C*= ，利用C*去計算新文本屬于各個類別的概率（或相似性值），并取最大值對應的那個類別為輸出。其中ai為分類器權重，即如果我們認為我們更應該相信分類器Classifieri，則可以將ai設置得相對大些，否則設小些，且 =1。

五、實驗結果

作者選取Rainbow數據集（http://www-2.cs.cmu.edu/afs/cs/project/theo-11/www/naive-bayes.html）對分類選舉器做了相應實驗。Rainbow數據集是一個具有20個類別的新聞組數據，每個類別都有100個文檔。每個文檔即是一封完整的郵件。對于每一個類別，我們隨機選取70個文本作為訓練例，另30個作為測試例。

在實驗中，作者選取了如下三個分類器：基于Multi-variate Bernoulli Model[3]的樸素貝葉斯分類器、基于Multinomial Model[3]的樸素貝葉斯分類器、簡單向量距離分類器[6]。為簡單起見，我們分別稱上述三個分類器為MVC、MMC和S_VSM，之所以選取這三個分類器進行實驗，是因為：（1）都是基于VSM的，因此可以共用相同的數據結構；（2）實現起來都相對簡單；（3）三個分類器分類速度及精度都較高，這種情況下與選舉器的實驗結果相比較，更能說明選舉器的設計是否合理。分類選舉器的時間復雜度在O(E*F)，E為訓練例個數，F為特征數。

圖1六種分類器在查準率上的比較

對分類器和選舉器的測試采用的是開放測試方法，圖1給出了MVC、MMC、S_VSM、PC_Voter、Voter1和Voter2的查準率比較結果。圖1 表明，“PC_Voter”在大多數類別上的查準率都優于其它的分類器或Voter，說明PC_Voter的設計是比較合理的。Voter1的效果比任何一個分類器的都要差，說明Voter1的設計是不合理的。Voter2的表現總體上優于MMC和S_VSM，但與MVC相比，在各類別上的查準率都沒有優于MVC的，至多是相等，說明Voter2的設計也不盡合理（實驗中， MVC權重設置為0.5，MMC的為0.3，S_VSM的為0.2）。

圖2四種分類器在查全率上的比較

圖2是MMC、MVC、S_VSM、“RC_Voter”在查全率上和比較示意圖。從圖中可以看出，“RC_Voter”的查全率總體上優于MMC、MVC及S_VSM。值得一提的是，RC_Voter對大部分類別的查準率都在90％以上，總體查準率比三個分類器中最高的總體查準率提高了4個百分點。

圖3顯示的是MMC、MVC、S_VSM、“F1 C_Voter”在F1指標上的實驗結果。從圖中可以看出“F1 C_Voter”在大多數類別上的F1指標值較三個分類器都有較大提高。尤其值得一提的是：三個分類器分類效果都較差的某些類別的測試例集上，“F1 C_Voter”都有較好的表現，且總體查全率和查準率都有5%左右的提高。

圖3四種分類器在F1指標上的比較

六、結束語

袋裝和推進方法雖然可以從一定程度上提高分類器精度，但訓練時間相對較長。從實驗情況來看，本文設計的三個C_Voter是比較合理的，它能從一定程度上提高參與選舉的分類器的查全率、查準率、F1指標值。而且由于可以選擇基于相同數據結構的分類器算法，從而使實現起來相對簡單。

參考文獻：

[1]李文斌，劉椿年，鐘寧.基于兩階段集成學習的分類器集成[J].北京工業大學學報，2010(03):411-419.

[2]Robert Schapire，Yoram Singer，Amit Singhal.A Boosting and Rocchio Applied to Text Filtering[EB/OL].http://citeseer.nj.nec.com/schapire98boosting.html，2002(12).

[3]Andrew Mccallum， Kamal Nigam. A Comparison of Event Models for Na#239;ve Bayes Text Classification[EB/OL[.http://citeseer.nj.nec.com/mccallum98comparison.html，2002(12).

[4]Jiawei Han，Micheline Kamber.Data Mining Concepts and Techniques[M].北京:高等教育出版社，2001.

[5]Suresh K.Choubey，Jitender S.Deogun，Vijay V.Raghavan，Hayri Sever.A Comparison of Feature Selection Algorithms in the Context[EB/OL].http://citeseer.nj.nec.com/choubey96comparison.html，2002(12).

[6]李文斌，陳嶷瑛，張娟.使用Fisher 線性判別方法的提取分類器[J].計算機工程與應用，2010(14):132-134.

[作者簡介]申建國（1978.01-），河北邯鄲人，學士學位，本科，工程師，職員，