（计算机系统结构专业论文）bwlvq邮件过滤模型.pdf

摘要 伴随着i n t e r n e t 的普及，电子邮件以其快捷、方便、低成本的特点曰益得 到了广泛的使用，成为了最流行使用的沟通工具之一。然而，作为其发展的副产 品一一垃圾邮件，却给i n t e m c t 用户、网络管理员和网络服务提供商i s p 带来了 无尽的烦恼，收件人的时间、带宽和存储资源被无效占用，网络链路因此造成拥 塞，还被作为不良信息的载体被到处散发。现在成熟应用的垃圾邮件过滤方法是 采用通过软件自动过滤与人工管理相结合的方式，但这不能很好的适应垃圾邮件 的多样性，只能过滤掉5 0 左右的垃圾邮件。因此，迫切需要引入更加智能化的 垃圾邮件过滤技术来治理日益猖獗的垃圾邮件问题。 本论文课题的主要目标是探索种具体的垃圾邮件过滤模型，实现并测试该 模型。研究中要观察所选择的模型是否适当，注意此模型自身参数和环境参数调 节对过滤性能的影响，因此，实验需要能够彻底的检测出模型的有效性和可行性。 作者在课题研究期间很好的完成了上述目标。 本论文提出了l v q 邮件过滤模型和改进型b w 邮件过滤模型，详细的描述 了两个模型的设计原理，讨论了两者之间的关系以及它们与邮件服务器的关系， 并给出了重要的实现框架与代码。l v q 邮件过滤模型解决了布尔型邮件过滤模 型特征项离散、垃圾邮件与正常邮件边界定义模糊的问题：改进型b w 邮件过 滤模型针对传统黑白名单模型提出了改进，减少了用户对边界地址错误界定带来 的损失。 虽然当前已经存在多种多样的垃圾邮件过滤方法，但是还有许多垃圾邮件相 关问题没有找到好的解决办法，这大大的影响了邮件过滤系统的过滤性能，使得 垃圾邮件的危害没有减轻。本论文提出的新的邮件过滤模型解决了其中的一些问 题，在一定环境下能够提高邮件过滤系统的过滤性能，因此，本课题的研究是具 有意义的。 关键词：垃圾邮件、学习矢量量化、黑名单、白名单、过滤模型。 a b s t r a c t a st h ep o p u l a r i z a t i o no fi n t e m e t ，e m a i l sa r em o r ea n dm o r ef r e q u e n t l yu s e d b e n e f i t i n gf r o mi t sh i g he f f i c i e n c y , c o n v e n i e n c ea n dl o wc o s t a tt h es a m et i m e ， h o w e v e r , t h e i rb y p r o d u c t ，s p a r e s a r e b r i n g i n g e n d l e s st r o u b l et oi n t e r a c t u s e r s ， n e t w o r ka d m i n i s t r a t o r sa n di n t e r n e ts e r v i c ep r o v i d e r s ，w i t ht h es p r e a d i n go ft h e s e c a r r i e r sf o rb a do ru s e l e s si n f o r m a t i o n ，t h eu s e r s t i m ei sw a s t e d ，t h eb a n d w i d t ha n d s t o r a g es p a c ea r ec o n s u m e d ，a n de v e r lt h ei n t e r n e ti sc o n g e s t e d t h em a t u r es p a n a f i l t e r i n gm e t h o d su s e dn o w c o m b i n eb o t ht h ea u t o m a t i cf i l t e r i n go ft h es o f t w a r ea n d m a n u a lm a n a g e m e n t ，w h i c hh a sb e e np r o v e dn o ta d a p t i v et ov a r i e t yo f s p a r e s ，a n di t i se s t i m a t e do n l y5 0 o f s p a m s c a r lb ed e t e c t e d t h e r e f o r e ，m o r ei n t e l l i g e n tf i l t e r i n g t e c h n i q u e s a r c r e q u i r e d t h i sm a i ng o a lo ft h i s p a p e ri s t o e x p l o r eas p e c i f i cs p a mf i l t e r i n gm o d e l ， i m p l e m e n ta n dt e s ti t d u r i n go u rr e s e a r c h ，w en e e dt oe x s j r l i n ec a r e f u l l yw h e t h e rt h e m o d e li saf i to n e ，a n do b s e r v eh o wt h e p a r a m e t e r so ft h i s m o d e li t s e l fa n dt h e e n v i r o n m e n t a lp a r a m e t e r si n f l u e n c et h ef i l t e r i n gp e r f o r m a n c e s o ，t h et e s ts h o u l d r e v e a lt h ef e a s i b i l i t ya n de f f i c i e n c yo f t h i sm o d e l t h o r o u g h l y t h ea u t h o rh a sa c h i e v e d t h e g o a la b o v e t h i s p a p e rp u t f o r w a r d st w o f i l t e r i n gm o d e l ，l e a r n i n g v e c t o r q u a n t i z a t i o n ( l v q ) a n di m p r o v e d b l a c k & w h i t e l i s t ( b w ) ，d e s c r i b e d t h e d e s i g n p r i n c i p l e s ，d i s c u s s e dt h e i ri n t e r - r e l a t i o n s h i pa n d t h e i rr e l a t i o n s h i pw i t ht h em a i ls e r v e r a n d p r o v i d e di m p o r t a n ti m p l e m e n t a t i o nf r a m e w o r ka n dc o d e s l v qm o d e l s o l v e dt h e d i s c r e t i o no fe i g e n i t e mi nt h eb o o l e a n f i l t e r i n g m o d e la n dt h ed i f f i c u l t i e si n d i s t i n g u i s h i n g b e t w e e n s p a r e s a n dn o r m a l m a i l s i m p r o v e d b wm o d e lm a d e i m p r o v e m e n t so v e rt h et r a d i t i o n a lb l a c kl i s ta n dw h i t el i s tm o d e l ，a n dd e c r e a s e dt h e u s e r s l o s sd u et oi n c o r r e c tb o r d e r i n ga d d r e s s t h o u g hv a r i e t i e so ff i l t e r i n gm e t h o d se x i s tn o w , al a r g en u m b e ro fp r o b l e m s a b o u t s p a mf i l t e r i n g s t i l lr e m a i nt ob es o l v e d ，w h i c h i m p e d e s t h e f i l t e r i n g p e r f o r m a n c ef r o mi m p r o v i n g n e wf i l t e r i n gm o d e l sb r o u g h tf o r w a r di nt h i sp a p e r h a s p r o v i d e d s o m es o l u t i o n s i th a sb e e np r o v e dt h a t t h e yc a ni m p r o v et h ef i l t e r i n g p e r f o r m a n c ei ns o m ee n v i r o n m e n t t h e r e f o r e ，t h e r e s e a r c hi so f g r e a tv a l u e k e y w o r d s ：s p a m ，l e a r n i n gv e c t o rq u a n t i z a t i o n ，b l a c kl i s t ，w h i t el i s t ，f i l t e r i n g m o d e 】 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所傲的任何贡献 均已在论文中作了明确的说明并表示谢意。 签名： 圣墅 日期：文柙斗年文月- 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丝导师签名： 日期：4 啊斗年 月一f 日 b w - - l v q 邮件过滤模型 1 。1 背景 第一章引言 伴随着i n t e r n e t 的普及，电予邮件以其快捷、方便、低成本的特点日益得 到了广泛的使用，成为了最流行使用的沟通工具之一。然而，作为其发展的副产 品一一垃圾邮件，却给i n t e m e t 用户、网络管理员和网络服务提供商i s p 带来了 无尽的烦恼。垃圾邮件占用收件人的宝贵时间，用来删除驱之不散的垃圾邮件， 还需要小心的判别垃圾邮件和正常邮件，阻免影响正常事务。垃圾邮件还占用了 接收方的带宽和存储资源。许多用户是以接入i n t e m e t 网络的时间预先支付费用 的，大量的垃圾邮件使得这些用户不得不花去一定的时间来下载毫无意义的内 容。对大部分用户来讲，邮箱的大小都是限额的，多一份垃圾邮件，正常邮件就 少了一份存储空间。而且，垃圾邮件往往是网络资源的盗用，影响到了网络管理 员和i s p 的工作。当前i n t e r n e t 网络资源还比较有限，垃圾邮件每次发送上万、 百万，甚至上亿份，占用了大量的带宽资源，严重时会拥塞整个i n t e m e t 链路， 中断部分线路的运营。垃圾邮件还利用别人的服务器转发邮件，造成了网络安全 隐患。垃圾邮件还带来了社会问题，如一些含有暴力、欺诈等各种不良信息的邮 件，可能诱导收信人的判断能力，特别是容易误导辨别是非能力还较弱的未成年 入。另外，发送垃圾邮件的行为还违背了i n t e r n e t 开放、民主、平等的文化，不 顾他人的反对，强制性的把邮件发到别人的邮箱，侵犯了个人的隐私权，打破了 平等自愿交流的规则。联合国贸发会议原引m e s s a g el a b s 的数据说，垃圾邮件 给全球企业带来的损失高达2 0 5 亿美元【】l 。 垃圾邮件起源于美国，在二十世纪九十年代曾经一度泛滥。经过不懈努力， 包括技术上和法律上的，目前美国的垃圾邮件正在逐年减少，而垃圾邮件的源头 正逐渐转到了中国及东南亚的一些国家和地区。由于中国网络的迅速普及，国内 一些商业机构也看到了这种广告方式的商机，从2 0 0 1 年下半年开始从国内直接发 出的垃圾邮件迅速增加。部分国外公司甚至利用中国没有相关的法律限制，直接 在中国设立公司从事此类商业活动。这些行为带来的后果是使中国成了i n t e r n e t 世界的众矢之的，国外的部分反垃圾邮件组织和公司开始大量屏蔽中国的i p 站点 和来自中国部分域名的邮件。在严峻的形式下，中国加大了反垃圾邮件技术的研 究。国内的邮件服务提供商所采用的反垃圾邮件的主要手段是通过软件自动过滤 与人工管理相结合的方式，比如系统全局规则、i p 过滤规则、客户过滤规则等等， 但是这些方法相对简单，不能很好的适应垃圾邮件的多样性，只能过滤掉5 0 左 b w - - l v q 邮件过滤模型 右的垃圾邮件。因此，迫切需要引入更加智能化的垃圾邮件过滤技术来治理日益 猖獗的垃圾邮件问题。 基于邮件内容含义的过滤技术属于邮件智能过滤领域，这种技术能够较好的 适应于垃圾邮件变化性。邮件过滤系统将邮件正文当作普通的文本，对其进行文 本识别和分类，尽力将邮件过滤器解读邮件内容含义的过程自动化。c o h e n 2 j 采 用t f i d f 方式表示邮件权重，用r i p p e r 规则学习算法实现对邮件的自动分类。 s a h a m i 【3 等人利用统计概率学理论和信息检索技术，用向量空间模型表示邮件， 假设向量中的各个项是相互独立的，用贝叶斯公式来计算邮件是垃圾邮件的概 率，从而完成垃圾邮件的自动识别。实验【4 】证明，基于贝叶斯公式的方法在垃圾 邮件识别效果方面远远好于基于关键字过滤的方法。x a v i e rc a r r e r a s 5 】等人应 用b o o s t i n g 算法来实现反垃圾邮件的过滤。d u h o n gc h e n 6 】等人对贝叶斯算法、 决策树、神经网络和b o o s t i n g 四种算法对垃圾邮件过滤的效果进行了比较，发现 神经网络算法有更高的正确分类率。j a m e sc l a r k 7 】等人编写l i n g e r 软件，他们 构建了一个3 层的b p 神经网络，其中输入层的神经元个数为特征项数，隐藏层的 神经元数选取在2 0 至4 0 个范围内，发现b p 网络结合用信息增益来选取特征项的方 法，有相当好的垃圾邮件识别效果。还有更多的学者正在从事这方面的研究，大 家都在力图找到一种能完美识别出垃圾邮件的过滤技术，但是到目前为止，仍然 没有哪一种过滤方法能够绝对精确的区分出垃圾邮件与正常邮件。作者被这一领 域的知识和问题深深吸引，也在此方面做了一定的研究，希望能找到一种新的过 滤模型达到更好的过滤效果。 1 2 项目目标 本课题的主要目标是探索一种具体的垃圾邮件过滤模型，实现并测试该模 型。研究中要观察所选择的模型是否适当，注意此模型自身参数和环境参数调节 对过滤性能的影响。并且，本论文主要是实验性的测试模型，而不是真正制造出 一个产品，因此，实验需要能够彻底的检测出模型的有效性和可行性，但用户交 互性等其他问题可以暂时不予考虑。 1 3 论文概要 论文首先介绍了邮件过滤的相关背景以及纂础知识，描述了现存的垃圾邮件 过滤方法。接着，详尽分析了新提出的学习向量量化( l v q ) 邮件过滤模型，并 具体设计了一个实验用于实现模型的功能以及做性能测试。实验性能测试结果以 表格的形式给出，以数据为基础探讨了该过滤模型过滤性能的优劣，得出了该过 2 b w - - l v q 邮件过滤模型 滤模型的适用范围。论文还对传统黑白名单过滤模型进行了改进，阐明了改进的 目的与方法，也完成了一个实验用于实现模型的功能。之后，对两种过滤模型在 邮件系统的接入点进行了讨论。最后，就两种过滤模型分别提出了优化过滤性能 的方法，这也是作者下一步需要完成的工作。其中，l v q 邮件过滤模型的设计 以及实验分析是本论文最重要的部分。 本论文正文一共分为九章：第一章为引言：第二章介绍邮件过滤的相关背景 知识和基础知识：第三章，为本论文重点，介绍了垃圾邮件的定义和分类，详细 描述了l v q 邮件过滤模型的原理以及相关算法；第四章描述了l v q 邮件过滤模 型的实现细节；第五章，是本论文的第二个重点，对l v q 邮件过滤模型的测试 结果做了非常细致的分析；第六章讲解了改进型的黑白名单模型；第七章是对过 滤系统与邮件系统之间合作的描述 第八章讲述了两种模型提高过滤性能的途 径：第九章是本论文的结论。正文后是参考文献以及致谢。 b w - - l v q 邮件过滤模型 第二章理论基础 本章介绍了关于论文课题的相关理论基础和背景知识，描述和评估了许多广 泛使用的邮件过滤方法，进一步探讨了文本分类中的主要问题，包括它的类型、 学习方法以及其它一些元素。此外，还考察了广泛应用于邮件过滤领域的一些典 型的文本分类方法。 2 1 邮件过滤的现有方法 由于因特网的爆炸性增长，垃圾邮件数量也随之爆发。这些垃圾邮件困扰着 用户、网络管理员和网络服务提供商。因此，人们投入了极大的精力对这一问题 加以研究，而且已经取得了一些成果，现在已经存在许多过滤方法，它们针对的 过滤对象可能不同，针对相同过滤对象也可以使用不同的过滤策略，这些方法都 能对垃圾邮件过滤起到一定的作用，但是在过滤效率上的表现有好有坏。 以邮件发送者的名字或者发送地址做为过滤对象来判断邮件合法性的邮件 过滤方法是过滤垃圾邮件最直接的方法。这种方法要求预先将违法邮件地址存储 起来，称之为黑名单。当一封邮件到来时，将其发送者地址在黑名单中检索，如 果属于该名单，则认为此邮件为垃圾邮件，否则认为此邮件为f 常邮件。然而， 垃圾邮件发送者能简单地获取一些新的合法邮件地址或者伪造地址来隐藏他们 的身份。就像c r a n o r 1 5 1 指出的，获取假名是廉价的。这使得到目前为止，黑名 单过滤器只能起到非常有限的作用。 邮件正文文本是另- - 0 e 过滤对象，它包含了更多的信息，是自动过滤方法研 究的焦点。一个典型的关注于邮件内容的技术就是关键字过滤技术，它已经应用 于e l m 和p r o c m a i l 等著名的邮件系统中。该技术的原理是针对邮件内容给出一 个规则集，如果一条规则中的所有关键字都出现在了邮件内容中，那么这条规则 就算匹配成功，其对应的处理方法会被调用来处理这封邮件。然而，对于许多不 了解计算机语言的人们来说，建立一个有效的规则集是件困难的事情，而且，具 体设置一条规则的过滤条件是很容易出错的，一些错误会导致灾难结果。另外， 用户在不同时间可以有他们不同的垃圾邮件标准，他们需要每次手动的修改对应 的规则来满足当前的过滤需要，这种方法的自动度因此被贬低。就像s a h a m ie t a l t 3 3 提出的，基于规则过滤的方法在垃圾邮件过滤方面的应用是有限的。 文本分类中一些成功的机器学习方法目前被成功的用于了垃圾邮件过滤领 域，这些也是以邮件正文文本做为过滤对象。c a r r e r a s 和m a r q u e z l 6 】指出垃圾邮 4 b w - - l v q 邮件过滤模型 件过滤可以被看作是文本分类问题的一个特例，它仅仅只有两个目标分类：即f 常邮件与垃圾邮件。基于学习的分类方法对过滤系统要求高自动化性能方面提供 了极大的支持，使过滤系统变得更加易用。事实上，许多文本分类方法已经衍生 出相对应的垃圾邮件过滤算法，其中的一些方法已经在邮件过滤领域展示出了极 好的使用前景。 2 2 文本分类 当前，对电子文件的使用已经普及，它成为网络资源的重要组成部分，用以 用户交流共享。但是相关资源众多，浏览式的检索十分费时，所以，根据用户需 求能自动过滤电子文件的自动方法被提出，使访问指定资源变得方便快速。t e x t c a t e g o r i s a t i o n ( t c ) 5 就是完成这项工作的工具之一。一般情况下，文本分类的 目标都是将文档分类至预先定义好的固定数量的文档类别中。现在，文本分类正 广泛应用于布尔信息恢复系统、文档过滤、文档组织、单词模糊识别以及网络资 源分级自动索引等领域，电子邮件过滤是文档过滤中的一种。 2 。2 1 文本分类的种类 2 2 1 1 s i n g l e - l a b l e v s m u l t i - i a b l e “单标签文本分类”( s i n g l e 1 a b l et e x tc a t e g o r i s a t i o n ) 是指个文本用例必 须确切的分配到预先定义好的文本类中的一个；“多标签文本分类”( m u l t i l a n e t e x tc a t e g o r i s a t i o n ) 是指一个文本用例可以属于不同的多个文本类。单标签文本 分类的种特殊情况就是二进制文本分类，它的每一个文本要不分配到一个文本 类中就会是在相对的那个文本类中。事实上，应该更关注二进制文本分类，这不 仅因为能够用于二进制分类的算法也能用于其它单标签分类，而且它在现实应用 中也更具有代表性。显而易见的，电子邮件过滤是二进制文本分类的一个案例， 它包括“垃圾邮件”和“正常邮件”两个分类。 2 2 。1 2c a t e g o r y - p i v o t e dv s d o c u m e n t - p i v o t e d 有两种不同的方法使用文本分类器，一种是先给出一个文档再找出它的所有 对应分类，另一种是先给出一个分类再找出此分类下的所有文档。前者称为“以 文档为中心的文本分类”( d o c u m e n t p r i v o t e d t e x tc a t e g o r i s a t i o n ，d p c ) ，后者称 为“以类型为中心的文本分类”( c a t e g o r y p r i v o t e d t e x tc a t e g o r i s a t i o n ，c p c ) 。 b w l 、7 q 邮件过滤模型 两者的区别不仅仅是在概念上，而更在于实用上。c p c 适用于当一个新的分类 类型要被加入到己经存在的分类集合中，而这时已经有许多文档已经分好类的应 用环境。d p c 则适用于在不同的时刻及时获取到文档并对其分类的应用环境。 显然地，电子邮件过滤属于以文档为中心的文本分类。 2 2 1 3h a r d - d e c i s i o nv s r a n k i n g “分级文本分类思想”( r a n k i n g ) 是指给出一个文档，分类系统根据计算结 果可以简单地将它分类到预定义好的某一级中，而不需要直接决定文档的分类。 这种分类是半自动的，人类专家通过辅助分级表作出最后的分类决定。这样的系 统在需要严格可靠性的应用环境下是特别有用的。“硬决策思想”( h a r d d e c i s i o n ) 是指文本分类系统可以根据一个文档在分级中最大可能性来决定此文档的分类。 这种分类方法是全自动的，分类系统处理了文档分类的全部工作。使用半自动还 是全自动分类取决于应用的需要。对电子邮件过滤而言，两种文本分类方法都具 有可行性，但是速度是邮件通信的另一个重要性能指标，而面对大量邮件进行专 家分类是极其费时的，所以，“硬决策思想”是做邮件过滤的一般思想，而“分 级文本分类思想”只在特殊的高严格环境下具有实用性。 2 2 2 文本机器学习 机器学习从研究人类学习行为出发，研究一些基本方法( 如：归纳、一般化、 特殊化、类比等) 去认识客观世界，获取各种知识和技能，以对人类的认识规律 进行探索，深入了解人类的各种学习过程，借助于计算机科学和技术原理建立各 科学习模型，从而为计算机系统赋予学习的能力【8 】。文本机器学习是它的一个应 用领域，用于文本智能分类。 2 2 2 。1 基本学习途径 “学习” 9 在机器学习领域的定义是：如果一个计算机程序针对某类任务t 的用p 衡量的性能根据经验e 来自我完善，那么我们称这个计算机程序在从经 验e 中学习，这对某类任务t ，它的性能用p 来衡量。基本的学习途径分为4 个步骤：选择训练经验；选择目标函数：选择目标函数的表示；选择函数逼近算 法，从而构建一个学习系统。文本机器学习系统的构建也要按照这一系列的步骤 完成。 系统从训练经验中学习，给学习器提供的训练经验对它的成败有重大的影 b w l 、7 q 邮件过滤模型 响。训练经验有三个关键属性：第一，训练经验能否为系统的决策提供直接或间 接的反馈；第二，学习器可以在多大程度上控制训练用例序列：第三，训练用例 的分布能多好的表示实际分布，通过用例来衡量最终系统的性能p ，一般而言， 当训练用例的分布和将来的测试用例的分布相似时，学习具有最大的可信度。实 际上，学习的用例通常与最终系统被评估时的用例有一定的差异，掌握了用例的 一种分布，不一定会使它对其他的分布也有好的性能。 目标函数是指在某些条件的约束下，对现状欲达到目标进行评估的函数，评 价函数和启发函数都是目标函数。目标函数的表示有很多选择，可以用程序表示， 可以用规则集合表示，可以用人工神经元网络。通常，选择这个描述包含一个重 要的权衡过程。一方面，总希望选取一个非常有表现力的描述，以最大可能地逼 近理想的目标函数。另一方面，越有表现力的描述需要越多的训练数据，使程序 能从它表示的多种假设中选择。 2 2 2 2 训练集和测试集 训练集和测试集可以合称为性能测试集。训练集是人工预先分类的文本的集 合，是机器学习方法的关键资源。分类器通过观察训练集的特征来归纳学习。测 试集用于测试模型的有效性。文本分类中的性能评估是看分类器作出的判断与专 家判断的匹配度。值得注意的是，测试集中的文档不应该和训练集中的文档具有 相近的特征，因为测试用的数据是最有利于此分类器得到高性能的数据，这样得 出的结果是很难让人信服的。性能测试集的另一个目的是提供给跨分类器比较测 试，跨分类器比较需要完全相同的集合和相同的训练集与测试集之间的分界。 y a n g ”j 于旨出如果不依从这些条件，将很难比较之间的实验结果。 2 2 2 3 特征选择 文本分类中的特征就是文档的字、词或者短语。y a n g 和p e d e r s o n 指出 3 0 l 3 1 1 , 文本分类较困难的问题在于确定特征向量的维数。为了提高分类性能、减少计算 复杂度，根据总体的频率度一些低信息的特征应该被除去，仅选择- - + 部分能代 表分类类型的特征保留下来。例如，“t h e ”、e ”或者“i t ”这些几乎出现在所 有文档中的词汇就应当被忽略，这样做不会失去任何影响分类的信息。这些词汇 通常存储于停止列表( s t o p 1 i s t ) 中，在个文档被分类器处理之前，先将其中 的属于停止列表中的词汇除去。另外，一些文本过滤方法在预处理时还要考虑衍 生词，也就是具有相同词根的一组词。在处理它们时，象“d i d ”、“d o i n g ”、“d o n e ” 这些词都会被变形为词根“d o ”。这样做减小了特征向量维数。自动的特征选择 b w - - l v q 邮件过滤模型 方法有很多，先根据统计集排列候选术语，再删除非信息术语，最后可构建出特 征向量。 2 2 2 4 有效性评估 准确率( p r e c i s i o n ) 和查全率( r e c a l l ) 是用于文本分类有效性评估时最广泛 使用的方法。准确率是指所有文本中与人工分类结果吻合的文本所占的比率，即 正确分类的文档数与实际分类的文档数之比：查全率是指人工分类结果应有的文 档中分类系统吻合的文档所占的比率，即正确分类的文档数与应有文档数之比。 除此之外，正确率( a c c u r a c y ) 用于指示总体正确分类的比率，错误率( e r r o r ) 用于指示总体误判的比率。 对电子邮件过滤而言，仅存在两个分类：正常邮件( 1 e g i t i m a t e ) 和垃圾邮 件( s p a m ) 。他们的相关评估指标如下：正常邮件准确率( 1 e g i t i m a t ep r e c i s i o n ， l p ) 、垃圾邮件准确率( s p a mp r e c i s i o n ，s p ) 、正常邮件查全率( 1 e g i t i m a t e r e c a l l ， l r ) 、垃圾邮件查全率( s p a r er e c a l l ，s r ) ，正确率( a c c ) 和错误率( e r r ) ，可 以按照如下的公式计算： 表2 1 邮件测试值表 专家人工判断 正常邮件垃圾邮件 正常邮件 ab 过滤网络判断 垃圾邮件 cd l p ：生 n + b 朋：三 a + c 4 。： ! ! 一 a + 6 + c + d s p ：j ls r ：生 c + db + d 胁： ! ! a + 6 + c + d 理想的，一个电子邮件过滤器应该提供高的准确率和垃圾邮件精确率。 s a h a r n ie ta l 2 8 1 指出s p 是绝大多数邮件用户最关注的性能，没有人愿意他们正常 的邮件被当作垃圾邮件而被丢弃了。l r 也是一项重要的指标，越高的l r 表示 越少的合法邮件被误判，这也是用户所希望的。当文本分类器的内部参数或者判 定闽值被调节时，它会展示出在精确率和查全率之间的平衡，单一追求高的查全 8 b w - - l v q 邮件过滤模型 率通常都会牺牲掉精确率，反之亦然。所以，一个分类器应该通过一种混和了准 确率和查全率的方法进行评估。现在广泛使用的混和方法是无亏损点和f 1 测试 值方法。无亏损点取准确率和查全率的平均值，然而，当准确率和查全率两者的 值相差很大时，无亏损点方法不能反映出系统的真实行为。f 1 测试值在1 9 7 9 年 由r i j s b e r g e n 定义，其表达式如下： e = 舞 这个表达式中查全率和准确率拥有相同的权值，当查全率与准确率越接近时 f l 测试值越接近最大值：否则，二者中具有较小值的一方决定了f 1 测试值。然 而，a n d r o u t s o p o u l o se ta l 1 0 l 指出，f 1 测试值不适用于电子邮件过滤，因为很难 简单地根据其两个分类的“成本”确定权值。在他们的实验中，“成本”意味着 将一个正常邮件划归为垃圾邮件所付出的代价是将一个垃圾邮件划归为正常邮 件的五倍。五越大，一个相关误判付出的代价越大。根据上面的分析，带权值的 准确率( w e i g h t e da c c u r a c y ，w a c c ) 和带权值的错误率( w e i g h t e de r r o r ，w e r r ) 被提出作为电子邮件过滤的补充评估方法，表达式如下： w a c c ： 墨：! 垡 丑+ ( a + c ) + ( b + d ) 耽押： 生：! 垒 五+ ( 盘+ c ) + ( b + d ) 为了避免主观错误的对准确率、错误率的高低的判断，需要定义另外两个判 断值：基准带权值准确率( b a s e l i n ew e i 曲t e da c c u r a c y ，b w a c c ) 、基准带权值错 误率( b a s e l i n ew e i g h t e de r r o r ，b w e r r ) 。“基准”是分类器没有使用时的情况， 也就是说，这时合法邮件都被f 确分类，但是垃圾邮件都被划分为了正确邮件。 在这种情况下，l p 为1 0 0 ，s r 和s p 都是o ，表达式如下： 删c c = 丑4 ( + c ) + ( 6 + d ) b w e ： ! ! 旯+ ( d + c ) + ( 6 + d ) 总成本率( t o t a lc o s tr a t i o n ，t c r ) 反映了过滤器使用后的错误率与基准错 误率的比较： t c r b w e r r 旦 臃兄4 c + b 9 b w - - l v q 邮件过滤模型 点。 t c r 越大，过滤器性能越好。当t r c li 特过辕艄件l i l 厂刘 过滤子系统 ( iv 卵i t 算法) 获知邮件类塑 图3 - 2l v q 邮什过滤模型构架 2 0 从模型构架中可以看 出，l v q 邮件过滤模型由 两部分组成。第一部分是 “训练予系统”，负责完成 邮件过滤系统的初始化训 练工作，将过滤系统中的 过滤相关参数调节到可用 值，采用l v q t r n 算法。 第二部分是“过滤予系 统”，负责完成将未知类型 邮件定位到目标类型的映 、；， 1 o o o o 1 o 0 l o 0 1 o o 1 o o 1 o 0 l 0 o 1 0 0 1 o 1 o ，。，。l = 矿 b w 一【v q 邮件过滤模型 射工作，采用l v q f l t 算法。两个算法的详细描述参见3 2 4 以及3 2 5 两节。 两个子系统之间功能独立，在运行时间上也是分离的。训练子系统先运行， 运行完成后才转入过滤子系统运行。l v q 邮件过滤模型存在三种状态，状态转 换关系见图3 3 。模型最初处于“原始状态”，此时系统各过滤参数没有可用值， 不能对邮件进行过滤。训练子系统运行，模型转入“初始化状态”，此时各过滤 参数正在向可用值逼近，在这一过程中系统仍然不能对邮件进行过滤。如果训练 成功，即各过滤参数达到可用值，模型转入“过滤状态”；如果训练失败，模型 退回到“原始状态”。模型转入“过滤状态”后，过滤子系统启动运行，开始执 行邮件过滤工作，接收外界传入的待分析邮件文本，进行邮件类型分析。 初始化训练( l v f f l r a 算法)邮件过涟( l v q f l t 算法) 初始化训练失败 图3 3l v q 邮什过滤模型状态转换图 3 2 4l v q 邮件过滤模型训练算法l v q t r n 3 2 4 1l v q t m 算法 l v q t m 算法用于l v q 邮件过滤模型的有监督学习，完成对l v q 邮件过滤 模型过滤参数的设置，是训练子系统的核心。 算法开始之前需要完成一系列的数据预处理工作：对邮件训练集分类，对每 封邮件样本的正文文本进行分词，计算每个单词在每个分类中的互信息量并选择 最大互信息量作为每个单词的互信息量，对邮件训练集提取特征向量。这一系列 工作在本章第- d , 节都有详细的介绍，这里不再累述。 b w - - l v q 邮件过滤模型 l v q t r n 算法描述如下 l v q t m 算法使用预先准备的邮件训练集将l v q 邮件过滤模型训练完成，每 b w - - l v q 邮件过滤模型 个子类得到个能代表该子类的聚类中心，这一组权值向量就是以后邮件过滤的 依据。 为了清晰呈现出l v q t m 算法的流程，在上面的介绍中隐去了对算法的些 细节描述，在接下来的几个小节将加以说明。 3 2 4 2 初始化聚类中心 在初始化聚类中心时，选取的邮件样本具有随机性，如果这个邮件样本本身 的类型和欲初始化的聚类中心所代表的邮件子类类型不相同，则会导致l v q t r n 算法不断学习，竞争层各神经元权值无法收敛的现象。所以，在初始化聚类中心 时，必须选取与欲初始化的聚类中心所代表的邮件子类类型相同的邮件样本。由 于l v q 邮件过滤模型在数据预处理的时候就已经完成了邮件分类工作，所以可 以方便的从各个邮件训练集子类中各抽取一个类型符合的样本，使用公式( 3 1 ) 矢量化后作为初始的聚类中心。 3 2 4 3 相似度的计算 在l v q t m 算法中，采用的公式( 3 - - 4 - - 1 ) 是向量空间模型( v s m ) 中普 遍使用的用于计算向量相似度的余弦公式，它对普通余弦公式有一点改动，对中 心向量引入了权值的概念，提高了相似度比较的精确性。在本论文实验中，由于 各个邮件子类的的竞争力相当，所以，每个子类的聚类中心的权值都为1 ，公式 ( 3 4 1 ) 简化为： 咖，2 卷n , f 豢2 n 2 馘( 3 - - 4 - - 2 ) s i m 值越大两个向量之间越相似，最大s u n 值对应的聚类中心与输入权值向 量有最大相似度，此聚类中心所代表的子类竞争获胜。 3 2 4 4 学习率选择 学习率是指一次训i 练迭代的学习力度，也即对聚类中心的调整力度。选择学 习率必须考虑在学习速度和最终权值稳定性之间做一个折衷。接近0 的学习率意 味着学习速度很慢，然而，一旦权值向量达到一个类的中心，它将保持在中心附 b w - - l v q 邮件过滤模型 近。相反，接近1 的学习率意味着学习速度很快，但是一个权值向量到达一个类 后，它将代表这个类中的不同向量来回振荡，不能收敛。因此，作者在l v q t m 算法中对学习率进行分段设置，这种方法既保证有较快学习速度，也使聚类中心 向量能尽快收敛。 学习分为两个阶段，第一阶段为粗学习阶段，在这阶段u ( t ) 选取大于o 0 5 的 参数加快学习步伐，本论文选取了o 5 这个经验值。当聚类中心能够较为集中的 代表所属邮件子类，也即各输入权值向量代表的子类连续五十次被正确划分后， 学习就转入了第二阶段。第二个阶段为细调整阶段，u ( t ) 设为经验值o 0 5 。在这 一阶段，聚类中心在较小范围内的进行调整，不会出现大的波动，易于敏感察觉 到收敛点。 3 2 4 5 终止条件 l v q t m 算法应该在各个聚类中心都收敛的情况下结束，这个时候，每个聚 类中心都能很好的代表相对应的邮件子类。上一小节介绍学习率时提到，聚类中 心相对稳定后就进入了学习率的细调整阶段，也就是说，在进入此阶段之前 l v q t r n 算法还不可能结束。在学习率粗学习阶段结束的时刻，统计剩余训i 练样 本数目，如果样本数目小于训练集中样本总数的一半，则训练失败并退出：否则， 进入学习率细调整阶段继续对模型进行训练，当有训练集样本总数一半的邮件样 本被：兀j ：确划分，则认为此时聚类中心已经收敛，训练正常完成并退出；但是，如 果邮件训l 练样本集全部使用完也没有使正确划分的邮件样本达到样本总数的一 半，则训练失败并退出。两种训练失败的情况都是因为选取的训练集的邮件样本 数目太少，不能满足训练要求，出现这种情况时需要对训练集调整后再重新训练 模型。 3 2 。5l v q 邮件过滤模型过滤算法l v q f i t 3 2 5 1l v q f i t 算法 l v q f l t 算法用于l v q 邮件过滤模型的无监督学习，完成对待过滤邮件的类 型定位，是过滤子系统的核心。 2 4 b w - - l v q 邮件过滤模型 l v q f l t 算法描述如下 b w l v q 邮件过滤模型 l v q f l t 算法计算过程简单，主要的计算消耗在对输入邮件的表示、与聚类 中心相似度的计算，以及规约计算三个方面。 为了清晰呈现出l v q t m 算法的流程，在上面的介绍中隐去t n 算法的一些 细节描述，在接下来的几个小节将加以说明。 3 2 5 2 胜者全得竞争 本章前面已经分析到，邮件被划分为若干子类后，各子类的特征会相对集中， 所以过滤模型的竞争层采用了“胜者全得竞争”机制，即每次竞争只能有一个竞 争元获得胜利，也就是说，在竞争层，一个输入向量会被划分到某一个子类中， 也仅会被划分到一个子类中。因此，l v q f l t 算法的公式( 3 7 ) 中，竞争输出 矩阵c p 在m 行上有且仅有一行被置1 ，其余行全为0 ，代表输入邮件的类型只 会被确认为是唯一一种邮件子类，即是被置为1 的行对应的邮件子类。 3 2 5 3 规约计算 l v q 过滤模型在规约层实现邮件子类到用户目标类型的映射，规约公式为 l v q f i t 算法的公式( 3 8 ) 。竞争输出矩阵c p 指示输入邮件所属的邮件予类， 规约矩阵w 2 指示出各个邮件子类对应的用户目标类型。规约计算就是将两个矩 阵相乘，根据矩阵乘法规则，w 2 的每一行与c p 的列逐一相乘作为结果分类矩 阵t 每一行的结果。由于c p 仅有第i 行为1 ，则w 2 的第i 列为1 的行就是t 被 置l 的行，按照规约矩阵的定义，此行正是表示i 子类对应的用户目标分类类型。 3 2 5 4 邮件类型常量标识 l v q f l t 算法在结束时要求返回邮件类型常量标识。邮件类型常量标识是自 定义的用于标识邮件类型的整型常量，它可以作为过滤结果传递给邮件系统，邮 件系统根据它调用相应的处理例程，对不同类型邮件进行不同的处理：还可以传 给测试系统用于测试值的统计。被过滤邮件的类型标识通过检索它的结果分类矩 阵得到，该矩阵每行代表一个用户目标类型，值为1 的行指示出邮件的类别。当 然，过滤系统还有很多方法向邮件系统传递过滤的结果，但是回送整型常量应该 算是其中比较简单的种方法，特别是在实验系统中更为常用。 b w - - l v q