（计算机应用技术专业论文）基于信息熵的反垃圾邮件技术研究.pdf

t h e s i ss u b m i t t e dt ot i a n j i n u n i v e r s i t yo ft e c h n o l o g yf o r t h em a s t e r sd e g r e e r e s e a r c ho n a n t i s p a mt e c h n o l o g y b a s e do ns h a n n o n e n t r o p y b y l it i n g s u p e r v i s o r w a n gc h u n d o n g j a n u a r y 2 0 10 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得天洼理工大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 f 学位论文作者签名：鸟户寺亚签字日期：29 ，d 年乡月 参日 学位论文版权使用授权书 本学位论文作者完全了解 墨盗墨墨盘堂有关保留、使用学位论文 的规定。特授权墨盗墨墨太望 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：吾书l 导师签名：赫岛 i 签字日期：o d 年弓月 6 日签字日期：2 口f 口年专月易日 摘要 当前国内的网络安全事件频频发生，垃圾邮件的泛滥成为其中显著的特点之一。传 统的反垃圾邮件方法以基于内容的过滤为主，按照基于统计和基于规则划分为多种算 法。但这些方法都有一定的局限性，难以在过滤邮件的效果上做到有效性和速度兼顾。 本文在贝叶斯分类的基础上，引入了信息熵的概念，在邮件服务器前端建立一个多层过 滤反馈系统，从邮件自身的行为参数和内容识别上来辨别垃圾邮件与合法邮件，在原有 贝叶斯分类的基础上降低了误检率，提高了正确率。 本文的研究工作主要包括以下三个方面： 首先对朴素贝叶斯进行了改进，采用了多级属性关联的依赖机制，提高了其在现实 问题中的可行性和适用性。另外对p o l y t r e e 传播条件下的复杂贝叶斯网络进行分析， 使用并行处理计算对输入信度进行了有效的处理和计算，得到了较好的性能结果。 论文将信息熵的理论应用到邮件过滤上，利用垃圾邮件的群发特性和其随机性小的 特点，对邮件的行为参数进行一系列计算，根据判断结果对邮件进行过滤。 最后实现部分对前面几个过滤方法进行了整合，建立一个邮件过滤系统。在进行邮 件分词、主成分分析的特征约简的基础上，依次进行熵计算模块和贝叶斯模块的过滤， 最终得到较好的邮件分类结果。从实验结果来看，取得了预期的效果，在处理效率上得 到了提升，具有一定的实用价值。 关键词：垃圾邮件贝叶斯信息熵参数计算 a b s t r a c t a tp r e s e n tn e t w o r ks e c u r i t ye v e n t sh a v ei n c r e a s e dr a p i d l y t h es p r e a do fs p a r e si so n eo f t h e s eb a di n c i d e n t s t h et r a d i t i o n a la n t i - s p a mt e c h n o l o g i e sa r em a i n l yb a s e do nt h ef i l t e r i n g o fm a i lc o n t e n t s a n dt h e ya r ed e v i d e di n t ob a s e do nt h es t a t i s t i c sa n db a s e do nt h er u l e s b u t t h e s em e t h o d sh a v ec e r t a i nl i m i t a t i o n s ，a st h e yc a n tw o r kw e l lo ne f f e c t i v e n e s sa n d s p e e d n e s ss i m u l t a n e o u s l y i nt h i sp a p e rw ei n t r o d u c es h a n n o ne n t r o p yt os o l v et h i sp r o b l e m w eb u i l dac o m p o s i t i v ef i l t e rs y s t e mt od i s t i n g u i s hs p a m si nf r o n to fm a i ls e r v e r s ，b a s e do n m a i l s b e h a v i o rp a r a m e t e r sa n dc o n t e n t s i tr a i s e sa c c u r a c yr a t ea n dr e d u c e sf a l s er a t e t h i sp a p e rm a i n l yi n c l u d e st h r e ea s p e c t sb e l o w ： f i r s t l yi ti m p r o v e sn a i v eb a y e sa l g o r i t h mb ya d o p t i n gm u l t i l e v e la t t r i b u t e sr e l a t e d ，a n d e n h a n c e si t sp r a c t i c a b i l i t ya n da p p l i c a b i l i t y o nt h eo t h e rh a n di ta n a l y s e sb a y e sn e t w o r ki n t h ep o l y t r e ec o n d i t i o n u s i n gp a r a l l e lp r o c e s s i n gi tc o m p u t e st h ei n p u tm e s s a g e sa n dg e t sa g o o dp e r f o r m a n c e s e c o n d l y , a c c o r d i n gt os p a m s c h a r a c t e r s ，t h ep a p e ru s e ss h a n n o ne n t r o p yw h i c hi sa l s o c a l l e di n f o r m a t i o ne n t r o p y a ss p a mh a v i n gb e e ns e n tr e g u l a r i t yw i t hl o w e rr a n d o m n e s s ，t h e p a p e rc a l c u l a t e ss o m ec h a r a c t e r sp a r a m e t e r so fm a i l s ，a n df i l t e r ss p a r e so nt h eb a s i so ft h e r e s u l t s a tl a s t ，t h ee x p e r i m e n tp a r ti n t e g r a t e sm o d u l e st ob u i l dac o m p r e h e n s i v ee m a i lf i l t e r i n g s y s t e m a f t e rm a i lp a r t i c i p l ea n dp r i n c i p a lc o m p o n e n ta n a l y s i s ，t h es y s t e mc a l c u l a t e se n t r o p y o fm a i lp a r a m e t e r sa n du s e st h eb a y e sc l a s s i f i c a t i o n f r o mt h ee x p e r i m e n tr e s u l t s ，t h es y s t e m h a sg o ta e x p e c t a n te f f e c ta n di m p r o v e dt h ee f f i c i e n c y s oi th a sap r a c t i c a lv a l u e k e yw o r d s ：s p a mb a y e s s h a n n o ne n t r o p y p a r a m e t e rc o m p u t i n g 目录 第一章引言1 1 1 背景1 1 1 1 垃圾邮件的定义1 1 1 2 垃圾邮件的产生和危害1 1 2 解决方法和问题2 1 3 本文的结构安排3 第二章反垃圾邮件技术现状4 2 1 黑白名单过滤5 2 2 关键词过滤5 2 3 基于行为模式的过滤5 2 4 基于内容的过滤6 2 4 1 基于规则的方法6 2 4 2 基于统计的方法7 2 5 本章小结7 第三章贝叶斯网络8 3 1 改进的朴素贝叶斯8 3 2p o l y t r e e 条件下的邮件特征网络一1 0 3 2 1b a y e s 邮件特征网络一1o 3 2 2p o l y t r e e 1 0 3 2 3 并行处理计算1 l 3 2 4 性能测试1 3 3 3 本章小结15 第四章基于香农熵的特征研究1 6 4 1 主成分分析16 4 1 1 原理16 4 1 2 步骤16 4 2 香农熵。18 4 3 香农熵在邮件过滤上的应用2 0 5 1 实验环境2 2 5 2 系统流程图一2 4 5 3 模块设计一2 4 5 3 1 预处理模块2 4 5 3 2 熵计算模块2 5 5 3 3 贝叶斯分类模块2 5 5 4 性能分析2 6 5 5 本章小结。2 9 第六章全文总结和未来展望3 0 6 1 全文总结3 0 6 2 未来工作一3l 参考文献3 2 发表论文和科研情况说明3 5 致谢3 6 第一章引言 1 1 背景 第一章引言 跨入2 1 世纪的大门后，互联网技术飞速发展，电子邮件成为现代社会便捷沟通方 式的代表。但随之而来的是其衍生物垃圾邮件的出现和泛滥。截至2 0 1 0 年，垃圾邮件 已成为影响互联网安全的几大威胁之一。当今互联网愈加商业化，企业与消费者直接打 交道，对社会造成的影响越来越大。 2 0 0 9 年4 月1 日至3 0 日短短3 0 天内，c n c e r t c c 收到国内外电子邮件、热线电 话、网站提交、传真等方式报告的网络安全事件1 9 1 3 件( 不含扫描类事件，也合并了 通过不同方式报告的同一网络安全事件) ，其中来自国外的事件报告有1 9 1 0 件。4 月网 络安全事件大幅增加，其主要原因是垃圾邮件报告数量急剧上升，相比3 月增长了一倍 以上。通过不同接收方式接收事件报告的具体数量，可以看出通过邮件报告事件的数量 最多。在1 9 1 3 件事件报告中，垃圾邮件的威胁占较大比例，4 月为1 5 4 2 件，较3 月增 长1 4 2 【l 】。 起初垃圾邮件只是少数人通过群发制造一些广播消息，但现在它已占用很大一部分 的服务器空间和流量带宽。这损害了用户利益，侵犯了个人隐私和安全，产生了及其恶 劣的商业形象，并给邮件服务器的安全和网络本身的可信度造成了严重的威胁。部分垃 圾邮件经常传播黄色和反动信息，对社会治安和文明也造成了极大的隐患。如何有效地 对垃圾邮件进行检测和防范，已经成为当今网络安全领域的重要话题。 1 1 1 垃圾邮件的定义 中国互联网协会反垃圾邮件规范【2 】将四种邮件称为垃圾邮件：第一种：用户没 有主动订阅而发送给用户的广告以及一些宣传资料：第二种缺少相关发送者的信息；第 三种：用户无法拒收的；第四种：捏造不实信息的。 对于一般用户而言，垃圾邮件主要是指第一种，即“不请自来的大宗邮件( u n s o l i c i t e d b u l ke m a i l ，u b e ) 、“不请自来的广告邮件( u n s o l i c i t e dc o m m a c i a le m a i l ，u c e ) ，其 带有显著的商业目的或政治目的。实际上，垃圾邮件的判定会因人而异，不同的用户的 需要不同，对同一邮件的判定结果也会存在差异 1 1 2 垃圾邮件的产生和危害 垃圾邮件之所以在网上出现并泛滥丌来，是由其背后蕴含的巨大经济利益所指使的。 垃圾邮件发送者( s p a m m e r ) 会用专门的地址搜索软件在网上进行电子邮件地址的 搜索和收集，然后通过群发软件或僵尸网络控制的“肉鸡 主机【3 】来完成垃圾邮件的发 送。一个邮件地址搜索软件每次可以搜索到几万至十几万个邮件地址。作为发送方来说， 第一章引言 邮件的成本极其低，相比发传单等传统需要发送方本身耗费大量金钱和人力资源的方 式，这只需要少量资源就可以完成，而且成本是追加在邮件收件方的头上。虽然回报率 也很低( 一千万封电子邮件广告之后可能只产生1 0 0 个销售量) ，但相对来说，发送商 业性质的垃圾邮件还是有利可图的。这证明了垃圾邮件会在很长一段时间存在并发展 着，反垃圾邮件研究是一项长期而艰巨的工作。 对垃圾邮件发送者而言，区区的几封邮件就可以取得可观的经济利润和良好的宣传 效果。对用户和网络公司来说，垃圾邮件意味着每年2 0 亿美元的经济损失和恶劣影响。 h 其危害主要表现在3 个方面：( 1 ) 网络资源是有限的。垃圾邮件的传输会占用有限的 带宽，从而使网络传输的负载增大；而毫无意义的垃圾邮件的保存会占用邮件服务器的 磁盘空间，造成不必要的开销。如果不使用有效的方法遏制垃圾邮件，任其在用户邮箱 中蔓延，那么开发电子邮箱的最终目的方便用户就无从谈起了。这样只会有一个结果 就是使用户远离邮箱。这种情况无论对用户还是对邮件提供商都是一个损失。另外一种 现实情况是用户通过邮件服务器发送垃圾邮件可能造成服务器地址被禁用。( 2 ) 毫无价 值的垃圾邮件的清理会占用用户的时间和精力。因为邮箱的空间是有限的，为了使有限 的网络空间发挥最大的价值，用户不得不额外的抽出时间去清理垃圾邮件。( 3 ) 对网络 安全形成威胁。一些垃圾邮件传播色情、反动等有害信息，给社会的稳定带来了隐患。 黑客们通过电子邮件发送数以万计的恶意代码来攻击目标，受害机器形成僵尸网络，使 服务器瘫痪。 1 2 解决方法和问题 由于垃圾邮件的危害，给人们带来了很多不便。针对这一问题，人们主要采用的方 法是： 1 采用法律的手段。在法律上，针对垃圾邮件给用户造成损失的不同，给垃圾邮 件的发送者以相应的惩罚。只有明确的法律规范，才能使人们对自己的行为有一个强制 的约束，从根本上减少垃圾邮件产生的可能性。 2 采用技术的手段。主要是垃圾邮件过滤，这是本文重点涉及的内容，详情在后 面会提到。 反垃圾邮件的工作任重而道远，归纳起来目前存在的主要问题有： 1 如何降低反垃圾邮件的成本。现在从事大规模电子邮件服务的企业绝大多数采取 了反垃圾邮件的技术措施和管理措施，在邮件系统上安装了反垃圾邮件的设备并还有专 门的人员负责处理问题，对于上千万用户级的服务商，每年为反垃圾邮件财务的支出都 超过了几百万人民币的数额。因此可以说，目前反垃圾邮件的成本和发垃圾邮件的成本 相比要高昂的多。 2 关于垃圾邮件的标准有待完善。垃圾邮件的管理涉及公民的基本权利，包括在对 垃圾邮件的犯罪行为取证时如何保护信息所有权和用户隐私权，在可行性上有一定难 度。还有法律空白的问题，就是如何判断和定性垃圾邮件的犯罪问题。 3 反垃圾邮件的各种方法目前都不太成熟，普遍存在性能或应用上的瓶颈限制，需 第一章引言 要继续深入研究新的、更可靠的反垃圾邮件技术。现有技术手段在防堵垃圾邮件上存在 技术缺陷，比如黑白名单技术、简单内容过滤和阻碍i p 段地址等传统技术已经被全球 电子邮件服务商反复使用，目前成效已经不够显著。垃圾邮件发送者也在不断升级他们 的策略和技术手段，以及通过有组织的行动，常常破解如依靠黑名单公布方式过滤的系 统，冲破对垃圾邮件的封锁【5 】。如果能找到一个在过滤性能和资源使用两者上做的都比 较出色的理论算法，可以说对解决当前垃圾邮件的泛滥有重大意义。 1 3 本文的结构安排 本文共分六章。 第一章为概述，介绍了了垃圾邮件的定义，以及它产生的原因和造成的危害。并简 单介绍了垃圾邮件发展现状，说明了研究反垃圾邮件过滤技术的紧迫和重要性。 第二章介绍了国内外当前反垃圾邮件的多种技术，每种技术的特点，所具有的优势 和缺陷在哪里，逐渐引入本文的重点之一贝叶斯理论，为下一章的研究打下铺垫。 第三章对传统的朴素贝叶斯分类进行改进，并研究了对p o l y t r e e 条件下的复杂贝叶 斯网络如何处理，使用并行处理算法，得到了较好的测试结果。 第四章介绍基于特征分析的过滤技术，引入了信息熵的概念，使用主成分分析法对 数据源进行特征约简，通过对特征参数的信息熵计算，对邮件进行较好较快的分类。 第五章为实验部分，在综合了贝叶斯分类和信息熵两种技术的基础上，设计实现一 个综合的邮件过滤系统，描述了相关的实验环境和工具，得出了实验结果，通过分析计 算证明了系统的有效性和实用性。 第六章为结论部分，总结本文所做工作并给出结论，并在其基础上，提出邮件过滤 上的个人见解。针对本文不足，对未来工作进行展望，以进行更完善的细化和实践工作。 第二章反垃圾i l t g f t ：技术现状 第二章反垃圾邮件技术现状 当前的反垃圾邮件技术试图通过有效正确地识别垃圾邮件与合法邮件，找出垃圾邮 件的来源和产生渠道，来降低垃圾邮件造成的恶劣影响。这些方法采取多种安全途径来 阻止垃圾邮件。现在主流的反垃圾邮件技术一般有以下四类：反向d n s 查询、验证查 询、挑战技术和过滤技术。 1 反向d n s 查询：垃圾邮件为了隐藏自己，不被用户和过滤器发现自己的域名身 份，经常通过开发转发( o p e nr e p l y ) 的功能使用别的服务器地址，向外发送邮件。这时 就需要用反向d n s 查询，根据邮件最先的i p 地址对其进行解析，查出其真正的来源。 如果其来源与它声称的域名地址不符时，就判定为垃圾邮件。 2 验证查询：验证查询是指通过验证查询发送者邮件地址、域名或身份的真实性、 合法性来判断所发送邮件是否是垃圾邮件。这种通过限制垃圾邮件源地址的方式主要存 在着两方面问题：一是错误的判断系统自己产生的邮件，因为很多邮件不能自动响应并 发送邮件地址、域名或身份。二是对于采用了询问并回应技术的邮件，可能产生死循环 情况，被抛弃。 3 挑战技术：挑战技术会采用例如电子证书的方式来验证该邮件的合法性，它能 大大延缓邮件的发送和处理过程，来阻碍垃圾邮件发送者大量群发邮件，致使其成本过 高。但它的不足之处在于：对于普通用户，会带来使用上的不便。而那些需要群发邮件 的合法发送者，可能就不使用电子邮件进行信息传送，因为它太耗费时间。这一技术只 有在一些特定场合下能得以使用。另外，当此时使用挑战技术处理大批量的垃圾邮件 时，同时也降低了正常邮件的处理速度。 4 邮件过滤技术 目前使用比较广泛的是垃圾邮件过滤技术。它是一种应用于接收端，通过各种算法 对邮件进行分类过滤，一种原理比较简单的处理技术。主要包括：黑白名单过滤，关键 字过滤，h a s h 技术，基于规则的过滤，基于内容的过滤等。 反向d n s 查询如果碰到具有动态i p 和域名地址的垃圾邮件发送者就显得无能为 力，因为垃圾邮件发送者不需用通过隐藏自己的身份就可以发送垃圾邮件。验证查询是 通过改善垃圾邮件泛滥的环境，改进通信协议中不足的地方，增强安全认证性能，来阻 止垃圾邮件的发送。出发点是好的，但现在的邮件协议根深蒂固，动一发而乱全身，很 难在根本上得以改善。挑战技术使用经济制裁和增加时间上的耗费，使垃圾邮件发送者 在大量发送垃圾邮件时，要面对额为的负担和难度。这使得通过垃圾邮件来获得商业利 益和恶意目的得不偿失。但这种方法会给普通用户收发合法邮件带来了极大的不便，违 背了电子邮件快速方便的初衷，现实可行性不高。而过滤分类是用算法技术检测出垃圾 邮件，在服务器接收前就过滤，用户不会收到这些邮件。前三种方法或从根本出发，或 以增加垃圾邮件发送者的代价，主动的防范垃圾邮件的产生，但实现起来难度较大，可 第二章反垃圾邮件技术现状 行性不高，存在许多技术和应用上的瓶颈。而过滤技术虽是被动的防范，只能在垃圾邮 件收到后进行识别和过滤，但这一块实现起来较易，可行性较高，在前几种方法并不能 有效奏效时具有良好的实用性，本文的研究重点也着力于此。 过滤技术一般分为以下几类：黑白名单过滤、关键词过滤、基于行为模式和过滤和 基于内容的过滤。 2 1 黑白名单过滤 黑白名单过滤【6 】是指对邮件的邮箱地址、发送i p 地址或网段进行黑白名单设置，凡 是被列入黑名单的邮件将不予接收，而列入白名单的邮件则不会受任何限制。一般的邮 件服务器都有自己的黑白名单，如网易、亿邮等，名单由一些比较有信誉的组织定期提 供地址，也可以由企业自己对邮件进行甄别和设置。中国反垃圾邮件协会和网易合作， 定期在主页上公布此段时间内所找出的垃圾邮件的服务器名单及i p 地址。个人也可以 根据个人原因和需求来设置自己的黑白名单。 黑白名单虽简单有效，但也有其局限性。一般垃圾邮件会利用一些开发的代理中继 服务器或伪造自己的地址域名，这一就给维护实时黑名单列表( r b l ，r e a lb l a c kl i s t s ) 带来了困难。不断变换的垃圾邮件地址需要维护者对r b l 进行不断的更新升级。如果 一个垃圾邮件发送者通过i s p 拨号上网，通过服务商提供的服务器登录到邮箱上发送垃 圾邮件，则该服务商的服务器会被认为是垃圾邮件源地址，列入黑名单予以禁用，造成 大量合法用户无法j 下常收发邮件。 2 2 关键词过滤 关键词过滤技术通常创建一些简单或复杂的与垃圾邮件关联的单词表来识别和处理 垃圾邮件。这种技术是根据在邮件头、邮件主题行或者邮件正文中的是否含有设定的关 键字符来判断邮件是否为垃圾邮件，然后采取处理措施。关键字符分为代表垃圾邮件类 的关键字符和代表正常邮件类的关键字符。关键字符可以是词、字符串或特定的符号等。 这种技术非常简单易行，现在的邮件客户端一般都提供这种技术。但其弊端和局限 也非常明显，一是其维护起来困难。当前垃圾邮件为了避免过滤，其内容也在发生变化， 技术也在改进，如拆字( “胡”拆为“古月 ) 、谐音字。过滤词列表需要每月甚至每日 更新，过于庞大。二是错报率高。相同的字词经过不同组合，出来的意思完全不同。如 果依据字词全部过滤，会造成很高的误检率，这是用户不能接受的。 2 3 基于行为模式的过滤 基于行为模式的过滤是通过邮件的群发性和是否含有大量图片来判别垃圾邮件。当 前的垃圾邮件发送者会采用穷举法来对邮件服务器的邮箱地址来批量批次发送垃圾邮 第二章反垃圾邮件技术现状 件，如果一个邮件服务器短期内收到的海量邮件都是从同一个邮件地址或同一个i p 地 址发来的，就能初步判定该地址为垃圾邮件发送地址，予以禁用，收到的邮件也为垃圾 邮件。如果一个邮件包含图片很多，一般都是含有商业性质的广告邮件，也可以予以过 滤。 这种方法的缺点是无法针对垃圾邮件发送源对不同服务器的邮件地址进行的攻击。 如果用户希望收到公司发来的商品广告邮件，也不应过滤，会造成误判。 2 4 基于内容的过滤 基于内容的过滤是当前常用的过滤技术，它对邮件标题和正文的内容进行分析，以 此来判断邮件是否为合法邮件。当f ； 的邮件服务器和客户端上大都使用了该技术，但它 存在一定的漏报率和错报率，需要在技术上加以改进。 当前基于内容的过滤从判别技术上可分为两大类，即基于概率统计和基于规则的方 法。后者是比较老的方法，通过一些显式规则来绝对地分辨邮件。f i 者通过一系列计算 来得出某一个邮件与垃圾合法邮件的契合率，超过或低于该标准就能被判断该邮件的性 质。基于概率统计是从基于规则发展而来，是后者的引申和发展。 基于内容的过滤需要一定量的数据源作为训练集来建立初始的判断标准，再将判断 标准对之后接收的邮件流量进行判断，并同时根据实际情况和用户需求，不断对结果进 行反馈和优化，以改进过滤结果的正确率和误判率。 2 4 1 基于规则的方法 ( 1 ) 决策树分类。决策树( d e c i s i o n t r e e ) 是种由结点和有向边组成的层次结构， 它通过一系列测试条件来逐步解决分类问题。每一个条件的答案将决定下一步的选择， 直到找到最后的分类标号。一开始的状态被定为根结点，中间状态被定为内部结点，最 后的分类标号被定为叶结点。决策树一旦构造，就通过属性判别对检验记录进行分类。 决策树常用的策略是贪心策略，如h u n t 算法，它是许多常用决策树算法的基础，如i d 3 、 c 4 5 和c a r t 。c a r r e r a s 首先使用决策树来分辨垃圾邮件【9 】，得到的准确率和正确率为 8 8 左右。 ( 2 ) 组合( b o o s t i n g ) 方法。通过聚集多个分类器的检测来提高分类准确率，被称 为组合。首先由训练数据构造一组基分类器，然后对这些分类器进行加权求和，以投票 的方式进行分类。这比其中的任何单分类器的效果要好。常用的组合方法有a d a b o o s t 1 3 】。 而c a r r e r a s 和n i c h o l a s 的实验证明了组合方法在邮件过滤上有着很好的效果。而 a n d r o u t s o p o u l o s 4 1 通过l o g i t b o o s t 组合方法对邮件过滤进行研究。d e s o u z a 1 5 】的实验证 明了包含基分类器为决策树的组合方法对l i n g s p a m 语料的过滤准确率很高( 大于 8 8 ) 。组合方法的局限之处在于它的训练速度较慢。 第二章反垃圾邮件技术现状 2 4 2 基于统计的方法 ( 1 ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) ，这是利用统计学进行分类的一 门新兴技术。它利用构造最大边缘超平面来应用到分类数据上。支持向量机在解决非线 性和小样本学习以及高维分类识别问题应用较广。对于线性分类，s v m 一般先寻找最大 边缘超平面，而非线性分类，s v m 通过一个变化将原问题转换到一个新的线性可分的空 间。s v m 在文本分类中应用较广。d r u c k e r n 引证明了，采用二值标示的s v m 性能比多维的 要好，并将其应用于邮件检测过滤领域。以后的a n d r o u t s o p o u l o s l l 7 】和k o l c z j 也对s v m 在邮件过滤上的作用进行了研究。 ( 2 ) 贝叶斯( b a y e s i a n ) 分类，它是一种把类的先验知识和数据源中提取的新证 据相结合得出的统计原理，再用该原理来进行分类的一种方法。在解决属性集和类变量 间关系不确定时，贝叶斯分类有良好的应用。因此，贝叶斯理论在邮件过滤上有着广泛 的应用。s a l l 锄i 【l9 】使用朴素贝叶斯，对邮件的词汇、词组特征及其他属性进行分类，并 表明了邮件二值区分的结果要胜于多值区分。a n d r o u t s o p o u l o s 2 0 】同样使用朴素贝叶斯来 过滤邮件，他着重于邮件的预处理模块，并实验得出了邮件的判定阈值并不是越高越好， 过高的正确率往往会导致过高的误判率，这是现实所不能允许的。s c h n e i d e r 2 1 1 、g a m a l 2 2 1 利用朴素贝叶斯验证了贝努利分布模型在效率和效果上都胜于多项式分布模型。而 m e r t z 2 3 】使用n 元语言模型来计算邮件是否合法的概率。a n d r o u t s o p o u l o s 2 4 j 建立一个 f l e x i b l eb a y e s 模型，并通过高斯分布来估计概率。 贝叶斯分类有着较高的正确率和较低的误检率，所以在当前的邮件过滤上有着较多 的应用。但由于计算过程过于复杂，有时会出现资源上占用率过高，过滤速度较慢的问 题。在第三章，本文将在贝叶斯理论的基础上，提出改进的朴素贝叶斯和p o l y t r e e 条件 下的复杂贝叶斯，这两类分类法将对结果进行优化，有着更小的错误率和更好的表现。 而在第四章，本文引入信息熵，利用不确定智能算法对邮件进行过滤，减少后续过滤模 块的压力，在正确率和误检率上有着良好的结果。 2 5 本章小结 本章介绍了当前反垃圾邮件的几种主要方法，并重点介绍了最常用的过滤技术的几 种方法：黑白名单、关键词过滤、基于行为的过滤、基于内容的过滤，简述了各类方法 的应用范围和限制瓶颈，并引入了基于内容过滤下的几种算法一决策树、b o o s t i n g 、 支持向量机和贝叶斯分类，为后面引入贝叶斯理论，对其研究应用提供了知识背景 第三章贝叶斯理论研究 第三章贝叶斯网络 贝叶斯定理是常用的分类方法，它是把类的先验知识和从训练集中收集的新证据相 结合的统计算法。应用于文本分类时，贝叶斯分类通过计算文本属于每个类别的概率， 将该文本归为概率最大的一类，这其中包括每个类别的概率和从某个类别生成文本的概 率。 最常用的贝叶斯分类是朴素贝叶斯( n a i v eb a y e s ) ，它建立在“贝叶斯假设 的基 础之上：假定所有的特征之间互相独立，某文本由这些特征共同生成。实际上，在生活 中这种独立性很难存在，但从目前的实验结果看来，基于这个假设的效果却很好，而且 计算简单，因此被广泛应用于文本分类中。 而贝叶斯网络是由j u d e ap e a r l 2 5 】【2 6 】【2 7 】基于概率提出的用于处理人工智能中不确定 信息的一种技术，它是一种利用图模型来表示变量间的关系概率。在自动控制、智能计 算机和医疗诊断上有许多应用。很多科学家对其理论的发展做出了卓越的贡献。如 l a u r i t z e n 和s p i e g e l h a l t e r l 2 8 】【2 9 】提出了影响图理论，而j e n s e n 对该理论的完善使其成为当 今主流的不确定性信息处理技术【3 0 】【3 。随后出现的动态贝叶斯网络【3 2 】【3 3 1 又促进了该理 论新的发展，它结合了隐马尔科夫模型，使整个网络具有了时序特征【3 4 l 。 3 1 改进的朴素贝叶斯 朴素贝叶斯( n a i v eb a y e s ) 分类模型是对贝叶斯分类模型的简化，它假设分类对 象的所有属性条件独立，通过贝叶斯定理计算该实例属于不同条件的后验概率，选择 最高的属性条件作为归属。 岫a x p r ( 勺ix ) = 咕a x p r ( x i 勺) 峨( q ) ( 3 - 1 ) ( 3 - 1 ) 式给出了朴素贝叶斯分类模型，其中p r ( o ) 为各个类标签的先验概率： p r ( x io ) = 兀p r ( 毛| 5 ) l = l ( 3 2 ) 朴素贝叶斯邮件过滤算法是基于内容的垃圾邮件过滤方法中的一种简单有效的方 法。它的原理是把一封邮件e 当作一份文本文件，来进行文本分类。邮件e 属于邮件 类别集合c 中的一种，c = 铆一c 姆) 。 首先通过学习一个含有n 个文本，其文本类别是己知的文本集 ( e i ，研) ：i = 1 ，n ) ( 句为第i 个邮件，c i 为第i 个邮件的对应类别) ，生成一个文本e 到类别c 的映射函数 第二章贝叶斯理论研究 f ，然后对于一个未知类别的文本，代入函数f 中求解出相应类别。 最后分别计算出邮件e 为正常邮件和垃圾邮件的概率，比为两种类别的概率大小， 较大者的类别为邮件最有可能的类别。 朴素贝叶斯中假设所以条件都相互独立，所以技术起来简单易行，效率极高。但当 面临实际生活中一些条件假设问联系很紧的时候，它就显得不那么适用了，需要加以 改进。在文本分类中，各个短语间存在不同程度的语义联系，不能生硬的割裂。f 3 5 】 文献 3 6 】、【3 7 ：j l 入了x 依赖，对朴素贝叶斯进行了改良，允许属性问的相互条件 依赖。朴素贝叶斯本身是o 依赖模型，兼顾到效率和适用性，建立一个1 依赖模型是个 更好的方法。 图3 1 就是一个简单的1 依赖贝叶斯分类模型，c 表示类别，属性zj 和x3 都单 独依赖于父属性x2 ，彼此互相独立。 图3 11 依赖贝叶斯分类模型 用魂代表父节点，1 依赖贝叶斯分类模型课表达如下： 。2 而柚( ) = 峙强p r ( ) 冉p r ( t h ) 3 ， 基于改进的朴素贝叶斯理论，本文构架出一个n 平均1 一依赖邮件分类模型。根据 邮件特征间的互信息大小，选取其中的n 个特征作为父节点。分别按照公式3 3 计算每 个特征的后验概率，然后对其进行加权求和并平均化，得到最终结果。这种模型的过滤 公式为： 6 2 畸a x 善np r ( ) = 咖p r ( ) 妒( t h 毛) 4 ， 第二章贝叶斯理论研究 3 2p oiy t r e e 条件下的邮件特征网络 3 2 1b a y e s 邮件特征网络 r f c 2 8 2 2 定义了邮件信息本身的格式和邮件地址在邮件标头里的格式。这些格式是 用于传输的格式，而不是存储在邮箱旱的实际格式。邮件可分为：标头( h e a d e r ) 、正 文部分( b o d y ) 和其之间的空行。标头由一系列语法特征的字段组成，如t o ：、f r o m ：、 s u b j e c t ：等。这些字段在名称之后都有一个冒号，之后才是其内容。有些标头字段间是 彼此相关的，必须被一起解读才有意义，所以不能用简单的朴素贝叶斯对其进行分类。 最简单的邮件至少要包含起始同期( d a t e ：) 和发件人地址( f r o m ：) ，其余字段由m t a 、 m u a 和m d a 按情况添加。常用的有s e n d e r ：、r e p l y - t o ：、t o ：、c c 、b c c 等。这些都可以 作为检查垃圾邮件的属性。因为恶意软件常在某些特点r 期选择爆发，而邮件的来源地 和到达地也至关重要。c g ：( 信件的辅收信人) 和b c c ：( 信件的密件抄送收信人) 一般用 来判断垃圾邮件是否采用群发手段。 这些字段彼此间也存在一定联系，如垃圾邮件发送者的i p 地址可以通过反向查询 s e n d e r ：的域名得到，来判断其i p 是否在黑名单中。因此，本文构建了如下的贝叶斯邮件 网络。 3 2 2p o l y t r e e 图3 - 2 基于邮件特征的b a y e s 网络 贝叶斯网络，又叫信度网，包括两部分：首先它是一个有向无环图( d a g ) ，每个 节点表示一个属性或随机变量，每条有向边表示节点间的条件依赖。其次它包含一个概 第二章贝叶斯理论研究 率表，表示各节点和其父节点间的条件概率。 贝叶斯网络分为单连通图和多连通图。单连通图的任意两节点间最多有一条有向路 径，而多连通网络存在两节点间存在不止一条的有向路径。单连通图从父节点的个数上 又分为树和多叉树( p o l y t r e e ) 。从表达能力上看，多连通图最强，p o l y t r e e 次之，树最 差。但从信息传播的复杂度来看，顺序完全相反。单连通图的解决方案是线性的，而多 连通图在构造上具有环路，可能会出现循环传播，计算复杂。对多连通图的精确推理一 般是n p _ - h 砌问题。但本文提到的邮件贝叶斯网络只有2 个父节点问存在依赖关系， 可以把s e n d e r 域和i p 域结合起来，作为一个节点，它们之间的关系拿出来单独计算。 这样改进后的邮件贝叶斯网络即为p o l y t r e e ，可以使用常用的几种精确算法和近似算法。 3 2 3 并行处理计算 本文利用网络传播算法来解决p o l y t r e e 的信息传播信度。它的优点是只需要局部计 算，整体复杂度跟网络的直径成线性关系。算法给每个节点设置了一个p 值和入值，用 于传送信息给周围节点。由于不需要全局协调和递归运算，使用并行处理运算就成了我 们的首选。 如果把每个节点都当作一个处理机，不符合一般情况下只有几个c p u 的计算情景。 为了实现动态负载平衡，必须提出一个新的计算模式，来实现处理机资源和计算需求的 灵活分配。 单个处理机分配的平均节点个数为： a v e r a g e= il_duties t o t a ld u t i e sn u m b e r s il ( 3 - 5 ) 第二章贝叶斯理论研究 图3 3 并行计算环境 图3 3 是本文设计的并行计算环境的逻辑结构。如图所示，父节点的p 值和入值分 别向其子节点和父节点进行信息传播，在各个节点上进行相互独立的并行运算。下面是 该并行算法的伪码描述： 选取p o l y t r e e 一个单元，其输入信度为第k 层的p 值和第n 层的入值，则经过该单 元计算后的输出信度为第k + l 层节点的p 值和第n 1 层节点的入值。再将输出信度作为 下一单元的输入信度，经过多次迭代，就能完成整个网络的信度传播。 具体流程如下： 第三苹贝r q 斯理论研究 l 1 输入：当前贝叶斯网络摸型，目，) 上一组变量z 和一组证据节点国， 其证据值为e - e | 一 2 输出：对任一选定的曩输出p 伍p a j 并行证据传播函数的形式化定义：一 m e v i d e n c e _ p r o p a g a t i o n ( d ，冒) j p 将p o l y t r e e 按深度划分成n 层，令甩= ，七= j ：j r n _ _ s e t _ 3 9 r o c s ( 川) ；l a s t 置进程数，进程数为整个网络的节点数。一 , nf o 砖( i m t i a l i z e n o d e ( d ，a ) ，i n i t i a l i z e n o d e ( d ，p ) ) ：仓0 建子进程按 层序对p o l y l r e e 所有节点的口、a 消息作并行初始化j m _ k i l l _ p r o c s ( ) ；所肖灭所有子进程。一 l r c h i l e ( 刀 dp m _ _ s e t _ p r o c s ( c ) ；l a s t 置进程数，进程数等于笫k 层的节点数一 朋加庸( s e n d _ m e s s g e ( 玑乙k 嗍? ) ，u p d a t 曹_ _ n o d e ( 玑口) ) ；创建子进程， 对第k 层的所有u 节点并行计算 鄹，并对口，( z ，) 执行并行更新函数。一 m _ k f f l _ p r o c s ( ) ；所肖灭所有子进程一 m _ a e t _ p r o c s0 ) ：徽置进程数，进程数等于笫1 3 层的节点数一 删加砖( s e n d _ m e e e g e ( zr 。矗谢) ，u p d a t e _ n o d e ( za ) ) ；肼f 0 建子进程，对 第n 层的所有y 节点并行计算肼，并对，a ，) 执行并行更新函数一 m _ a l l _ p r o c