劉國鋒 吳 陳

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

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

劉國鋒 吳 陳

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

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

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

1 引言

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

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

2 稀疏表示分類

2.1 稀疏表示

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

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

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

2.2 稀疏表示進行分類

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

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

1）理論上，在完備詞典D下，所有非零項β都使得測試集和訓練集是相同類別。這樣，一個測試集就分配具有最大值訓練樣本的類標簽。

2）實際上，對應于其他類的測試樣本，也可以是非零的?；谶@一點，我們計算了所有的所有類別的稀疏度，并選擇最大的稀疏度的類作為類標簽的測試樣本。讓δM(β)作為m類值為 β的一個向量，然后給定的類標簽的一個測試樣本的賦值：

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

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

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

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

3.1 直方圖交叉核

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

3.2 卡方核函數(shù)

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

卡方計算總數(shù)為

3.3 Hellinger核函數(shù)

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

計算匹配總數(shù)為

4 分類器組合

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

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

對于測試樣本來講，類標簽是后驗概率決定的。對于每一個測試樣本，分類器都計算一個后驗概率。測試文檔的類別就是所有分類器中最大后驗概率的類別。

5 文本分類實驗仿真

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

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

圖1 對SRC和SVM性能分析

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

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

表1 分類效果比較

表2給出了在SRC和SVM結合后的分類效果。給出了三種結合方法的分類：第一，SRC和三種不同分類規(guī)則結合，第二，基于高斯核函數(shù)，直方圖交叉核，卡方核函數(shù)，還有Hellinger核函數(shù)的SVM結合，第三，將三種結合后SRC和四種結合后的SVM相結合?？梢钥闯觯擲RC的三種不同規(guī)則相結合時，分類正確率提高了約5%。，當用四種SVM函數(shù)結合時有正確率提高了大約7%，當結合所有的SRC和SVM時，分類正確率提高了約8%。

表2 SRC和SVM結合后的分類效果

6 結語

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

［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］尚朝軒，王品，韓壯志，等.基于類決策樹分類的特征層融合識別算法［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文本分類器類偏斜問題的一種處理對策［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］.電子與信息學報，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］.南京大學學報（自然科學版），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日

劉國鋒，男，碩士研究生，研究方向：信息處理理論與技術應用。