火善棟

（重慶三峽學(xué)院，重慶 404000）

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

火善棟

（重慶三峽學(xué)院，重慶 404000）

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

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

0 引言

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

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

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

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

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

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

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

個，k為文檔編號）；

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

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

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

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

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

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

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

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

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

4 實驗和測試

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

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

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

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

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

表1 AdaBooster算法訓(xùn)練結(jié)果表

表2 “質(zhì)心匹配算法”和AdaBooster算法測試結(jié)果對照表

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

5 結(jié)語

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

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

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

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

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

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

[6]葉核亞.Java程序設(shè)計實用教程.電子工業(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