基于内容特征分析垃圾邮件过滤关键技术研究.doc

学号：2009021316姓名：赵静联系电话mail：所在学院：信息科学与工程学院硕 士 学 位 论 文论 文 题 目学科专业名称申请人姓名指 导 教 师论文提交时间基于内容特征分析的垃圾邮件过滤关键技术研究通信与信息系统赵静刘培玉 教授2012 年 6 月 15 日单 位 代 码10445学 号2009021316分 类 号TP393.08研究生类别全日制独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得（注：如没有其他需要特别声明的，本栏可空）或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：学位论文版权使用授权书本学位论文作者完全了解学校 有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 学校 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名：导师签字：签字日期：20年月日签字日期：20年月日山东师范大学硕士学位论文目 录摘 要 .IAbstract . III第一章 绪论 . 11.1 研究背景与意义 . 11.2 邮件过滤的研究现状 . 11.2.1 垃圾邮件解决方案 . 21.2.2 垃圾邮件过滤技术 . 31.3 邮件过滤面临的问题 . 41.4 论文研究工作 . 51.5 论文组织结构 . 6第二章 基于内容的邮件过滤技术基础知识. 72.1 电子邮件基础理论 . 72.1.1 工作原理 . 72.1.2 相关协议 . 72.1.3 邮件结构 . 102.2 基于内容的邮件过滤关键技术 . 112.2.1 邮件预处理 . 112.2.2 特征选择 . 122.2.3 文本表示 . 142.2.4 分类算法 . 142.2.5 反馈方法 . 152.3 过滤性能评测 . 152.3.1 评测环境 . 152.3.2 评测语料 . 152.3.3 评测指标 . 15第三章 邮件过滤中特征选择算法的分析与改进. 173.1 问题分析 . 173.2 特征选择影响因素 . 173.3 评价与结果分析 . 183.3.1 分类器的适应性 . 183.3.2 数据集依赖性 . 203.3.3 时间复杂度 . 213.4 改进的优势率方法 . 223.4.1 优势率的分析与改进 . 223.4.2 实验与结果分析 . 23第四章 结合特征与非特征信息的 Nave Bayes 邮件过滤算法 . 254.1 问题分析 . 254.1.1 朴素贝叶斯算法 . 254.1.2 存在的问题 . 254.2 结合特征与非特征信息的 Nave bayes 算法 . 264.2.1 信息提取 . 264.2.2 邮件表示 . 27山东师范大学硕士学位论文4.2.3 改进的 Nave bayes 算法 . 274.3 实验与结果分析 . 284.4 相关研究 . 29第五章 邮件过滤模块的设计与实现. 315.1 邮件过滤模块需求分析 . 315.2 邮件过滤模块设计 . 325.2.1 层次垃圾邮件过滤方案 . 325.2.2 内容过滤方案 . 335.3 邮件过滤模块实现 . 345.3.1 系统设置 . 345.3.2 工作过程 . 35第六章 总结与展望 . 37参考文献 . 38攻硕期间发表论文及科研成果. 41致 谢 . 42山东师范大学硕士学位论文基于内容特征分析的垃圾邮件过滤关键技术研究摘 要随着互联网技术的快速发展，电子邮件以操作简单、价格低廉等特点成为一种新的信息交互方式，深入人们的日常生活中。然而，日益泛滥的垃圾邮件对社会造成严重的经济损失和危害。垃圾邮件不但耗费网络资源及带宽，浪费用户的时间和上网费用，而且传播有害信息，甚至被黑客用来传播病毒。可见，研究有效地反垃圾邮件技术有着深远的社会意义和巨大的经济价值。基于内容的垃圾邮件过滤技术过滤效果较好，能及时捕捉垃圾邮件特征的变化，成为反垃圾邮件技术研究的热点。目前其在研究与应用中取得一定的成果，但仍然存在一些亟需解决的问题。(1) 数量巨大的训练样本和过高的向量维数使邮件过滤运算的时间和空间复杂度较高；(2) 基于邮件内容特征的判断具有不确定性、不及时性等缺点；(3) 基于内容的过滤技术忽略邮件的结构特征；(4) 单一技术难以满足垃圾邮件过滤的需求。这些问题使得其面对不断变化的垃圾邮件发送技术和传播手段时，性能有所下降。本文针对内容过滤中存在的以上问题展开研究，以提高垃圾邮件识别的准确率、召回率为目标，主要工作总结为以下三个方面：(1) 提出一种改进优势率的特征选择方法，减少邮件过滤运算的时间和空间复杂度。针对内容过滤中训练样本数量大和向量维数过高的问题，本文提出一种改进优势率的特征选择方法。首先，本文从分类器适应性、数据集依赖性、时间复杂度三个方面评估现有特征选择方法在邮件过滤中的性能。实验结果表明，优势率在综合评估中优于其它方法。其次，通过分析优势率所选特征及其计算公式，发现其忽略高频特征、难以选出对两个类别都有贡献的特征。最后，针对优势率的以上两个缺点，本文考虑词频因子、类别信息，改进优势率计算公式。实验证明，改进的优势率在保持邮件过滤准确率的同时，可进一步降低邮件过滤运算的时间和空间复杂度。(2) 提出一种结合特征与非特征信息的 Nave bayes 算法，提高垃圾邮件过滤的准确率。针对基于内容特征判断的不确定性和忽略邮件结构特征的问题，本文提出一种结合特征与非特征信息的朴素贝叶斯算法。该方法综合考虑邮件信头和信体对识别垃圾邮件的贡献，有效地克服了对邮件内容的依赖性，提高了邮件过滤的准确性，降低了合法邮件的误判率。在该方法中，本文首先分析邮件结构特征，从信头提取合法邮件与垃圾邮件的差异信息即非特征项，从信体提取类别区分能力强的特征项；其次，结合特征和非特征信息改进朴素贝叶斯公式并用于邮件过滤。实验证明，该方法提高了垃圾邮件识别的准确率和召回率。(3) 设计并实现层次垃圾邮件过滤模块，并将其用于邮件服务器端实施过滤。针对单一技术难以满足垃圾邮件过滤需求的问题，本文设计并实现融合多种过滤技术的层次垃圾邮件过滤模块，并将其用于邮件服务器端实施过滤。在该模块中，采用了黑白I山东师范大学硕士学位论文名单技术、关键词过滤技术、基于 Nave bayes 的邮件过滤技术，各种技术紧密合作以实施高性能的垃圾邮件过滤。其中，该模块将本文改进的关键技术融合于内容过滤中，提高了垃圾邮件过滤的准确性。关键字：邮件过滤；特征选择；优势率；朴素贝叶斯中图法分类号：TP393.08II山东师范大学硕士学位论文Research on Spam Filtering Technologies based on ContentCharacteristics AnalysisAbstractWith the fast development of internet technology, e-mail which is low-cost and simpleoperation becomes a new way to exchange information in our daily life. However, amounts ofspam mails have great impacts on societies, and often cause vast economic losses. They consumenetwork resources, waste users time and money, and even spread both harmful information andvirus. For this reason, researching effective anti-spam technology will bring far-reaching socialmeaning and huge economic value.Content-based filtering is becoming the hotspot of anti-spam technology research, becauseit has good filtration effect and catches change in spam characteristics in time. At present, It hasmade some achievements in research and application , but there are still some problems that needto be resolved. (1) The large number of training samples and high vector dimension lead to highoperation and space complexity; (2) Classifying emails by analyzing email content is uncertaintyand timeliness; (3) The structure features of email are ignored; (4) Single technology is hard tosatisfy the request of spam filtering.This dissertation does researches due to the above problems and improves filtering accuracy.The innovative work of this dissertation mainly includes the following aspects:(1) This dissertation proposes a feature selection approach based on improved odds ratio,which reduces the operation time and space complexity.Due to the problem that operation time and space complexity are high in content-basedfiltering, this dissertation improves odds ratio to selecte feature items. Firstly, this dissertationevaluates the following aspects of feature selection methods which used to filter emails:classifier adaptability, data set dependence, time complexity. Experimental results show that oddsratio is better than other methods. Secondly, it analyses feature items selected by odds ratio andcomputational formula of odds ratio, which show that the odds ratio is hard to select the featureitems with high word frequency or feature items contributing to two categories. Finally, due tothe above problem of odds ratio, it improves the computational formula of odds ratio byanalyzing frequency factor and categorie information. Experimental results indicate that theimproved odds ratio shows a further decline in operation time and space complexity, while theprecision of spam filtering is still high.(2) This dissertation proposes an improved nave bayes algorithm combining feature withIII山东师范大学硕士学位论文noncharacteristic information, which increases the precision of spam filtering.Due to the problems that content-based filtering has uncertainty of classifying emails byanalyzing email content and ignores structure features of email, this dissertation proposes animproved nave bayes algorithm combining feature with noncharacteristic information. Theimproved algorithm considers the contributions of email header and body between ham andspam, which overcomes the dependence of classifying emails by analyzing email content,increases the precision of spam filtering, and reduces the false rate of ham emails. In this method,this dissertation firstly analyzes structure features, extracts noncharacteristic information, whichare different attributes of fields in email header between ham and spam, and selects typicalfeature information from email content; then, it combines feature with noncharacteristicinformation to improve the formula of nave bayes. Experimental results show that the approachimproves the recall and precision of spam filtering.(3) This dissertation designes and realizes multi-layer spam filtering modules, and uses it inmail server to filter spam emails.Due to the problem that single technology is hard to satisfy the request of spam filtering,this dissertation designes and realizes multi-level spam filter modules, which is a collection oftechnologies, and applys it in mail serve to filter spam emails. In this module, it includesblacklist and whitelist technology, key words filtering, content-based filtering. All kinds oftechnology cooperate perfectly to do high performance of spam filtering. In especial, thecontent-based filtering modules use these improved approaches of the dissertation, whichimproves the filtering veracity.Keywords: Spam Filtering; Feature Selection; Odds Ratio; Naive BayesIV山东师范大学硕士学位论文第一章 绪论1.1 研究背景与意义互联网时代，电子邮件以操作简单、投递迅速、价格低廉、全球通讯便捷等特点成为一种新的信息交互方式，已深入人们的日常生活中。通过第 28 次中国互联网络发展状况统计报告的数据我们可以看到：中国网民的数量逐年增加，截止到 2011 年 6 月底网民数量高达 4.85 亿，网络普及率提升至 36.2%；电子邮件用户规模达 25172 万人，使用率为51.9%1。电子邮件成为人们相互交流的主要工具之一。然而，用户在事先没有订阅或同意接收的情况下，经常收到大量的广告、各种带有宣传性质的电子邮件以及隐藏发件人身份、地址或含虚假信息源、路由信息的电子邮件。这些邮件通常是一些公司、团体或个人为获取商业利益或达到政治目的而向用户发送的，被定义为垃圾邮件。大量的垃圾邮件耗费网络资源及带宽，损害 ISP 的市场形象，阻碍有效信息的传播，浪费用户的时间和上网费用，传播的虚假或有害信息甚至危害青少年的健康成长等。这破坏了和谐的网络文明，对社会造成严重的危害。Symantec Intelligence Report:July 2011 显示，2011 年 7 月垃圾邮件占全球邮件总量的77.8%，较六月份上升 4.9%2。Nucleus Research 研究机构的科学计算指出：电子邮箱用户大约用时 16 秒来处理一封垃圾邮件，依此比例计算，企业每年因垃圾邮件问题造成的经济损失达 700 亿美元。中国互联网协会反垃圾邮件中心发布的 2011 年第一季度中国反垃圾邮件状况调查报告显示：中国网民平均每周收到 13.8 封垃圾邮件，垃圾邮件占总收到邮件数量的 40.1%；超过 66%的用户收到了“欺诈”类型的垃圾邮件；每周需花费 7.9 分钟识别和删除垃圾邮件3。可见，研究有效地反垃圾邮件技术有着深远的社会意义和巨大的经济价值。目前，为解决垃圾邮件问题，国内外学者或研究机构提出黑白名单过滤技术、基于规则的内容过滤技术、基于统计的内容过滤技术、身份认证技术、基于行为识别的技术等多种反垃圾邮件方法。其中，基于统计的内容过滤技术过滤效果较好，能够及时捕捉垃圾邮件特征的变化，人工干预少，在反垃圾邮件的过程中发挥重要作用，成为国内外研究的热点。但随着垃圾邮件制造者不断变换垃圾邮件的发送和传播手段，传统的基于统计的内容过滤性能有所下降。因此，深入分析邮件结构特征、邮件内容特征、垃圾邮件过滤技术，总结邮件过滤中面临的问题，研究并改进基于内容的垃圾邮件过滤关键技术，提高垃圾邮件的召回率和准确率，对有效防止垃圾邮件具有重要的现实意义。1.2 邮件过滤的研究现状目前防范垃圾邮件的方法主要总结为三个方面：制定反垃圾邮件法规、成立反垃圾邮件组织和研究反垃圾邮件技术。1山东师范大学硕士学位论文1.2.1 垃圾邮件解决方案1. 反垃圾邮件法规目前，国内外一些国家通过颁布和实施反垃圾邮件法律，有效制裁垃圾邮件制造者，从源头上阻止垃圾邮件。在国外，美国 2003 年制定了反垃圾电子邮件法案，欧盟 2002年批准了反垃圾邮件及保护在线隐私权法，波兰、新西兰政府也开始实施新的法律法规，以严厉处罚垃圾邮件发送者。在国内，2006 年 3 月信息产业部公布实施互联网电子邮件服务管理办法。2. 反垃圾邮件组织目前，国内外已成立多个规模不等的反垃圾邮件组织。国外较权威的组织有 spamhaus、Coalition Against Unsolicited Commercial Email (CAUCE)、Mail Abuse Prevention System(MAPS)等，国内成立了中国教育与科研网络中心反垃圾邮件小组、中国反垃圾邮件联盟、中国互联网协会国家反垃圾邮件中心等组织。它们在一定程度上缓解了垃圾邮件的危害，在全球反垃圾邮件工作中发挥领导作用。3. 反垃圾邮件技术反垃圾邮件技术是企业和用户防范垃圾邮件最有效的措施。目前，国内外学者或研究机构主要从根源阻断和邮件过滤两个方面对反垃圾邮件技术进行研究，并取得一定的研究成果。(1) 根源阻断“根源阻断”是指从发件源头阻止垃圾邮件的发送。它不但可以帮助用户摆脱垃圾邮件的困扰，还可以减少服务器的信息处理量，节省网络资源，减轻服务器负担。常采用的方法有增加邮件的发送成本和修改现有的邮件传输协议。垃圾邮件发送具有大规模发送、成本小的行为特征。为遏制垃圾邮件，一方面可以增加垃圾邮件发送的经济成本，如微软公司提出了对发送邮件进行收费的解决方案，但这种方式对正常邮件发送者带来了新的负担；另一方面，可以增加垃圾邮件发送的时间成本，如采用 challenge-response 方式。针对 SMTP 协议没有提供认证等功能的缺陷，Meng Weng Wong 结合了反向 MX 域名解析(Reverse MX) 和 DMP (Designated Mailer Protocol) 的优点，于 2003 年提出 SPF（Sender Policy Framework）来防止伪造邮件地址4；qmail 的开发者 D. J. Beernstein 通过制定新的邮件传输协议 Inernet Mail 2000 以减少垃圾邮件的危害。该协议的基本思想是把邮件存储在发送端，接收者到发送端去取邮件，其相对复杂，实施难度较大5-7。总之，无论是修改 SMTP 或是制定新的协议，只有被全球共同采用时才能有效防止垃圾邮件，实施起来相对困难。(2) 邮件过滤邮件过滤技术根据已产生邮件的格式、发送特点、文件大小、邮件内容等特征，来区分邮件的性质。目前国内外学者主要从垃圾邮件行为识别技术、基于规则的过滤技术、基于统计的内容过滤技术三方面进行研究。2山东师范大学硕士学位论文1.2.2 垃圾邮件过滤技术1. 垃圾邮件行为识别技术国内外对基于行为的邮件识别技术研究主要从邮件拓扑行为和邮件发送行为两个方面进行。基于拓扑的方法采用图论知识分析合法邮件与垃圾邮件在拓扑图中的差异，来识别垃圾垃圾邮件；基于行为的方法通过分析 SMTP 的会话信息、电子邮件报文的相关数据信息，来挖掘垃圾邮件的行为特征，从而识别垃圾邮件。赵治国等根据垃圾邮件大量发送行为特征，提出基于 P2P 协作的垃圾邮件行为识别技术8。白秋颖等采用决策树算法分析网络会话层数据以找出垃圾邮件的行为特征，并在邮件内容信息发送前实施过滤，该方法能有效地解决垃圾邮件占用网络带宽的问题9。总之，基于行为的邮件识别技术通过分析大量垃圾邮件样本来建立垃圾邮件行为模式数学模型。该方法在理论计算上有较高的区分度，在实际应用中不需要扫描邮件的全部内容，节省了垃圾邮件的处理时间102. 基于规则的过滤技术基于规则的过滤方法是通过与预先设定的规则相比较来判定是否为垃圾邮件，常见的过滤方法有黑白名单技术、关键词过滤技术、基于机器学习的技术等。(1) 黑白名单技术黑名单中记录了已知垃圾邮件制造者及其 ISP 的域名或 IP 地址。通常将其部署在网关处，这样就可以拒绝任何黑名单上已存在的垃圾邮件制造者的邮件。相反，使用白名单的用户只能接收来自白名单上允许接入的邮件。(2) 关键词过滤技术关键词过滤的基本思想是将待判断邮件特征与预先创建的与垃圾邮件关联的关键词列表相匹配来识别垃圾邮件。该方法具有明显的缺陷：一是关键词表的创建需要收集大量垃圾邮件样本；二是简单的匹配易造成误判，且垃圾邮件发送者通过拆词、关键词变形等方式易绕过过滤。(3) 基于机器学习的技术基于机器学习的技术利用机器学习中的智能算法从大量训练样本中提取有规律性的特征生成过滤规则，并利用该规则判断新到达的邮件是否为垃圾邮件。常用的智能算法有Ripper 算法、决策树、Boosting 算法、粗糙集等。文献11采用 Ripper 算法识别垃圾邮件，其垃圾邮件判别准确率高于 80%；Carreras 等人12采用决策树识别垃圾邮件，其准确率在88%左右；刘洋等人13采用非文本属性(收件人个数、主题字数等)进行邮件分类，并利用粗糙集进行过滤，达到 80%以上的正确率。总之，采用这种方式过滤效果好，实现简单，其缺点也较为明显，表现在以下三个方面：一是规则需要手工制定或采用某种技术创建和维护，对用户的技术要求较高；二是规则的制订总是落后于垃圾邮件特征的变化，需要不断的调整规则，实时更新代价大；三是垃圾邮件制造者通过关键词变形、拆分等手段易逃避规则过滤。3. 基于统计的内容过滤技术3。山东师范大学硕士学位论文基于统计的内容过滤方法根据邮件内容特征的统计特性自动分类邮件，是文本分类技术的应用之一。常采用的文本分类算法有贝叶斯(Bayesian)、支持向量机(Support VectorMachine, SVM)14、K 近邻(K-Nearest Neighbor, KNN)15、Rocchio 等。Androutsopoulos16在 Ling-Spam 邮件语料上采用 Nave bayes 算法得到垃圾邮件的召回率为 81.10%，正确率为 96.85%；Konstantin Tretyakov17在 pul 邮件语料上采用支持向量机算法得到垃圾邮件的召回率 97.7%，正确率 97.9%；采用 KNN 算法的召回率为 93.1%，正确率 86.8%。总之，基于统计的过滤算法性能较好，通过及时更新训练样本集，分类器的更新速度能跟得上垃圾邮件出现的速度，时效性较强。近年来，研究学者将合作理论引入内容过滤中，为垃圾邮件过滤增添新的思路。合作过滤技术通过分布在各地的防垃圾邮件网关之间的协同工作，来减少垃圾邮件的危害。此外，随着垃圾邮件过滤技术的研究和发展，发件人特征识别技术、多重图片识别技术、意图分析技术等新型过滤技术也应用于垃圾邮件识别中。综上所述，每一种过滤