（计算机软件与理论专业论文）基于累积反馈学习的简单贝叶斯邮件过滤方法.pdf

基于累积反馈学习的 简单贝叶斯邮件过滤方法 专业：计算机软件与理论 硕士生：张立成 指导老师：李磊教授 摘要 本文对基于内容的垃圾邮件过滤，特别是简单贝叶斯过滤方法做一些实际应 用方面的研究工作。 首先讨论了简单贝叶斯的垃圾邮件过滤，在p u l 语料上实现了简单贝叶斯 算法，并得出了较优的参数设定，同时给出了与前人的实验结果的比较。 然后讨论了基于简单贝叶斯的中文邮件过滤，将前人的简单贝叶斯算法引入 到中文邮件过滤中，自己收集整理建立中文邮件语料库，并在该语料库上进行中 文邮件过滤的实验，探索简单贝叶斯方法在中文邮件过滤中的效果，并得出了与 英文邮件有一定差别的较优的参数设定。 在上述基础上，我们讨论基于简单贝叶斯的累积反馈学习的方法、模型，并 给出了简单贝叶斯的累积反馈学习算法及实现。在自己收集的中文语料库上进行 累积反馈学习方法实验，结果表明累积反馈学习对不断保持和提高分类器的分类 效果是必要的。 最后，通过对邮件领域的分析，得到一些经验规则。通过规则的引入，对基 于累积反馈学习的简单贝叶斯过滤方法进行改进，以提高垃圾邮件过滤效果。我 们完成了相应的实验系统设计和实现，结果表明经验规则的引入对提高垃圾邮件 的过滤效果是有帮助的。 关键词：垃圾邮件过滤简单贝叶斯累积反馈学习 i i y 1 0 1 4 5 5 8 n a i v eb a y e s i a ns p a m f i l t e r i n gm e t h o d b a s e do na c c u m u l a t i v ef e e d b a c k l e a r n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：l i c h e n gz h a n g s u p e r v i s o r ：l il e i a b s t r a c t i n t h i s p a p e r ，w ed os o m ep r a c t i c a lw o r k so nc o n t e n t b a s e ds p a mf i l t e r i n g ， e s p e c i a l l yo nn a l v eb a y e s i a nm e t h o d ， f i r s t ，w ed i s c u s st h en a i v eb a y e s i a na n t i s p a mf i l t e r i n ga n dr e a l i z et h en a m e b a y e s i a na l g o r i t h m c o n d u c t i n gat h o r o u g he v a l u a t i o no ft h i sa l g o r i t h mo np u i b e n c h m a r k s ，w eo b t a i nas e to fp r e f e r a b l ep a r a m e t e r s ，a n dt h ee x p e r i m e n tr e s u l t sa r e b e t t e rt h a nt h o s ei np r e v i o u s l yi s s u e s s e c o n d ，w ed i s c u s st h ep r o b l e ma b o u tc h i n e s ea n t i s p a mf i l t e r i n gb yn a m e b a y e s i a nm e t h o d w ee x t e n dt h ep r e d e c e s s o r l sn a i v eb a y e s i a nm e t h o di n t oc h i n e s e a n t i - s p a mf i l t e r i n g 。w ec o l l e c t e dm a n yc h i n e s em a i l sa n dc r e a t eac h i n e s em a i l c o r p u s m a k i n ge x p e r i m e n to nt h ec h i n e s em a i lc o r p u s ，w eg e tap r e f e r a b l ep a r a m e t e r c o n f i g u r a t i o nd i f f e r i n gf r o me n g l i s hm a i l t h i r d ，w ep r o p o s ea na c c u m u l a t i v ef e e d b a c km o d e la n dr e a l i z et h ea l g o r i t h m w h i c hi sb a s e do ni t i na d d i t i o n a l ，w em a k e e x p e r i m e n to nt h es e l f - c o l l e c t e dc h i n e s e c o r p u s w eg e tt h ec o n c l u s i o nt h a tt h ea c c u m u l a t i v ef e e d b a c km e t h o di sn e c e s s a r yo n m a i n t a i n i n ga n de n h a n c i n gt h ec l a s s i f i e r se f f e c t a tl a s t ，t h r o u g ht h em a i ld o m a i na n a l y s i s ，w eo b t a i ns o m ee m p i r i c a lr u l e sa n d a p p l yt h e mi n t oo u ra c c u m u l a t i v ef e e d b a c kn a l v eb a y e s i a na l g o r i t h mt oi m p r o v et h e i i c l a s s i f i e r sp e r f o r m a n c e w em a k ee x p e r i m e n tb yt h ei m p r o v e dc l a s s i f i e ro no u r c h i n e s em a i lc o r p u st h er e s u l ti n d i c a t e dt h a t e m p i r i c a lr u l e sa r eh e l p f u lf o rt h e c l a s s i f i e r k e y w o r d s ：s p a mf i l t e r i n g n a i v eb a y e s i a na c c u m u l a t i v ef e e d b a c kl e a r n i n g v 第一章引言 1 1 背景 随着国际互联网的发展与普及，互联网上的应用就被越来越多的用户所使 用。电子邮件( e m 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 ) 、s p a m 或j u n km a i l ，本文称之为“垃 圾邮件”。 据中国互联网络信息中心( c n n i c ) 于2 0 0 5 年7 月发布的第十六次中国 互联网发展状况统计报告显示，我国网民平均每周收到1 4 5 封电子邮件，其 中垃圾邮件9 3 封，占收到邮件的6 4 ，垃圾邮件数量已经超过了正常邮件数量， 并有进一步增长的趋势。垃圾邮件的增多已经越来越影响到用户正常的互联网使 用。据有关调查显示，垃圾邮件已成为互联网用户的最大烦恼之一，垃圾邮件的 病毒率高达4 7 。同时，大量的垃圾邮件还占用互联网带宽、占用邮件系统资源， 影响正常的邮件收发。因垃圾邮件所造成的损失，由以下数据就可以反映：美国 企业每年由于垃圾邮件损失8 9 亿美元，欧洲企业的损失为2 5 亿美元，美国和欧 洲的i s p 的损失为5 亿美元。2 0 0 3 年我国处理垃圾邮件而浪费的g d p 高达4 8 亿元人民币。此外，些垃圾邮件还传播色情、反动的信息，给社会带来危害。 黑客们利用电子邮件系统发送数以万计的垃圾邮件以攻击目标，使之瘫痪或拒绝 服务。垃圾邮件还可以被病毒利用，成为它们的传播途径，这些都对网络的安全 和正常运行带来了巨大威胁。 面临垃圾邮件问题日益严重的现状，人们开始从多方面寻找解决方案，目前 解决、缓解垃圾邮件问题主要从技术和非技术两方面着手。 从非技术方面来看，主要通过社会手段或个人行为加以解决。其一是通过制 定相必法律法舰来对垃圾邮件发送者给予相应的处罚制裁。虽然已有相关提议， 但要真l f 实施还有定难度。首先是垃圾邮件的界定较难，目莳对垃圾邮件没有 一个准确、清晰的界定标准。其次是实施较难，对许多境外垃圾邮件，如果缺少 国际合作，很难对发送者给予制裁，况且要追查到垃圾邮件发送者，也不是件 容易的事。其二是通过对发送方收取一定费用来制约垃圾邮件发送者发送大量垃 圾邮件，对发送邮件收取费用，对广大用户来说接受起来还有一定难度，而且刘 于如何解决计费、费用如何支付等问题也不是容易的。其三是尽量保守自己的邮 件地址，不要在网页上出现，不要回复不明来路的邮件，不要在b b s 上泄露等， 虽然这些可以避免收到一些垃圾邮件，但并不能从根本上有效的解决垃圾邮件问 题。 对垃圾邮件过滤从技术方面的解决方案。早期主要是通过黑名单、白名单、 定制简单的过滤规则等方法来实现，这些方法对用户来说一方面较为烦琐，另一 方面来说效果也不太理想。近年来出现了一些垃圾邮件过滤的技术方法f ”，简要 列举如下： l 、简单d n s 解析：通过对发送者邮件地址中的域名进行解析，来验证域名 的真实性及s m t p 服务器的真实性【2 j 。 2 、s p a r ep o i s o n i n g ：针对垃圾邮件发送者通过对网页扫描来获取邮件地址的 一种方法。故意在网页上发布一些错误的邮件地址，让垃圾邮件发送都获取到， 用以消耗垃圾邮件发送者系统资源。 3 、协同过滤( c o l l a b o r a t i v ef i l t e r i n g ) ：根据垃圾邮件的发送特点来加以过滤， 如短时间内发送大批量的内容相同或相似的邮件口】f 4 】。 4 、i n t e r n e tm a i l2 0 0 0 5 】：它是一个新的协议提案，现在的邮件系统构架是实 行“推”的机制，即邮件是由发送方强行传给接收方，而i n t e m e tm a i l2 0 0 0 是采 用“拉”的机制，即邮件并不被发送，而是存储在发送方的邮件服务器上，收件 人会得到条提示信息，直接到发送方的邮件服务器上下载。 5 、问题回答投递机制：发送邮件时，要求邮件发送人回答一个随机产生的 对真人来说的简单问题( 如3 + 2 = ? ) 。或者是服务器端提出一个难题，只发送几 封邮件的计算机可以解决这个难题，对于发送大量邮件来说，解决该难题的系统 耗费将会很大。 6 、内容过滤：通过事先对一定邮件样本内容进行“学习”后，根据学爿结 果对以后收到的邮件进行正常邮件和垃圾邮件的分类。 目前这些方法齐有优缺点，没有哪种方法能的彻底解决垃圾邮件闷题，只 有将多种方法结合起，才能收到令人满意的效果。 1 2 本文的内容安排 本文对基于内容的垃圾邮件过滤，特别是简单贝叶斯过滤方法做一些探索， 全文内容组织如下。 第二章主要介绍基于内容的垃圾邮件过滤技术，综述了前人在基于内容的 。垃圾邮件过滤技术方面的研究工作。同时，介绍了一些常用的语料库。 第三章着重的讨论简单贝叶斯的垃圾邮件过滤。我们在p u i 语料上实现了 简单贝叶斯算法，得出了较优的参数设定，并且给出了与前人的实验结果的比较。 第四章讨论基于简单贝叶斯的中文邮件过滤。我们将前人的简单贝叶斯算 法引入到中文邮件过滤中，自己收集整理建立中文邮件语料库，并在该语料库上 进行中文邮件过滤的实验，探索简单贝叶斯方法在中文邮件过滤中的效果，以得 出与英文邮件有一定差别的较优的参数设定。 第五章讨论基于简单贝叶斯的累积反馈学习的方法、模型，并进行算法设 计及实现。并进一步在自己收集的中文语料库上进行反馈学习方法实验，结果表 明在简单贝叶斯方法上进行累积反馈学习，对不断的保持和提高分类器的分类效 果是非常必要的。 第六章讨论提高垃圾邮件过滤效果的一些经验规则的引入，以提高垃圾邮 件过滤效果。设计了实验系统，结果表明经验规则的引入对提高垃圾邮件的过滤 效果是有帮助的。 第二章基于内容的垃圾邮件过滤技术 2 1 基于内容的垃圾邮件过滤与文本分类 文本分类的任务是根据预先定义好的类别体系，将待分类的文本分到相应 的类别中去。基于内容的垃圾邮件过滤，可看作简单的文本分类：根据邮件内容 将邮件分为垃圾邮件和j 下常邮件两类，是一个二值分类问题。因此，我们可利用 文本分类所取得的技术成果，来应用到垃圾邮件过滤中去，这也是目前垃圾邮件 过滤技术研究的个趋势，但垃圾邮件过滤与一般的文本分类在某些方面又有所 区别，主要表现在： 1 、对于文本分类，每个类别的内容一般不会经常改变，而对垃圾邮件过滤 而言，“垃圾邮件”类别是和用户密切相关的，用户对垃圾邮件的判别准则会随 时间的推移而有所变化，而垃圾邮件本身的内容形式也不断的变化。 2 、在分类效果上，人们不希望将一封正常邮件分作垃圾邮件，这类错误对 用户来讲是难以接受的，因此对垃圾邮件类别的分类准确性要求较高 3 、对垃圾邮件过滤而言，邮件分类的实时性要求是比较高的，因此要尽可 能采用简便、速度快的分类算法。 2 2 问题描述 基于内容的垃圾邮件过滤，我们的目标就是通过一定的机器学习方法，得 到一个邮件过滤器( 分类器) ，也就是邮件判定函数：厂，我们能通过函数来 判断一封邮件是正常邮件) 还是垃圾邮件( ，如果我们定义所有的邮件集为 i ，那么我们的目标就是寻找函数：厂：i 斗 s ，l 。 寻找函数厂的方法是通过一定的机器学 - j 方法来对预先分好类的样本集来 进行学习而获得，这是一个通用的机器学习问题。 2 3 邮件表示 我们要进行分类处理的对象是文本信息、字符串等。然而字符串处理起来 不足很方便。在文本处理领域，通常采用向量空i n j 模型( v s m ：v e c t o rs p a c em o d e l ) 来表示文本。一篇文本可表示为一个”维向量( w ，w 2 ，w o ) ，其中w ( f = 1 ，2 ，n ) 表示第i 个特征项的权重， 是特征项的个数，特征项可以是字、词、短语等。 权重有多种计算方法，最简单的是布尔权重，即“1 ”表示该特征项在文本中出 现，“0 ”表示该特征项在文本中没出现。更一般的情况下，v s m 中的权重计算 采用词频t f ( t e r mf r e q u e n c y ，表示该特征词在文本中出现的次数) 和文档频次 d f ( d o c u m e n tf r e q u e n c y ，表示出现该特征词的文本数量) 的某种组合。 对垃圾邮件过滤来说，设我们所有的邮件集为m ，提供学习的邮件样本数为 d 预先分好类的邮件样本集为 ( 啊，c ，) ，( m 2 ，c ：) ，( m e ，勺) ，m m ，c | s ，l ) ，所 选择特征数为r l ，每封样本邮件表示为：m ，= ( w f ，w r ：，w j 。) ，f = 1 ，2 ，d ， f ( m ，) = c ，一封待分类的邮件可表示为m ，= ( w x 。，u 。，w x 。) ，我们的最终任务是 将分到相应的类别中去。即f ( m ，) = c x , c ，e s ，l ) 。 2 4 特征选取 如果将训练集中出现的所有词汇都作为特征词来选取，那向量的维数将会 很大，这将给计算带来非常大的压力，耗费大量空间，大大降低分类器的效率。 虽然有证据表明，当所选取的特征词都是统计独立的时，特征数的增加对分类效 果会有所提高【6 】，但是由于我们所采用的训练集的数据是有限的，选取过多的特 征词后，将会使词频分布太过分散，反而会降低区分度，从而降低分类效果。 因此为了降低向量维数，提高计算效率，应选取那些包含信息多的、区分 度高的、具有代表性的词作为特征词，去掉那些对分类用处不大的、不具代表性 的词。具体处理方法是采用某种特征选择方法【7 】f 8 】，计算所有词的区分度”，将 所有词按“区分度”由大到小排序，选取排在前面的一定数量的词作特征词。常 用的特征选择方法有：文档频次、信息增益、互信息、z 2 统计量、词强度等。 2 4 1 文档频次 文档频次即d o c u m e n tf r e q u e n c y ，简称d f ，指在训练样本中包含特定特征 闻的文档数量。通常认为d f 太小的词没有代表性，而d f 太大的词又没有区分 度所以基于d f 的特征词选择一般只选择那些d f 介于中间的特征词。d f 方法 是最简单的方法，但它没有一个明确的特征词选择原则，只用在一些特殊的场合。 2 4 2 信息增益 信息增益即i n f o r m a t i o ng a i n ，简称i g 。定义如下： g ( f ) = 一兰j p ( e ) l o g 尸( q ) + 尸( ，) 芝| p ( ef f ) l 。g p ( ef ，) + j ) ) 芝p ( ti - ) l 。g 尸( ef ；) g ( ，) 反映了词f 为整个分类所提供的信息量。式中j d ( i ) 表示词f 不出现的概 率，p ( i ，) 表示词，不出现的情况下文本属于e 类的概率。 2 4 3 互信息 互信息即m u t u a li n f o r m a t i o n ，简称m i 。定义如下： 心一扎s 意 尸( ，) 表示词，在训练样本集中出现的概率，j d ( fc ) 表示c 类文本中f 出现的 概率。，( f ，c ) 越大，词，和类别t 2 的共现程度越大，当，( f ，c ) = 0 时，表示词r 与。 类无关。为了更全面方便的表示词t 的互信息，可针对所有类来计算一个平均互 信息。定义如下： k ( f ) = p ( c f ) ，( f ，e ) 2 4 4 ，统计量 z 2 统计量定义如下： z 2 ( ，c ) = 百面丽n 鬲x ( 永a d 百- c 两b ) z 而 z 三。( ，) = ，) ( ) z ! ( ，) 爿，口，c ，d 均表示文本数量，其具体意义如表2 1 所示 表2 1 j c 类文本集合非e 类文本集合 词t 出现 爿口 词f 不出现cd 例如，a 表示t 类文本中出现词t 的文本数量。 为所有的文本总数，刊+ b + c + d ，z 2 ( ，c ) 表示词，和类c 的独立性的 缺乏程度，z2 ( ，c ) 的值越大，和c 的独立性就越小，它们之间的相关性就越大。 z 。2 。表示对所有类别求平均的z 2 统计量。 2 , 4 5 词强度 词强度即t e r ms t r e n g t h ，简称t s 。该方法通过判断词f 在相似文档间同时 出现的频度来计算词f 的重要性。定义如下： s ( t ) = e ( t y l t x ) 0 ，y ) 为文档对，x 和y 是通过定相似度计算而得到的相似文档。 该方法是基于文档簇的，认为出现共同词汇越多的文档间的关系越密切， 而越多文档的交集的共同词汇信息度就越高，越重要。 2 5 基于内容的垃圾邮件过滤方法 基于内容的垃圾邮件过滤方法受益于机器学习方法在文档分类中的应用p 1 。 许多文档分类方法都可用于基于内容的垃圾邮件过滤中f 1 。1 。现主要的基于内容 的垃圾邮件过虑方法有：贝叶斯方法( b a y e s i a nc l a s s i f y ) 、k 近邻( k - n e a r e s t n e i g h b o r ) 、支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 、神经网络( a r t i f i c i a l n e u r a ln e t w o r k s ) 、b o o s t i n g 方法、决策树、粗糙集( r o u g hs e t ) 等。这些机器 学习方法可分为两类，一是基于规则的方法，这类方法的训练过程就是从训练样 本集合中学习分类剃则，如b o o s t i n g 方法、决策树、租糙集等；另外一类是基 于统计的方法，这类方法的训练过程是一个统计学习过程，最后得到相应的分类 器，如9 1 叶斯方法、k 近邻、支持向量机( s v m ) 、神经网络等。 这些方法部有各自的优缺点，目前还没有哪种方法能做到相当的完美， 因此也有部分文献提出了将多种基于内容过滤的技术方法相结合的思想，并进行 了算法设计及实现，最终的实验结果还比较良好】。 2 5 1b o o s t i n g 方法 在b o o s t i n g 方法中，定义准确率很高的分类规则为“强规则( 或强假 设) ”，准确率不高，仅比随机猜测略好的分类规则为“弱规则( 或弱假设) ”，最 简单的弱规则自 ) 可以这样定义： ，、i + i 如果x 满足某个断言p 州。l - - 1 坏满足卢 一般来说，弱规则比较容易得到，而强规则较难得到。b o o s t i n g 方法的基 本思想就是通过对样本进行训练，从而将原有多条弱规则提升为一条强规则。 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 i 等，下面 以a d a b o o s t 为例来介绍。 a d a b o o s t 的算法如下： 给定训练集：s = ( 五，m ) ，( ，y m ) ，一x ，只y = 一1 ，+ 1 初始化：皿( f ) = 1 m f o rt = 1 ，t 商4 - - b a s e l e a r n e r ( s ，d ，) 计算口；昙l n ( 堕) u p d a t e ： 州垆继麴华丛蚴 厶， 亿是标准化变量，保证d ，+ ，是一个权重分配) 输出最终分类归则： 厂7、 月( x ) = s i g n l q 囊( x ) i a d a b o o s t 算法首先输入训练集( ，y ，) ，( ，y ，) ，其中x 属于样本空间x y 属于符号空间y ，只- 1 表示样本一属于该类别，y = 一l 表示样本不属于该类 别。丌始时，每个样本权重都初始化为1 m 。a d a b o o s t 事先假定一个基本( 弱) 学习器b a s e l e a r n e r 用以获取弱规则，接着进行t 次的循环调用b a s e l e a n e r 。该 算法的主要思想是对样本进行权重分配，口( i ) 表示第f 次循环是计算样本i 的权 重。刚开始时，所有样本的权重都是一样的，但在每一次循环中，分类错误的样 本权重将增加，这样b a s e l e a r n e r 将会更关注那些难的、分类错误的样本。 b a s e l e a n e r 的任务是的使分类错误最小化，为错误率 s ，= 口( f ) ，h a 为弱规则权重系数，对二值分类 弘1 ：i n ( 字) 经过7 1 次循环，得到分类规则日，h 是各个弱规则的线性组合的符号函数。 2 5 2 决策树 决策树( d e c i s i o nt r e e ) 方法是从训练的样本集中通过学习得到以决策树 的形式表示的分类规则。在进行分类时，将待分类的文本按照其属性值自树根向 下逐步比较判断，直到叶子结点时，就可以确定文本所属类别。 一棵简单的决策树如图2 1 所示。树的内部结点表示属性或属性的集合，分 支上的数值表示属性的取值，叶子结点表示最终的分类结果。图中l 表示正常 邮件，s 表示垃圾邮件。例如，当邮件的属性a 取值为a 3 ，属性b 的取值为b l ， 属性c 的取值为c 2 时，则邮件是垃圾邮件。决策树实际上就是一系列规则的形 式化表示，如上例可表述为：“如果邮件m 的属性a = a 1 ，b = b 2 ，c = c 3 时，则 m l ”。 决策树的学习算法有i d 3 、c 4 5 、c 5 0 等，本文不再作详细介绍。 图2 i 一棵简单的决策树 2 5 3m e m o r yb a s e 方法 m e m o r yb a s e 是基于实例的方法【1 6 j f l 刀，其中以k 近邻( k n n ，k - n e a r e s t n e i g h b o r ) 方法最具代表性。我们以k n n 方法为例来说明。k n n 方法是m e m o r y b a s e 方法的一种，其主要思想是定义文档间的距离，认为越相似的文档其距就 越近。因此当对文档进行分类时，就判断待分类文档与哪类样本文档最近，从而 将待分类文档也分为该类。计算文档间的距离有多种方法，最常用的是计算两个 文档向量之间的夹角余弦值。k n n 算法的基本思想如下： 训练过程： 存储样本邮件 分类过程： 设待分类邮件为m ，在训练样本中找出与m 最近的k 个样本邮件，在这k 个样本邮件中，如果垃圾邮件s 数目比正常邮件的数目多，则将m 归为s 类， 否则将m 归为类。 我们可以看到，在训练过程中，k n n 方法不用进行复杂训练，其主要时耗 都花在分类过程。如果不作处理，其分类时间复杂度为o ( m n ) ，n 为训练样本数 目，1 2 1 为文档向量的元素数量。经过一些灵活处理，其时间复杂度可降为o ( n ) 。 k n n 方法被广泛的用于文档分类，同时它也是少数的几个通用稳定分类 ( u n i v e r s a l l v n s i s t e n tc t a s s i f i c a t i o nr u l e ) 方法之一1 1 8 1 。 2 5 4 人工神经网络方法 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n s ) 也是一种常用的文档 分类方法。人工神经网络有许多种，在此我们仅讨论最简单的“感知器” ( p e r c e p t r o n ) 神经网络。其算法主要思想是找到一个线性函数厂( x ) = w 7 x + b ，使 得对于一类向量集厂( x ) o 。w = ( w o w ：，) 为函 数的向量权重，b 为偏移值( b i a s ) 。如果我们将两个类别用数字+ l 和一l 来表示， 那可将该函数定义为符号函数：，( x ) = s i g n ( w 7 工+ 6 ) ，该函数可用一个简单的神经 元表示，如图2 2 。 x 】 x 2 - x m 图2 2 一个最简单的神经元 p e r c e p t r o n 基本算法： 训练过程： 1 、初始化w 和6 ( 赋随机值或0 ) 2 、找一个训练样本( x ，c ) ，使得s i g n ( w 7 x + 6 ) c ；如果不存在这样的样本， 则训练过程结束，并存储最终的w 和6 ，否则进行下一步。 3 、更新w 和b ：w = w - p c x ，b = 6 + c ，返回至第2 步。 分类过程： 给定一个待分类文本x ，通过判断s i g n ( w 7 x + 6 ) 值而决定z 所属类别。 该算法是一个迭代求解过程，剐开始时，选择任意的初始参数( w o ，) ，然 后每一步对其进行迭代更新。当在第n 次迭代时存在样本( x ，c ) ，使得 s i g n ( 以x + 以) c ，则参数( ，b o ) 更新为w n + 。= + “，“= b 。+ c 。当训练样本 线性不可分时，算法将不收敛，这时如果不能被正确分类的样本己很少时，我们 可以停止算法，求近似解。 2 5 5 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是在二十世纪9 0 年代以 束发展起来的一种统计学习方法，其主要思想跟p e r c e p t r o n 方法类似，即找到一 个线性函数，( x ) = w 。x + 6 将训练样本正确的分开。与p e r c e p l r o n 方法不同的是， p e r c c p t r o n 方法是的找到任意一条满足要求的直线就行，而s v m 方法是找一条 唯一的、特殊的“最优分类线”。 如图2 3 所示，图中的点分别表示两类的训练样本，考虑线性可分的情况。 直线l 可以将两个类别正确地分开，l l 和l 2 分别为经过各类样本中离分类线最 近的点且平行于分类线l 的直线，皿1 j 、l l 2 1 分别为直线l l 和l 2 与直线l 的距 离。r a i n ( i l l i ，i l 2 1 ) n 做直线l 的分类空隙( m a r g i n ) 。最优分类线定义为：该分类线 不但能将两类样本分开，并且它的分类空隙最大。直线i l l 、h 2 上的训练样本叫 做支持向量，( 如图中带圈的点) 因为它们支撑了最优分类线，图中l 为最优分 类线。 图2 3 最优分类线图中带圈的点为支持向量 推广到高维空间，最优分类线就成为最优分类面。对于线性不可分的情况 可以构造一个变换，将问题转换到一个新的空间，在这个空间中线性可分。 2 5 6 简单贝叶斯分类 简单贝叶斯分类即n a i v eb a y e s i a n 方法，是种广泛应用的分类算法。在文 本分类中，通过计算文本属于每个类别的概率p ( c i x ) ，从而将该文本归为概率 最大的一类。计算p ( cj ) 时利用贝叶斯公式，并假定所有的特征之间相互独立。 事实上，在生活中这种独立性很难存在，但从目前的分类效果看，该方法的结果 还较理想。在后续章节中将详细讲述该方法 2 6 垃圾邮件内容过滤中的常用语料库 为了比较各种垃圾邮件内容过滤的算法性能，评测算法的实用性，需要一 个公共的语料库( c o r p u s ) 。语料库相当于提供了一个“基准”( b e n c h m a r k ) ，人 们都在这上面做实验，结果才有可比性。为了保证评测的客观性、真实性和代表 性，语料库中的电子邮件都应该是来自现实生活中的真实邮件。但由于电子邮件 本身的特殊性，合法邮件涉及到用户的个人隐私，因此收集和建立这样的语料库 有一定的困难。通常可以通过两种途径来解决：( 1 ) 从公用的邮件列表或新闻组 上获得邮件，这上面的大部分邮件都不涉及到用户的隐私，不足之处是这上面收 集到的邮件有一定的偏向性，与实际的邮件有一定差别。( 2 ) 将邮件用一定的手 段进行“加密”，既隐藏了邮件的真实内容，又不影响实验。 i o na n d r o u t s o p o u l o s 、l u s t i nm a s o n 、h o p k i n s 等人在邮件语料库的建设上做 了很多卓有成效的工作【1 9 。下面简要介绍几种常见的垃圾邮件语料库。 2 6 1p u l 语料 p u l 语料由i o na n d r o u t s o p o u l o s 收集，来源于提供者一段时间内收至的真 实邮件。一共有1 0 9 9 封邮件，其中垃圾邮件有4 8 1 封。邮件去掉了附件、h t m l 格式的t a g 等，保留了邮件纯文本内容和邮件主题，为了保护提供者的隐私，邮 件中的词汇都转换成相应的数字编码。i o n a n d f o u t s o p o u l o s 将所有的邮件分成1 0 份，每份约1 1 0 封，并且每分保持相同的垃圾邮件和正常邮件比例。可以每次取 其中的9 份作为训练集，另外l 份作测试集，如此循环1 0 次，最后将1 0 次的结 果求平均值，( 当使用小样本数据作实验时，用该方法可增加实验数据的可信度) ， 这种实验方法被称为k 次交叉验证( k f o l dg r o s sv a l i d a t i o n ) 。 根据对邮件文本的处理层次，p u l 提供了4 种形式的语料。预处理包括去 停用词( s t o pl i s t ) 和词汇还原( l e m m a t i s e r ) 。去停用词是去除英语中1 0 0 的最 高词频的单词，例如“a ”、“t h e ”等。l e m m a t i s e r 将单词转换为其基本形式，它 不同于一般的词干还原( s t e m m e r ) ，它处理的结果是返回完整的词汇，而不是词 干，例如将a m 、i s 、w a s 、a r e 、b e e n 等词转换为b e 。有关l e m m a t i s e r 的介绍请 参考h t j p ：w w w , c o n c o r d a n c e s o f t w a r e c o u k m a n u a l h s 2 3 3 0 , h t m 。 这4 种形式的p u i 语料是： ( 】) b a r e 语料：没有用l e m m a t i s e r ，电没有去停用词。 f 2 ) l e m m 语料：使用了l e m m a t i s e r ，没有去停用词。 ( 3 ) s t o p 语料：没有用l e m m a t i s e r ，去掉了停用词。 ( 4 ) l e m m _ s t o p 语料：使用了l e m m a t i s e r ，并去掉了停用词。 一篇p u i 语料实例： s u b j e c t ：2 1 2 91 7 3 4 54 3 3 91 3 6 0 61 4 3 3 8 6 9 6 37 0 91 3 5 2 15 8 3 91 0 1 3 04 74 74 74 74 71 5 5 2 71 1 2 8 08 6 6 19 59 38 69 51 8 7 3 2 1 8 3 2 21 9 6 76 0 3 71 5 8 5 61 5 7 0 01 3 7 3 92 1 3 03 6 9 61 1 2 5 08 41 4 7 6 68 3 96 12 1 2 98 4 1 4 8 8 02 3 1 7 88 41 1 2 7 95 9 31 3 4 0 67 2 5 31 1 6 6 22 2 1 9 34 7 8 46 3 0 61 1 88 68 66 5 0 98 4 6 3 7 88 4 6 4 7 68 48 3 i8 61 4 3 3 08 61 3 4 0 38 46 2 0 4 p u 系列语料还包括p u 2 、p u 3 、p u a ，见下表 表2 2 p u 系列语料 语料名称非垃圾邮件数垃圾邮件数邮件总数 p u l6 18 4 8 1 1 0 9 9 p u 25 7 91 4 27 2 1 p u 32 3 1 31 8 2 64 1 3 9 p u a5 7 15 7 11 1 4 2 p u 系列语料可以从l l t t p ：w w w a u e b g r u s e r s i o n d a t a 下载 a n d r o u t s o p o u l o s 等在p u l 语料上作了贝叶斯算法、支持向量机、b o o s t i n g 方法等实验。c a r r e r a s 等人在p u l 语料上作了b o o s t i n gt r e e 算法。 2 6 2l i n g - s p a m 语料 l i n g s p a m 也是由a n d r o u t s o p o u l o s 等人提供的英文语料，共2 8 9 3 封邮件， 其中包括来自语言学家列表( l i n g u i s tl i s t ) 的2 4 1 2 封非垃圾邮件和提供者自已 收集的4 8 1 封垃圾邮件。类似p u l ，l i n g s p a m 也去掉了附件、h t m l 格式的t a g ， 为方便进行1 0 次交叉验证，也将语料分成l o 份，并且也包含4 种形式：b a r e 、 e m m 、s t o p 和l e m m s t o p 。l i n g - s p a r e 语料未作加密处理，全以明文提供。 一篇l i n g s p a r e 浯料实例： s u b j e c t ：d e s e r e tl a n g u a g ea n dl i n g u i s t i cs o c i e t y c a l lf o rp a p e r s ：19 9 9d e s e r e tl a n g u a g ea n dl i n g u i s t i c ss o c i e t ys y m p o s i u mt h e2 5 t h a n n u a ld e s e r e tl a n g u a g ea n dl i n g u i s t i c ss y m p o s i u m ( d l l s ) i n v i t e sp a p e r si n a l la r e a s o fl i n g u i s t i c sa n dl a n g u a g ef o ro u r19 9 9s y m p o s i u mt ob eh e l do nf e b r u a r y18 t ha n d 19 t h ，19 9 9 t h i sy e a r sp l e n a r ys p e a k e ri sj o h nr s e a r l e ，p r o f e s s o re m e r i t u so f p h i l o s o p h ya tt h eu n i v e r s i t yo fc a l i f o r n i aa tb e r k e l e y t oa p p l y ，p l e a s es u b m i ta d l l s p r o p o s a lf o r mi n c l u d i n ga na b s t r a c tf o rr e v i e wo fn om o r et h a n2 5 0 w o r d sb ye m a i lo r r e g u l a rm a i lb yf r i d a y ，d e c e m b e r11 ，19 9 8t oe i t h e ra l a n m a n n i n g b y u e d uo r a l a nm a n n i n gl i n g u i s t i c sd e p a r t m e n t212 9j k h bb r i g h a n ay o u n gu n i v e r s i t yp r o v o ，u t 8 4 6 0 2m o r ei n f o r m a t i o na b o u tt h es o c i e t ya n dt h es y m p o s i p m ( i n c l u d i n gt h ep r o p o s a l s u b m i s s i o nf o r m ) c a nb er e a d i l ya c c e s s e da t ：h t t p ：e n g l i s h b y u e d u s o c i e t i e s d l l s l i n g ，s p a m 语料的不足之处是它的合法邮件都来自于一个特定的邮件列表， 因此邮件内容都偏向于一个主题，而实际生活中用户一般收到的正常邮件内容主 题都很发散。 在l i n g s p a m 语料上做实验的研究者也比较多，如a n d r o u t s o p o u l o s 使用 b a y e s 和k n n ，g o m e zh i d a l g o 使用c 4 5 、n f f f v eb a y e s 、r o c c h i o 和s v m ，s c h n e i d e r 使用n a i v eb a y e s ，d e s o u z a 等人使用b o o s t i n g 等。l i n g s p a m 语料可以从 h t t p ：w w w a u e b , i 塑u s e r s i o n d a t a 下载 2 6 3s p a m a s s a s s i n 语料 s p a m a s s a s s i n 语料是由n e t w o r ka s s o c i a t e s 的j u s t i nm a s o n 提供的。与 l i n g s p a m 有些类似，其合法邮件来自公众论坛。包含18 9 7 封垃圾邮件和4 1 5 0 封非垃圾邮件。 s p a m a s s a s s i n 语料可以从h t t p ：w w w s p a