基于贝叶斯算法的垃圾邮件过滤相关技术研究.doc

1、 基于贝叶斯算法的垃圾邮件过滤相关技术研究摘要电子邮件系统目前互联网上最普及的应用之一。然而，电子邮件在给人们提供便捷通信手段的同时，也遭到了一些人为的滥用。当今垃圾邮件问题已经愈演愈烈，对互联网造成了很大危害。利用技术方法来阻挡垃圾邮件，是目前为止对付垃圾邮件问题最有效的手段。各种过滤技术中，贝叶斯过滤技术，借鉴了在文本挖掘问题中获得成功的机器学习算法，是目前研究较多的一种过滤技术。贝叶斯过滤方法在分类的效果上以及在不需要太多人工干预上都有很大优势，因此逐渐被广泛接受。 我们分析了目前的垃圾邮件内容过滤技术，认识到垃圾邮件过滤技术与普通的文本分类和挖掘问题存在着很多不同。我们总结和分析了目前

2、基于贝叶斯垃圾邮件过滤技术的现状，包括文本表 示、特征选择、分类算法、评价体系，以及垃圾邮件过滤领域中常用的公共语料库，对基于贝叶斯的过滤方法提出了一系列改进。论文的具体内容包括： （1）对朴素贝叶斯算法进行了详细的研究，并且提出了三个方面的改进思路。在文本表示方面，提出采用指纹特征的表示方法；在特征选择方面，提出了基于类条件分布的特征选择；第三个方面，根据学习的不断深入性，提出了阈值动态调整算法。基于这些改进，实现了改进的朴素贝叶斯过滤器。（2）分析邮件结构特点，从邮件结构不同于普通文本出发，提出集成加权模型，以充分利用邮件的结构信息。基于集成加权模型对邮件头和邮件正文分别建立模型，最后通过

3、加权方法集成二者结果，对垃圾邮件进行过滤。（3）研究了最小风险贝叶斯和主动学习贝叶斯两种贝叶斯的扩展模型。最小风险贝叶斯能够减少正常邮件判为垃圾邮件的风险，而主动学习贝叶斯主动训练样本集，能够降低样本顺序对过滤精度的影响。根据实验结果对比，得到两种扩展模型的最佳应用条件，并提出了改进后的邮件过滤算法。综合以上改进和扩展而设计的贝叶斯过滤器在最新的标准数据集上的测试结果表明，与经典的贝叶斯过滤器Bogo相比，过滤效果有较大的提高。关键词： 集成加权贝叶斯 ； 最小风险贝叶斯 ； 主动学习贝叶斯 ； 特征选择 ； 阈值调整ABSTRACT Electronic mail (e-mail) is a

4、 big success of Internet; it is becoming one of the fastest and most economical ways of communication available. At the same time,the growing problem of junk mail (also refered to as “spam”) has generated a need for e-mail filtering. There have been a lot of methods to beat spam, and the approach of

5、 using automated text categorization and information filtering to filter spam is become a most efficient one. We analyzed the current technology of content-based spam filtering, and found lots of differences between the traditional text categorization Problem and the one of spam filtering. Depend on

6、 this analysis, develop some methods to improve the performance of the spam filtering algorithm. The contents of this article are as following: (1) A summary about the state of the content-based spam filtering. We investigating anti-spam problem from the text categorization perspective, introducing

7、the approaches of feature selection, classifiers and e-mail corpus in this task.(2) We study the bayes algorithm in details and propose the improvings in four aspects.The first aspect is the showing of text.We proposes a new method which is fingerprint feature. The second aspect is feature selecting

8、. We propose a new method which is class condition distribute. The e-mail corpus and text corpus are very different in structure. We analyzed the structure of email, and purposed a email header and email body integrated model. In the fourth aspect, we propose threshold adjusting algorithm. In the en

9、d ,we combine four aspects, and realize the improving bayes percolator.(3) From the shortcomings of ordinary bayes,Bayes proposed minimum risk Bayes model and initiative studying Bayes model. Minimum risk Bayes model reduced the risk to judge the normal mail as spam email And the initiative studying

10、 Bayes model can reduce the impact of the order of corpus in the email filtering accuracy.Keywords: Minimum risk bayes ; Active learning bayes ; Integration weighted bayes ; Feature selection ; Threshold adjustment 目录摘要IABSTRACTII目录III第一章绪 论11.1引言11.1.1课题研究背景11.1.2贝叶斯研究简介11.1.3贝叶斯垃圾邮件过滤发展史21.1.4国内外贝

11、叶斯垃圾邮件过滤发展现状21.2垃圾邮件的危害及当前状况51.2.1.垃圾邮件的定义51.2.2我国垃圾邮件的当前状况61.3 垃圾邮件过滤常用技术61.3.1黑白名单技术71.3.2反向域名验证71.3.3关键词过滤71.3.4基于规则评分的过滤技术81.3.5贝叶斯过滤法81.4本文研究的内容81.5论文组织结构9第二章 贝叶斯算法及邮件评测相关技术简介102.1 贝叶斯定理102.2朴素贝叶斯的原理102.3 贝叶斯过滤器122.4 朴素贝叶斯算法在邮件过滤应用上的优缺点122.5 朴素贝叶斯邮件过滤器的扩展132.5.1最小风险贝叶斯132.5.2主动学习贝叶斯132.6 邮件评测14

12、2.6.1邮件过滤语料库142.6.2 邮件过滤模式152.6.3 评价体系172.7 本章小结20第三章 朴素贝叶斯过滤器的改进213.1 贝叶斯分类流程213.2 贝叶斯邮件过滤器的改进方面213.3文本表示223.3.1 词语特征项223.3.2指纹散列特征项223.3.3一种指纹算法233.4特征选择233.4.1 信息增益243.4.2 期望交叉熵244.4.3 互信息253.4.4 基于类条件分布的特征选择253.4.5 三种特征选择方法邮件过滤精度比较263.5阈值动态调整303.5.1阈值对过滤精度的影响303.5.2 阈值调整自适应算法313.5.3 阈值动态调整的实验结果分

13、析313.6 改进的朴素贝叶斯邮件过滤流程333.7本章小节33第四章 邮件头邮件正文集成加权分类模型354.1 邮件消息格式354.2邮件头邮件正文独立训练374.3特征CCD值在邮件头和邮件正文中的分布374.4将权重应用到朴素贝叶斯分类424.5 邮件头邮件正文集成加权模型流程434.5邮件头邮件正文集成加权模型与普通模型实验结果对比444.6 本章小结45第五章 贝叶斯过滤器的扩展465.1基于最小风险的贝叶斯过滤算法465.1.1 过滤规则465.1.2 邮件过滤算法485.1.3 最小风险贝叶斯算法实现机制及实现代码495.1.4基于最小风险贝叶斯与朴素贝叶斯的实验对比505.2

14、主动学习贝叶斯525.2.1 主动学习的一般原理525.2.2 主动贝叶斯分类模型545.2.3主动学习策略545.2.4 基于最大最小熵主动学习555.2.5 最大最小熵主动学习的实现机制及实现代码555.2.5加入主动学习的朴素贝叶斯与未加入主动学习的朴素贝叶斯实验对比575.4 本章小结58第六章 实验与性能分析596.1 过滤器设计596.2 朴素贝叶斯过滤器与bogo过滤器的比较606.2.1 离线过滤模式下朴素贝叶斯过滤器与bogo过滤器的比较606.2.2在线过滤模式下朴素贝叶斯过滤器与bogo过滤器的比较616.3 本章小结61结论及展望62参考文献63攻读硕士学位期间取得的研

15、究成果65致谢66VI第一章绪 论第一章绪 论1.1引言 1.1.1 1.1.1课题研究背景Internet的迅速发展，人与人的交往更加方便，电子邮件以其快捷低廉的特性逐渐成为人们信息交互的重要工具。人们用它来交流思想，传输文件，发表意见等，逐渐成为日常生活中不可缺少的通信工具。但是电子邮件在其给人们带来极大便利的同时也带来了一些负面影响，那就是我们每天收到的邮件有很大一部分是不请自来的。它们有些是商业广告，有些是政治宣传，有些是色情广告，还有一些甚至是病毒，这就是我们俗称的垃圾邮件。根据美国nucleus research 公司公布的数据，全球每天大约有140亿封垃圾邮件在网上传播，相当于地

16、球上每个人每天都要收到两封以上的垃圾邮件。垃圾邮件给网民造成的经济损失是相当惊人的：据统计仅下载它们所花费的上网费和电话费用等费用，每年就会花掉全球网民94美元。作为垃圾邮件的发送方，价格是及其低廉的，通常是通过各种方式群发。而对于电子邮件服务提供商和用户来说，垃圾邮件却给他们带来了很大的危害和损失，而且如色情，电脑病毒，以及荷重欺诈信等造成的损失更是造成难以评估。1.1.2 1.1.2贝叶斯研究简介贝叶斯的论文“关于几率性问题求解的理论”奠定了贝叶斯学派的基础。而后著名数学家laplace用贝叶斯理论导出的”相继律”使得贝叶斯理论受到人们的关注。但是由于当时贝叶斯方法在理论和实际的应用中还存

17、在很多不完善的地方，因而在十九世纪并未被人接受。八十年代以后，人工智能的发展尤其是机器学习，数据挖掘等兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。尽管对于贝叶斯学派哲学上的观点还是存在很多的异议，然而它的思想和方法在社会生活和生产实践中得到越来越广泛的应用确实不争的事实。尤其是近年来，贝叶斯方法以其独特的不确定知识表达形式，丰富的概率表达能力，综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一。1.1.3 1.1.3贝叶斯垃圾邮件过滤发展史 1996年，Rvennie基于贝叶斯算法建立了一个用于邮件过滤的机器学习应用系统ifile1，利用贝叶斯算法对邮件进行分

18、类。在建立ifile系统的过程中，Rennie注意到每个用户有不同的邮件集，并且组织邮件 的方式也各不相同，因此允许用户手工调整被误判的邮件。 1998年，Sahami利用贝叶斯算法对邮件进行过滤时，注意到垃圾邮件具有不同于合法邮件的特有属性：例如，在快速致富类的垃圾邮件中，除了邮件的文本中会含有许多free money之类的文本信息之外，还会有大量类似于 “!”的强调符号以及“$”这种表征线的符号。所以Sahamiliy利用朴素贝叶斯算法滤邮件时，手工加入了这些特定任务的域信息短语以及具有垃圾邮件特征的字符到过滤器中，提高了过滤垃圾邮件的精确度；另外，他还利用一个表征损失率的门槛值来降低合法

19、邮件的误判率。 2001年，Matthew等人开发了一个垃圾邮件过滤器MEF。MEF可以在UNIX中过滤掉附件中有可执行程序的病毒邮件。该邮件过滤器首先对可执行程序的二进制码进行解码，然后把它与现有病毒的二进制码进行比较，利用朴素贝叶斯算法计算出它属于垃圾邮件的概率值，并据此作出决策。1.1.4 1.1.4国内外贝叶斯垃圾邮件过滤发展现状文献利用朴素贝叶斯算法设计了垃圾邮件过滤系统SpamCop2。该系统能够识别大约92%的垃圾邮件，并且有1.16%的错纠率。SpamCop系统在关键词的选取原则上进行了改进，忽略掉空格，连续序列的字母和数字，以及除掉上述字符之外的不超过长度为3的连续序列字符。

20、并且该系统对特征类概率的计算使用了m估计，采用了如下的公式：公式 (1-1)公式 (1-2)公式 (1-3)其中，表示特征Token属于垃圾类别的后验概率。代表该关键字在垃圾邮件中出现的次数，表示关键词在正常出现的次数。表示正常邮件的个数，代表垃圾邮件的个数。K代表待检邮件中不同关键字的个数，从而解决了零概率问题。文献提供了一个有效的过滤垃圾邮件的贝叶斯方法3，该过滤器抓住了99.5%的垃圾邮件，且错纠率低于0.03% 。该过滤器对垃圾邮件和正常邮件集分别建立两个哈希表，用于统计相应得语料库的关键词及其出现的次数。计算每一个关键词的概率，使用以下的公式： 公式 (1-4)其中b代表该关键词在垃

21、圾邮件集中出现的次数，g代表该关键词在正常邮件集中出现的次数，nbad代表垃圾邮件的总数，ngood代表正常邮件的总数。在分母中的系数2是一个推荐的经验值，用于减少把正常邮件当作垃圾邮件的概率。在计算联合概率时，过滤器使用如下的公式： 公式 (1-5)其中（i=1，2，n）表示已经计算出来的第i个关键词的概率。当使用公式(1-5)计算一个邮件属于垃圾邮件的概率时，会经常遇到数据稀疏问题，即如果邮件中包含一个新出现的特征项，则不管这封邮件中包含的其他特征项的条件概率有多高，都会导致条件概率的零概率问题。这是个不容忽略的问题。其中文献3给出了一个零概率平滑公式，较好的解决了零概率问题。公式如下所示

22、： 公式 1-6其中a是一个可调节的常量，n为包含特征w的垃圾邮件和正常邮件的总合，x是初始概率，当n=0时，f(w)等于初始概率，随着n的增大，f（w）越来越接近p（w）。根据经验，一般设置初始概率为0.52，a值为0.0178。文献4对公式1-5也进行了改进。给出了计算关键词联合概率的新方法。公式 1-7公式1-8公式 1-9S的值介于-1和1之间，高的值意味着垃圾邮件，低的意味着正常邮件。0意味着介于两者之间。上述利用朴素贝叶斯构建的过滤器大多在贝叶斯的计算公式上进行改进，没有考虑到邮件过滤与普通的文本分类的区别，另一方面，这些传统的贝叶斯方法都是基于最小错误率的决策方法，没有考虑到合法

23、邮件与垃圾邮件具有的不同特性，即合法邮件误判为垃圾邮件可能给用户带来更大的损失。另外传统的贝叶斯学习算法使用给定的训练样本学习分类参数，它所处理的训练样本必须是带有类别标注的，并且随机选择样本，被动接受这些样本的信息。本文研究贝叶斯垃圾邮件过滤流程，在特征选择等流程提出改进方法，并且提出两种朴素贝叶斯的扩展模型：最小风险贝叶斯和主动学习贝叶斯。1.2垃圾邮件的危害及当前状况 1.1.5 1.2.1.垃圾邮件的定义 垃圾邮件一般指的是未经用户可，但却被强行塞入用户邮箱的电子邮件 。迄今为止，垃圾邮件在国际上还没有统一的定义。 在中国互联网协会反垃圾邮件规范中垃圾邮件被界定为：1） 收件人事先没有

24、提出要求或者不同意接收的广告，电子刊物以及各种形式的宣传邮件 。2） 收件人无法拒收的电子邮件。3） 隐藏发件人身份，地址，标题等信息的电子邮件。4） 含有虚假的信息源，发件人，路由等噢，信息的电子邮件。按照上述界定，上面四类邮件都属于垃圾邮件范畴。相反，我们可以称收到的其他邮件为”合法邮件”。对大多数用户，收到的垃圾邮件大部分都是没有主动订阅的广告，电子期刊登宣传品，其基本特征是”不请自来 “，带有商业目的(unsolicited commercial e-mail)或者政治目的 。实际上，垃圾邮件的判定会因而异，不同的用户对同一邮件的判定结果可能存在差异。虽然我们很难对垃圾邮件下一个确定的

25、定义，但是绝大多数的垃圾邮件都具有以下某些特点 ：1) 未授权 他们大多都是指未经请求而发送的电子邮件。2) 商业目的 很多垃圾邮件都直接或者间接的和商业联系起来，如未经发件人请求而发送的行业广告或者非法的电子邮件 。 3) 数目众多 垃圾邮件往往不是一封两封的发出，绝大多数为成百上千。垃圾邮件造成的危害主要包括：1) 增加破坏机械设备的可能（垃圾邮件可能携带危险的电脑病毒，对电脑硬盘资料及系统造成威胁）；2) 影响电子邮箱的工作效率（大批量的垃圾邮件能使得邮箱堵塞，使得网络速度大幅下降）；3) 影响与客户的正常业务联系，造成间接经济损失；4) 增加合法邮件服务的成本（大量的垃圾邮件使得它们必

26、须大幅度提高计算机及网络性能，以维持邮件服务器的正常运行，为此所花的成本要么自己消化，要么转嫁到用户身上）；5) 耗费收件人的上网时间；6) 对有用电子邮件的淹没（超出邮箱容量时，旧有的有用邮件被自动删除，或者混杂于大量的垃圾邮件中不易找出）；7) 影响接收人的身心健康（垃圾邮件中含有不健康内容的占有相当大的比例）；8) 对人权的挑战（垃圾邮件可认为是强迫别人接收不同意接收的信息，是对人通信自由的侵犯）；9) 动摇了人们对互联网的信心（垃圾邮件不仅阻碍了信息业的发展，损害了人们对于网络交流的信心）。10) 带来了严重的社会问题 （国内有些IP地址被国际上某些反垃圾邮件组织和网络运营商列入黑名单

27、，甚至许多网络被国外屏蔽 ，使得合法邮件也不能正常使用 ）。据统计，美国每年因为垃圾邮件造成的直接或者间接损失高达10亿美元，全球的损失更高达20亿美元。1.1.6 1.2.2我国垃圾邮件的当前状况目前我国垃圾邮件泛滥，情况十分严重。全球前十大垃圾邮件大国之中，中国仅次于美国高居垃圾邮件大国第二。中国网民收到的垃圾邮件数量占全球的十分之一，并且这个数字没五个月会翻一番。 我国目前拥有网民数接近一亿，其中绝大多数网民至少拥有一个电子邮件信箱，他们因此成为垃圾邮件的直接受害者。数据还显示，每个网民平均每天收到1.85封垃圾邮件，为处理这些垃圾邮件，每个网民每天需要花费3.65分钟。这意味着，全国网

28、民每年会浪费点15亿小时的宝贵时间。网络安全界一直认为如果所有的邮件服务器不被非法利用，就可以有效地遏制垃圾邮件的传播。即使有部分组织可能会使用自己的邮件服务器发送垃圾邮件，但将会容易得被追查出来。我们国内面临的主要问题是Open Relay，特别是被国外的组织和个人利用，并且屡屡找到受害者的投诉，时有IP被列入国外反垃圾邮件组织黑名单的情况。1.3 垃圾邮件过滤常用技术随着垃圾邮件的泛滥，垃圾邮件过滤技术也在不断的发展，产生了许多对付垃圾邮件的方法。一些成熟的方法在客户端、服务器端等被广泛的应用，新的方法也在不断的产生。下面就介绍一下常用的垃圾邮件过滤技术。1.1.7 1.3.1黑白名单技术

29、 黑名单(Black List)和白名单(White List)分别是己知的垃圾邮件发送者和可信任发送者的IP地址或邮件地址。黑名单技术是最早出现的一种垃圾邮件过滤技术，一般的邮件服务器都有该功能。黑名单技术的原理是确定已知垃圾邮件制造者及其ISP的域名或IP地址、电子邮件地址，将其整理成黑名单，将黑名单部署在处理网关处，拒绝任何来自黑名单上的垃圾邮件制造者的邮件。白名单的原理是拒绝接收任何邮件，除非用户的邮件地址在白名单上。白名单提供两种使用方式：一种方法是用户阻止不在名单上的信件；另一种方式是系统邮件发送者发送信件，要求其回复，以证实确有邮件发送者其人，经过确认后将其列入白名单中。 该技术

30、的优点是不占用计算机资源，易于实施；缺点是需要手动维护黑白名单。由于垃圾邮件发送者经常修改和伪造他们的IP地址和邮件地址以逃避反垃圾邮件手段的检测，因此该方案在总体的垃圾邮件解决方案中仅起补充作用。1.1.8 1.3.2反向域名验证 该技术对邮件发送者的IP地址进行逆向名字解析，通过DNS查询来判断发送者的IP与其声称的名字是否一致，来判断是否是垃圾邮件。如果反向DNS查找提供的域与邮件上的来源IP地址相符合，该邮件被接受。如果不符合，该邮件被拒绝。 由于很多反向DNS目录未被有效建立，或无法正常建立，比如，任何”vanity”域名绝大多数情况下没有一个正确的反向DNS查找。在这种情况下，由这

31、些域发送的邮件将被阻断，造成不可接受的高误报率。1.1.9 1.3.3关键词过滤 关键词过滤是一种基于内容检查的过滤技术，通常创建一些简单或复杂的与垃圾邮件关联的单词表来识别和处理垃圾邮件，比如”免费”、”色情”等在垃圾邮件中经常出现的词语。该方法通过对邮件的信头、信体、附件的内容进行检查，判定是否符合过滤规则，从而判定是否为垃圾邮件。这是一种简单的内容过滤方式来处理垃圾邮件，它的基础是必须创建一个庞大的过滤关键词列表。 这种技术缺陷很明显，过滤的能力同关键词有明显的联系，关键词列表造成漏报、错报的可能性比较大。垃圾邮件发送者经常会采用一些躲避关键词的技术，比如拆词、组词、将一些单词拼错，以图

32、饶过词语过滤器，所以过滤关键词需要经常升级，以适应新的需要。现在的邮件群发软件做的也越来越智能了，由其自动生成和发送的垃圾邮件是随机生成的，不但能随机生成邮件的发件人、收件人和邮件主题，还能随机生成邮件的内容，使得该种技术目前应用范围日趋狭窄。1.1.10 1.3.4基于规则评分的过滤技术 这是一种集合了人工智能技术的应用技术。该技术对邮件进行规则判断。在规则中，每条规则对应一个分数，当邮件符合某一条规则时，就给邮件增加相应的分数，分数越高，该邮件是垃圾邮件的可能性就越高，得分超过一定值时，该邮件将被分类为垃圾邮件。该技术过滤准确率可以达到90%，但不能检测新的垃圾邮件，即漏检率高。为了能使评

33、分有效，规则需要经常更新。1.1.11 1.3.5贝叶斯过滤法 贝叶斯算法是以著名数学家托马斯.贝叶斯(Thomas 贝叶斯)(1702-1761)命名的一种基于概率分析的可能性推理理论，通过分析过去事件的知识，来预测未来的事件。贝叶斯过滤法对大量用户已经判定的垃圾邮件和合法邮件进行学习，根据垃圾邮件和合法邮件中相同词语及短语出现的概率对比来确定垃圾邮件的可能性。贝叶斯过滤法可以通过不断地学习来适应垃圾邮件的新规则。贝叶斯过滤法是阻断垃圾邮件最为精确的技术之一，过滤准确率可以达到99%，但过滤准确性依赖大量的历史数据。1.4本文研究的内容本文旨在对贝叶斯模型在垃圾邮件过滤中的应用进行深入研究，

34、并针对其面临的一些关键问题提出有效的解决或改进方法，以提高贝叶斯模型在垃圾邮件过滤中的性能和可扩展性。现将本文所做的主要工作概括如下：(1) 贝叶斯分类模型研究 对目前贝叶斯邮件过滤器的基本原理和基本方法做了研究。(2) 文本表示 中文邮件内容一般表示为词语向量，英文文本的特征项则表示为由空格隔开的英语单词。对多封垃圾邮件进行相似度比较的时候，发现在同类垃圾邮件出现较高的是一些文本块短语，所以本文提出一种新的文本表示方法，用代表文本块的指纹作为特征项，研究垃圾邮件过滤的精度。(3) 文档特征选择算法研究与改进特征选择是垃圾邮件过滤中一个重要的预处理环节，迄今为止，已经有多种特征选择算法被提出。

35、常见的特征选择的方法有：信息增益法，互信息法，卡方检验法，主成分分析法等等。这些方法或者从信息论的角度或者从统计分析的角度，来找出含有信息最大或者影响显著的特征。针对贝叶斯垃圾邮件过滤，本文提出了一种基于类条件分布的特征选择方法，提取出类条件分布最不均匀的特征。(4) 邮件结构研究 邮件过滤是文本分类的一种，而邮件相对于传统的文本来说，又有其特殊结构。邮件的邮件头包含了很多信息，为此本文分析邮件头邮件正文的特征分布情况，并且据此提出邮件头邮件正文集成加权模型。(5）阈值对垃圾邮件过滤精度的影响 概率阈值对贝叶斯过滤器垃圾邮件过滤精度有着直接的重要影响，不同的邮件集有自己的最佳阈值，对同一个邮件

36、集，阈值取值对过滤精度也有影响。因此本文研究阈值问题，并且提出一种阈值调整算法。（6）贝叶斯过滤器的扩展模型 对朴素贝叶斯过滤器进行扩展，实现了最小风险贝叶斯和主动学习贝叶斯，并且对最小风险贝叶斯和主动学习贝叶斯应用的条件进行了分析。1.5论文组织结构 论文共分为七章，第一章为绪论，第七章为结束语，第二章到第六章为本文的主要研究内容。第二章介绍了基于贝叶斯算法的垃圾邮件过滤技术以及评价过滤算法的评价平台，第三章介绍如何从文本表示，特征选择方法方面来改进朴素贝叶斯算法；第四章绍了邮件头邮件正文集成加权模型；。第五章描述了贝叶斯算法的两种扩展模型：最小风险贝叶斯算法和主动学习贝叶斯算法，第五章还实

37、现了这两种模型并将两种扩展模型与改进贝叶斯模型进行过滤精度比较。第六章将改进模型与国外开源软件bogofilter进行比较。20第二章 贝叶斯算法及邮件评测相关技术简介第二章 贝叶斯算法及过滤相关技术2.1 贝叶斯定理 贝叶斯定理是决策逻辑学的一个分支，使用理论统计学研究概率推论，即根据已经发生的事件来预测将来可能发生的事件。贝叶斯理论假设，如果过去试验中事件的出现的概率己知，那么根据数学方法可以计算出未来试验中事件出现的概率。贝叶斯理论指出，如果事件的结果不确定，那么量化它的唯一方法就是事件的发生概率。 垃圾邮件过滤其实就是邮件分类问题，把邮件分为垃圾邮件和正常邮件。这就可以应用贝叶斯定理，

38、通过对己经正确分类的邮件来预测新接收的邮件是否为垃圾邮件。贝叶斯定理的描述如下： 对于一个统计实验，样本空间s是所有可能结果的集合，并且是s的一个划分。令p(A)； A S表示定义在s中所有事件上的一个概率分布，则对于s中的任意事件A和B，有p(A) 0，表示条件概率，即在己知A发生的情况下B发生的概率。贝叶斯定理可以表示为： (i=1， 2，r) 公式(2-1)其中p(A) 0，由全概率公式可得 公式(2-2)在公式(2-1)中，p(Bi / A)为后验概率，为似然概率，为先验概率。2.2朴素贝叶斯的原理贝叶斯方法是垃圾邮件过滤中一个重要的方法，该方法的实质是把邮件确定为垃圾邮件或者正常邮件

39、，这是一个分类问题。设有m个样本空间，邮件d中有n个特征项，对于给定的类(k=1,2,m)，d属于类的概率为 公式(2-3)通过贝叶斯概率公式可得： (k=1,2,，m) 公式(2-4)其中： 公式(2-5)公式(2-4)中的分母p(d)与类别无关，因而在公式(2-3)中比较最大值的时候可以忽略，所以只需计算概率和即可划分邮件d的类别。公式(2-4)中，为先验概率，很容易计算，但的计算比较困难，特别是在特征项的数量较大，且特征项之间相依程度较高时，其计算将是极其费时间的。为了简化计算，引入了条件概率独立假设，即假定各特征项之间是相互独立的，这就是朴素贝叶斯过滤器，那么公式(2-5)就可以转换为

40、： 公式(2-6)朴素贝叶斯过滤器的结构如图所示： 图 2-1 朴素贝叶斯过滤器结构图朴素贝叶斯过滤器主要是利用先验概率求出后验概率，并且根据训练样本集构造过滤器，过滤器根据邮件的后验概率对文本进行分类。 2.3 贝叶斯过滤器 Bogofilter是目前比较流行的贝叶斯过滤器，它的主要原理是朴素贝叶斯理论。Bogofilter建立垃圾邮件和非垃圾邮件贝叶斯概率模型，在贝叶斯原理的实现上，加入了Paul Graham 关于垃圾邮件的过滤理论。该理论大体思想是，在已知的垃圾邮件中，一些单词出现的频率较高，而在合法邮件中，另一些单词出现的频率较高。运用一些众所周知的数学知识，对于每个单词，可以生成一

41、个”垃圾邮件指示性概率”。根据消息中所办含一组词，可以用另一个简单的数学公式来确定文本消息的整体垃圾邮件概率。Bogofilter将由空格隔开的单词作为特征，并且对特征进行更加严格的定义，譬如，去除单纯包含数字的特征，对于$20-25这种形式的价格范围，被标记为两个关键词，$20和$25等。Bogofilter还使用了平滑技术，来加强过滤器的过滤精度。 在过滤效率上，Bogofilter采取有效的数据表示，和高效的数据存储技术，获得比较高的过滤效率。Bogofilter使用高性能的Berkerly DB 数据库。Berkerly DB是历史悠久的嵌入式数据库系统，其小巧，可靠，性能高。Berk

42、erly DB 比SQL SERVER 等数据库性能要高10-20倍。2.4贝叶斯过滤器的优缺点 朴素贝叶斯算法，其条件概率独立假设，虽然忽略了特征的条件依赖性，但是，在许多实际应用领域中取得了很好的结果，而且其计算简单，降低了算法的复杂性。 不同与对普通文本的分类，在邮件过滤方面，朴素贝叶斯过滤器也存在一些缺陷。因为邮件分类是一种二类分类问题，且邮件不同于普通文本，有其独特的结构。例如：邮件由邮件头和邮件正文组成，普通的文本分类朴素贝叶斯算法会将邮件头和邮件正文不加区别，而没有考虑到邮件头和邮件正文对邮件类别影响程度的不同。另外邮件分类是一种二类分类问题，两个分类之间是互相影响的，例如合法邮

43、件的误判率低，而非法邮件的误判率高，说明判定一封邮件为非法邮件的阈值过高，为合法邮件的阈值过低。而在普通文本分类时，朴素贝叶斯只是挑选后验概率最大的分类作为文本类别，没有考虑到两类分类中，阈值相关问题。 针对朴素贝叶斯在邮件过滤问题上暴露的缺点，我们对朴素贝叶斯过滤器的相关流程做出一系列改进，改进的内容在第四章会有详细描述。2.5 朴素贝叶斯邮件过滤器的扩展 朴素贝叶斯过滤器在样本学习阶段，通常采用被动学习的方式，这种学习方式没有样本筛选的过程，算法复杂性小，但是这种学习方式造成过滤精度依赖样本的顺序性。本节提出一种主动学习的贝叶斯过滤器作为普通贝叶斯过滤器的一种扩展。在分类决策阶段。朴素贝叶

44、斯算法是一种基于最小错误率的决策方法，这种决策方法把各种类别的错误判断一视同仁，但是在邮件过滤中，合法邮件误判更应该引起人们重视，所以在此提出最小风险贝叶斯算法，以风险高低作为类别的决策依据，也是在决策阶段对于朴素贝叶斯邮件过滤器的一种扩展。1.1.12 2.5.1最小风险贝叶斯朴素贝叶斯算法是基于最小错误率的决策方法。但是，在邮件的分类与过滤中，合法邮件与垃圾邮件具有不同的特性。合法邮件被判定为垃圾邮件可能给用户带来更大的损失。因此，考虑到各种错误造成的损失不同，可采用最小风险的贝叶斯决策对邮件进行过滤和分类。基于最小风险的贝叶斯过滤算法是一种特殊的贝叶斯算法，它把邮件分为两类，即合法邮件和

45、非法邮件。最小风险贝叶斯算法是用来增强前面描述的朴素贝叶斯过滤器的性能，降低邮件过滤的风险，以得到一个风险最小的邮件过滤器，是对朴素贝叶斯进行的修正。最小风险贝叶斯的邮件过滤算法，对合法邮件判断为非法邮件以及非法邮件判断为合法邮件定义不同的风险，选择风险最小的决策类别，可以有效降低错误决策造成的损失。1.1.13 2.5.2主动学习贝叶斯根据分类学习对训练样本的处理方式，可将分类模型分成两类：被动分类和主动分类模型。被动分类模型也称”从样本中学习” ，它随机的选择训练样本，被动地接受这些样本的信息，如图3-2。它对于具有严格序关系的训练样本来说是必要的，也是不可改变的。然而绝大部分分类学习中都

46、认为训练样本是独立同分布的，这种被动的学习显示出明显的不足：1)顺序的处理训练样本往往会使学习的过滤器具有顺序相关性，对数据过分敏感；2)遇到噪音样本时，会使这种噪音一直传播下去，影响分类精度3)缺乏综合未带标注样本信息的能力。在学习分类模型中，未带标注的样本往往包含有助于分类的信息。在这种情况下，选择好的未带标注的样本，把它加入到当前的过滤器中是相当重要的。主动分类模型对训练样本的选择是主动的，它选择最有利于过滤器性能的样本来训练过滤器，属于更高层次的，具有潜意识的学习，如图2-3图 2-2 被动学习模式 图 2-3 主动学习模式 由于贝叶斯网络分类具有增量学习的特性，它更适宜主动学习，在增量地分类和增量学习概率分布方面可以大大的提高效率.传统的学习算法使用给定的训练样本学习分类参数，它所处理的训练样本必须是带有类别标注的，并且一般都假定各训练样本是独立同分布的.相反，主动学习算法在侯选样本集中主动选择测试样本.2.6 邮件评测为了能对不同的垃圾邮件过滤算法进行评测，必须有一个可供比较的平台。这包括公共的评测语料，统一的过滤模式和统一的评价方法。1.1.14 2.6.1邮件过滤语料库文本分类问题研究的成功开展，很大程度得益于规范，手工标注类别，公共的文本分类语料库，例如路透社语料，已经成为了标准的测试平台。但是垃圾邮件的