（计算机软件与理论专业论文）基于rough集的垃圾邮件过滤技术的研究与应用.pdf

摘要 摘要 随着互联网上邮件的广泛使用，垃圾邮件的问题变得同益严重，它不仅消 耗网络带宽和计算机时空开销，而且会对企业的正常运行和用户的正常工作造 成严重的干扰。要解决垃圾邮件问题，必须综合法律、技术等手段。 目前，国内外垃圾邮件过滤的技术有黑白名单技术、基于关键词匹配技术， 以及基于内容的垃圾邮件过滤技术等等。本文对基于内容的垃圾邮件过滤技术 研究现状进行了详细的介绍。它是当前解决垃圾邮件问题的主流技术，主要包 括基于规则的内容分析方法和基于概率统计的内容分析方法两个研究方向。 由于r o u g h 集理论具备不需要任何先验信息，能在保持分类能力不变的前 提下，通过属性约筒，导出问题的决策规则的特点，因此在基于内容的垃圾邮 件过滤技术上，引入r o u g h 集理论。将该理论用于垃圾邮件过滤是一个新的研 究方向。 。 首先，文中重点研究分析基于r o u g h 集的经典属性约简算法。进一步提出 了一种改进的r o u g h 集属性约简算法。实验证明该算法是可行的，高效的，尤 其适用于大数据集的属性约简。 然后详细介绍了基于r o u g h 集的垃圾邮件过滤系统模型和工作流程；在垃 圾邮件过滤的特征选择问题上，采用了改进的r o u g h 集属性约简算法过滤掉冗 余特征和不相关特征；将邮件正文内容特征集和邮件头的7 个相关特征综合实 现对邮件的识别，从而提高了系统过滤的正确率，降低垃圾邮件的错判率。 最后通过三组对比实验表明：将r o u g h 集理论应用于垃圾邮件过滤领域是 可行的、高效的。 关键词：电子邮件；r o u g h 集；属性约简；垃圾邮件过滤 a b s t r a c t a b s t r a c t w i t ht h ew i d e s p r e a du s eo fe - m a i l i n c r e a s i n g l ys e r i o u sp r o b l e m i ti sn o to n l y o nt h ei n t e m e t ，s p a mh a sb e c a m ea n c o n s u m et h en e t w o r kb a n d w i d t ha n dt h e t i m e s p a c eo v e r h e a do fc o m p u t e rb u ta l s od i s t u r bt h ee n t e r p r i s e sn o r m a lr u n n i n g a n d t h eu s e r sn o r m a lw o r k t os o l v et h ep r o b l e mo fs p a m ，w em u s t u s et h e c o m p r e h e n s i v em e a n s ，s u c ha sl e g a la n dt e c h n o l o g y , e t c n o wa th o m ea n da b r o a dt h et e c h n o l o g yo fs p a mf i l t e r i n gi n c l u d e sb l a c ka n d w h i t el i s tt e c h n o l o g y , k e y w o r db a s e do nc o n t e n tf i l t e r i n ga n dt h et e c h n o l o g yo f c o n t e n t b a s e ds p a mf i l t e r i n ga n ds oo n t h ep a p e rg i v e sad e t a i l e di n t r o d u c t i o nt ot h e r e s e a r c hs t a t u so ft h ec o n t e n t b a s e ds p a r ef i l t e r i n gt e c h n o l o g y , w h i c hi sam a i n s t r e a m t e c h n o l o g yf o rs o l v i n gt h es p a mf i l t e r i n gp r o b l e ma tp r e s e n t ，a n di t st w or e s e a r c h d i r e c t i o n si s r e s p e c t i v e l y t h er u l e b a s e dc o n t e n ta n a l y s i sa p p r o a c h a n dt h e s t a t i s t i c - b a s e dc o n t e n ta n a l y s i sa p p r o a c h f o rr o u g hs e tt h e o r y ，w i t h o u ta n yp r i o ri n f o r m a t i o n ，c a nd e d u c e dap r o b l e m s d e c i s i o nr u l e st h r o u g ha t t r i b u t er e d u c t i o no nt h ep r e m i s eo fm a i n t a i n i n gt h e c l a s s i f i c a t i o nc a p a b i l i t y , s ow ei n t r o d u c er o u g hs e tt h e o r yt ot h ef i e l do fs p a mf i l t e r i n g o nt h eb a s i so ft h et e c h n o l o g yo fc o n t e n t - b a s e ds p a mf i l t e r i n g ，w h i c hi san e wr e s e a r c h d i r e c t i o nf o rf i l t e r i n gs p a m f i r s t l y , t h i sp a p e rs t u d i e da n da n a l y z e dt h ec l a s s i c a la t t r i b u t er e d u c t i o na l g o r i t h m b a s e do nr o u g hs e tt h e o r ya n df u r t h e rp r o p o s e da ni m p r o v e da l g o r i t h mo fa t t r i b u t e a l g o r i t h mb a s e do nr o u g hs e t t h ee x p e r i m e n ts h o w e dt h ei m p r o v e da l g o r i t h mi s f e a s i b l ea n de f f i c i e n t ，e s p e c i a l l ys u i t a b l ef o rt h el a r g ed a t as e t s s e c o n d l y , t h es y s t e mm o d e lo fs p a mf i l t e r i n gb a s e do nr o u g hs e ta n d i t sw o r k p r o c e s sa r ed e s c r i b e di nd e t a i li nt h i sp a p e r ；i nt h ep r o b l e mo ff e a t u r es e l e c t i o n o ft h e s p a mf i l t e r i n g ，w ea d o p t e dt h ei m p r o v e da l g o r i t h mt o r e d u c et h er e d u n d a n ta n d i r r e l e v a n tf e a t u r e sa n di n t e g r a t e dt h em a i lh e a d ss e v e nc h a r a c t e r i s t i c sw i t ht h em a i l b o d y sc h a r a c t e r i s t i c st oi d e n t i f ya ne - m a i lf o ri m p r o v i n gt h ef i l t e r i n gs y s t e m s a c c u r a t er a t ea n dd e c r e a s et h es p a m se r r o rr a t e f i n a l l y , t h r e eg r o u p sc o n t r a s t i n ge x p e r i e n t ss h o w e dt h a tt h es p a mf i l t e r i n gb a s e d o nr o u g hs e ti sf e a s i b l ea n de f f e n c i e n t k e yw o r d s ：e - m a i 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 ；s p a mf i l t e r i n g i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得南昌大学或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：王云4 4 - 签字日期：少移年肛月知日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：；萝导师签名： 1扒 签字日期：瑚年肛月) o e t签字日期：力谚年2 月2 oe l ， 第1 章引言 第1 章引言 1 1 研究背景和意义 1 1 1 垃圾邮件的存在的状况 根据全球电子商务专家中国诺网的统计【1 1 ：在最经常使用的互联网服务中， 有8 7 6 5 的用户选择了电子邮件服务，居互联网服务的首位。在美国，电子邮 件为它的第一大互联网应用，使用率达到9 2 【2 】；在韩国，根据其国家互联网发 展局( n i d a ) 调查显示：网民的使用率为8 0 8 ；而根据中国2 0 0 8 年7 月份的 互联网络发展状况统计报告显示：中国的电子邮件目前使用6 2 6 ，该报告同时 给出近两年我国电子邮件使用率和变化情况，如表1 1 所示。 表1 1 电子邮件使用率和变化情况( 中国) 随着i n t e m e t 在全球的发展，上网人数不断的增多，作为互联网服务中最重 要的电子邮件服务，其规模也在全球不断的扩大。但是随着电子邮件被人们广 泛使用和享受其带来巨大便利的同时，也引发了大量的问题，其中最为严重、 最为引人注目的就是垃圾邮件的问题。 位于美国加利福尼亚州的巴拉库达网络安全公司，在对其世界各地大约5 万家客户收到的超过1 0 亿封电子邮件进行分析后，公布报告说：2 0 0 7 年全球互 联网用户收到的电子邮件中，近9 5 是垃圾邮件【3 】。 中国互联网协会反垃圾邮件中心公布的( ( 2 0 0 7 年第四季度中国反垃圾邮件 调查报告1 4 】表明：2 0 0 7 年第四季度中国网民平均每周收到的垃圾邮件比例为 5 5 6 5 。2 0 0 8 年第一季度反垃圾邮件状况调查报告中调查显示，中国网民每周 收到垃圾邮件的比例为5 6 7 0 。 以上的数据已经足以说明垃圾邮件的传播在全球的泛滥成灾。其根本原因 是早期的电子邮件系统采用的都是开放式接受并转发所有的邮件，而广告商和 黑客们等人正是以此为漏洞，不断的往用户的邮箱中发送不同的广告邮件、病 第1 章引言 毒等人们不希望接收到的邮件。 1 1 2 垃圾邮件的定义 那么，什么是垃圾邮件呢? 又如何来定义一封邮件是否属于垃圾邮件? 到目 前为止，国际上对于垃圾邮件还没有一个统一的定义。但习惯上都把那些大量 的、未经用户许可，但却被强行塞入用户邮箱的电子邮件称为垃圾邮件。 2 0 0 3 年2 月2 6 日，中国互联网协会颁布的中国互联网协会反垃圾邮件规 范中的第三条【5 】对垃圾邮件给出了一个明确的范畴定义： ( 一) 收件人事先没有提出要求或者同意接受的广告、电子刊物、各种形 式的宣传品等宣传性的电子邮件； ( 二) 收件人无法拒收的电子邮件； ( 三) 隐藏发件人身份、地址、标题等信息的电子邮件： ( 四) 含有虚假的信息源、发件人、路由等信息的电子邮件； 按照上述界定，满足上述四种情况的邮件都属于垃圾邮件的范畴。反之， 其他邮件称为“合法邮件”。实际上，对大多数用户，收到的垃圾邮件大部分都 是没有主动订阅的广告、电子期刊等宣传品，其基本特征是“不请自来”、带有商 业目的或者政治目的。 在国际上，垃圾邮件的英文名称有很多种叫法，如s p a m ，j u n km a i l ， u c e ( u n s o l i c i t e dc o m m e r c i a le m a i l ，即不请自来的商业邮件) 或u b e ( u n s o l i c i t e d b u l ke m a i l ，即不请自来的大量电子邮件) 。一般使用s p a m 一词的较多。 在本文中，将按照中国互联网协会反垃圾邮件规范中第三条的解释说 明来表述垃圾邮件的概念，其英文表述采用s p a m 一词。 1 1 3 过滤垃圾邮件的必要性和意义 据来自f e r r i c 调研公司于2 0 0 3 年发布的一份调研报告( 其量化了垃圾邮件 每年给企业带来的损失) 显示：美国企业在此方面损失8 9 亿美元；欧洲企业损 失2 5 亿美元：另外，美国和欧洲的互联网服务提供商每年也因此损失5 亿美元。 在新加坡，2 0 0 3 年进行的一项调查表明，垃圾电子邮件给新加坡网民在效 率方面造成的损失约为2 3 0 0 万新元( 约合1 5 2 3 万美元) 。 在中国，2 0 0 7 年第4 次反垃圾邮件调查报告显示：垃圾邮件将给中国的国 民经济每年造成约为1 8 7 2 亿人民币的损失，给邮件运营商带来的直接损失大约 2 第1 章引言 为1 2 亿，间接损失则无法估算。综合起来，给中国国民经济造成的总体损失为： 1 8 8 4 亿人民币。与2 0 0 6 年的1 0 4 3 1 5 亿相比增长了8 0 6 。 另外，由于国内垃圾邮件的泛滥现状导致我国许多i p 网段遭受国外反垃圾 邮件组织的封杀，严重影响了国内邮件服务的正常通信。从2 0 0 4 年到2 0 0 6 年3 月上旬，中国被国外反垃圾邮件组织列入黑名单的i p 地址段共计2 5 2 7 个。而自 2 0 0 5 年1 1 月至2 0 0 6 年3 月上旬期间，中国被国外反垃圾邮件组织列入黑名单 的i p 地址段共计4 7 9 个，比2 0 0 5 年最后一次调查的结果被封的3 2 3 个多出1 5 6 个。 显而易见，垃圾邮件的问题已经给整个国际社会带来了巨大的损失，它可 以说是i n t e r n e t 带给人类最具争议性的副产品，它的泛滥已经使整个因特网不堪 重负。它的危害表现在以下三方面： ( 一) 对用户的影响 垃圾邮件的常见类型主要是商业宣传邮件、政治宣传邮件、非法色情邮件 和病毒邮件，具有数量多、反复性、强制性、欺骗性、不健康和传播速度快等 特点，严重干扰了用户的正常生活，侵犯收件人的隐私权和邮箱空间，并耗费 收件人的时间、精力和金钱。特别是非法色情邮件和不健康邮件将严重侵害青 少年的身心健康，给社会主义精神文明建设造成不良的影响。 ( 二) 对i s p 的影响 占用大量网络、存储和运算资源，造成邮件服务器拥堵，严重影响了运营 商的服务质量和用户的满意度。 ( 三) 对社会的影响 垃圾邮件的蔓延，容易被不法黑客所利用，它通过大面积的病毒传播和突 发性的邮件攻击，造成服务器、网络的瘫痪，特别是非法反动、色情暴力邮件 的传播，给社会经济带来严重的损失、给政府行政安全管理带来极大的隐患， 给人们日常生活带来严重的影响，给社会造成一定的不稳定性。 面临着垃圾邮件问题日益严重的现状；为了还互联网社会一个清洁的环境； 为了减少单位企业的损失，提高其工作效率；为了邮件用户远离垃圾邮件的骚 扰；人们开始从多方面寻找解决方案。可见，寻找出一个有效的垃圾邮件过滤 的方法急迫需要的、是有着深远的社会意义和巨大的经济价值的。 3 第1 章引言 1 2 国内外垃圾邮件的过滤现状 1 2 1 垃圾邮件过滤的法律实施现状 目前各国己认识到垃圾邮件的危害，相继出台多种措施，制定了反垃圾邮 件法，希望规范互联网上发送电子邮件的行为，通过法律手段对发送垃圾邮件 者或公司进行处罚，以取得“垃圾邮件战”的胜利。在美国、日本、韩国、英国、 法国、意大利、瑞典、挪威、加拿大、印度等国家都制定了相应的反垃圾邮件 法。 新加坡规定，公司不能未经许可将电子邮件、文字或多媒体信息发送给消 费者；所有广告类电子邮件在发出时，必须清楚标明其广告性质，并注明发送 人的真实电子邮件地址；消费者可无需付费退订这类邮件；消费者可要求违反 规定的垃圾电子邮件发送人赔偿损失，赔偿费为每封垃圾电子邮件2 5 新元( 约 合1 6 5 美元) ，赔偿总额最高不超过1 0 0 万新元( 约合6 6 2 万美元) 瑞士联邦政府从2 0 0 8 年4 月1 日起加强对滥发电子广告等垃圾邮件的管理 力度。新修订的法规禁止通过电子邮件、短信或其他电信手段，在未经收件人 允许的情况下，大量发送或转发广告等垃圾邮件。 同本总务省2 0 0 8 年2 月宣布，将采取措施加强对垃圾邮件的管理，包括对 发信者处以最高3 0 0 0 万日元罚款、禁止向信箱用户发送其事先不了解的广告邮 件、加强与海外管理部门的合作等。这些措施将被纳入特定电子邮件法修正 案( 简称修正案) ，于2 0 0 8 年8 月提交日本国会。 但是，许多国家在建立了反垃圾邮件法后，垃圾邮件问题仍然很突出，收 效不大。原因主要是：第一是该法没有得到有力的执行，因为大部分网民和企 业对垃圾邮件采取了默许的态度，没有起诉垃圾邮件发送者，让垃圾邮件继续 泛滥；第二，也是最重要的原因，互联网是无国界的。由于国际上没有一个统 一的反垃圾邮件法律或措施，当通过其他国家来转发垃圾邮件时，本国法律就 无法适用，因此光通过立法来治理垃圾邮件问题还远远不够。 1 2 2 垃圾邮件过滤的技术研究现状 国内外已经有很多科研机构在进行有关邮件分类的研究，从而过滤掉垃圾 邮件，并已经取得了良好的效果。目前常用的垃圾邮件过滤技术有【6 j ：基于黑白 名单的过滤技术、基于规则的过滤技术和基于内容的过滤技术。 4 第1 章引言 ( 一) 基于黑白名单的过滤技术 这种技术最早也是最常用的一种垃圾邮件过滤技术，一般的邮件服务器都有 该功能【_ 7 1 。过滤系统在处理新到达的邮件时，首先查看邮件头部的发送方地址，对 于地址处于白名单中的邮件将全盘接收，而对于处于黑名单中的邮件则直接拒 收。该技术的优点是简单明确，最大程度地减少了处理垃圾邮件所需的系统资源。 但它的缺点也很明显，在处理陌生人来信时无能为力；需要不断更新和维护；容 易造成误判；效率不高。 黑白名单可以由用户提供，也可由相关组织机构进行统一管理，通常是按照 某个地址发送邮件的性质来判断。国际上的一些反垃圾邮件组织f 如m a p s 、 o r b s 、s p a m c o p 等) 以及国内的反垃圾邮件组织( 如c a s a ) 都维护一种称为实时 黑名单( r e a l t i m e b l a c kl i s t ) 的i p 地址数据库，简称为r b l ，任何i s p 都可以订阅这 些数据库，使这类邮件在到达之前就自动被拒绝。 ( 二) 基于规则的过滤技术 这种技术可以按照预先设定好的规则对邮件标题和信件内容等进行多项过 滤，比如结合内容扫描引擎，根据垃圾邮件的常用标题语、垃圾邮件受益者的姓 名、电话号码、w e b 地址等信息关键词进行过滤。若在邮件中找到属于垃圾邮 件关键词的个数达到一定阀值，则判定此邮件为垃圾邮件，然后在邮件服务器上 删除它们。这一工作原理决定了基于规则的过滤技术时效性较差。它的优点是 规则可以共享，因此它的推广性很强。一个人写出的规则可以提供给多个人，多个 服务器使用。 ( 三) 基于内容的过滤技术 该技术是从邮件的主题和正文上分析理解邮件所表达的意思，以此来判断 邮件是否为正常或垃圾邮件。基于内容的过滤方法一般都能智能自动地分析邮 件，但是存在一定的误判率。这种技术可以在网关、邮件服务器以及邮件客户 端上处理。基于内容的邮件过滤技术有多种方法【8 】，本文将在第2 章它们进行详 细地介绍。 虽然以上所述的过滤技术发挥了很大的作用，但仍不尽如人意，最主要的 问题有两点：一是错分类( 如将正常邮件当作垃圾邮件) 比较高，使得电子邮 件用户对现有的垃圾邮件过滤软件不信任；其二是邮件服务器端的处理量太大， 速度较慢，使电子邮件用户不能够及时的收到重要的邮件。 针对以上问题，如何提高邮件过滤器的分类准确率，是一个值得深入研究 5 第1 章引言 的问题，因此本课题将r o u g hs e t 理论应用在基于内容的垃圾邮件过滤系统中以 实现高效的过滤功能。 1 3 论文的主要研究内容 本文的主要研究内容： ( 1 ) 研究目前互联网上垃圾邮件的存在状况，给出垃圾邮件的定义，总结 垃圾邮件的危害，从而提出垃圾邮件的过滤已经成为全球广为关注的重要课题。 ( 2 ) 分析总结当前国内外主要的垃圾邮件过滤技术，尤其是基于内容的邮 件过滤技术，对常用邮件分类方法的基本原理进行详细介绍。 ( 3 ) 相比传统文本挖掘问题处理的对象，邮件包含了种类更丰富的信息， 比如邮件头中发信人、收信人、发信时间、邮件中继次数、邮件类型等等，如 果忽略掉这类信息，就是一个巨大的损失。因此本文将邮件头的特征和邮件文 本的特征结合进行分析，因为邮件文本的一些特征对分类的判断来说，是非常 重要的。 ( 4 ) 在获得最优或次优特征子集算法方面，已往的基于内容的垃圾邮件过 滤系统都是采用常规的算法实现。本文中，分析研究目前存在的经典的r o u g h 集属性约简算法，提出一个改进的r o u g h 集属性约简算法，并将其应用于垃圾 邮件过滤系统中。 ( 5 ) 建立一个基于r o u g h 集的电子邮件过滤系统的模型，并分析研究其中 的r o u g h 集分析模型。 1 4 论文的组织结构 本文组织结构： 第1 章：对垃圾邮件的现状进行分析介绍，阐述对垃圾邮件进行过滤的必 要性和意义。 第2 章：对目前流行的基于内容的垃圾邮件过滤技术进行详细地分析介绍， 为将r o u g h 集理论应用于基于内容的垃圾邮件过滤中打好理论基础。 第3 章：对r o u g h 集理论的发展和基本概念进行了详细地介绍。 第4 章：对r o u g h 集理论中的经典属性约简算法进行了详细地分析和介绍， 提出了一种改进的粗糙集特征约简算法，分析了其时间复杂度和空间复杂度。 6 第1 章引言 第5 章：介绍了基于r o u g h 集理论的电子邮件过滤系统的系统框图，分析 每一个模块的实现技术。研究了反垃圾邮件系统的评价方法和评价指标，收集 互联网上公开的邮件语料库，利用k 次交叉验证法对反垃圾邮件系统进行评测， 并通过与采用传统方法的反垃圾邮件效果对比，验证了该系统过滤垃圾邮件的 有效性。 第6 章：给出了结论和展望。 7 第2 章基丁内容的垃圾邮件过滤技术的研究 第2 章基于内容的垃圾邮件过滤技术的研究 2 1 概述 通常，并不仅仅是某几个固定的发件人在发送垃圾邮件，发送者在不断地 变化，黑、白名单方法有局限性。规则方法的不足之处在于规则都是人工指定 的，需要人们不断去发现和总结、更新，人为因素比较多，一些没有经验的用 户可能很难提供有效的规则。而且，手工制定规则比较耗时，准确率也受到了 限制。随着时间的变化，垃圾邮件的特征也在变化，让用户维护这些规则也不 是一件易事。 一个很自然的想法是，对电子邮件的内容进行分析，识别出垃圾邮件。这 就将垃圾邮件过滤与文本分类和信息过滤联系起来了，将文本分类和信息过滤 中常用的方法引入垃圾邮件过滤任务，这种邮件过滤技术称为“基于内容的垃圾 邮件过滤”或者“垃圾邮件内容过滤”。这种内容过滤技术提供了更为准确的邮件 过滤方法，可以自动获得垃圾邮件的特征，并即时捕捉到垃圾邮件特征的变化。 目前，人们己经应用于垃圾邮件内容过滤领域的一些分类算法p j 包括：k 近邻 ( k - n e a r e s tn e i g h b o r ) 、决策树( d e c i s i o nt r e e s ) 、贝叶斯算法( b a y e s i a nc l a s s i f i e r s ) 、 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 、b o o s t i n g 方法等等。 这些方法可以分成两类，一是基于规则的内容分析方法，这类方法通过对 邮件内容进行智能分析，得出人们可以理解的显式规则，如决策树、b o o s t i n g 方 法等；另外一类是基于统计的内容分析方法，训练过程是一个统计学习过程， 通过某种计算表达式推出结果，得到相应的分类器，如贝叶斯算法、k 近邻方法 等。本质上，概率统计方法可以看成规则方法的一种特例，只不过概率统计方 法中得到的规则是一种不被人轻易理解的“隐式规则”。 不管是基于规则的内容分析方法还是基于概率统计的内容分析方法，在使 用时都经历从训练到过滤的过程。通过已有的邮件训练集合( 正例+ 反例) i ) t l 练出 相应的垃圾邮件规则( 包括显式规则或隐式规则) ，然后将规则应用到新的邮件判 定中去。在实际系统中可能还会加入人机交互过程，通过用户对判定结果的认 可与否对已有的垃圾邮件规则进行更新。 8 第2 章基于内容的垃圾邮件过滤技术的研究 2 2 基于规则的内容分析方法 基于规则的内容方法是通过训练得到显式规则( 如：i f 邮件包含s a r em o n e y t h e n 该邮件为垃圾邮件) 。规则方法学习的过程实际上是归纳总结的过程，通过 考查一个个的训练样本，归纳总结出其中规律性的东西来形成规则。规则方法 的主要优点是可以生成人类理解的规则。缺点是在规律性不明显的应用领域效 果较差。目前，这方面主要有r i p p e r 方法、决策树方法、b o o s t i n g 等方法。下 面对这几种方法进行详细的介绍。 2 2 1r i p p e r 方法 19 9 6 年，w i l l i 锄w c o h e n 1 0 】利用一种基于规则的r i p p e r 方法，该方法比 传统的规则方法速度更快、性能更高。该方法先学习训练集中的所有正例，不 断地向一初始集为空的规则集中加入规则，形成一个正例的规则集，然后利用 所有反例不断地对规则集中的关键字加入约束条件，最后用这个包含了约束条 件的规则集来做出决策。为了减小规则集的大小，作者对构造好的规则集进行 了人工处理，仅使用了文本中出现频率很高的或具有高信息的单词。 d r u c k e r 1 1 】将r i p p e r 方法用于垃圾邮件过滤，在1 0 0 0 个文本特征的情况下， 通过从正例中学习规则并对规则进行修剪来获取垃圾邮件的覆盖规则，在某单 位员工真实邮件语料库( 含8 5 0 篇垃圾邮件和2 1 5 0 篇非垃圾邮件) 上取得了8 0 上的精确率。 2 2 2 决策树( d e c i s i o nt r e e ) 方法 决策树( d e c i s i o n t r e e ) 方法的实质是从训练集中学习得到以决策树的形式 表示的分类规则。分类时，将待分类的邮件按照属性值自树根向下逐步比较判 断，到叶子结点时，就可以确定邮件所属类别。 一棵最简单的决策树结构如图2 1 所示。树的内部结点表示属性或者属性的 集合，分支上的权值表示属性的取值，叶子结点是类别。图中，实例空间分为 三类：1 、2 和3 ，例如，当属性a 的取值为a 2 ，属性b 的取值为b 2 ，属性c 的取值为c 1 时，属于类别1 。决策树实际上就是一系列规则的形式化表示，如“如 果属性a 取值为a 2 ，属性b 取值为b 2 ，属性c 取值为c 1 ，则属于类别1 ”。训 练的过程就是从样本中学习决策树或者说是学习规则，分类的时候就是沿着决 策树往下走到叶子，找到类别归属。 9 第2 章基丁内容的垃圾邮件过滤技术的研究 b l丽 扇目 c 2 0b6b 图2 1 一颗最简单的决策树 按照上述的理论所述，y a n l e i t l 2 】等学者提出了利用决策树来建立邮件过滤器 的方法，主要是利用来源于邮件文本中的具有较高互斥信息的特征项单词，以 及从邮件头中手工提取的信息短语来建立决策树，进而通过决策树来对邮件进 行分类。该方法比较适合训练集中邮件数较小、待分类邮件中的非法邮件较多 的情况，而对有大量的邮件需过滤，或邮箱中有较多的合法邮件时，其合法邮 件的查全率和准确率都较低。 2 2 3b o o s t i n g 方法 实际上，b o o s t i n g 方法并不是一种特定的学习方法，它一般结合决策树等学 习方法使用，是在已有学习方法基础上的进行“投票”的技术。其基本思想是：给 每个训练样本都赋予一个权重，进行t 次迭代，每次迭代后，对分类错误的样 本加大权重，使得下一次的迭代更加关注这些样本，得到最终的分类器。这里 的每个分类器称为弱规则或者弱假设，加权求和以后的分类器称为强规则。 b o o s t i n g 通过关注弱规则的错误而逐渐组合成强规则，它是一种错误驱动的方 法，该种方法有多种形式，如a d a b o o s t 、a d a b o o s t m 1 、a d a b o o s t m h 等，其 中，a d a b o o s t 是b o o s t i n g 方法中最常用的一种。 c a r r e r a s 1 3 1 等人将a d a b o o s t 引入到垃圾邮件过滤，获得了很高的性能。 1 0 尽 第2 章基丁内容的垃圾邮件过滤技术的研究 c a r r e r a s 的方法中还考察了不同深度决策树作为弱学习器下的过滤性能，他们发 现，随着深度的增加，过滤的正确率将更高。与此类似的是，d e s o u z a 0 4 1 使用了决 策树方法作为弱学习器在l i n g s p a m 语料上进行垃圾邮件过滤的两组实验，一组 是采用一层的决策树进行多遍b o o s t i n g 循环，另一组是采用完全的决策树进行少 量b o o s t i n g 循环。实验证明，两组情况下都能取得很高的精确率( 9 8 以上) 。 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 tb o o s t ，其弱 学习器采用了对数回归方法，学习到的是实数值而不是分类结果，最后通过一 个阈值来实现分类。从发表的结果看，l o g i tb o o s t 在p u l 上的结果略逊于 a d a b o o s t 。b o o s t i n g 方法的最主要缺点是训练速度较慢。 2 3 基于统计的内容分析方法 基于统计的方法是指根据统计理论，先对已分类的邮件训练样本进行学习， 提取出能表示各类邮件的特征向量及特征值，再将根据这些值对以后的邮件进 行计算，由此来完成分类过滤。目前用于垃圾邮件过滤的基于统计的内容分析 方法主要有：基于贝叶斯理论、基于支持向量机理论和基于神经网络理论及基 于其他理论的方法。 2 3 1b a y e s 方法 贝叶斯分类器是基于贝叶斯定理所提出的，其训练过程是一个统计学习过 程，得到相应的分类器。最基本的形式是朴素贝叶斯分类器，它是建立在“贝叶 斯假设”的基础上：即假定特征与特征之间是独立的。其原理是首先计算待识别 文本d ，属于某个类别的概率e ( c ，i d ，) ，然后根据概率的分布情况，将待识别邮 件d ，归类于概率最大的类别中去。 实际应用过程中，概率p ( c ，l d ，) 采用贝叶斯公式2 1 ： p ( c j 限) = 掣 ( 2 - 1 ) p ( c ，) 是类的先验概率，p ( 砍lc ，) 是类条件概率。对同一篇文本，p ( d ，) 不 变。设以表示为特征集合( ，。，：，j 。) ，n 为特征个数，假设特征之间相互独立， 则有： 第2 章基丁内容的垃圾邮件过滤技术的研究 p ( d ，ic j ) = p o lc j ) 宰p q 2c ) 幸p ( ，。lc ) = up ( f ，ic ，) ( 2 2 ) # i p ( c ，) 和p ( t ，ic ，) 都可以利用训练集估计。 目前此种方法已经应用于垃圾邮件过滤系统中，并得到了广泛地好评。 1 9 9 8 年，s t a n f o r d 大学的s a h 锄i 【1 5 】将该方法引入到垃圾邮件过滤。s a h a m i 采用了自己收集的邮件作为实验数据，并在过滤中注意到垃圾邮件具有一些不 同于合法邮件的特有属性：如，在快速致富类的垃圾邮件中，邮件文本中会含 有大量的“f l e em o n e y ”，以及大量类似于“! ! ! ”的强调符号和“$ ，等符号；同时，垃 圾邮件还有许多非文本的域特征，如，垃圾邮件常来源于c o m 域、大部分没有 附件等。因此，s a h a m i 除了使用词汇作为特征外，还使用了词组特征和其他属 性特征，实验结果表明，其他属性特征能够较大幅度地提高过滤结果。 a n d r o u t s o p o u l o s 6 】也利用该方法来判别垃圾邮件。他采用了公开语料 l i n g s p a m 进行实验，并在实验中考查了不同文本预处理形式对过滤结果的影响。 因此，他指出如果对原始文本除去停用词和词干处理，能得出最佳的实验结果。 他的另一个工作是提出垃圾邮件的代价因子指标，并分析了不同过滤阈值条件 下代价因子的变化情况，他指出，一味地追求高的邮件j 下确率在系统实现时可 能会造成很大的代价。 在国内，也有很多学者将贝叶斯算法用于垃圾邮件过滤。谭立球i l6 j 提出将 贝叶斯算法和规则学习相结合的方法来构建邮件过滤器，采用信息增益来完成 特征选择。周威成【1 7 】采用朴素贝叶斯算法做为分类器，互信息做为特征选择。 蔡立军【1 8 】贝i j 采用向量空间模型来表征邮件文本，在朴素贝叶斯方法的基础上， 利用最小风险贝叶斯算法修正过滤器，并利用遗传算法处理特征向量的选取。 2 3 2s v m 方! 法 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) ，是统计学习理论【l 9 j ( s t a t i s t i c a l l e a m i n gt h e o r y , s l t ) 中最年轻的部分支，由v l a d i m i rn v a p n i k 博士 提出。它通过结构风险最小化准则和核函数方法，较好地解决了小样本与算法复 杂性的问题。 如图2 2 所示的二维两类线性可分情况，图中实心点和空心点代表两类样 本，h 为分类线，h 1 ，h 2 分别为过各类中离分类线最近的样本且平行于分类线 的直线，它们之间的距离叫做分类间隔( m a r g i n ) 。所谓最优分类线就是要求分 1 2 第2 章基于内容的垃圾邮件过滤技术的研究 类线不但能将两类正确分开( 训练错误率为o ) ，而且使分类间隔最大。前者是 保证经验风险最小( 为o ) ，分类间隔最大实际上就是使推广性的界中的置信范 围最小，从而使真实风险最小。推广到高维空间，最优分类线就成为最优分类 面。 h 2 oo w o 图2 2 最优分类面 支持向量机的基本思想可以概括为：首先将输入空间变换到一个新空间， 然后在这个新空间中求取最优线性分类面。 d r u c k e r t l l 】将s v m 用于英文垃圾邮件的过滤，实验结果为在错纠率小于1 的限制下遗失率为2 3 6 。d r u c k e r 还得到一个结论就是，采用二值表示的s v m 的性能稍高于采用多值表示的s v m 。a n d r o u t s o p o u l o s 也在实验中引入了s v m 方法【刀。 2 3 3k n n 方法 k n n ( kn e a r e s tn e i g h b o r ，k 近邻) 是最常用的基于实例的方法，它没有 训练过程，它直接利用训练集分类：计算待分类文本与每一篇训练文本的距离， 找出最相近( 最相似) 的k 篇文本，然后根据文本所属类别划分这k 篇文本， 将待分类文本分到包含文本数最多的那一类中去。计算文本之间的相似度有多 种方法，最常用的就是计算两个文本向量之间的夹角余弦值。 在文本分类中，k n n 常常能够取得好的结果，但是由于其分类速度的局限 性，不太适用于对分类速度要求较高的垃圾邮件过滤场合。a n d r o u t s o p o u l o s 【7 j 1 3 第2 章基于内容的垃圾邮件过滤技术的研究 使用了一种类k n n 方法，该方法使用k 组最近的距离而不是k 个最近的样本来 计算，如果多个样本同待过滤邮件距离相差不大的话，则这些样本都将用于确 定最后的结果，此时，过滤中真正使用的样本数目大于k 。实验表明，k n n 在k 取较小值的情况性能较好，和朴素贝叶斯分类器的结果性能几乎相当。 2 4 小结 本章总结了基于内容的垃圾邮件过滤的研究现状，介绍常用的过滤技术的 原理和特点。 目前该技术主要分为基于规则的内容分析方法和基于统计的内容分析方 法，前者是通过分析邮件的正文内容得到人们可以理解的显式规则，后者则是 通过统计的方法，得到隐式的规则。 同时在该章中详细介绍了目前的常用过滤技术，如决策树方法、b o o s t i n g 方 法、b a y e s 方法等等。并对各类别的现有研究成果进行了详细介绍。 1 4 第3 章r o u g h 集理论简介 第3 章r o u g h 集理论简介 3 1r o u g h 集的概述 r o u g h 集理论是一种新的处理模糊和不确定性知识的数学工具。它于1 9 8 2 年以波兰数学家p a w l a k 为代表的研究者在研究不精确、不确定性和不完全知识 表示和分类的基础上首次提出【2 0 1 。1 9 9 1 年，p a w l a k 教授出版的第一本关于r o u g h 集的专著r o u g hs e t s ：t h e o r e t i c a la s p e c t so f r e a s o n i n ga b o u td a t a 和1 9 9 2 年s l o w i n s k i r 主编的关于r o u g h 集应用及其相关方法比较研究的论文集的出版，推动了国 际上对r o u g h 集理论与应用的深入研究。 国内r o u g h 集的研究始于1 9 9 4 年【2 1 1 ，王珏、苗夺谦、王国胤、曾黄麟等人 在将r o u g h 集理论引入我国方面作出了重要的贡献。刘清等探讨了r o u g h 集在 近似推理、模态逻辑和智能代理方面的理论研究情况，张文修、梁吉业、吴伟 志等人提出了基于随机集的r o u g h 集模型，并研究了r o u g h 集理论同包含度理论 之间的关系。马志锋、刑汉承等在r o u g h 控制方面作了深入的研究。从2 0 0 1 年 开始，每年都召开了一次中国r o u g h 集与软计算学术研讨会( c r s s c ) 。 r o u g h 集的主要特点有【2 2 】：能处理各种数据，包括不完整数据和众多变量 的数据；能处理数据的不精确性；它能在保留关键信息的前提下对数据化简， 求得知识的最小表达和知识各种不同颗粒层次；它能识别和评估数据间的相关 关系，从数据中揭示出概念简单、易于操作的模式：它能从经验数据中产生精 确而又易于检查和证实的规则等；最为重要一点是，它不需要预先给定某些特 征或属性的数量描述，如统计学中的概率分布、模糊集理论中的隶属度或隶属 函数和神经网络中的权值等，而是直接从给定问题出发，通过不可分辨关系和不 可分辨类来确定问题的近似域，从而找出该问题中的内在规律。正是由于r o u g h 集无需对知识或数据的局部信息给予主观评价，r o u g h 集理论对不确定性的程度 的描述相对于其他方法更客观，应用范围更广泛。 近年来，r o u g h 集理论在许多重要的实际生活中都有应用，利用r o u g h 集 理论处理的主要问题包括数据库中的数据约简、数据相关性的发现、数据意义 的评估、由数据产生决策控制算法、数据的近似分类、数据中的相似性或差异 性的发现、数据中范式的发现以及因果关系的发现。特别地，r o u g h 集方法在医 1 5 第3 章r o u g h