第卷增刊系统工程理论与实践，年月—文章编号： 中图分类号： 文献标志码：基于社会计算和机器学习的垃圾邮件快速过滤徐雅斌李卓， 董源北京信息科技大学计算机学院， 北京北京信息科技大学网络文化与数字传播北京市重点实验室，北京摘要在对当前垃圾邮件过滤方法进行研究和分析的基础上， 本文将社交网络的概念用于垃圾邮件识别， 并提出了一种将社会计算和机器学习相结合的垃圾邮件过滤方法， 以减少垃圾邮件的误判率为了提高邮件过滤的实时性， 我们利用平台所提供的模型进行分布式并行处理对比实验结果表明， 我们所采用的识别方法的识别准确率和识别效率都有较大的提高， 尤其是降低了正常邮件的误判率关键词社会计算； 泣圾邮件过滤； 云计算’，’，引言电子邮件服务诞生以来，一直在网络交流沟通中扮演着重要的角色但是它包含大量推销广告或不良信息甚至是木马病毒的垃圾邮件日益泛滥严重影响了人们的通信感受垃圾邮件不仅使用户花费大量的时间和精力来处理， 还占用了大量的服务器空间和带宽资源， 并且存在诸多的安全问题因此， 研究垃圾邮件过滤问题具有非常重要的意义当前采用的反垃圾邮件技术主要分为基于规则的过滤方法和基于概率的过滤方法基于规则的过滤方法主要有决策树算法、粗粮集方法基于概率的过滤方法主要有方法、支持向量机（简称， 贝叶斯过滤方法等在基于规则的过滤方法中决策树方法效果一般， 它本身并不直接用于垃圾邮件过滤而是作为一种弱学习器来使用； 粗糙集方法针对小规模的垃圾邮件样本实验有较好的效果但在大规模数据中的表现不如其他方法在基于概率的过滤方法中方法在值较小的情况下性能较好， 但是由于其分类速度的局限性， 不太适用于对分类速度要求较高的垃圾邮件过滤场合； 方法是通过构造最优线性分类收稿日期资助项目： 国家自然科学基金网络文化与数字传播北京市重点实验室资助项目（作者简介徐雅斌（ ， 男， 汉辽宁锦州人教授， 研究方向： 社交网络， 云计算与物联网， 李卓男， 汉， 河南安阳人， 讲师， 博士， 研究方向： 无线网络， 董源（， 男， 汉， 河北邢台人， 硕士研究生， 研究方向： 社交网络，1 8 0 系统工程理论与实践第卷面来指导分类， 虽然在二元问题上有很好的效果， 但是在面对大量数据的时候， 同样也体现出了分类速度上的缺陷； 贝叶斯分类算法在垃圾邮件过滤这种二元分类问题上有较好的表现， 但是其前期需要对邮件进行大量的学习进而得出知识库， 需要浪费大量的系统资源和时间但是以上各种方法都不可避免地会将一部分正常邮件误判为垃圾邮件， 这样就会丢失一些非常重要的邮件可能会产生严重的后果和影响因此， 很多邮件系统对垃圾邮件的过滤慎之又慎， 甚至有些邮件系统不敢进行垃圾邮件的过滤通过研究发现， 现有的垃圾邮件过滤系统模型通常忽略了邮件发送者与接收者之间的社会关系对邮件的分类问题来说， 两位联系人之间的社会关系包含了一些对分类有用的信息这些社会关系可以从邮件头部信息中提取出来， 通过历史上的收发邮件数据， 构造出社交网络结构图％ 对于发往某个邮件服务器的每封邮件来说， 都要对该图进行检索， 如果在图中存在一条发送者和接收者之间的路径说明这两个人在社交网络的概念上是认识的， 那么这二个人之间的往来邮件就应当被认为是正常邮件， 从而减少正常邮件的误判率％对于垃圾邮件过滤， 采用单一方法进行过滤的效果通常很一般， 为了提高垃圾邮件过滤的精度， 必须采用多方法共同协作进行过滤， 才能最大限度地提高邮件过滤的准确率另外， 邮件服务器需要对大批量的邮件进行过滤， 所以最大限度地提高邮件过滤效率也是必须的鉴此， 本文提出了一种在云计算平台下将贝叶斯方法和社会计算方法相结合的垃圾邮件过滤机制垃圾件快速过滤的基本思想事先通过分析历史往来邮件头部信息首先构造一个社交网络结构图对于待识别邮件， 在进行邮件预处理及黑名单过滤后， 如果其联系人在所构造的社交网络结构图中存在且边的权值比较大， 那么证明待识别邮件的联系人之间有很多来往， 于是就直接予以放行； 反之， 证明联系人是新进入的， 就送入基于机器学习的垃圾邮件过滤器进行过滤这样就可以大大减少垃圾邮件的误判率但是这样一来， 就要降低垃圾邮件过滤的实时性为了提高垃圾邮件过滤的效率， 同时考虑到大量数据中心正在采用云计算环境， 云计算越来越普遍， 甚至开源云计算平台巳经被广泛应用， 因此我们对于以上三个过程均基于开源云计算平台的架构进行并行处理， 以缩短垃圾邮件的过滤时间， 提高垃圾邮件过滤的效率和实时性垃圾邮件过滤的总体设计思想如图所示更新社交网络结构图〖邮件预处理及黑白名单匹配一“—“社交网络结构图检“朴素贝叶斯过滤器丨… …丨丨丨…滤」！ ！由？ 二奴— — 虹…一件； ；」垃圾件未分类邮件集正常件未分类邮件集垃圾邮件正常邮件—图垃圾邮件过滤的总体结构图中将垃圾邮件过滤分为三个阶段进行：邮件预处理及黑名单匹配邮件预处理过程包括对每封邮件提取邮件头部中联系人相关信息以及对邮件体进行文本处理重点是黑名单过滤， 我们采用中国反垃圾邮件联盟公布的黑名单， 对待过滤邮件进行初次过滤， 且将未被判定为垃圾邮件的剩余邮件集送入到下一阶段进行过滤基于社交网络结构图的检索此处基于社交网络概念对邮件进行第二次过滤， 对联系人双方存在社交关系的邮件， 在此步中被判定为正常邮件， 从而减少正常邮件的误判率对没有被判定为正常邮件的剩余邮件集送入下一阶段过滤利用朴素贝叶斯过滤器过滤此处对上两个阶段未成功识别的邮件采用朴素贝叶斯过滤器进行过滤，最后将识别出来的正常邮件的社交关系提取出来， 更新到第二阶段采用的社交网络结构图中为了快速地进行垃圾邮件的识别， 每个邮件过滤阶段均采用分布式并行编程模型进行设计增刊徐雅斌， 等： 基于社会计算和机器学习的垃圾邮件快速过滤由件预处理及黑名单过滤一封完整的邮件包含众多的信息， 但是这些信息并不是我们都需要的所以在进行实验之前要对邮件集中的邮件进行预处理预处理主要有以下三点提取邮件头部中联系人信息： 邮件头中含有大量对研究有用的信息， 例如： 发送方地址， 接收方地址， 添加的抄送等， 这些数据与构建社交网络结构图相关需要进行提取， 将其他无用信息去除对邮件体进行中文分词本文主要针对中文邮件进行垃圾邮件识别中文邮件中使用的词语没有明显的界限， 需要单独进行处理本文采用中科院计算所开发的分词系统对网页中的数据进行分词处理去除停用词对分词处理后得到的结果与停用词库中的词进行匹配如果存在便去除结果为巳经去除停用词的词语集合对预处理完的邮件集首先进行黑名单检索过滤为保证黑名单的可信度， 本文中采用的黑名单是中国反垃圾邮件联盟（ 公布的黑名单对发送方邮箱处于黑名单中的邮件将其判定为垃圾邮件； 反之， 对没有处在黑名单中的邮件将其送入下一阶段进行过滤为加快黑名单检索过滤的效率， 采用分布式编程模式设计黑名单检索程序基于社会计算的垃圾邮件识别社交网络结构图的构建联系人双方通过邮件进行联系的时候， 对于联系人双方可见的是邮件的主体内容， 通常就是我们所说的邮件体但是邮件在传递过程中， 还存在用户不可见的一部分内容， 这就是邮件头在邮件头中不仅记录了联系人双方的邮箱信息还包括抄送、密送、转发、回复等重要信息利用这些历史信息就可以构建一幅联系人之间的社交网络结构图定义邮件联系人社交网络结构图图是一个有向赋权图其中， 是图中节点的集合， 表示电子邮件的发件人或收件人是图中有向边的集合， 访是有序对， 方向是叫指向巧是图中边的权重集合， 用于表示叫向巧发出的邮件数任意两个节点的表明讲， 之间存在通信联系在明确了图的定义以及关系之后， 开始进行图的构造， 对图中边的定义如公式⑴ 所示：—’，公式中， 表示图的邻接矩阵， 表示从发送邮件节点到接收节点巧的有向边权值反之表示从发送节点巧到接收叫的有向边权值表示一种分割符没有特殊意义按此定义构建的较小规模的社交网络结构图如图所示图小规模社交网络结构图图展示出部分社交网络结构图， 从图中可以看出边缘处某些节点有很多的直连节点， 这证明这些节点可能是垃圾邮件的发件源而中间部分的节点组成的网络图很有可能是联系人之间正常邮件的往来路径社交网络结构图的检索算法根据上文给出的社交网络结构图的定义， 利用邮件头中包含的信息， 我们可以得出邮件集中联系人之间的社交网络结构图利用社交网络结构图， 我们可以对邮件集进行第二阶段的识别当邮件中联系人双方1 8 2 系统工程理论与实践第卷被认定为存在社会关系， 那么这封邮件就被认定为合法邮件， 反之， 就将其送入下一阶段由贝叶斯过滤器进行过滤利用社交网络结构图识别邮件的算法如算法所示算法联系人社交网络结构图的检索算法输入： 经过黑名单匹配之后的邮件集输出： 、区分好的邮件名称及类型、未被区分的邮件集第步提取输入邮件集中每一封邮件的联系人信息；第步： 从发信人开始对社交网络结构图进行检索， 首先检索出和发信人直接相连的联系人， 如果有收信人信息， 证明他们是有联系的， 这封邮件就为正常邮件反之就继续深度检索， 当检索深度为但还没有找到收信人信息， 就将这封邮件送入下一阶段过滤；第步重复进行第二步的工作， 直到将邮件检索完毕；第步： 输出区分好的邮件名称及类型并将未被区分的邮件集送入下一阶段进行过滤算法中对社交网络结构图的检索具体使用的是图的广度优先搜索算法对一封邮件首先提取它的发信人和收信人首先检索与有直接关联的联系人中是否存在联系人如果存在并且边的权重证明其存在社会关系， 那么这封邮件会被认定为正常邮件反之就对第一次搜索到的点再次进行搜索， 直到搜索到收信人未知在此过程中如果搜索次数达到并且还没有检索到收信人就认为联系人和之间没有社会关系对联系人和的检索， 实际上就是査找社交网络结构图中节点的邻接点的过程耗费的时间取决于所采用的存储结构， 本文中社交网络结构图的存储结构为矩阵存储， 故在此使用广度优先搜索算法其时间复杂度为基于的社交网络结构图的并行检索算法社交网络结构图的检索算法中， 最重要的部分就是根据送入邮件的发信人向下深度搜索社交关系由于构造的社交网络结构图非常庞大， 故搜索其与收信人的联系也是非常耗时的， 在算法中统计搜索社交关系是单机完成的可以在此处对算法进行并行化并行化后的算法如算法所示“算法联系人社交网络结构图的并行检索算法输入： 经过黑名单匹配之后的邮件集输出： 、区分好的邮件名称及类型、未被区分的邮件集第步： 进入的邮件集进行处理， 提取每封邮件中的发信人和收信人生成联系人文件；第步： 将提取出来的联系人文档送入在编程模型下编写的检索程序；第步： 阶段将特征文件根据使用节点数目进行等分， 然后分配到各个节点单独进行社交网络结构图的检索， 当在检索深度小于的情况下检索成功， 就将这封邮件归为正常邮件， 反之将邮件送入下一阶段过滤器；第步： 阶段将每个节点的输出结果进行合并；第步： 输出区分好的邮件名称及类型并将未被区分的邮件集送入下一阶段进行过滤算法较算法使用了编程模型对社交网络结构图的检索过程进行了优化， 采用不同的节点数目对邮件进行实验， 检索消耗的时间也有所不同， 具体运行时间对比情况如图所示基于朴素贝叶斯算法的垃稿件过滤朴素贝杆斯算法及其在垃圾邮件过滤中的应用贝叶斯分类是一种典型的基于统计学的分类方法， 它可以预测类成员关系的可能性， 如给定样本属于一个特定类的概率其基本思想是利用先验信息和样本数据信息来确定事件的后验概率对于将朴素贝叶斯算法用于文本分类， 主要是将待分类文档进行特征词提取， 然后向量化， 对于给定的向量，… 爲属于类的概率为：… ， — …■—，允一’ 爪（增刊徐雅斌等： 基于社会计算和机器学习的垃圾邮件快速过滤由公式（ 可知要判断一个文档的类别， 可以通过计算概率来完成根据文档中出现的单词与向量空间中特征项％ 的匹配情况， 来决定该文档属于第类的概率假定％ 表示第个特征项， 有：上述是利用朴素贝叶斯进行文本分类的基本流程， 朴素贝叶斯分类方法因其简洁的分类原理以及高效的分类效果从而被使用在诸多领域在垃圾邮件识别这种二元分类领域， 朴素贝叶斯算法更是有着良好的表现垃圾邮件过滤设计垃圾邮件类和正常邮件类在邮件学习过程中， 系统通过大量的垃圾邮件和正常邮件， 建立邮件训练集通过对这些邮件训练集中的每一封邮件提取独立字符串作为特征词， 记作并统计各特征词相应的词频■ 最后形成知识库假设邮件文档中的特征词％ 之间相互独立根据公式（ ， 可以计算出新邮件属于垃圾邮件类的概率， 如公式（ 所示：同理可计算新邮件属于正常邮件类的概率如公式（ 所示：；由上公式和公式可以看出， 朴素贝叶斯算法如果用来过滤邮件， 需要计算待过滤邮件中特征词出现的概率而邮件服务器往往是在短时间内需要对大量邮件进行识别， 对每一封邮件都依次进行计算就耗用了大量系统资源， 延长了邮件过滤时间因此我们可以在待过滤邮件输入到朴素贝叶斯过滤模型和计算出待过滤邮件特征词向量出现的概率⑷ 之间进行并行计算为此， 我们利用开源云计算平台的分布式并行架构对大量邮件的特征词概率⑷ 进行并行化计算基于架构的朴素贝叶斯垃圾邮件过滤模型当经过前两个阶段未被分类的邮件集进入到基于架构的朴素贝叶斯分类器中时使用此次统计邮件中特征词的词频和总数， 然后根据特征词的总数和词频计算出分词的类条件概率丨…经过此次环节将邮件集进行分类具体分类过程如图所示、：丨分！ 垃圾邮件丨— ： ； 的‘““ 知」—‘！ 、由：‘ 卓丨图基于架构的并行贝叶斯垃圾邮件识别模型——‘节点个数个） 节点数目个图基于的并行社交网络结构图检索时间图基于的并行贝叶斯算法过滤时间模型中过程的功能是计算待过滤邮件中特征词词频和总数并且计算分词的类条件概率阶段输入待过滤邮件集对每一封邮件进行中文分词并且统计好各邮件分词词频和分词总数阶段的输出为分词的类条件概率通过以上此次过程， 我们可以计算出待过滤邮件为哪类邮件的概率，进而可以判定出待过滤邮件是否为垃圾邮件1 8 4 系统工程理论与实践第卷本文分别采用不同的节点数目对邮件进行实验， 过滤时间对比图如图所示实验证明， 采用并行化的编程框架的朴素贝叶斯算法比单机运行朴素贝叶斯算法在时间上有较大的提升系统性能指标计算与评价评价指标本次实验采用召回率， 误判率和加速比作为性能评价指标假设待测试的邮件集合中共有封邮件，垃圾邮件过滤系统的判定结果如表所示表垃圾邮件判别状态表实际为垃圾邮件实际为合法邮件系统判定为垃圾邮件系统判定为合法邮件其中，斤队况为实际的垃圾邮件数目， 为实际的合法邮件数目则：定义召回率召回率表示识别出的垃圾邮件占实际垃圾邮件总数的比例， 反映系统检出垃圾邮件的能九召回率越高，“漏网” 的垃圾邮件就越少计算方法如下：召回率— 去定义误判率误判率表示被判定为垃圾邮件中实际为合法邮件的数量反映系统辨别正常邮件的能力， 误判率越低将合法邮件误判为垃圾邮件的可能性越小计算方法如下：误判率定义加速比加速比表示系统在执行同一任务时， 系统改进前后所用时间比例， 反映系统执行效率的高低系统改进前执行任务消耗时间为系统改进后执行任务消耗时间为计算方法如下：加速比实验结果实验分为两个阶段进行， 第一阶段在单机环境下采用不同的邮件数来构建社交网络结构图， 用以测试在不同的社交阿络结构图规模下对匹配结果的影响以封测试邮件进行社会关系的匹配， 消耗时间以及对匹配准确率的影响如图、图所示时间丨— 匹配成功率°丨—。— —■ ■■‘ ‘邮件数目封） 邮件数目封）图不同规模下社会关系检索时间图图不同规模下社会关系检索成功率由图和图可以看出， 社交网络结构图的规模越大， 对其检索消耗的时间越长， 匹配成功率也是越来越高但当社交网络结构图的规模到一定程度时， 检索消耗的时间和检索成功率有一定的减缓其匹配成功率和消耗时间并不是随着社交网络结构图的规模线性增长在此， 我们以封邮件来构建社交网络结构图增刊徐雅斌， 等基于社会计算和机器学习的垃圾邮件快速过滤第二阶段实验我们对封邮件在不同并行计算节点数目下进行过滤， 分别测试系统的实际运行时间、召回率、误判率和加速比社交网络结构图规模采用第一阶段中封邮件构成的社交网络结构图以上三个阶段完全采用单机识别算法和完全采用并行化识别算法的时间对比情况如图所示过滤时问单机过滤时间■ 单独使用贝叶斯■ 使用本： 文方法过滤‘一暴一一一一式審忘一工讓一—丨丨丨丨丨—；—节点个数个） 召回率误判率图垃圾邮件过滤时间对比图图系统召回率与误判率对比图由图可见， 随着采用并行计算节点数目的增加， 对相同邮件过滤所消耗时间是逐渐降低的当使用节点数目小于时， 在平台下的运行速度要比单机情况下慢， 这是因为节点之间相互通信占用了大量时间当节点数目高于个时平台分布式计算的优势就体现出来了运行时间也逐渐降低我们提出的方法和单独采用贝叶斯算法情况下系统召回率与误判率的对比情况如图所示由图可以发现在利用了本文提出的过滤方法之后， 邮件集在召回率方面较单纯地使用贝叶斯过滤器都有明显的提高对正常邮件的误判率也有所降低因为使用了社交网络结构图来对邮件进行过滤，一些在单独使用贝叶斯过滤器下被判定为垃圾邮件的邮件可能在第二阶段进行过滤的时候与社交网络结构图匹配成功而被认定为正常邮件， 因此降低了正常邮件的误判率为体现出节点数目对实验时间的影响本文中分别采用个节点来进行加速比实验各阶段加速比实验结果如图所示黑名单匹配加速比社交关系图检索加速比贝叶斯过滤加速比——■一■焉‘■ ‘ ‘ ’ ‘ ■丨节点数目个）图不同阶段加速比数据由图的不同阶段的加速比可以看出， 在节点个数较少的情况下平台上的执行时间甚至比单机的执行时间少， 随着节点数目的逐渐增多， 程序在平台上的执行时间逐渐减少， 并且低于单机运行时间黑名单检索由于算法较为简洁， 在使用个节点的时候就开始大于单机由于社交关系图检索算法比较复杂所以在节点数目为时它的加速比最大而贝叶斯过滤只有在节点数目大于时才能体现出分布式运算的优势结语垃圾邮件的大量存在， 不仅严重影响了邮件服务器的工作效率， 而且大大降低了用户体验的满意度鉴于目前普遍采用的基于机器学习的垃圾邮件过滤方法对垃圾邮件识别具有片面性， 因此本文提出了基于社交网络结构图对垃圾邮件进行过滤的方法， 并且将该方法与基于贝叶斯的机器学习方法共同进行垃圾邮件的过滤为了提高过滤速度， 本文提出了采用云计算平台上提供的编程模型进行了分布式并行计算实验结果证明在编程模型下共同协作进行垃圾邮件过滤的方法较单一采用基于机1 8 6 系统工程理论与实践第卷器学习的垃圾邮件过滤方法在精确率和时间上都有显著的提高辨文献王斌， 潘文峰基于内容的垃圾邮件过滤技术综述中文信息学报， ，—，，胡燕， 滕桂法， 董素芬， 等基于邮件结构的邮件内容提取技术的研究现代图书情报技术， ，张茜电子邮件网络中的社团挖掘研究上海： 华东理工大学，孙凌宇， 冷明， 谭云兰， 等赋权有向图的最小生成树算法计算机工程，，戴劲松， 白英彩基于贝叶斯理论的垃圾邮件过滤技术计算机应用与软件，—潘文锋基于内容的垃圾邮件过滤研究北京： 中科院计算所，