基于支持向量的迭代修正質心文本分類算法

王德慶 張 輝

(北京航空航天大學軟件開發環境國家重點實驗室，北京100191)

文本分類(TC，Text Categorization)是一項將未標記的自然語言文本分配到事先定義的主題類別中的任務［1］.文本分類技術已經被廣泛應用到在線新聞分類［1］、軟件 bug分類［2］及垃圾郵件過濾等實際的應用中.由于語料的高維、稀疏等特點，特征選擇也是文本分類的重要組成部分［1］.

基于質心的分類算法 (CC，Centroid-based Classification)由于其簡單性、高效性等特點受到研究人員越來越多的關注，并且Han等人已經證明質心分類算法對于文本分類來說是一個有效的、魯棒的分類模型［3］.質心分類算法的基本觀點是利用屬于同類的訓練實例來構造一個類別的質心向量 (Centroid Vector)，然而傳統CC的分類精度要明顯地低于其他分類器，如支持向量機分類器(SVMs，Support Vector Machines)［4］.導致分類精度低的原因之一是質心向量的構造函數存在問題［5］.因此研究人員針對質心向量的構造或者修正提出了很多改進型的算法，例如Class Feature Centroid 分 類 器［5］、DragPushing［6－7］、基 于 Term Distribution 方 法［8］、Weight Adjustment 方 法［9］.這些改進型方法的性能要優于傳統質心分類算法與k最近鄰等，但與最好的SVMs仍存在一定的差距.

值得注意的是:不論傳統的還是改進的質心分類算法，它們都是將全部的訓練實例作為支持集.然而，這樣極有可能引起過度擬合問題，并且影響到質心分類器的泛化能力，即越多的訓練樣本不一定得到越準確的分類模型［10］.同時，支持向量機的出現及其在文本領域的成功應用［11－12］，激發對傳統算法的重新思考與改進.通過大量實驗發現:選擇“部分”的訓練實例來構造質心向量可能有助于推導出更加準確的分類預測模型.

盡管文本分類中最優子集選擇的理論還沒有建立，但是存在很多可以用來識別邊界實例的成熟技術.例如，SVMs具有完備的理論與數學基礎，并且SVMs擅長區分一個訓練實例是靠近類別邊界還是類別中心.因而，聯合SVMs和迭代修正策略研究并提出基于支持向量的迭代修正質心分類算法 (IACC_SV，Support-Vector-based Iteratively Adjusted Centroid Classifier).

1 質心分類算法的問題分析

在將質心分類算法應用到文本分類之前，每篇文檔通常采用向量空間模型［13］進行表示，權重計算采用 tf-idf(termfrequencyandinverse document frequency)［14］的標準形式 ltc［15］，為了消除文本長度對于項權重的影響，需要對權重進行歸一化處理.

與SVMs相比，質心分類算法更加的簡單與高效.但是，質心分類算法同樣存在著明顯的缺點，即在實際的系統中其分類精度較低.如圖1所示，類別A在特征空間中的分布要比類別B更加廣.如果一個來自類別A的訓練實例向量dA落在該類別的質心向量CA附近(如圖1中dA左箭頭所指實心圓所示)，那么dA很容易被正確分類.但是，如果dA落在類別A與B的邊界MidLine(CA，CB)附近，則dA很容易被誤分(如圖1中右箭頭所指實心圓所示).為了避免上述情況發生，一種可行的方式就是通過訓練集誤差(training-set error)來迭代修正質心向量，即從CA到C'A.基于這種思路出現了很多的研究文獻［5－7，9］，并且改進的算法確實能夠提高傳統的質心分類算法的性能.然而，改進算法的性能仍然劣于最新的分類算法，如SVMs.這意味著僅僅通過迭代修正策略是不夠的，還需采用其他的技術來進一步提高質心分類算法的效能.

圖1 經典質心分類器誤分樣本的可視化示例

仔細觀察圖1，如果類別A的初始質心向量是C'A而不是CA，則將出現如下情況:即圖1中類別A與B的分類邊界由MidLine(CA，CB)變為MidLine(C'A，C'B)，更加靠近最優分類邊界 OptimalMidline(虛線所示).但是，以C'A作為初始質心向量，必須選擇“部分”的樣本而不是全部樣本來構造質心向量，這是本文的第1個研究動機.

問題1 在傳統的質心分類器中，選擇部分樣本構造的質心向量要優于采用全部樣本構造的質心向量嗎?

問題1的答案很可能是肯定的，因為SVMs就是一個很好的例子.SVMs通過從訓練集中選擇出的支持向量構建的分類模型具有較高的模型泛化能力，完成較高的分類預測準確率.因此，需要研究的第2個問題隨之而來.

問題2 如何準確地和自動地選擇部分樣本才能使得構造的質心向量能夠完成比傳統的質心向量更優的分類性能?

對于文本分類來說，文本訓練集往往是高維度、稀疏的向量，想要找到2類之間明確的邊界是很困難的.一種可行的方法是借助于著名的SVMs，因為SVMs中的支持向量就是在映射后的高維空間中處于類別邊界的訓練實例，與需要的邊界實例是相似的.

2IACC_SV算法

IACC_SV算法具有2個重要特點:①IACC_SV算法只利用由SVMs發現的支持向量構造初始的質心向量;②最終的質心向量是通過訓練集誤差迭代修正獲得.IACC_SV算法的具體描述如下:

在IACC_SV算法中，首先利用線性SVMs找到所有的支持向量SV(第1行);然后，利用支持向量構造每類的初始質心向量(第2行);第3～10行用來迭代修正質心向量，即用已有的質心向量來預測支持向量SV中的訓練實例，如果實例被誤分，則按照公式(1)和公式(2)來調整質心向量.

其中，d為類別Ci中的一個實例向量，但是被第l步迭代獲得的質心向量C(l)i誤分到類別Cj中，|Ci|為類別Ci中文本總數.迭代修正直到最大迭代次數m.為避免過度擬合，m默認設定為3.同時，為避免實例讀入順序對于質心的影響，采用隨機無放回的方式讀取樣本d(第4行);最后，第11行返回最終的質心向量用于后續的分類預測過程.

IACC_SV算法中有2點特別值得注意:

1)邊界實例的選擇問題，對于多類問題，采用“1對1”策略來獲得每個類別的邊界實例;

2)質心向量的迭代修正問題，不同于Tan的DragPushing［6－7］，IACC_SV 算法每發現一個誤分樣本都要對質心向量進行修正，這樣做的好處是減少了誤分樣本的數量，從而加快了迭代收斂的速度.

時間復雜度.IACC_SV算法的時間由2部分組成:第1部分為獲得支持向量SV所需的時間;第2部分為迭代修正質心向量所需的時間，與|SV|成線性關系.因此IACC_SV算法訓練時間近似于SVMs的訓練時間.分類預測時間復雜度為O(|T|KW)，其中|T|為測試集T的樣本總數，K為類別總數，W為單詞總數.

3 實驗環境

3.1 實驗語料

實驗語料共 8 個常用的文本數據集［1，5－7，12］，表1列出了所有數據集的基本信息，其中變異系數(CV，Coefficient of Variation)［16］的值越大，說明數據集越不均衡.

表1 8個文本語料集基本信息

Reuters-21578［17］根據“ModApte”劃分得到單標簽語料共9100篇文檔，52個類別.通過停靠詞過濾、詞根還原等文檔預處理，總的單詞數是 27953.通過刪除重復文檔，20Newsgroup［18］得到18828個文檔，訓練集和測試集按2∶1的比例隨機劃分，最終的單詞總數為178456.

從 Tmdata［15］中選取 oh0，wap，fbis，tr11，tr21和tr23共6個語料，其特征維數分別為3 182，8460，2000，6429，7902 及5832.在每次實驗中，訓練集與測試集按4∶1的比例隨機劃分［3］.對于Tmdata中的數據集，采用10次實驗取平均值的方式獲得宏平均F1(macro-F1)與微平均F1(micro-F1)［19］.

3.2 分 類 器

為了比較分類算法的性能，設計實現了一系列的分類器，分別是支持向量機(SVMs)［11－12，20］，加權 k 近鄰(kNN)［21］，經典的質心算法(CC)［3］，批量更新的質心算法(BUCC)［6－7］，迭代修正質心(IACC)算法，基于支持向量的質心分類器 (CC_SV)，基于支持向量的迭代修正質心分類器(IACC_SV).其中SVMs分類器采用開源軟件LIBSVM［22］實現，選擇線性核函數，并使用 5-fold交叉驗證獲取最佳參數C;其余的分類器采用Java編程實現.對于 kNN 分類器，設定 k=10［3］.BUCC的參數“Learnrate”根據文獻［6］中的建議設為0.5.CC_SV與IACC_SV都是采用支持向量作為算法的輸入，除了后者采用迭代修正策略來調整質心向量.

4 實驗結果與分析

4.1 支持向量的作用

為了驗證支持向量在CC的積極作用，首先比較CC與CC_SV在8個數據集上的性能.圖2展示了在macro-F1指標上的比較.很明顯，在所有的8個數據集中，CC_SV在6個數據集上的性能要優于CC，僅有2個略劣于CC分類器 (tr21與tr11).在micro-F1指標上的比較結果如圖3所示，再一次驗證了支持向量在質心分類器中起到的積極作用.相比于傳統的CC算法，通過使用支持向量作為質心分類算法的輸入，CC_SV算法在Reuters-21578語料上的macro-F1與micro-F1分別提高4.3%和3.2%，而在20 Newsgroup語料上的提高分別是2.2%與2.4%.

圖2 采用支持向量與采用全部樣本的macro-F1比較圖

圖3 采用支持向量與采用全部樣本的micro-F1比較圖

進一步觀察到在迭代修正質心分類中，支持向量的作用仍然是正面的.如圖2與圖3所示，IACC_SV在7個數據集上取得優于IACC算法的macro-F1和 micro-F1，除了 oh0.盡管 IACC_SV 提高的程度不如CC_SV和CC之間的明顯.

總之，使用支持向量來構造質心向量確實能夠提高質心分類算法的泛化能力，這也回答了前面提出的問題1，即在文本分類中計算初始質心向量時選擇部分實例要優于選擇全部實例.

4.2 迭代修正策略的作用

圖4與圖5顯示了CC_SV與IACC_SV在macro-F1及micro-F1上的性能比較圖，其中迭代次數m設為3.圖中可見，IACC_SV算法在8個數據集上都要優于CC_SV算法.相比于CC_SV算法，IACC_SV算法在tr23語料庫上將macro-F1提高了8%，在Reuters-21578，fbis及tr21提高了5%;而對于micro-F1，IACC_SV在5個數據集上相比于CC_SV算法提高了3%，分別是Reuters-21578，20 Newsgroup，fbis，tr21 與 tr23.值得注意的是，迭代修正策略也有助于經典的質心分類算法CC性能的提高.從圖2和圖3可知，IACC算法的性能要優于CC算法.這些結果說明，利用訓練集誤差來迭代修正質心向量的方法能夠提高基于質心的分類器的性能和分類預測的準確率.

圖4 CC_SV與IACC_SV在macro-F1上的比較圖

圖5 CC_SV與IACC_SV在micro-F1上的比較圖

4.3 參數確定

IACC_SV算法中，質心向量的最大迭代次數，即參數m，是需要人為設定的.越大的m意味著更多的時間消耗并且有可能導致過度擬合.圖6給出了 IACC_SV算法的準確率在Reuters-21578與fbis上隨參數m遞增的變化情況.可以看出，當m由0增加到1時，IACC_SV算法的準確率提高比較明顯，然而當m＞1，分類器的性能提升就趨向于平穩.例如，在Reuters-21578數據集上，當m=3時，IACC_SV算法取得最高的準確率:93.6%，大約比CC_SV算法提高5.4%;當m＞3時，分類器的準確率的提高趨于平穩甚至降低.相似的結果同樣發生在fbis語料集上.因此，在所有實驗中，將參數m的值設定為3.

圖6 最大迭代次數m對分類算法準確率的影響

4.4 與其他分類算法的比較

本節繼續比較IACC_SV算法與其他分類算法的性能比較，表2列出了5種分類算法的macro-F1值.從表中可以看出，在8個語料集上，IACC_SV，SVMs，BUCC，CC 分別完成 6，2，1 與 1個最優macro-F1，而kNN沒有取得最優結果.最優結果用粗體標出.

表2 5種分類算法的macro-F1比較

首先，8個語料集上，IACC_SV在7個語料集上的macro-F1值都高于SVMs分類器，除了20 Newsgroup，并且在某些語料集上IACC_SV算法的提高幅度很明顯.例如，在不均衡的 Reuters-21578數據集上，IACC_SV算法較SVMs算法提高了6%，同樣在不均衡tr21語料集上，提高幅度高達 8%，這種提高主要是基于 2個方面:①SVMs分類算法是一個全局最優的算法，它可能導致分類器對于稀有類別的嚴重誤分;②macro-F1給每個類別賦予相同的權重，因而可以懲罰分類器在稀有類別上的分類錯誤率.

接下來，比較IACC_SV與BUCC的性能，兩者的不同是BUCC采用全部訓練實例作為算法輸入并且其迭代修正的公式與IACC_SV算法略有不同，其迭代公式參見文獻［6］.從表2中可知，IACC_SV算法在7個數據集上的macro-F1值高于BUCC算法，這也驗證了使用訓練實例的子集，比如支持向量，可以提高CC的分類準確率.

IACC_SV算法要明顯地提高經典的CC算法的性能，特別是在 Reuters-21578，20Newsgroup，fbis，tr21及tr23等5個數據集上.例如，相比于經典的CC算法，IACC_SV算法在 tr23語料庫上提高了10%，在 Reuters-21578語料庫上提高了8.8%，在20Newsgroup，fbis及tr21等3個語料庫上提高了5%.但是，IACC_SV算法在oh0上的性能與CC相同，這是由于迭代次數過多引起的過度擬合問題，如果將IACC_SV算法的迭代次數由3次變為1次，那么IACC_SV算法在上述語料集上的性能就高于CC算法.

最后，從表2最后一行可知，在平均macro-F1上，本文提出的IACC_SV算法在比SVMs，kNN，CC，BUCC 分別提高 2.7%，9%，4.6% 和 1.3%，因此IACC_SV算法優于其他的分類算法.

5種分類器的micro-F1值如表3所示，在所有的8個數據集上，IACC_SV，SVMs及CC分別完成了5，2及1個最好的結果.可以看到IACC_SV算法在 micro-F1指標上同樣優于BUCC，CC及kNN等3種分類算法.然而，IACC_SV與SVMs在micro-F1指標上的比較不同于macro-F1指標，兩者在micro-F1上的差異要小的多.這是因為micro-F1指標給每個測試實例的權重相同，而不考慮類別特性，這就抵消了算法在稀有類別上較差的結果.同時，當SVMs取得最優結果的時候，IACC_SV算法都取得了次優的結果.在平均micro-F1上，IACC_SV 算法在比 SVMs，kNN，CC，BUCC 分別提高 0.1%，7.1%，4.9%及 1.1%.因此在micro-F1上，IACC_SV算法略優于其他的分類算法.

表3 5種分類算法的micro-F1比較

在所有的分類算法中，kNN算法的性能最差，IACC_SV算法的分類準確率與著名的SVMs分類器相接近，并且IACC_SV算法在macro-F1指標上要明顯地優于SVMs分類算法.因此，本文提出的IACC_SV分類算法借助于SVMs選擇出具有代表性的訓練實例，然后利用迭代修正策略來調整質心向量，新的算法在8個文本數據集上的性能要優于 SVMs，BUCC，經典的 CC及 kNN算法.

4.5 在不均衡語料上的性能比較

IACC_SV算法在處理非均衡語料集的文本分類時具有很多的優勢，選擇了不均衡的語料集tr21，對應CV值為1.553.表4列出了5種分類算法在不均衡語料tr21中每個類別(只統計前4大類，第5、第6類由于文檔數太小，不具統計意義而過濾掉)的F1值，其中|Tr|與|Te|分別表示該類訓練集文檔數及測試集文檔數，從表中可以看出該語料集為一個不均衡的數據集.可以看到，IACC_SV在每個類別上的F1值都高于其他的分類算法;SVMs在大類上 (No.1)的準確率接近于IACC_SV算法，但是其在稀有類別上的準確率要明顯地低于IACC_SV算法.整體上，IACC_SV算法比SVMs算法的平均F1高出10%.

表4 不均衡語料集tr21上的F1比較

5 結論

本文提出一種基于支持向量的迭代修正質心文本分類算法.該算法通過使用線性SVMs選出的支持向量作為質心分類算法的輸入，并通過訓練集誤分樣本來迭代修正初始的質心向量.新的算法在8個常用文本語料的分類效果要優于使用最佳參數訓練的線性SVMs，BUCC，kNN及傳統的質心分類算法，驗證了新算法的有效性.特別是在非均衡語料集上的性能要明顯地優于SVMs分類器及k最近鄰分類.

References)

［1］Sebastiani F.Machine learning in automated text categorization［J］.ACM Computing Surveys，2002，34(1):1－47

［2］Wang D，Zhang H，Liu R，et al.Predicting bugs’components via mining bug reports ［J］.JournalofSoftware，2012，7(5):1149－1154

［3］Han E H，Karypis G.Centroid-based document classification:analysis ＆ experimental results［C］//Proceedings of PKDD’00.London:Springer-Verlag，2000:424－431

［4］Tam V，Santoso A，Setiono R.A comparative study of centroidbased，neighborhood-based and statistical approaches for effective document categorization［C］//Proceedings of 16th ICPR.Washington:IEEE Computer Society，2002:235－238

［5］Guan H，Zhou J，Guo M.A class-feature-centroid classifier for text categorization［C］//Proceedings of WWW.New York:ACM，2009:201－210

［6］Tan S.An improved centroid classifier for text categorization［J］.Expert Systems with Applications，2008，35(1/2):1279－1285

［7］Tan S，Wang Y，Wu G.Adapting centroid classifier for document categorization ［J］. Expert Systems with Applications，2011，38(8):10264－10273

［8］Lertnattee V，Theeramunkong T.Effect of term distributions on centroid-based text categorization［J］.Information Sciences，2004，158:89－115

［9］Shankar S，Karypis G.Weight adjustment schemes for a centroid based classifier［R］.TR 00－035，2000

［10］Foody G M.Issues in training set selection and refinement for classification by a feedforward neuralnetwork［C］//Proceedings of IGARSS.Seattle:IEEE，1998:409－411

［11］Cortes C，Vapnik V.Support-vector networks［J］.Machine Learning，1995，20:273－297

［12］Joachims T.Text categorization with support vector machines［R］.TR-23，University of Dortmund，1997

［13］Salton G，Buckley C.Term-weighting approaches in automatic text retrieval［J］.Information Processing ＆ Management，1988，24(5):513－523

［14］Jones K S.A statistical interpretation of term specificity and its application in retrieval［J］.J Documentation，1972，28(1):11－21

［15］HanE H.Tmdata［DB/OL］.Minnesota:Universityof Minnesota，2000［2011-07-02］.http://www.cs.umn.edu/～han/data/tmdata.tar.gz

［16］Xiong H，Wu J，Chen J.K-means clustering versus validation measures:a data-distribution perspective［J］.IEEE Transactions on Systems，Man，and Cybernetics Part B，2009，39(2):318－331

［17］Lewis D.Reuters-21578［DB/OL］.Dublin:Trinty College，2007［2011-07-01］.http://ronaldo.cs.tcd.ie/esslli07/sw/step01.tgz

［18］Lang Ken. 20Newsgroup ［ DB/OL ］. Massachusetts:Massachusetts Institute of Technology，2007［2011-07-01］.http://people.csail.mit.edu/jrennie/20Newsgroups/

［19］Lewis D D.Evaluating and optimizing autonomous text classification systems［C］//Proceedings of 18thSIGIR.New York:ACM，1995:246－254

［20］Yu H，Hsieh C J，Chang K W，et al.Large linear classification when data cannot fit in memory［C］//Proceedings of KDD'10.New York:ACM，2010:833－842

［21］Yang Y，Liu X.A re-examination of text categorization methods［C］//ProceedingsofSIGIR ’99.New York:ACM，1999:42－49

［22］Chang C C，Lin C J.Libsvm:a library for support vector machines［CP/OL］.Taiwan:Department of Computer Science and Information Engineering，National Taiwan University，2001［2011-07-01］.http://www.csie.ntu.edu.tw/～ cjlin/libsvm