垃圾郵件分類算法的研究與分析

1、垃圾郵件分類算法的研究與分析西北工業(yè)大學(xué)計算機(jī)學(xué)院陜西西安710129(SchoolofComputer,NorthwesternPolytechnicUniversityXi'an710129China)摘要：隨著互聯(lián)網(wǎng)的高速發(fā)展，電子郵件已經(jīng)成為人們信息獲取和信息交流的一個重要的渠道。與此同時垃圾郵件也成為互聯(lián)網(wǎng)上的一個日益嚴(yán)重的安全問題，引起了越來越多的社會大眾和研究人員的重視和關(guān)注。為了有效的分辨垃圾郵件，本文通過對訓(xùn)練數(shù)據(jù)進(jìn)行相應(yīng)的預(yù)處理及特征提取，分別使用樸素貝葉斯、C4.5決策樹、支持向量機(jī)三種方法來對垃圾郵件進(jìn)行分類，通過測試結(jié)果，比對各個分類算法的優(yōu)劣，并進(jìn)行了詳細(xì)的

2、分析。關(guān)鍵詞：垃圾郵件樸素貝葉斯C4.5決策樹支持向量機(jī)Abstract:WiththerapiddevelopmentoftheInternet,e-mailplaysanimportantrolesinpeople'sinformationaccessandinformationexchange.Atthesametime,spamhasbecomeanincreasinglyserioussecurityproblemontheInternet,causingmoreandmoreattentionofthecommunityandresearchers.Inordertoeff

3、ectivelydistinguishthespam,thispaperPre-processingsandextractsfeatureofthetrainingdata,andusestheNaiveBayes,C4.5DecisionTreeandSVMtoclassifythespam,Throughthetestresults,compareandanalysistheadvantagesanddisadvantagesofeachclassificationalgorithm.Keywords：spamNaiveBayesC4.5DecisionTreeSVM1引言Internet

4、的問世帶來了電子郵件業(yè)務(wù)的出現(xiàn)，網(wǎng)絡(luò)技術(shù)的飛速發(fā)展促進(jìn)了郵件服務(wù)的廣泛普及及繁榮，電子郵件已經(jīng)成為生活在信息時代的人們?nèi)粘Ｉ钜粋€重要部分。電子郵件不僅是一個信息交流的重要渠道，而且也是人們信息獲取的重要途徑之一。隨著互聯(lián)網(wǎng)的普及，不僅人們的日常事務(wù)可以通過電子郵件來進(jìn)行處理，而且越來越多正式和重要的信息也通過電子郵件來進(jìn)行傳達(dá)和交流。隨著電子郵件越來越普及和重要性的持續(xù)增長，一些商家和不法分子開始利用垃圾郵件這種方式來進(jìn)行廣告信息的傳播和用戶消費行為信息的獲取。根據(jù)無線服務(wù)機(jī)構(gòu)WirelessServicesCorporation公司提供的一份最新調(diào)查顯示，目前美國移動通信市場上所有的電子郵

5、件服務(wù)當(dāng)中，43%的都是垃圾信息，而年前垃圾郵件在電子郵件中的比例為18%。而在國內(nèi)，據(jù)有關(guān)部門統(tǒng)計，國內(nèi)的電子郵件用戶，平均每天發(fā)送的短信數(shù)量超過了3億條。郵件甚至被稱為繼報紙、廣播、電視、網(wǎng)絡(luò)之后的第五媒體。不過在數(shù)量龐大的電子郵件背后，垃圾郵件的問題也愈加嚴(yán)重。垃圾郵件可以說是因特網(wǎng)帶給人類最具爭議性的副產(chǎn)品之一，它的泛濫已經(jīng)使整個因特網(wǎng)不堪重負(fù)，人們不得不花費大量時間來對付郵箱里的垃圾郵件。在這樣的情勢下，制定切實可行的反垃圾郵件方案無疑是Internet的一個重要課題，而對于反垃圾郵件技術(shù)的研究也稱為一個新的熱點領(lǐng)域。本文根據(jù)現(xiàn)有郵件分類的知識，結(jié)合訓(xùn)練數(shù)據(jù)集的特點，選擇合適的分類算

6、法，來實現(xiàn)對垃圾郵件的分類。2相關(guān)工作本文垃圾郵件的分類工作主要包括以下三個部分：文本數(shù)據(jù)預(yù)處理，數(shù)據(jù)集特征選擇，分類算法的應(yīng)用及結(jié)果分析。2.1 文本數(shù)據(jù)預(yù)處理根據(jù)提供的訓(xùn)練數(shù)據(jù)集及測試數(shù)據(jù)集，編寫程序，提取數(shù)據(jù)集中所有單詞及對應(yīng)的頻率，并更改數(shù)據(jù)格式，以矩陣的形式存儲。初步處理過后的訓(xùn)練數(shù)據(jù)集Pre-train1.csv第一行表示數(shù)據(jù)集中出現(xiàn)的所有單詞、字母和數(shù)字屬性共1000個，第2-9001行代表之前的9000條郵件訓(xùn)練數(shù)據(jù)集，對應(yīng)第一行的單詞，存儲了每個單詞出現(xiàn)的頻率。Pre-train1.csv最后一列添加了label標(biāo)簽，表明每一條數(shù)據(jù)的屬性，ham或spam。在Pre-trai

7、n1.csv的基礎(chǔ)上，我們開始對數(shù)據(jù)集中的屬性進(jìn)行篩選，去掉統(tǒng)計出來的單個字母，純數(shù)字，以及無意義詞匯屬性143條，得到最終的數(shù)據(jù)集Pre-train2.csv共包含857個可靠單詞屬性，如圖1所示，基于Pre-train2.csv數(shù)據(jù)集，我們進(jìn)行后續(xù)的特征提取。kariTHn-Jj;itile土Ar1!匚七比七lab-L&00a0hitD口L00口020tjBL6bG000dGhai.060gJQ0l-.btD口00QQ0_l10D0Qqqa0EiBL0b0曲d0d0q0200oQQ0SJiiii10QQ00u0DD0d0a0g0融>00trit、0D000Q砂n0D00q00

8、000Q0安0Qq0中小0D0屯00000000000Q00WILL-006*中fcQQu0PouQqOqq找耳彳DD003t0d0口0i100mt圖1數(shù)據(jù)集格式2.2 特征提取2.2.1 婿與信息增益燧是信息理論中一個非常重要的概念，表示任何一種能量在空間中分布的均勻程度，能量分布越均勻,越不確定，®就越大。Shannon將婿應(yīng)有于信息處理，提出了“信息婿”的概念。信息婿是信息的量化度量，是衡量一個隨機(jī)變量取值的不確定性程度令X為隨機(jī)變量，如果X隨機(jī)變量的變化越多，通過它獲取的信息量就越大，X的信息婿定義為：H(X)=-£p(Xi)lb(p(x)(2-1)通過觀察隨機(jī)變量

9、Y獲得的關(guān)于隨機(jī)變量X的信息婿定義為：H(X|Y)=-£p(yi)£p(x|y)lb(p(x|yj)(2-2)信息增益是信息燧的差，表示在消除不確定性后獲得的信息量，定義為：IG(X,Y)=H(X)H(X|Y)(2-3)信息增益是信息論中的一個重要概念，被廣泛應(yīng)用在機(jī)器學(xué)習(xí)領(lǐng)域。對分類系統(tǒng)來說，計算信息增益是針對一個一個的特征項而言的，它通過統(tǒng)計某一個特征項t在類別C中出現(xiàn)與否的文檔數(shù)來計算特征項t對類別C的信息增益1,定義為考慮出現(xiàn)前后的信息:W之差，某個特征項的信息增益值越大，表示其貢獻(xiàn)越大，對分類也越重要。因此，在進(jìn)行特征選擇時，通常選取信息增益值大的若干個單詞構(gòu)造文

10、本的特征向量。本文中，訓(xùn)練數(shù)據(jù)集中有857個屬性，全部參與訓(xùn)練效率過低，因此需要提取出有代表性的詞匯，故選用信息增益的方式來從數(shù)據(jù)集中提取特征。將處理過后的訓(xùn)練數(shù)據(jù)集導(dǎo)入到WEKA軟件中，并在預(yù)處理階段使用AttributeSelection界面中InfoGainAttributeEval來進(jìn)行信息增益特征提取，同時，將提取出來的特征屬性按信息增益由高到低進(jìn)行排列，結(jié)果如圖2所示：1 酬加0j-m3 3WHIP4 二*irW5 二mailman6 二amlprB.Hfir*加d日二StiE9msmifltp10 _Mcnr-Dlcits11 ulner12 BITSHalDT13 _Jrshi

11、xi14 .minwolt15 7?rntp&vc16 Rtgi二d17 MIA1iejuin191dasB520-kflk信息增益特征提取結(jié)果400的單詞作為最終的訓(xùn)練集，并生成Pre-train(3).arff數(shù)據(jù)圖2根據(jù)特征提取結(jié)果，選擇信息增益排列前集文件。3算法實驗與分析實驗部分采用自主程序設(shè)計和WEKA數(shù)據(jù)挖掘工具相結(jié)合的方法，利用經(jīng)過預(yù)處理的訓(xùn)練集，編寫MATLAB程序進(jìn)行垃圾郵件分類，同時，利用WEKA軟件中提供的多種常用的分類算法，進(jìn)行實驗。最后對各種分類方法的優(yōu)劣進(jìn)行總結(jié)。3.1 樸素貝葉斯算法樸素貝葉斯分類器2是一種有監(jiān)督的學(xué)習(xí)方法，其假設(shè)屬性的值對給定類的影響而

12、獨立于其他屬性值。用貝葉斯網(wǎng)表達(dá)樸素貝葉斯的分類器如圖3所示。圖3樸素貝葉斯網(wǎng)樸素貝葉斯后驗概率網(wǎng)的計算公式如式(3-1)P(C=Ck|X=x)=P(X=x|C=c"(C=cQP(X=x)(3-1)其中X表示單詞序列，C表示分類。其中P(X=x|C=ck)的計算公式如式(3-2)P(X=x|C=ck)=一：P(Xi|C=ck)(3-2)則分類結(jié)果C的選擇方式為式(3-3)C=argmax(P(C=g|X=x)(3-3)實驗部分使用兩種方法來實現(xiàn)貝葉斯分類算法，分別是MATLAB編寫程序和WEKA平臺提供的NaiveBayes算法。MATLAB程序中，根據(jù)樸素貝葉斯公式，使用經(jīng)過預(yù)處理

13、的4000條數(shù)據(jù)作為訓(xùn)練集，實驗結(jié)果如表1所示:表1基于MATLAB勺樸素貝葉斯實驗結(jié)果/40001500.0970在WEKA件中，使用9000條數(shù)據(jù)，400條屬性作為訓(xùn)練集，在Classify條目下選擇NaiveBayes分類算法，并選擇Suppliedtestset作為訓(xùn)練模型評價方法,實驗結(jié)果如表2所示：表2基于weka平臺的樸素貝葉斯分類算法實驗結(jié)果hamspamtotalham16951420spam61519580total23057010003.2 C4.5決策算法C4.5算法是目前最具影響的決策樹算法，已廣泛應(yīng)用于數(shù)據(jù)分類領(lǐng)域，C4.5算法是在ID3算法的基礎(chǔ)上改進(jìn)過來的，不僅

14、可以處理離散型描述屬性，還可以處理連續(xù)性屬性。C4.5算法采用信息增益率作為選擇分枝屬性的標(biāo)準(zhǔn)，彌補了ID3算法在使用信息增益選擇分枝屬性時偏向于取值較多的屬性的缺陷。作為ID3算法的改進(jìn)算法，C4.5算法克服了ID3算法的兩大缺點：(1) ID3算法使用信息增益作為評價標(biāo)準(zhǔn)來選擇根節(jié)點和各內(nèi)部節(jié)點中的分枝屬性，信息增益的缺點是傾向于選擇取值較多的屬性，在某些情況下這類屬性可能不會提供太多有價值的信息，而C4.5算法采用信息增益率作為評價標(biāo)準(zhǔn)，克服了ID3算法的這點不足；(2) (2)ID3算法只能處理描述屬性為離散的數(shù)據(jù)集，而C4.5算法既可以處理離散型描述性，又可以處理連續(xù)型描述屬性。C4

15、.5算法也是一種基于信息論的機(jī)器學(xué)習(xí)方法，其核心思想是通過分析訓(xùn)練數(shù)據(jù)集，在整個數(shù)據(jù)集上遞歸地建立一個決策樹。使用WEK徽據(jù)挖掘軟件提供的C4.5算法進(jìn)行分類，實驗結(jié)果如表3所示表3C4.5決策樹算法實驗結(jié)果hamspamtotalham4119420spam11569580total42257810003.3 支持向量機(jī)算法支持向量機(jī)算法簡稱SVM(SupportVectorMachine)算法4,該算法建立在統(tǒng)計學(xué)習(xí)理論中的VC維和結(jié)構(gòu)風(fēng)險最小化基礎(chǔ)之上，并結(jié)合最優(yōu)化理論來得到分類決策函數(shù)的分類算法。其基本思想是尋找一個分類超平面，將兩類樣本分到超平面的兩側(cè)他在解決非線性問題、高維模式識別

16、問題等許多問題中顯示出許多優(yōu)勢，是統(tǒng)計學(xué)習(xí)理論中比較實用的算法之一，目前已在人臉識別、手寫數(shù)字識別、文本分類5、信息檢索等領(lǐng)域得到成功應(yīng)用。支持向量機(jī)的數(shù)學(xué)模型如式（3-4）和式（3-5）,該模型保證在滿足條件下，超平面距離各樣本點距離最大。一1min一(3-4)(3-5)w,b2s.t.yi(wTxi-b)_1,i=1,2,.n利用WEK軟件實現(xiàn)支持矢量機(jī)（SMO算法的實驗結(jié)果如表4所示表4支持向量機(jī)算法實驗結(jié)果hamspamtotalham40317420spam13567580total41658410003.4 實驗結(jié)果評價與分析3.4.1 實驗評價方法測試郵件集合中垃圾郵件、非垃圾郵

17、件的數(shù)量分別是Ns、Nh,垃圾郵件中正確分類和被錯分的郵件數(shù)量分別為Nss、Nsh,非垃圾郵件中被正確分類和被錯誤分類的郵件數(shù)量分別為Nhh、Nhs,則垃圾郵件識別算法的性能可以根據(jù)以下幾個指標(biāo)進(jìn)行衡量。（1）垃圾郵件召回率（recall）垃圾郵件樣本集中能被算法正確分類的樣本所占比例，記為r,定義如式（3-6）ssNssNsh100%(3-6)可見當(dāng)垃圾郵件召回率反應(yīng)了算法對垃圾郵件的檢測能力，該值越大說明檢測能力越強(qiáng)，被遺漏的郵件越少。（2）垃圾郵件識別準(zhǔn)確率（precision）被正確識別分類的郵件數(shù)占所有樣本的比例，記為p,定義如式（3-7）(3-7)NssNhhp二NsNh準(zhǔn)確率反應(yīng)

18、郵件被正確分類的概率，準(zhǔn)確率越高，說明被錯誤分類的郵件數(shù)量就越少。3.4.2 實驗結(jié)果分析MATLAB寫程序?qū)崿F(xiàn)的樸素貝葉斯算法結(jié)果與WEKA平臺的實驗結(jié)果存在一定的差異，對比結(jié)果如表5所示表5基于MATLAB勺樸素貝葉斯實驗結(jié)果算法實現(xiàn)環(huán)境準(zhǔn)確率MATLAB0.903WEKA平臺0.888實驗結(jié)果存在差異的原因在于MATLAB1序僅僅是單純使用樸素貝葉斯公式來進(jìn)行結(jié)果計算，未考慮數(shù)據(jù)集中的噪音等因素，WEK臺的算法包括更進(jìn)一步的預(yù)處理，噪音數(shù)據(jù)去除，以及算法的優(yōu)化，導(dǎo)致實驗結(jié)果的準(zhǔn)確率低于MATLAB®序結(jié)果o基于WEKAF臺提供的三種分類方法，對比結(jié)果如表6所示表6三種算法分類效果對比準(zhǔn)確度召回率支持向量機(jī)97.0%97.8%8.24sC4.5決策樹98.0%98.1%4.12s樸素貝葉斯88.8%89.5%0.87s對比三種分類方法的實驗結(jié)果，可以發(fā)現(xiàn)樸素貝葉斯分類算法的準(zhǔn)確率和召回率最低，C4.5決策樹的準(zhǔn)確率和召回率最高，在執(zhí)行時間方面，樸素貝葉斯所需的執(zhí)行時間最短，支持向量機(jī)的執(zhí)行時間最長。4總