用AdaBooster算法實現(xiàn)中文文本分類問題

火善棟

（重慶三峽學院，重慶 404000）

用AdaBooster算法實現(xiàn)中文文本分類問題

火善棟

（重慶三峽學院，重慶 404000）

文本分類是文本挖掘的一個重要內容，在很多方面都有著廣泛的應用。為了實現(xiàn)中文文本分類問題，先采用分詞技術和特征詞統(tǒng)計相關方法得到每類訓練文檔的特征向量中心（質心），通過比較測試文檔到質心的距離來實現(xiàn)中文文檔分類，然后采用AdaBooster算法通過不斷調整每類訓練文檔的質心構建一個強分類器。實驗表明：采用AdaBooster算法進行中文文本分類時，算法簡單、分類速度快、正確率高、占用內存小而且可以根據(jù)訓練文檔的不同實時地調整迭代次數(shù)。

中文文本分類；AdaBooster算法；中文分詞；文檔特征向量

0 引言

文本分類是指按照預先定義的主題類別，為文檔集合中的每個文檔確定一個類別，文本分類是文本挖掘的一個重要內容。目前，在國內已經對中文文本分類進行了廣泛的研究，并在信息檢索、Web文檔自動分類、數(shù)字圖書館、自動文摘、分類新聞組、文本過濾、單詞語義辨析以及文檔的組織和管理等多個領域得到了初步的應用。

AdaBooster[1]算法是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器（弱分類器），然后把這些弱分類器集合起來，構成一個更強的最終分類器（強分類器）。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。將修改過權值的新數(shù)據(jù)集送給下層分類器進行訓練，最后將每次訓練得到的分類器最后融合起來，作為最后的決策分類器。

為了實現(xiàn)中文文本分類問題，本文先采用分詞技術和特征詞統(tǒng)計等相關方法得到每個訓練文檔的特征向量和每類訓練文檔的特征向量中心（質心），通過比較訓練文檔到到各個類別質心的距離來實現(xiàn)中文文檔分類的目的，為了表達的簡潔性，本文將這種方法稱之為“質心匹配算法”，然后采用AdaBooster算法通過不斷調整每篇訓練文檔的權重進而調整每類訓練文檔的質心來達到對中文文檔進行分類的目的，實驗表明：該分類算法具有分類速度快、正確率高和占用內存小的特點。

1 AdaBooster算法實現(xiàn)中文分類流程框圖

用AdaBooster算法實現(xiàn)中文文本分類，其過程如圖1所示：該方法主要包括學習和分類兩大部分，涉及到的一些主要技術包括中文詞典構建和查找算法、中文文檔分詞算法、TFIDF特征向量權值計算算法和AdaBooster算法。

2 “質心匹配算法”的實現(xiàn)過程

（1）分詞：采用最大逆向分詞算法對訓練文檔集中的每一個文檔進行分詞，并根據(jù)停用詞表去掉一些常用的停用詞，然后通過分詞得到所有訓練文檔集的特征詞表Dt（每個特征詞條都不相同，t為特征詞的序號）和每個文檔的特征詞空間Dk（每個特征詞可以有多

個，k為文檔編號）；

（2）計算訓練文檔的特征向量：根據(jù)文檔中每個特征詞的詞項頻率tf[3]（特征詞在相應文檔中出現(xiàn)的次數(shù)）和文檔頻率df[3]（所有訓練集文檔中包含該特征詞的文檔數(shù)，通過公式為wtf×itf計算出每個訓練文檔的特征向量，其中itf為逆文檔頻率，由公式itf=log（N/df）計算得出；wft為修正后的詞項頻率；采用公式（1）計算得到：

（3）計算訓練文檔的類向量中心：通過訓練文檔的特征向量計算出每類文檔的特征向量中心最后通過分配給每個訓練文檔的權重Di（d1，d2，d3，…，dn）得到不同的特征向量中心Cmi，m為訓練文檔的類別編號，vn為特征詞的權值，n為特征詞的序號。

圖1 AdaBooster算法實現(xiàn)中文文本分類流程框圖

（4）分類：通過比較測試文檔的特征向量和不同類文檔特征文檔向量質心的相似度（余弦夾角）對文檔進行分類。

3 AdaBooster算法實現(xiàn)中文文本分類，其過程如下

（1）得到訓練集文檔的特征向量Vk（vk1，vk1，vk3…vkn，ykm）。該特征向量是一個二維空間向量，k為文檔編號、n為訓練文檔特征詞的個數(shù)，vki為特征詞對應的權值，ym為文檔類別編號，m為類別個數(shù)；

（3）統(tǒng)計訓練文檔的分類錯誤率error：求classEsti中最小的cim所對應的文檔分類編號k，如果k=yim則分類正確，否則則分類錯誤；錯誤率計算公式為：ε=Σ Dj，j為分類錯誤文檔編號；

（7）更新累計類別估計值：對每一篇訓練文檔的分類結果進行累計求和：aggrClassEsti+=α×classEsti，aggr-ClassEsti為一個二維向量，其數(shù)據(jù)結構與classEsti相同；

（8）統(tǒng)計累計分類錯誤率：通過aggrClassEsti判斷每篇訓練文檔的訓練結果（判斷過程與classEsti相同）從而統(tǒng)計出所有訓練文檔的錯誤率aggrErrorRate，如果aggrErrorRate=0或者迭代次數(shù)t小于訓練給定的訓練次數(shù)則返回到步驟（3）繼續(xù)循環(huán)執(zhí)行，否則退出循環(huán)，訓練結束。

4 實驗和測試

本實驗共收集了政治（246篇）、經濟（238篇）、醫(yī)藥（204篇）、體育（）217篇、藝術（248篇）、教育（220篇）、交通（214篇）、軍事（249篇）和環(huán)境（201篇）9類共2038篇文檔作為訓練文檔進行了訓練。由于實驗沒有對特征詞做降維處理，所以其訓練文檔的的維數(shù)比

較大為69664，在形成弱分類器時時間比較長，需要占用較大的內存空間。本文測試采用Java進行了實現(xiàn)，實驗電腦的基本配置為AMD 4核，內存大小為4G；Java虛擬機內存大小為1.6G。為了便于測試和實驗參數(shù)的調整，本實驗分為三個階段來完成。

（1）訓練弱分類器：采用“質心匹配算法”對訓練文檔進行訓練形成弱分類器，保存訓練結果數(shù)據(jù)（學習成果），其數(shù)據(jù)包括每一個訓練文檔的文檔特征向量、所有訓練文檔的特征詞表、每個特征詞的反文檔頻率、所有訓練文檔的總篇數(shù)和每類訓練文檔的中心向量。該階段實驗共運行了大約13分鐘，數(shù)據(jù)文件的大小為544M。

（2）訓練強分類器：載人1階段的實驗數(shù)據(jù)采用AdaBooster算法，通過訓練文檔的分類錯誤率error、alpha值不斷地調整每一個訓練樣本的權重Di（i為文檔編號），通過Di調用“質心匹配算法”，并保存每一個弱分類器的實驗數(shù)據(jù)（每類訓練文檔的質心和對應的alpha值），當?shù)螖?shù)滿足一個給定的值或者每個弱分類器的分類累加錯誤率為0時結束第2階段的訓練。本實驗的訓練結果如表1所示，從表1中可以看出，隨著迭代次數(shù)的增加，累計分類錯誤文檔的篇數(shù)先減少然后又稍微變大，最后趨向穩(wěn)定，其總的情況是：（93，12，10，7，6，4，5，6，6，6，……），之所以會出現(xiàn)這種情況，相關資料稱之為過擬合現(xiàn)象[1]，為了保證本實驗的正確率，本實驗將迭代次數(shù)設置為6，也就是說當訓練文檔累計分類錯誤文檔篇數(shù)為4時結束2階段的訓練，保存訓練結果。本階段需要保存的訓練結果數(shù)據(jù)（學習成果）為：每個弱分類器的參數(shù)（每類訓練文檔的向量中心和對應的alpha值）、所有訓練文檔的特征詞表、每個特征詞的反文檔頻率IDF和總的訓練文檔的篇數(shù)。本階段運行時間大約為1分鐘，實驗結果數(shù)據(jù)文件大小為：15.3M。說明：本階段的數(shù)據(jù)為分類器的最終學習成果。

對分類算法進行測試：載人2階段的各個弱分類器（每個弱分類器對應于不同的文檔類型質心）和對應的alpha值對測試文檔的測試結果進行加權求和從而得到最后的分類結果，其實驗結果如表2所示：

表1 AdaBooster算法訓練結果表

表2 “質心匹配算法”和AdaBooster算法測試結果對照表

實驗說明：本實驗的訓練文檔和測試文檔均從網上下載，算法的實驗效果和測試文檔的數(shù)目無關，之所以列出兩組實驗數(shù)據(jù)是由于開始使用的測試數(shù)據(jù)比較少，感覺AdaBooster算法沒有太大的優(yōu)勢，后來才加大了測試文檔的數(shù)目。

5 結語

通過本實驗可以看出：由“質心匹配算法”所構建的弱分類器其正確率還是比較高的，但AdaBooster算法分類效果要明顯高于單一的“質心匹配算法”。由“質心匹配算法”所構建的AdaBooster中文文本強分類器，其算法簡單、分類速度快、準確率高占用內存小而且可以根據(jù)訓練文檔的不同實時地調整AdaBooster算法的迭代次數(shù)。為了進一步的提高AdaBooster算法在中文文本中的性能，下一步的主要工作是：（1）優(yōu)化分詞算法；（2）優(yōu)化特征向量的提取和降低特征向量的長度；（3）改善AdaBooster算法在“非均衡”[1]訓練文本中的分類效果。

[1]（美)Peter Harrington.機器學習實戰(zhàn).李悅，李鵬，曲亞東，王斌譯.人民郵電出版社，2013，6（第一版）.

[2](美)George E Luger.人工智能復雜問題求解的結果和策略.郭茂祖等譯.機械工業(yè)出版社，2010（第一版）.

[3]（美)Christopher D.Manning Prabhakar Raghavan,（德）Hinrich Schütze.信息檢索導論.王斌譯.人民郵電出版社，2010，10（第一版）.

[4]高一凡.《數(shù)據(jù)結構》算法實現(xiàn)及其解析.西安電子科技大學出版社，2002，10（第一版）.

[5]程杰.大話數(shù)據(jù)結構.清華大學出版社，2011，6（第一版）.

[6]葉核亞.Java程序設計實用教程.電子工業(yè)出版社，2014，1（第二版）.

Using AdaBooster Algorithm to Achieve Chinese Text Categorization

HUO Shan-dong

（Chongqing Three Gorges University,Wanzhou 404000）

Text classification is an important element of text mining,and in many ways have a wide range of applications.In order to achieve the Chinese text classification problem,uses word segmentation and feature words statistical correlations to obtain eigenvector centrality of each type of training documentation(centroid),to achieve the Chinese document classification by comparing the test documentation from the centroid,then uses AdaBooster algorithm constantly to adjust the centroid of each type of training documents to build a strong classifier.Experiments show that:AdaBooster Chinese text classification algorithm,the algorithm is simple,fast classification correct rate,small memory and can be adjusted in real time depending on the number of iterations of training documents.

Chinese Text Classification;AdaBooster Algorithm;Chinese Word Segmentation;Document Feature Vector

1007-1423（2016）30-0003-04

10.3969/j.issn.1007-1423.2016.30.001

火善棟（1974-），男，湖北孝感人，碩士，講師，研究方向為智能信息系統(tǒng)

2016-08-09

2016-10-18