基于Hadoop平台的电子邮件分类

邵叶秦

摘要：为了从大量的电子邮件中检测垃圾邮件，提出了一个基于Hadoop平台的电子邮件分类方法。不同于传统的基于内容的垃圾邮件检测，通过在MapReduce框架上统计分析邮件收发记录，提取邮件账号的行为特征。然后使用MapReduce框架并行的实现随机森林分类器，并基于带有行为特征的样本训练分类器和分类邮件。实验结果表明，基于Hadoop平台的电子邮件分类方法大大提高了大规模电子邮件的分类效率。

关键词：Hadoop；MapReduce；大规模；垃圾邮件；分类

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8119-03

随着 Internet的迅速发展，电子邮件已经逐渐演变成了一种快捷、经济、有效的通信方式，并且得到了广泛使用。然而，作为其副产品的垃圾邮件不断泛滥，不仅占用网络带宽和服务器资源，耗费用户的精力和时间，而且传播危险的病毒和散播不实信息，给运营商、用户和社会都带来了不良影响，解决垃圾邮件问题已成为人们迫切的要求。

然而邮件数据数量庞大，这使得在单机上实施邮件分类往往需要消耗大量的、甚至不可承受的时间和资源。这启发我们使用Hadoop [1]平台，利用MapReduce [2]计算模型将算法并行化，从而提高邮件分类的效率。

1 Hadoop技术

Hadoop是一个可以处理海量数据的分布式开源计算平台。它通过高容错性、高伸缩性的分布式文件系统Hadoop Distributed Filesystem [3]部署在普通的硬件设备上，通过分布式的MapReduce框架简单、快速的开发运行于普通计算机上的并行应用。

MapReduce[5]主要有Map操作和Reduce操作组成。Map操作负责把一个任务分解成多个任务进行处理，Reduce操作负责汇总分解后的多个任务的处理结果。Map操作和Reduce操作都可以高度并行的处理。用户只要根据具体需求实现map函数和reduce函数。它们的输入输出都是以<键，值>的形式传递。利用MapReduce框架并行处理数据的过程如下：

2 基于Hadoop平台的垃圾邮件分类

基于Hadoop平台的邮件分类主要包括基于Hadoop平台的特征提取以及分类。为了准确分类邮件，需要提取出有效的特征，因此先要在大量的邮件数据上利用Hadoop平台高效的提取相关特征。然后基于提取的特征，在大量的训练和测试样本，再次利用Hadoop平台训练具有并发特性的随机森林分类器，并分类测试邮件。

2.1 基于Hadoop的特征提取

现有的邮件分类方法大都基于邮件内容。由于图片和动画等伪装技术的出现，使得越来越多的垃圾邮件逃避基于内容的分类过滤方法，因此，研究者们提出基于行为的邮件分类技术来检测垃圾邮件[4-7]，取得了很好的结果。他们通过研究邮件账号的行为特征来推测邮件账号是否为垃圾邮件制造者，比如发送邮件的频率、收信人数量、发送邮件失败的比例等，进而判断其发送的是否为垃圾邮件。这种方法不需要扫描邮件的全部内容，大大提高邮件分类过滤的速度，也不会出现侵犯隐私权的法律风险。

由于基于行为的特征需要统计分析大量的邮件记录，为了高效的获得邮件特征，我们采用Hadoop平台。实现时我们考虑了38个行为特征，如邮件账号发送的邮件总数，向各个接收者发送的邮件数量的最大值、最小值、平均值、方差，接受到的邮件数量，发件人的邮件地址长度等，这里重点介绍以下几个行为特征：

某个用户对应的邮件接受者数量 代表了收到某用户主动发送的邮件的接收者数量。不同于正常用户，垃圾邮件制造者为了达到自己的目的，需要向尽量多的人发送邮件，因此这个特征一般很大。

平均发送的邮件数量 代表了某个用户向其它用户主动发送的平均邮件数量。这个值越大，表示他和其他人的通信越频繁。通常，垃圾邮件制造者发送的平均邮件数量基本为1，而正常用户平均发送的邮件数量是一个随机值。

向某用户发送邮件的邮件发送者数量 代表了向某个用户发送邮件的邮件地址数量。相比于正常用户，垃圾邮件制造者发送的是垃圾信息，基本不会有人主动向其发送邮件。

回复比例 代表了某用户和其他用户间通信的活跃程度。不同于正常用户，垃圾邮件制造者发出去的邮件一般是没有回复的，回复比例的值几乎为0。

由于这些特征的提取过程类似，下面以某个用户对应的邮件接受者数量特征为例进行说明。主要包括以下几步：

1） 从服务器上的原始邮件记录中提取发送者-接受者列表，作为输入。这里，发送者-接受者列表包含一系列的发送者-接受者记录，比如，代表发送者sender1给接收者recv1， 接收者3，…. 发送了一个邮件。

2） 使用Map函数并行的将邮件的发送者-接受者记录转换成发送者和每个接收者的一对一发送关系。

Map函数的输入<键，值>对：<缺省的每行偏移量，邮件的发送者-接受者记录>。

Map函数的输出<键，值>对：<发送者 接收者，1>。

Map函数的处理过程：将输入的每条邮件发送者-接受者记录切分成发送者及各个接收者，然后将发送者和每个接收者拼接起来作为输出的键，输出的值设为1。

3） 使用Reduce函数计算每个发送者对应的邮件接收者的个数。

Reduce函数的输入<键，值>对：<发送者 接收者，List（1，1，…，1）>。

Reduce函数的输出<键，值>对：<发送者，对应的邮件接收者数量>。

Reduce函数的处理过程：切分输入记录的键（“发送者 接收者”），提取发送者，然后使用一个全局变量计数具有相同发送者的输入记录个数，就得到当前发送者对应的邮件接收者数量。

4） 最终输出每个发送者对应的邮件接收者数量。

2.2 基于Hadoop的邮件分类

针对大量的垃圾邮件，该文选择具有很高并行性的随机森林（Random Forests）[8]分类器分类邮件。随机森林分类器是一种基于分类与回归决策树（Classification And Regression Tree，CART）的集成算法。随机森林一般包含若干棵决策树。每棵树是从独立同分布的训练样本集上训练得到的。预测时，不同的测试样本可以相互独立的由每棵决策树预测结果，随机森林通过组合每棵树的预测给出最终的预测结果。随机森林具有分类能力强，人工干预少的特点，而且无需预处理就能有效地处理大规模的数据。由于随机森林的每棵决策树可以独立的训练和预测，因此适合在Hadoop平台上分布式处理。

2.2.1 随机森林分类器的训练

随机森林通过在训练集上多次随机的有放回采样获得独立同分布训练样本集，用于训练森林中的每棵决策树。接着通过迭代的将数据分配到左右两个子集中构造一棵决策树。这是一个在最大信息增量意义下寻找最佳参数和阈值的过程。这个迭代过程一直到预先设定的最大树深度或者到叶子结点只包含预先设定的最少的样本数或者到不能通过分裂获取更大的信息增益为止。由于决策树是在各自训练样本上相互独立的训练得到的，因此可以在MapReduce框架下按一个Map函数训练一棵决策树的方式并行进行。其训练过程如下：

1） 从全体训练样本中，有放回的采样n组训练样本[Xi，i=1，2，…，n]，其中，每组训练样本[Xi]包含[Ni]个样本，即[Xi=ei，j，li，j，j=1，2，…，Ni]。每组训练样本作为一个输入分片，用于训练一棵决策树。

2） 使用Map函数并行的生成多个决策树。

Map函数的输入<键，值>对：<决策树的标记[Ii]，[Xi]>。

Map函数的输出<键，值>对：<随机森林的标记，训练好的决策树[Ti]>。

Map函数训练决策树的过程如下：首先所有的样本都位于根节点上，然后依据最优的分裂，不断地将当前节点中的样本分到左、右两个孩子节点中，一直到决策树达到生长的终止条件。在每个分裂节点上，通过穷举大量随机选择的特征和随机生成的阈值，选择一个可以使分裂前、后的信息增益最大的特征和对应的阈值组合，将当前节点中的训练样本分到左、右两个孩子节点中。分裂前后的信息增益如下式所示。

其中，[IGk] 是第[k]节点分裂的信息增益，[Sk]代表决策树中的第[k]个节点，其中存放了这个节点上所有训练样本的类标，[SLk]和[SRk]是节点[Sk]的左、右子节点，[H?]表示训练样本类标的信息熵，[pk，m]是节点[Sk]中第[m]个类标的分布概率，[M]是总的类别数。该文中，决策树的每个叶子结点存放了落在这个叶子结点上的训练样本的类标。

3） 使用Reduce函数把决策树聚成随机森林

4） 最终输出训练好的随机森林[R]。

2.2.2 利用随机森林分类邮件

对每一个测试样本，利用训练好的随机森林中的决策树，从根节点开始，或左或右的沿决策树到达叶子节点，根据该叶子节点中各类训练样本的类标分布给出测试样本属于各类的概率。最后，通过聚合各个决策树的结果得到最终的分类结果。由于各个测试样本可以相互独立的利用各个决策树预测，然后汇总得到最后的分类结果，因此可以使用MapReduce框架实现。

1） 所有要分类邮件样本的标识[IDj]和特征[ej] [j=1，2，…，E]，和训练好的随机森林[R=T1，T2，…，Tn]作为输入。

2） 使用Map函数并行的利用每棵决策树分类邮件样本。

Map函数的输入<键，值>对：<测试样本标识[IDj]，<测试样本特征[ej]，决策树[ Ti]>>，这里，值域保存了另一个<键，值>对。

Map函数的输出<键，值>对：<测试样本标识[IDj]，[Ti]预测其属于各个类别的概率[ pTi，j]>。

Map函数的处理过程：利用决策树[Ti]预测测试样本[ej]的属于各个类别的概率。

3） 使用Reduce函数聚合每个邮件样本的分类结果。

4） 最终输出各个邮件样本所属的类别。

3 实验

本文利用作者单位所用邮件服务器上2013年12月份第一周收集的真实邮件数据进行了实验，并提取了所有的邮件账号和相应的行为特征。数据集中共有119988封邮件，其中正常邮件29023封，垃圾邮件90965封。实验采用两重交叉验证，其中一半的邮件（59994封）作为训练样本，另一半邮件作为测试样本。由于邮件数据庞大，我们搭建了由11台台式机组成的Hadoop平台，其中一个master node，10个data node。每个节点配有四核2.90 GHz CPU，16G内存和1G的以太网卡。安装的Hadoop版本1.2.1。随机森林中共建了30棵决策树，每颗决策树随机抽取5000个训练样本。

为了验证Hadoop平台的有效性，该文实验比较了在单机平台和Hadoop平台上的特征提取和随机森林训练和测试。如表 1和表 2所示，Hadoop平台相比于单机平台，不论是特征提取还是随机森林分类器的训练和测试，所用时间都大大减小。由于Hadoop平台本身的开销，因此Hadoop平台的加速比率并不是严格的10倍。随着平台节点的不断增加，Hadoop平台可以展现出更好的效率提升。由于实验中所用的算法是相同的，因此Hadoop平台上的邮件分类的精度（accuracy） 和单机平台一样，也是99.2%。

4 结束

本文基于大规模的邮件数据，提出了一个基于Hadoop平台的邮件分类方法，对邮件分类过程中的特征提取和分类器的训练和测试都使用Hadoop平台进行了并行加速。首先使用Hadoop平台提取邮件账号的行为特征，接着基于这些特征，在Hadoop平台上训练随机森林分类器，并再次利用Hadoop平台用训练好的随机森林分类大量的邮件样本。实验证明，针对大量的邮件记录，基于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，Feamster 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，Feamster 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，Feamster 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