一种基于贝叶斯的垃圾邮件过滤系统.doc

精品论文推荐一种基于贝叶斯的垃圾邮件过滤系统裘敬功，张闯，肖波，蔺志青 北京邮电大学信息与通信工程学院，北京 (100876) e-mail: 摘要：本文提出了一种基于贝叶斯的智能垃圾邮件过滤系统的设计与实现方案。首先，基于贝叶斯的智能垃圾邮件过滤系统会通过训练一定数量的样本邮件，来提取区分度高的特征 值；然后对新邮件进行向量化，并利用贝叶斯公式结合训练结果对新邮件进行评分；最后，通过设定的阈值来判断该邮件是否属于垃圾邮件。 关键词：垃圾邮件；贝叶斯理论；分类器 中图分类号：tp3111.引言电子邮件在 internet 中的广泛应用极大地满足了大量存在的人与人通信的需求，也使人 们的交流方式得到了极大的改变。但是随之而来的垃圾邮件也越来越泛滥，占用了有限的存 储、计算和网络资源，耗费了用户大量的处理时间，影响和干扰了用户的正常工作，生活和 学习。垃圾邮件可以说是因特网带给人类最具争议性的副产品，它的泛滥已经使整个因特网 不堪重负。当前一些技术已经应用到反垃圾邮件系统中，如基于验证查询的技术（包括 dns 反向 查询、mx 查询、dkim 技术和 sendid 技术等），基于密码术的技术(包括 amtp、mtp、 s/mime 等)、基于挑战的技术（包括挑战-响应方式和计算性挑战等）以及基本的垃圾邮件 过滤技术。过滤是反垃圾邮件的一种重要的方法，也是应用范围最广的技术。过滤技术实现 起来相对简单，并且主要用于接收系统来辨别和处理垃圾邮件，比如很多邮件服务器上的反 垃圾邮件插件、反垃圾邮件网关、客户端上的反垃圾邮件功能等，都是采用的过滤技术。总体来说，目前的过滤技术从过滤的依据来分，可以分为基于 ip 地址过滤、基于信头 的过滤和基于内容的过滤三种。对于从自身服务器发出的垃圾邮件可以采取 ip 地址过滤的 方法。这种方法通过维护一个发送或转发垃圾邮件的 ip 数据库进行垃圾邮件过滤，可以用 于那些长期转发垃圾邮件的服务器。这种方法的优点是有效便捷，但缺点同样很明显，从该 ip 地址发出的正常邮件也将被过滤掉。基于信头的过滤技术根据信头中的某些域来进行过 滤，如发送或转发的邮件地址。常用的过滤方法是基于内容过滤，通过对邮件内容的识别， 来判断邮件是垃圾邮件还非垃圾邮件。基于内容的过滤方法结合人工智能、概率论等方法对 邮件进行判别，有着较高的识别率，有着广泛的应用。在基于内容的过滤方法中，贝叶斯过 滤方法训练以及分类的速度较快，而且从本质上讲是基于统计信息的，有着很高的识别率， 因此本系统采用基于贝叶斯的思想对垃圾邮件进行过滤处理。2. 贝叶斯决策理论2.1 贝叶斯公式贝叶斯决策理论的基础是贝叶斯公式，贝叶斯公式定义如下：若 b1 , b2 是一系列u互不相容的事件，且bi = ，且 p(bi ) 0 ，i=1,2， 则对任一事件 a 有:i =1- 7 -p(bi | a) =p(bi )p( a | bi ) p( a | bi )p(bi )i =1i=1,2， 贝叶斯公式又称逆概率公式，反映的是由已知事件的先验概率来获得事件发生的后验概 率。先验概率指的是事件发生的概率，即事件没有发生，求事件发生的可能性大小。而后验 概率则是指事件发生之后，这件事件发生的原因是由某个原因引起的可能性的大小，是一种 条件概率。但条件概率却不一定是后验概率。后验概率是由先验概率通过贝叶斯公式计算出 来的。可见，先验概率是“因”，而后验概率是“果”。2.2 利用贝叶斯理论进行垃圾邮件过滤通过对大量邮件的单词进行分析，可以认为邮件中的单词是符合贝叶斯概率模型的。利 用贝叶斯理论进行垃圾邮件过滤的基本思想如下：1某些单词在已知的垃圾邮件中出现的概 率比较大，而另外一些单词在正常邮件中出现的概率比较大。因此，一封新邮件到达后，对 其中的每个单词可以求出其在垃圾邮件中出现的概率，也就是这封邮件根据这个单词可以判 别为是垃圾邮件的概率。通过加权求和可以得到一个分数，也就是把这封邮件判决为垃圾邮 件得到的分数。同理，也可以得到把这封邮件判决为正常邮件的分数。通过求差或求积就可 以得到这个邮件的最终得分，然后再利用一定的阈值就可以得到判决结果。因此，可以根据邮件的内容来建立贝叶斯模型，将贝叶斯公式中的事件与垃圾邮件、 正常邮件对应起来，然后利用贝叶斯公式得到这封邮件的分数，再根据一定的判别规则进行 邮件类型的判别。垃圾邮件的贝叶斯模型简历以后，贝叶斯公式就成为如下形式：p(c j ) p(dx c j )p(c jd x ) =p(d x ), j = 0,1其中， p(c j ) ， j = 0,1 即为经训练集统计出来的先验概率分布，其值公式表示如下：训练中属于cj类的文本数量p(c j ) =训练集中文本数量p(d x c j )c文本的类条件概率是贝叶斯计算的关键，由待测邮件 dx 的向量和训练集对 jv的统计信息求得。我们在向量表示中提到 dx 可以用向量 e = w1 ,l, wn 表示，但是如果向量的各个元素间相关联，模型计算相当复杂，因而研究者们提出了朴素贝叶斯模型，并且该 模型完全胜任了该模型在分类领域的运用。2朴素贝叶斯模型又称简单贝叶斯模型(navie bayes)，假设构成待测文本向量的各个特 征项彼此独立，该模型如下图所示：图 1 朴素贝叶斯结构图模型假设成朴素贝叶斯模型后，p(d x c j )的求解方式如下：np(d xc j ) = p(tii =1c j )p(d xc j )目前为止，计算方法已经比较清楚，不过还不能完全求出，因为表达式中涉及待测文本的特征项，而特征项的分布模型还不清楚。常见的特征项分布模型有多变量贝 努力分布和多项式分布模型，它们属于朴素贝叶斯模型的一个变异，也就是说他们具有朴素 贝叶斯模型的性质。3智能垃圾邮件过滤系统的设计与实现总体来说，基于贝叶斯模型的垃圾邮件系统分为三个模块：邮件预处理模块、分类器训 练模块和邮件分类模块。其中，邮件预处理模块主要实现了邮件的解析、邮件的分词(即向 量化)；分类器训练模块实现了词频、文档频率的统计、特征向量的降维处理、用户反馈的 处理；邮件分类模块实现了新邮件的向量化、特征项提取、邮件评分并分类的功能。系统整 体设计框图如下图所示：图 2 系统整体框架在处理过程中，无论是训练样本、测试样本还是反馈回来的判断错误的邮件，都要首先 经过预处理模块，进行邮件解析，从邮件头和邮件体中提取内容信息，并进行分词处理，并 将邮件解析结果以向量形式保存；如果进行样本的训练，则进入分类器训练模块，统计出每 个单词的词频(tf)、文档频率(df)，然后利用 tf-idf 方法计算出每个单词在向量空间中的权 重，然后通过设定权重阈值提取权重比较大的特征值，从而实现了特征向量的降维处理，最 后将得到两个向量：spam 向量和 ham 向量，分别保存降维后特征向量中特征值在垃圾邮件 中和非垃圾邮件中的词频，也就是分类器训练得到的特征项；当一封新的邮件进入到系统后， 首先也会被解析成一个特征值向量，然后利用分类器训练得到的特征项进行降维处理，并通 过查询特征项以及结合分类决策，也就是规定的评分规则，进行对邮件的评分，最后根据评 分阈值判定邮件是否为垃圾邮件；如果在分类过程中判断错误，可以将错误的邮件进行反馈， 重新进行训练并更新关键词库。4.系统模块设计4.1 邮件预处理模块由于电子邮件是半结构化文本，语义不是很确定，需要采用一定策略从电子邮件中提取 重要的文本信息。预处理的目的是通过对邮件进行解析，从邮件头和邮件体中提取出目标文 本信息、进行分词处理，最后将结果保存到分词向量中以供分类器训练和邮件分类使用。邮 件的预处理是分类器训练和邮件分类的重要前提，预处理结果的好坏和分词的精准直接影响 到后序的处理结果。邮件的预处理主要完成了邮件的解析和文本的分词两个功能。下面将分别介绍。 目前的电子邮件一般都采用 mime(multipurpose internet mail extensions)标准，即多用途互联网邮件扩展，它定义邮件内容传输的格式以及编码方式等，邮件解析要按照 mime标准进行。一个 mime 邮件分为 mime 信息头和 mime 邮件体两部分。mime 信息头也就 是邮件头，包含了邮件的基本信息，如收件人、发件人等。此外，还包含两个重要字段： content-type 和 content-transfer-encoding。其中 content-type 定义了数据的类型，如文本、 音频、视频等类型，以便数据能被适当的处理；content-transfer-encoding 定义了数据的编 码方式，以便客户端对数据进行解码处理。如果 mime 信息头中 content-type 定义邮件体 为多部分消息(multipart)，那么每个部分还会有 mime 段头，用来指定子段的数据类型和编 码方式。下图是邮件解析的主要流程。图 3 邮件解析的基本流程解析邮件时首先获取邮件头信息，主要包括主题(subject:)、内容类型(content-type)以及内容传输编码(content-transfer-encoding)字段的内容，然后根据内容类型进行判断，如果 是文本类型就进行处理，根据编码方式读取邮件体中的文本信息；如果邮件体是多个子段组 成的，那么分别读取各个子段中文本信息，然后将文本信息汇总并保存起来。最后将邮件头 的主题和邮件体中的文本信息保存起来以便进行分词处理。在进行文本分类处理之前，要进行文本的分词。由于英文语句在书写上的特殊性，在分 词处理上相对汉语要容易的多。中文分词，也称为切词。现有的分词方法可分为三大类:基 于词典的字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。分词处理过 后的文本以单词的形式保存在向量中等待后序模块进行处理。4.2 分类器训练模块3经过分词处理后向量中存放大量不同的单词，如果将每个单词都表示成特征项的话， 那特征向量的维数将会非常庞大，而且大量不同的单词中真正能对邮件类别起到区分作用的 又占少数，因此需要通过特征选择来筛选特征项，实现特征向量的降维处理。目前特征子集 的选取算法一般是构造一个评价函数，对特征集中的每个特征进行独立的评估。本模块采用 了 tf-idf(term frequency-inverse document frequency)即词频-逆向文档频率方法来对每个 特征进行评估，以决定该特征是否作为用来分类的特征项。特征向量经过降维处理后，就可以对从训练样本提取的特征向量进行分类处理。分类器 会根据已知的邮件类别将特征项保存到指定的 spam 向量和 ham 向量。这两个向量分别保 存了垃圾邮件和非垃圾邮件中出现的特征项以及特征项的词频。4.2.1 特征向量降维特征向量的降维处理采用 tf-idf（词频-逆向文档频率）方法，该方法是一种统计方法， 用于评估一字词对一个文件集或一个语料库中某一个文件的重要程度。字词的重要性随它在 文件中出现的次数成正比，随它在语料库中出现的频率成反比。具体做法是：将每一封邮件d 表示成训练样本向量空间中的一个向量，向量中的每一维由邮件中的一个单词 wi 和其权重 组成。每个单词的权重值 di 由下式计算：r miss=num(s h)num(s h) + num(s)其中，tf (wi , d ) 为词频， d 为文档总数， df (wi ) 为文档频率。 求出每个单词的权重值后，就可以将权重值低于门限值的单词，也就是对邮件类别区分度较小的单词排除在特征项之外，最后得到精简后的特征向量。4.2.2 文本分类训练 文本的分类采用贝叶斯分类方法，贝叶斯方法基于如下的假定：待考查的数据变量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以做出最优的决策。具体的实现方法：训练样本经过解析向量化并进行降维处理后，统计每个单词在垃圾邮 件和非垃圾邮件中出现的次数，分别保存到两个向量中作为训练的结果集。两个向量 spam 向量和 ham 向量分别保存了在训练样本向量空间中垃圾邮件和非垃圾邮件出现的单词以及 词频。在这个过程中统计出类先验概率和类条件概率，从而得到贝叶斯分类器。邮件分类时需要再次查询 spam 向量和 ham 向量，以获取某关键词在垃圾邮件和非垃圾邮件中的词频来进行评分处理。为了加快查询速度，利用哈希函数将表示单词的字符串映 射为散列值，实际上 spam 向量和 ham 向量保存的是特征项的散列值。这样就加快了在邮 件分类时对已分类文本的查询速度，也加快了系统处理的速度。n下图是分类器训练模块的流程图。4.3 邮件分类模块图 4 分类器训练模块工作流程4基于贝叶斯分类方法来对一封新的邮件进行分类，首先要经过邮件的预处理、特征向 量的降维处理，然后再结合特征项库的先验概率进行组合计算获得这封邮件为垃圾邮件的后 验概率。将计算结果和设定的阈值进行比较来判定邮件是否为垃圾邮件。根据判定的邮件类型，可以进行反馈学习来更新分类器，反馈学习采用增量式学习，在 学习过程不断更新原有的各种统计量。通过贝叶斯分类器的反馈学习，该系统可以随着垃圾 邮件的变化而不断的进行更新。由于分类模块依赖于训练模块得到 spam 向量和 ham 向量，因此训练模块包括预处理 模块的分词功能处理结果的准确度直接影响到邮件的判别结果。下图是邮件分类的基本流 程。5实验结果图 5 邮件分类基本流程为了评价此过滤系统的性能，引入两个性能指标：误报率 r err 和漏报率 r miss 。其中误num(h s)报率的定义如下:r err=num(h s) + num(h)，其中 num(h s) 是将合法邮件判为垃圾邮件的概率， num(h) 为实际的合法邮件的数量。漏报率的定义如下：r miss=num(s h)num(s h) + num(s)其中 num(s h) 是将垃圾邮件判为合法邮件的数量，而 num(s) 为实际垃圾邮件的数 量。实验共使用样本邮件 37822 封，其中垃圾邮件有 24232 封，正常邮件 12611 封。其中， 正确判断出邮件类型的邮件共 36318 封，将正常邮件判为垃圾邮件共 66 封，垃圾邮件漏判 为正常邮件的共 459 封。通过计算可以得知，邮件的正确识别率为 98.575%，误判率为 0.52%， 漏判率为 1.86%。实验证明，基于贝叶斯的智能垃圾邮件过滤系统有着良好的系统性能。6. 结束语本文给出了一种基于贝叶斯的智能垃圾邮件过滤的解决方案。通过对大量样本邮件进行 测试，该系统对垃圾邮件的正确识别率在 98%以上。在贝叶斯过滤器的设计过程中有几个 难点。一是预处理模块的分词部分，切词的准确与否直接影响到样本的训练结果、邮件的分 类结果。另外一点就是特征向量降维和邮件评分阈值的选取。对于邮件特征向量降维，选取 特征项过多或过少都会对影响判决结果。而评分阈值的选择更是直接影响到邮件的分类结 果。因此，在设计过程中一定要注意对这几个细节的处理。参考文献1 刘明川，彭长生. 基于贝叶斯概率模型的邮件过滤算法探讨. 重庆邮电学院学报（自然科学版）, 第17卷, 第5期2 张铭锋，李云春，李巍. 垃圾邮件过滤的贝叶斯方法综述. 计算机应用研究 20053 邵必林，马维平，边根庆. 基于贝叶斯理论的中文垃圾邮件过滤