摘  要： 傳統(tǒng)的貝葉斯垃圾郵件過(guò)濾系統(tǒng)雖然具有較高的分類(lèi)準(zhǔn)確性，但是在處理郵件時(shí)存在效率低、消耗資源量大的問(wèn)題。本文針對(duì)貝葉斯垃圾郵件過(guò)濾算法進(jìn)行了在Hadoop MapReduce下的研究，并對(duì)判定類(lèi)別的閾值進(jìn)行了優(yōu)化，實(shí)驗(yàn)表明，本文提出的算法降低了正常郵件的誤判率，提高了垃圾郵件判定的準(zhǔn)確率和F值，同時(shí)提高了垃圾郵件過(guò)濾的效率。

　　關(guān)鍵詞： Hadoop；垃圾郵件；貝葉斯；MapReduce

0 引言

　　電子郵件作為網(wǎng)絡(luò)最基本的服務(wù)，已成為人們生活中不可或缺的一部分。截止2014年12月，中國(guó)網(wǎng)民規(guī)模達(dá)到6.49億，電子郵件用戶(hù)規(guī)模3.9億，占網(wǎng)民總數(shù)的60.1%[1]。在其中充斥著的海量垃圾郵件給人們的生活帶來(lái)了困擾，如何處理海量垃圾郵件已經(jīng)成為亟待解決的重要問(wèn)題。

　　在目前存在的垃圾郵件過(guò)濾技術(shù)中，以過(guò)濾垃圾郵件時(shí)使用的過(guò)濾方法作為分類(lèi)點(diǎn)，可將這些垃圾郵件過(guò)濾技術(shù)分為以下三種：基于黑白名單的過(guò)濾技術(shù)[2]、基于規(guī)則的過(guò)濾技術(shù)[3]、基于內(nèi)容統(tǒng)計(jì)的過(guò)濾技術(shù)。其中，貝葉斯垃圾郵件過(guò)濾技術(shù)分類(lèi)能力和準(zhǔn)確性較高，但其前期需要對(duì)訓(xùn)練樣本進(jìn)行大量的訓(xùn)練學(xué)習(xí)，對(duì)訓(xùn)練樣本依賴(lài)性較強(qiáng)。海量垃圾郵件的出現(xiàn)使得傳統(tǒng)的方法無(wú)法滿(mǎn)足需要，隨著云計(jì)算Hadoop的出現(xiàn)和發(fā)展，Hadoop MapReduce模型為海量垃圾郵件的過(guò)濾提供了新思路。

　　針對(duì)傳統(tǒng)貝葉斯垃圾郵件過(guò)濾算法的缺點(diǎn)，本文對(duì)貝葉斯垃圾郵件過(guò)濾算法與MapReduce編程模型的結(jié)合進(jìn)行了研究，提出了垃圾郵件過(guò)濾的數(shù)學(xué)模型，并在此基礎(chǔ)上對(duì)判定郵件所屬類(lèi)別的決策分類(lèi)方法給出了一定的改進(jìn)。

1 研究基礎(chǔ)介紹

　　1.1 貝葉斯定理

　　貝葉斯定理由條件概率和全概率組成，主要用于在已知事件A發(fā)生的條件下，判斷A是伴隨著{B1，B2，…，Br}中哪個(gè)事件發(fā)生。E是隨機(jī)試驗(yàn)，對(duì)于E的每一次事件A發(fā)生的概率，記為P（A）。設(shè)A，B為兩個(gè)事件，且P（A）>0。如果兩個(gè)事件A和B不是相互獨(dú)立的，并且已知事件B中的一個(gè)事件已經(jīng)發(fā)生，則能得到關(guān)于P（A）的信息。這反映為A在B中的條件概率，其計(jì)算公式如式（1）所示：

　　P（A）通常稱(chēng)為先驗(yàn)概率，而條件概率P（A|B）稱(chēng)為后驗(yàn)概率。

　　對(duì)于一個(gè)統(tǒng)計(jì)實(shí)驗(yàn)，樣本空間S是所有可能結(jié)果的集合，并且{B1，B2，…，Br}是S的一個(gè)劃分。令{p（A）；AS}表示定義在S中所有事件的一個(gè)概率分布。式（2）為貝葉斯定理的表示：

　　1.2 Hadoop平臺(tái)下郵件流提取和流重組的實(shí)現(xiàn)

　　電子郵件流重組就是對(duì)所有五元組中端口為25和110的TCP流進(jìn)行重組。通過(guò)對(duì)TCP流序列號(hào)的排序重組即可以重組出原郵件流。在建立TCP連接的三次握手時(shí)，發(fā)送方和接收方會(huì)相互發(fā)送TCP頭部中的握手報(bào)文（即SYN報(bào)文，其中SYN=1），而在結(jié)束時(shí)會(huì)互相發(fā)送TCP頭部中FIN報(bào)文（即FIN報(bào)文）。通過(guò)獲取以上兩種報(bào)文，可以容易地通過(guò)FIN報(bào)文與SYN報(bào)文的seq差值與FIN報(bào)文大小的和，求出本條TCP流的長(zhǎng)度。用來(lái)區(qū)別不同的TCP流的標(biāo)志為五元組[4]（即源IP、源端口號(hào)、目的IP、目的端口號(hào)、傳輸層協(xié)議），其能夠?qū)Σ煌腡CP會(huì)話(huà)進(jìn)行區(qū)分。Hadoop平臺(tái)下流提取重組的MapReduce[5]過(guò)程如圖1所示。

　　完成完整的郵件流重組必須從該五元組對(duì)應(yīng)的流中獲取帶有SYN=1與FIN=1（或RST）的報(bào)文。當(dāng)TCP出現(xiàn)亂序或者重傳覆蓋時(shí)，對(duì)這些流按照seq進(jìn)行重新排序。對(duì)于不完整的TCP流進(jìn)行丟棄處理。

　　HDFS進(jìn)行大規(guī)模流量文件的分割，InputFormat將輸入的大規(guī)模報(bào)文文件分割為若干InputSplit，每一個(gè)InputSplit將單獨(dú)作為Map的輸入。每條流形成一個(gè)鍵值對(duì)<k1，v1>，此處k1表示報(bào)文在文件中的偏移量，v1表示整條報(bào)文內(nèi)容。

　?。?）Map階段：對(duì)每個(gè)<k1，v1>鍵值對(duì)進(jìn)行處理，從報(bào)文內(nèi)容中提取出每條報(bào)文的五元組信息，得到<k2，v2>，其中k2為報(bào)文的五元組信息，v2是從IP層開(kāi)始的整個(gè)報(bào)文。

　?。?）Combine階段：Combine相當(dāng)于對(duì)每個(gè)DataNode結(jié)點(diǎn)上的數(shù)據(jù)流進(jìn)行流重組，此時(shí)以Map階段的輸出作為Combine階段的輸入。之后通過(guò)指針從報(bào)文信息中提取每條報(bào)文的SYN、FIN、TCP中的序號(hào)。以<k3，v3>作為輸出，k3為每條報(bào)文的五元組信息，v3為每條報(bào)文的數(shù)組。

　?。?）Shuffle階段：在Shuffle階段輸入為<k3，v3>輸出為<k4，v4>，完成局部的流重組整合，也就是對(duì)在Combine階段未完成的流重組過(guò)程繼續(xù)完成，這樣可以有效減少在Reduce的計(jì)算壓力。

　?。?）Reduce階段：接收到Shuffle的輸出后，對(duì)每個(gè)鍵值對(duì)進(jìn)行處理，完成在Combine階段和Shuffle階段未完成的流重組過(guò)程。如果經(jīng)過(guò)以上階段，發(fā)現(xiàn)有的流重組出來(lái)是不完整的，則將這條流丟棄。

　　Reduce階段完成后，將Reduce處理好的流交給OutputFormat（即MyOutputFormat）類(lèi)。它將重組好的報(bào)文寫(xiě)入文件中。按照以上流程即可完成POP3和SMTP郵件的相關(guān)流重組。

2 Hadoop平臺(tái)下貝葉斯垃圾郵件過(guò)濾

　　2.1 改進(jìn)的貝葉斯垃圾郵件過(guò)濾算法

　　貝葉斯方法包括兩個(gè)步驟：訓(xùn)練樣本和分類(lèi)，其實(shí)質(zhì)是把郵件判定為垃圾郵件或者正常郵件。假設(shè)郵件的特征詞集合為d，且d中的各特征詞之間相互獨(dú)立，則構(gòu)建過(guò)濾器的過(guò)程如下。

　　首先收集大量的垃圾郵件和正常郵件，并將其分為垃圾郵件集和正常郵件集兩組。之后對(duì)過(guò)濾器進(jìn)行訓(xùn)練。假定在訓(xùn)練集中，垃圾郵件有S封，正常郵件有H封，垃圾郵件有n個(gè)特征詞{w1，w2，…，wn}。在模型建立時(shí)，假設(shè)垃圾郵件有2個(gè)特征詞，即d={w1，w2}，則當(dāng)特征詞出現(xiàn)時(shí)，該封郵件屬于垃圾郵件的概率為P（Spam|w1），而屬于正常郵件的概率為P（Ham|w1）；當(dāng)特征詞w2出現(xiàn)時(shí)，該郵件屬于垃圾郵件的概率為P（Spam|w2），而屬于正常郵件的概率為P（Ham|w2）。則根據(jù)貝葉斯定理有如下推論：

　　P（Spam|d）=P（Spam|w1）P（Spam|w2）P（Spam）（3）

　　P（Ham|d）=（1-P（Spam|w1））（1-P（Spam|w2））（1-P（Spam））（4）

　　在郵件的特征詞w1，w2出現(xiàn)的情況下，令P（Spam|w1）=p1，P（Spam|w2）=p2，則郵件屬于垃圾郵件的概率如式（5）所示：

　　若d={w1，w2，…，wn}，則可以進(jìn)行如下處理：將訓(xùn)練集中的S封垃圾郵件進(jìn)行訓(xùn)練，查看垃圾郵件中是否存在這些特征詞，假設(shè)d={w1，w2，…，wn}對(duì)應(yīng)出現(xiàn)的數(shù)量為{f1，f2，…，fn}。則此時(shí)，郵件屬于垃圾郵件類(lèi)概率為：

　　其中，。設(shè)定當(dāng)上式≥Q時(shí)，判定郵件屬于垃圾郵件Spam類(lèi)，結(jié)合參考文獻(xiàn)[6]的經(jīng)驗(yàn)，可將閾值設(shè)置為0.9。

　　在一般情況下，假設(shè)待分類(lèi)郵件di計(jì)算出的PSpam值為pi，其中1≤i≤N，N為待分類(lèi)的郵件總數(shù)。此處假設(shè)pi是有序遞增的，即存在pi≤pj，其中1≤i≤j≤N。假設(shè)閾值為Q，存在x，1≤x<N，使得px<Q，而px+1≥Q，則可判定，前x封郵件歸為正常郵件Ham類(lèi)，后N-x封郵件歸為Spam類(lèi)。

　　下文對(duì)閾值的設(shè)定進(jìn)行改進(jìn)，在系統(tǒng)判定為正常郵件的前面x封郵件中，錯(cuò)誤判定類(lèi)別的郵件數(shù)量和正確判定類(lèi)別的郵件數(shù)量的期望分別如式（7）、式（8）所示：

　　在判定為垃圾郵件的后面N-x封郵件中正確判定類(lèi)別和錯(cuò)誤判定類(lèi)別的期望如式（9）、式（10）所示：

　　使用上述期望可求出垃圾郵件過(guò)濾系統(tǒng)的四個(gè)指標(biāo)[7]，如式（11）~式（14）所示：

　　隨著Q的增加，P（x）會(huì)增大，R（x）會(huì)降低；反之，隨著Q變小，P（x）會(huì)降低，R（x）會(huì)增大，因此可以求出使F值達(dá)到極值的Q。記SN為數(shù)列{pi}的前N項(xiàng)和，因?yàn)?<T（x）<1，0<P（x）<1，0<R（x）<1，因此，0<F（x）<1。對(duì)于待分類(lèi)郵件來(lái)說(shuō)，N和SN均為常數(shù)。對(duì)F（x）、T（x）求導(dǎo)可得式（15）、式（16），令F′（x）=0，則可得式（17）。

　　所以，當(dāng)時(shí)，F(xiàn)（x）為x的嚴(yán)格單調(diào)增函數(shù)；反之，為單調(diào)減函數(shù)。由于數(shù)列{pi}有序遞增，所以唯一存在一個(gè)x使當(dāng)時(shí)，F(xiàn)（x）可以達(dá)到極大值。求出x后，就可以確定正常郵件與垃圾郵件的分界點(diǎn)，可以有效改善Hadoop平臺(tái)下的垃圾郵件過(guò)濾方法，在一定程度上提高郵件判定的F值和過(guò)濾的性能。

　　2.2 垃圾郵件過(guò)濾技術(shù)的MapReduce模型

　　Hadoop平臺(tái)下的垃圾郵件過(guò)濾技術(shù)的MapReduce模型分為兩階段：郵件訓(xùn)練樣本階段和郵件分類(lèi)階段。

　　郵件訓(xùn)練階段的MapReduce過(guò)程如圖2所示。第一個(gè)MapRecue階段抽取垃圾郵件的特征，MapReduce輸入為已經(jīng)分好類(lèi)的垃圾郵件集合，通過(guò)Map和Reduce得出垃圾郵件特征詞詞頻。第二個(gè)MapReduce過(guò)程計(jì)算正常郵件類(lèi)別的特征詞詞頻，以分類(lèi)的正常郵件集作為MapReduce的輸入，輸出為每封郵件對(duì)應(yīng)的正常郵件特征詞的詞頻。第三個(gè)MapReduce作業(yè)計(jì)算出垃圾郵件特征詞的條件概率，以前面兩個(gè)MapReduce作業(yè)的輸出作為輸入，通過(guò)MapReduce得出每個(gè)類(lèi)別的特征詞相應(yīng)的聯(lián)合條件概率。結(jié)合垃圾郵件和正常郵件類(lèi)別的先驗(yàn)概率，形成n個(gè)特征詞的郵件訓(xùn)練庫(kù)。

　　郵件分類(lèi)階段的MapReduce過(guò)程如圖3所示?？偣卜譃閮蓚€(gè)過(guò)程，第一個(gè)MapReduce過(guò)程計(jì)算待過(guò)濾郵件的特征詞詞匯及其詞頻，輸入為待過(guò)濾郵件集合，通過(guò)Map和Reduce得出特征詞的詞頻。此過(guò)程與訓(xùn)練階段的第一個(gè)MapReduce過(guò)程類(lèi)似。第二個(gè)MapReduce過(guò)程接收第一個(gè)MapReduce過(guò)程生成的中間數(shù)據(jù)及郵件訓(xùn)練結(jié)果集，通過(guò)MapReduce計(jì)算出每個(gè)待分類(lèi)郵件屬于垃圾郵件的概率，并且與閾值Q比較，判斷郵件所屬的類(lèi)別。

3 相關(guān)實(shí)驗(yàn)

　　3.1 實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)環(huán)境

　　為保證實(shí)驗(yàn)內(nèi)容的真實(shí)性，本文采用上海海事大學(xué)信息工程學(xué)院出口網(wǎng)關(guān)上截獲的40 258封郵件作為本次實(shí)驗(yàn)的數(shù)據(jù)集，其中包含垃圾郵件20 132封，正常郵件20 126封，為了保證實(shí)驗(yàn)的可靠性和平均分配，首先將垃圾郵件隨機(jī)剔除32封，正常郵件隨機(jī)剔除26封。選取其中5 100封垃圾郵件、5 100封正常郵件作為訓(xùn)練集，將另外的30 000封郵件作為測(cè)試集。將測(cè)試集中的郵件平均分為10份，對(duì)每份測(cè)試集進(jìn)行實(shí)驗(yàn)，以10次實(shí)驗(yàn)的平均值作為實(shí)驗(yàn)結(jié)果進(jìn)行分析。

　　Hadoop集群具體硬件配置信息如表1所示。

　　3.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

　　在對(duì)垃圾郵件過(guò)濾實(shí)驗(yàn)進(jìn)行評(píng)判時(shí)，用召回率（Recall）、查準(zhǔn)率（Precision）、正確率（T）、F值四個(gè)實(shí)驗(yàn)性能評(píng)價(jià)指標(biāo)[7]來(lái)衡量本文提出的垃圾郵件過(guò)濾技術(shù)的性能。召回率為垃圾郵件過(guò)濾系統(tǒng)識(shí)別出的垃圾郵件數(shù)量占實(shí)際垃圾郵件數(shù)量的比例；查準(zhǔn)率為實(shí)際為垃圾郵件總數(shù)占過(guò)濾系統(tǒng)判別出的垃圾郵件數(shù)量的比例；正確率為垃圾郵件過(guò)濾系統(tǒng)正確歸類(lèi)的郵件數(shù)量占所有待分類(lèi)郵件數(shù)量的比例；F值為垃圾郵件查準(zhǔn)率和召回率的調(diào)和平均，它將查準(zhǔn)率和召回率綜合成為一個(gè)新的判定指標(biāo)。

　　3.3 實(shí)驗(yàn)結(jié)果及分析

　　實(shí)驗(yàn)1采用傳統(tǒng)的貝葉斯垃圾郵件過(guò)濾算法，既未引入Hadoop MapReduce模型，也未進(jìn)行優(yōu)化算法，垃圾郵件的概率閾值Q=0.9。

　　實(shí)驗(yàn)2中引入了本文設(shè)計(jì)的MapReduce模型和算法，使用Hadoop集群，但未對(duì)算法做優(yōu)化處理，垃圾郵件概率閾值取Q=0.9。

　　實(shí)驗(yàn)3中引入了本文設(shè)計(jì)的MapReduce模型，使用Hadoop集群，并改進(jìn)了郵件分類(lèi)時(shí)的概率閾值。垃圾郵件分類(lèi)時(shí)的概率閾值根據(jù)算法進(jìn)行設(shè)定。

　　結(jié)合三種實(shí)驗(yàn)情況，可得出召回率、查準(zhǔn)率、F值和正確率如表2所示。

　　根據(jù)上表可以發(fā)現(xiàn)，改進(jìn)后的Hadoop平臺(tái)下的垃圾郵件過(guò)濾系統(tǒng)在召回率、F值和正確率方面均有所提升，查準(zhǔn)率略有下降，垃圾郵件過(guò)濾系統(tǒng)的整體性能得到了提升。可以得出結(jié)論，改進(jìn)后的模型較原來(lái)的模型在性能上有了一定的提高。

　　本文針對(duì)實(shí)驗(yàn)3，分析了不同DataNode數(shù)量下基于Hadoop平臺(tái)的垃圾郵件過(guò)濾系統(tǒng)較單機(jī)環(huán)境下貝葉斯垃圾郵件過(guò)濾系統(tǒng)的加速比，實(shí)驗(yàn)數(shù)據(jù)如圖4所示。通過(guò)分析發(fā)現(xiàn)，與單機(jī)下的貝葉斯垃圾郵件過(guò)濾算法相比，基于Hadoop平臺(tái)的貝葉斯垃圾郵件過(guò)濾技術(shù)隨著DataNode數(shù)量的增加，加速比處于線性上升狀態(tài)。

4 結(jié)束語(yǔ)

　　本文針對(duì)海量垃圾郵件的過(guò)濾做出研究，在分析了傳統(tǒng)的貝葉斯垃圾郵件過(guò)濾算法的缺點(diǎn)后，將貝葉斯垃圾郵件過(guò)濾算法與Hadoop MapReduce編程模型結(jié)合起來(lái)，提出了垃圾郵件過(guò)濾的數(shù)學(xué)模型，并在此基礎(chǔ)上對(duì)判定郵件所屬類(lèi)別的閾值選擇給出了一定的改進(jìn)。本文提出的垃圾郵件過(guò)濾算法在垃圾郵件過(guò)濾評(píng)價(jià)指標(biāo)上較單機(jī)環(huán)境下和改進(jìn)前都有所提升，將算法在Hadoop集群中運(yùn)行，得到了較好的加速比。

參考文獻(xiàn)

　　[1] 中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心.第35次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[R/OL].（2015-02-03）[2015-05-02].http：//www.cnnic.net.cn/hlwfzyj/hlwmrtj/.

　　[2] 徐洪偉，方勇，音春.垃圾郵件過(guò)濾技術(shù)分析[J].通信技術(shù)，2003（10）：126-128.

　　[3] 向旭宇，姬林，楊岳湘.電子郵件系統(tǒng)過(guò)濾技術(shù)研究及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2003，20（S1）：136-137.

　　[4] 李國(guó)元，李雙慶，楊錚.一種流序列化的網(wǎng)絡(luò)流量分類(lèi)算法[J].電子技術(shù)應(yīng)用，2009，35（6）：121-127.

　　[5] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[J]. Communications of the ACM， 2008，51（1）：107-113.

　　[6] Zhan Chuan， Lu Xianliang， Zhou Xu， et al. An improved Bayesian with application to anti-spam Email[J]. Journal of Eelctronic Science and Technology of China， 2005，3（1）：30-33.

　　[7] 李文斌，陳嶷瑛，劉椿年，等.郵件過(guò)濾算法的比較[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（17）：4433-4436.