基于經(jīng)驗(yàn)風(fēng)險(xiǎn)的中心文本分類(lèi)算法

周曉堂,歐陽(yáng)繼紅,李熙銘

(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長(zhǎng)春 130012)

互聯(lián)網(wǎng)的快速發(fā)展為信息共享提供了一個(gè)通用平臺(tái).文本是信息的主要載體,研究文本自動(dòng)分類(lèi)可系統(tǒng)地規(guī)范文本,提高信息檢索速度,因此,對(duì)文本分類(lèi)算法的研究具有重要意義[1].近年來(lái),人們已提出了許多文本分類(lèi)算法,包括中心分類(lèi)法[2]、樸素Bayes算法[3]、支持向量機(jī)[4]、人工神經(jīng)網(wǎng)絡(luò)[5]、K近鄰算法[4]和決策樹(shù)[6]等.其中,中心分類(lèi)法具有高效、健壯和計(jì)算簡(jiǎn)便并易于編程等優(yōu)點(diǎn),得到廣泛應(yīng)用.但中心分類(lèi)法的訓(xùn)練過(guò)程忽略了文本權(quán)值對(duì)類(lèi)別中心的影響.針對(duì)中心分類(lèi)法的缺陷,目前已提出了許多改進(jìn).文獻(xiàn)[7]提出的權(quán)重調(diào)整方法中,使用特征的“純度”表示每個(gè)特征的區(qū)別能力,然后根據(jù)驗(yàn)證集上的錯(cuò)誤率使用“純度”迭代調(diào)整文本向量中的所有特征權(quán)重,該方法認(rèn)為平均分配在各類(lèi)中的特征具有較低的“純度”和區(qū)別能力,而非平均分布在各類(lèi)中的特征具有較高的“純度”和區(qū)別能力.文獻(xiàn)[8]提出的基于特征分布方法中,考慮了特征在類(lèi)中的分布,并使用特征分布加強(qiáng)特征權(quán)重函數(shù).文獻(xiàn)[9]提出的類(lèi)-特征-中心方法中,應(yīng)用類(lèi)間和類(lèi)內(nèi)特征索引構(gòu)建相對(duì)于傳統(tǒng)方法具有更好初始值的類(lèi)中心向量.文獻(xiàn)[10]提出的拖拽方法利用訓(xùn)練集上的分類(lèi)錯(cuò)誤信息通過(guò)拖拽方法改善類(lèi)中心向量,并提出了按組更新的中心分類(lèi)法,該方法對(duì)類(lèi)中心進(jìn)行拖拽,使其靠近屬于該類(lèi)且被錯(cuò)誤分到其他類(lèi)的文本,同時(shí)遠(yuǎn)離不屬于該類(lèi)且被錯(cuò)誤分到該類(lèi)的文本.在引入訓(xùn)練集分類(lèi)錯(cuò)誤信息的基礎(chǔ)上,為提高模型分類(lèi)的泛化能力,譚松波等[11]又引入了訓(xùn)練集邊界信息,定義了數(shù)據(jù)的假設(shè)邊界,并依此對(duì)類(lèi)中心進(jìn)行拖拽,使類(lèi)中心靠近屬于該類(lèi)且處在假設(shè)邊界附近的文本,該方法利用訓(xùn)練集上的分類(lèi)錯(cuò)誤信息和訓(xùn)練集的邊界信息定義了目標(biāo)函數(shù),通過(guò)利用梯度下降法求得目標(biāo)函數(shù)的最小值指導(dǎo)類(lèi)中心的拖拽.但該方法給出的目標(biāo)函數(shù)并不處處光滑、可導(dǎo),在應(yīng)用梯度下降方法時(shí),可能會(huì)產(chǎn)生異常結(jié)果.

本文在傳統(tǒng)中心分類(lèi)法的基礎(chǔ)上,基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則構(gòu)建目標(biāo)函數(shù),通過(guò)引入Sigmoid函數(shù)平滑得到一個(gè)處處光滑、可導(dǎo)的目標(biāo)函數(shù),解決了文獻(xiàn)[11]中目標(biāo)函數(shù)的可導(dǎo)性問(wèn)題.使用最優(yōu)化技術(shù)優(yōu)化目標(biāo)函數(shù)調(diào)整類(lèi)中心向量,求得了代表性更強(qiáng)的類(lèi)中心向量,進(jìn)而提高了分類(lèi)性能.實(shí)驗(yàn)結(jié)果表明,本文算法具有與支持向量機(jī)相近的分類(lèi)性能,并適用于偏斜數(shù)據(jù)集,魯棒性較強(qiáng).

1 中心分類(lèi)法

中心分類(lèi)法的基本思想：根據(jù)訓(xùn)練文本集合的信息為每個(gè)類(lèi)別構(gòu)建中心特征向量作為該類(lèi)的代表向量,待分類(lèi)文本則根據(jù)與各個(gè)中心特征向量的相似度決定所屬類(lèi)別.

1) 預(yù)處理階段.使用向量空間模型處理非結(jié)構(gòu)化的文本數(shù)據(jù),計(jì)算每個(gè)文本對(duì)應(yīng)的數(shù)值特征向量d=(w(t1,d),w(t2,d),…,w(tNT,d)),各項(xiàng)特征權(quán)重w(ti,d)的計(jì)算公式為

(1)

該數(shù)值特征向量由特征空間中的特征權(quán)重組成,包含了文本內(nèi)部潛在的統(tǒng)計(jì)信息.其中:d表示來(lái)自訓(xùn)練集的一篇文本;tf(ti,d)表示在文本d中特征ti的出現(xiàn)次數(shù);Nti表示訓(xùn)練集D中包含特征ti的文本總數(shù);分母為規(guī)范化因子,使每個(gè)數(shù)值特征向量都具有單位長(zhǎng)度,消除不同文本的不同長(zhǎng)度對(duì)特征權(quán)重的影響.

(2)

3) 測(cè)試階段.中心分類(lèi)法使用余弦函數(shù)度量測(cè)試文本d和類(lèi)別中心Ci的相似度.相似度計(jì)算公式為

(3)

其中,“·”表示兩個(gè)向量的點(diǎn)積.

經(jīng)過(guò)相似度對(duì)比,中心分類(lèi)法認(rèn)為測(cè)試文本d屬于與文本d具有最大相似度類(lèi)別中心所代表的類(lèi)別.引入變量Cjudge(d,C),判別公式為

(4)

2 本文算法

傳統(tǒng)中心分類(lèi)法使用算術(shù)平均值計(jì)算類(lèi)別的中心向量.該策略給每篇文本相同的權(quán)重,未考慮不同文本的表達(dá)能力是不同的,影響了中心向量的表達(dá)能力,從而影響了中心分類(lèi)法的分類(lèi)性能.針對(duì)此問(wèn)題,本文基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的原則構(gòu)建目標(biāo)函數(shù),通過(guò)梯度下降算法計(jì)算目標(biāo)函數(shù)極值點(diǎn)求得類(lèi)別中心向量.同時(shí),為了解決文獻(xiàn)[11]中目標(biāo)函數(shù)不是處處可導(dǎo)的問(wèn)題,本文引入Sigmoid函數(shù)平滑目標(biāo)函數(shù),避免其不可導(dǎo)產(chǎn)生的不穩(wěn)定因素.

(5)

其中: 函數(shù)Cneighbor(d,C)表示集合C中與文本d的相似度最高且屬于不同類(lèi)別的類(lèi)中心向量;函數(shù)Ctrue(d,C)表示集合C中與文本d同類(lèi)的類(lèi)中心向量;函數(shù)Sgn(x)是指示函數(shù),定義如下：

(6)

由式(6)可見(jiàn),當(dāng)函數(shù)Sgn(cos(d,Cneighbor(d,C))-cos(d,Ctrue(d,C)))=0時(shí),表明文本d被正確分類(lèi)；否則,表明文本d被錯(cuò)誤分類(lèi).因此,目標(biāo)函數(shù)RSgn(D,C)有效表達(dá)了中心分類(lèi)法在訓(xùn)練集D上的經(jīng)驗(yàn)誤差.

通過(guò)最小化函數(shù)RSgn(D,C),可得到更具代表性的類(lèi)中心,提高中心分類(lèi)法的分類(lèi)性能.但由于指示函數(shù)Sgn(x)的階梯函數(shù)性質(zhì),使得目標(biāo)函數(shù)RSgn(D,C)不是處處光滑且不可導(dǎo),不能直接使用解析法求解極值.因此,本文使用平滑單調(diào)函數(shù)Sigmoid(x)近似模擬指示函數(shù)Sgn(x),以得到處處光滑、可導(dǎo)的目標(biāo)函數(shù)RSig(D,C),定義如下：

(7)

其中

(8)

λ為控制Sigmoid(x)函數(shù)形狀的參數(shù).

最后,得到類(lèi)中心的梯度更新公式為

(9)

(10)

其中

(11)

在經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則下,使用梯度下降法獲得最優(yōu)類(lèi)中心的算法偽代碼如下：

輸入：訓(xùn)練集D,最大迭代次數(shù)Max_iter.

輸出：最優(yōu)類(lèi)中心向量集CMax_iter.

按式(2)初始化起始類(lèi)中心向量集C0

Fort=1∶Max_iter//迭代開(kāi)始；

Fori=1∶ND//迭代的第一部分

計(jì)算文本di和當(dāng)前所有類(lèi)中心Ct-1的相似度

計(jì)算文本di的Cneigbor(di,Ct-1)值

End for

Fori=1∶K//迭代的第二部分

Forj=1∶NT

按式(9)更新類(lèi)中心

End for

End for

End for//迭代結(jié)束

ReturnCMax_iter

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)數(shù)據(jù)集選取來(lái)自TREC,OHSUMED和Reuters-21578這3個(gè)基準(zhǔn)文本數(shù)據(jù)集中的4個(gè)子文本數(shù)據(jù)集la12,new3,ohscal和re1.其中: la12和new3來(lái)自TREC;ohscal來(lái)自O(shè)HSUMED;re1來(lái)自Reuters-21578.4個(gè)子文本數(shù)據(jù)集la12,new3,ohscal和re1的特征列于表1.由數(shù)據(jù)集規(guī)模大小可見(jiàn),la12和ohscal是大數(shù)據(jù)集,new3和re1是小數(shù)據(jù)集；由數(shù)據(jù)集平衡程度可見(jiàn),la12,ohscal,new3是平衡數(shù)據(jù)集,re1是不平衡數(shù)據(jù)集.

表1 文本數(shù)據(jù)集Table 1 Text data

實(shí)驗(yàn)選用宏平均F1值和微平均F1值[12]度量分類(lèi)性能.宏平均F1值為整個(gè)測(cè)試集上的F1值,微平均F1值為測(cè)試集各類(lèi)別上F1值的均值.F1值為查準(zhǔn)率和查全率的調(diào)和平均值,定義如下：

F1=2×[(查準(zhǔn)率×查全率)/(查準(zhǔn)率+查全率)].

(12)

3.2 實(shí)驗(yàn)結(jié)果

為了獲得模型預(yù)測(cè)能力的準(zhǔn)確估計(jì),減弱訓(xùn)練集、測(cè)試集分割時(shí)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生的影響,實(shí)驗(yàn)過(guò)程采用三折交叉驗(yàn)證方式[13].實(shí)驗(yàn)選取的對(duì)比算法包括傳統(tǒng)中心分類(lèi)法(BCC)及支持向量機(jī)的兩個(gè)變體SVMTorch和LibSVM.實(shí)驗(yàn)結(jié)果如圖1和圖2所示.

圖1 不同方法的宏平均F1值對(duì)比Fig.1 Comparison of macro-F1 mean values by different methods

圖2 不同方法的微平均F1值對(duì)比Fig.2 Comparison of micro-F1 mean values by different methods

由圖1和圖2可見(jiàn),本文算法的分類(lèi)性能明顯高于傳統(tǒng)中心分類(lèi)法.此外,本文算法在彌補(bǔ)了傳統(tǒng)中心分類(lèi)法在平衡數(shù)據(jù)集上分類(lèi)性能較差的缺點(diǎn)、使其分類(lèi)性能逼近支持向量機(jī)方法的同時(shí),進(jìn)一步增強(qiáng)了傳統(tǒng)中心分類(lèi)法在偏斜數(shù)據(jù)上分類(lèi)性能較強(qiáng)的優(yōu)勢(shì),使其分類(lèi)性能明顯優(yōu)于支持向量機(jī)方法.

綜上所述,本文提出的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則下的中心分類(lèi)法相比于傳統(tǒng)中心分類(lèi)法,能得到代表性更強(qiáng)的類(lèi)中心,其分類(lèi)性能逼近支持向量機(jī)方法,且在偏斜數(shù)據(jù)集上優(yōu)于支持向量機(jī)方法.

[1] XUE Gui-rong,XING Di-kan,YANG Qiang,et al.Deep Classification in Large-Scale Text Hierarchies [C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York: ACM,2008: 619-626.

[2] Han E H,George K.Centroid-Based Document Classification: Analysis and Experimental Results [C]//Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery.London: Springer-Verlag,2000: 424-431.

[3] Ashraf M K,Eibe F,Bernhard P,et al.Multinomial Naive Bayes for Text Categorization Revisited [C]//Proceedings of the 17th Australian Joint Conference on Artificial Intelligence.Berlin: Springer Verlag,2004: 488-499.

[4] Naohiro I,Tsuyoshi M,Takahiro Y,et al.Text Classification by Combining Grouping,LSA and kNN [C]//Proceedings of the 5th IEEE/ACIS International Conference on Computer and Information Science.Washington DC: IEEE Computer Society,2006: 148-154.

[5] Rowena C,Chunghsing Y,Katea S.A Neural Network Model for Hierarchical Multilingual Text Categorization [C]//Proceedings of the Second International Symposium on Neural Networks.Berlin: Springer Verlag,2005: 238-245.

[6] GAO Sheng,WU Wen,LEE Chin-hui,et al.A Maximal Figure-of-Merit (MFoM)-Learning Approach to Robust Classifier Design for Text Categorization [J].ACM Transactions on Information Systems,2006,24(2): 190-218.

[7] Shrikanth S,George K.A Feature Weight Adjustment Algorithm for Document Categorization [C]//Proceedings of the KDD-2000 Workshop on Text Mining.Boston: Citeseer,2000: 12-19.

[8] Verayuth L,Thanaruk T.Effect of Term Distributions on Centroid-Based Text Categorization [J].Information Sciences,2004,158: 89-115.

[9] GUAN Hu,ZHOU Jing-yu,GUO Min-yi.A Class-Feature-Centroid Classifier for Text Categorization [C]//Proceedings of the 18th International Conference on World Wide Web.New York: ACM,2009: 201-210.

[10] TAN Song-bo.Large Margin DragPushing Strategy for Centroid Text Categorization [J].Expert Systems with Applications,2007,33(1): 215-220.

[11] TAN Song-bo,CHENG Xue-qi.Using Hypothesis Margin to Boost Centroid Text Classifier [C]//Proceedings of the 2007 ACM Symposium on Applied Computing.New York: ACM,2007: 398-403.

[12] Michael B,Fredric G.The Relationship between Recall and Precision [J].Journal of the American Society for Information Science,1994,45(1): 12-19.

[13] Christopherd M,Prabhakar R,Schütze H.Introduction to Information Retrieval [M].New York: Cambridge University Press,2008: 151-176.