（信号与信息处理专业论文）基于svm算法的垃圾邮件过滤研究与实现.pdf

摘要 摘要 垃圾邮件过滤是互联网领域内个重要的研究课题。自上世纪8 0 年代以来，随着互联网的普及，电子邮件成为互联网上最大的应用， 也成为人们工作生活最重要的交流工具之一。随之出现的垃圾邮件问 题成为互联网上的第二大公害。各国电子邮件服务商和学者纷纷尝试 各种方法进行垃圾邮件过滤。使用的方法从简单的黑、白名单方法， 到n a i v eb a y e s ，s v m 等模式识别领域的文本分类技术层出不穷。目前， 国内对垃圾邮件的过滤，尤其是中文垃圾邮件的过滤尚处于起步阶段。 除了借鉴国外的垃圾邮件过滤技术之外，中文垃圾邮件过滤问题还存 在中文分词问题。随着互联网进一步深入人们的生活，如何识别、过 滤垃圾邮件成为i t 界、邮件服务提供商迫切需要解决的问题。 本文针对国内中文垃圾邮件过滤研究缺乏语料库的问题，首先收 集了7 0 0 多封邮件建立了语料库。再在这个语料库的基础上进行研究， 将邮件文本特征向量化，利用支持向量机文本分类算法进行二值分类， 并根据邮件过滤中代价不对称问题对支持向量机算法进行了 c o s t s e n s i t i v e 改进。 支持向量机是统计学习理论的新发展，与朴素贝页斯等传统的分 类算法相比，它较好的解决了局部极小，训练样本过少引起的过学习， 以及维数灾难等问题，具有坚实的理论基础。论文首先收集了有较好 代表力的邮件集合，在进行有效的预处理、特征向量化之后，利用支 持向量机算法和代价敏感的支持向量机算法对样本进行训练和分类测 试。实验表明，该算法在中文邮件集合上取得了非常高的分类准确率。 代价敏感的支持向量机算法有效的防止了将合法邮件错分成垃圾邮 件，减小了错误代价，具有比较好的实用意义。 同时，结合中文分词，特征提取等垃圾邮件过滤问题中的关键技 术，本文设计开发了一个垃圾邮件过滤预处理系统，该系统实现了将 邮件文本表示成数字化的特征向量的功能，为本文研究提供了可靠的 实验平台，并为开发实用的垃圾邮件过滤系统奠定了基础。 关键词：垃圾邮件文本分类中文分词特征提取 支持向量机c o s t s e n s i t i v e a b s t r a c t a b s t r a c t s p a r nf i l t e r i n gi sa ni m p o r t a n ta n d n e wr e s e a r c hs u b j e c ti nt h ef i e l do f i n t e r n e t s i n c et h e9 0 s 2 0 “c o n t r a r y e - m a i l h a sb e e nt h e b i g g e s t a p p l i c a t i o ni nt h ei n t e m e t a l s o i t sb e e n o n eo ft h em o s ti m p o r t a n tt o o l s f o rc o m m u n i c a t i o ni nt h el i r eo f p e o p l e b u t ，a l lt h i si sa c c o m p a n i e dw i t h t h ea p p e a r a n c eo ft h es p a r e w h i c hi st h es e c o n d l ys e r i o u sp r o b l e mi nt h e i n t e r n e tn o w m a i ls e r v i c ep r o v i d e r sa n dr e s e a r c h e r sa r ea l l t r y i n g a v a r i e t yo fm e t h o d st of i l t e rs p a m t h e s em e t h o d si n c l u d es o m es i m p l e o n e sa sb l a c k h o l e w h i t e h o l el i s tt e c h n o l o g ya n ds o m et e c h n o l o g i e so f t e x tc l a s s i f i c a t i o n c a t e g o r y , u s i n g t h ep a t t e r nr e c o g n i t i o na r i t h m e t i co f n a j v eb a y e s ，s v me t c a tp r e s e n t ，t h er e s e a r c ha b o u ts p a r nf i l t e r i n g ， e s p e c i a l l ya b o u tt h es p a r ni nc h i n e s ef i l t e r i n g ，i s s t i l la tt h eb e g i n n i n gi n c h i n a e x c e p ta l lt h ep r o b l e m sf o r e i g nr e s e a r c he n c o u n t e r i n gi n s o a m f i l t e r i n g ，t h ec h i n e s es p a mf i l t e r i n gi sa l s of a c i n gt h ep r o b l e mo f c h i n e s e w o r ds e g m e n t a t i o n s u p p o r tv e c t o rm a c h i n ei s a ni m p r o v e m e n to ft h es t a t i s t i cl e a r n i n g t h e o r y c o m p a r i n gw i t ht h e t r a d i t i o n a ic l a s s i f i c a t i o nm e t h o d ss u c ha s na j c v e b a y e s s v mo v e r c o m e sm a n y d i f f i c u l t i e s i t c a na v o i dl o c a l m i n m u m i tc a l la l s op r o v i d et h ep r o t e c t i o no fo v e r f i n i n ga n dc u r s eo f d i m e n s i o n a l i t yi n v o k e db yt h es m a l ls a m p l e i n0 1 1 1 p a d e r , w ec o l l e c ta l o t o fm a i l sa sc o r p u s ，t h e nc l a s s i f yt h e mw i t hs v ma n dc o s t s e n s i t i v es v m a f t e rd o i n gt h ee f f i c i e n tp r e t r e a t m e n ta n dr e p r e s e n t i n gt h e mw i t hf e a t u r e v e c t o r s 0 u r e x p e r i m e n t h a s p r o v e d t h a ta r i t h m e t i cc a r ld ot h e c l a s s i f i c a t i o n a c c u r a t e l y t h e c o s t ，s e n s i t i v es v mc a np r o t e c t a g a i n s t c l a s s i f y i n gt h el e g i t i m a t em a i li n t os p a mt om i n i s ht h ee r r o rc o s t s oi th a s ap r a c t i c a lm e a n i n g i no u r p a p e r , w e a l s od e s i g na n di m p l e m e n tap r e t r e a t m e n ts y s t e mf o r s p a mf i l t e r i n g ，w h i c hi n t e g r a t e t h e t e c h n o l o g y o fc h i n e s ew o r d s e g m e n t a t i o na n df e a t m ee x a c t i o n ，t h i ss y s t e ma c c o m p l i s h e st h ef u n c t i o n o fr e p r e s e n t i n gm a i lt e x tw i t l lf e a t u r ev e c t o r s i t p r o v i d e s ar e l i a b l e e x p e r i m e n tp l a t f o r mf o rt h er e s e a r c ha n d c a l lb eab a s et h ep r a c t i c a ls p a m f i l t e r i n gs y s t e m k e yw o r d s ：s p a m ，t e x tc l a s s i f i c a t i o n ，c h i n e s ew o r ds e g m e n t a t i o n ， f e a t u r ee x t r a c t i o n ，s u p p o r tv e c t o rm a c h i n e ，c o s t s e n s i t i v e 独创性声明 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成慕。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成集，也不包含为获得北 京交通大学或其他教学机构的学位或证书两使用过的材 料。与我起工作的同志对本研究所傲的任何贡献已在 论文中作了明确的说晒并表示了谢意。 本人签名： 日期：年一月日 引言 第一章引言 1 1 研究背景 电子邮件是互联网上最大的业务，也是人们工作生活中最重要的 交流手段之一。然而随着垃圾邮件的出现，电子邮件在给人们带来便 利的同时也带来了互联网上仅次于病毒的第二大问题：垃圾邮件的 防治和过滤问题。反垃圾邮件技术成为近年来研究的热点。 1 1 1 垃圾邮件定义 1 9 9 4 年4 月1 2 日，一对居住在美国亚利桑那，专门承接移民事务 的律师夫妇写了一段p e r l 脚本的小程序，将他们的移民顾问服务广告 的电子邮件发送给大约6 0 0 0 个u s e n e t 新闻组用户。这一事件即为垃 圾邮件的起源，被称为“绿卡”事件。时至今日，垃圾邮件成为了k n t e m e t 上仅次子病毒的第二大问题，耗费了人们大量的时间和花销。 中国互联网协会在中国互联网协会反垃圾邮件规范【2 中是这 样定义垃圾邮件的： 本规范所称垃圾邮件，包括下述属性的电子邮件： ( 一) 收件人事先没有提出要求或者同意接收的广告、电子干u 物、 各种形式的宣传品等宣传性的电子邮件； ( 二) 收件人无法拒收的电子邮件； ( 三) 隐藏发件人身份、地址、标题等信息的电子邮件； ( 四) 含有虚假的信息源、发件人、路由等信息的电子邮件。 通常来说，垃圾邮件是未经同意接受的广告等信息。 1 1 2 垃圾邮件发展现状以及其危害 由于电子自日件成本低廉，垃圾邮件已经成为很多公司和组织进行 北京交通大学硕士论文 营销宣传的手段，而且有愈演愈烈的趋势。除了给电子信箱的使用者 造成很多不便，垃圾邮件还给社会造成了很大的经济损失。著名网络 安全研究机构g a d i c a t i g r o u p 3 指出，2 0 0 4 年全球企业因垃圾邮 件而引起的损失已超过2 0 5 亿美元。情况如得不到控制，2 0 0 7 年时损 失将暴涨到1 9 8 0 亿美元，到那时候，垃圾邮件将占总邮件比例的7 0 。在我国，2 0 0 3 年我国处理垃圾邮件浪费的6 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 公司的最新研究报告吵 2 0 0 5 年垃圾邮件给全球生产力造成的损失和其他反垃圾邮件的投资 将达到5 0 0 亿美元，其中仅美国公司的损失和投资将超过三分之一， 达到1 7 0 亿美元。而中国作为仅次于美国的受垃圾邮件影响的第二大 国，因垃圾邮件带来的损失同样相当严重。具体说来，垃圾邮件的危 害主要表现在以下几个方面： 1 ) 占用网络带宽，浪费网络资源，干扰邮件系统的正常运行。 当有限的网络资源和网络带宽上充斥大量的垃圾邮件时，就降低了 网络的使用效率。对邮件服务器而言，收到的垃圾邮件占用了它的磁 盘空间和网络带宽，浪费了处理时间。更严重的是，如果垃圾邮件得 不到有效控制，用户会放弃邮箱，服务商将被迫终止服务，给企业带 来很大的损失。另外，当一些用户利用邮件服务器对外发送垃圾邮件 时，该服务器会被列入黑名单而遭外部封杀。因此，邮件服务器既要 拒收来自外部的垃圾邮件，还要阻止自己的邮件用户对外发送垃圾邮 件。 引言 2 ) 浪辩用户的宝贵时闻和上阐赞用。 如攫我们每天都要花费一段时间来处理垃圾邮件，工作效率就要降 低，对熬个李会寒滋，驶渡费熬瓣凌蔓是一大氅宝囊懿璐嘉。毒关调 查显示，2 0 0 3 年，网民平均每天黹花费6 。5 分钟来处理无用的邮件， 单是下藏垃圾邮件所花费的上网赞与电话费，全年就要浪赞全球网民 辩亿荧元。 3 ) 对网络安全形成威胁。 黢垃圾邮件传播色情、反动簿吝式各样的有害信息，绘社会带来 危害。爨客们秘瘸滚子邮件系统发送数醣万计鹃垃圾部件风暴攻击爵 标，使之瘫痪、拒绝服务。垃圾邮件还可以被瘸毒利用，成为它们的 话播谂经。 1 2 反垃圾邮件技术现状 面临着垃圾邮件润题同益严熏的现状，人们开始从多方面寻找解 决方案。爨建，一麓“女g 麓运营甏”蔽立了专门瓣都门整理蟪圾自s 停， 并设立“首席垃圾邮件官”，有些邮件客户端工嶷也提供了定的垃圾 邮件过滤功能。 解决、缓解垃圾自g 件问题的方法帮手段一般有法律和蔽术两释手 段手段，下面我们简单介绍。 l 。2 。l 反缝瑗藤谗立法 反垃圾邮件立法是通过政府等部门通过法律手段来控制垃圾邮 件。例如，一旦确认某个团体或个人是垃圾邮件的发送者，郧饱就面 漆羞法德匏泰l 鞍与焚镄。或者麓建发送饪簿郄俘餐要彳寸蠢一定静“部 票”代价，以此来制约垃圾邮件发送者大规模羲复的发送邮件。针对目 北京交道大学硕j j 沦文 蓖垃圾郫僻泛滥鲢现状，反蟪圾女传立法的碍声隧益渐裹，中黧互联 弼协会覆垃掇部件协调小组2 0 0 4 年2 胃1 8 舀在北京发出关于嬲资反 垃圾邮件立法”进程的偶议【3 】，得到了众多组织机构和邮件用户的响应 【4 】。2 0 0 5 年3 嚣，政掺委员叉在嚣会上提交了热快反垃圾郎传立法黪 提案。毽立法面临着一系列的问题。首先是垃圾自g 件的概念之争，期 底什么是垃圾邮件，像窟传品、电子期刊等这类邮件是不是垃圾邮件 擐难界定，垃圾邮件发送学会想尽切办法逃脱法镎於惩鼹；蔟次是 法律的执行问题，给予什么样的处镄，两且，鲡浆缺少国际台作，即 使发现来自境夕 的垃圾邮件，也无法制裁。如果舰定发送邮件都需要 一定敷鬏努代俊，在现黔菠显然缀港褥到广大邸体建户熬试可。毽蓝， 尽管立法燎解决垃圾尚$ 件闽题最有效的方法，但艇垃圾邮件立法在目 前的情况下还无法得到实施。 l 。2 。2 蝰圾郾髂遥灌技术 近年乘，有关垃圾邮件过滤技术的研究开始逐步兴起，相关的投 入也越来越大，涌现了一大批相关产晶。如果能够从技术上解决垃圾 熬 串懑麓，餮是最理想豹了。餮蔫鬻愿熬技拳主蘩是放鼙 譬瓣发送途 径，发件人，收件人，正文等邮件储息方面识别j 奠滤垃圾邮件。下 节我们介缨目前常用的土盘圾邮件过滤技术。 l 。3 绶圾邮件过滤技术余绍 电子邮件有自身的结构特点。邮件的协议和内容格式也是由r f c ( r e q u e s t f o rc o m m e n t s ) 斡几个文档援定鲍。r f c9 2 l 口】艘定了 s m t p ( s i m p l e m a i l t r a n s f e r p r o t o c o l ，篱单自# 僻传输协议) ，是义发送 邮件的机制。r f c1 7 2 5 ( 6 t 规定了p o p 3 ( p o s to 施c ep r o t o c o l3 ，邮局协 议版本3 ) ，定义驮p o p 3 照务器收取憋馋缒极鬏。r f c8 2 2 1 q 定义酆 4 引禽 俘格式。随着电子邸件的广泛傻愆，自s 件系统不仅露要传输备种字符 集的文本内容，而且逑需要传送各种非文本文件( 例如图像文件、w o r d 文 牛、p d f 文件、z i p 文徉等) ，根据这个嚣隶，人宙3 又定义了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 m e tm a i l e 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 9 】 这亵个褥准掏成。爨裁几乎所有筑龆件强务系统都支持m l m 嚣标准。 从电子邮件的绪拳句出发，寻找垃圾邮件的特征，在发件入、收件 人、邮件头、邮件正文内容等各方面展开邮件过滤工作，是垃圾邮件 过滤卷袋爝戆基本方法。 1 3 1 服务器端和客户端的邮件过滤 先绘蹬几个概念的勰释； 1 ) m u a 。n i u a 即m a i lu s e r a g e n t ，邮件用户代理。i v i u a 是邮件 阅谈绒发送程序，如o u t l o o k ，在邮件系统中用户只与m u a 打 交避，撇将郏传系统熬复袈j 缝与爱户疆纛开。 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 决定了塞s 謦翁述霹静遗翁貉经。喾薄黪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 。 图l * l 是利用t c p i p 协议进行电子自日彳牛交按的示意图。发放者利 北京交通大学硕士论文 用m u a 写好邮件，交给发送方的m 1 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 ) 协议。 图l 一1 电子邮件系统示意图 按照邮件系统的角色结构，可以将邮件过滤分为三类： 1 ) m u a 过滤。即在用户端过滤。 2 1m t a 过滤。m t a 过滤是指m t a 在会话过程中对会话的数据进 6 引藩 行检查，对于符合过滤条件孵邮件做过滤处理。 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 m s i m a p 等。 m t a 帮m d a 遭滤都是鄄嚣黢务器溃斡遥滤，瑟m u a 过滤是稚 件用户的客户端的过滤。 从垃圾邮件过滤技术上看，舅静常用的有囱名单和黑名攀技术、 蕊弼过滤以及邮件露容过滤等。这些技术一般都同时适用予黻务器端 和客户端的邮件过滤。 王。3 。2 叁名单嗣罴名单 岛名单中的发件人发送的任何邮件都认为怒合法邮件，照名单中 的发件人发送的任何邮件都认为题垃圾邮件。这是目前电予邮件过滤 中广泛镄焉夔技寒。遴霉骰法是 | 芟集一个嚣、藏名荤羁表，露淡是逛 予邮件地址，也可以怒邮件服务器的域名、i p 地址，收到邮件时对发 件人进行实时检查。这种名单一般幽比较有信誉的组织提供，如中国 互联阚秘会(：w v , w , i s c o r 避) 襄孛黧反垃圾嚣侉联釜 ( h 如；缝燧篮垫蜓擞：q ! g ) 定期在主页上公开垃圾邮件服努器i p 地 址名单【l o 。个人也可以根据需求定义和维护自恐的黑、自名单。 l 。3 。3 设定过滤规则 设鬣些规则，只要符合这热规则的一条或几条，就认为是垃圾 部馋。这些援襄逶豢鸯； 1 ) 信喜k 分析 7 ! ! 塞鍪堕盔兰堡熹堡兰 即分析邮件头部信息梭查发件人的地址是否肖伪造。通常，一封 郝件从发件久至l 牧件人，中闻要经过好几台殷务器。每经过台撇务 器，就会襁相应的头部加入一条r e c e i v e d 的信息，按照经过的服务器 顺序由后向前添加。下面怒一个邮件头部信息例子： r e t u r n _ p a t h ：e a i 9 9 2 c a i c c w w c o m d e l i v e r e d - t o ：p a n w e n f e n g m x 3 2m a i t , s o h u c o r n r e c e i v e d f r o m t z l o w o l 3 m b k - t e x t i t ee o r a ( t z l o w o t 3 m b k - t e x t i l g 。m f 61 2 0 8 , 2 1 2 2 0 2 ) 咖s o h u m x 0 6 s o h u 。；e o s 疥x ) w i t he s m t p i d3 8 8 d 9 5 7 f a 4 ；f r i 1 6 j a n2 0 0 41 55 9 。0 3 + 0 8 0 0 ( c s r ) r e c e i v e d ：f r o m ? c i 1 2 1 8 i i 0 17 2 4 8 ) 5 s 0 谤t z i o w o 3 m b k - t e x t i i e , c o r nw i t h m i c r o s 卵s f f t s z c ( 5 5 , 1 8 7 7 1 9 7 1 9 ) , f | 6j a n2 0 0 41 3 ：0 5 ：2 5 + 0 9 0 0 r e c e i v e d f r o mm 如m ( h e l o q i a n c o m 2 0 2 1 7 0 f 6 3 6 3 j _ 妙c w 砒c o m v i t hs m t p ； 丹t1 6 j a n2 0 0 40 4 ：0 5 2 6 g m t m e s s a g e 劢! g 翟勰墼至：建始坠觑靛 f r o m ： j i e h a o p a n ” t o p a n w e n f e n 9 1 2 3 s o h u c o m ，p a n w e n f e n g s o h u c o m ，p a n w e n g e s o h u , e o m s u b j e c t ：一让迎新的钟声带蛤你我对你的声声呼唤”祝你幸+ 福。 s e n d e r ：i d e c 国s o h u c o m , x u s o h u e o m 寒 引言 m i m e v e r s i o n ：10 c o n t e n t - t y p e ：m u t t i p a r t r e l a t e d , b o u n d a r y = 二一= _ n e x t p a r t0 0 0 0 0 1 1 0 1 c 3 d b o e , e l l o b 7 2 0 ” t y p e 2 ”m u l t i p a r t a l t e r n a t i v e ” d a t en i 。1 6 j a n2 0 0 4l55 9 ：1 9 + 0 8 0 0 ( c s t ) s t a t u s ：r 0 ) ( - u i d l ：z0 7 4 2 4 0 4 3 11 3 0 4 71 6 m x 3 2m a i l s o h uc o m 邮件中的f r o m 和t o 是由发件人自己规定的，一些垃圾邮件发送 者为欺骗邮件系统和用户通常伪造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 域可以看 到“p a n w e n f e n 9 1 2 3 s o h u t o m 、p a n w e n f e n g s o h u c o m 、 p a n w e n g e s o h u c o m ”这些收件人。 3 ) 关键词精确匹配 可以定义一些反映垃圾邮件特征的关键词或短语“3 ，如“f r 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 格式正文中将大量的 无敏感内释的文字设嚣为很小而几乎滑不见的字体，而将较少的敏感 瘫套设为歪喾字镶，这黪篾豸以保证女传懿援囊效鬃，叉强为楚蓐藿 大量的正常文字，欺骗邮件过滤工鼠的检查。 l 。3 4 基于内容的蝰圾郏件_ ；童滤技术 通常，并不仅仅最綮几个固定的绽件入在发送垃圾口侔，发送者 在不断地鼹化，黑、白名单方法有局限性。规则方法的不足之处在于 甄剥都是人工指定豹，嚣簧人们不凝焱发理彝总缝、更薪，人为嚣素 比较多，些没有经验的用户可能狠雉提供有效的耀则。而且，手工 制定规则比较耗时，凇确率也受到了限制。随着时间的变化，垃圾邮 锌豹蒋征魄逛交璁，选愆户维护这磐激烈也不是一佟易事。 一个缓自然的想法鼯，对电子邮件的内容( 如芷文文本) 避行分 析，识别出垃圾邮件。避就将垃圾邮件过滤与文本分类和信息过滤联 系超寒了，褥支零势粪窝僖惠遘滤中鬻霞靛方法罨l 入垃圾部待过滤饪 务。在本文中，作者将越种自日件过滤技术称为“基于内容的垃圾邮件过 滤”或者“垃圾邮件内容过滤”。这种内容过滤技术提供了更为凇确的 女辞过滤方法，霹以鑫波获霉绞毂郄转瓣特征，势颦鬟重攘提裂缝寝蠹器 件特征的变化。 日【言 基于内容的垃圾邮件过滤技术是文本分类技术的个应用。文本 分类的任务是根据预先确定好的类别体系，将待分类文本分到相应的 类别中去。从文本分类角度来看，垃圾邮件过滤就是要求将邮件分为 垃圾、非垃圾两类中的一类，是一个二值分类问题。我们可以将电子 邮件经过预处理提取出邮件正文的文本内容，利用文本分类的算法识 别垃圾邮件，这也是目前垃圾邮件过滤技术研究的一个重要趋势。 基于内容的垃圾邮件过滤方法通常借鉴数据挖掘的思想，使用规 则学习或统计学习的算法来进行垃圾邮件过滤研究f 1 2 j 。这种方法的主 要思路是通过对大量的邮件集( 包括垃圾邮件和合法邮件) 进行学习， 训练分类算法，从而智能的、自动的识别新的邮件。应用在垃圾邮件 过滤中的学习算法很多，主要包括：规则学习类的分类算法，如 r i p p e r 2 8 1 算法，决策树算法口0 1 ，等等；统计学习类的分类算法，如朴 素贝叶斯( n a i v eb a y e s ) 算法 1 3 j 【1 4 1 5 l ，最小近邻法( k - n n ) 1 6 】【1 7 】， 支持向量机算法( s v m ) 等等。在本文中我们就研究使用s v m 算法进行垃圾邮件过滤。 基于内容的垃圾邮件过滤技术的发展尽管只有十几年的历史，但 已经广泛应用到了实用的邮件系统之中。目前，有很多支持垃圾邮件 过滤的客户端邮件工具，如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 l 5 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 本文研究的内容 本文重点磅究了基予支持匀量凝( s v m ) 霎渡黢垃圾郑馋过滤技 术，主要工作归纳如下： 对垃圾邮件过滤技术产生的背景，当前发展的檄况进行了研究， 对手楚毂邸 拳痘焉懿主蘩技术遗嚣了学习露琵较； 收集整理了大量的中文垃圾邮件和正常邮件作为研究的训练集和 测试集； 对女 譬文本羲楚毽援零避行臻究，采爝掇穰分词粒统嚣分溺麟结 合的方法逃行中文分词，分析了向量窝悯及特征礤桶选择和抽取的原 理和方法，撼融二进制的特征表示方法以及使用z i p f 溯j 降低特镢向 囊维鼗。 对s v m 算法的原理和优缺点进行深入的研究和探讨，基于谈判损 失的不对称性，使用改进的c o s t s e i l s i t i v es v m 算法对中文邮件进行 处理； 使用v c + + 构建了一个基于s v m 的垃圾自日件过滤实验系统，验证 了算法的效祭。 本文惫掇了敦下章节：第章弓| 裔，夯绍了垃圾瓣俘垂袭过滤静 研究背景和必要性，邮件过滤技术的发展现状，以及本文的主要内容； 第二章郏件文本预处理技本，介绍了中文分词算法，文本的向爨空闽 模鍪( v s m ) 戮及特征袭示和提取按零；第三牵文本分类算法，余缓 了r i p p e r , k n n ，神经网络等最常用的文本分类算法，并比较了他们 在文本分类中的应用效聚；第理章s v m 算法橛述及改进，介绍了支 持商量税s v m 算法的璎论鹜景，原瀵，并摄据垃圾郯俘过滤代 泠不 引言 平衡的特点对算法提出了改进；第五章使用改进的s v m 算法进行垃 圾邮件过滤，介绍了使用s v m 算法及改进算法进行垃圾邮件过滤的 实验，并对实验结果进行分析比较；第六章垃圾邮件过滤实验系统， 介绍如何使用v c + + 搭建垃圾邮件过滤试验系统。第七章结论，对 全文进行总结，并对今后工作提出展望。 北京交通大学硕士论文 第二耄垃圾邮件过滤预处理技术 2 1 基予内容的地圾邮件过滤基本模型 基予蠢餐夔垃毂鑫器 孛过滤潺瑟矮予文本分类勰溪莲跨，它燕对瓣 件文本进行：值分类的个特例。垃圾邮件过滤器就是一个两焱文档 分类器，它以自b 件中的文本信息为醋究对象，将已标明类别的冉睇件样 本集佟为稍练集，缮蜀冬粪i 彳孛瓣特缝模式，良该模式为基礤遴 亏：辊 器学习，彳舄划分类器。然后通过该分裟器将未知邮件分为垃圾邮件和 合法邮件。通常，邮件分类由两个阶段组成：训练阶段和分类阶段。 调练酚段侵爝已稼注瓣女俘集合湄舔分类器，褥裂箍佳参鼗；分凳酚 段将待分炎邮件输入分擞器，得到分凝结果。在每个阶段当中，都要 经历三个步骤：邮件预处理，特征提取，训练分炎。如图2 - 1 所示。 鬻2 1 文本分类模型 垃圾邮件过、滤预处理技术 邮件内容是无缝褐的自然语言，两计算橇只缆进行数字晌计算。 因此，搬邮件文本预处理，将文本内容表示成计簿机可以计算的形式， 是对郝饽使用规器学习算法进行分类鹣处理粒熬菠莉提和关键步骤。 通常自s 件过滤文本预处理包括以下几个步骤：中文分词，特绶表示， 特征选择。在本章里，我们将详细介绍以上的各项技术。 2 。2 巾文分词技术 中文分词技术是麟于自然语言处理范畴的重要研究内容，是处理 文本分擞的基础和关键技术。我们知道，与英文词汇之间有天然的空 薅箨为分隔耱不嚣，缀裁汲灌懿的鏊奉蕈位是字，悉汉语鹣激枣语义 单位是裔一个或多个字组成的词。将中文文本切分成由词衰达的最小 语义单饿是进行文本分类下一步工作的基础。随着自然语言处理技术 静发震，壤鸯三静主簧魏黪分嚣冀法：茎子字籀率莲怒兹分词方法、 基于理解的分词方法和基于统计的分词方法。 2 2 1 基于字符蹈的分词方法 这耱方法又e l 徽麓i 穰分谣方法，它是按照定斡策酪将待分褥 的汉字串与一个“充分大的”机器词典中的词祭进行配，若在词典中 找到某个字德串，则题配成功( 识剃趣一个词) 。按照扫描方向骢不同， 率匹配分诞方法可黻分为正商匹酝辅逆离匹配；谈照不同长发优先匹 配的情况，可以分为凝大( 最长) 旺配和最小( 最短) 匹配：按照是 否与词杈檬注过程楣缝合，又可以分为单纯分词方法和分词与标注楣 结合的俸纯方法。常庵的凡静梳械分词方法如下： 1 ) 碰向最大匹配法( 由左到右的方向) ； 2 ) 逆向最大匹配法( 由右到左的方向) ； 3 ) 麓少切分( 傻簿一句中弱国豹词数最，l 、) 。 北京交通大学硕= e 论文 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方 法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词 的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆 向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结 果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向最 大匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的需要。 实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过 利用各种其它的语言信息来进一步提高切分的准确率。 对机械分词进行改进的一种方法是改进扫描方式，称为特征扫描 或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征 的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分 词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起 来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又 反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。 2 2 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解【2 ”，达到识别 词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用 句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子 系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系 统可以获得有关词，句子等的句法和语义信息来对分词歧义进行判断， 即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言 知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信 息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处 在试验阶段。 垃圾邮件过滤颓处理技术 2 2 3 基于统计的分词方法 从形式上看，侧是稳定的字的组合，因此在上下文中，相邻的字 夏装掇凌懿次数越多，羲逮毒可缝秘成一个潺。嚣噩乏字与字翱邻共理 的频率馘概率能够较好的反映成词的可信度。可以对语料中相邻共现 的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字 豹互璎信惠，诗葵蒋个汉字x 、y 嚣稳邻荚臻援率。互王冕臻怠俸琨了 汉字之间结合关系的紧密程度。当紧密程度高于某一个闽憾时，便可 认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进 行统诗，不嚣要甥分溺典，嚣毳又嘲救无词典分遴法或绫诗敬词方法。 但这种方法也有一定的局限性，会经常抽出一魑共现频度高、但并不 是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的” 等，莠燕对霉焉运黪撅澍精度差，露空开镑太。实骣应薅豹绕诗分运 系统都攫使用一部攮本的分词词欺( 常用词词熙) 进行串甄配分词， 同时使用统计方法识别些新的溯，即将串频统计和串匹配结合起来， 蒺发臻涎酝分词甥分速度块、效率离翡特点，又翁磊了无蠲娶分词缝 合上下文识别生词、自动消除歧义的优点。 2 2 。4 分词中的难题及解决方法 尽鬻已经有了成熟的分谣算法，僵是中文分调的闻题还遴没有完 全解决。中文是一种十分复杂的语言，让计算机理解中文语言更是困 难。在中文分词过稷中，有两大难题至今一直没有完全突破。 1 竣义谈别 歧义是指同样的句话，可能有两种或者照多的切分方法。例如： 表面麴，嚣妥“表霹”翻“蟊的”罄是词，那么这个短语裁埘以分残 “表丽的”萃珏“衰黼的”。这种称为交叉歧义。像这种交叉妓义十分 靶衷交避亢学矮论文 常见，例如“化妆和服装”可以分成“化妆和服装”或者“化妆和 鼹装”。瘸子漫考入豹强谖去瑾簿，计算瓿矮蘧籁遒餮瘗秘个方案正 确。 交叉歧义相对组合歧义来说是还簿比较容易处理，组合歧义就必 雾疆爨鏊令訇子寒裁鼗了。爨懿，在匐予“这令f 1 怒手坏了”审，“整 手”是个谰，但在句子“请把手拿开”中，“把手”就不是个词；在 句子“将军任命了一名中将”中，“中将”是个词，但在句子“产量三 年孛蒋绻长两售”孛，“孛将”藏不孬是弱。 但避，除了交叉歧义和组合歧义，在歧义中还有一个难题，是真 歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词， 渗令应该不楚逐。鞠辩：“乒乓球接爨完了”，露苏韬分藏“乒乓稼螽 卖完了”、也可切分成“乒乓球拍粪完了”，如果没有上下文其他 的句子，恐怕谁也不知道“拍卖”在这里算不算个词。 下甏我销夯绥咒释鬻藤麴瀵狳羧义翡方法。 1 ) 用统计方法消除交叉歧义 一般而言，交集型歧义字段中伪歧义字段的切分结果不随实际语 凌熬交纯嚣变诧，莰麓字葭疼都信想羲哥以 乍密髑断。要蟊三礁切分这 种字段，酋先建立独立成词字段的频度库，对于链长为i 的交榘型歧 义字段，如“本地区”，既可以切分成“本地”+ “区”，又可以切分 残“本”+ “逡区”，这穗竣义字黢可以蔫a b c 袋表示，热鬃a b 残 词的频麟+ c 成词的频艘 a 成词的频度+ b c 成词的频度，则将a b c 切分成a b 和c ，否贝畦，切分成a 和b c 。 魏：“率遣嚣”：零) = 3 ，鳃嚣) = 6 0 0 ，f ( 本继) = o ，f ( 嚣) 一1 4 。 于是，切分为“本| i 地区”。 对于镳长为2 的交蔟型歧义字墩，如“献出趣己的爱心”，“献出 垃圾邮件过滤预处理技术 自己”可以有三种成词方法：“献出”，“出自”，“自己”。这种歧义字 段可以表示成a b c d ，则直接切分成a b i i c d 。 如：“献出自己的爱心”切分成：献出| | 自己的爱心 “洪水已经过去”切分成：洪水已经| | 过去 对于链长为3 的交集型歧义字段，如“奉献出自己的爱心”，可以 表示为a b c d e ，首先将它切分成a b c i i d e ，然后将a b c 作为链长为 1 的交集型歧义字段处理。 如：“奉献出自己的爱心”：奉献出自己的爱心 2 ) 使用词性方法消除交叉歧义 这种方法是根据汉语词语之间词性的约束和搭配关系，来确定切 分位置。如，链长为1 的交集型歧义字段中，划分为：a ( 介词) f lb c 型， 如以下各例： 从1 l 中国，中央，军事政治， 为i 队们重点主导 在f | 理论世界场院 把| | 关系手术手表手掌 但是这种处理方法存在一些盲点，如从小学、以北约、把握住等， 就无法用这种方法得到正确的切分结果。 链长为1 的交集型歧义字段中，还可以划分为：a b f fc ( 介词) 型， 如：创建存在有n 应用适用| | 于( 介词) ，这种方法也有一些无法解决 的特例，如：“从属于”既符合“a ( 介词) 0b c ”型的切分规则，也符 合“a b i lc ( 介词) ”的切分规则，此时则无法进行正确分词。 对于这些切分中的特例，可以采用特殊规则处理。 3 ) 利用汉字间的二元关系消除交叉歧义 首先定义对于有序汉字串x y ，汉字x ，y 之间的互信息由如下