Hadoop平臺下垃圾郵件過濾技術(shù)研究*

李 毅，劉廣鐘

（上海海事大學 信息工程學院，上海 201306）

0 引言

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

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

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

1 研究基礎(chǔ)介紹

1.1 貝葉斯定理

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

P（A）通常稱為先驗概率，而條件概率 P（A|B）稱為后驗概率。

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

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

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

圖1 MapReduce流重組方法流程

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

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

（1）Map 階段： 對每個＜k1，v1＞鍵值對進行處理，從報文內(nèi)容中提取出每條報文的五元組信息，得到＜k2，v2＞，其中k2為報文的五元組信息，v2是從IP層開始的整個報文。

（2）Combine階段：Combine相當于對每個 DataNode結(jié)點上的數(shù)據(jù)流進行流重組，此時以Map階段的輸出作為Combine階段的輸入。之后通過指針從報文信息中提取每條報文的 SYN、FIN、TCP 中的序號。以＜k3，v3＞作為輸出，k3為每條報文的五元組信息，v3為每條報文的數(shù)組。

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

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

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

2 Hadoop平臺下貝葉斯垃圾郵件過濾

2.1 改進的貝葉斯垃圾郵件過濾算法

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

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

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

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

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

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

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

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

隨著 Q 的增加，P（x）會增大，R（x）會降低；反之，隨著 Q 變小，P（x）會降低，R（x）會增大，因此可以求出使F值達到極值的 Q。記 SN為數(shù)列{pi}的前 N項和，因為0＜T（x）＜1，0＜P（x）＜1，0＜R（x）＜1，因此，0＜F（x）＜1。 對于待分類郵件來說，N 和 SN均為常數(shù)。 對 F（x）、T（x）求導可得式（15）、式（16），令 F′（x）=0，則可得式（17）。

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

Hadoop平臺下的垃圾郵件過濾技術(shù)的MapReduce模型分為兩階段：郵件訓練樣本階段和郵件分類階段。

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

圖2 郵件訓練階段MapReduce流程圖

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

圖3 郵件分類階段MapReduce流程圖

3 相關(guān)實驗

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

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

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

表1 Hadoop集群具體硬件配置信息

3.2 實驗評價指標

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

3.3 實驗結(jié)果及分析

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

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

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

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

表2 過濾系統(tǒng)性能比較

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

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

圖4 隨著DataNode數(shù)量變化與單機比較的加速比

4 結(jié)束語

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

[1]中國互聯(lián)網(wǎng)絡信息中心.第35次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告[R/OL].（2015-02-03）[2015-05-02].http：//www.cnnic.net.cn/hlwfzyj/hlwmrtj/.

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

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

[4]李國元，李雙慶，楊錚.一種流序列化的網(wǎng)絡流量分類算法[J].電子技術(shù)應用，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]李文斌，陳嶷瑛，劉椿年，等.郵件過濾算法的比較[J].計算機工程與設(shè)計，2008，29（17）：4433-4436.