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

詹 毅

(成都大學旅游文化產(chǎn)業(yè)學院,四川 成都 610106)

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

詹 毅

(成都大學旅游文化產(chǎn)業(yè)學院,四川 成都 610106)

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

Web分類系統(tǒng);樸素貝葉斯算法;SVM算法;效率分析

0 引 言

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

1 Web分類系統(tǒng)總體設計

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

2 Web數(shù)據(jù)采集及處理

2.1 Web數(shù)據(jù)預采集

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

圖1 Web分類系統(tǒng)數(shù)據(jù)流程設計圖

圖2 數(shù)據(jù)預處理流程圖

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

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

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

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

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

2.2 算法建模

2.2.1 樸素貝葉斯算法建模.

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

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

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

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

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

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

n←在docs中不同單詞的總數(shù),

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

nk←單詞wk在docsj中出現(xiàn)的次數(shù)

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

2.2.2 SVM算法建模.

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

3 文本分類算法評估

3.1 文本分類算法評估依據(jù)

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

表1 分類混淆矩陣

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

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

式中,N為實例的總個數(shù).

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

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

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

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

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

式中,β是權(quán)重,且 β＞0.

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

3.2.1 樸素貝葉斯算法評估.

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

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

2)返回v.

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

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

表2 樸素貝葉斯分類器測試結(jié)果

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

3.2.2 SVM算法評估.

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

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

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

表3 SVM分類測試結(jié)果

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

3.2.3 算法性能比較.

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

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

4 結(jié) 論

綜合全部實驗對比結(jié)果,在召回率和準確率上SVM算法有較大優(yōu)勢,但是在分類速度和訓練集、測試集大小上,樸素貝葉斯算法則擁有明顯優(yōu)勢.因此,在處理大規(guī)模的文檔且對分類精度要求相對不是很嚴格的情況下,樸素貝葉斯算法更為適用.反之在處理小規(guī)模文檔且對精確度要求較高的情形下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] 胡可云.數(shù)據(jù)挖掘理論與應用[M].北京:清華大學出版社,2008.

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

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

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

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

[9] 段瑩.支持向量機在文本分類中的應用[J].計算機與數(shù)字工程,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—),男,碩士,從事計算機模擬與仿真技術(shù)研究.

book=46,ebook=46