（计算机应用技术专业论文）基于内容过滤的反垃圾邮件技术研究.pdf

基于内容过滤的反垃圾邮件技术研究 摘要 随着因特网的迅猛发展，在线的可用电子信息业迅速增加，电子 邮件作为一种最快捷、最经济的通信方式也得到了飞速发展。但是同 时，许多垃圾邮件也在网络中蔓延，占据了邮件服务器中的大量存储 空间，用户往往要花费大量的时间去删除这些垃圾邮件。因此，研究 邮件的自动过滤具有重要的意义。 目前经常采用的垃圾邮件过滤技术一般包括白名单与黑名单技 术、规则过滤】以_ 及基于关键词匹配的内容扫描等。另外还有一种就是 从电子邮件的文本内容入手，使用文本分类算法，对邮件进行分类。 垃圾邮件过滤中常用的文本分类方法有简单贝叶斯、k 一近邻、决策树 等。基于概率的朴素贝叶斯算法具有方法简单、运算速度快、分类精 确度高等优点，在文本分类中得到了广泛的应用。由于在邮件过滤过 程中，合法邮件被误判为垃圾邮件将可能给用户带来据大的损失，因 此在邮件过滤中就要采取适当的措施以减小损失。 具体来说，本文的工作主要包含以下内容： 1 ) 简述了垃圾邮件问题的背景。包括垃圾邮件的定义、历史、 泛滥原因以及危害。 2 ) 概述了垃圾邮件过滤研究的现状。简要描述了一些基本概念 和常用的垃圾邮件过滤算法。 、3 ) 介绍文本分类算法在邮件过滤上的应用，总结了常用的特征 选择方法、分类算法以及通用的邮件语料库和垃圾邮件过滤的评价体 系。 4 ) 详细分析邮件过滤中的简单贝叶斯算法。介绍了贝叶斯分类 方法的现状、贝叶斯算法的两种模型、基于最小风险的贝叶斯决策， 以及垃圾邮件中的反馈学习和一些改进朴素贝叶斯分类器的建议，还 在l i n g s p a m 语料上实验了朴素贝叶斯算法，比较了特征数量、垃圾 邮件的阈值以及语料的预处理层次等因素对实验结果的影响。 5 ) 综合各种过滤技术，设计了一个具有高度灵活性和可扩展性 的客户端垃圾邮件过滤系统模型，总结了贝叶斯过滤算法的基本步 骤，给出了一个贝叶斯过滤器的设计方案。 关键词：垃圾邮件过滤文本分类简单贝叶斯特征抽取 r e a r c ho nc 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 o l o g y a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e t ，t h eo n l i n ee le c t r o n i c i n f o r m a t i o ni sb o o m i n g a n de l e c t r o n i cm a i lb e c o m et h ef a s t e s ta n dm o s t e c o n o m i c a lf o r mo fc o m m u n i c a t i o na v a i l a b l e u n f o r t u n a t e l y , al o to fj u n k m a i l s ( a l s or e f e r r e dt oa s “s p a m ”) a r ep o p u l a ra tt h es a m et i m e t h ej u n k m a i l sn o to n l yf i l lu pm a i ls e r v e rs t o r a g es p a c e ，b u ta l s om a k eu s e rs p e n d m u c ht i m eo nr e m o v i n gt h e s ej u n km a i l s a sar e s u l t ，i ti ss i g n i f i c a n tt o e x p l o r ea na u t o m a t e dm a i lf l t e r n o w a d a y s ，b l a c k l i s to rm i t e l i s tt e c h n o l o g y ，r u l e b a s e df i l t e r i n g a n dk e y w o r d b a s e dc o n t e n tf i l t e r i n ga r et h em o s tc o m m o na n t i s p a m a p p r o a c h e s a n o t h e ra p p r o a c hi su s i n ga u t o m a t e dt e x tc a t e g o r i z a t i o na n d i n f o r r n a t i o nf i l t e r i n gt of i l t e rs p a m s o m ea l g o r i t h m so ft e x t c a t e g o r i z a t i o n s u c ha sn a i v eb a y e s ， 删a n dd e c i s i o nt r e ec a nb e a p p l i e dt of i l t e rs p a m c o m p a r e dw i t ho t h e rt e x tc l a s s i f i e r s ，n a i v eb a y e s a l g o r i t h mh a sb e e nw i d e l yu s e di nt h ea r e ao f t e x tc l a s s i f i c a t i o nb e c a u s e o ft h es i m p l i c i t y , e f f i c i e n c ya n dv e r a c i t y h o w e v e r , i tw i l lc o s tal o ti f t h ef i l t e rm i s c l a s s i f yl e g i t i m a t em a i la sj u n ki nt h ep r o c e s so ff i l t e r i n g j u n km a i l s ow em u s tt a k es o m ea c t i o nt op r e v e n ti t t h ec o n t e n t so ft h i sa r t i c l ea r ea sf o l l o w i n g ： 2 3 4 i n t r o d u c e dt h eb a c k g r o u n do ft h es p a m ，i n c l u d i n gt h ed e f i n i t i o n ， h i s t o r y ，h a r mo fs p a m s u m m a r i z e dt h es t a t eo ft h es p a mf i l t e r i n g i n v e s t i g a t i n ga n t i s p a r ep r o b l e m f r o mt h et e x t c a t e g o r i z a t i o n p e r s p e c t i v e ，i n t r o d u c i n gt h ea p p r o a c h e so ff e a t u r es e l e c t i o n ，c l a s s i f i e r s a n de - m a i lc o r p u si nt h i st a s k a n a l y z e dt h en a i v eb a y e s i a nm e t h o dd e t a i l e d i n c l u d i n gt h es t a t eo f n a i v eb a y e s i a n ，t w om o d e l so ft h eb a y e s i a n ，s o m ea d v i c e so f i m p r o v i n gt h en a i v eb a y e s i a nf i l t e r c o m p a r e dt h ei n f e c t i o n s o f f e a t u r en u m b e r , t h r e s h o l da n dt h ev a r i a t i o n so fc o r p u si nl i n g s p a m 5 i nt h ee n d ，s u m m a r i z e dm a n yk i n d so ft e c h n o l o g i e sa n dd e s i g n e da 1 1 f l e x i b 。l ea n de x t e n s i b l em o d e lo fa n t i s p a r ef i l t e ro nt h ec l i e n ts i d e d e s c r i b e dt h eb a s ics t e p so fn a i v eb a y e s i a na l g o r i t h m sa n db u i l da m o d e lo f i t k e y w o r d s ：s p a mf i l t e r i n g t e x tc a t e g o r i z a t i o n n a i v eb a y e s f e a t u r ee x t r a c t i o n 1 1 1 独创性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电 大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 斗 日期：j 坐 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定， 即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学 校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论 文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用 影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密 后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学 本人签名 导师签名 用本授权书。 日期：h 盘扯 日期： 1 1 背景 1 1 1 垃圾邮件的定义 第一章绪论 i n t e m e t 的迅速发展，人与人的交往更加快捷方便，电子邮件( e m a i l ， e l e c t r o n i cm a i l ) 以其快捷、低廉的特性日益成为人们信息交互的重要工具。人 们用它交流思想、传输文件、发表意见等，逐渐成为日常生活中不可缺少的通信 手段之一。但是电子邮件在其给人们带来极大便利的同时也带来了一些负面影 响，那就是我们每天收到的邮件中有很大一部分是“不请自来”的，它们有些 是商业广告，有些是政治宣传，有些是关于色情的广告，还有一些甚至是病毒， 这些就是我们所说的垃圾邮件。 。迄今为止，垃圾邮件在国际上没有统一的定义。在中国互联网协会反垃圾 邮件规范中垃圾邮件被界定为： 1 ) 收件人事先没有提出要求或者不同意接收的广告、电子刊物以及各 种形式的宣传邮件。 2 ) 收件人无法拒收的电子邮件。 3 ) 隐藏发件人身份、地址、标题等信息的电子邮件。 4 ) 含有虚假的信息源、发件人、路由等信息的电子邮件。 5 ) 含有病毒、恶意代码、色情、反动等不良信息或有害信息的邮件 按照上述界定，对大多数用户，收到的垃圾邮件大部分都是没有主动订阅的 广告、电子期刊等宣传品，其基本特征是“不请自来”、带有商业目的( u n s o l i c i t e d c o m m e r c i a le m a i l ) 或者政治目的。现在各种病毒邮件也越来越泛滥，成为了又 一种形式的垃圾邮件。实际上，垃圾邮件的判定会因人而异，不同的用户对同一 邮件的判定结果可能存在差异。 1 1 2 垃圾邮件的历史 1 9 8 5 年8 月一封通过电子邮件发送的链锁信，一直持续至u 1 9 9 3 年，这是首次 关于垃圾邮件的记录。1 9 9 3 年6 月份，在i n t e m e t 上出现了名为“m a k e m o n e y f a s t ”的电子邮件。 1 9 9 4 年4 月份，c a n t e r & s i e g e l 的法律事务所把一封移民顾问服务广告邮件 发到6 0 0 0 多个新闻组，一时间群情激奋。这是首次用s p a m 称呼垃圾邮件。 1 9 9 5 年5 月出现第一个专门的垃圾邮件群发软件f l o o d g a t e 。 2 0 0 5 年1 1 月，中国互联网络信息中心( c n n i c ) 发布的4 2 0 0 5 年第三次 反垃圾邮件调查报告”显示，我国在今年己成为继美国之后的全球第二大垃圾 邮件受害国，今年2 月至8 月，来自中国内地和香港的垃圾邮件几乎翻了一番， 占全球垃圾邮件的比例从6 2 4 增加到1 1 6 3 。 由中国互联网协会反垃圾邮件中心开展的第三次反垃圾邮件专项调查结果 显示由2 0 0 5 年8 月n 2 0 0 5 年】o 月中国用户收到的垃圾邮件比例由6 0 6 3 上升到 6 1 5 3 ，如图卜1 所示。收到垃圾邮件数量由每周1 6 5 6 封上升到每周1 7 2 5 封。 圈i - i 我国网民近两年每周收到垃圾邮件比例的柱状图 1 1 3 垃圾邮件泛滥原因 垃圾邮件的泛滥主要有以下几个原因： 1 ) 宽带网络的快速发展，邮件发送的条件越来越便利。 2 ) 网络通信成本的下降，这样使得垃圾邮件发送的成本也随之下降。 3 ) 硬件性能的提高并且成本不断降低，垃圾邮件数量也因此有所增多，成 本也随之下降。 4 ) 成本与产出的巨大反差。垃圾邮件发送的成本极其低廉，几乎未零，其 产出却比较大。 5 ) 邮件的易伪造。现在的有关电子邮件的协议还不是很完善，使得邮件极 易伪造。 6 ) 缺乏法律与规范的约束。现在法律方面对垃圾邮件的立法几乎是空白， 完全靠技术解决垃圾邮件有些力不从心。 1 1 4 危害 作为垃圾邮件的发送方，其成本是极低的，通常是通过各种方式群发。而对 电子邮件服务提供商和用户而言，垃圾邮件却给他们带来很大的危害和损失。据 统计，美国每年因垃圾邮件造成的损失高达1 0 亿美元，全球的损失更高达2 0 亿美元。具体的说，其危害主要表现在以下几个方面： 1 ) 占用网络带宽，浪费网络资源，干扰邮件系统的正常运行。当有限的网 络资源和网络带宽上充斥大量的垃圾邮件时，就降低了网络的使用效 率。对邮件服务器而言，收到的垃圾邮件占用了它的磁盘空间，而且， 如果垃圾邮件得不到有效控制，用户会放弃邮箱，服务商将被迫终止服 务，给企业带来很大的损失。另外，当一些用户利用邮件服务器对外发 送垃圾邮件时，该服务器会被列入黑名单而遭外部封杀。因此，邮件服 务器既要拒收来自外部的垃圾邮件，还要阻止自己的邮件用户对外发送 垃圾邮件。 2 ) 浪费用户的宝贵时间和上网费用。如果我们每天都要花费一段时间来处 理垃圾邮件，工作效率就要降低，对整个社会来说，被浪费的时间更是 一大笔宝贵的财富。有关调查显示，2 0 0 3 年，网民平均每天需花费6 5 分钟来处理无用的邮件，单是下载垃圾邮件所花费的上网费与电话费， 全年就要浪费全球网民9 4 亿美元。 3 ) 对网络安全形成威胁。一些垃圾邮件传播色情、反动等各式各样的有害 信息，给社会带来危害。黑客们利用电子邮件系统发送数以万计的垃圾 邮件风暴攻击目标，使之瘫痪、拒绝服务。 4 ) 垃圾邮件和黑客攻击、病毒等结合也越来越密切，比如，s o b i g 蠕虫就 利用安装了开放的、可以用来支持邮件转发的代理。随着垃圾邮件的演 变，用恶意代码或者监视软件等来支持垃圾邮件已经明显地增加了。 2 0 0 3 年1 2 月3 1 ，巴西的一个黑客组织发送包含恶意j a v a s c r i p t 脚本的 垃圾邮件给数百万用户，那些通过h o t m a i l 来浏览这些垃圾邮件的人们 在不知不觉中已经泄露了他们的账号。越来越具有欺骗性的病毒邮件， 让很多企业深受其害，即便采取了很好的网络保护策略，依然很难避免， 越来越多的安全事件都是因为邮件产生的，可能是病毒、木马或者其他 恶意程序。 5 ) 除了以上几点外，某些国家也因垃圾邮件的泛滥使其国际形象受到了不 良的影响。 1 2 本文内容安排 本文将在垃圾邮件过滤技术特别是内容过滤技术上做一些探索，重点研究了 运用简单贝叶斯算法的邮件过滤。主要的工作归纳如下： 1 ) 垃圾邮件的定义、历史、泛滥原因、以及其危害等。 2 ) 垃圾邮件过滤的研究现状，包括一些基本概念一些如关键词过滤、黑白 名单等常用的客户端垃圾邮件过滤方法。 3 ) 文本分类方法在垃圾邮件过滤中的应用。 4 ) 贝叶斯分类方法的现状、贝叶斯算法的两种模型、基于最小风险的贝叶 斯决策以及在l i n g - s p a m 语料上的实验。 5 ) 设计了一个客户端垃圾邮件过滤系统模型，总结了贝叶斯过滤算法的基 本步骤，给出了一个贝叶斯过滤器的设计方案。 6 ) 对本文的总结以及展望。 2 1 基本概念 第二章垃圾邮件过滤研究现状 电子邮件的格式及其发送和收取过程是由一系列的r f c ( r e q u e s tf o r c o m m e n t s ) 定义的。其中r f c 8 2 2 定义了邮件的基本格式，随着电子邮件的广 泛使用，其传输的内容的形式也不断增多，增加了多用途互联网邮件扩展协议 m i m e ( m u l t i p u r p o s ei n t e r n e tm a i le x t e n s i o n s ) 标准作为对r f c 8 2 2 的补充，使 得从单一的文本到各种文档( 如：w o r d ，p d f 等) 以及图片、声音、视频等文件 都能通过电子邮件发送。m i m e 由r f c l 5 2 1 和r f c l 5 2 2 这两个标准构成。 在广义上来说电子邮件是一种半结构化的文档，它由一些列的提前定义好的 结构化域和一些可变长度的自由文本类型的域组成。 结 构 化 域 冀 构 化 域 图2 - 1 电子邮件结构简单示意图【2 1 如图2 1 ，f i e l dl 到f i e l ds 是结构化域，它包含一些如时间、发送者、收 件人、邮件类型等信息。f i e l ds + l 到f i e l dn 是一些非结构化的自由文本域，比 如主体、消息内容等。在进行垃圾邮件过滤时，从邮件的结构出发，寻找邮件特 征，综合邮件头一些结构化的信息以及邮件内容正文进行垃圾邮件过滤是现在垃 圾邮件过滤的一些基本方法。 在邮件的收发方面，r f c 8 2 1 规定了简单邮件传输协议s m t p ( s i m p l em a i l t r a n s f e rp r o t o c 0 1 ) ，它定义了电子邮件的发送机制。r f c1 7 2 5 规定了邮局协议 第三版p o p 3 ( p o s to f f i c ep r o t o c o l3 ，) ，定义从p o p 3 服务器收取邮件的机制。 矗八”=儿vn“儿v 图2 2 是一个电子邮件系统的系统示意图： ，图2 - 2 电子邮件系统简单示意图 首先来解释一下其中几个概念： 1 ) m u a ：m u a 即m a i lu s e ra g e n t ，邮件用户代理。m u a 是邮件阅读或 发送程序，如o u t l o o k ，在邮件系统中用户只与m u a 打交道，m u a 将邮件系统的复杂性与用户隔离开。 2 ) m t a ：m t a 即m a i lt r a n s f e r a g e n t ，邮件传输代理。m t a 是一个专用程 序，其作用类似于邮局，用于在两个机器之间发送邮件，m t a 决定了 邮件到达目的地的路径。 3 ) m d a - m d a 是m a i ld e l i v e r ya g e n t ，邮件递交代理。m t a 自己并不完 成最终的邮件发送，它要调用其他的程序来完成最后的投递服务，这个 负责邮件递交的程序就是m d a 。 图2 2 是利用t c p i p 协议进行电子邮件交换的示意图。发放者利用m u a 写好邮件，交给发送方的m t a ，发送方的m t a 再通过中继m t a 将邮件传送到 接收方的m t a 。中继m t a 可以没有，也可以是多个。m t a 与m t a 之间的通信 协议是s m t p 。m d a 将邮件递交给接收方的邮箱，接受者可以通过三种方式与 邮箱交互： 1 ) 利用网络文件系统直接访问； 2 ) p o p 协议； 3 ) i m a p ( i m e m e tm a i la c c e s sp r o t o c 0 1 ) 协议。 邮件过滤按照邮件系统的角色结构可以分为三类： 1 ) m t a ( 邮件传输代理) 过滤； 2 ) m d a ( 邮件递交代理) 过滤； 3 ) m u a ( 邮件用户代理) 过滤。 m t a 过滤是指m t a 在会话过程中对会话的数据进行检查，对于符合过滤条 件的邮件进行过滤处理。邮件会话过程中有两个阶段可以进行过滤：发送邮件数 据前和s m t p 连接时。 m d a 过滤是指m d a 在从m t a 中接收到信件，在本地或远程进行递交时进行 检查，对于符合过滤条件的邮件进行过滤处理，很多的m d a 女h p r o c m a i l 、m a i l d r o p 都支持在这个过程进行过滤。 m u a 过滤是邮件用户的客户端的过滤。多数流行的邮件客户端，女l o u t l o o k 、 o u t l o o ke x p r e s s 、n e t s c a p em a i l 、f o x m m l 等都支持m u a 过滤。 其中m t a 和m d a 属于服务器端过滤，而m u a 属于客户端过滤。 2 2 常用的垃圾邮件过滤方法 过滤( f i l t e r ) 是一种相对来说最简单却很直接的处理垃圾邮件技术。这种 技术主要用于接收系统( m u a ，如o u t l o o ke x p r e s s 或者m t a ，如s e n d m m l ) 来 辨别和处理垃圾邮件。从应用情况来看，这种技术也是使用最广泛的，比如很多 邮件服务器上的反垃圾邮件插件、反垃圾邮件网关、客户端上的反垃圾邮件功能 等，都是采用的过滤技术。 当前的垃圾邮件过滤技术主要有：关键词过滤、黑白名单、h a s h 技术以及 基于规则和基于邮件内容的过滤。这些技术一般都同时适用于服务器端和客户端 的邮件过滤。 2 2 1 关键词过滤 关键词过滤技术通常创建一些简单或复杂的与垃圾邮件关联的单词表来识 别和处理垃圾邮件。比如某些关键词大量出现在垃圾邮件中，如一些病毒的邮件 标题。这种方式比较类似反病毒软件利用的病毒特征一样。可以说这是一种简单 的内容过滤方式来处理垃圾邮件，它的基础是必须创建一个庞大的过滤关键词列 表。 这种技术缺陷很明显，过滤的能力同关键词有明显联系，关键词列表也会造 成错报可i i i i 较大，当然系统采用这种技术来处理邮件的时候消耗的系统资源会 比较多。并且，一般躲避关键词的技术比如拆词，组词就很容易绕过过滤。 2 2 2 黑白名单 黑名单( b l a c kl i s t ) 和白名单( w h i t el i s t ) ，分别是已知的垃圾邮件发送者 或可信任的发送者i p 地址或者邮件地址。现在有很多组织都在做* b l ( b l o c kl i s t ) ， 将那些经常发送垃圾邮件的i p 地址( 甚至i p 地址范围) 收集在一起，做成b l o c kl i s t ， l l ! t h s p a m h a u s 的s b l ( s p a m h a u s b l o c kl i s t ) 。一个b l 可以在很大范围内共享， 许多i s p 正在采用一些组织的b l 来阻止接收垃圾邮件。白名单则与黑名单相反， 对于那些信任的邮件地址或者i p 就完全接受了。 。 目前很多邮件接收端都采用了黑白名单的方式来处理垃圾邮件，包括m u a 和m t a ，当然在m t a 中使用得更广泛，这样可以有效地减少服务器的负担。 b l 技术也有明显的缺陷，因为不能在b l o c kl i s t 中包含所有的( 即便是大量) i p 地址，而且垃圾邮件发送者很容易通过不同的i p 地址来制造垃圾。 2 2 3h a s h 技术 h a s h 技术是邮件系统通过创建h a s h 来描述邮件内容，比如将邮件的内容、 发件人等作为参数，最后计算得出这个邮件的h a s h 来描述这个邮件。如果h a s h 相同，那么说明邮件内容、发件人等相同。这在一些i s p 上在采用，如果出现重 。 复的h a s h 值，那么就可以怀疑是大批量发送邮件了。 2 2 4 基于规则的过滤 基于规则的过滤器是比关键词过滤器更为高级和完善的技术。通过对大量合 法和非法邮件的综合分析，得到一个庞大的规则数据库。对新到邮件采用该规则 库进行评判，匹配的每条规则都有对应的分数，总分数达到某个阀值时，就认 为该邮件是垃圾邮件。规则的定义非常灵活，可以针对邮件的各个部分进行定义， 包括邮件头、邮件内容和邮件结构等。但是，要定义合适的规则并不是一件简单 的事情，随着垃圾邮件的发展，这些规则也应该得到及时的更新。不过要使得过 滤器有效，就意味着管理人员要维护一个庞大的规则库。 2 2 5 基于内容的过滤 通常并不仅仅是某几个固定的发件人在发送垃圾邮件，发送者在不断地变 化，黑白名单方法有局限性。规则方法的不足之处在于规则都是人工指定的，需 要人们不断去发现、总结和更新，人为因素比较多，一些没有经验的用户可能很 难提供有效的规则。而且手工制定规则比较耗时，准确率也受到了限制。随着时 间的变化，垃圾邮件的特征也在变化，让用户维护这些规则也不是一件易事。 一个很自然的想法是，对电子邮件的内容( 如正文文本) 进行分析，识别出 垃圾邮件。这就将垃圾邮件过滤与文本分类联系起来了，将文本分类中常用的方 法引入到垃圾邮件过滤中来。现在很多文本分类的方法可以直接用于垃圾邮件的 过滤问题中，比如贝叶斯方法、启发式规则、支持向量机s v m ( s u p p o r tv e c t o r m a c h i n e ) 方法、基于实例的学习( i n s t a n c e - - - b a s e d ) 方法( 包括最近邻方法和基于案 例的推理) 以及最大熵方法等等。 在本文中，作者将这种邮件过滤技术称为“基于内容的垃圾邮件过滤”或者 “垃圾邮件内容过滤”。这种内容过滤技术提供了更为准确的邮件过滤方法，可以 自动获得垃圾邮件的特征，并即时捕捉到垃圾邮件特征的变化。 第三章文本分类与垃圾邮件过滤 3 1 文本分类简介 图3 1 是一个文本分类的基本模型，从图中可以看到文本分类由训练过程和 测试过程构成的。在训练过程中，首先要生成训练文本的特征，得到特征的集合； 特征选择算法从文本特征的全集中抽取一个最优的特征子集；这里的“最优子 集是由评价算法来判定的，它根据分类器对由特征子集所表示的训练文本进行分 类，并对分类性能进行性能评价。在分类过程中，首先将测试文档用最优特征子 集表示，再经分类器分类，得到测试文本所属的类别。 图3 - 1 文本分类器基本模型 基于内容的垃圾邮件过滤实际上就是一个二值的文本分类问题，首先用大量 的已经明确分好类的正常邮件和垃圾邮件对分类器进行训练，然后用这个训练好 的分类器对以后收到的电子邮件进行分类过滤。文本分类的任务是根据预先确定 好的类别体系，将待分类文本分到相应的类别中去。从文本分类角度来看，垃圾 邮件过滤就是要求将邮件分为垃圾、非垃圾两类中的一类，是一个二值分类问题。 我们可以将电子邮件经过预处理提取出邮件正文的文本内容，利用文本分类的算 法识别垃圾邮件，这也是目前垃圾邮件过滤技术研究的一个趋势。 文本分类与垃圾邮件过滤同时也有很大的区别，其主要表现在： 1 ) 垃圾邮件过滤对分类结果的准确性要求更高，因为若将一封非垃圾邮件 分类为垃圾邮件有可能使用户蒙受很大的损失。 2 ) 无论是客户端还是服务器端的垃圾邮件过滤对实时性的要求比较高，因 此必须选择一个计算简单、快速、高效的文本分类算法。 3 ) 对于文本分类而言，某个文档属于哪个类别一般都是比较固定的，其它 因素影响其类别的变化的可能性很小。而垃圾邮件则不同，它是针对个 人而言的，非常个性化，它很有可能会随着用户的兴趣爱好以及职业等 变化而改变，而且垃圾邮件的发送者很有可能根据过滤器的特征而改变 其发送的垃圾邮件的内容和形式。这样就使得在垃圾邮件过滤时必须提 供一种学习和反馈策略，以使得过滤器能够适应新变化。 3 2 文本的表示 计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产 生对文章内容的模糊认识，而计算机并不能轻易地”读懂”文章，从根本上说，它 只认识0 和l ，所以必须将文本转换为计算机可以识别的格式。 目前，在信息处理方向上，文本的表示主要采用向量空问模型( v s m ) 。通 常有布尔型向量空间模型和数值型向量空间模型。假如有一个文档集，对于一个 特定的文档d ，w j 是其对应的特征项，即d = ( w ，w ，一w 。) ，在布尔向量空间中， 若该项在文档中出现则特征值为1 ，反之，若该项在文档中没有出现，则特征值 为0 。布尔向量空间模型通常用于基于规则的学习算法中，在文本分类中，分类 规则仅仅考虑某特征在文档中有没有出现。 在数值向量空间模型中，特征项的值可以用一个函数计算得到，常用的计算 特征权值的方法有五种，本文将在下一节中阐述。这样，每一文档都可以用有一 定特征值的特征向量来表示。 由于布尔型向量空问模型没有考虑到特征项在文本中的出现频率这一特性， 因此，相对于数值型空间模型来说，分类精确度有所下降。 3 2 1 特征项 特征项通常定义为用空格键或各种标点符号等隔开的一系列连续字符串，通 常情况下，特征项即为有意义的单词或词组。基于单词的特征向选择与抽取不仅 方法简单，而且有更高的分类精度。例如： t h e r ea r e m a n y m e t h o d st of i l t e r j u n k m a i l 在这句话中共有8 个特征项单词，每个特征项单词出现一次。 3 2 2 特征项的权值 特征项权值的计算方法主要有五种。假定f ( a ) 是一个计算特征权值的函数， 在文档的向量空间模型中，特征项权值的计算方法主要包括： f ( a ) = l o g ( a + 1 ) 公式( 3 - 1 ) f ( a ) = 石公式( 3 - 2 ) f ( a ) = 忑a 公式( 3 3 ) 在t f i d f 学习算澍4 1 中利用单词在文档中出现的频率( t f ) 和每个特征项 在整个数据集文档的反向频率( i d f ) 来计算权值，i d f 定义为： ，州礼矧 公式( 3 - 4 ) 其中n 表示整个集合中包括的文档数，n ，是集合中包括了特征项t 的文档数。 假定n ( t ，d ) 表示文档d 中所包含的特征项t 的次数，则t f i d f 公式定义为： t f i d f ( t ，d ) = n ( t ，d ) 木i d f ( t ) 公式( 3 - 5 ) 另一种广泛使用的且简单的方法为仅用特征项单词在文本中出现的次数来 计算特征项权值。这种方法首先假定每个特征项与一个主题相关，对于每个主题， 都有一些与主题相关的文档集，计算公式为： f ( a ) = a 3 2 3 特征项的选择与抽取 公式( 3 - 6 ) 许多研究者在建立向量空间模型的过程中，利用单词和聚类单词作为特征 项，例如“l o wc o s t ”、“g e tr i c hq u i c k l y ”可作为两个特征项。l e w i s 5 】通过基于 单词、基于词组、基于聚类单词和基于聚类词组这四种常见特征项的抽取方法进 行实验分析与比较，实验表明了基于单词的特征项表示法对于其它三种特征项表 示法来说，不仅方法简单，而且具有更高的分类精确度，其中基于聚类词组的特 征项表示法的分类精确度最低，基于单词的特征向表示法比基于词组的特征向表 示法的精确度甚至高2 0 一3 0 ，这主要是因为基于单词的特征项表示法在文本中 有更高的出现频率。 特征项数量的多少会影响到学习算法的性能。理论上，特征向的数量越多， 模型的精确度就越高。但是，特征项的数量过多，并不能显著提高分类的精确度， l e w i s i s 用实验说明了当训练集中特征项的数量比较少时，分类的精确度会随着 特征项数量的增加而增加；但是，当特征项集合的数量增大到一定的数量时，精 确度达到最大；随后，分类的精确度会随着特征项的数量的增加而减小；另外， 随着特征项的数量的增加，学习算法的复杂会增加，学习的时间也会显著增加。 因此，在构建分类器时，必须考虑到特征项数量的多少，如果特征项过多，必须 采取一些措施减小特征项的数量。 常用的特征选择方法有1 ： 1 ) 文档频次 文档频数即d f 。它是最简单的评估函数，其值为训练集合中该单词发生的 文本数。d f 评估函数的理论假设稀有单词可能不含有用信息，也可能太少而不 足以对文本分类产生影响，也可能是噪音，因此可以删去。显然它在计算量上比 其它评估函数小得多，但在实际运用中它的效果却很好。d f 的缺点是稀有单词 可能在某一类文本中并不稀有，也可能包含着重要的判断信息，简单地舍弃，可 能影响分类器的精度。因此在实际运用中并不直接使用d f 。通常认为d f 太小的 词没有代表性，而d f 太大的词又没有区分度，所以基于d f 的特征选择方法只留 下那些d f 介于中间的词作为特征。 2 ) 互信息 互信息即m u t u a li n f o r m a t i o n ，简称m i ，定义如下： m i ( t ) = 2 篓p ( c i ) l o g 掣 = ) l o 号掣 公式( 3 7 ) p ( c ；) 表示第谈文本在训练文本集合中出现的概率，p ( t ) 表示词维训练文 本集合中出现的概率，p ( t l c i ) 表示在第j 类的文本中芒的出现概率。m i 越大，词 和类的共现程度越大。 3 ) 文本中单词的信息增益 信息增益最1 i n f o r m a t i o ng a i n ，简称i g ，定义如下： i c i c 1 g ( t ) = - z p ( ? ，) l o g p ( c ，) + p ( f ) p ( c ，it ) l o g p ( c 。if ) + i = ti = 1 旧 尸( f ) 尸( c l t ) l o g p ( c ff ) 公式( 3 - 8 ) i g ( t ) 反映了该词为整个分类所提供的信息量。 上式中，p ( f ) 表示词f 不出现的概率，p ( c ，l f ) 表示词f 出现的情况下文本属 于类的概率，p ( c ，lf ) 表示词f 不出现的情况下文本属于类的概率。下面的公式中 相应变量的含义与此相同。 4 ) z 2 统计量( c h i ) 批，c ，) = 酉石币n 历x ( a 河d - 瓦b c ) 而2 公式( ，3 9 ) z 2 v g ( ) ：艺p ( c ，) z 2o ，c ，) 公式( 3 一l o ) a 、b 、c 、d 均表示文本数量，如表3 1 所示，n = a + b + c + d 。 表3 - 1 文本分布表 c 类文本集合非q 类文本集合 f 出现 ab f 不出现 cd z 2 统计量度量词和类别的独立性，z 2 越大，独立性越小，相关性越大。z 2 嘴 表示对所有类别求平均的z 2 统计量。 5 ) 相对熵 咖) = 善i c lp ( c ，i t ) l 。g 等 ( f ) = ，o 等 公式( 3 - 1 1 ) 也称为k l 距离( k u l l b a c k - l e i b l e rd i v e r g e n c e ) ，反映了文本类别的概率分布 和在出现了某个词的条件下文本类别的概率分布之间的距离，该值越大，词对文 本类别分布的影响也越大。 6 ) 优势率 且, p o d d sr a t i o ，用于二类分类问题： o r ( 垆崦器渊 公式( 3 - 1 2 ) 注意优势率并不像前面提到过的几类评估函数将各个类别同等对待，而是只 关心目标类别。这使得优势率特别适合二值分类问题。在二元分类中希望识别出 尽可能多的正类，而不关心识别出来的负类。 3 2 4 向量空间的降维方法 从上一节可知，在用相量空间模型来表示文档的过程中，由于向量空间的维 数由文档集中所出现的不同单词的数目来决定，因此，向量空间将很大。例如， 即便是一个很小的文本集，它也很可能包含有成千上万的特征项。处理高维的向 量空间不仅需要大量时间，而且容易产生干扰，降低邮件分类的正确性，因此需 要采取措施对高维的向量空间进行降维处理。 常用的降维处理方法有两种：一种是建立一个禁用词库，删除禁用词库中出 现的单词；第二种是z i p 骸则，删除出现频率过少的单词。 1 ) 建立禁用词库 在一般的文本中，有许多常用英语单词会在各类文章中出现，但与文章的特 定类型没有相关性。这些与特定主题没有相关性的常见单词通常为冠词、介词、 连词等，大约有三四百个，他们在文章中出现的频率很高，不仅对邮件的分类与 过滤没有什么作用，相反会产生一定的干扰，影响邮件分类与过滤的准确性：因 此在文本检索领域中，通常把这些常见的单词收集到禁用词库中，在建立向量空 间模型的过程中，若文档中出现了禁用词库中的词，就把他删除掉，而不作为向 量空间的特征项。 图3 2 为一个禁用词库样例。 a h l b e b e f o r e b u t b e t w e e n o y c a n c 0 m e d o f o r o f o n o v e r t h a t t h e 【n e s e t h i s t o u s v e 纠 图3 - 2 一个禁用词库样例旧 2 ) z i p 献则嘲 在某一文本集中，有些单词出现的次数很少，整个向量空间会有大量仅出现 n e m s v 瞳 h 妇 妇 。 曼 ，晦 健 胁 时 s 2 n 油 刚弧 。 耐 腑 a a a a a a a a a a 一次或两次的单词，从而大大增加了向量空间的维数。他们对文本分类及过滤不 但没什么作用，相反还会出现过适应问题，降低分类的精确度。因此可以删除掉 这些出现频率过少的单词来减小向量空间的维数。 3 3 垃圾邮件过滤中的文本分类方法 本文中，只简要介绍人们已经应用于垃圾邮件内容过滤领域的一些分类算 法。 多种分类方法和机器学习理论都可以应用于垃圾邮件过滤【刀，包括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 n c 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 方法、粗 糙集( r o u g hs e t ) 等等。 这些方法可以分成两类，一是基于规则的方法，这类方法的训练过程就是从 训练文本集合中学习分类规则，如决策树、b o o s t i n g 力 法、粗糙集等；另外一类 是基于统计的方法，训练过程是一个统计学习过程，得到相应的分类器，如贝叶 斯分类算法、k 近邻方法等。 3 3 1 贝叶斯分类算法 b a y e s 方法是通过计算文本d 属于每个类别e ( ，= 1 ，2 ，肛为类别 个数) 的概率p ( qd ) 并将它们排序取其最大值来得到口，所属的类别。根据b a y e s 公式，最后归结于求每个类别的概率尸( c f ) 和从类别g 生成文本d 的概率 p ( dlc j ) 。这两个概率都可以通过训练语料得到。n a i v eb a y e s 是b a y e s 方法中使 用最广泛的一种。在这种方法中，假设d 由互相独立的多个特征彩，( 户1 ，2 ， m 是d 中不同特征数) 生成，于是尸( dic f ) 由可以归结成求尸 ，lc f ) 。n a i v e b a y e s 方法被广泛用于文本分类中n 引，取得了不错的效果。 简单贝叶斯分类算法在垃圾邮件过滤上的应用将在本文第四章详细介绍。 3 3 2k n n 方法 k n n 方法是传统的模式识别算法，是一种基于实例的文本分类方法，在文 本分类方面得到了广泛的研究与应用。他是通过计算文本间的相似度，找出训练 集合中预测是文本最相似的k 篇文本，然后指定类别。k n n 方法实际上是矢量 相似度法的一种改进。 一般以两种方式计算相似度： 1 欧氏距离，两个标准化的文本向量a 、 为： 晰) 2 妒 2 余弦距离： s i m ( d 。，c f ) = w x j w o j = l b ，它们之间的欧氏距离 公式( 3 - 13 ) 公式( 3 - 1 4 ) k n n 分类器有两种基本的实现方式： 、 1 ：首先计算测试文本与训练文本集中每个文本的文本相似度，找出k 个最 相似的训练文本，然后统计这k 篇训练样本中属于某