一種基于SVM的博客大數(shù)據(jù)分類算法及應(yīng)用

陳建峽， 朱季騏， 王鷹適， 倪一鳴

(1 湖北工業(yè)大學(xué) 計算機學(xué)院，湖北 武漢 430068； 2 湖北泰信科技信息發(fā)展有限責(zé)任公司, 湖北 武漢 430071)

?

一種基于SVM的博客大數(shù)據(jù)分類算法及應(yīng)用

陳建峽1， 朱季騏1， 王鷹適2， 倪一鳴2

(1 湖北工業(yè)大學(xué) 計算機學(xué)院，湖北 武漢 430068； 2 湖北泰信科技信息發(fā)展有限責(zé)任公司, 湖北 武漢 430071)

提出了一種基于SVM的博客大數(shù)據(jù)分類算法BBD-SVM，根據(jù)RSS博客文本特點提取博客特征詞，通過SVM模型參數(shù)尋優(yōu)化SVM分類模型實現(xiàn)博客大數(shù)據(jù)分類。并設(shè)計了RSS博客爬蟲，以互聯(lián)網(wǎng)上各種計算機程序設(shè)計語言的技術(shù)博客為爬取對象，利用BBD-SVM算法對相關(guān)技術(shù)博客進行專業(yè)分類，為用戶學(xué)習(xí)程序設(shè)計語言提供專業(yè)推薦服務(wù)。其中，博客文本特征的提取選用改進的TF-IDF作為權(quán)重計算函數(shù)，SVM分類模型的參數(shù)尋優(yōu)很好地提高了分類效率。實驗結(jié)果表明，BBD-SVM算法具有準(zhǔn)確率高，耗時少的優(yōu)勢，能夠?qū)崿F(xiàn)快速準(zhǔn)確的博客推薦服務(wù)。

支持向量機；博客；大數(shù)據(jù)；分類算法；社交網(wǎng)絡(luò)；用戶推薦

目前，博客文本分類方法主要有樸素貝葉斯法、K最鄰近(kNN，k-Nearest Neighbor)方法和支持向量機(SVM, Support Vector Machine)方法。樸素貝葉斯法是通過假設(shè)各個單詞之間兩兩獨立，然后用條件概率模型進行分類。kNN方法是一種基于實例的文本方法，對一個測試文本計算它與訓(xùn)練樣本中每個文本的相似度，找出k個最相似的文本，在此基礎(chǔ)上給每一個文本類別打分，然后根據(jù)打分高低排序分類[1]。SVM方法通過對樣本的學(xué)習(xí)尋找最優(yōu)分類超平面，然后根據(jù)找到的最優(yōu)分類超平面進行分類。在與樸素貝葉斯法和kNN方法的比較中，SVM方法取得了更好的分類效果，并且對于高維數(shù)據(jù)的處理表現(xiàn)出了 優(yōu)良的性能[2]。

本文基于SVM，提出博客大數(shù)據(jù)分類算法BBD-SVM(Blog Big Data-SVM)，通過SVM分類模型實現(xiàn)相關(guān)技術(shù)博客專業(yè)分類。在該模型中采用了改進的TF-IDF權(quán)重計算函數(shù)，提高了SVM的分類效率。

1　SVM分類模型

支持向量機(Support Vector Machine，SVM)是一種基于統(tǒng)計學(xué)習(xí)理論的通用學(xué)習(xí)方法。SVM的基本思想見圖1，圖中實心圓代表正樣本，空心圓代表負樣本，每一個樣本點可以表示為(x,y)，其中x代表該樣本的特征向量，y代表樣本類別。這里樣本類別y∈{+1,-1}。需要找到一個分類超平面H(二維平面中為一條直線)將2類樣本分開，這個分類超平面可以表達為w·x-b=0。過離H最近的正負樣本點且平行于H的超平面分別為H1、H2，H1與H2之間的距離成為分類間隔。為了簡化計算表達，對于樣本集(xi,yi),i=1,…,n需要滿足yi[(w·xi)+b]≥1，此時分類間隔等于2/‖w‖，所以在此基礎(chǔ)上使‖w‖最小的超平面就是最優(yōu)的分類超平面，H1和H2上的樣本點就是支持向量[3]。根據(jù)最優(yōu)化理論求得最優(yōu)解的w*，再用一個支持向量計算出b*就可以得到最后的分類函數(shù)f(x)=sgn{(w*+x)+b*}，最后根據(jù)分類函數(shù)f(x)就能對輸入樣本進行分類計算了。

圖1　 SVM分類原理圖

SVM模型的確定主要在于核函數(shù)與其參數(shù)選擇，為了使SVM適用于大樣本數(shù)據(jù)集的訓(xùn)練就需要加快參數(shù)尋優(yōu)速度或縮小參數(shù)尋優(yōu)范圍，所以本文使用一種基于均勻設(shè)計的自調(diào)用SVR方法(UD-SVR)來解決這一問題[4]。

2　TF-IDF的改進

2.1傳統(tǒng)TF-IDF

在博客文本特征的提取時，權(quán)重計算函數(shù)選用了目前應(yīng)用較多、效果較好的TF-IDF函數(shù)，評估特征詞的重要程度。TF-IDF的思想是:如果一個特征詞在某個文檔中出現(xiàn)次數(shù)很多，且其他的文檔中包含該特征詞較少，則該特征詞能夠很好地表示該文檔。TF為詞頻，表示特征詞m在博客文本d中出現(xiàn)的次數(shù)，反映博客文本的內(nèi)部特征。IDF為逆文本頻數(shù)，表示某一特征詞m在整個博客文本集合中的分布情況，反映博客文本間的特征。

TF-IDF計算公式為：

(1)

其中，m為特征詞在博客文本d中出現(xiàn)的次數(shù)，M為博客文本d中總詞數(shù)。

(2)

其中：n為包含某項特征詞的博客文本總數(shù)，N為總博客文本數(shù)。

TF-IDF將博客文本集作為整體處理，但是在IDF的計算中，存在很大的問題。往往一些生僻詞的IDF會比較高，這些生僻詞就會被誤認為是文檔關(guān)鍵詞。

而且，傳統(tǒng)TF-IDF函數(shù)中的IDF部分只考慮了特征詞與它出現(xiàn)的博客文本數(shù)之間的關(guān)系，而忽略了當(dāng)前類別中的特征詞在不同的類別間的分布情況。

2.2改進的TF-IDF

現(xiàn)有待分類博客文本類別的集合Y={y1,y2,…,yj}，在yi(yi∈Y)中，博客文本集合D={d1,d2,…,dn}，n為博客文本數(shù)目。特征詞集合M={m1,m2,…,mk}，k為yi中出現(xiàn)的所有詞語個數(shù)。針對傳統(tǒng)的TF-IDF中存在的不足，本文選取了一種改進的TF-IDF函數(shù)，對TF和IDF的計算方面都做了改進[5]。

TF的改進：文檔內(nèi)的詞頻率更改為同一類文檔內(nèi)的詞頻率。

IDF的改進如下式：

(3)

其中，P(mk)表示特征詞mk在當(dāng)前類別中的頻率，P(mk)′表示特征詞mk在其他類別中的頻率。從(3)式中可以看出，當(dāng)P(mk)很大，IDF的絕對值反而小。對它取反，根據(jù)log函數(shù)的特性，自變量要大于0，IDF要為正值，則修正后的IDF公式為

(4)

實驗中運用改進后的IF-IDF函數(shù)，提取訓(xùn)練博客文本集D中每個類別yi的特征詞時，特征詞與類別相關(guān)性相較于傳統(tǒng)TF-IDF效果更好，分類效果也有了很大的改善[6]。

3　BBD-SVM分類算法

本文根據(jù)博客信息的特點，利用參數(shù)尋優(yōu)的方法改進SVM模型，研究并實現(xiàn)了一種新的BBD-SVM(BlogBigData-SVM, 基于SVM的博客大數(shù)據(jù))分類算法，以計算機程序設(shè)計語言為分類的實驗對象，為用戶提供專業(yè)的程序設(shè)計語言技術(shù)博客分類。實驗表明，BBD-SVM分類算法具有較高的分類精度和訓(xùn)練速度。BBD-SVM分類算法的研究思路見圖 2。

圖2　 BBD-SVM分類研究思路

3.1博客信息特征提取

利用項目組以前開發(fā)的博客搜索引擎中的爬蟲工具[7]，爬取各大技術(shù)博客網(wǎng)站的網(wǎng)頁信息，由于爬取下來的信息均為網(wǎng)頁標(biāo)簽文本信息，不能直接用于分類模型的訓(xùn)練和預(yù)測，所以必須要對文本信息進行特征提取的預(yù)處理過程。具體步驟如下：

步驟一：通過爬蟲工具爬取到標(biāo)準(zhǔn)的RSS格式的博客信息，RSS是一種基于XML的標(biāo)準(zhǔn)格式，規(guī)則且解析容易。

步驟二：按照RSS格式將標(biāo)題、標(biāo)簽和正文內(nèi)容解析保存為純文本，并在此過程中進行一些特殊符號等的過濾處理。

步驟三：本文選用性能和準(zhǔn)確率都比較出眾并帶有詞性分析功能的中文分詞器Ansj，對博客文本信息進行分詞與統(tǒng)計。

步驟四：根據(jù)分詞后每個詞的詞性再對分詞后的結(jié)果進行一次過濾，得到最終的處理語料。

步驟五：根據(jù)改進后的TF-IDF公式計算每個詞的TF-IDF的值，根據(jù)TF-IDF值的高低選擇每個類別的特征詞。

本文針對計算機程序設(shè)計的技術(shù)博客進行了爬取，獲得相應(yīng)的博客信息特征提取結(jié)果見圖3樣例所示。

圖 3　 特征詞提取結(jié)果樣例

3.2SVM模型參數(shù)尋優(yōu)

3.2.1傳統(tǒng)參數(shù)尋優(yōu)傳統(tǒng)的SVM參數(shù)尋優(yōu)的流程見圖4，尋優(yōu)需要對參數(shù)c，g(c表示懲罰系數(shù)，g表示核函數(shù)參數(shù))組合在給定范圍內(nèi)進行窮盡搜索。搜索次數(shù)為兩個參數(shù)向量長度的乘積，總的搜索時間為搜索次數(shù)乘訓(xùn)練樣本個數(shù)。對于小樣本數(shù)據(jù)窮盡搜索算法運行時間尚能接受，但隨著樣本數(shù)目的增大，所需的計算時間會呈幾何級數(shù)增加，致使SVM無法有效適用于大數(shù)據(jù)集。一般情況下，g的選取需要根據(jù)實際的分類情況把握其范圍。由于本文研究的是博客文本分類方面，且博客文本分類量化后向量比較稀疏，g的最優(yōu)參數(shù)一般偏小。所以，文中c和g這兩個參數(shù)的范圍定為：log2c=-1:1:14，log2g=-8:-1:-23。

圖 4　 傳統(tǒng)的SVM參數(shù)尋優(yōu)過程

3.2.2UD-SVR算法尋優(yōu)本文運用UD-SVR算法[8]，對傳統(tǒng)的SVM尋優(yōu)方法進行了優(yōu)化。該算法以基于均勻設(shè)計的自調(diào)用SVR代替?zhèn)鹘y(tǒng)參數(shù)尋優(yōu)過程，并從兩個方面對傳統(tǒng)SVM尋優(yōu)方法進行了優(yōu)化。一方面，基于均勻設(shè)計僅從全部256組參數(shù)組合中選取16組具有代表性的組合，有效降低搜索范圍，大幅度縮短了尋優(yōu)時間。另一方面，基于此16個參數(shù)組合及其評價指標(biāo)(準(zhǔn)確率)以自調(diào)用SVR建立評價指標(biāo)與參數(shù)組合之間的關(guān)系模型，并以此對全部參數(shù)組合進行預(yù)測，以預(yù)測的評價指標(biāo)代替?zhèn)鹘y(tǒng)SVM尋優(yōu)方法中的交叉測試評價指標(biāo)，有效提升了尋優(yōu)效率。UD-SVR參數(shù)尋優(yōu)的流程見圖5。

圖 5　 UD-SVR參數(shù)尋優(yōu)過程

均勻設(shè)計(UniformDesign)，是只考慮試驗點在試驗范圍內(nèi)均勻散布的一種試驗設(shè)計方法。它由方開泰[9]教授和數(shù)學(xué)家王元共同提出，是數(shù)論方法中的“偽蒙特卡羅方法”的一個應(yīng)用，它能提高試驗點“均勻分散”的程度，使試驗點具有更好的代表性,能用較少的試驗獲得較多的信息。由于c，g因素水平不同，根據(jù)混合水平均勻設(shè)計表生成n個(c,g)組合(本文中n等于16)。

將16組(c,g)組合對訓(xùn)練樣本進行交叉驗證得到對應(yīng)的16個準(zhǔn)確率值，然后將這16組參數(shù)組合和準(zhǔn)確率作為訓(xùn)練樣本進行SVR訓(xùn)練，得到一個SVR預(yù)測模型，利用這個模型本文 可以對全部256組參數(shù)組合預(yù)測其準(zhǔn)確率，從預(yù)測的準(zhǔn)確率中選取準(zhǔn)確率最高的一組參數(shù)做為本文 的最優(yōu)參數(shù)組合，最后將這組最優(yōu)參數(shù)組合作為訓(xùn)練SVC的參數(shù)進行訓(xùn)練就得到了最終的分類模型。

本文使用三個方面的數(shù)據(jù)集進行對比試驗，數(shù)據(jù)集1為UCI酒類數(shù)據(jù)集、數(shù)據(jù)集2為搜狗開放的新聞?wù)Z料數(shù)據(jù)集，數(shù)據(jù)集3為本文 爬取的博客數(shù)據(jù)集，實驗結(jié)果見表1。

表1　傳統(tǒng)參數(shù)尋優(yōu)與UD-SVR算法尋優(yōu)對比試驗

從表1中可以看出：采用UD-SVR尋優(yōu)算法和不采用的精度差別不大，但是訓(xùn)練耗時則有著數(shù)量級的差別，所以UD-SVR尋優(yōu)算法可以在幾乎不損失分類精度的前提下大幅度提升訓(xùn)練尋參速度，非常適合用于緯度高、計算量大的文本多分類問題。

3.3BBD-SVM算法表達

將BBD-SVM算法用偽代碼形式表達如下：

webcrawling;

for(i=0,i

pretreatment;

for(i=0,i

wordsegment;

for(i=0,i

wordcount;

for(i=0,i

{for(everyword)

tfidf-tf*idf

sortbytfidf;

}

for(i=0;i

getfeatureword;

for(i=0;i

(j=0;j

{

if(bloghasfeatureword

vector[j]=countoffeatureword;

}

if(totrain(

svmtrainwithud-svr;

if(topredict)

svmpredict;

4　實驗結(jié)果與分析

如上所述，本文從互聯(lián)網(wǎng)上獲取真實數(shù)據(jù)進行實驗，利用Heritrix爬蟲工具[7]從網(wǎng)絡(luò)中爬取博客信息。然后運用改進的TF-IDF函數(shù)進行特征詞的提取，并將每篇博客的文本信息量化為數(shù)值信息, 進行訓(xùn)練樣本數(shù)量和分類類別數(shù)量的實驗。

本文選擇的是CSDN等技術(shù)博客網(wǎng)站進行的數(shù)據(jù)爬取，所以實驗以多種編程語言為分類類別進行。訓(xùn)練樣本數(shù)量實驗中, 類別數(shù)為5，樣本維度為1000，預(yù)測樣本數(shù)量為5000；分類類別數(shù)實驗中訓(xùn)練樣本數(shù)量為2000/類，測試樣本數(shù)量為2000/類，樣本維度為100維/類。訓(xùn)練樣本數(shù)量實驗結(jié)果見表2，對應(yīng)的分類類別數(shù)量實驗的結(jié)果見表3。

表2　訓(xùn)練樣本數(shù)量實驗

表3　分類類別數(shù)量實驗

由表3可以看出分類類別的增加會使得分類準(zhǔn)確率有所下降，而且由于分類類別的增加，訓(xùn)練樣本的增加和樣本維度也需要隨之增加，導(dǎo)致訓(xùn)練時間大幅增加。

圖 6　 訓(xùn)練樣本數(shù)量與各類F1值關(guān)系圖

圖6中，查準(zhǔn)率(precision)表示檢出相關(guān)文檔與檢出全部文檔的百分比，查全率(recall)表示檢出相關(guān)文檔與所有相關(guān)文檔的百分比，這里相關(guān)即指同類別。綜合查準(zhǔn)率和查全率，F(xiàn)1=2×查準(zhǔn)率×查全率/(查準(zhǔn)率+查全率)，用F1值作為分類好壞的指標(biāo)，F(xiàn)1值越高，說明分類效果越好，分類精度越高。

由圖6可以看出分類結(jié)果的精度會隨著訓(xùn)練樣本的數(shù)量增加而增加，但是增長速度會隨之下降，由圖7可以看出訓(xùn)練時間會隨訓(xùn)練樣本數(shù)量的增加而增加，并且增長的速度越來越快。所以，為了提高分類精度，大量的訓(xùn)練樣本是必須的，但伴隨大量樣本，訓(xùn)練時間會迅速增長。

圖 7　 訓(xùn)練樣本數(shù)量與訓(xùn)練時間關(guān)系圖

試驗中均使用了UD-SVR參數(shù)尋優(yōu)算法進行樣本訓(xùn)練，如果使用傳統(tǒng)尋優(yōu)，表1的實驗結(jié)果可以看出，在面對大量多類別的訓(xùn)練樣本時，訓(xùn)練所花費的時間將是極高的。

5　總結(jié)與展望

提出了一種運用SVM分類模型進行博客分類的BBD-SVM算法，該算法使用改進的TF-IDF進行特征提取，并采用改進的參數(shù)尋優(yōu)算法對SVM中的c和g參數(shù)做了尋優(yōu)處理。實驗結(jié)果表明，該方案在面對大量訓(xùn)練樣本和高樣本維度時，呈現(xiàn)出了較高的準(zhǔn)確率和較少的樣本訓(xùn)練時間，取得了一定成果。

對于類別過多的情況,準(zhǔn)確率還是差強人意，而且多分類問題中特征提取的維度還是較高，如何更好地適應(yīng)分類類別數(shù)量較大的應(yīng)用環(huán)境和如何縮小特征提取維度將會是未來研究的重點。

[1]陳建峽,李志鵬. 基于移動終端的博客搜索引擎系統(tǒng)研究與應(yīng)用[J].湖北工業(yè)大學(xué)學(xué)報,2015,30(2):89-94.

[2]崔彩霞, 馮登國. 文本分類方法對比研究[J]. 太原師范學(xué)院學(xué)報(自然科學(xué)版), 2007, 6(4): 52-54.

[3]成艷潔. 基于SVM的多類文本分類算法及應(yīng)用研究[D].西安:西安理工大學(xué)圖書館, 2011.

[4]CohenE,KrishnamurthyB.AshortwalkintheBlogistan[J].ComputerNetworks,2006,50(5):615-630.

[5]覃世安, 李法運. 文本分類中TF_IDF方法的改進研究[J].現(xiàn)代圖書情報技術(shù), 2013, 238: 27-30.

[6]盧中寧, 張保威. 一種基于改進TF-IDF[J]. 河南師范大學(xué)學(xué)報(自然科學(xué)版), 2012, 40(6): 158-160.

[7]吳偉, 陳建峽 . 基于Heritrix的web信息抽取優(yōu)化與實現(xiàn)[J]. 湖北工業(yè)大學(xué)學(xué)報,2012， 27 (2):23-26.

[8]龔永罡, 湯世平. 面向大數(shù)據(jù)的SVM參數(shù)尋優(yōu)方法[J]. 計算機仿真, 2010, 27(9): 204-207.

[9]方開泰.均勻設(shè)計與均勻設(shè)計表[M].北京:科學(xué)出版社,1994:18-23.

[責(zé)任編校： 張巖芳]

A SVM-based Blog Big Data Classification Algorithm and Its Application

CHEN Jianxia1， ZHU Jiqi1，WANG Yingshi2，NI Yiming2

(1.SchoolofComputerScience,HubeiUniversityofTechnology,Wuhan, 430068,China; 2HubeiTaixinInformationDevelopmentCo.,Ltd.,Wuhan, 430071,China)

The paper proposes a blog big data classification algorithm based on Support Vector Machine (Blog Big Data-SVM, namely BBD-SVM). It completes blog texts’feature extraction according to the RSS blogs characteristics, and optimizes SVM classification model via improving its

to realize blog big data classification efficiently. The paper designs a crawler for the RSS blogs especially, takes a variety of technology blogs about computer programming languages over the Internet as objects. Therefore, the proposed algorithm can provide the users with relevant professional classifications of technology blogs accurately. In particular, the proposed approach utilizes the improved TF-IDF as the weight calculation function when extracting blog text features, and the improved SVM model has been verified to be a good way to improve the classification efficiency. The experimental results show that BBD-SVM algorithm has high accuracy and less time-consuming advantages, so that it is able to achieve fast and accurate information referral blog services for the users.

SVM; blog; big data; classification algorithm; user recommenation

2015-09-15

2013年國家大學(xué)生創(chuàng)新項目(41301371)(Q20141410)

陳建峽(1971-)， 女，湖北丹江口人，湖北工業(yè)大學(xué)副教授，研究領(lǐng)域為數(shù)據(jù)挖掘，搜索引擎

朱季騏(1994-)，男，湖北潛江人，湖北工業(yè)大學(xué)本科生，研究領(lǐng)域為數(shù)據(jù)挖掘

1003-4684(2016)04-0070-05

TP393

A