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

火善棟

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

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

火善棟

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

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

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

0 引言

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

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

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

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

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

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

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

個(gè)，k為文檔編號(hào)）；

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)和測(cè)試

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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

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

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

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

[6]葉核亞.Java程序設(shè)計(jì)實(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-），男，湖北孝感人，碩士，講師，研究方向?yàn)橹悄苄畔⑾到y(tǒng)

2016-08-09

2016-10-18