（计算机系统结构专业论文）基于偏最小二乘方法的垃圾邮件过滤研究.pdf

摘要 随着电子邮件应用越来越普遍，垃圾邮件问题已经有愈演愈烈之势，严重地 影响了电子邮件的正常使用。因此，垃圾邮件过滤技术的研究有着十分重要的实 用价值。 近年来，基于机器学习方法自动构建个性化的过滤模型已经成为垃圾邮件过 滤研究重点之一。运用机器学习方法，也就是预先人工判定邮件的类别，将垃圾 邮件过滤当作文本分类的一个分支来处理。因为训练过程中同时使用了正常邮件 和垃圾邮件的特征，所以最终生成的过滤器可以自适应不同用户的邮件分布。许 多机器学习方法已经应用到了垃圾邮件过滤领域，取得了较为满意的结果，但由 于每封邮件中的词很少，对大量邮件进行处理时很容易产生高维的特征空间，而 其中大部分词出现的次数很少，从而会产生严重的数据稀疏性；同时，邮件中经 常出现同义词或者近义词，而且很多邮件的内容非常类似，因此在邮件的内容之 间容易出现严重的多重相关性。针对这些问题，本文提出一种基于偏最4 - - 乘 ( p l s ) 的特征抽取方法。 新方法的基本思想是：通过分析邮件原始特征与对应类别之间的关系求解二 者之间协方差的最大化问题。对高维的原始特征进行多次线性组合的迭代处理， 并用偏最小二乘回归函数进行拟合，分别提取出最能反映原高维数据的特征向量 组合，从而达到降低特征维数和克服多重相关性的目的。然后应用交叉有效性算 法得到最佳的特征维数后用提取出的向量构造新的向量空间。 本文采用c e a s2 0 0 6 的基准数据集e n r o n s p a m 数据集进行了过滤实验， 并与目前常用的贮特征选择方法进行了对比实验，实验结果表明，新方法在较 低维数上可以获得良好的邮件过滤性能，是一个可行而有效的邮件过滤方法。 本文的主要创新点如下： 1 将偏最d , - 乘特征抽取方法应用于邮件过滤领域，有效地解决了邮件数 据中普遍存在的高维数、数据稀疏性和多重相关性问题； 2 采用交叉有效性算法来确定抽取出的特征维数，提高了模型效率。 关键词：垃圾邮件过滤；偏最d , - - 乘；特征抽取；维数约简；交叉有效性 a bs t r a c t t h e p r o b l e mo f u n s o l i c i t e db u l ke - m a i l ，o rs p a m ，g e t sw o r s ew i t he v e r yy e a r t h i s d e v e l o p m e n th a s s t r e s s e dt h en e e df o ra u t o m a t i cs p a mf i l t e r s r e c e n t l y ，t h ef o c u so fs p a r nf i l t e r i n gr e s e a r c hh a sb e e np u to nm a c h i n el e a r n i n g f o rt h ea u t o m a t i cc r e a t i o no fp e r s o n a l i z e ds p a mf i l t e r s i no t h e rw o r d s ，s p a mf i l t e rh a s b e e nr e g a r d e da so n ee m b r a n c h m e n to ft e x tc l a s s i f i c a t i o n t h er e s u l t i n gs p a mf i l t e r h a st h ea d v a n t a g eo fb e i n go p t i m i z e df o rt h ee - m a i ld i s t r i b u t i o no ft h ei n d i v i d u a lu s e r u pt on o w , t h e r ea lem a n ym a c h i n el e a r n i n ga l g o r i t h m sa t t e m p t e dt og e n e r a t es p a m f i l t e r s b u tb e c a u s et h ew o r d sa p p e a ri ne a c hm a i la r es os p a r s et h a tw h e nw ed e a l w i t ht h e s ed a t a s e tw ec a ne n c o u n t e rh i g l lw o r dd i m e n s i o n a l i t i e sa n ds e v e r e d a t a - s p a r s e n e s s ；m o r e o v e r , s i n c et h e r ea r eq u i t eaf e wt h e s a u r u so rs i m i l a rc o n t e n ti n d i f f e r e n tm a i l ，t h es e v e r em u l t i - c o l l i n e a r i t yo ft h ew o r d sa p p e a ri no n em a i lm u s tb e t a k ei na c c o u n t t od e a lw i t ht h e s ep r o b l e m s ，an e wf e a t u r ee x t r a c t i o nm e t h o db a s e d o np a r t i a ll e a s ts q u a r e s ( p l s ) i sp r e s e n t e di nt h i sp a p e r t h ei d e ao fn e wm e t h o di st h a t f i r s t l ya n a l y z i n gt h er e l a t i o n s h i po fm a i l s o r i g i n a lf e a t u r e sa n dc o r r e s p o n d i n gs o r t ，i no r d e rt of i g u r eo u tt h em a x i m i z a t i o ni s s u e o fc o v a r i a n c eb e t w e e nt h e m ，o r i g i n a lf e a t u r e sa r ep r o c e s s i n gl i n e a rc o m b i n a t i o n r e p e a t l ya n de x t r a c tn e wm u c hl e s sc o m p o n e n t s ，s ot h es u b s p a c ec o n s t r u c t e db yn e w c o m p o n e n t sc a nr e s o l v et h ep r o b l e m ss t a t e da b o v e f i n a l l y , i n t r o d u c i n gc r o s s v a l i d i t y a l g o r i t h ma n dm a k ec e r t a i nt h ee x t r a c t e ds u b s p a c e sd i m e n s i o n s t h ee x p e r i m e n t so nc e a s2 0 0 6b e n c h m a r kd a t a s e t s ( e n r o n s p a r ed a t a s e t s ) s h o wt h a tp r o m i s i n gr e s u l t sa r er e p o r t e da f t e re v a l u a t e db yt r e cs p a mt r a c ka n dt h e n e wm e t h o dp e r f o r m sb e t t e rt h a nf e a t u r es e l e c t i o nb y 贮s t a t i s t i c s t h em a i nc r e a t i v e so ft h i sp a p e ra r e ： ( 1 ) p r o p o s i n gp l sf e a t u r ee x t r a c t i o nm o d e lf o rs p a mf i l t e r i n gr e s e a r c h ，i tc a n e f f e c t i v e l yr e s o l v et h eu b i q u i t o u sp r o b l e m si nm a i ld a t a s e t ：h i g hw o r d d i m e n s i o n a l i t i e s ，s e v e r ed a t a - s p a r s e n e s sa n dm u l t i - c o l l i n e a r i t yp r o b l e m s ( 2 ) t oi m p r o v ef i l t e re f f i c i e n c y , i n t r o d u c i n gc r o s s - v a l i d i t ya l g o r i t h mt om a k e c e r t a i nt h ee x t r a c t e ds u b s p a c e sd i m e n s i o n s k e yw o r d s ：p a r t i a ll e a s ts q u a r e s ；s p a mf i l t e r i n g ；f e a t u r ee x t r a c t i o n ；c r o s s v a l i d i t y i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：签字日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：年月 日 导师签名： 签字日期：年 月 e 1 基丁偏最小二乘方法的垃圾邮什过滤研究 1引 言 1 1 研究背景 电子邮件是互联网上最大的业务，也是人们工作生活中最重要的交流手段 之一。然而随着垃圾邮件的出现，电子邮件在给人们带来便利的同时也带来了 互联网上仅次于病毒的第二大问题【l 】：垃圾邮件的防治和过滤问题。反垃圾邮 件技术成为近年来研究的热点。 1 1 1 垃圾邮件定义 1 9 9 4 年4 月1 2 日，一对居住在美国亚利桑那，专门承接移民事务的律师 夫妇写了一段p e r l 脚本的小程序，将他们的移民顾问服务广告的电子邮件发送 给大约6 0 0 0 个u s e n e t 新闻组用户。这一事件即为垃圾邮件的起源，被称为“绿 卡事件。时至今日，垃圾邮件成为了i n t e m e t 上仅次于病毒的第二大问题，耗 费了人们大量的时间和花销。 中国互联网协会在中国互联网协会反垃圾邮件规范【2 】中是这样定义垃 圾邮件的： 本规范所称垃圾邮件，包括下述属性的电子邮件： ( 一) 收件人事先没有提出要求或者同意接收的广告、电子刊物、各种形式 的宣传品等宣传性的电子邮件； ( 二) 收件人无法拒收的电子邮件； ( 三) 隐藏发件人身份、地址、标题等信息的电子邮件； ( 四) 含有虚假的信息源、发件人、路由等信息的电子邮件。 通常来说，垃圾邮件是未经同意接受的广告等信息。 1 1 2 垃圾邮件发展现状以及其危害 由于电子邮件成本低廉，垃圾邮件已经成为很多公司和组织进行营销宣传 的手段，而且有愈演愈烈的趋势。除了给电子信箱的使用者造成很多不便，垃 圾邮件还给社会造成了很大的经济损失。著名网络安全研究机构 g a d i c a t i g r o u 3 】指出，2 0 0 4 年全球企业因垃圾邮件而引起的损失已超过2 0 5 亿美元。情况如得不到控制，2 0 0 7 年时损失将暴涨到1 9 8 0 亿美元，到那时候， 垃圾邮件将占总邮件比例的7 0 。在我国，2 0 0 3 年我国处理垃圾邮件浪费的 g d p 高达4 8 亿元人民币；2 0 0 4 年中国互联网协会年公布的第二次反垃圾邮件 调查结果显示，2 0 0 4 年第一季度，中国网民平均每周收到垃圾邮件1 9 3 封，占 硕士学位论文 收到邮件总数的6 0 5 ，这个数字较2 0 0 3 年年底第一次调查时的2 6 2 7 上涨 了3 4 2 3 个百分点。据市场调研公司f e r r i s 公司的最新研究报告【3 l ，2 0 0 5 年垃圾 邮件给全球生产力造成的损失和其他反垃圾邮件的投资将达到5 0 0 亿美元，其 中仅美国公司的损失和投资将超过三分之一，达到1 7 0 亿美元。而中国作为仅 次于美国的受垃圾邮件影响的第二大国，因垃圾邮件带来的损失同样相当严重。 具体说来，垃圾邮件的危害主要表现在以下几个方面： 1 ) 占用网络带宽，浪费网络资源，干扰邮件系统的正常运行。 当有限的网络资源和网络带宽上充斥大量的垃圾邮件时，就降低了网络的 使用效率。对邮件服务器而言，收到的垃圾邮件占用了它的磁盘空间和网络带 宽，浪费了处理时间。更严重的是，如果垃圾邮件得不到有效控制，用户会放 弃邮箱，服务商将被迫终止服务，给企业带来很大的损失。另外，当一些用户 利用邮件服务器对外发送垃圾邮件时，该服务器会被列入黑名单而遭外部封杀。 因此，邮件服务器既要拒收来自外部的垃圾邮件，还要阻止自己的邮件用户对 外发送垃圾邮件。 2 ) 浪费用户的宝贵时间和上网费用。 如果我们每天都要花费一段时间来处理垃圾邮件，工作效率就要降低，对 整个社会来说，被浪费的时间更是一大笔宝贵的财富。有关调查显示，2 0 0 3 年， 网民平均每天需花费6 5 分钟来处理无用的邮件，单是下载垃圾邮件所花费的 上网费与电话费，全年就要浪费全球网民9 4 亿美元。 3 ) 对网络安全形成威胁。 一些垃圾邮件传播色情、反动等各式各样的有害信息，给社会带来危害。 黑客们利用电子邮件系统发送数以万计的垃圾邮件风暴攻击目标，使之瘫痪、 拒绝服务。垃圾邮件还可以被病毒利用，成为它们的传播途径。 1 2 反垃圾邮件技术现状 面临着垃圾邮件问题同益严重的现状，人们开始从多方面寻找解决方案。 例如，一些“邮箱运营商”成立了专门的部门处理垃圾邮件，并设立“首席垃 圾邮件官”，有些邮件客户端工具也提供了一定的垃圾邮件过滤功能。 解决、缓解垃圾邮件问题的方法和手段一般有法律和技术两种手段，下面 我们简单介绍。 1 2 1 反垃圾邮件立法 反垃圾邮件立法是通过政府等部门通过法律手段来控制垃圾邮件。例如， 一旦确认某个团体或个人是垃圾邮件的发送者，那他就面临着法律的制裁与处 罚。或者规定发送任何邮件都要付出一定的“邮票”代价，以此来制约垃圾邮 2 基于偏最小二乘方法的垃圾邮件过滤研究 件发送者大规模重复的发送邮件。针对目前垃圾邮件泛滥的现状，反垃圾邮件 立法的呼声日益渐高，中国互联网协会反垃圾邮件协调小组2 0 0 4 年2 月1 8 日 在北京发出关于加快“反垃圾邮件立法”进程的倡议【3 】，得到了众多组织机构 和邮件用户的响应【4 l 。2 0 0 5 年3 月，政协委员又在两会上提交了加快反垃圾邮 件立法的提案。但立法面临着一系列的问题。首先是垃圾邮件的概念之争，到 底什么是垃圾邮件，像宣传品、电子期刊等这类邮件是不是垃圾邮件很难界定， 垃圾邮件发送者会想尽一切办法逃脱法律的惩罚；其次是法律的执行问题，给 予什么样的处罚，而且，如果缺少国际合作，即使发现来自境外的垃圾邮件， 也无法制裁。如果规定发送邮件都需要一定的额外代价，在现阶段显然很难得 到广大邮件用户的认可。因此，尽管立法是解决垃圾邮件问题最有效的方法， 但反垃圾邮件立法在目前的情况下还无法得到实施。 1 2 2 垃圾邮件过滤技术 近年来，有关垃圾邮件过滤技术的研究开始逐步兴起，相关的投入也越来 越大，涌现了一大批相关产品。如果能够从技术上解决垃圾邮件问题，那是最 理想的了。目前常用的技术主要是从邮件的发送途径，发件人，收件人，正文 等邮件信息方面识别过滤垃圾邮件。下一节我们介绍目前常用的垃圾邮件过滤 技术。 1 3 垃圾邮件过滤技术介绍 电子邮件有自身的结构特点。邮件的协议和内容格式也是由r f c ( r e q u e s t f o rc o m m e n t s ) 的几个文档规定的。r f c8 2 1 5 】规定了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 o l ，简单邮件传输协议) ，定义发送邮件的机制。r f c1 7 2 5 t 6 】规定 了p o p 3 ( p o s to f f i c ep r o t o c o l3 ，邮局协议版本3 ) ，定义从p o p 3 服务器收取邮 件的机制。r f c8 2 2 7 1 定义邮件格式。随着电子邮件的广泛使用，邮件系统不仅 需要传输各种字符集的文本内容，而且还需要传送各种非文本文件( 例如图像 文件、w o r d 文件、p d f 文件、z i p 文件等) ，根据这个需求，人们又定义了m i m e 标准，作为r f c8 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 l 5 2 1 8 1 和r f c l 5 2 2 t 9 】这两个标准构成。 目前几乎所有的邮件服务系统都支持m i m e 标准。 从电子邮件的结构出发，寻找垃圾邮件的特征，在发件人、收件人、由邮 件头、邮件正文内容等各方面展开邮件过滤工作，是垃圾邮件过滤常采用的基 本方法。 1 3 1 服务器端和客户端的邮件过滤 先给出几个概念的解释： 硕士学位论文 1 ) m u a 。m u a 即m a i lu s e ra g e n t ，邮件用户代理。m u a 是邮件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 ra g e n t ，邮件传输代理。m t a 是一个专用 程序，其作用类似于邮局，用于在两个机器之间发送邮件，m t a 决定了邮件到 达目的地的路径。常用的m t a 有s e n d m a i l 、q m a i l 、p o s t f i x 等。 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 ，最常用的m d a 是p r o c m a i l 。 图1 1 电子邮件系统示意图 图1 1 是利用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 + 将邮件递交给接受方的邮箱，接收者可以通过三种方 式与邮箱交互： 利用网络文件系统直接访问； p o p 协议； i m a p ( i n t e m e tm a i la c c e s sp r o t o c 0 1 ) 协议。 按照邮件系统的角色结构，可以将邮件过滤分为三类： 1 ) m u a 过滤。即在用户端过滤。 2 ) m t a 过滤。m t a 过滤是指m t a 在会话过程中对会话的数据进行检查， 对于符合过滤条件的邮件做过滤处理。 3 ) m d a 过滤。m d a 从m t a 中接收到信件，在本地或远程递交时进行检 查，对于符合过滤条件的邮件进行过滤处理。很多的m d a 都支持垃圾邮件过 滤，如p r o c m a i l 、m a i l d r o p 和c y r u s i m a p 等。 4 基于偏最d , - 乘方法的垃圾邮件过滤研究 m t a 和m d a 过滤都是邮件服务器端的过滤，而m u a 过滤是邮件用户的 客户端的过滤从垃圾邮件过滤技术上看，目前常用的有白名单和黑名单技术、 规则过滤以及邮件内容过滤等。这些技术一般都同时适用于服务器端和客户端 的邮件过滤。 1 3 2 白名单和黑名单 白名单中的发件人发送的任何邮件都认为是合法邮件，黑名单中的发件人 发送的任何邮件都认为是垃圾邮件。这是目前电子邮件过滤中广泛使用的技术。 通常做法是收集一个黑、自名单列表，可以是电子邮件地址，也可以是邮件服 务器的域名、p 地址，收到邮件时对发件人进行实时检查。这种名单一般由比 较有信誉的组织提供，如中国互联网协会( h t t p ：w w w i s c o r g c n ) 和中国反垃圾 邮件联盟( h t t p ：w w w a n t i s p a m o r g ) 定期在主页上公开垃圾邮件服务器p 地 址名单1 0 】。个人也可以根据需求定义和维护自己的黑、白名单。 1 3 3 设置过滤规则 i 设置一些规则，只要符合这些规则的一条或几条，就认为是垃圾邮件。这 些规则通常有： 1 ) 信头分析 即分析邮件头部信息检查发件人的地址是否有伪造。通常，一封邮件从发 件人到收件人，中间要经过好几台服务器。每经过一台服务器，就会在相应的 头部加入一条r e c e i v e d 的信息，按照经过的服务器顺序由后向前添加。下面是 一个邮件头部信息例子： r e c e i v e d ：f r o mx r t m v 2 ( u n k n o w n 2 2 4 2 0 6 8 0 5 8 ) b yp 27 1 5 2 0 r a 9 h j e d u c n ( p o s 哿谢w i t hs m t p i d7 e 8 2 5 5 8 6 0 d f o r ：w e d , 2 5o c t2 0 0 60 0 ：0 3 ：1 1 + 0 8 0 0 ( c s r ) r e c e i v e d ：f r o mr e l a y a 9 h j e d u c n ( f i l t e r a 9 h j e d u c n 2 2 4 2 0 丘8 & 2 0 6 ) b yx r t m v 2v i ax i r t a m - a n t i s p a m s m t p ( v 2 1 2 1 + a n t i - r e l a y + a n t i - s p a r e ) i dx m a 1 1 5 8 9 4 0 2 6 0 9 f c j k y ； w e d , 2 5o c t2 0 0 62 3 ：5 1 ：0 0 + 0 8 0 0 ( c s t ) r e c e i v e d ：( f r o m0 5 5 5 0 u ! l o c a l h o s o b yr e l a y , a 9 h j e d u e l l ( 8 1 2 1 1 8 1 2 1 1 ) i dk 8 m f p o 9 0 0 0 5 8 3 2 力， iw e d , 2 5o c t2 0 0 62 3 ：5 1 ：0 0 + 0 8 0 0 m e s s a g e - l d ： r e c e i v e d ：f r o mu n k n o w n 1 4 8 1 8 0 4 4 2 3 b yr e l a y a 9 h j e d u e l lv i ax i r t a m - a n t i s p a m s m t p ( r 2 1 2 1 + a n t i - r e l a y + a n t i - s p a m ) i d x m a 1 1 5 8 9 4 0 2 5 6 0 2 t j 8 p ；w e d , 2 5o c t0 62 3 ：5 0 ：5 6 + 嬲d d 硕七学位论文 f r o m ： i z x 2 r 4 s u b j e c t ： s p a m 尊敬的注册用户您好： t o ： c o n t e n t - t y p e ：t e x t h t m l ；c h a r s e t = g b 2 3 1 2 ” r e p l y - t o ：”l d 7 8 “ d a t e ：w e d , 2 5o c t2 0 0 62 3 ：5 3 ：5 9 + 0 8 0 0 x - p r i o r i t y ：2 x - m a i l e r ：m i c r o s o f to u t l o o ke x p r e s s6 0 0 2 8 0 0 1 1 5 8 邮件中的f r o m 和t 0 是由发件人自己规定的，一些垃圾邮件发送者为欺骗 邮件系统和用户通常伪造f r o m 地址。但在邮件头部中r e c e i v e d 信息是由服务 器自动加上去的，通过比较r e c e i v e d 域( 特别是第一次经过的邮件服务器的 r e c e i v e d 域) 可以识别出伪造的发件人地址。 2 ) 群发过滤 如果一个邮件服务器在一段较短的时间内收到来自同一个地址的大量邮 件，就认为这个地址有可劁在发送垃圾邮件。另外，如果一个邮件服务器在一 段较短的时间内收到从不同地址发送过来的大量内容基本相同的邮件，就认为 这封邮件有可能是垃圾邮件。而且，有些垃圾邮件是通过猜测地址的方法群发， 在本节中的邮件头t o 域可以看到只有“q 4 s 9 u 3 4 2 7 4 f a 9 h j e d u c a 一个收件人。 3 ) 关键词精确匹配 可以定义一些反映垃圾邮件特征的关键词或短语【l 】，如“f l e e 、“免费”、“抢 注”、“热卖 、“实惠”、“特惠”、“特卖 、“赠送 、“保证有你想要的等，当 在邮件标题或者正文中匹配到若千条关键词或者短语，就判定为垃圾邮件。目 前很多邮件客户端软件( m u a ) ，如p r o c m a i l ，c o r e m a i l 等都支持用户自定义关 键字过滤。 4 ) 邮件内容的其他特征 例如，邮件中文字比较少，却有大量的超级链接：邮件正文中包含有大量 的随机字符等。还有些垃圾邮件在h t m l 格式正文中将大量的无敏感内容的文字 设置为很小而几乎看不见的字体，而将较少的敏感内容设为正常字体，这样既 可以保证邮件的视觉效果，又因为充斥着大量的正常文字，欺骗邮件过滤工具 的检查。 1 3 4 基于内容的垃圾邮件过滤技术简介 通常，并不仅仅是某几个固定的发件人在发送垃圾邮件，发送者在不断地 变化，黑、白名单方法有局限性。规则方法的不足之处在于规则都是人工指定 的，需要人们不断去发现和总结、更新，人为因素比较多，一些没有经验的用 户可能很难提供有效的规则。而且，手工制定规则比较耗时，准确率也受到了 6 基于偏最小二乘方法的垃圾邮什过滤研究 限制。随着时间的变化，垃圾邮件的特征也在变化，让用户维护这些规则也不 是一件易事。 一个很自然的想法是，对电子邮件的内容( 如正文文本) 进行分析，识别 出垃圾邮件。这就将垃圾邮件过滤与文本分类和信息过滤联系起来了，将文本 分类和信息过滤中常用的方法引入垃圾邮件过滤任务。在本文中，作者将这种 邮件过滤技术称为“基于内容的垃圾邮件过滤”或者“垃圾邮件内容过滤，【h 】。 这种内容过滤技术提供了更为准确的邮件过滤方法，可以自动获得垃圾邮件的 特征，并即时捕捉到垃圾邮件特征的变化。 基于内容的垃圾邮件过滤技术是文本分类技术的一个应用。文本分类的任 务是根据预先确定好的类别体系，将待分类文本分到相应的类别中去。从文本 分类角度来看，垃圾邮件过滤就是要求将邮件分为垃圾、非垃圾两类中的一类， 是一个二值分类问题。我们可以将电子邮件经过预处理提取出邮件正文的文本 内容，利用文本分类的算法识别垃圾邮件，这也是目前垃圾邮件过滤技术研究 的一个重要趋势。 基于内容的垃圾邮件过滤方法通常借鉴数据挖掘的思想，使用规则学习或 统计学习的算法来进行垃圾邮件过滤研究【1 2 1 。这种方法的主要思路是通过对大 量的邮件集( 包括垃圾邮件和合法邮件) 进行学习，训练分类算法，从而智能 的、自动的识别新的邮件。应用在垃圾邮件过滤中的学习算法很多，主要包括： 规则学习类的分类算法，如r i p p e r t 2 8 1 算法，决策树【3 0 1 算法等等；统计学习类的 分类算法，如朴素贝叶斯( n a i v eb a y e s ) 算法【1 3 】【1 4 】【15 1 ，最小近邻法( k - n n ) 【1 6 】【17 1 ，支持向量机算法( s v m ) 1 8 】等等。 基于内容的垃圾邮件过滤技术的发展尽管只有十几年的历史，但已经广泛 应用到了实用的邮件系统之中。目前，有很多支持垃圾邮件过滤的客户端邮件 工具，如o u t l o o k2 0 0 3 ，o u t l o o ke x p r e s s6 ，f o x m a i l5 0 ，e u d o r a6 等，这些工 具都提供了关键词匹配过滤的功能，其中f o x m a i l 还使用了n a i v eb a y e s 算法进 行智能过滤。还出现了一些具有垃圾邮件过滤功能的邮件网关，如美讯智公司 的安全邮件网关、九洲联信公司的a s f 反垃圾邮件网关、思维世纪的i x r a y 反 垃圾邮件网关等，可以为电信运营商、政府机关、企业以及学校提供邮件系统 安全防护。这些产品采用的技术大多是黑名单、规则过滤以及邮件内容扫描关 键词匹配等。 1 4 本文研究的内容 从发展现状来看，邮件过滤技术现在已经逐渐成熟，但在处理过程中往往 会遇到以下问题：一般来说，在把邮件文本表示为向量形式时，训练集中的原 始特征项可能多达数万个。通常认为，这些特征中的任何一个都对实现j 下确的 7 硕士学位论文 分类有着它的贡献。但是，由于邮件中经常出现同义词或者近义词，而且很多 邮件的内容非常类似，因此在这些大量的特征中肯定还包含着许多彼此相关的 特征，即在邮件的内容之间往往存在严重的多重相关性。这些相关的特征是冗 余的，是可以去除的。而且这种高维向量的处理具有极高的计算复杂度，尤其 是会产生所谓的“维数灾难”问题，因此，如何保留那些对判定邮件类别起着 重要贡献的特征，去除那些冗余的特征，以减少特征总数，即如何进行维数约 简，已成为一个日益重要的研究领域。 目前维数约简的方法分为特征选择( f e a t u r es e l e c t i o n ) 和特征抽取( f e a t u r e e x t r a c t i o n ) 两种。 1 特征选择：又叫独立评估法。在特征选择时一般都是利用某种评价函 数独立地对每个原始特征项进行评分，然后将它们按分值的高低排序， 从中选取若干个分值最高的特征项。现有的邮件过滤大部分采用这种 方法，但是通过这种方法选择的特征项中可能还包含着一些彼此相关 的因素，也就是说并不能很好地解决邮件数据中普遍存在的多重相关 性问题。 2 特征抽取：也叫综合评估法。其基本思想是利用映射( 或变换) 的方 法把原始特征项集映射到较低维的空间中，映射后的特征叫二次特征， 它们是原始特征的某种组合( 通常是线性组合) 。通过降维映射的方法， 构造数目较少的新特征，每个特征都是原有特征的函数，并通过新特 征进行识别。 偏最小二乘( p a r t i a ll e a s ts q u a r e s ，p l s ) 是一种先进的多元分析方法，可 以较好地解决自变量之间的多重相关性问题和样本点容量不宜太少等问题，同 时可以实现多种数据分析方法的综合应用，它的应用领域已经从最初的化工领 域快速扩展到机械、生物、地质、医学、社会学以及经济学等领域，但目前还 很少应用到邮件过滤领域。从发展方向来看，继续丰富邮件过滤方法，深入研 究降维技术是其发展的方向之一，而这也是邮件过滤的研究难点。对此，本文 提出了基于偏最d - 乘特征抽取的邮件过滤算法。 由于偏最小二乘特征( p l s ) 抽取算法本身并不对原始特征向量进行取舍， 而是通过构造所有特征的线性组合抽取出新的特征向量，所以该方法能最充分 地利用高维观测数据中的所有信息，特别是可以处理邮件数据中普遍存在的多 重相关性问题。通过偏最小二乘特征抽取算法，可以真实地描述高维邮件数据 的客观内在规律，从而达到提高邮件过滤的精度的目的。 本文的主要工作是： 1 根据偏最小二乘回归算法抽取出原始特征空间中的第一个潜在变量对， 使其能尽可能地表示x 与l ，之间的关系。 基丁偏最小二乘方法的垃圾邮件过滤研究 2 用原始信息减去第一次提取的信息后得到剩余信息，从剩余信息中得 到第一个潜在变量对，使其能尽可能地表示剩余信息。 3 重复1 、2 步，依次可以得到其余的潜在变量对。 4 采用交叉有效性算法来确定抽取出的潜在变量对的维数。 5 用抽取出的潜在变量对构造新的向量空间，在新的向量空间上进行邮 件类别的判定。 本文的主要创新点如下： 1 将偏最小二乘特征抽取方法应用于邮件过滤领域，通过对高维的原始特 征进行多次线性组合的迭代处理抽取出少量的特征向量，然后用提取出 的向量构造新的向量空间，最后采用普通的s v m 算法进行分类。 2 采用交叉有效性算法来确定抽取出的特征维数，大大提高了模型效率。 1 5 论文组织 本文的具体安排如下： 第一章：引言。介绍了邮件过滤技术的产生背景及其意义。 第二章：基于内容的垃圾邮件过滤技术概述。介绍了在垃圾邮件过滤领域 中，基于内容的过滤技术种类以及评价方法，并介绍了几种比较重要的邮件过 滤算法。 第三章：偏最小二乘特征抽取。介绍了偏最小二乘基于单变量的回归方法， 并对本文提出的偏最小二乘特征抽取方法作了较为详细的阐述。 第四章：实验与分析。该章节为本文的重点，集中介绍了本人所做的工作， 针对邮件数据中普遍存在的多重相关性问题，将偏最d - - 乘回归方法引入到邮 件过滤中，提出了基于偏最小二乘特征抽取的垃圾邮件过滤模型，并进行了实 验，对实验结果进行分析。 第五章：总结与展望。对全文工作进行了总结并提出下一步的工作展望。 9 硕士学位论文 2 基于内容的垃圾邮件过滤技术概述 基于内容的垃圾邮件过滤问题属于文本分类问题范畴，它是对邮件文本进 行二值分类的一个特例。简单地说，基于内容的垃圾邮件过滤就是有监督的学 习，即先根据已有的样例邮件数据找出能描述并区分邮件类别的分类器( 规则、 假设、或模型) ，然后利用该分类器对新的未分类邮件进行分类。 邮件过滤一般包括两个阶段，即学习建模阶段和测试分类阶段，学习建模 阶段的任务是归纳并得出分类器，为此，必须预先给定一个邮件集合s ：缸，观， 品) ，其中每个元素s i 为一个邮件文本，并同时标记了其所对应的类别如j c ， 因此s 中的每个元素都代表一个序偶勺h 如护。集合s 称为训练样本集，其中 的每个元素s ，称为训练样本。通过对该训练样本集进行学习，学习器将能够归 纳出一个分类假设。在测试分类阶段，为了评估该假设与目标函数的一致程度， 必须给出另一个邮件集合z f ，t 2 ，岛 ，其中每个元素也各自标记了其所对 应的类别y c ，集合丁称为测试样本集，其中的每个元素棚尔为测试样本。 对于每一个测试样本，用前面得到的分类假设对其进行分类，最后根据其分类 性能对该假设进行评估。若在测试集上的分类性能未达到预定目标，则必须回 到学习建模阶段，利用更多的样本重新进行学习或者修改分类学习算法，若测 试分类性能达到了预定的目标，则可应用该假设对新的待分类文本进行自动分 类。 2 1 邮件的表示 邮件过滤的首要问题就是原始邮件数据的处理问题，或者称表示问题。因 为邮件数据需要被表示为一种分类模型可识别的形式，分类器才能完成相应的 训练和分类过程。邮件过滤是根据邮件的内容完成的，最方便采用的特征就是 词或短语。所以词汇通常被用作表示邮件的特征。然后采用所谓的“特征表示”， 即通过提取该邮件的某些特征( 词汇) 来表示一个邮件。 由于邮件具有非结构化的特点，计算机很难对其进行直接处理，因此在进 行邮件过滤之前，首先要把邮件转化为结构化的表示形式，目前通常采用的是 词袋表示法( b a go fw o r d s ) ，它忽略了每个词条在邮件文本中的位置信息， 而仅仅把邮件看成是由若干词条构成的一个集合( 即“词袋”) 。目前，在邮件 过滤中，人们最常用向量来表示文本，即使用向量空间模型【3 6 】( v s m ) 来表示 文本。在向量空间模型中，每个邮件被看成是由一组正交词条( f ，t 2 ，乙) 所 l o 基于偏最小二乘方法的垃圾邮件过滤研究 张成的向量空间中的一个点：以力= ( w ，w 2 ，w n ) ，其中为词条t i 的权值， 表示该词条在文本中的重要程度。这样如果有m 个邮件文本，则可以构成一个 二维的mx n 阶矩阵g ，其中第f 行代表第f 个邮件文本，第，列代表第，个词条 ( 或特征) ，g u 则代表第，个词条在第f 个邮件文本中所具有的权值，大量邮件 文本中的词条( 或词典中的所有词条) 可能有几千甚至几万个，处理这种高维 矩阵的计算复杂度太大，因此必须进行降维处理，但在降维的同时又希望能把 信息的损失降到最低，因此必须找到并保留对分类贡献最大的那些特征，这个 过程采用的方法一般分为特征选择和特征抽取两大类，它是邮件过滤中非常重 要的一个环节，因为特征选择和提取的好坏将直接影响到文本分类算法的准确 率。 2 2 项的权值 在向量空间模型中，每个邮件文本d 被映射为一个项( 特征) 集( f ，t 2 ，乙) ， 于是河表示为一个特征向量：h 妒( w j ，w 2 ，) ，其中w i 为项t i 的权值，表示 该项在邮件文本中的重要程度。对于项( 特征) 集中每个项的权值的计算方法有 很多，目前，最常用的方法是t f i d f ( t e r m sf r e q u e n c yi n v e r s ed o c u m e n tf r e q u e n c e ) 函数： 厂 、 = 纸l o g ( 二+ o 0 1 ) ( 2 1 ) 刀七 其中娠表示词条改在文档西中的出现频数，表示用于特征抽取的全部训练邮 件的文档总数，n k 表示词条玖的文档频数。该函数反映了我们对于某词条重要性 的直观理解：( 1 ) 、一个单词在某邮件文本中出现的次数越多，则对邮件内容的 贡献越大；( 2 ) 、一个单词在不同邮件文本中出现的次数越多，则它区分不同邮一 件的能力越弱。在实际应用中为了消除由邮件的长度不同引起的差异，通常还会 对该函数作规范化处理，即把公式( 2 1 ) 改写为： = 吮1 。g ( 盟+ 0 0 1 ) 像 ( 2 2 ) 这样所有的权值都将落在 0 ，1 区间内，使每个文本的特征权向量都变成长 度为l 的单位向量。当然，除了t f i d f 外，还有一些其它的权值计算方法，如 概率的方法，信息论的方法等。 2 3 维数约简 硕十学位论文 在应用统计方法解决模式识别问题时，经常碰到的一个问题就是被b e l l m a n 称之为“维数灾难 的问题。在低维空间里，解析上或计算上可行的方法在应 用到5 0 维或1 0 0 维空间里时，就可能变得完全没有丝毫实际意义。为解决此问 题发展出了许多压缩特征空间维数的方法，即维数约简【3 2 ，3 7 ，3 8 1 方法。例如只要 把d 维空间中的数据投影到一条直线上，就能把d 维的数据压缩到一维。 在处理邮件过滤实际问题中，构成邮件的词汇，数量是非常多的，因此， 在全特征集建立起来之后，表示邮件文本的向量空间的维数也是非常高的，常 常可以达到几万维，同时，邮件中经常出现同义词或者近义词，而且很多邮件 的内容非常类似，因此在邮件的内容之间容易出现严重的多重相关性。即在这 些大量的特征中通常包含着许多彼此相关的特征，它们是信息的重复，是冗余 的信息，而且，过多的数据将会导致占用大量的存储空间和耗费大量的机器处 理时间；因此，如何保留那些对分类起着重要贡献的特征，去除那些冗余的特 征，以减少特征总数即如何进行降维已成为一个日益重要的研究领域。 2 3 1 特征选择 特征选择2 7 ，3 1 】：又叫独立评估法。在特征选择时一般都是利用某种评价函 数独立地对每个原始特征项进行评分，然后将它们按分值的高低排序，从中选 取若干个分值最高的特征项。现有的邮件过滤大部分采用这种方法，但是通过 这种方法选择的特征项中可能还包含着一些彼此相关的因素，也就是说并不能 很好地处理邮