国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于Hadoop平臺(tái)的電子郵件分類

2015-01-06 00:26邵葉秦
電腦知識(shí)與技術(shù) 2014年34期
關(guān)鍵詞:垃圾郵件分類

邵葉秦

摘要:為了從大量的電子郵件中檢測(cè)垃圾郵件,提出了一個(gè)基于Hadoop平臺(tái)的電子郵件分類方法。不同于傳統(tǒng)的基于內(nèi)容的垃圾郵件檢測(cè),通過在MapReduce框架上統(tǒng)計(jì)分析郵件收發(fā)記錄,提取郵件賬號(hào)的行為特征。然后使用MapReduce框架并行的實(shí)現(xiàn)隨機(jī)森林分類器,并基于帶有行為特征的樣本訓(xùn)練分類器和分類郵件。實(shí)驗(yàn)結(jié)果表明,基于Hadoop平臺(tái)的電子郵件分類方法大大提高了大規(guī)模電子郵件的分類效率。

關(guān)鍵詞:Hadoop;MapReduce;大規(guī)模;垃圾郵件;分類

中圖分類號(hào):TP311 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2014)34-8119-03

隨著 Internet的迅速發(fā)展,電子郵件已經(jīng)逐漸演變成了一種快捷、經(jīng)濟(jì)、有效的通信方式,并且得到了廣泛使用。然而,作為其副產(chǎn)品的垃圾郵件不斷泛濫,不僅占用網(wǎng)絡(luò)帶寬和服務(wù)器資源,耗費(fèi)用戶的精力和時(shí)間,而且傳播危險(xiǎn)的病毒和散播不實(shí)信息,給運(yùn)營(yíng)商、用戶和社會(huì)都帶來了不良影響,解決垃圾郵件問題已成為人們迫切的要求。

然而郵件數(shù)據(jù)數(shù)量龐大,這使得在單機(jī)上實(shí)施郵件分類往往需要消耗大量的、甚至不可承受的時(shí)間和資源。這啟發(fā)我們使用Hadoop [1]平臺(tái),利用MapReduce [2]計(jì)算模型將算法并行化,從而提高郵件分類的效率。

1 Hadoop技術(shù)

Hadoop是一個(gè)可以處理海量數(shù)據(jù)的分布式開源計(jì)算平臺(tái)。它通過高容錯(cuò)性、高伸縮性的分布式文件系統(tǒng)Hadoop Distributed Filesystem [3]部署在普通的硬件設(shè)備上,通過分布式的MapReduce框架簡(jiǎn)單、快速的開發(fā)運(yùn)行于普通計(jì)算機(jī)上的并行應(yīng)用。

MapReduce[5]主要有Map操作和Reduce操作組成。Map操作負(fù)責(zé)把一個(gè)任務(wù)分解成多個(gè)任務(wù)進(jìn)行處理,Reduce操作負(fù)責(zé)匯總分解后的多個(gè)任務(wù)的處理結(jié)果。Map操作和Reduce操作都可以高度并行的處理。用戶只要根據(jù)具體需求實(shí)現(xiàn)map函數(shù)和reduce函數(shù)。它們的輸入輸出都是以<鍵,值>的形式傳遞。利用MapReduce框架并行處理數(shù)據(jù)的過程如下:

2 基于Hadoop平臺(tái)的垃圾郵件分類

基于Hadoop平臺(tái)的郵件分類主要包括基于Hadoop平臺(tái)的特征提取以及分類。為了準(zhǔn)確分類郵件,需要提取出有效的特征,因此先要在大量的郵件數(shù)據(jù)上利用Hadoop平臺(tái)高效的提取相關(guān)特征。然后基于提取的特征,在大量的訓(xùn)練和測(cè)試樣本,再次利用Hadoop平臺(tái)訓(xùn)練具有并發(fā)特性的隨機(jī)森林分類器,并分類測(cè)試郵件。

2.1 基于Hadoop的特征提取

現(xiàn)有的郵件分類方法大都基于郵件內(nèi)容。由于圖片和動(dòng)畫等偽裝技術(shù)的出現(xiàn),使得越來越多的垃圾郵件逃避基于內(nèi)容的分類過濾方法,因此,研究者們提出基于行為的郵件分類技術(shù)來檢測(cè)垃圾郵件[4-7],取得了很好的結(jié)果。他們通過研究郵件賬號(hào)的行為特征來推測(cè)郵件賬號(hào)是否為垃圾郵件制造者,比如發(fā)送郵件的頻率、收信人數(shù)量、發(fā)送郵件失敗的比例等,進(jìn)而判斷其發(fā)送的是否為垃圾郵件。這種方法不需要掃描郵件的全部?jī)?nèi)容,大大提高郵件分類過濾的速度,也不會(huì)出現(xiàn)侵犯隱私權(quán)的法律風(fēng)險(xiǎn)。

由于基于行為的特征需要統(tǒng)計(jì)分析大量的郵件記錄,為了高效的獲得郵件特征,我們采用Hadoop平臺(tái)。實(shí)現(xiàn)時(shí)我們考慮了38個(gè)行為特征,如郵件賬號(hào)發(fā)送的郵件總數(shù),向各個(gè)接收者發(fā)送的郵件數(shù)量的最大值、最小值、平均值、方差,接受到的郵件數(shù)量,發(fā)件人的郵件地址長(zhǎng)度等,這里重點(diǎn)介紹以下幾個(gè)行為特征:

某個(gè)用戶對(duì)應(yīng)的郵件接受者數(shù)量 代表了收到某用戶主動(dòng)發(fā)送的郵件的接收者數(shù)量。不同于正常用戶,垃圾郵件制造者為了達(dá)到自己的目的,需要向盡量多的人發(fā)送郵件,因此這個(gè)特征一般很大。

平均發(fā)送的郵件數(shù)量 代表了某個(gè)用戶向其它用戶主動(dòng)發(fā)送的平均郵件數(shù)量。這個(gè)值越大,表示他和其他人的通信越頻繁。通常,垃圾郵件制造者發(fā)送的平均郵件數(shù)量基本為1,而正常用戶平均發(fā)送的郵件數(shù)量是一個(gè)隨機(jī)值。

向某用戶發(fā)送郵件的郵件發(fā)送者數(shù)量 代表了向某個(gè)用戶發(fā)送郵件的郵件地址數(shù)量。相比于正常用戶,垃圾郵件制造者發(fā)送的是垃圾信息,基本不會(huì)有人主動(dòng)向其發(fā)送郵件。

回復(fù)比例 代表了某用戶和其他用戶間通信的活躍程度。不同于正常用戶,垃圾郵件制造者發(fā)出去的郵件一般是沒有回復(fù)的,回復(fù)比例的值幾乎為0。

由于這些特征的提取過程類似,下面以某個(gè)用戶對(duì)應(yīng)的郵件接受者數(shù)量特征為例進(jìn)行說明。主要包括以下幾步:

1) 從服務(wù)器上的原始郵件記錄中提取發(fā)送者-接受者列表,作為輸入。這里,發(fā)送者-接受者列表包含一系列的發(fā)送者-接受者記錄,比如,代表發(fā)送者sender1給接收者recv1, 接收者3,…. 發(fā)送了一個(gè)郵件。

2) 使用Map函數(shù)并行的將郵件的發(fā)送者-接受者記錄轉(zhuǎn)換成發(fā)送者和每個(gè)接收者的一對(duì)一發(fā)送關(guān)系。

Map函數(shù)的輸入<鍵,值>對(duì):<缺省的每行偏移量,郵件的發(fā)送者-接受者記錄>。

Map函數(shù)的輸出<鍵,值>對(duì):<發(fā)送者 接收者,1>。

Map函數(shù)的處理過程:將輸入的每條郵件發(fā)送者-接受者記錄切分成發(fā)送者及各個(gè)接收者,然后將發(fā)送者和每個(gè)接收者拼接起來作為輸出的鍵,輸出的值設(shè)為1。

3) 使用Reduce函數(shù)計(jì)算每個(gè)發(fā)送者對(duì)應(yīng)的郵件接收者的個(gè)數(shù)。

Reduce函數(shù)的輸入<鍵,值>對(duì):<發(fā)送者 接收者,List(1,1,…,1)>。

Reduce函數(shù)的輸出<鍵,值>對(duì):<發(fā)送者,對(duì)應(yīng)的郵件接收者數(shù)量>。

Reduce函數(shù)的處理過程:切分輸入記錄的鍵(“發(fā)送者 接收者”),提取發(fā)送者,然后使用一個(gè)全局變量計(jì)數(shù)具有相同發(fā)送者的輸入記錄個(gè)數(shù),就得到當(dāng)前發(fā)送者對(duì)應(yīng)的郵件接收者數(shù)量。

4) 最終輸出每個(gè)發(fā)送者對(duì)應(yīng)的郵件接收者數(shù)量。

2.2 基于Hadoop的郵件分類

針對(duì)大量的垃圾郵件,該文選擇具有很高并行性的隨機(jī)森林(Random Forests)[8]分類器分類郵件。隨機(jī)森林分類器是一種基于分類與回歸決策樹(Classification And Regression Tree,CART)的集成算法。隨機(jī)森林一般包含若干棵決策樹。每棵樹是從獨(dú)立同分布的訓(xùn)練樣本集上訓(xùn)練得到的。預(yù)測(cè)時(shí),不同的測(cè)試樣本可以相互獨(dú)立的由每棵決策樹預(yù)測(cè)結(jié)果,隨機(jī)森林通過組合每棵樹的預(yù)測(cè)給出最終的預(yù)測(cè)結(jié)果。隨機(jī)森林具有分類能力強(qiáng),人工干預(yù)少的特點(diǎn),而且無需預(yù)處理就能有效地處理大規(guī)模的數(shù)據(jù)。由于隨機(jī)森林的每棵決策樹可以獨(dú)立的訓(xùn)練和預(yù)測(cè),因此適合在Hadoop平臺(tái)上分布式處理。

2.2.1 隨機(jī)森林分類器的訓(xùn)練

隨機(jī)森林通過在訓(xùn)練集上多次隨機(jī)的有放回采樣獲得獨(dú)立同分布訓(xùn)練樣本集,用于訓(xùn)練森林中的每棵決策樹。接著通過迭代的將數(shù)據(jù)分配到左右兩個(gè)子集中構(gòu)造一棵決策樹。這是一個(gè)在最大信息增量意義下尋找最佳參數(shù)和閾值的過程。這個(gè)迭代過程一直到預(yù)先設(shè)定的最大樹深度或者到葉子結(jié)點(diǎn)只包含預(yù)先設(shè)定的最少的樣本數(shù)或者到不能通過分裂獲取更大的信息增益為止。由于決策樹是在各自訓(xùn)練樣本上相互獨(dú)立的訓(xùn)練得到的,因此可以在MapReduce框架下按一個(gè)Map函數(shù)訓(xùn)練一棵決策樹的方式并行進(jìn)行。其訓(xùn)練過程如下:

1) 從全體訓(xùn)練樣本中,有放回的采樣n組訓(xùn)練樣本[Xi,i=1,2,…,n],其中,每組訓(xùn)練樣本[Xi]包含[Ni]個(gè)樣本,即[Xi=ei,j,li,j,j=1,2,…,Ni]。每組訓(xùn)練樣本作為一個(gè)輸入分片,用于訓(xùn)練一棵決策樹。

2) 使用Map函數(shù)并行的生成多個(gè)決策樹。

Map函數(shù)的輸入<鍵,值>對(duì):<決策樹的標(biāo)記[Ii],[Xi]>。

Map函數(shù)的輸出<鍵,值>對(duì):<隨機(jī)森林的標(biāo)記,訓(xùn)練好的決策樹[Ti]>。

Map函數(shù)訓(xùn)練決策樹的過程如下:首先所有的樣本都位于根節(jié)點(diǎn)上,然后依據(jù)最優(yōu)的分裂,不斷地將當(dāng)前節(jié)點(diǎn)中的樣本分到左、右兩個(gè)孩子節(jié)點(diǎn)中,一直到?jīng)Q策樹達(dá)到生長(zhǎng)的終止條件。在每個(gè)分裂節(jié)點(diǎn)上,通過窮舉大量隨機(jī)選擇的特征和隨機(jī)生成的閾值,選擇一個(gè)可以使分裂前、后的信息增益最大的特征和對(duì)應(yīng)的閾值組合,將當(dāng)前節(jié)點(diǎn)中的訓(xùn)練樣本分到左、右兩個(gè)孩子節(jié)點(diǎn)中。分裂前后的信息增益如下式所示。

其中,[IGk] 是第[k]節(jié)點(diǎn)分裂的信息增益,[Sk]代表決策樹中的第[k]個(gè)節(jié)點(diǎn),其中存放了這個(gè)節(jié)點(diǎn)上所有訓(xùn)練樣本的類標(biāo),[SLk]和[SRk]是節(jié)點(diǎn)[Sk]的左、右子節(jié)點(diǎn),[H?]表示訓(xùn)練樣本類標(biāo)的信息熵,[pk,m]是節(jié)點(diǎn)[Sk]中第[m]個(gè)類標(biāo)的分布概率,[M]是總的類別數(shù)。該文中,決策樹的每個(gè)葉子結(jié)點(diǎn)存放了落在這個(gè)葉子結(jié)點(diǎn)上的訓(xùn)練樣本的類標(biāo)。

3) 使用Reduce函數(shù)把決策樹聚成隨機(jī)森林

4) 最終輸出訓(xùn)練好的隨機(jī)森林[R]。

2.2.2 利用隨機(jī)森林分類郵件

對(duì)每一個(gè)測(cè)試樣本,利用訓(xùn)練好的隨機(jī)森林中的決策樹,從根節(jié)點(diǎn)開始,或左或右的沿決策樹到達(dá)葉子節(jié)點(diǎn),根據(jù)該葉子節(jié)點(diǎn)中各類訓(xùn)練樣本的類標(biāo)分布給出測(cè)試樣本屬于各類的概率。最后,通過聚合各個(gè)決策樹的結(jié)果得到最終的分類結(jié)果。由于各個(gè)測(cè)試樣本可以相互獨(dú)立的利用各個(gè)決策樹預(yù)測(cè),然后匯總得到最后的分類結(jié)果,因此可以使用MapReduce框架實(shí)現(xiàn)。

1) 所有要分類郵件樣本的標(biāo)識(shí)[IDj]和特征[ej] [j=1,2,…,E],和訓(xùn)練好的隨機(jī)森林[R=T1,T2,…,Tn]作為輸入。

2) 使用Map函數(shù)并行的利用每棵決策樹分類郵件樣本。

Map函數(shù)的輸入<鍵,值>對(duì):<測(cè)試樣本標(biāo)識(shí)[IDj],<測(cè)試樣本特征[ej],決策樹[ Ti]>>,這里,值域保存了另一個(gè)<鍵,值>對(duì)。

Map函數(shù)的輸出<鍵,值>對(duì):<測(cè)試樣本標(biāo)識(shí)[IDj],[Ti]預(yù)測(cè)其屬于各個(gè)類別的概率[ pTi,j]>。

Map函數(shù)的處理過程:利用決策樹[Ti]預(yù)測(cè)測(cè)試樣本[ej]的屬于各個(gè)類別的概率。

3) 使用Reduce函數(shù)聚合每個(gè)郵件樣本的分類結(jié)果。

4) 最終輸出各個(gè)郵件樣本所屬的類別。

3 實(shí)驗(yàn)

本文利用作者單位所用郵件服務(wù)器上2013年12月份第一周收集的真實(shí)郵件數(shù)據(jù)進(jìn)行了實(shí)驗(yàn),并提取了所有的郵件賬號(hào)和相應(yīng)的行為特征。數(shù)據(jù)集中共有119988封郵件,其中正常郵件29023封,垃圾郵件90965封。實(shí)驗(yàn)采用兩重交叉驗(yàn)證,其中一半的郵件(59994封)作為訓(xùn)練樣本,另一半郵件作為測(cè)試樣本。由于郵件數(shù)據(jù)龐大,我們搭建了由11臺(tái)臺(tái)式機(jī)組成的Hadoop平臺(tái),其中一個(gè)master node,10個(gè)data node。每個(gè)節(jié)點(diǎn)配有四核2.90 GHz CPU,16G內(nèi)存和1G的以太網(wǎng)卡。安裝的Hadoop版本1.2.1。隨機(jī)森林中共建了30棵決策樹,每顆決策樹隨機(jī)抽取5000個(gè)訓(xùn)練樣本。

為了驗(yàn)證Hadoop平臺(tái)的有效性,該文實(shí)驗(yàn)比較了在單機(jī)平臺(tái)和Hadoop平臺(tái)上的特征提取和隨機(jī)森林訓(xùn)練和測(cè)試。如表 1和表 2所示,Hadoop平臺(tái)相比于單機(jī)平臺(tái),不論是特征提取還是隨機(jī)森林分類器的訓(xùn)練和測(cè)試,所用時(shí)間都大大減小。由于Hadoop平臺(tái)本身的開銷,因此Hadoop平臺(tái)的加速比率并不是嚴(yán)格的10倍。隨著平臺(tái)節(jié)點(diǎn)的不斷增加,Hadoop平臺(tái)可以展現(xiàn)出更好的效率提升。由于實(shí)驗(yàn)中所用的算法是相同的,因此Hadoop平臺(tái)上的郵件分類的精度(accuracy) 和單機(jī)平臺(tái)一樣,也是99.2%。

4 結(jié)束

本文基于大規(guī)模的郵件數(shù)據(jù),提出了一個(gè)基于Hadoop平臺(tái)的郵件分類方法,對(duì)郵件分類過程中的特征提取和分類器的訓(xùn)練和測(cè)試都使用Hadoop平臺(tái)進(jìn)行了并行加速。首先使用Hadoop平臺(tái)提取郵件賬號(hào)的行為特征,接著基于這些特征,在Hadoop平臺(tái)上訓(xùn)練隨機(jī)森林分類器,并再次利用Hadoop平臺(tái)用訓(xùn)練好的隨機(jī)森林分類大量的郵件樣本。實(shí)驗(yàn)證明,針對(duì)大量的郵件記錄,基于Hadoop平臺(tái)的郵件分類方法不論在特征提取還是在郵件分類方面都能有效的提高算法效率。endprint

參考文獻(xiàn):

[1] Borthakur D.The hadoop distributed file system: Architecture and design [M]. Hadoop Project Website, 2007:11: 21.

[2] Dean J,Ghemawat S0MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.

[3] Shvachko K. The hadoop distributed file system [C]//Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium on. IEEE, 2010.

[4] Naksomboon S C. Charnsripinyo,Wattanapongsakorn N. Considering behavior of sender in spam mail detection [C].Networked Computing (INC), 2010 6th International Conference on. IEEE, 2010.

[5] Ramachandran A,F(xiàn)eamster N. Understanding the network-level behavior of spammers [C].ACM SIGCOMM Computer Communication Review. ACM, 2006.

[6] Wang M F. Social feature-based enterprise email classification without examining email contents [J]. Journal of Network and Computer Applications, 2012,35(2): 770-777.

[7] Zamil M F. A behavior based algorithm to detect Spam bots [C]//Collaborative Technologies and Systems (CTS), 2010 International Symposium on. IEEE,2010.

[8] Breiman L. Random forests [J]. Machine learning, 2001. 45(1): 5-32.endprint

參考文獻(xiàn):

[1] Borthakur D.The hadoop distributed file system: Architecture and design [M]. Hadoop Project Website, 2007:11: 21.

[2] Dean J,Ghemawat S0MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.

[3] Shvachko K. The hadoop distributed file system [C]//Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium on. IEEE, 2010.

[4] Naksomboon S C. Charnsripinyo,Wattanapongsakorn N. Considering behavior of sender in spam mail detection [C].Networked Computing (INC), 2010 6th International Conference on. IEEE, 2010.

[5] Ramachandran A,F(xiàn)eamster N. Understanding the network-level behavior of spammers [C].ACM SIGCOMM Computer Communication Review. ACM, 2006.

[6] Wang M F. Social feature-based enterprise email classification without examining email contents [J]. Journal of Network and Computer Applications, 2012,35(2): 770-777.

[7] Zamil M F. A behavior based algorithm to detect Spam bots [C]//Collaborative Technologies and Systems (CTS), 2010 International Symposium on. IEEE,2010.

[8] Breiman L. Random forests [J]. Machine learning, 2001. 45(1): 5-32.endprint

參考文獻(xiàn):

[1] Borthakur D.The hadoop distributed file system: Architecture and design [M]. Hadoop Project Website, 2007:11: 21.

[2] Dean J,Ghemawat S0MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.

[3] Shvachko K. The hadoop distributed file system [C]//Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium on. IEEE, 2010.

[4] Naksomboon S C. Charnsripinyo,Wattanapongsakorn N. Considering behavior of sender in spam mail detection [C].Networked Computing (INC), 2010 6th International Conference on. IEEE, 2010.

[5] Ramachandran A,F(xiàn)eamster N. Understanding the network-level behavior of spammers [C].ACM SIGCOMM Computer Communication Review. ACM, 2006.

[6] Wang M F. Social feature-based enterprise email classification without examining email contents [J]. Journal of Network and Computer Applications, 2012,35(2): 770-777.

[7] Zamil M F. A behavior based algorithm to detect Spam bots [C]//Collaborative Technologies and Systems (CTS), 2010 International Symposium on. IEEE,2010.

[8] Breiman L. Random forests [J]. Machine learning, 2001. 45(1): 5-32.endprint

猜你喜歡
垃圾郵件分類
從“scientist(科學(xué)家)”到“spam(垃圾郵件)”,英語單詞的起源出人意料地有趣 精讀
分類算一算
一種基于SMOTE和隨機(jī)森林的垃圾郵件檢測(cè)算法
分類討論求坐標(biāo)
數(shù)據(jù)分析中的分類討論
基于支持向量機(jī)與人工免疫系統(tǒng)的垃圾郵件過濾模型
基于貝葉斯算法的垃圾郵件過濾器的模擬實(shí)現(xiàn)