（计算机软件与理论专业论文）基于最大熵模型的垃圾邮件过滤系统研究.pdf

基予鼎太熵模擞的垃圾部件过滤系绕研究 中文摘拦 基于最大熵模型的垃圾邮锌过滤系统研究 中文摘要 电子邸件已经成戈人们日常生活中透信、交流的重要手段之一，但垃圾龆件的泛 滥融带来严重后果，有效地区分合法邮件和垃圾邮件成为一项紧迫的任务。 近年寒，骞关蟪圾郏锌过滤搜零麴磅突逐澎兴超，霉霭粒过滤方法鸯照，塞名繁 技术、规则过滤等，但由于垃圾邮件的特征在不断地变化，规则难以维护、准确率不 离镲霖因，这些方法都其菊一定赘羯隈往。嚣蔫，穗垃圾郝 孛过滤与梳器学习、文本 分类和信息过滤技术结合起来，对邮件正文内容进行分析，成为研究的热点；基于内 容的分析能够自动获得垃圾都侔酌特征，怒一种更为精确的垃圾部件过滤技术。 本文蘑先介绍了垃圾邮件过滤技术的研究背景，重点对目前常用的基子内容的垃 圾邮件过滤算法进行了分析、比较。在此基础上，对邮件进行预处理，将蕻表示成 旺搀式，楚嚣囱郏锋的废爆程黟开发提供7 统一熬结梅纯表示。 最大熵模型是一个比较成熟的统计模型，其计算模型独立于特定的任务，具有简 滂、逶焉秘易子移棱等耱杰，近年来在鑫然语言楚理领蠛貉魏7 广泛应瘸。 本文的重点工作是将最大熵方法应用到垃圾邮件过滤中，提出了基于最大熵的士点 缀自s 俘过滤系统的基本框絮：结合躯侔豹睾结构纯特往，撵取部俘的结构特征、歪文 特征，对邮件内容进行初步的信息抽取，将邮件表示成邮件特征向爨，并对使用不同 特征集情况下的过滤性能进行了对比实验；改进传统最大熵模型中的特征溺数定义， 实验结果表明词频犍征函数具有较好的过滤性能；弓l 入n - g r a m 中饯能较好的平滑舞 法对最大熵模型进行平滑，解决“稀疏”搴件问题，对绝对折扣和尚斯先验两种平滑 算法遴露了j i 砉跑；箍窭了逡滤模型戆鑫逶痰潺整秘攀习算法，以逶艨女箨耱缓豹交缘， 满足用户的个性化过滤要求；将最大熵方法与其它常用的垃圾邮件过滤方法进行了性 能跪较，实验结栗表臻，这静方法在召容率、正确牵、f l 德、错误率等方瑟表琨出了 良好的过滤性能。 最后，将基于最大熵的垃圾邸件过滤方法与o u t l o o k 掇供的p i a 相结合，开发出 个垃圾懿馋过滤糖件，农客户端用最大熵方法实现了基予内容的竣圾自5 传过滤，较 好地帮助用户解决了垃圾邮件泛滥的问题。 生趔塞墅墼塑塑丝亟螋燮塑塑 关键谰：缱骧瓣释j 霪滤；赣楚疆；最大缡；蒋缎提取；平潜技米；o u t l o o k ：播鹌： i i 作卷：司广涛 攘譬老照：寒巧嘎 r e s e a r c ho ns p a m f i l t e r i n gs y s t e mb a s e d o n m a x i m u m e n t r o p ym o d e l a b s t r a c t e 。m a i li sb e c o m i n gam a j o rm e a j l so fc o m m u n i c a t i o ni no u rd a i l yw o r ka n dl i f e b u t t h ef l o o d i n go fs p a mh a sm a d eag r e a ti m p a c to ni t s a p p l i c a t i o n ，t h e r e f o r ei t i sav e r y i m p o r t a n tt a s kt od i s t i n g u i s hs p a mf r o ml e g i t i m a t em a i l s m a n yr e s e a r c h e so ns p a mf i l t e r i n gh a v eb e e nc a r d e do u ti nr e c e n ty e a r s s o m e m e a s u r e so fs p a mf i l t e r i n g ，s u c ha sb l a c ko rw h i t el i s t ，m a n u a lr u l e sa n ds oo nh a v eb e e n w i d e l yu s e d b u ti t i sd i f f i c u l tt om a i n t a i nt h er u l e sb e c a u s et h ef e a t u r e so fs p a ma r e a l t e r a t i v e ，a n dt h er u l e s - b a s e df i l t e r i n gi sn o ts a t i s f a c t o r yi np r a c t i c e s ot h e s em e a s u r e s h a v ec e r t a i nl i m i t a t i o n s n o w a d a y s ，w i t ht h e d e v e l o p m e n to fm a c h i n el e a r n i n g ，t e x t c a t e g o r i z a t i o na n di n f o r m a t i o nf i l t e r i n g ，t h ea n a l y s i so fe m a i lc o n t e n ti sb e c o m i n gah o t r e s e a r c ht o p i ci ns p a mf i l t e r i n g t h ec o n t e n t - b a s e df i l t e r i n gm e t h o dc a l lo b t a i nt h ef e a t u r e s o fs p a ma u t o m a t i c a l l y , s oi ti sa g o o da p p r o a c ho nf i l t e r i n gt e c h n i q u ei na c c u r a c y s o m eb a c k g r o u n d so ft h er e s e a r c ha r ep r e s e n t e di nt h i st h e s i s ，a n dt h e ns o m ea n a l y s e s a n dc o m p a r i s o n sa r em a d e a m o n gt h ec o m m o n l yu s e dc o n t e n t - b a s e ds p a mf i l t e r i n g t e c h n i q u e s s u b s e q u e n t l y , s o m ep r e p r o c e s s i n go fe m a i li sp e r f o r m e d ，a n dax m l d e n o t a t i o no fe 。m a i li si n t r o d u c e dt op r o v i d eau n i f o r ms t r u c t u r ef o rt h ed e v e l o p m e n to f e m a i lo r i e n t e da p p l i c a t i o n s m a x i m u me n t r o p ym o d e li sam a t u r es t a t i s t i c a lm o d e lw h o s em o d e lo fc o m p u t a t i o ni s i n d e p e n d e n to fs p e c i a lt a s k s ，a n di tt a k e so ns i m p l e n e s s ，u n i v e r s a l i t ya n dp o r t a b i l i t y t h e r e f o r e ，m a x i m u me n t r o p ym o d e lh a sb e e nw i d e l yu s e di nn a t u r a ll a n g u a g ep r o c e s s i n g i nr e c e n ty e a r s t h em a i nt a s ko f t h i st h e s i si st oa p p l ym a x i m u me n t r o p ym o d e lt os p a mf i l t e r i n g ，a n d t h ep r i m a r yf r a m e w o r ko fs p a mf i l t e r i n gs y s t e mb a s e do nm a x i m u me n t r o p yi sp r o p o s e d c o n s i d e r i n gt h es e m i - s t r u c t u r ec h a r a c t e r i s t i co fe m a i l ，f e a t u r e sa r ee x t r a c t e df r o me m a i l i i i 垒! ! ! 里壁坠! ! ! 竺! ! ! ! ! 竺! ! ! 竺! ! ! g ! ：! ! ! 竺里竺! 12 1 坚竺! 竺! 竺星! ! 竺型塑! ! ! ! h e a d e ra n de m a i lb o d y , a n ds o m ee l e m e n t a r yi n f o r m a t i o ne x t r a c t i o n sa l ep e r f o r m e do n e - m a i lc o n t e n t o nt h eb a s i so ft h e s eo p e r a t i o n s ，e a c he - m a i li sp r e s e n t e da sav e c t o ro f e - m a i lf e a t u r e s ，a n ds o m ee x p e r i m e n t sa l em a d eo nt h ef i l t e r i n gp e r f o r m a n c ew i t hd i f f e r e m m a i lf e a t u r es e t s s o m em o d i f i c a t i o n sa l em a d eo nt h et r a d i t i o n a lf e a t u r ef u n c t i o n si n m a x i m u me n t r o p y , a n de x p e r i m e n t ss h o wt h a tb e t t e rf i l t e r i n gp e r f o r m a n c ec a nb ea c h i e v e d w i t hw o r d 丘e q u e n c ya st h ef e a t u r ef u n c t i o n s o m es m o o t h i n gt e c h n i q u e st h a ta c h i e v e b e t t e rp e r f o r m a n c ei nn - g r a ma l ea p p l i e d1 0s m o o t ht h em a x i m u me n t r o p ym o d e la n d r e s o l v et h ed a t as p a r s e n e s s ，a n da ne x p e r i m e n ti sp e r f o r m e dt ot e s tt h ep e r f o r m a n c eo f a b s o l u t es m o o t h i n ga n dg a u s s i a np r i o rs m o o t h i n g a na d a p t i v ea l g o r i t h mt oa d j u s ta n d r e - t r a i nt h em a x i m u me n t r o p ym o d e li sa d v a n c e dt om a k et h em o d e la c c u s t o m e dt ot h e v a r i a b i l i t yo fe - m a i lf e a t u r e sa n di m p l e m e n tp e r s o n a lf i l t e r i n g f u r t h e r m o r es o m e c o m p a r i s o n so nf i l t e r i n gp e r f o r m a n c ea r em a d eb e t w e e nt h em a x i m u me n t r o p ym e t h o da n d o t h e rc o m m o n l yu s e ds p a r ef i l t e r i n gm e t h o d s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h i s m e t h o da c h i e v e sb e t t e rf i l t e r i n gp e r f o r m a n c ei nr e c a l l ，p r e c i s i o n ，f j ，e r r o rr a t ea n ds oo n l a s t l y , c o m b i n e dw i t i lt h ep i ap r o v i d e db yo u t l o o k a no u t l o o ka d d i nf o rs p a m f i l t e r i n gb a s e d0 nm a x i m u me n t r o p ym e t h o di sd e v e l o p e d w i t ht h i sa d d i n ，u s e r se a r a p p l yc o n t e n t b a s e df i l t e r i n gw i t hm u a t ok e e pa w a yf r o ms p a r ee a s i l y k e y w o r d s ：s p a mf i l t e r i n g ；p r e p r o c e s s i n g ；m a x i m u me n t r o p y ；f e a t u r ee x t r a c t i o n ； s m o o t h i n gt e c h n i q u e s ；o u t l o o ka d d - i n w r i t t e nb ys ig u a n g t a o s u p e r v i s e db yz h uq i a o m i n g 苏州大学学位论文独创性声明及使用授权声鞠 攀位论文独创性雾鞠 本人郑鬟声聪：所提交酌学位论文是本入在导师酶指辱下，猿立 避行磅究工俸瑟淑褥麓成暴。除文孛憋经遽镤葶 爆熬凑枣豁，本论文 不含篡媳个人或集体已经发表或摸写过的研究戏慕，也不禽为获褥苏 燃大学或其它教育巍拣赡攀位涯书嚣艇爱过豁瓣辍。对搴文数研究 牡 惑重要嚣献熬个人粒集体，均已或文中以明确方式禄明。本人承携本 声骥辫法律责任。 掰究生篓霆：童3 生；签 基 嬲：“；： 2 学健论文使用授权声躜 苏毒辩大学、中窗科学技零债患研究所、溪家蓠书镶、潘攀大学论 文台俸罄、孛瀣率科院文熬缤息撼搬中心窍杈绦留本人所送交学位论 文酾复印件窬蘸子文档，可以采蒂影辩、缭帮或其箍复铡手段保存论 文。本天拖予文樘辫内蜜和纸鹱论文魏魂容檩一致。狳在僳密期内救 傈鬻论文补，允许论文被查溺辫僚阕，可戬公布( 毯耩刊登) 论文酾 全颦或舔分蠹枣。论文怨公毒 ； 七 l 系统j 图1 3s m t p 模型 s m t p 中存在严重的安全问题。首先，它缺乏足够的验证要求，服务器的连接请 求中可以输入任意的参数，接收方服务器没有足够的验证手段，导致了假冒他人邮件 地址和滥用别人s m t p 服务器的现象，即电子欺骗和o p e nr e l a y 问题。其次，应答 信息中会显示邮件服务器的软件产品信息，使攻击者可以根据版本信息找到漏洞。再 次，它没有规定如何加密传输的内容，无法保证邮件到达最终用户前没有被篡改。 ( 3 ) e s m t p 为了解决s m t p 中存在的缺陷，1 9 9 5 年公布的r f c1 8 6 9 定义了一套扩展s m t p 功能的方法，称为e s m t p 。它对s m t p 的主要扩展是为了防止上述的o p e n r e l a y 问 题而开设了安全认证服务。在e s m t p 邮件服务器中，系统为了限制非本系统的正式 用户利用本系统发送垃圾邮件或其他不当行为，发送邮件前需要对用户身份进行验 攮十最大熵模型的垃圾| j | j 件过滤系统研究 t j l 宣 证。验证之后的邮件发送过程与传统的s m t p 方式一致。 ( 4 ) p o p 3 大多数情况下，客户机无法与因特网保持持续不断的连接，因此无法在任何时候 都接收远程s m t p 服务器要发送给它的邮件。为了对客户机提供邮箱服务，r f c1 3 9 3 文档中定义了p o p 3 ( p o s to 伍c ep r o t o c o l v e r s i o n3 ，邮局协议第3 版) 。 p o p 3 与s m t p 存在相似之处，同样使用文本命令和应答信息与客户端进行交互 式通信。与s m t p 不同的是，p o p 3 服务器将客户端请求的邮件数据发送给客户端。 p o p 3 的客户端月务器会话由3 个不同的状态组成，即授权( a u t h o r i z a t i o n ) 、事务处 理( t r a n s a c t i o n ) 和更新( u p d a t e ) 状态。 授权状态：客户端向服务器证明自己的身份，执行身份验证过程。 事务处理状态：客户端将命令发送到服务器，取回邮件。此外，还可以对邮 件进行操作，如做删除标记、获取邮件统计信息等。 更新状态：客户端发出q u i t 命令，服务器删除已做了删除标记的邮件，释 放对客户端邮箱的独占权，结束p o p 3 会话。 ( 5 ) i m a p p o p 3 只能为客户端提供基本的邮箱服务，通常邮件从服务器上下载到客户端后， 就会从服务器上删除。r f c2 0 6 0 定义的i m a p ( i n t e r n e tm e s s a g ea c c e s sp r o t o c o l ， i n t e m e t 消息访问协议) 第4 版也是一个邮件访问协议，对p o p 3 的功能进行了改进。 它与p o p 3 之阳j 的最大差别是，i m a p 能够将邮件永久存放在服务器上，用户可以从 任何客户端访问自己的邮件。此外，i m a p 还提供了更加广泛的可供选择的命令，使 客户能够更好地访问和操作他们的邮件。 用户可以在自己的邮箱中建立文件央，并在文件央之间移动邮件，从而建立 一个有组织的邮件存储层次。 i m a p 提供了邮件检索和处理的扩展功能，可以指定邮件头字段、邮件主题 或邮件内容等条件对邮件进行搜索。 用户可以获得一个邮件清单，然后选择有用的邮件进行下载，这种特性对于 低速网络连接非常有用。 j i 斋 罐于最大熵模型的垃圾邮件过滤系统研究 1 3 课题的工作与意义 中国目前已经成为第二大垃圾邮件制造国，中国相关部门已经或准备采取一系列 措施，利用法律和技术的手段与垃圾邮件进行坚决的斗争。目前对境内的垃圾邮件可 以采取法律手段进行抵制，但对境外的垃圾邮件只能通过技术手段进行屏蔽。因此， 研究垃圾邮件过滤技术，对于防范垃圾邮件具有重要意义。 本文在分析比较现有常用垃圾邮件过滤技术的基础上，将自然语言处理领域应用 广泛的最大熵方法应用到垃圾邮件过滤中，取得了良好的过滤性能。主要工作包括： 对垃圾邮件过滤技术研究现状进行分析总结。 对解码后的邮件进行分析，经过分词、去停用词、邮件内容信息提取等预处 理操作后，表示成x m l 格式，为面向邮件的应用程序开发提供统一的结构化表示。 提出基于最大熵的垃圾邮件过滤系统的基本框架。 结合邮件的半结构化特性，对邮件进行特征提取，表示成邮件特征向量，改 进传统最大熵模型中的特征函数定义，通过实验进行性能比较。 提出最大熵模型的参数调整算法，增强模型的自适应性，更好地满足用户的 个性化要求。 将基于最大熵的垃圾邮件过滤方法与现有常用的过滤方法进行分析比较。 将基于晟大熵的垃圾邮件过滤方法与o u t l o o k 提供的p i a 相结合，在n e t 平 台上开发出一个垃圾邮件过滤插件，在客户端实现了基于内容的垃圾邮件过滤。 1 4 本文的内容安排 第一章引言 阐述本文的工作背景和意义，重点介绍了当前反垃圾邮件的主要措施、电子邮件 的工作原理及本文的主要工作及内容安排。 第二章垃圾邮件过滤技术研究的现状 对当前常用的垃圾邮件过滤技术进行分析比较，重点阐述了基于内容的垃圾邮件 过滤技术及相关的过滤性能评价指标。 第三章邮件预处理 主要阐述了垃圾邮件过滤的些预处理工作，如邮件解码、主题内容分词、特 肇十最人熵模型的垃圾邮牛过滤系统研究c 引击 征提取、x m l 表示等。其中重点介绍了将邮件表示成x m l 的方法，以便为面向邮 件的上层应用程序的开发提供统一的数据格式。 第四章最大熵模型在垃圾邮件过滤中的应用 首先阐述了最大熵模型的基本原理及其相关的模型选择、特征选择等算法，然后 将最大熵模型引入到垃圾邮件过滤中，提出了基于最大熵模型的垃圾邮件过滤系统的 基本框架。具体实现中，结合邮件的半结构化特性，对邮件进行特征提取，形成邮件 特征向量空间，改进传统模型中特征函数的定义，利用平滑技术对邮件特征进行平滑 处理，将最大熵方法与其它常用的垃圾邮件过滤方法进行对比，提出了最大熵模型的 自适应调整算法，以使其更好地适应用户的个性化过滤需求和邮件特征的变化。 第五章基于最大熵的垃圾邮件过滤插件的设计与开发 主要介绍利用最大熵方法进行垃圾邮件过滤插件设计与开发的相关技术。将基于 最大熵的垃圾邮件过滤方法与o u t l o o k 提供的p i a 相结合，利用n e t 技术丌发出一 个垃圾邮件过滤插件，在客户端了实现基于内容的垃圾邮件过滤。 第六章总结与展望 总结了本文的主要工作，并针对工作中的不足之处，提出进一步的研究目标。 1 5 本章小结 首先说明了垃圾邮件的定义、现状、危害，从法律、经济、技术等方面说明了反 垃圾邮件的主要措施，回顾了反垃圾邮件技术发展的历史。然后，对电子邮件的工作 原理进行了简单介绍，以更好地理解垃圾邮件过滤的相关技术。最后说明了本课题的 主要工作和本文的内容安排。 在阐述了相关的研究背景的基础上，下一章的主要工作是对当前垃圾邮件过滤技 术研究的现状进行分析、总结和比较。 垃圾邮件过滤技术研究的现状 恭于最人熵模型的垃圾邮件过滤系统研究 第二章垃圾邮件过滤技术研究的现状 从电子邮件的结构出发，寻找垃圾邮件的特征，在邮件头、邮件正文内容等各方 面开展过滤工作，是垃圾邮件过滤常采用的基本方法。 2 1 垃圾邮件过滤的位置 从过滤的依据来分，可以分为基于i p 地址的过滤、基于邮件头的过滤和基于邮 件内容的过滤三种。从实施过滤的主体来分，邮件过滤有多种方法【3 1 ，如图2 1 所示。 图2 1 邮件过滤模型 垃圾邮件过滤可以选择在以上五个层次中任意一个层次进行，过滤越往外层，越 能有效减轻内层的压力，但实际上，每个层次的过滤都有其各自的特点，往往要在多 个层次同时进行过滤。路由器过滤一般采耿基于i p 地址的过滤方法。m t a 可选的过 滤方式有基于m 地址的过滤、基于邮件头的过滤，也可以进行基于内容的过滤。m d a 和m u a 可以进行各种过滤，但出于效率方面的考虑，更多的是进行基于内容的过滤。 表2 1 是一个各种过滤方式的组合列表。 表2 1邮件过滤在不同位置执行的影响 m t a) ar u a 信封数据 o ko k 邮件头数据 o k0 ko k 邮件体数据 ppo k 注：o k 可以采用的组合；p 该组合可能会带来性能上的影响。 目前，实际使用较多的是基于i p 地址的过滤。一些反垃圾邮件组织维护了一个 已知的发送垃圾邮件的名单，m t a 可以通过d n s 查询等方式使用这项服务。 堆十最人熵摸型的垃圾邮件过滤系统f l j f 究墙圾| j | l ；件过滤投术研究的现状 基于内容的过滤可以应用在m t a 、m d a 、m u a 上。目前的主要研究方向是将 机器学习、人工智能等方法相结合，自动学习垃圾邮件的特点并进行过滤，这种方法 要解决的一个关键问题是如何提高过滤的准确度。 2 2 基于i p 地址的垃圾邮件过滤 基于i p 地址的过滤技术是使用最广泛的一种过滤技术，包括基于网络的碑地址 过滤技术，如b g p 和路由器访问控制列表：基于主机的i p 地址过滤技术，如t c p w r a p p e r s 和主机路由表的过滤：以及目前最常用的i pn t t k 黑、白名单的过滤【3 1 。 黑、白名单技术基于这样一个界定：白名单中的任何邮件都是合法邮件，而黑名 单中的任何邮件都是垃圾邮件。因此通常的做法是收集一个黑、白名单列表，可以是 电子邮件地址或邮件服务器的域名、i p 地址等，收到邮件时进行实时检查，将符合 黑名单的邮件直接删除或者放入垃圾邮件央中。黑、白名单一般由具有权威性的组织 提供，如中国互联网协会等。个人也可以根据需求定义和维护自己的黑、白名单。 其它常用的基于i p 地址的过滤技术包括d n sm x 记录查找、反向d n s 查找、 群发过滤等。 基于i p 地址的过滤技术使用简单方便，可以应用于备个层次，但是由于它只是 简单地屏蔽掉可能产生垃圾邮件的【p 地址，而很多垃圾邮件是通过别人的服务器来 转发的，所以可能会伤及无辜。 2 3 基于邮件头的垃圾邮件过滤 即通过分析邮件头信息，检查发件人的信息是否符合过滤要求，一般采用正则式 对邮件头信息进行关键字匹配，根据匹配结果决定阻塞或者接收包含特定单词或者短 语的邮件。分析邮件头时，注意理解下面几点将有助于识别含有伪造内容的信头p j 。 ( i ) 收件人地址和发件人地址 一般的m u a 是从用户在s m t p 的d a t a 命令后输入的数据中提取f r o m 、t o 等 字段内容的，但如果发件人的m u a 不是按照这个逻辑工作，或者发件人有意使这两 个字段的内容与s m t p 会话时使用的m a i lf r o m 和r c p t t o 的内容不一致时，就 会发生发件人是自己的名字或者收件人不是自己的名字等情况。 垃圾f | l | f 件过滤技术研究的现：状基于最大熵模型的垃圾邮件过滤系统研究 ( 2 ) 关于o p e nr e l a y 如果发件人使用的不是自己的服务器，而是利用别人服务器的o p e nr e l a y 漏洞， 就会为追踪邮件的真实来源带来困难。如果一个邮件服务器与发件人、收件人都不属 于同一个域，就应该怀疑是否利用了o p e nr e l a y 。 ( 3 ) r e c e i v e d 信息 邮件头中的r e c e i v e d 信息是由s m t p 服务器自动加入的，发送者无法干预因 此，通过比较r e c e i v e d 域，特别是第一次经过的邮件服务器的r e c e i v e d 域，可以识 别出伪造的发件人地址。 2 4 基于内容的垃圾邮件过滤 黑、白名单方法有其局限性，而规则匹配方法的缺点在于规则都是人工指定的， 需要不断发现和总结、更新，而且手工制定规则比较耗时，准确率也受到了限制。 目前，把垃圾邮件过滤与文本分类、信息过滤、机器学习等技术结合起来，将这 些领域中常用的方法引入到垃圾邮件过滤中，对邮件正文内容进行分析，成为研究的 热点。基于内容的分析能够自动获得垃圾邮件的特征，及时捕捉垃圾邮件特征的变化， 是一种更为精确的垃圾邮件过滤技术【9 i 。 2 4 1 垃圾邮件过滤与文本分类 文本分类( t e x tc a t e g o r i z a t i o n ) 的任务是根据预先确定好的类别体系，将待分类 文本分到相应的类别中去。图2 2 表示了文本分类器的一般模型。 图2 2 文本分类器的一般模型 基十最大熵摸型的垃圾邮件过滤系统研究 垃圾邮件过滤技术研究的现状 从文本分类角度来看，垃圾邮件过滤是一个二类非兼类分类问题，即将邮件分类 为“垃圾邮件”和“合法邮件”，因此，多种文本分类算法可以用于垃圾邮件过滤。 然而垃圾邮件过滤是一个特定领域的分类问题，与一般的文本分类在很多方面又有所 区别，主要表现在： ( 1 ) 文本分类的对象通常是自由文本，没有结构性，而邮件是一种半结构化文 本，其邮件头信息为垃圾邮件过滤提供了重要依据。 ( 2 ) 文本分类中每个类别的内容一般不会改变，而“垃圾邮件”类别是和用户 密切相关的，更注重个性化，用户对垃圾邮件的判别准则会随时间改变，而且垃圾邮 件本身的内容、形式也在不断地变化。 ( 3 ) 垃圾邮件过滤对性能要求比较高，因此要尽可能的采用计算简便、速度快 的文本分类算法，不仅要考虑过滤效果，还要考虑过滤效率。 ( 4 ) 从过滤效果上看，用户宁愿接收更多的垃圾邮件，也不希望将合法邮件误 判为垃圾邮件而过滤掉，因此，垃圾邮件过滤更重视f 确率。 2 4 2 垃圾邮件过滤与文本过滤 文本过滤是指从大量的文本数据流中寻找满足用户需求的文本的过程。预先给定 用户需求和输入文本流，文本过滤系统必须首先根据用户需求建立一个初始的用户模 板：然后判断文本流中的每一个文本是否符合用户需求，将符合用户需求的文本提交 给用户；由用户对文本作出是否符合其需求的评判，根据评判结果自适应地修改用户 模板，以更好地符合用户需求【1 0 】。文本过滤系统的一般组成如图2 t 3 所示。 图2 3 文本过滤系统的一般组成 垃圾邮件内容过滤可以看成一个文本过滤问题：初始时，提供一定的垃圾邮件和 合法邮件给过滤系统学习，得到过滤模型：过滤的信息源是动态的邮件流；用户可以 指定自己的垃圾邮件集和合法邮件集，供系统反馈学习，建立新的过滤模型。 垃圾邮件过滤技术研究的现状基于= 砬火熵模型的垃圾邮件过滤系统研究 2 4 3 过滤性能评价体系 垃圾邮件过滤的性能评价通常借用文本分类和信息检索领域的相关指标f 4 】【”1 。具 体地，假设测试邮件集合中共有封邮件，为方便叙述，定义如表2 2 所示的变量。 表2 2 过滤性能评价相关变量( 单位：封) 实际为垃圾邮件实际为合法邮件 系统判定为垃圾邮件 ab 系统判定为合法邮件 cd 冥中n = a + b + c + d ，j ，= 4 + c 为买际的垃圾邮件数目，f = b + d 为实际的 合法邮件的数目。定义如下评价指标来衡量垃圾邮件过滤系统的性能： ( 1 ) 召回率：r e c a l l = 1 0 0 ，即垃圾邮件“检出”率，反映了过滤系统 爿+ c 。 发现垃圾邮件的能力，召回率越高，“漏网”的垃圾邮件就越少。 ( 2 ) 正确率：p r e c i s i o n = 二。+ 1 0 0 ，即垃圾邮件“检对”率，反映了过滤系 a + b 统“找对”垃圾邮件的能力，正确率越大，合法邮件误判为垃圾邮件的可能性越小。 ( 3 ) 精确率：a c c u r a c y = 竺娑1 0 0 ，即对所有邮件的“检对”率。 ( 4 ) 错误率：e r r o ，：旦箬1 0 0 ：l a c c “阳砂，即对所有邮件的“判错，率。 ( 5 ) f 值：f = ( f 1 虿2 + 了1 万) ( p 品r e 焉c i 磊s i o 了n * 乏r 矿e c a l l ) + 1 0 0 ，它将召回率和正确率综合成 一个指标，能更全面地反映过滤系统的性能，其中口表示召回率和正确率的权重因子， 通常取纠棚只= 篇。 ( 6 ) 虚报率：f a l l o u t = l + 1 0 0 。 b + d ( 7 ) 漏报率：m i s sr a t e = 亡1 0 0 = 卜r e c a l l 十l 一 另外，在实际的垃圾邮件过滤中，人们往往不希望将合法邮件误判成垃圾邮件。 为了表示不同情况下垃圾邮件系统的代价，a n d r o u t s o p o u l o s 等提出了代价因子的概 念【1 2 】。设将合法邮件误判为垃圾邮件的损失是将垃圾邮件误判为合法邮件的损失的五 倍( 月 1 ) 刚可以定义： 幕十垃人炳模型的垃圾j 船件过滤系统研究 垃圾邮件过滤技术研究的现状 垃圾邮件过滤系统的加权错误率：形跏= 面2 丽b + c 垃圾邮件过滤系统的加权精确率：腑c c = 杀号鲁 = 1 一胁 在没有任何垃圾邮件过滤器( 即所有的邮件被当成合法邮件) 的情况下，可以计 算基准的加权错误率：形甜= i 睾瓦 豫代价野t c r = w 胁e r r h = 老耥= 熹 t c r 越高，表明当前垃圾邮件过滤系统的性能越好，如果t c r 小于1 ，则表示 过滤性能比不进行任何过滤还差，因此，实际应用中t c r 至少应该大于l i j 。 关于兄的取值问题，a n d r o u t s o p o u l o s 试验了三个不同的值：旯= 1 , 9 ； 0 9 9 9 ，a 的 值越大，说明系统要求越严格，把合法邮件误判成垃圾邮件造成的后果越严重。 目前，机器学习方法在垃圾邮件过滤中的应用总体上分成两种：基于规则的方法 和基于概率统计的方法+ 。前者通常得出人们可以理解的显式规则：后者往往通过某 种计算表达式推出结果。本质上，概率统计方法可以看成规则方法的一种特例，只不 过得到的规则是一种“隐式规则”。 不管是基于规则的方法还是基于概率统计的方法，在使用时都经历从训练到过滤 的过程。利用已有的训练集合( 正例+ 反例) 训练出相应的垃圾邮件规则( 包括显式 规则或隐式规则) ，然后将规则应用到新邮件判定中，实际应用中可能还会加入人机 交互过程，通过用户的反馈对过滤规则进行更新。 2 4 4 基于规则的过滤方法 基于规则的方法通过训练得到显式规则，规则方法学习的过程实际上是归纳总结 的过程，通过考查训练样本，归纳总结出其中规律性的东西来形成规则。 ( 1 ) r i p p e r 本节的部分内容参考文献 4 】 垃圾邮件过滤技术研究的现状 摹于墩大熵模型的垃圾邮件过滤系统研究 r i p p e r 是c o h e n 提出的一种基于规则的方法，比传统的规则方法速度更快、性能 更高【1 4 】。c o h e n 的实验表明，r i p p e r 方法的正确率和决策树方法c 4 5 相差不大，但 是速度却提高了两个数量级。d r u c k e r 将r i p p e r 方法用于垃圾邮件过滤，取得了8 0 以上的精确率【1 5 】。 ( 2 ) 决策树方法 决策树( d e c i s i o nt r e e ) 是著名的规则方法之一。一般决策树的训练过程是，首 先通过按照某种属性的顺序自顶向下地生成一棵大规模的树结构，树的节点是属性 名，而边是属性值；然后将这棵树剪枝到合理的大小，以避免过适应问题。分类过程 从树的根节点开始，根据当前文档在每个节点对当前属性值的判断，选择不同的分支， 重复迭代，直到树的叶子节点。因此，从树根到树叶的一条路径构成一条规则。著名 的决策树算法有1 1 3 3 、c 4 5 等。c a r r e r a s 使用决策树来过滤垃圾邮件，得到的垃圾邮 件过滤的正确率和召回率都在8 8 左右【嗡】。 ( 3 ) b o o s t i n g 方法 b o o s t i n g 方法通过对已有的分类器( 称为弱规则或者弱假设) 进行加权求和得到 最终的分类器( 称为强规则) 。它通过关注弱规则的错误而逐渐组合成强规则，是一 种错误驱动的方法。a d a b o o s t 是b o o s t i n g 方法中最常用的一种。c a r r e r a s 和n i c h o l a s 将a d a b o o s t 引入到垃圾邮件过滤中，取得了很好的性能【1 6 i 1 7 1 。a n d r o u t s o p o u l o s 在实 验中引入了另外一种b o o s t i n g 方法一l o g i t b o o s t 。 ( 4 ) 粗糙集方法 粗糙集( r o u g hs e t ) 理论是由p a w l a k 提出的一种研究不完整、不确定知识和数 据的表达、学习、归纳的理论方法，其研究对象是一个多值属性集合描述的向量集合。 它通过集合等价关系操作来确定属于给定类的最大对象集合和可能属于给定类的最 小对象集合，从而指导分类决策。r o u g hs e t 通常经过属性约简( 消除对决策属性没 有影响的属性) 和属性值约简( 消除对决策属性没有影响的属性值) 来简化分类规则。 刘洋等将r o u g hs e t 引入到垃圾邮件过滤中，采用了11 种非文本属性来进行邮件分 类，在一个小规模的垃圾邮件样本上的实验，可以达到8 0 左右的正确率f 1 9 1 。于洪 等提出了垃圾邮件过滤系统的粗糙集模型，提取1 2 种邮件特征作为决策属性建立相 应的信息模型，利用实验和经验数据对系统模型进行了验证，取得了较好的效果【2 0 1 。 接十最人墒模型的垃圾邮件过滤系统研究 垃圾邮件过滤技术研究的现状 2 4 5 基于统计的过滤方法 ( 1 ) 贝叶斯方法 贝叶斯( b a y e s ) 方法通过计算样本d 属于类别c = s p a r e ，l e g i t i m a t e 的概率 p ( c ，id ) ，取其中较大概率对应的类别q 作为d 所属的类别。根据b a y e s 公式 北旧= 掣 其中p ( q ) 为类先验概率，p ( dj q ) 为类条件概率。 朴素贝叶斯( n a i v eb a y e s ) 是b a y e s 方法中使用最广泛的一种。假设d 由互相独 立的多个特征w ( _ ，= l ，2 ，n ，n 表示d 中不同特征的个数) 组成，则有 n p ( d i q ) = p ( i q ) + p ( w 2 i q ) h - + p ( w i q ) = 兀p ( w ，i q ) 对同一个样本而言，p ( d ) 不变，而p ( q ) 和p ( w ，i q ) 都可以由训练集得到。 尽管这种特征之间的独立性假设往往并不成立，但在实际应用中，由于其计算简 单，且具有良好的过滤性能，因此，这种方法成为应用最广泛的过滤方法，通常作为 与其它过滤方法进行性能比较的基础。 s a h a m i 【2 1 1 用n a v y eb a y e s 方法进行垃圾邮件过滤实验。a n d r o u t s o p o u l o s 1 2 1 也利用 n a i v eb a y e s 来判别垃圾邮件，考查了不同文本预处理形式对过滤结果的影响，实验 表明如果对原始文本去除停用词和进行词汇还原，能得出最佳的结果。s c h n e i d e r 比 较了n a i v eb a y e s 的两种事件模型：多变量贝努里事件模型与多项式事件模型，结果 表明当多项式事件模型具有较高的精确率。 除了n a i v eb a y e s 外，其它的b a y e s 模型也得到了一定的应用。m e r t z 23 i 不是采用 独立性假设而是考虑使用n g r a m 模型来估计相关的概率。另外，a n d r o u t s o p o u l o s 使用了一种f l e x i b l eb a y e s 模型，虽然该模型仍然采用独立性假设，但是对概率的估 计使用了高斯分布模型。 ( 2 ) k n n 方法 k n n ( k n e a r e s t n e i 曲b o r ，k - 近邻) 是最常用的基于实例的方法，它没有训练过 垃圾邮件过滤技术研究的现状基于最火熵模型的垃圾邮件过滤系统研究 程，分类时直接将待分类样本与训练集合中的每个样本进行比较，然后根据前t 篇相 似样本的类别得到新样本的类别。样本之间相似度的计算有多种方法，最常用的就是 计算两个样本向量之间的夹角余弦值。 在文本分类中，k n n 常常能够取得好的结果，但是由于其分类速度的局限性， 不太适用于对分类速度要求较高的垃圾邮件过滤场合。尽管如此，出于研究的目的， 一些文献【2 4 i 仍然将它应用于垃圾邮件过滤领域。实验表明，在t 取较小值的情况下性 能较好，与n a i v eb a y e s 的结果几乎相当。 ( 3 ) s v m s v m ( s u p p o r t v e c t o r m a c h i n e ，支撑向量机) 通过构造最优线性分类面来指导分 类，可以直接用于线性可分问题，而对于线性不可分的情形，则可以通过非线性变换 转化为某个高维空间中的线性问题，在此变换空间中求最优分类面。在文本分类中， s v m 是公认的较好的方法之一。d m c k e r 【”1 将s v m 用于垃圾邮件过滤。结果表明采 用二值表示的s v m 的性能稍高于采用多值表示的s v m 。a n d r o u t s o p o u l o s i 8 1 也在实验 中引入