垃圾基于贝叶斯算法分类的反垃圾邮件系统的改进毕业论文

学位论文题目基于贝叶斯算法分类的反垃圾系统

学位论文原创性声明

本人重声明所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的容外本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。

作者签名 日期 年 月 日

学位论文使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名 日期 年 月 日

导师签名 日期 年 月 日

摘 要

电子成为一种快捷、经济的现代通信技术手段极方便了人们的通信与交流。然而垃圾的产生影响了正常的电子通信 占用了传输带宽对系统安全造成了严重的威胁。因此研究反垃圾问题已经成为全球性的具有重大现实意义的课题。

目前应对垃圾的主要方法和手段是通过反垃圾立法和使用过滤技术进行处理现已相继出现了多种过滤技术。常用的包括黑/白技术、基于容的分析方法以及基于规则的方法等。基于容分析的技术正逐步进入过滤技术当中并成为当前研究热点其中基于容分析的过滤方法中的典型方法是基于贝叶斯算法的垃圾过滤模型。

本论文对中文垃圾的特点进行了比较系统的分析和研究结合贝叶斯Bayes理论构造基于贝叶斯分类的垃圾过滤模型在特征提取方面采用互信息值的方法在分类方法上引入了适合本文的分类方法并采用了一种更加适合于贝叶斯计算的表示方法本文作者采用中国教育科研网CERNET收集并维护的大量中文垃圾和正常样本的标准数据集对本文研究的方法进行了大量测试准确率和误判率分别达到了95.8%和5.3%。结果表明基于贝叶斯算法的垃圾过滤系统对拦截垃圾有很好的作用。

关键词 电子垃圾过滤贝叶斯理论

Abstract

The has become a quick and economical means of moderncommunication technology, which enormously facilitates people'scommunication and exchanges. However, the emergence of spam hasaffected the normal email correspondence,and taken the transmission bandwidth, even posed the serious threat to the system saf ety.Therefore, thestudy of anti-spam has become a global problem of great practicalsignificance of the topic.

At present, the main ways and means of the response to spam are theanti-spam legislation and the use of mail filtering technology.But now avariety of mail filtering technologies have appeared in succession,which areusually used including black / white list technologies, content-basedanalysis methods, and rule-based methods. Content-based analysistechniques are gradually entering the mail filtering technology which hasbecome hot spots of current research.The typical method of content-basedanalysis mail filtering methods is based on Bayesian algorithm for spamfiltering model.

In this paper, the Chinese characteristics of spam has been studied andanalyzed systematically.Combining with Bayesian(Bayes) theory, this paperconstructs the spam filtering model which is based on Bayesian classification.In feature extraction, mutual information values are used. In theclassification method,a classification method is introduced which is suitablein this article, and a more suitable expression in the Bayesian calculationmethod is adopted; the standard sample data sets of a large number ofChinese spam and regular mail are collected and maintained by the ChineseEducation and Research Net (CERNET) .The author conducted a lot of testingtowards the methods which are studied by this paper.The accuracy andmisjudgment rate reached 95.8%and 5.3%respectively.The results showthat the spam filtering system based on algorithm Bayesian plays a very goodrole to block spam.

Key Words: , spam,mail filtering,Bayesian theory

目 录

第一章绪论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

1.1引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

1.2垃圾的定义及其危害. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

1.2.1垃圾的定义. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

1.2.2垃圾的危害. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2

1.3国外反垃圾现状. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

1.4论文研究的目标与容. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

第二章垃圾技术. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2.1电子工作原理简介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2.1.1电子的概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2.1.2电子的格式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2.1.3的传送过程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6

2.1.4相关协议. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8

2.2非技术手段反垃圾. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

2.3常用反垃圾技术. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

2.3.1客户端反垃圾过滤技术. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14

2.3.2服务器端反垃圾过滤技术. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14

第三章垃圾分类向量与特征向量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

3.1垃圾分类向量概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

3.2垃圾分类向量与特征向量的定义. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

3.3分类方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18

3.3.1文本量的表示方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18

3.3.2关键词的选取. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

3.3.3特征提取. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

3.3.4分类方法介绍. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

3.4基于垃圾特征向量判断垃圾算法的设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

3.4.1贝叶斯定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

3.4.2贝叶斯过滤器的工作原理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

3.4.3算法的描述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25

第四章基于标准集构造垃圾分类向量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

4.1标准集. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

4.1.1标准集的背景. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

4.1.2标准和正常的收集. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

4.1.3标准集的概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27

4.2基于标准集的垃圾分类向量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27

4.2.1分类的实现. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27

4.2.2提取分类向量的过程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28

4.2.3先验概率的计算方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31

4.2.4特征提取的实现. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31

4.3基于贝叶斯原理的过滤系统的实现. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32

4.4算法的实现. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

第五章实验结果及分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36

5.1基于贝叶斯算法的过滤系统实验环境. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36

5.2基于贝叶斯算法的过滤系统总体结构图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36

5.3实验结果及性能分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37

5.3.1系统实验结果的质量评价指标. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37

5.3.2阈值的确定及对过滤精度的影响. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38

5.3.3实验数据. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39

第六章总结与展望. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42

6.1论文总结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42

6.2待改进的问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42

致. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44

参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45

攻读学位期间发表论文情况. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47

原创性声明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48

第一章绪论

1.1引言

伴随着电子的迅速普及越来越多的人使用电子。然而 电子在为人们提供极其方便的同时也成为垃圾、病毒、恶意程序或敏感容传播的重要载体对系统安全造成了严重的威胁。

最早在1975年的RFC706‚On the Junk Mail Problem‛ [1]中就提到了垃圾首次关于垃圾的记录可以追溯到1985年8月的一封以电子发送的连锁信。历史上比较著名的事件是1994年4月份 C an t er和S i eg el的法律事务所把一封信发到6000多个新闻组宣传获得美国国绿卡的法律支持。这是第一次使用S pam垃圾一词用来描述新闻或电子的主动性发布。一些商人开始学习C an t er和S i eg el为商业公司提供广告信件和发送服务。 1995年5月 网上出现了历史上第一个专用的垃圾工具Floodgate[2] 一次可以自动把发给很多人垃圾越来越多与商业联系起来。1995年8月第一次有人公开贩卖200万个地址各种垃圾和组织也相继出现。

随着垃圾的出现和泛滥人们开始了反垃圾的不懈努力。 1996年的1月第一个反垃圾组织‚自由骑士‛成立 1996年7月著名的反垃圾S p am H au s成立例如使用REMOVE.TO.REPLY的工具来过滤地址。随着垃圾过滤技术的发展以及人们对发送垃圾者的谴责垃圾的制造者不得不采取更为隐蔽的技术比如伪造信头中的发件人、域名和地址等。然而这些方法还是逃不出IP地址的过滤。

近几年来垃圾的泛滥是由于专门发送垃圾的服务器大批涌现。根据中国互联网协会反垃圾中心的统计 2005年以来几乎每月我国都有100多台服务器被国外权威反垃圾组织列入黑[3]。中国是电子大国由于网络的开放性垃圾成为互联网上的一个日益严重的全球性安全问题越来越得到社会大众和研究人员的重视和关注。因此针对这一问题尽快寻找解决方案的需求也更加迫切。

1.2垃圾的定义及其危害

1.2.1垃圾定义

垃圾的英文名称为Spam或Junk Mail一般使用Spam一词。很多组织或机构都给垃圾下过定义。例如著名的反垃圾组织s p am h au s提出垃圾具备以下两个特征

(1)不请自来。用户事先并未提出要求或者同意接收该。

(2)批量性。该的副本在短时间被大量发送给一个或多个用户。

2003年中国互联网协会在《中国互联网协会反垃圾规》中对垃圾作了以下定