種 飛，徐 野，張自圃

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110159)

Hadoop平臺(tái)垃圾郵件過(guò)濾算法研究

種 飛，徐 野，張自圃

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110159)

傳統(tǒng)分布式大型郵件系統(tǒng)對(duì)海量數(shù)據(jù)的處理雖然具有比較高的準(zhǔn)確性，但是具有效率低、程序復(fù)雜、占用資源多等缺點(diǎn)，因此，需要在傳統(tǒng)過(guò)濾技術(shù)的基礎(chǔ)上進(jìn)行優(yōu)化。采用Hadoop平臺(tái)貝葉斯過(guò)濾算法的Mapreduce框架，對(duì)系統(tǒng)配置進(jìn)行優(yōu)化，能夠得到比較全面的知識(shí)庫(kù)，不僅提高了郵件過(guò)濾階段的可靠性，還使實(shí)驗(yàn)性能評(píng)價(jià)指標(biāo)有了很大的提升。

Hadoop；Mapreduce；垃圾郵件；貝葉斯過(guò)濾算法

隨著Intenet的迅速發(fā)展，電子郵件技術(shù)使通過(guò)互聯(lián)網(wǎng)來(lái)進(jìn)行郵件信息交換成了現(xiàn)實(shí)，電子郵件憑借其快速便捷、成本低廉、易于保存等特點(diǎn)得到了人們的認(rèn)可，并迅速成為當(dāng)今交流的主要方式之一。然而，隨之而來(lái)的副產(chǎn)品也就是垃圾郵件也漸漸地影響到人們生活，例如：傳播病毒，發(fā)送廣告和不良信息，嚴(yán)重時(shí)甚至?xí)绊懯褂谜叩纳踩詰?yīng)該加強(qiáng)對(duì)垃圾郵件進(jìn)行處理。

在傳統(tǒng)的垃圾郵件過(guò)濾技術(shù)中，主要采用基于黑白名單技術(shù)[1]，基于規(guī)則的過(guò)濾技術(shù)[2]，基于內(nèi)容統(tǒng)計(jì)的過(guò)濾技術(shù)。在傳統(tǒng)的過(guò)濾技術(shù)中，都呈現(xiàn)出一些缺點(diǎn)，比如：準(zhǔn)確率低、處理數(shù)據(jù)慢、成本高、操作復(fù)雜等。貝葉斯算法[3]在內(nèi)容統(tǒng)計(jì)過(guò)濾技術(shù)中得到了很好的運(yùn)用，它對(duì)文本具有很強(qiáng)的分類能力且準(zhǔn)確率高，不過(guò)這種技術(shù)前期要進(jìn)行大量的訓(xùn)練，之后得出知識(shí)庫(kù)，其對(duì)訓(xùn)練樣本的依賴性太強(qiáng)，故面對(duì)海量的郵件文本具有一定缺陷。

考慮到傳統(tǒng)垃圾郵件過(guò)濾技術(shù)的缺陷，本文提出在Hadoop平臺(tái)上對(duì)過(guò)濾算法的應(yīng)用，并作適當(dāng)?shù)母倪M(jìn)，又采用分布式的Mapreduce編程模型，這樣不僅可以對(duì)海量數(shù)據(jù)分布式處理，還有效提高了系統(tǒng)對(duì)垃圾郵件的執(zhí)行效率。

1 過(guò)濾技術(shù)介紹

1.1 貝葉斯定理

概率論中的貝葉斯定理(Bayes＇theorem)[3]是一個(gè)學(xué)習(xí)定理，貝葉斯定理基礎(chǔ)是基于條件概率分布和邊緣概率分布。

設(shè)S是隨機(jī)事件，E是它的樣本空間。則隨機(jī)事件S中某一事件A發(fā)生，記為P(A)，稱為事件A發(fā)生的概率。

條件概率公式：設(shè)A、B是兩個(gè)事件，且P(A)>0，則稱

(1)

是在A發(fā)生基礎(chǔ)上B發(fā)生的條件概率。

=P(B1)P(A/B1)+P(B2)P(A/B2)+…+P(Bn)P(A/Bn)

(2)

貝葉斯公式(Bayes formula)：設(shè)試驗(yàn)S的樣本空間為E，A為S的事件，B1,B2,…,Bn為E的一個(gè)劃分，且P(Ai)>0，P(Bi)>0(i=1,2,…,n)，則

(3)

1.2 Hadoop云計(jì)算

云計(jì)算是網(wǎng)絡(luò)計(jì)算、分布式計(jì)算、并行計(jì)算等傳統(tǒng)計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)發(fā)展融合的產(chǎn)物，也是效用計(jì)算、虛擬化、硬件即服務(wù)(HaaS)、軟件即服務(wù)(SaaS)、平臺(tái)即服務(wù)(PaaS)等概念結(jié)合創(chuàng)新的結(jié)果。Hadoop三大核心設(shè)計(jì)Mapreduce、HDFS和HBase，分別是Google云計(jì)算核心技術(shù)Mapreduce、GFS和Bigtable的開(kāi)源實(shí)現(xiàn)。

Mapreduce模型[4]是一種在集群上能夠進(jìn)行分布式并行處理海量數(shù)據(jù)的模型，是一種可用于數(shù)據(jù)處理的編程模型，該模型結(jié)構(gòu)簡(jiǎn)單，Mapreduce程序本質(zhì)上是并行運(yùn)行的，可以將大規(guī)模的數(shù)據(jù)分析任務(wù)分發(fā)給任何一個(gè)擁有足夠多機(jī)器的數(shù)據(jù)中心，其優(yōu)勢(shì)在于處理大規(guī)模數(shù)據(jù)集[5]。Mapreduce的工作原理大致可分為Map階段和Reduce階段，兩個(gè)階段在處理數(shù)據(jù)時(shí)都以鍵值對(duì)進(jìn)行，其輸出和輸入的類型相同。Mapreduce作業(yè)(job)包括輸入數(shù)據(jù)、Mapreduce程序和配置信息。系統(tǒng)把作業(yè)處理為許多任務(wù)并由Map和Reduce來(lái)完成。在執(zhí)行任務(wù)時(shí)主要由一個(gè)Jobtracker和一系列Tasktracker節(jié)點(diǎn)進(jìn)行。Jobtracker負(fù)責(zé)對(duì)任務(wù)的管理，Tasktracker 負(fù)責(zé)處理任務(wù)，Jobtracker與Tasktracker之間的通信和任務(wù)分配通過(guò)心跳機(jī)制實(shí)現(xiàn)，Tasktracker會(huì)主動(dòng)定期向Jobtracker發(fā)送心態(tài)信息，詢問(wèn)是否有任務(wù)要做，果有，就會(huì)申請(qǐng)到任務(wù)。Tasktracker拿到任務(wù)，會(huì)將所有信息拷貝到本地。如果某個(gè)Tasktracker節(jié)點(diǎn)壞掉，這時(shí)Jobtracker會(huì)調(diào)用另一個(gè)Tasktracker節(jié)點(diǎn)繼續(xù)執(zhí)行任務(wù)，原理如圖1所示。當(dāng)Map階段輸出鍵值對(duì)流入到Reduce階段的過(guò)程中，要經(jīng)過(guò)Shuffle(混洗)，這樣不僅降低了Reduce階段的工作量，還有利于數(shù)據(jù)的處理。

圖1 Hadoop平臺(tái)Mapreduce的工作原理

2 樸素貝葉斯算法的應(yīng)用

2.1 樸素貝葉斯算法

樸素貝葉斯算法是目前公認(rèn)的一種簡(jiǎn)單而有效的概率分類方法[6]，是通過(guò)假設(shè)各元素之間相互獨(dú)立而得到的一種簡(jiǎn)化算法。

樸素貝葉斯分類器對(duì)文本分類具有準(zhǔn)確率高、易操作等優(yōu)點(diǎn)，其工作原理是算出文本dx屬于Di類的概率。當(dāng)計(jì)算P(Di/dx)時(shí)，利用了貝葉斯公式：

(4)

其中，根據(jù)全概率公式，有

(5)

Di類的先驗(yàn)概率為

(6)

由以上算法可知，判定一個(gè)事件的類別，只要得出它的概率即可。假設(shè)文本d有特征字符串wj(j=1,2,…,n)為某一事件，并且wj出現(xiàn)是相對(duì)獨(dú)立的。設(shè)定P(wj/Di)表示特征項(xiàng)wj在事件Di中的條件概率，既文本d是Di類的概率，P(Di)表示Di類的先驗(yàn)概率，有

(7)

分詞結(jié)果如圖2所示。

圖2 樸素貝葉斯分類器分詞

設(shè)郵件分為：正常郵件類Ham和垃圾郵件類Spam。首先對(duì)待訓(xùn)練樣本分類，分為垃圾郵件(Spam)和正常郵件(Ham)兩大類，再對(duì)郵件集合中的所有郵件進(jìn)行讀取掃描并提取特征字符串w1、w2、…、wn，統(tǒng)計(jì)每個(gè)字符串出現(xiàn)的次數(shù)f1、f2、…、fn。假設(shè)特征字符串w1、w2、…、wn之間互不影響，由以上算法得，一封郵件d是垃圾郵件的概率為

(8)

郵件d是正常郵件的概率，如下公式：

(9)

其中P(d)的計(jì)算公式如下

=P(Spam)×P(d/Spam)+P(Ham)×P(d/Ham)

(wi/Ham)

(10)

式中n是指特征詞的總數(shù)。

P(wi/Spam)=

(11)

P(wi/Ham)=

(12)

由式(8)和式(9)之比得到如下公式：

(13)

由公式(13)知，中間值P(d)可以不用計(jì)算，這不僅減少了計(jì)算量，還提高了運(yùn)算效率。取閥值M，若K≥M，則可判定該郵件d為垃圾郵件，否則歸為正常郵件。閥值越大，則判定結(jié)果越精確。

2.2 MapReduce模型的樸素貝葉斯算法實(shí)現(xiàn)

系統(tǒng)將輸入的文件分割為許多分片split，經(jīng)過(guò)處理后形成鍵值對(duì)(k1,v1)，此鍵值對(duì)輸入Map，由Map階段進(jìn)行處理輸出另一中間結(jié)果(k2,v2)，之后系統(tǒng)將此鍵值對(duì)經(jīng)過(guò)shuffle階段的處理再次生成一個(gè)鍵值對(duì)(k2,{v2i,…})，最終進(jìn)入Mapreduce模型的最后階段，鍵值對(duì)(k2,{v2i,…})經(jīng)Reduce處理得到鍵值對(duì)(k3,v3)，流程圖如圖3所示。

垃圾郵件過(guò)濾系統(tǒng)分為訓(xùn)練部分和過(guò)濾部分。訓(xùn)練階段有3個(gè)Mapreduce處理過(guò)程如圖4所示，首先對(duì)待訓(xùn)練郵件集進(jìn)行預(yù)處理，得到正常郵件集和垃圾郵件集；其次由訓(xùn)練部分的前兩個(gè)Mapreduce對(duì)預(yù)處理結(jié)果進(jìn)行特征詞提取和詞頻的計(jì)算，由第三個(gè)Mapreduce計(jì)算出垃圾郵件特征詞的條件概率；最后得出郵件的知識(shí)庫(kù)。過(guò)濾階段和訓(xùn)練階段類似，同樣用Mapreduce模型來(lái)過(guò)濾垃圾郵件，只是比訓(xùn)練階段少一個(gè)Mapreduce過(guò)程，一個(gè)Mapreduce用來(lái)對(duì)待過(guò)濾郵件進(jìn)行同樣預(yù)處理，把預(yù)處理數(shù)據(jù)和知識(shí)庫(kù)同時(shí)導(dǎo)入另一Mapreduce(即樸素貝葉斯過(guò)濾模塊)進(jìn)行過(guò)濾，最后得出的結(jié)果就是合法郵件和垃圾郵件。

圖3 Mapreduce工作流程

圖4 待訓(xùn)練郵件集訓(xùn)練過(guò)程

這里取正常郵件和垃圾郵件各50封，訓(xùn)練集和測(cè)試集如圖5所示，具體分類細(xì)節(jié)如圖6所示。

圖5 訓(xùn)練和測(cè)試結(jié)果

圖6 郵件分類明細(xì)

3 結(jié)果分析

本文在開(kāi)源的Hadoop平臺(tái)上進(jìn)行實(shí)驗(yàn)，由于實(shí)驗(yàn)環(huán)境有限，采用偽分布式方式搭建6個(gè)節(jié)點(diǎn)構(gòu)成集群，其中1個(gè)主節(jié)點(diǎn)，5個(gè)從節(jié)點(diǎn)。CPU型號(hào)為Inter(R)Core(TM) i5-2410M CPU @ 2.30GHz 2.30 GHz，8.0GB內(nèi)存，操作系統(tǒng)為CentOS64位，Hadoop版本為2.2.0，jdk-7u51-linux-x64版本的jdk。

采用的樣本來(lái)自于個(gè)人收集的郵件，包含有廣告、公司內(nèi)部及私人郵件等共64620封，其中垃圾郵件42854封、合法郵件21766封。

為了更好地測(cè)試算法的性能，要從垃圾郵件和正常郵件中取出一定數(shù)量的郵件，以保證數(shù)據(jù)的合理性，故取54封垃圾郵件和66封正常郵件。從郵件類別集合中分別取出7000封郵件進(jìn)行訓(xùn)練，余下50500封郵件進(jìn)行測(cè)試。在測(cè)試之前，把要進(jìn)行測(cè)試的郵件集分為5等份，在相同的條件下進(jìn)行實(shí)驗(yàn)，最后取平均值。在對(duì)垃圾郵件過(guò)濾實(shí)驗(yàn)進(jìn)行判斷時(shí)，用召回率(R)、查準(zhǔn)率(I)、判對(duì)率(T)和F值四個(gè)實(shí)驗(yàn)性能評(píng)價(jià)指標(biāo)[7]來(lái)衡量過(guò)濾算法的性能。召回率為系統(tǒng)判定正確的垃圾郵件與實(shí)際的垃圾郵件之比，召回率越高表示漏掉的垃圾郵件越少。查準(zhǔn)率為系統(tǒng)判定正確的垃圾郵件與系統(tǒng)判定的垃圾郵件之比，查準(zhǔn)率越高表示系統(tǒng)誤判的合法郵件越少。判對(duì)率為所有系統(tǒng)判定類別正確的郵件與所有系統(tǒng)判定的郵件之比，其反映正確歸類郵件的能力。F值為垃圾郵件查準(zhǔn)率和召回率的綜合運(yùn)用，即為2IR/(I+R)。

在不同的實(shí)驗(yàn)中，令閥值為0.8，分別在傳統(tǒng)郵件過(guò)濾算法和Hadoop平臺(tái)樸素貝葉斯算法的兩種情況下進(jìn)行實(shí)驗(yàn)，得出結(jié)果并進(jìn)行比較，如表1所示。改變閥值再重復(fù)測(cè)試，對(duì)比測(cè)試效果。

表1 傳統(tǒng)過(guò)濾算法和Mapreduce模型過(guò)濾算法對(duì)比

由測(cè)試數(shù)據(jù)可知，在閥值一定的前提下，Mapreduce模型樸素貝葉斯算法的各個(gè)性能指標(biāo)都要優(yōu)于傳統(tǒng)分布式貝葉斯算法。將樸素貝葉斯算法運(yùn)用到Hadoop平臺(tái)上，實(shí)現(xiàn)對(duì)垃圾郵件的分布式處理，使得對(duì)處理海量垃圾郵件的效率和準(zhǔn)確性都有了顯著提升。圖7為DataNode數(shù)量與加速比的關(guān)系圖。

圖7 DataNode數(shù)量與加速比的關(guān)系圖

由圖7可知，隨著DataNode節(jié)點(diǎn)數(shù)量的增加，其加速比也隨之升高，即相比傳統(tǒng)的貝葉斯過(guò)濾算法，改進(jìn)后的過(guò)濾系統(tǒng)在處理時(shí)間上明顯減少。

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

傳統(tǒng)的垃圾郵件過(guò)濾算法，在面對(duì)海量數(shù)據(jù)時(shí)會(huì)出現(xiàn)處理效率低、資源浪費(fèi)大、運(yùn)行成本高等缺點(diǎn)。但將此算法過(guò)度到Hadoop平臺(tái)下實(shí)現(xiàn)，能夠運(yùn)用廉價(jià)的PC構(gòu)建龐大的集群實(shí)現(xiàn)性能高的數(shù)據(jù)處理平臺(tái)，提高了郵件過(guò)濾平臺(tái)的性價(jià)比，面對(duì)海量郵件也能發(fā)揮其良好的處理能力。由實(shí)驗(yàn)可得，運(yùn)用在Hadoop平臺(tái)的樸素貝葉斯算法遠(yuǎn)優(yōu)于傳統(tǒng)的垃圾郵件過(guò)濾算法，該算法在Mapreduce模型上能夠很好的執(zhí)行，進(jìn)一步提高了處理海量數(shù)據(jù)的性能。

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

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

[3] Seigo Michaela A.In vivo assessment of retinal neuronal layers in multiple sclerosis with manual and automated optical coherence tomography segmentation techniques[J].Journal of Neurology,2012,259(10):2119-2130.

[4] White T.Hadoop 權(quán)威指南[M].周敏奇譯.北京:清華大學(xué)出版社,2011.

[5] 懷特.Hadoop權(quán)威指南[M](第三版).華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院譯.北京:清華大學(xué)出版社,2015.

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

ResearchonSpamFilteringAlgorithmofHadoopPlatform

CHONG Fei,XU Ye,ZHANG Zipu

(Shenyang Ligong University,Shenyang 110159,China)

Traditional distributed large-scale mail system deals with the massive data.Although it has relatively high accuracy,but it has low efficiency,complex proceduce and other drawbacks.Therefore,it needs to be optimized by traditional filtering technology.Hadoop platform Bayesian filter algorithm Mapreduce framework is adopted to optimize system configuration and could get a more comprehensive knowledge base,which improves nots only the reliability of the mail filter phase,but also experimental performance of evalution index.

Hadoop;Mapreduce;spam;Bayesian filtering algorithm

2017-01-08

種飛(1987—),男，碩士研究生；通訊作者：徐野(1976—)，男，教授，博士，研究方向：無(wú)線網(wǎng)絡(luò)信息處理技術(shù)等。

1003-1251(2017)06-0042-05

TP393

A

馬金發(fā))