樸素貝葉斯算法和SVM算法在Web文本分類中的效率分析

詹 毅

(成都大學旅游文化產業學院,四川 成都 610106)

樸素貝葉斯算法和SVM算法在Web文本分類中的效率分析

詹 毅

(成都大學旅游文化產業學院,四川 成都 610106)

為分析對比樸素貝葉斯算法和SVM算法在Web文本分類中的效率及其適用的范圍,構建了一個Web分類系統,此分類系統將已分類的Web網頁作為訓練集,利用分類算法構建Web分類器,通過Web測試集評價兩類算法在Web文本分類中的性能體現,為Web文本分類算法選擇提供一定的參考依據.

Web分類系統;樸素貝葉斯算法;SVM算法;效率分析

0 引 言

隨著互聯網上海量文本信息的增加,數據挖掘擴展到了Web數據挖掘,文本挖掘也隨之擴展到了Web文本挖掘.Web文本分類技術是Web文本挖掘的重要分支之一,而文本分類算法的選擇對Web文本分類技術至關重要.本研究通過構建Web分類系統,將樸素貝葉斯算法和支持向量機算法(Support Vector Machine,SVM)在自建的Web分類系統中進行測試對比,探討2類算法在Web分類過程中的特性及適用范圍.

1 Web分類系統總體設計

為選擇一個對網頁內容已分類的Web網站,本研究選取網易門戶網站(www.163.com).從該網站下載數據,并將其分為訓練集和測試集,然后利用樸素貝葉斯算法和SVM算法對其進行建模和測試,最終評價2種算法的性能.分類系統總體流程設計如圖1所示.

2 Web數據采集及處理

2.1 Web數據預采集

采用Hatem Mostafa編寫的開源Net Crawler[1]作為網絡爬蟲(Spider),從網易下載Sports,Life,Finance等7個分類下的共約80 000個HTML文件,并對它們進行數據預處理.數據處理流程如圖2所示,具體步驟為:

圖1 Web分類系統數據流程設計圖

圖2 數據預處理流程圖

1)使用網絡爬蟲下載網易7個分類下足夠數量的HTML文件;

2)利用開源軟件SgmlReader[2]和部分人工處理的方法將每個正常HTML文件轉換為符合XML格式的XML文件;

3)對每個XML文檔提取其主題信息;

4)利用中科院ICTCLAS分詞器[3]將提取出的文本信息進行分詞,并以向量空間模型的形式儲存.

在步驟4)時,可根據不同的文本分類算法對單詞做進一步的統計,生成不同的向量模型.使用樸素貝葉斯分類過程中,由于算法需要“單詞—詞頻”數組對及“單詞—類別”對應的頻率矩陣,其對空間要求相對較小但對查找速度要求較高,故本研究采用.NET類庫中的Hashtable存儲上述向量,而在SVM算法中必須生成“文檔—詞頻向量”向量矩陣,需利用二維數組滿足相應要求,對存儲空間要求較高.

2.2 算法建模

2.2.1 樸素貝葉斯算法建模.

樸素貝葉斯算法描述[4]如下:

1)收集Docs中所有的單詞;

2)vocabulary←Docs中文本文檔出現的所有單詞集合;

3)計算概率P(Vj)和 P(wk|Vj):

①對V分類集中的每一個目標值Vj有,

docs←Docs中類標簽的Vj的文檔子集,

n←在docs中不同單詞的總數,

②對vocabulary中每一個單詞wk有,

nk←單詞wk在docsj中出現的次數

實現過程中,利用Hashtable存儲 vocabulary,利用j個HashTable以 ＜wk,nk＞的格式存儲每個分類下的詞頻統計信息,得到n,nk,|vocabulary|,最終求出P(wk|Vj).將所有w對應所有V的P(wk|Vj)值儲存為一個K行J列的矩陣,為下一步測試數據做準備,其中,K是所有wk總數,J是所有Vj總數.

2.2.2 SVM算法建模.

SVM算法作為新一代機器學習算法,近年來被成功地應用到很多模式識別問題中,其在數學上表示為求解一個二次規劃問題[5].因此,SVM算法可以利用Matlab中的quadprog函數實現建模.在選擇核函數K(x1,x2)=(x1*x2+1)2后(該核函數是分類系統中較常用的一個核函數,也有文獻中指出文本分類多是線性可分的,可以使用線性核函數[6]),利用文獻[5]中的算法,可編寫Matlab程序實現SVM算法建模.

3 文本分類算法評估

3.1 文本分類算法評估依據

對分類算法的性能評估其主要依據來自于各分類算法對測試集的評估結果,根據文檔測試集的實際真實類別Oc和分類算法所分類識別的類別Pc之間的關系,可形成如表1所示的混淆矩陣[4].其中,數據集的類別用c1,c2,…,cm表示,數據a(Oci,Pcj)表示真實類別為Oci,分類識別類型為Pcj的實例數量.

表1 分類混淆矩陣

從表1中可以看出,對角線所示的數字為分類正確的實例個數,最理想的分類算法應是除對角線上的數據不為0外,其余所有各個位置全部為0.

通常,算法C的精確度ACC(C)可以定義為,

式中,N為實例的總個數.

對于每個單獨類,還可以定義2個度量值,即召回率(查全率)和準確率(精度).

召回率(Recall)是實際為ci類別的所有實例中被分類算法正確分類為ci的比例,

準確率(Precision)是所有被分類算法識別為 ci類的實例(包括實例類別為其他類而錯分到ci中實例)中確實是分類為ci的實例所占的比例,

一般期望召回率和準確率同時都盡可能高,這2個指標高,則說明該分類算法更有效.如果用一個指標來平衡這2個指標,則可以定義 F1測度.F1測度是一種綜合了準確率與召回率的指標.只有當2個值均比較大的時候,對應的F1測度才比較大,它是比單一的召回率和準確率更具有代表性的指標.

實際上,F1測度就是概率與統計中F指數的常用形式(β=1).F指數定義為,

式中,β是權重,且 β＞0.

3.2 樸素貝葉斯算法與SVM算法評估

3.2.1 樸素貝葉斯算法評估.

樸素貝葉斯的測試算法[4]如下,

//Doc為待分類的目標文檔,ai表示Doc中第i個單詞.

2)返回v.

樸素貝葉斯分類測試根據樸素貝葉斯建模得到的P矩陣,查找若干矩陣值并求和且比較和大小,這一過程完成較快.同時,空間占用率也只有O(K*J+T*K)的大小,其中,K 是vocabualry中的單詞數目,J是分類總數,T是測試文檔總數.事實上很少有一個文檔包含了vocabulary中的所有單詞,所以實際的空間占用會比T*K少得多.

表2為利用7 000*7個訓練集訓練后的樸素貝葉斯分類器對3 500*7個測試集的測試結果.

表2 樸素貝葉斯分類器測試結果

由表2數據可知,在處理24 500個文檔的情況下,樸素貝葉斯分類器的平均召回率達到73.60%,平均準確率達到78.03%.

3.2.2 SVM算法評估.

因為用于SVM的分類方法一次只能劃分正類和負類,所以需要對業務需求中的7個分類逐一進行分類.本研究采取一類對余類的多類算法[7],以其中一個類別為正類,其他為負類來訓練SVM,并使用其對測試集進行測試,在計算正確率時使用如下公式,

在部署實施此分類系統時,判斷任一篇未知類別文檔分類的方法是:假定它屬于分類1,以分類1為正類,其他類為負類來訓練SVM分類器;測試未知類別文檔類型,若類型為正,則未知類別文檔類別為1,否則假定它屬于分類2.重復上述過程,直至找到它為正的類別,或者在所有類別都被假設而無一為正后,認為該文檔類型是無法分類的文檔類型.

本研究經過編寫Matlab決策函數對1 217個文檔進行訓練后,對916個文檔進行了測試,測試結果如表3所示.

表3 SVM分類測試結果

表3結果顯示,全部文檔都被標記了分類,準確率平均為89.79%,召回率平均為80.97%,F1測度的平均值為85.13%.

3.2.3 算法性能比較.

樸素貝葉斯算法和SVM算法所做對比測試中的性能參數如表4所示.

表4 樸素貝葉斯與SVM性能比較

4 結 論

綜合全部實驗對比結果,在召回率和準確率上SVM算法有較大優勢,但是在分類速度和訓練集、測試集大小上,樸素貝葉斯算法則擁有明顯優勢.因此,在處理大規模的文檔且對分類精度要求相對不是很嚴格的情況下,樸素貝葉斯算法更為適用.反之在處理小規模文檔且對精確度要求較高的情形下SVM算法更為適用.另外,如果分類任務是在兩類之中分出一類,SVM算法更為方便,反之如果是多類任務的劃分,則樸素貝葉斯算法更為方便.

[1] HatemMostafa.NetCrawler[CP/OL].[2006-3-19].http://www.codeproject.com/KB/IP/Crawler.aspx,2012-10-11.

[2] Chris Lovett.SgmlReader[CP/OL].[2010-3-14].http://wiki.developer.mindtouch.com/SgmlReader,2012-10-11.

[3] 張華平.ICTCLAS[CP/OL].[2012-7-3].http://ictclas.org,2012-10-11.

[4] 胡可云.數據挖掘理論與應用[M].北京:清華大學出版社,2008.

[5] 董婷.支持向量機分類算法在MATLAB環境下的實現[J].榆林學院學報,2008,18(4):94-96.

[6] 孫強,李建華,李生紅.基于 Python的文本分類系統開發研究[J].計算機應用與軟件,2011,28(3):13-14.

[7] 鄧乃揚,田英杰.數據挖掘中的新方法——支持向量機[M].北京:科學出版社,2004.

[8] 陳葉旺,余金山.一種改進的樸素貝葉斯文本分類方法[J].華僑大學學報,2011,32(4):401-404.

[9] 段瑩.支持向量機在文本分類中的應用[J].計算機與數字工程,2012,40(7):87-88.

Efficiency Analysis of Naive Bayes Algorithm and SVM Algorithm in Web Text Classification

ZHAN Yi
(School of Tourism and Culture Industry,Chengdu University,Chengdu 610106,China)

A web classification system is built to analyze and compare the efficiency and scope of Naive Bayes algorithm and SVM algorithm in web text classification.The classified Web pages are used for training sets.The Web text classifier is built by using classification algorithm.The performance of both algorithms in the web text classification is evaluated by the web test set,which provides some reference for selection of web text classification algorithms.

web classification system;Naive Bayes algorithm;SVM algorithm;efficiency analysis

TP391.1

A

1004-5422(2013)01-0050-04

2012-11-14.

詹 毅(1983—),男,碩士,從事計算機模擬與仿真技術研究.

book=46,ebook=46