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

火善棟

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

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

火善棟

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

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

中文文本分類(lèi)；AdaBooster算法；中文分詞；文檔特征向量

0 引言

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

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

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

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

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

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

（1）分詞：采用最大逆向分詞算法對(duì)訓(xùn)練文檔集中的每一個(gè)文檔進(jìn)行分詞，并根據(jù)停用詞表去掉一些常用的停用詞，然后通過(guò)分詞得到所有訓(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ù)，通過(guò)公式為wtf×itf計(jì)算出每個(gè)訓(xùn)練文檔的特征向量，其中itf為逆文檔頻率，由公式itf=log（N/df）計(jì)算得出；wft為修正后的詞項(xiàng)頻率；采用公式（1）計(jì)算得到：

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

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

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

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

（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為文檔類(lèi)別編號(hào)，m為類(lèi)別個(gè)數(shù)；

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

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

（8）統(tǒng)計(jì)累計(jì)分類(lèi)錯(cuò)誤率：通過(guò)aggrClassEsti判斷每篇訓(xùn)練文檔的訓(xùn)練結(jié)果（判斷過(guò)程與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類(lèi)共2038篇文檔作為訓(xùn)練文檔進(jìn)行了訓(xùn)練。由于實(shí)驗(yàn)沒(méi)有對(duì)特征詞做降維處理，所以其訓(xùn)練文檔的的維數(shù)比

較大為69664，在形成弱分類(lèi)器時(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è)階段來(lái)完成。

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

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

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

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

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

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

5 結(jié)語(yǔ)

通過(guò)本實(shí)驗(yàn)可以看出：由“質(zhì)心匹配算法”所構(gòu)建的弱分類(lèi)器其正確率還是比較高的，但AdaBooster算法分類(lèi)效果要明顯高于單一的“質(zhì)心匹配算法”。由“質(zhì)心匹配算法”所構(gòu)建的AdaBooster中文文本強(qiáng)分類(lèi)器，其算法簡(jiǎn)單、分類(lèi)速度快、準(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)練文本中的分類(lèi)效果。

[1]（美)Peter Harrington.機(jī)器學(xué)習(xí)實(shí)戰(zhàn).李?lèi)偅铢i，曲亞?wèn)|，王斌譯.人民郵電出版社，2013，6（第一版）.

[2](美)George E Luger.人工智能復(fù)雜問(wèn)題求解的結(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