一種基于SVM的博客大數據分類算法及應用

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

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

?

一種基于SVM的博客大數據分類算法及應用

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

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

提出了一種基于SVM的博客大數據分類算法BBD-SVM，根據RSS博客文本特點提取博客特征詞，通過SVM模型參數尋優化SVM分類模型實現博客大數據分類。并設計了RSS博客爬蟲，以互聯網上各種計算機程序設計語言的技術博客為爬取對象，利用BBD-SVM算法對相關技術博客進行專業分類，為用戶學習程序設計語言提供專業推薦服務。其中，博客文本特征的提取選用改進的TF-IDF作為權重計算函數，SVM分類模型的參數尋優很好地提高了分類效率。實驗結果表明，BBD-SVM算法具有準確率高，耗時少的優勢，能夠實現快速準確的博客推薦服務。

支持向量機；博客；大數據；分類算法；社交網絡；用戶推薦

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

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

1　SVM分類模型

支持向量機(Support Vector Machine，SVM)是一種基于統計學習理論的通用學習方法。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‖，所以在此基礎上使‖w‖最小的超平面就是最優的分類超平面，H1和H2上的樣本點就是支持向量[3]。根據最優化理論求得最優解的w*，再用一個支持向量計算出b*就可以得到最后的分類函數f(x)=sgn{(w*+x)+b*}，最后根據分類函數f(x)就能對輸入樣本進行分類計算了。

圖1　 SVM分類原理圖

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

2　TF-IDF的改進

2.1傳統TF-IDF

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

TF-IDF計算公式為：

(1)

其中，m為特征詞在博客文本d中出現的次數，M為博客文本d中總詞數。

(2)

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

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

而且，傳統TF-IDF函數中的IDF部分只考慮了特征詞與它出現的博客文本數之間的關系，而忽略了當前類別中的特征詞在不同的類別間的分布情況。

2.2改進的TF-IDF

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

TF的改進：文檔內的詞頻率更改為同一類文檔內的詞頻率。

IDF的改進如下式：

(3)

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

(4)

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

3　BBD-SVM分類算法

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

圖2　 BBD-SVM分類研究思路

3.1博客信息特征提取

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

步驟一：通過爬蟲工具爬取到標準的RSS格式的博客信息，RSS是一種基于XML的標準格式，規則且解析容易。

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

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

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

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

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

圖 3　 特征詞提取結果樣例

3.2SVM模型參數尋優

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

圖 4　 傳統的SVM參數尋優過程

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

圖 5　 UD-SVR參數尋優過程

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

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

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

表1　傳統參數尋優與UD-SVR算法尋優對比試驗

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

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　實驗結果與分析

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

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

表2　訓練樣本數量實驗

表3　分類類別數量實驗

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

圖 6　 訓練樣本數量與各類F1值關系圖

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

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

圖 7　 訓練樣本數量與訓練時間關系圖

試驗中均使用了UD-SVR參數尋優算法進行樣本訓練，如果使用傳統尋優，表1的實驗結果可以看出，在面對大量多類別的訓練樣本時，訓練所花費的時間將是極高的。

5　總結與展望

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

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

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

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

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

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

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

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

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

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

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

[責任編校： 張巖芳]

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年國家大學生創新項目(41301371)(Q20141410)

陳建峽(1971-)， 女，湖北丹江口人，湖北工業大學副教授，研究領域為數據挖掘，搜索引擎

朱季騏(1994-)，男，湖北潛江人，湖北工業大學本科生，研究領域為數據挖掘

1003-4684(2016)04-0070-05

TP393

A