劉國(guó)鋒 吳 陳

（江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 鎮(zhèn)江 212003）

基于支持向量機(jī)和稀疏表示的文本分類研究?

劉國(guó)鋒 吳 陳

（江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 鎮(zhèn)江 212003）

文本分類對(duì)于各個(gè)領(lǐng)域挖掘文本信息非常重要，論文在基于頻率核函數(shù)的文本分類基礎(chǔ)上，充分比較各種分類器的優(yōu)缺點(diǎn)，提出一種利用稀疏表示分類器（SRC）和支持向量機(jī)（SVM）的組合方法進(jìn)行文本分類，以提高文本分類的性能。最后通過(guò)實(shí)驗(yàn)表明，使用二者結(jié)合的方法效果明顯好了很多。

稀疏表示；SVM；頻率核函數(shù)；文本分類

1 引言

互聯(lián)網(wǎng)的迅速發(fā)展，大量的數(shù)字媒體的信息傳播產(chǎn)生大量數(shù)據(jù)，這些數(shù)據(jù)包括大量許多有價(jià)值的信息，怎樣去挖掘數(shù)據(jù)中有價(jià)值的信息。文本分類就是挖掘信息的很重要的解決方法。文本分類就是將一個(gè)文本文檔通過(guò)各種方法判定文檔的屬性類型和文檔主題。傳統(tǒng)的貝葉斯分類［1］，決策樹［2］，k近鄰方法［3］等；這些算法的缺點(diǎn)是不能對(duì)大量文本進(jìn)行分類。為了解決這個(gè)問(wèn)題，研究者們又相繼提出了許多特征選擇文本方法。在本文中，對(duì)幾種的分類進(jìn)行了探討，提出了一種稀疏表示分類器（SRC）的文本分類方法。目前利用稀疏表示進(jìn)行文本分類的研究很少。

支持向量機(jī)（SVM）［4］是目前流行的文本分類方法，支持向量機(jī)傳統(tǒng)的方法是利用線性核函數(shù)或高斯核函數(shù)進(jìn)行分類。然而在本文中，將支持向量機(jī)運(yùn)用直方圖交叉核、卡方分布和Hellinger核函數(shù)［5］在文本分類中。最后充分利用各種分類器的優(yōu)點(diǎn)，本文提出一種新的方法將分類器進(jìn)行相結(jié)合，然后進(jìn)行分類。

2 稀疏表示分類

2.1 稀疏表示

假設(shè)向量X∈Rd字典D={u1，u2，…，uNt}T∈Rd×Nt，

那么X的稀疏表示就是將X表示為u的線性組合X= β1u1，β2u2，…，βNtuNt，這 里 β={β1，β2，…，uβNt}T是和基向量有關(guān)的系數(shù)向量，稀疏表示時(shí)，要確保β只能有很小一部分能為0，稀疏表示通過(guò)β和X可以轉(zhuǎn)化為

這里||β||0是 X的稀疏度，β為非零系數(shù)的個(gè)數(shù)。我們想使得 X盡可能稀疏，就要使得||β||0最小。最近有研究表明，上述問(wèn)題最小可以有

2.2 稀疏表示進(jìn)行分類

在進(jìn)行分類時(shí)，文本分類的訓(xùn)練集作為基向量D ，則有字典矩陣 D=[D1，D2，…，DM]T，M 為種類數(shù)量，在這里，DM=[Xm1，Xm2，…，XmN]T，n=1，2，…，m；有M類訓(xùn)練樣本。對(duì)于樣本是否屬于M類可以求m類訓(xùn)練樣本是否可以線性組合，即系數(shù)β和訓(xùn)練樣本M的相關(guān)系數(shù)不為0，其他系數(shù)均為 0；系數(shù)向量 β ，表示為 β ={0，…，0βm1，βm2，…，βmn，0，…0}T理想情況下，一個(gè)測(cè)試集的最優(yōu) β應(yīng)該使得訓(xùn)練集和測(cè)試集相同時(shí)相關(guān)的系數(shù)不為零并且為稀疏的。

用稀疏表示方法來(lái)進(jìn)行文本分類的主要問(wèn)題是要具有超完備字典D，特征詞向量的維數(shù)大小取決于詞匯量的大小。通常情況下，詞匯量遠(yuǎn)大于訓(xùn)練集數(shù)目，這不滿足超完備字典D的必要條件，為了解決這個(gè)問(wèn)題，有人提出減少詞匯的方法［6］，在本文中采用對(duì)詞匯的特征向量進(jìn)行主成分提取的方法，用主成分分析的方法確保了主成分訓(xùn)練的數(shù)量要少于訓(xùn)練總數(shù)量，本文給出下面三種分類規(guī)則

1）理論上，在完備詞典D下，所有非零項(xiàng)β都使得測(cè)試集和訓(xùn)練集是相同類別。這樣，一個(gè)測(cè)試集就分配具有最大值訓(xùn)練樣本的類標(biāo)簽。

2）實(shí)際上，對(duì)應(yīng)于其他類的測(cè)試樣本，也可以是非零的?；谶@一點(diǎn)，我們計(jì)算了所有的所有類別的稀疏度，并選擇最大的稀疏度的類作為類標(biāo)簽的測(cè)試樣本。讓?duì)腗(β)作為m類值為 β的一個(gè)向量，然后給定的類標(biāo)簽的一個(gè)測(cè)試樣本的賦值：

Label=max(||δm(β)||2)；m=1，2，…，M

3）最小殘差：X作為測(cè)試樣本，Dβ指出了X的范圍。X和它的重構(gòu)時(shí)候出現(xiàn)殘余誤差。既然屬于其他類的 β也可以是非零，||X-Dδm(β)||2給出了M類殘余誤差，最小殘差作為測(cè)試樣本的類標(biāo)簽：

Label=min(||X-Dδm(β)||2)；m=1，2，…，M

3 基于頻率核函數(shù)的SVM分類

3.1 直方圖交叉核

則通過(guò)HIK計(jì)算全部匹配總數(shù)為

3.2 卡方核函數(shù)

卡方統(tǒng)計(jì)方法和HIK方法［7］計(jì)算相似，第q個(gè)bin中的匹配數(shù)如下公式計(jì)算：

卡方計(jì)算總數(shù)為

3.3 Hellinger核函數(shù)

Hellinger核函數(shù)［8］也和HIK方法計(jì)算相似，第q個(gè)bin中的匹配數(shù)如下公式計(jì)算：

計(jì)算匹配總數(shù)為

4 分類器組合

由于采用SRC分類會(huì)把一些文本文檔錯(cuò)誤分類，而用SVM分類時(shí)卻是正確的，一些文本SVM會(huì)分錯(cuò)誤而SRC會(huì)分類正確，為了解決這個(gè)問(wèn)題，本文利用基于投票表決的方法去進(jìn)行分類器的組合。m表示類別數(shù)和k表示對(duì)應(yīng)的分類器。每一個(gè)分類器 λk，K=1，2，…，K ；都會(huì)為測(cè)試樣本提供一個(gè)投票數(shù) vk，vk∈{1，2，3，…，M}，那么測(cè)試樣本類別可表示為

出現(xiàn)次數(shù)最多即A最大，那么測(cè)試樣本就是這一類別，這樣做有時(shí)會(huì)失敗，這需要分類器之間有某種約定，可能在一次投票中，兩個(gè)分類器投票時(shí)對(duì)同一測(cè)試樣本投的不是同一類。

對(duì)于測(cè)試樣本來(lái)講，類標(biāo)簽是后驗(yàn)概率決定的。對(duì)于每一個(gè)測(cè)試樣本，分類器都計(jì)算一個(gè)后驗(yàn)概率。測(cè)試文檔的類別就是所有分類器中最大后驗(yàn)概率的類別。

5 文本分類實(shí)驗(yàn)仿真

在本文中采用實(shí)驗(yàn)仿真來(lái)進(jìn)行文本分類。本文運(yùn)用20 Newsgroup新聞?wù)Z料庫(kù)來(lái)進(jìn)行分類實(shí)驗(yàn)。本語(yǔ)料庫(kù)由18774個(gè)文件，分為20類不同的新聞組，其中的60%（11269個(gè)）的文件用于訓(xùn)練模型，剩余的40%的文件被用于測(cè)試。這里采用詞頻作為主要特征，我們從所有的訓(xùn)練中得到53975個(gè)單詞作為詞匯，在文檔中計(jì)算每個(gè)詞匯發(fā)生的頻率，每一個(gè)文檔都被表示為一個(gè)53975維的詞頻向量。

首先，利用稀疏表示的分類器（SRC）［9］進(jìn)行分類，對(duì)于用的語(yǔ)料庫(kù) Nt=11269小于文檔D的53975，不滿足SRC必要條件，所以用上面提出的主成分分析進(jìn)行分析［10］。采用主成法分析D值從1000到11000并且每增加1000的SRC性能分析。對(duì)于不同詞匯數(shù)量的SRC分類精度如圖1，圖1還比較了SRC與支持向量機(jī)的高斯方法性能比較。由圖1可見，當(dāng)d=6000是分類性能最佳。還可以看到，使用第二種SRC的分類規(guī)則要優(yōu)于第一和第三種的分類規(guī)則。SRC使用第二種規(guī)則的分類精度可達(dá)78.78%。還可以看出使用SRC文本分類比基于高斯方法的SVM分類器性能好。

圖1 對(duì)SRC和SVM性能分析

對(duì)基于頻率核函數(shù)的支持向量機(jī)方法進(jìn)行研究，對(duì)每一個(gè)文檔詞頻向量表示維度都是53975。運(yùn)用svmtorch工具建立分類器［11］?；陬l率核函數(shù)有：直方圖交叉核，卡方分布，Hellinger核函數(shù)，表1對(duì)它們的分類效果進(jìn)行比較，同時(shí)也比較了基于SVM和SRC的高斯核的分類效果。可以看出，SVM用Hellinger核函數(shù)時(shí)的分類略優(yōu)于使用直方圖交叉核和卡方核函數(shù)，SVM基于頻率核函數(shù)要略優(yōu)于基于高斯核分類。這說(shuō)明基于頻率核函數(shù)的SVM分類器效果更好。

由于不同種類分類器對(duì)文檔產(chǎn)生不一樣的分類結(jié)果。而且不同規(guī)則制定和SVM運(yùn)用不同核函數(shù)時(shí)，結(jié)果也不一樣。本文提出將分類器進(jìn)行結(jié)合，可以適當(dāng)解決不同分類造成的差異而且適用于各個(gè)訓(xùn)練集。k是分類器的數(shù)量取決于文本數(shù)量多少。如果K個(gè)分類器對(duì)樣本都分配同樣的標(biāo)簽，那么該文本就屬于這一類別。

表1 分類效果比較

表2給出了在SRC和SVM結(jié)合后的分類效果。給出了三種結(jié)合方法的分類：第一，SRC和三種不同分類規(guī)則結(jié)合，第二，基于高斯核函數(shù)，直方圖交叉核，卡方核函數(shù)，還有Hellinger核函數(shù)的SVM結(jié)合，第三，將三種結(jié)合后SRC和四種結(jié)合后的SVM相結(jié)合。可以看出，當(dāng)SRC的三種不同規(guī)則相結(jié)合時(shí)，分類正確率提高了約5%。，當(dāng)用四種SVM函數(shù)結(jié)合時(shí)有正確率提高了大約7%，當(dāng)結(jié)合所有的SRC和SVM時(shí)，分類正確率提高了約8%。

表2 SRC和SVM結(jié)合后的分類效果

6 結(jié)語(yǔ)

本文從比較了SVM和SRC的分類器性能，可以看出使用組合分類器性能對(duì)于文本分類效果有了很大的提升。但是本文中對(duì)于組合分類器的適用的范圍有所限制，提高分類器的普適性也是以后文本分類進(jìn)一步的研究方向。

［1］Andrew McCallum，Kamal Nigam.A comparison of event?models for naive Bayes text classification［J］.in Proceed?ings of AAAI-98 workshop on learning for text categoriza?tion，1998，752：41-48.

［2］尚朝軒，王品，韓壯志，等.基于類決策樹分類的特征層融合識(shí)別算法［J］.控制與決策，2016（6）：1009-1014.SHANG Zhaoxuan，WANG Pin，HAN Zhuangzhi，et al.Features of decision tree classification fusion recognition algorithm based on［J］.Control and Decision，2016（6）：1009-1014.

［3］郝秀蘭，陶曉鵬，徐和祥，等.KNN文本分類器類偏斜問(wèn)題的一種處理對(duì)策［J］.計(jì)算機(jī)研究與發(fā)展，2009（1）：52-61.HAO Xiulan，TAO Xiaopeng，XU Hexiang，et al.A kind of countermeasure of KNN text classifier class skew problem［J］.Journal of Computer research and development，2009（1）：52-61.

［4］Thorsten Joachims.Text categorization with support vector machines：Learning with many relevant features［C］//in Proceedings of the 10th European Conference on Machine Learning（ECML'98）.ACM，1998：137-148.

［5］黃宏圖，畢篤彥，高山，等.基于局部敏感核稀疏表示的視頻跟蹤［J］.電子與信息學(xué)報(bào)，2016（4）：993-999.HUNG Hongtu，BI Duyan，GAO Shan，et al.Video track?ing based on local sensitive kernel sparse representation［J］.Journal of Electronics and Information Technology，2016（4）：993-999.

［6］Tara N Sainath，Sameer Maskey，Dimitri Kanevsky，Bhu?vana Ramabhadran，David Nahamoo，and Julia Hirsch?berg.Sparse representationsfor text categorization.［J］.in Proceedings of INTERSPEECH，2010，10：2266-2269.

［7］Jan C.van Gemert，Cor J.Veenman，Arnold W.M.Smeul?ders，and JanMark Geusebroek.Visual word ambiguity［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（17）：1271-1283.

［8］Ken Chatf i eld，Victor S Lempitsky，Andrea Vedaldi，and Andrew Zisserman.The devil is in the details：an evalua?tion of recent feature encoding methods［C］//in Proceed?ings of the 22nd British Machine Vision Conference（BM?VC 2011），Kingston，UK，September 2011：76.1-76.12.

［9］陳才扣，喻以明，史俊.一種快速的基于稀疏表示分類器［J］.南京大學(xué)學(xué)報(bào)（自然科學(xué)版），2012（1）：70-76.CHEN Caikou，YU Yiming，SHI Jun.a fast sparse repre?sentation classifier based on［J］.Journal of Nanjing Uni?versity（Natural Science Edition），2012（1）：70-76.

［10］范雪莉，馮海泓，原猛.基于互信息的主成分分析特征選擇算法［J］.控制與決策，2013（6）：915-919.FAN Xue li，F(xiàn)ENG Haihong，YUAN Meng.Principal component analysis based on mutual information feature selection algorithm［J］.Control and Decision，2013（6）：915-919.

［11］R.Collobert and S.Bengio.SVMTorch：Support vector machines for large-scale regression problems［J］.Jour?nal of Machine Learning Research，2001：143-160.

Text Classification Using Combined Sparse Representation Classifiers and Support Vector Machines

LIU GuofengWU Chen
（School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang 212003）

Text classification is very important for various fields of management of a large number of text content，based on text classification based on the frequency of kernel function，the advantages and disadvantages of all kinds of classifiers are com?pared，this paper proposes a sparse classifier（SRC）and support vector machine（SVM）combination method to improve the perfor?mance of text classification.Sparse representation classifier the field dictionary is constructed by means of the vector representation of the document.SVM text classifier linear kernel function and Gauss kernel function are used for the vector representation of the document.

sparse representation，SVM，frequency-based kernels，text classification

Class Number TP391

TP391

10.3969/j.issn.1672-9722.2017.12.032

2017年6月6日，

2017年7月27日

劉國(guó)鋒，男，碩士研究生，研究方向：信息處理理論與技術(shù)應(yīng)用。