1、精選文檔垃圾郵件分類(lèi)算法的爭(zhēng)辯與分析西北工業(yè)高校 計(jì)算機(jī)學(xué)院 陜西 西安 710129 (School of Computer, Northwestern Polytechnic University Xian 710129 China)摘要：隨著互聯(lián)網(wǎng)的高速進(jìn)展,電子郵件已經(jīng)成為人們信息獵取和信息溝通的一個(gè)重要的渠道。與此同時(shí)垃圾郵件也成為互聯(lián)網(wǎng)上的一個(gè)日益嚴(yán)峻的平安問(wèn)題,引起了越來(lái)越多的社會(huì)大眾和爭(zhēng)辯人員的重視和關(guān)注。為了有效的辨別垃圾郵件，本文通過(guò)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行相應(yīng)的預(yù)處理及特征提取，分別使用樸實(shí)貝葉斯、C4.5決策樹(shù)、支持向量機(jī)三種方法來(lái)對(duì)垃圾郵件進(jìn)行分類(lèi)，通過(guò)測(cè)試結(jié)果，比對(duì)各個(gè)分類(lèi)算

2、法的優(yōu)劣，并進(jìn)行了具體的分析。關(guān)鍵詞：垃圾郵件 樸實(shí)貝葉斯 C4.5決策樹(shù) 支持向量機(jī)Abstract：With the rapid development of the Internet, e-mail plays an important roles in people's information access and information exchange. At the same time, spam has become an increasingly serious security problem on the Internet, causing more and mo

3、re attention of the community and researchers. In order to effectively distinguish the spam, this paper Pre-processings and extracts feature of the training data, and uses the NaiveBayes, C4.5 Decision Tree and SVM to classify the spam, Through the test results, compare and analysis the advantages a

4、nd disadvantages of each classification algorithm.Keywords: spam NaiveBayes C4.5 Decision Tree SVM1 引言 Internet 的問(wèn)世帶來(lái)了電子郵件業(yè)務(wù)的消滅，網(wǎng)絡(luò)技術(shù)的飛速進(jìn)展促進(jìn)了郵件服務(wù)的廣泛普及及富強(qiáng)，電子郵件已經(jīng)成為生活在信息時(shí)代的人們?nèi)粘Ｉ钜粋€(gè)重要部分。電子郵件不僅是一個(gè)信息溝通的重要渠道，而且也是人們信息獵取的重要途徑之一。隨著互聯(lián)網(wǎng)的普及，不僅人們的日常事務(wù)可以通過(guò)電子郵件來(lái)進(jìn)行處理，而且越來(lái)越多正式和重要的信息也通過(guò)電子郵件來(lái)進(jìn)行傳達(dá)和溝通。隨著電子郵件越來(lái)越普及和重要性的持續(xù)增

5、長(zhǎng)，一些商家和不法分子開(kāi)頭利用垃圾郵件這種方式來(lái)進(jìn)行廣告信息的傳播和用戶消費(fèi)行為信息的獵取。依據(jù)無(wú)線服務(wù)機(jī)構(gòu) Wireless Services Corporation 公司供應(yīng)的一份最新調(diào)查顯示，目前美國(guó)移動(dòng)通信市場(chǎng)上全部的電子郵件服務(wù)當(dāng)中，43%的都是垃圾信息，而年前垃圾郵件在電子郵件中的比例為 18%。而在國(guó)內(nèi)，據(jù)有關(guān)部門(mén)統(tǒng)計(jì)，國(guó)內(nèi)的電子郵件用戶，平均每天發(fā)送的短信數(shù)量超過(guò)了3億條。郵件甚至被稱(chēng)為繼報(bào)紙、廣播、電視、網(wǎng)絡(luò)之后的第五媒體。不過(guò)在數(shù)量浩大的電子郵件背后，垃圾郵件的問(wèn)題也愈加嚴(yán)峻。垃圾郵件可以說(shuō)是因特網(wǎng)帶給人類(lèi)最具爭(zhēng)議性的副產(chǎn)品之一，它的泛濫已經(jīng)使整個(gè)因特網(wǎng)不堪重負(fù)，人們不得不

6、花費(fèi)大量時(shí)間來(lái)應(yīng)付郵箱里的垃圾郵件。在這樣的情勢(shì)下，制定切實(shí)可行的反垃圾郵件方案無(wú)疑是Internet的一個(gè)重要課題，而對(duì)于反垃圾郵件技術(shù)的爭(zhēng)辯也稱(chēng)為一個(gè)新的熱點(diǎn)領(lǐng)域。本文依據(jù)現(xiàn)有郵件分類(lèi)的學(xué)問(wèn)，結(jié)合訓(xùn)練數(shù)據(jù)集的特點(diǎn)，選擇合適的分類(lèi)算法，來(lái)實(shí)現(xiàn)對(duì)垃圾郵件的分類(lèi)。2 相關(guān)工作本文垃圾郵件的分類(lèi)工作主要包括以下三個(gè)部分：文本數(shù)據(jù)預(yù)處理，數(shù)據(jù)集特征選擇，分類(lèi)算法的應(yīng)用及結(jié)果分析。2.1文本數(shù)據(jù)預(yù)處理依據(jù)供應(yīng)的訓(xùn)練數(shù)據(jù)集及測(cè)試數(shù)據(jù)集，編寫(xiě)程序，提取數(shù)據(jù)集中全部單詞及對(duì)應(yīng)的頻率，并更改數(shù)據(jù)格式，以矩陣的形式存儲(chǔ)。初步處理過(guò)后的訓(xùn)練數(shù)據(jù)集Pre-train1.csv第一行表示數(shù)據(jù)集中消滅的全部單詞、字母和

7、數(shù)字屬性共1000個(gè)，第2-9001行代表之前的9000條郵件訓(xùn)練數(shù)據(jù)集，對(duì)應(yīng)第一行的單詞，存儲(chǔ)了每個(gè)單詞消滅的頻率。Pre-train1.csv最終一列添加了label標(biāo)簽，表明每一條數(shù)據(jù)的屬性，ham或spam。在Pre-train1.csv的基礎(chǔ)上，我們開(kāi)頭對(duì)數(shù)據(jù)集中的屬性進(jìn)行篩選，去掉統(tǒng)計(jì)出來(lái)的單個(gè)字母，純數(shù)字，以及無(wú)意義詞匯屬性143條，得到最終的數(shù)據(jù)集Pre-train2.csv共包含857個(gè)牢靠單詞屬性，如圖1所示，基于Pre-train2.csv數(shù)據(jù)集，我們進(jìn)行后續(xù)的特征提取。 圖1 數(shù)據(jù)集格式2.2 特征提取2.2.1熵與信息增益熵是信息理論中一個(gè)格外重要的概念，表示任何一種

8、能量在空間中分布的均勻程度，能量分布越均勻，越不確定，熵就越大。Shannon將熵應(yīng)有于信息處理，提出了“信息熵”的概念。信息熵是信息的量化度量，是衡量一個(gè)隨機(jī)變量取值的不確定性程度令 X 為隨機(jī)變量，假如 X 隨機(jī)變量的變化越多，通過(guò)它獵取的信息量就越大，X的信息熵定義為： （2-1）通過(guò)觀看隨機(jī)變量 Y 獲得的關(guān)于隨機(jī)變量 X 的信息熵定義為： （2-2）信息增益是信息熵的差，表示在消退不確定性后獲得的信息量，定義為： （2-3）信息增益是信息論中的一個(gè)重要概念，被廣泛應(yīng)用在機(jī)器學(xué)習(xí)領(lǐng)域。對(duì)分類(lèi)系統(tǒng)來(lái)說(shuō)，計(jì)算信息增益是針對(duì)一個(gè)一個(gè)的特征項(xiàng)而言的，它通過(guò)統(tǒng)計(jì)某一個(gè)特征項(xiàng)t在類(lèi)別C中消滅與否的

9、文檔數(shù)來(lái)計(jì)算特征項(xiàng)t對(duì)類(lèi)別C的信息增益1，定義為考慮消滅前后的信息熵之差，某個(gè)特征項(xiàng)的信息增益值越大，表示其貢獻(xiàn)越大，對(duì)分類(lèi)也越重要。因此，在進(jìn)行特征選擇時(shí)，通常選取信息增益值大的若干個(gè)單詞構(gòu)造文本的特征向量。本文中，訓(xùn)練數(shù)據(jù)集中有857個(gè)屬性，全部參與訓(xùn)練效率過(guò)低，因此需要提取出有代表性的詞匯，故選用信息增益的方式來(lái)從數(shù)據(jù)集中提取特征。將處理過(guò)后的訓(xùn)練數(shù)據(jù)集導(dǎo)入到WEKA軟件中，并在預(yù)處理階段使用AttributeSelection界面中InfoGainAttributeEval來(lái)進(jìn)行信息增益特征提取，同時(shí)，將提取出來(lái)的特征屬性按信息增益由高到低進(jìn)行排列，結(jié)果如圖2所示：圖2 信息增益特征提

10、取結(jié)果依據(jù)特征提取結(jié)果，選擇信息增益排列前400的單詞作為最終的訓(xùn)練集，并生成Pre-train(3).arff數(shù)據(jù)集文件。3 算法試驗(yàn)與分析試驗(yàn)部分接受自主程序設(shè)計(jì)和WEKA數(shù)據(jù)挖掘工具相結(jié)合的方法，利用經(jīng)過(guò)預(yù)處理的訓(xùn)練集，編寫(xiě)MATLAB程序進(jìn)行垃圾郵件分類(lèi)，同時(shí)，利用WEKA軟件中供應(yīng)的多種常用的分類(lèi)算法，進(jìn)行試驗(yàn)。最終對(duì)各種分類(lèi)方法的優(yōu)劣進(jìn)行總結(jié)。3.1樸實(shí)貝葉斯算法樸實(shí)貝葉斯分類(lèi)器2是一種有監(jiān)督的學(xué)習(xí)方法，其假設(shè)屬性的值對(duì)給定類(lèi)的影響而獨(dú)立于其他屬性值。用貝葉斯網(wǎng)表達(dá)樸實(shí)貝葉斯的分類(lèi)器如圖3所示。圖 3 樸實(shí)貝葉斯網(wǎng)樸實(shí)貝葉斯后驗(yàn)概率3的計(jì)算公式如式（3-1） (3-1)其中X表示單

11、詞序列，C表示分類(lèi)。其中的計(jì)算公式如式（3-2） (3-2)則分類(lèi)結(jié)果C的選擇方式為式（3-3） (3-3)試驗(yàn)部分使用兩種方法來(lái)實(shí)現(xiàn)貝葉斯分類(lèi)算法，分別是MATLAB編寫(xiě)程序和WEKA平臺(tái)供應(yīng)的NaiveBayes算法。MATLAB程序中，依據(jù)樸實(shí)貝葉斯公式，使用經(jīng)過(guò)預(yù)處理的4000條數(shù)據(jù)作為訓(xùn)練集，試驗(yàn)結(jié)果如表1所示：表1 基于MATLAB的樸實(shí)貝葉斯試驗(yàn)結(jié)果訓(xùn)練數(shù)量/條訓(xùn)練屬性條錯(cuò)誤率40001500.0970在WEKA件中，使用9000條數(shù)據(jù)，400條屬性作為訓(xùn)練集，在Classify條目下選擇NaiveBayes分類(lèi)算法，并選擇Supplied test set作為訓(xùn)練模型評(píng)價(jià)方法，

12、試驗(yàn)結(jié)果如表2所示：表2 基于weka平臺(tái)的樸實(shí)貝葉斯分類(lèi)算法試驗(yàn)結(jié)果hamspamtotalham16951420spam61519580total23057010003.2 C4.5決策算法C4.5 算法是目前最具影響的決策樹(shù)算法, 已廣泛應(yīng)用于數(shù)據(jù)分類(lèi)領(lǐng)域，C4.5算法是在ID3算法的基礎(chǔ)上改進(jìn)過(guò)來(lái)的，不僅可以處理離散型描述屬性，還可以處理連續(xù)性屬性。C4.5算法接受信息增益率作為選擇分枝屬性的標(biāo)準(zhǔn)，彌補(bǔ)了ID3算法在使用信息增益選擇分枝屬性時(shí)偏向于取值較多的屬性的缺陷。作為 ID3 算法的改進(jìn)算法， C4.5 算法克服了ID3算法的兩大缺點(diǎn)： (1) ID3 算法使用信息增益作為評(píng)價(jià)標(biāo)

13、準(zhǔn)來(lái)選擇根節(jié)點(diǎn)和各內(nèi)部節(jié)點(diǎn)中的分枝屬性，信息增益的缺點(diǎn)是傾向于選擇取值較多的屬性，在某些狀況下這類(lèi)屬性可能不會(huì)供應(yīng)太多有價(jià)值的信息，而C4.5 算法接受信息增益率作為評(píng)價(jià)標(biāo)準(zhǔn)，克服了 ID3算法的這點(diǎn)不足； (2) (2) ID3 算法只能處理描述屬性為離散的數(shù)據(jù)集， 而 C4.5 算法既可以處理離散型描述性，又可以處理連續(xù)型描述屬性。 C4.5 算法也是一種基于信息論的機(jī)器學(xué)習(xí)方法，其核心思想是通過(guò)分析訓(xùn)練數(shù)據(jù)集，在整個(gè)數(shù)據(jù)集上遞歸地建立一個(gè)決策樹(shù)。 使用WEKA數(shù)據(jù)挖掘軟件供應(yīng)的C4.5 算法進(jìn)行分類(lèi)，試驗(yàn)結(jié)果如表3所示表3 C4.5決策樹(shù)算法試驗(yàn)結(jié)果hamspamtotalham4119

14、420spam11569580total42257810003.3支持向量機(jī)算法支持向量機(jī)算法簡(jiǎn)稱(chēng) SVM（Support Vector Machine）算法4，該算法建立在統(tǒng)計(jì)學(xué)習(xí)理論中的 VC 維和結(jié)構(gòu)風(fēng)險(xiǎn)最小化基礎(chǔ)之上，并結(jié)合最優(yōu)化理論來(lái)得到分類(lèi)決策函數(shù)的分類(lèi)算法。其基本思想是查找一個(gè)分類(lèi)超平面，將兩類(lèi)樣本分到超平面的兩側(cè)他在解決非線性問(wèn)題、高維模式識(shí)別問(wèn)題等很多問(wèn)題中顯示出很多優(yōu)勢(shì)，是統(tǒng)計(jì)學(xué)習(xí)理論中比較有用的算法之一，目前已在人臉識(shí)別、手寫(xiě)數(shù)字識(shí)別、文本分類(lèi)5、信息檢索等領(lǐng)域得到成功應(yīng)用。支持向量機(jī)的數(shù)學(xué)模型如式（3-4）和式（3-5），該模型保證在滿足條件下，超平面距離各樣本點(diǎn)距離最

15、大。 （3-4） （3-5）利用WEKA軟件實(shí)現(xiàn)支持矢量機(jī)（SMO）算法的試驗(yàn)結(jié)果如表4所示表 4 支持向量機(jī)算法試驗(yàn)結(jié)果hamspamtotalham40317420spam13567580total41658410003.4試驗(yàn)結(jié)果評(píng)價(jià)與分析3.4.1試驗(yàn)評(píng)價(jià)方法測(cè)試郵件集合中垃圾郵件、非垃圾郵件的數(shù)量分別是Ns、Nh，垃圾郵件中正確分類(lèi)和被錯(cuò)分的郵件數(shù)量分別為Nss、Nsh，非垃圾郵件中被正確分類(lèi)和被錯(cuò)誤分類(lèi)的郵件數(shù)量分別為Nhh、Nhs，則垃圾郵件識(shí)別算法的性能可以依據(jù)以下幾個(gè)指標(biāo)進(jìn)行衡量。（1）垃圾郵件召回率(recall)垃圾郵件樣本集中能被算法正確分類(lèi)的樣本所占比例，記為r，定義

16、如式（3-6) （3-6）可見(jiàn)當(dāng)垃圾郵件召回率反應(yīng)了算法對(duì)垃圾郵件的檢測(cè)力量，該值越大說(shuō)明檢測(cè)力量越強(qiáng)，被遺漏的郵件越少。（2）垃圾郵件識(shí)別精確率(precision)被正確識(shí)別分類(lèi)的郵件數(shù)占全部樣本的比例，記為p，定義如式（3-7) （3-7）精確率反應(yīng)郵件被正確分類(lèi)的概率，精確率越高，說(shuō)明被錯(cuò)誤分類(lèi)的郵件數(shù)量就越少。3.4.2試驗(yàn)結(jié)果分析MATLAB編寫(xiě)程序?qū)崿F(xiàn)的樸實(shí)貝葉斯算法結(jié)果與WEKA平臺(tái)的試驗(yàn)結(jié)果存在肯定的差異，對(duì)比結(jié)果如表5所示表5 基于MATLAB的樸實(shí)貝葉斯試驗(yàn)結(jié)果算法實(shí)現(xiàn)環(huán)境精確率MATLAB0.903WEKA平臺(tái)0.888試驗(yàn)結(jié)果存在差異的緣由在于MATLAB程序僅僅是單

17、純使用樸實(shí)貝葉斯公式來(lái)進(jìn)行結(jié)果計(jì)算，未考慮數(shù)據(jù)集中的噪音等因素，WEKA平臺(tái)的算法包括更進(jìn)一步的預(yù)處理，噪音數(shù)據(jù)去除，以及算法的優(yōu)化，導(dǎo)致試驗(yàn)結(jié)果的精確率低于MATLAB程序結(jié)果?；赪EKA平臺(tái)供應(yīng)的三種分類(lèi)方法，對(duì)比結(jié)果如表6所示表6三種算法分類(lèi)效果對(duì)比精確度召回率執(zhí)行時(shí)間支持向量機(jī)97.0%97.8%8.24sC4.5決策樹(shù)98.0%98.1%4.12s樸實(shí)貝葉斯88.8%89.5%0.87s對(duì)比三種分類(lèi)方法的試驗(yàn)結(jié)果，可以發(fā)覺(jué)樸實(shí)貝葉斯分類(lèi)算法的精確率和召回率最低，C4.5決策樹(shù)的精確率和召回率最高，在執(zhí)行時(shí)間方面，樸實(shí)貝葉斯所需的執(zhí)行時(shí)間最短，支持向量機(jī)的執(zhí)行時(shí)間最長(zhǎng)。4總結(jié)本文介紹

18、了對(duì)數(shù)據(jù)集樣本進(jìn)行預(yù)處理及特征提取的方法，并使用支持向量機(jī)、樸實(shí)貝葉斯、C4.5決策樹(shù)這三種垃圾郵件分類(lèi)方法對(duì)樣本集中垃圾郵件進(jìn)行識(shí)別，對(duì)比分析了它們的分類(lèi)效果，樸實(shí)貝葉斯方法執(zhí)行效率高，但試驗(yàn)精確率不夠抱負(fù)，SVM和決策樹(shù)的試驗(yàn)精確率較高，但執(zhí)行時(shí)間較長(zhǎng)，這三種分類(lèi)算法都有各自的優(yōu)勢(shì)和不足。在進(jìn)行垃圾郵件分類(lèi)的時(shí)候，可以考慮結(jié)合三種方法的優(yōu)點(diǎn)，更快速精確的實(shí)現(xiàn)垃圾郵件識(shí)別。本文在數(shù)據(jù)預(yù)處理階段使用信息增益來(lái)進(jìn)行特征提取，可以考慮使用卡方統(tǒng)計(jì)量的方式來(lái)提取特征，或者兩者相互結(jié)合，得到更加合理的數(shù)據(jù)集特征信息。參考文獻(xiàn)：1 劉慶和，梁正友.一種基于信息增益的特征優(yōu)化選擇方法J. 計(jì)算機(jī)工程與應(yīng)用 2011，47（12）:130-132.2 M. Sahami, S. Dumais, D. Heckerman. Bayesi