（计算机应用技术专业论文）中文邮件过滤系统的研究与实现.pdf

中文邮件过滤系统的研究与实现 摘要 电子邮件已经成为人们日常生活中通信、交流的重要手段之一然而，大量出现的 垃圾邮件，给用户造成了对闻和资源上的浪费，同时也极大地消耗了网络传输资源以 及邮件服务器的存储空间，并对网络安全构成威胁。本文针对这一问题展开研究。 目前，常用的包括黑名单与白名单技术、基于关键词搜索以及设定过滤规则等方 法。在实际使用中已逐渐不能满足过滤需求，基于内容分析的文本分类技术正逐步进 入邮件过滤技术当中，并成为当前研究热点其中，基于内容分析的邮件过滤方法中 的典型方法是基于贝叶斯模型。本文结合文本分类技术以及贝叶斯理论，提出了基于 粗集属性约简的贝叶斯中文邮件过滤技术，它通过基于粗集属性约简的特征提取，并 在贝叶斯分类方法中通过计算属性间的依赖性来提高朴素贝叶斯算法的适用性。同时， 本系统还结合了邮件的一些自身特性来提高过滤效果。并围绕这种针对中文邮件的贝 叶斯过滤技术来叙述相关的关键技术与方法，其中主要内容有： ( 1 ) 计算邮件的m d 5 值，系统通过计算每封邮件的m d 5 特征值，来统计内容相同 部件出现的次数，当次数超过一定阈值8 时，认为这些为垃圾邮件； ( 2 ) 根据n - 最短路径方法对中文邮件进行中文分词处理，通过改进的向量空间模 型方法在计算机中表示文本： ( 3 ) 在特征项选取方面，提出一种基于粗集属性重要度和属性依赖度的约简算法， 利用基于耦集的属性约简方法，在不损失原有信息的前提下，矗彳综合考虑条件属 性和决策属性问的依赖性以及条件属性间的依赖性对约简的影响，获取属性的最优约 简； ( 4 ) 在贝叶斯分类技术中，朴素贝时斯算法引入了“特征之间互相独立”的假设， 而在实际的中文邮件中，特征属性之间往往存有一定关联，当违背条件独立的假定时， 简单贝叶斯分类器也表现出相当的鲁棒性，本文把特征间的这种依赖性考虑进来，提 出了基于最优属性约简算法的贝叶斯分类器算法。它改善了属性变量问独立性的限制， 提高了分类的准确性，使贝叶斯技术适用于更大的范围。此外，本文在此研究的基础 上对该过滤方案进行了实验，设计与实现了一个中文垃圾邮件过滤系统。 关键词：中文邮件过滤向量空间模型粗糙集属性约简贝叶斯分类 4 s t u d ya n di m p l e m e n t a t i o no nc h i n e s ee - m a r lf i l t e rs y s t e m a b s t r a c t e - m a i lh a sh e m eo n eo ft h ei m p o r t a n tm e a n sf o rd a i l yc o m m u n i c a t i o n j u n km a i l s , h o w e v e r , l e a dt on o to n l yt h ew a s t e si nt i m ea n dr e s o n r c j e so f t h e 叫冁b u ta l s ot h ew a s t e si n c y b e rt r a n s m i s s i o ns o u r c ea n ds e r v e rs t o r a g es p a c e ，a n dt h r e a t e ns e c u r i t yo ni n t e m c t 雒w e l l t h er e s e a r c ho nt h et r o u b l ei sd o n e c u r r e n t l y , s o m ec o m m o n l yu s e dm e t h o d si n c l u d eb l a d d i s ta n dw h i t e l i s tt e c h n i q u e s e a r c hv i ak e yw o r d sa n de s t a b l i s h i n gf i l t e rr u l e s i np r a c t i c e , h o w e v e r , t h e s em e t h o d s m e n t i o n e dd o n tw o r kw e l le n o u g hn o w 1 f 1 地r e s e a r c ht h e nf o c u s e so nt h et e x ts o r ti nt e r m s o f c o n t e n ta n a l y s i s ，a m o n gw h i c ht h et y p i c a lo n ei sn a i v eb a y e s 1 1 l i st h e s i s 。b a s m go i lt h e t e x ts o r tt e c h n i q u ea n db a y e st h e o r y , p r o p o s e st h eb a y e se - m a i lf i l t e rt e c h n i q u ei nt e r m so f r o u g hs e ta t t r i b u t er e d u c t i o n t h i sf i l t e rt e c h n i q u ei sa d v a n c e do nt h er o u g hs e ta t t r i b u t e r e d u c t i o na n de l e v a t e st h ep r a c t i c a b i l i t yo fn a i v eb a y e so nt h eb a s i so ft h ed e p e n d e n c eo i l w h i c ht h ea t t r i b u t e sa r e c a l c u l a t e dw i t hb a y e sc l a s s i f i c a t i o n b e s i d e s ，t h i ss y s t e ma l s o c o n s o l i d a t e st h ee - m a l lf e a t u r e st oi m p r o v et h ef i l t e r 眦st h e s i s ，f o c u s i n go nb a y e sf i l t e rt e c h n i q u ef o rc h i n e s ee - m a i l ，i n t r o d u c e st h ef o l l o w i n g k e yt e c h n i q u e sa n dm e t h o d s ： ( 1 ) c a l c u l a t em d 5o fe a c hm e s s a g e ，t h es y s t e mt h e nc o u n t st h ef r e q u e n c yo ft h es a m e e - m a i la c c o r d i n gt om d 5 w h e nt h es a m ee - m a i la p p e a r sm o r et h a nt h r e s h o l dv a l u eb ，i t i sc o n s i d e r e da j u n km a i l ； ( 2 ) d i v i d et h ec h i n e s ec h a r a c t e r so f t h em a i lv i at h es h e r t e s tp a t hn ，t h e ne x p r e s st h et e x ti n t h ec o m p u t e ru s i n gt h ei m p r o v e dv e c t o rs p a c em o d e l ； ( 3 ) p u tf o r w a r dar e d u c t i o nc a l c u l a t i o ni nt e r m so f c o n s e q u e n c ea n dd e p e n d e n c eo f r o u g hs e t a t 砸b u t ec o n c e r n i i | gt h ef e a t u r es e l e c t i o n , o nw h i c hs o m ei n f l u e n c e sa r cb r o u g h tu po n t h ep r e r e q u i s i t e so fl o s i n gn oo r i g i n a li n f o r m a t i o nc o n s i d e r i n gt h ed e p e n d e n c eb e t w e e n c o n d i t i o na n dd e c i s i o n - m a k i n ga t t r i b u t e s ，a n da l s oa m o n gt h ed e c i s i o n - m a k i n ga t t r i b u t e s a sw e l ls oa st oa c q u i r et h el e a s ta t t r i b u t er e d u c t i o n ； ( 4 ) a sf o rb a y e ss o r tt e c h n i q u e ，n a i v eb a y e sc a l c u l a t i o ns u p p o s e st h ei n d e p e n d e n c e b e t w e e nt h ef e a t u r e s a sam a t t e ro ff a c t , t h e yd oh a v es o m er e l a t i o n si nas p e c i f i c m e s s a g e w h e nv i o l a t i n gt h i si n d e p e n d e n c es u p p o s i t i o n , t h eb a y e ss o r t e rm a n i f e s t sa h i 曲r o u g h n e s s m st h e s i s ，t a k i n gt h ed e p e n d e n c ei n t oc o n s i d e r a t i o n , l i f t sr e s t r i c t i o n s o nt h ev a r i a b l ei n d e p e n d e n c et om a k ei tm o r ea p p l i c a b l ei ns c o p e f u r t h e r m o r e , i ta l s o s 删si nm a k i n gp r a c t i c a le x p e r i m e n t a t i o na n a l y s i s k e yw o r d s ：c h i n e s ee - m a l lf i l t e r , v e c t o rs p a c em o d e l ，r o u g hs e t , a t t r i b u t er e d u c t i o n , b a y e i a nc l a s s i f y i n gm e t h o d 5 图2 1 图2 2 图2 - 3 图3 1 图4 1 图4 - 2 图4 3 图4 - 4 插图清单 中文分词算法流程图 切分有向无环图。 1 2 “我答的确实在理”的分词过程( n = 3 ) 1 4 文本的向量空间模型( v s d 以及文本间的相似度s i m ( d i ，0 2 ) 。1 7 树状贝叶斯网络 系统的总体设计框架 邮件的m d 5 特征值的阈值比较 属性约简方法比较 9 2 8 3 9 4 1 表4 _ l 表4 2 表4 _ 3 表4 - 4 表4 5 表4 - 6 插表清单 垃圾邮件系统判定情况分布( 单位：封) 邮件过滤决策表 基于s x y l 的属性选择结果 邮件的m d 5 特征值的阈值比较 邮件标题的重要性参数 属性约简方法与其它方法比较 1 0 。3 6 3 8 3 8 3 9 4 0 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果据我所 知，除了文中特别加以标注和致谢的地方外论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得盒a b 王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签名 衣蝴岬年6 月7 b 学位论文版权使用授权书 本学位论文作者完全了解金胆王些鑫堂有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金厦王些盔堂可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 黼期峄6 月| 7 日 乏砘黜名： 蝴忻石 电话： 邮编： 致谢 本学位论文是在我的导师周健副教授的亲切关怀和悉心指导下完成的在论文写 作过程中，无论是论文的选题、结构的安排、还是资料的选取、文字的推敲，都得到 周老师的大力帮助。周老师严谨、求实的工作作风、缜密的思维以及广博的学识将使 我受益终生。从课题的选择到论文的最终完成，周老师都始终给予我细心的指导和不 懈的支持。在此谨向周老师致以诚挚的谢意和崇高的敬意。 感谢计算机学院的老师们，特别是胡学钢院长、候整风老师、周国祥老师、沈明 玉老师、徐静老师以及其他老师，在我求学期间给予我知识的传授和人格感染，让我 学会了如何做学问和做人。在这三年里，我在学识上和为人上都有了不小的进步，受 益终生。 感谢和我在一起愉快的度过这三年高校教师班的所有同学，创建了一个积极向上 团结的集体，感谢他们三年来对我学习和生活上的关心和帮助 感谢审阅我论文和参加我论文答辩的各位老师，感谢你们在百忙之中帮助我完成 硕士论文的最后一个环节i 感谢所有关心和帮助过我的师长、同学、朋友和亲人们l 6 李六杏 2 0 0 7 年5 月 第一章绪论 1 1 研究邮件过滤的背景和意义 随着i n t e m c q 技术的发展，各种网络应用服务越来越多。众所周知，电子邮件是互 联网最重要、最普及的应用，它大大方便了人们生活、工作和学习然而，面对每天 各种各样、种类繁多的邮件，近年来，一些公司或个人为了个人或商业利益，在未经 收件人同意的情况下，利用电子邮件发送大量商业广告及各种不良信息，对收件人的 生活和工作造成极大的影响，一般称这种邮件为垃圾邮件( j u n k e - m a i l ) 。所谓垃圾邮件 口硼；收件人事先没有提出要求或者同意接收的广告、电子刊物、各种形式的宣传品等 宣传性的电子邮件；收件人无法拒收的电子邮件；隐藏发件人身份，地址、标题等信 息的电子邮件：含有虚假的信息源、发件人、路由等信息的电子邮件；含有病毒、恶 意代码、色情、反动等不良信息或有害信息的邮件。这些电子邮件虽然每封的信息量 不一定很大，但是邮件内容不是大多数用户需要的，甚至对大多数用户的计算机产生 危害。铺天盖地的宣传邮件不仅侵犯了用户的私人空问，而且干扰了大多数用户正常 使用电子邮件功能，同时给用户带来了上网时间和上网资金上的浪费，垃圾邮件的泛 滥不仅极大地浪费了网络资源，占用了用户的电子信箱资源，降低了网络使用效率， 影响了互联网的正常使用，还侵犯了用户的个人权利。 在我国的互联网上，垃圾邮件也已经是泛滥成灾，不容忽视。杀毒软件公司赛门 铁克在2 月初发表的每月垃圾邮件报告称【l 刀j ，2 0 0 6 年1 2 月垃圾邮件的数量达到了最 高点并且在今年1 月份继续保持这个水平。在过去的6 个月里，垃圾邮件的数量占全 部电子邮件数量的5 5 。i t 安全公司s o p h o s 发布了2 0 0 6 年7 月9 月全球垃圾邮件 “排行榜”，其中美国以2 1 6 的比例位居第一，中国紧随其后，比例是1 3 4 ，中国 互联网协会反垃圾邮件小组最近的调查显示，国内拥有邮件服务器的企业普遍受到垃 圾邮件的侵扰，有的企业每周收到上万封垃圾邮件，部分企业每年为应付垃圾邮件投 入上百万元的设备和大量的人力，给企业造成了沉重的负担。虽然每个公司为处理垃 圾邮件造成的危害所投入的成本各不相同，但是人们经常会引用到两个数据，即 f e r r i s r e s e a r c h 得出2 0 0 5 年人们为应对垃圾邮件投入了5 0 0 亿美元( 不包括机会成本) ， r a d i c a t i g r o u p 预计2 0 0 8 年这一数字会上升至1 9 8 0 亿美元。垃圾邮件已经成为各国共 同面临的棘手问题。如果不及时采取有效的反垃圾邮件措施，互联网上的垃圾邮件势 必对互联网的使用、产业的发展，以及广大用户的利益构成严峻的威胁。垃圾邮件的 肆虐使得电子邮件系统本身的存在受到严重挑战。中国的垃圾邮件问题已经发展到了 必须引起高度重视的程度，反垃圾邮件技术的提高已追在眉睫，它对我国信息产业的 发展，对我国实施以信息化带动工业化、促进经济发展的政策方针有着重要的影响。 1 2 当前主要的反垃圾邮件技术 要解决垃圾邮件问题，必须综合法律、技术等手段，采用法律手段打击传播垃圾 邮件的行为是解决垃圾邮件不断增长的一个有效方法。目前，反垃圾邮件的立法还不 完善同时，国际上的研究机构也提出了防止垃圾邮件的解决方案但是，它们都需 要对现有的邮件发送机制进行较大的改变，实施起来有很大的难度。这些研究方案主 要有 3 8 1 ：( 1 ) i r t f 提出三个在不放弃s m t p 等协议的情况下对邮件地址进行校验的方 案：终端发送准许( s p f ) 、指定邮寄者协议( d m p ) 、保留邮件交换( r m x ) ；( 2 ) 雅虎的 d o m a i n k e y s 方案为邮件服务器编写出特定的检测软件，检测发送方的域合法性，并 对邮件标上加密的验证标签，带有标签的邮件才为正常邮件。据报道，比尔盖茨曾提 出通过对发送邮件收费来减少垃圾邮件。另一种称为z o m a i l 的技术，试图通过给每个 用户分配密码锁的方法来保护邮件接收者的安全这些方法目前还没有走向实用，即 使走向实用也需要对全球的邮件系统进行全面改造。所以，对垃圾邮件进行阻断还有 很长的路要走。主流的反垃圾邮件技术是。存在发现”，即对已经产生的垃圾邮件进行 过滤。目前垃圾邮件问题的解决方法主要有下面介绍的几类【2 l 。 1 2 1 关键词过滤 通常首先要建立一个特征关键词库，当特定邮件的信头或者正文中的简单字符串 与关键词库中的关键词发生匹配时，则认为该邮件为垃圾邮件。目前，几乎所有的电 子邮件客户软件都实现了这样的过滤器。 1 2 2 验证过滤器 3 9 1 验证过滤器包括以下几种技术： 黑白名单：接收者主动设置黑白名单中的邮件地址将过滤所有在黑名单中的邮 件地址。该方法的缺点在于垃圾邮件可以伪造信头使得黑名单失去作用； 实时黑名单：与黑白名单不同实时黑名单中维护的是发送邮件服务器的m 地址 新到邮件的来源是实时黑名单中的i p 时就被认为是垃圾邮件而被过滤： 主机名反向验证技术。系统查找新到邮件的发件人地址的域如果该域没有一个 有效的d n sm x 记录就判定这个发邮地址是无效的该邮件就被认为垃圾邮件同时对 收到邮件的来源d 地址可以采用反向d n s 查找如果反向d n s 查找提供的域与邮件上 的来源口地址相符合该邮件就被接受。如果不符合该邮件被拒绝。 1 2 3 规则过滤器 基于规则的过滤器是比关键词过滤器更为高级和完善的技术。通过对大量合法和 非法邮件的综合分析，得到一个庞大的规则数据库。对新到邮件采用该规则库进行评 判，匹配的每条规则都有对应的分数，总分数达到某个阈值时，就认为该邮件是垃圾 邮件。但是，要定义合适的规则并不是一件简单的事情，随着垃圾邮件的发展，这些 规则也应该得到及时的更新。 上述几种方法目前已经得到了实际应用。通过用户建立一系列规则来判定垃圾邮 件，显然，这些方法的主观性会造成大量合法邮件的误判和垃圾邮件的漏判因此，目前 的邮件用户代理i lu s e r a g e n t ) t 具如f o x m a i l o m so u t l o o k 等，大多都采用机器学习 的算法基于垃圾邮件的内容进行过滤。 2 1 3 常用邮件内容过滤技术研究现状及存在问题 1 3 1 r i p p e r r i p p e r 是w i l l i a mw c o h e n 2 1 提出的一种基于规则的方法。它比传统的规则方法速 度更快、性能更高c o h e n 的普通文本分类的实验表明，r i p p e r 方法的正确率和决策 树方法c 4 5 相差不大，但是速度却提高了两个数量级d m c k c r i “1 将r i p p e r 方法用于 垃圾邮件过滤，在1 0 0 0 个文本特征的情况下，通过从正例中学习规则并对规则进行修剪 来获取垃圾邮件的覆盖规则，在某单位员工真实邮件语料库( 含8 5 0 篇垃圾邮件和2 1 5 0 篇非垃圾邮件) 上取得了8 0 以上的精确率。 1 3 2 决策树( d e e b i o nt r e e ) 方法 决策树是著名的规则方法之一。通过按照某种属性的顺序自顶向下地生成一棵树。 树的每个节点是属性名，而每条边是属性值，从树根到树叶的一条路径便对应一条规则。 基于信息增益进行属性顺序选择是决策树中常用的方法之一。著名的决策树算法有 1 i ) 3 、c 4 5 【3 】等。c a r r e r a s 使用决策树来过滤垃圾邮件，他采用r l m 距离方法而非信息增 益来选择特征，采用t f i d f 来描述特征，在p u i 语料上得到的垃圾邮件过滤的正确率和 召回率都在8 8 左右。目前，由于决策树方法效果一般，它本身并不常常直接用于垃 圾邮件过滤，而是作为b o o s t i n g 方法的弱学习器来使用。 1 3 3b o o s t i n g 方法 b o o s t i n g 方法f 4 j 不是一种特定的学习方法，而是一种在已有学习方法基础上的进行 “投票”的技术。它通过对已有的分类器( 称为弱规则或弱假设) 进行加权求和得到最终 的分类器( 称为强规则或强假设) 。虽然从理论上来说，任何机器学习方法都可以作为 b o o s t i n g 方法的弱学习器，但在实际中，b o o s t i n g 的弱规则常常采用基于规则的方法， b o o s t i n g 通过关注弱规则的错误而逐渐组合成强规则，它是一种错误驱动的方法。 1 3 4 粗糙集( r o u g hs e 0 方法 r o u g hs e t 理论是由p a w l a k 于上世纪8 0 年代提出的一种研究不完整、不确定知识 和数据的表达、学习、归纳的理论方法。r o u g hs e t 的研究对象是一个多值属性集合描 述的向量集合。它通过集合的等价关系操作来确定属于给定类的最大对象集合和可能 属于给定类的最小对象集合，从而指导分类决策。r o u 曲s e t 通常经过属性约简( 消除对 决策属性没有影响的属性) 和属性值约简( 消除对决策属性没有影响的属性值) 来简化分 类规则。刘洋等1 3 0 1 将r o u g hs e t 引入到垃圾邮件过滤，采用了1 1 种非文本属性( 包括收 信人个数、中继个数等等) 来进行邮件分类( 正常、广告和反动) 。在一个小规模的垃圾 邮件样本上实验，可以达到8 0 左右的正确率 1 3 5 k n n 方法 k n n 是最常用的基于实例的方法。k n n 没有训练过程，分类时直接将待分类文本 与训练集合中的每个文本进行比较，然后根据最相似的k 篇文本得到新文本的类别。 k n n 的原理非常直观在文本分类中，k n n 常常能够取得较好的结果但是由于其分类 速度的局限性，不太适用于对分类速度要求较高的垃圾邮件过滤场合。 a n d r o u t s o p o u l o s l 3 习使用了一种类k n n 方法应用于垃圾邮件过滤领域，该方法使用k 组 最近的距离而不是k 个最近的样本来计算，如果多个样本同待过滤邮件距离相差不大 的话，则这些样本都将用于确定最后的结果，此时，过滤中真正使用的样本数目大于k 。 实验表明，k n n 在k 取较小值的情况性能较好，和n a i v e b a y e s 的结果性能几乎相当。 1 3 6 基于统计的支持向量机( s v m ) 支持向量机聊1 ( s u p p o r t v e c t o r m a c h i n e ，简称s v m ，也叫做支撑向量机) 是在二十世 纪9 0 年代以来发展起来的一种统计学习方法，它通过构造最优线性分类面来指导分类。 s v m 可以直接用于线性可分问题，而对于线性不可分的情形，可以构造一个变换，将 问题转换到一个新的空间，在这个新空间中线性可分。在文本分类中，s v m 是公认的 较好的方法之一。d r u c k e r 将线性s v m 用于垃圾邮件过滤，得到的结果再次印证了这 一点。d r u c k e r 还指出，采用二值表示的s v m 的性能稍高于采用多值表示的s v m 。另 一个使用s v m 的好处是不需要进行特征选择就可以直接利用s v m 进行过滤，其结果 和经过特征选择差别不大。 1 3 7r o e c h i o 方法： r o c c h i o 3 6 l 方法由是信息检索领域常常用于相关反馈的方法。它用于分类的基本思 路很简单：将所有训练文本向量化，类别向量等于所有正例向量和反例向量的加权差。 形式地： 瓦南荔+ z 一晶iix 互, 。o - z 其中d + 、d 分别表示正例和反例集合，矿卜i d l 分别表示正例集合和反例集合的 大小。a 、为加权系数计算得到的结果c 表示该类的类别向量。用于垃圾邮件过滤 时，通过上式可以得到垃圾邮件类的类别向量。新的邮件与类别向量计算距离，距离 小于某个阈值0 ，则判定该邮件属于垃圾邮件类，否则为合法邮件实际应用中，a 可 以设定为l ，和。可以通过训练得到( 使得训练集合的分类错误率最低) d r u c k e r “j 将该方法用于垃圾邮件过滤。该方法十分简洁，分类时间短，但是过滤效果稍差。 1 3 8w i n n o w 方法 w m n o w 是一种线性分类器。它训练的目的是为了找到某个类所有特征的权重向量 产w 1 ，w 2 ，w n 讲是特征数) 和阈值0 ，对于新文本x - - x i ，x 2 ，x p ，若两者的 内积w o x 0 ，则判定属于该类否则，不属于该类w i n n o w 在学习w 时采用的是一 种错误驱动的方法在训练时，一旦发生错误，将根据需要降低或者升高w 里相应特征 的权重值。b a l a n c e dw m n o w 【m 算法是w m n o w 算法的一种，它和普通w m n o w 算法的 不同在于引入了两个权重向量w + 和w - ，训练时通过同时变化w + 和订来达到更新权值 的目的。潘文锋田】将b a l a n c e dw i n n o w 算法引入到垃圾邮件过滤，在应用时使用了固 定的阙值0 ，它的大小是每篇训练文本所含的平均特征数，而初始的w + 和w 分别取全 2 向量和全l 向量。在不同语料库上的实验结果表明，该方法效果接近目前所发表的最 好结果，而w u m o w 在训练速度和分类速度上具有较大的优势，所以具有更高的实用 价值。另外，作为一种在线( o n - l i n e ) 学习方法的w m n o w ，在训练集合不断扩大的情况 下能够快速对分类器进行更新。 1 3 9b a y e s 方法 贝叶斯算法是以著名数学家托马斯贝叶斯命名的一种基于概率分析的可能性推 论理论。2 0 0 2 年8 月，p a u lg r a h a m 在“a p l a nf o rs p a r e ”一文【4 】中提出了将该算法用 于邮件过滤的想法，并用a r c 语言实现了该算法。贝叶斯过滤以基于规则评分的过滤 技术为基础，通过对邮件中的单词进行概率统计，使用以前收到的垃圾邮件和合法邮 件中的相同词语及短语出现的概率对比，来确定垃圾邮件的可能性。贝叶斯过滤法功 能强大，是阻断垃圾邮件较为精确的技术，过滤准确率可达到9 8 ，目前大多数反垃 圾邮件产品都采用了该技术。 贝叶斯过滤的流程：首先在已经确定的垃圾邮件集和正常邮件集中进行学习，根 据每个单词分别在两个集合中出现的次数，计算单词的垃圾概率。当一封新邮件到达 时，系统对信件全部内容进行分词和选词，得到一组单词流，然后根据学习到的信息， 计算整个单词流的概率，并最终判断该信件是否为垃圾邮件。由于贝叶斯过滤是通过 已知的邮件集进行概率计算的，过滤准确性依赖大量的历史数据。 n a i v e b a y e s 方法被广泛用于文本分类中，取得了不错的效果。已有多位学者将 b a y e s 方法应用于垃圾邮件的判别，s t a n f o r d 大学的s a h a m i ( 3 4 将n a i v e b a y e s 方法引入 到垃圾邮件过滤进行实验。s a h a m i 采用了自己收集的邮件作为实验数据。值得一提的 是，s a h a m i 除了使用词汇作为特征外，还使用了词组特征和其他属性特征( 如标题中非 字母和数字字符所占的百分比) 。实验结果表明，其他属性特征能够较大幅度地提高过 滤结果( 精确率在9 5 左右) 。s a h a m i 的另外一项工作是将垃圾邮件细分为色情和非色 5 情邮件，再加上合法邮件，变成一个三类问题进行实验( 当然实验的最终目标还是区分 垃圾和合法邮件两类) s a h a m i 的实验结果却表明，将垃圾邮件判别看成三类问题反而 降低了效果，文章对该出乎意料的结果进行了分析。除了n a i v e b a y e s 外，不少学者还 使用了其他的b a y e s 模型。i b m 的m 眦口】不是采用独立性假设而是考虑使用n 元语言 模型来估计相关的概率。文章发现三元语言模型是一个很好的选择a n d r o u t s o p o u l o s p s i 使用了一种f l e x i b l e b a y e s 模型，虽然该模型仍然采用独立性假设，但是对概率的估计 使用了高斯分布模型。该方法获得了较好的效果。 在上面介绍的各种邮件过滤方法中，针对的主要是英文邮件，贝叶斯分类方法表 现出了很好的性能，朴素贝叶斯过滤器是其中非常简单有效的方法但是，朴素贝叶 斯分类的前提是“假定属性值相互条件独立即在属性间不存在依赖关系”，而中文词 意间的相关性是肯定存在的。本文在中文邮件的过滤方法方面进行了探索研究，并在 此研究的基础上对该过滤方案进行了实验分析，证明了改进的有效性。 1 3 本文的研究内容 本文将按照邮件过滤过程中的主要技术进行分析介绍。由于本文的研究对象是中 文邮件，首先必须对中文进行分词处理，分词处理的准确性将直接影响后面分类的精 度。本文采取的是利用n - 最短路径方法进行中文分词。将这些中文分词用向量空间模 型表示成计算机能识别的符号。其次邮件训练库中的词汇量是巨大的，必须要对其进 行特征提取。本文对特征提取的各种方法进行了介绍。数据的约简是粗糙集理论的一 个重要研究课题。由于中文词意的相关性，综合考虑各种文本特征选择方法，本文采 用了基于粗集约简的特征提取，把特征问的这种依赖性考虑进来，提出了最优属性约 简算法( s x l 儿) 。在不影响条件属性的分类能力的情况下，既删除了不相关属性和完 全依赖属性，又删除了多数部分依赖属性降低了特征选取计算的复杂性，提高了特 征选取的精度。最后本文将邮件分为垃圾邮件和正常邮件两类，根据朴素贝叶斯理论 对其分类，通过对训练样本库的分析，得到各特征词在垃圾邮件和正常邮件中分别出 现的初始概率。对于新到邮件，首先抽取出特征词，根据训练样本库中学习的概率计 算新到邮件分类为垃圾邮件或者正常邮件的概率。其中贝叶斯算法是基于概率论中的 先验概率和条件概率的，在推导朴素贝叶斯算法的过程中引入了“特征之间互相独 立”的假设。而在实际邮件文本中，特征属性之间往往存有一定关联，当违背条件独 立假定时，简单贝叶斯分类器也表现出相当的鲁棒性，影响了分类的精度。本文在此 方面进行了探索研究，把特征间的这种依赖性考虑进来，由此提出了基于最优属性约 简算法的贝叶斯分类器算法( b v s c ) 。它改善了属性变量间独立性的限制，提高了分类 的准确性，使贝叶斯技术适用于更大的范围。 1 4 本文的组织结构 本文共分六章： 第一章绪论。本章是全文的统领，提出了研究的背景和动机，介绍了当前的主要 6 反垃圾邮件技术，并介绍了论文研究的主要内容和内容安捧 第二章中文垃圾邮件过滤系统及其关键技术。本章主要对中文的词法进行了分 析，对基于字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法这三 种分词算法进行了描述并对自动分词基本算法中的最大正向匹配算法( n n i 算法) 作了描述，并举例说明，对f m m 算法进行了算法评价。然后对常见分词算法进行了 比较，指出其优缺点。根据比较的结果，采用了n 最短路径方法对中文邮件进行分词 处理。并对n - 最短路径方法进行了详细的描述 第三章基于粗集的属性约简的中文特征项选择本章首先提出了文本的表示的各 种模型。本文采用的是向量空间模型，介绍了向量空间模型中的一些常用概念。当中 文分词被表示成计算机可以识别的信息以后，接下来进行的是特征提取，常见的中文 特征项选择的方法有文档频率( d o c u m e n tf r e q u e n c y ) 、信息增益( i n f o r m a t i o nc a i n ) 、互 信息( m u t u a li n f o r m a t i o n ) 、z 统计量“c h d 、词条期望嫡、文本证据权、单词权等等， 对它们进行了介绍。考虑到朴素贝叶斯算法的过程中引入了“特征之间互相独立”的 假设。本文采用了基于粗集约简的特征提取，详细介绍了粗糙集( r o u g hs e t ) 理论中约 简的特征选取，提出了基于信息归纳的概率粗糙集约简算法。 第四章中文垃圾邮件过滤系统模拟及其分析。本章对现有的基于文本挖掘的邮件 分类技术进行了回顾，对贝叶斯分类技术中的贝叶斯定理、朴素贝叶斯分类、贝叶斯 信念网络、树状贝叶斯网络进行了介绍。提出了基于粗集的属性约简的贝叶斯邮件分 类技术的模型，针对邮件自身的特点来构件分类模型。根据分类模型进行介绍。首先 是邮件的预处理、邮件文档的文本表示。然后详细介绍了基于依赖性的属性约简的贝 叶斯邮件分类技术，把特征问的这种依赖性考虑进来，提出了针对贝叶斯分类器的最 优属性约简算法和基于粗集属性约简的贝叶斯分类器算法( b y s c ) 。并对系统进行模拟 与分析，首先说明了评测的重要性，介绍了评估方法、模拟系统的构建，对测试需要 的数据、测试所需环境进行了描述，最后得出实验结果。 第五章总结与展望。本文通过对上述实现技术的阐述及其对试验结果的分析，提 出了一些关于邮件分类研究的见解，并对今后的研究工作进行了展望。 7 第二章中文垃圾邮件过滤系统中的关键技术 目前。针对英文邮件过滤的论述有很多，研究方法也较成熟本文主要针对中文 邮件过滤技术进行分析众所周知，英文中一个单词独立成“词( w o r d ) ”，但对中 文而言，组成词的字的个数是不确定的，可以是一个，两个，甚至多个所以处理中 文邮件时首先应对中文语句进行分词。决定一篇邮件内容的关键是邮件中包含的实意 词，如果不能很好的提取邮件中的实意词，就不能很好的对邮件的内容进行判断针 对中文的贝叶斯垃圾邮件过滤算法，关键在于很好的分析中文语言的特点，实现对中 文邮件中词语的合理提取。 2 1 中文词法分析 汉语在语法上有一些特点，英文是以词为单位的，词和词之间是靠空格隔开，而 中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子ia n la s t u d e n t ，用中文则为；“我是一个学生”计算机可以很简单通过空格知道s t u d e n t 是 一个单词。但是不能很容易明白“学”、“生”两个字合起来才表示一个词把中文 的汉字序列切分成有意义的词，就是中文分词，有时也称为切词。仅仅从形式上看， 这种特点主要体现在以下几个方面嘲： 汉语的基本构成单位是汉字而不是字母。常用汉字就有3 0 0 0 多个( g b 2 3 1 2 一级 汉字) ，全部汉字达数万之多( u n i c o d e 编码收录汉字2 0 0 0 0 多) 。而词的数量 更为巨大。 汉语的词与词之间没有空格分开，从形式上看，汉语中没有“词”这个单位。 汉语词没有形态上的交化，同一个词在句子中充当不同语法功能时，形式是完全相 同的。 汉语句子没有形式上唯一的谓语中心词。 在中文邮件分类系统中要用到的中文分词处理技术应能完成下面几项任务： 查词典识别标准词。 处理重叠词、离合词、前后缀。 未定义词( 未登录词) 识别：时间词、数词处理；中国入名识别；中国地名识别； 译名识别；其它专名识别。 某些有特殊意义的非汉字字符的识别提取，如￥、$ 等。 一词多义或词汇变形问题。事实上，自然语言有着极为丰富的语言现象。例如词汇 之间的关系，就有同义关系、近义关系、从属关系、关联关系等等。在使用短语等 复合词时关系就更加复杂了。另外词汇的歧义和多义也很普遍，因此，不同的词义 当作不同的项来看待会更合理。 在中文词法分析方面，国内开展研究比较早，已有很多成熟有效的技术，中文分 词实现汉字字串到词串序列的转化。然而，由于汉语的特殊性，分词存在一定的困难。 首先，中文词与词之间没有明显分割符号。其次，汉语句法复杂，语法模糊，语义多 s 样，而至今中文信息处理还没有一个公认的、确切完备的计算机处理标准另外，字 典中不能囊括所有的词，特别是一些人名、地名，而且随着语言的发展，没有收录的 新词在不断增加。 2 2 分词算法描述 现有的分词算法可分为三大类；基于字符串匹配的分词方法、基于理解的分词方 法和基于统计的分词方法。 2 2 i 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充 分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功( 识 别出一个词) 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配： 按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配：按 照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体 化方法常用的几种机械分词方法如下： 正向最大匹配法( 由左到右的方向) ； 逆向最大匹配法( 由右到左的方向) ； 最少切分( 使每一句中切出的词数最小) 。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹 配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最 小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义 现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向 最大匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的需要。实际使用的分词 系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一 步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识 别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串 再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来， 利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进 行检验、调整，从而极大地提高切分的准确率。 2 2 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本 思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现 象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分在总控部分的 协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判 断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。 由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形 9 式，因此目前基于理解的分词系统还处在试验阶段 2 2 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数 越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成 词的可信度可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互 现信息定义两个字的互现信息，计算两个汉字x 、y 的相邻共现概率。互现信息体 现了汉字之间结合关系的紧密程度当紧密程度高于某一个阈值时，便可认为此字组 可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典， 因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽 出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、。有的气“我的”、 。许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统 都要使用一部基本