基于Hadoop平臺的電子郵件分類

邵葉秦

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

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

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）34-8119-03

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

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

1 Hadoop技術(shù)

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

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

2 基于Hadoop平臺的垃圾郵件分類

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

2.1 基于Hadoop的特征提取

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

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

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

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

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

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

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

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

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

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

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

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

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

Reduce函數(shù)的輸入<鍵，值>對：<發(fā)送者 接收者，List（1，1，…，1）>。

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

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

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

2.2 基于Hadoop的郵件分類

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

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

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

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

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

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

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

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

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

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

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

2.2.2 利用隨機森林分類郵件

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

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

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

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

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

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

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

4） 最終輸出各個郵件樣本所屬的類別。

3 實驗

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

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

4 結(jié)束

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

參考文獻：

[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

參考文獻：

[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

參考文獻：

[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