（计算机应用技术专业论文）基于支持向量机的垃圾邮件过滤技术研究.pdf

西华大学硕士学位论文 基于支持向量机的垃圾邮件过滤技术研究 计算机应用技术专业 研究生杨霁琳指导教师彭宏 摘要 随着互联网的快速普及与发展，垃圾邮件的泛滥已成为一大难题，它不 仅损害了电子邮件用户的合法权益，威胁着互联网信息安全，而且每年给国 民经济造成数十亿元的巨大损失，因此研究有效的垃圾邮件过滤方法具有重 要的现实意义。 支持向量机( s v m ) 是一种建立在统计学习理论之上的机器学习方法 其最大特点是根据结构风险化最小原则，尽量提高学习机的泛化能力，即由 有限的训练样本得到小的误差仍然能够保证对独立的测试集保持小的误差 另外，由于支持向量机算法是一个凸优化问题，所以局部最优解一定是全局 最优解它已被成功地运用于许多分类问题的研究 我们注意到。目前已有机器学习方法在进行垃圾邮件过滤时，一封邮件 都是被确定地分类为垃圾邮件或者是合法邮件但实际上，针对邮件服务器 端的多个用户，一封邮件是垃圾邮件还是合法邮件，不同的用户有不同的认 识，而且还有程度的问题，因此对邮件过滤的处理应被视为不确定信息的处 理问题。 在本文的研究中，我们把这些不确定性形式化，即合法邮件被认为是邮 件样本集上的模糊概念它的模糊函数是通过聚合互联网上用户的评价信息 所获得的，而这个聚合算子采用有序加权平均算子由于每封邮件训练样本 都有一个合法邮件的模糊隶属度，因此我们采用模糊支持向量机作为分类器， 模糊支持向量机的惩罚因子是根据特定内容的错分代价所决定。这个方法的 西华大学硕士学位论文 好处就在于：( 1 ) 在邮件分类中考虑了合法邮件的不确定性，即模糊隶属度， 并给出了模糊隶属度的计算方法。( 2 ) 根据具体内容的错分代价来确定f s v m 中惩罚因子的值。 在上面这个方法中，我们注意到在训练时，合法邮件和垃圾邮件样本均 通过赋予的相对于合法邮件的隶属度，容易让人产生逻辑上的歧义。为此我 们就提出了一种改进了的基于一分类支持向量机的邮件过滤方法把模糊支 持向量机的模糊因子引入到一分类支持向量机中并同时与错分代价中的分类 模型相结合来确保合法邮件分类的正确率这样邮件过滤被认为是一个一分 类问题，我们只需训练合法邮件来建立过滤模型，垃圾邮件用来作为检测 其中邮件的不确定信息也在一分类问题中进行处理。即把合法邮件认为是邮 件样本集上的模糊概念，并且所有的邮件样本都赋予这一类合法邮件的 隶属度，以此就解决了存在的逻辑上的歧义问题 最后，我们针对这两种方法分别进行了仿真实验和相关方法的实验对比， 以其分别验证这两种方法的有效性。 关键词；邮件过滤、支持向量机、模糊支持向量机、聚合算子、一分类支持 向量机 西华大学硕士学位论文 r e s e a r c ho fe - m a i lf i l t e r i n gb a s e do ns c o m p u t e ra p p l i c a t i o nt e c h n i q u e s m a s t e r c a n d i d a t e ：y a n g j i i n s u p e r v i s o r ：p e n gh o n g w i t ht h er a p i dd e v e l o p m e n to fi n t e m c ta n di t sa p p l i c a t i o n , t h es p a mh a s b e c o m eah e a d a c h ep r o b l e mf o fi t su s e r s i td o e sh a r mt ot h el e g a lr i g h t so f e m a i c u s t o m e r s , t h r e a t e n st h ei n t e r a c ti n f o r m a t i o ns a f e t y , a n dc a u s c sg r e a tl o s s e st o n a t i o n a le c o n o m y a n n u a l l y t h e r e f o r e ，r e s e a r c ho f v a l i df i l t e r i n ge m a i i sm e t h o di s as u b j e c tw i t hg r e a tr e a l i s t i cv a l u e s u p p o r tv e c t o rm a c h i n e ( s 田i sak i n do f 删m a c h i n el e a r n i n gm e t h o d b a s e do nt h es t a t i s t i c a ll e a r n i n gt h e o r y a c c o r d i n gt os t r u c t u r er i s km i n i m i z a t i o n p r i n c i p l e ，i ti si m p o r t a n tt oi m p r o v et h eg e n e r a l i z a t i o na b i l i t yo fl e a r n i n gm a c h i n e i ft h e r eh a ss m a l le r r o rf o rl i m i t e dt r a i n i n gs a m p l e s , t h e nt h ee r l d fw o u l dk e e p s m a l lf o ri n d e p e n d e n tt e s t i n gs a m p l e s s v ma l g o r i t h mi sae o n v e xo p t i m i z a t i o n p r o b l e m , s ot h el o c a lo p t i m a ls o l u t i o ni ss u r et ob et h eg l o b a lo p t i m a ls o l u t i o n , w h i c hh a sb e e ns h o w nt op r o v i d eh i g h e rp e r f o r m a n c et h a nt r a d i t i o n a ll e a r n i n g m a c h i n e sa n dh a sb e e ni n t r o d u c e da sp o w e r f u lt o o l sf o rs o l v i n gc l a s s i f i c a t i o n p r o b l e m s w ef i n dt h a tt h ec u r r e n tm a c h i n el e a r n i n gm e t h o d sc l a s s i f yc m a i l si n t ot h e l e g i t i m a t eo rt h es p a mf o rac e r t a i n t y h o w e v e r , i np r a n c ed i f f e r e n tu s e r so f s e r v e r - s i d eh o l dd i f f e r e n to p i n i o n so fw h e t h e ra ne m a i li st h el e g i t i m a t eo rn o t , a n dt ow h a te x t e n t a sa r e s u l t , r e s e a r c ho fe m a i lf i l t e r i n gs h o u l d b ec o n s i d e r e da s d e a l i n gw i t ht h eu n c e r t a i n t i e s h i 西华大学硕士学位论文 i nt h i sp a p e r , t of o r m a l i z et h eu n c e r t a i n t y , t h el e g i t i m a t ee m a i li su n d e r s t o o d a sf u z z yc o n c e p to nas e to fe m a i ls a m p l e s ，i t sm e m b e r s h pf u n c t i o ni so b t a i n e db y a g g r e g a t i n go p i n i o n so fi n t e r a c tu s e r s , a n da g g r e g a t i o no l 弛r a t o ri so w a o p e r a t o r d u et oe m a i l 缸a i n i n gs a m p l e sw i t hm e m b e r s h i pd e g r e e so ft h el e g i f u n a t ee m a i l , f u z z ys u p p o r tv c c t o i m a c h i n ef f s v m ) i sa d o p t e dt oc l a r i f ye m a i l s , a n dl 把n a l t y f a c t o ro ff s v mi sd e c i d e db yc o n t e n t - s p e c i f i cm i s c l a s s i f i c a t i o nc o s t s t h e a d v a n t a g e so fo u rm e t h o da r e ：1 ) u n c e r t a i n t yo ft h el e g i t i m a t ee m a n , i c ， m e m b e r s h i pd e g r e e ，i sc o n s i d e r e di nc l a s s i f y i n ge m a i l s , a n dam e t h o dt oo b t a i n m e m b e r s h i pd e g r e ei sg i v e n ；2 ) c o n t e n t - s p e c i f i cm i s c l a s s i f i c a t i o nc o s t si su s e dt o d e c i d ep e n a l t yf a c t o ro ff s v m i na d d i t i o n , l e g i t i m a t ea n ds p a r es a m p l e s 玳e n d o w e dw i t ht h ef u z z ya t t i t u d e o fl e g i t i m a t ei nt h et r a i n i n gm o d e li na l x f c cf i l t e r i n gm e t h o d , w h i c hp r o b a b l y b r i n g sl o g i c a la m b i g u i t y t h e r e f o r ew ep r e s e n ta ni m p r o v a b l ef i l t e r i n ge m a i l m e t h o dw h i c hb a s e do i lo n e - c l a s ss u p p o r tv e c k hm a c h i n e so - s v 鸠f i r s t l y , f u z z yf a c t o ri nf s v m , i e ，f u z z ya t t i t u d eo fe m a i ls a m p l e si s 姗o d u c e d i - s v m i nt h i sw a y , u n c e r t a i n t i e so fe m a i la p r o c e s st l l n o u g ho n ec l a s s i f i c a t i o n p r i n c i p l e m e a n w h i l et h ep e n a l t yf a c t o rm o d e lo fl e g i t i m a t ei ns p e c i a lc o n t e n t m i s c l a s s i f i c a f i o nc o s t si si n t e g r a t e di n t o1 - s v mf o ri n s u r i n ge f f e c t i v e n e s so f e m a i lf i l t e r i n g w e j u s tr e q u i r el e g i t i m a t es a m p l e st os e tu pf i l t e r i n gm o d e la n dt h e s p a r ei sd e t e c t e di nt h em e t h o d t h el e g i t i m a t e 锄a i li su n d e r s t o o da sf u r y c o n c e p t 0 1 1as e to fe m a i ls a m p l e s a n da l lo fe m a i ls a m p l e sa e n d o w e dw i t ho n e c l a s sf h z 巧a t t i t l i d t - l c g i t i m a t ea t t i t u d e t h em e t h o dn ol o n g e rh a sl o g i c ：d a m b i g u i t y f i n a l l y , s i m u l a t i v ee x p e r i m e n t sa r ec o n d u c t e df o rt h ee f f e c t i v e n e s sa n d h u m a n c o n s i s t e n to f o u rt w om e t h o d sr e s p e c t i v e l y k e y w o r d s ：e m a i lf i l t e r i n g , s v m , f s v m , o w a , 1 - s v m i v 西华大学硕士学位论文 申明 本学位论文是在导师的指导下完成的研究工作和取得的研究成果除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包括为西华大学或其他教育机构的学位或证书而使用过的 材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。论文成果归西华大学所有，特此申明 作者签名书埤砩札t 7 年月占日 新微杉 6 诈二月多日 | 西华大学硕士学位论文 1 绪论 1 1 研究背景和意义 2 0 0 6 年1 月中国互联网络信息中心( c m 町c ) 发布了“第十七次中国互联 网络发展状况统计报告”，显示我国上网用户总数突破1 亿，为1 1 1 亿人1 1 1 这已表明i n t e r a c t 正在以极其快的速度普及到我们的生活当中，网络已成为 一种人们获取信息和传递信息的重要手段。其中电子邮件更以方便、快捷、 高效的优势成为最受欢迎的网络功能之一据统计我国互联网上网用户中 8 4 的人经常使用电子邮箱，每位用户平均拥有e - m a i l 账号1 5 个，电子邮 件成为人们日常生活中信息交流的重要手段之一【2 1 但随之而来的垃圾邮件 也越来越猖獗。 垃圾邮件诞生予1 9 7 4 年i 习，主要有两类，一类是名且繁多的商业广告， 另一类是非法团体为其政治、经济等且的而进行的“网络宣传”普通意义上 的垃圾邮件是指未经主动请求的大量的电子邮件在英文中称为 s p a m u b e ( u n s o f i c i t e db u l ke 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 ) 。具 体的讲垃圾邮件包括：收件人事先没有提出要求或者同意接收的广告、电子 刊物、各种形式的宣传品等宣传性的电子邮件：收件人无法拒收的电子邮件； 隐藏发件人身份、地址、标题等信息的电子邮件；含有虚假的信息源、发件 人、路由等信息的电子邮件垃圾邮件的特点有：发件人地址随机变化；邮件 主题随机变化：伪造邮件头干扰信息；信体内容随机变化；正文以图片方式 显示，难以识别；垃圾邮件在不同的时段、范围内的传播内容不一样等等 垃圾邮件的另外一个特征是它被大量的发送，被数百上千万的发送出去 自从2 0 0 3 年垃圾邮件的大肆泛滥以来，它现在已成为互联网上最证人头 疼的一件事据中国互联网协会发布的最新统计数字，中国互联网用户收到 的垃圾邮件占所收邮件总数的6 3 9 7 ，平均每天收到的垃圾邮件数量超过 2 7 封，并且用户平均每周要花1 3 1 5 分钟处理垃圾邮件i n 垃圾邮件的主要危害可归纳为以下六点唧： 西华大学硕士学位论文 1 占用大量传输、存储和运算资源，造成邮件服务器拥堵，降低了网络 的运行效率，严重影响正常的邮件服务； 2 我国开始被其他国家视为垃圾邮件的温床，许多ip 地址有遭受封杀 的危险，长期下去可能使我国成为“信息孤岛”； 3 垃圾邮件以其数量多、反复性、强制性、欺骗性、不健康性和传播速 度快等特点，严重干扰用户的正常生活，侵犯收件人的隐私权和信箱空问， 并耗费收件人的时间、精力、金钱； 4 垃圾邮件一旦被黑客利用，危害更大。2 0 0 0 年2 月，黑客侵入并控制 了一些高带宽的网站，集中众多服务器的带宽能力，然后用数以亿计的垃圾 邮件发动猛烈攻击，造成都分网站瘫痪； 5 严重影响电子邮件服务商的形象收到垃圾邮件的用户可能会因为服 务商没有建立完善的垃圾邮件过滤机制，而转向其他服务商； 6 妖言惑众、骗人钱财、传播色情、反动等内容的垃圾邮件，已经对现 实社会造成危害。 垃圾邮件的泛滥，不仅耗费网络资源，而且对企业正常运作和用户的正 常工作造成严重干扰，对国家利益造成严重损失经过综合计算，垃圾邮件 给国民经济每年造成印6 9 亿元人民币的损失i 】因此对于垃圾邮件过滤方法 的研究已成为刻不容缓的重要课题，具有深刻的意义 1 2 垃圾邮件过滤技术的研究现状 在日益泛滥的垃圾邮件给我们的互联网带来麻烦的同时，垃圾邮件过滤 技术的研究也在如火如荼的展开，专家和研究者提出了各种垃圾邮件的过滤 方法。从邮件过滤的执行方法来说大致可以分为以下三类：一是基于口地址 的方式，根据发送方的邮件地址或口地址，拒绝接收不正当的邮件攻击；二 是基于手工规则的过滤，手工设置一些规则，只要符合这些规则的一条或几 条，就认为是垃圾邮件；三是基于邮件内容的过滤，通过对邮件内容进行识 别和检查，来决定是否接收邮件嘲另外随着邮件过滤技术的发展还出现了 一些其他的方法 2 西华大学硕士学位论文 1 2 1 基于口地址的垃圾邮件过滤方法 在垃圾邮件过滤技术中发展最早且应用最普遍的就是基于口地址的过 滤技术为了有效地拒绝来自于恶意的垃圾邮件来源站点和邮件来源站点所 发来的垃圾邮件，最直接和有效的办法就是拒绝该来源站点的连接虽然从 理论上说，这样也有可能会拒绝掉来自该站点的正常邮件，从而造成邮件不 能正常的投递，但是通过专家长时问的实践有充分的理由支持这样做 基于口地址的过滤之所以是使用最广泛的一种过滤技术，就在于它几乎 在各个层次都可以进行其主要技术有白名单过滤、黑名单过滤和反向域名 验证等技术最为典型的是黑白名单过滤技术 自名单过滤方法是由h a l l l 6 1 在1 9 9 8 年提出，就是在邮件过滤系统中维 持一张白名单表，其中收录了用户许可的邮件地址，当收到的邮件其发送者 在用户的白名单表中，该邮件就被判定为正常邮件如果不再其中，就会产 生一个特殊的质询发给相应的发送者，并且等待发送者的答复，以便将其加 入到自名单中，如果邮件发送者能正确给出答复，就将新的发送者加入到白 名单中【7 1 但白名单技术使得合法邮件发送者和邮件服务器带来了许多额外 的负担，而且会有较高的误判率 黑名单过滤阐，即利用国内外有很多组织提供垃圾邮件制造者或策源地 的“黑名单”，服务器接收到邮件后，先到“黑名单”上去查找。如果邮件来自“黑 名单”中的地址，则认为该由日件是垃圾邮件目前有专门的反垃圾邮件网站或 r r 部门定期提供实时黑名单表r b l ( r e a lb l a c kl i s t ) ，如美国的“邮件滥用预 防系统( m a p s ) 当然对于黑名单和白名单也常常结合起来使用，这样可以 进行动态的更新，但它的误判率太高 在2 0 0 3 年，杨锋【9 1 等人提出了一个基于d n sb l o c k l i s t 的反垃圾邮件系 统，他利用d n s 技术、o p e nr e l a y ( 开放性中继器) 测试技术，以及策略分级 过滤规则技术，实现了国内教育网的垃圾邮件过滤 反向d n s 查询1 1 0 l 是对发送者的口地址进行逆向域名解析通过d n s 查询判断发送者的球与其声明的名字是否一致但反向d n s 查询需要耗费 大量的系统和网络资源。当前t o m 的邮箱反向d n s 的记录是1 6 3 n e t ，但这 种方法在国内使用非常有局限性。 3 西华大学硕士学位论文 1 2 2 基于手工规则的垃圾邮件过滤方法 手工设置一些规则，只要符合这些规则的一条或几条，就认为是垃圾邮 件基于手工规则的垃圾邮件过滤技术主要有以下几种： 1 信头分析：一封邮件发送和接受的过程要经过多台服务器，每经过一 台服务器，就会在相应的头部加入一条r e c e i v e d 的信息，按照经过的服务器 顺序由后向前添加【1 1 l 。信头分析的目的是识别含有伪造内容的信头，从而过 滤掉垃圾邮件主要关注是否含有伪造机器的名字，或信头中是否含有伪造 的r e c e i v e d 信息l ( 1 ) 如果是发件人伪造机器的名字，当它在s m r p 对话的h e l d 命令后 自称为另外一个名字时，此时收件方邮件服务器就会生成另一种信头这就 很容易看出收件方服务器记录的口地址以及反向解析的域名同发件人宣称 的域名不同。 ( 2 ) 如果是信头中含有伪造的r e c e i v e d 信息，则在分析信头时一般是根 据r e c e i v e d 行的信息依次查找出信件的路由信息，直至找到第一个邮件服务 器于是，某些制造垃圾邮件的人可能就会有意地在信件中加入一些无关的 r e x ：e i v e d 行，企图掩盖真实的邮件信息由于信件一旦离开主机，发件人就 无法继续控制该信件，邮件服务器的路由信息是依次加在信头顶部的，因此 伪造的r e c e i v e d 行一定在底部从上到下追踪邮件的f r o m 和b y 的信息，以 及口的路由信息，一般比较容易判断出伪造的r e c e i v e d 行l 坷 2 基于关键字匹配的垃圾邮件过滤；一种过滤方法是对邮件的头部进行 检查，根据用户设定的不受欢迎的主题，自动将其过滤掉；另一种过滤方法 针对邮件的内容进行过滤，根据用户设定的一些反映垃圾邮件的关键词，当 在邮件正文中匹配到其中的若干条时，则将其过滤掉c z 4 7 基于关键词匹配 的过滤技术，是一种较为有效的过滤技术，但有时会对正常邮件进行误处理。 因为那些在垃圾邮件中出现的关键词，在正常邮件中也可能出现旧 3 群发过滤：群发的垃圾邮件表现为以下两种情况：一是在一段时间内 收到同一源头大量的邮件：一是收到从不同地址发送过来的大量内容基本相 同的邮件。群发的垃圾邮件主要特点是数量极大，而来源又相对集中在这 里，“源”不仅指信件的初始源地址，而且包括邮件路径，从源服务器到目标 西华大学硕士学位论文 服务器所经过的中继邮件服务器( 如果有的话) 相对集中，因为在同一段时间 内可供垃圾邮件组织利用的邮件服务器不是非常多，所以也可以说同一批的 垃圾邮件的路径相对集中i 埘应对的措施一般是将群发垃圾邮件的口地址列 入黑名单，拒收他们发来的电子邮件 1 2 3 基于内容的垃圾邮件过滤方法 对于不同的用户来说黑自名单是不一样的；而手工设置过滤规则，普通 用户又难于胜任；群发过滤的能力也有限，这些技术都存在很大的局限性 而基于内容的垃圾邮件过滤技术就成为了目前的研究热点 1 4 1 5 , l s l 基于内容的垃圾邮件过滤技术是通过分析邮件的内容，来过滤垃圾邮件 的一种技术，相对于前几种基本技术，它的准确率更高，是当前电子邮件过 滤技术的主流技术。目前基于内容的垃圾邮件过滤主要包括基于规则的方法 和基于概率统计的方法和其它一些新的过滤方法无论是何种方法都是通过 已有的训练集合( 正例+ 反例) 训练出相应的垃圾邮件规则，然后将规则应用 到新的邮件判定中去在实际系统中可能还会加入人机交互过程通过用户 对判定结果的认可与否对已有的垃圾邮件规则进行更耕 1 基于规则的邮件过滤 这里所说的规则与上节所讲的规则是不一样的，上节所讲的主要指手工 建立的规则，并不分析邮件的内容，这里所说的规则是指通过训练得到的显 式规则规则学习的过程实际上是归纳总结出一定的规律的过程其方法的 主要优点是可以生成人类理解的规则，缺点是在规律性不明显的应用领域效 果较差 ( 1 ) r i p p e r ：1 9 9 6 年，c o h e n 1 7 1 利用r i p p e r 算法，设计了一种基于 规则的邮件过滤器。该算法先学习训练集中的所有正例，不断地向一初始集 为空的规则集中加入规则，形成一个正例的规则集，然后利用所有反例不断 地对规则集中的关键字加入约束条件，最后用这个包含了约束条件的规则集 来做出决策其优点是它所具有的先验知识易于理解和更新，但对大量的训 练数据和存在噪声时效果不好。 西华大学硕士学位论文 ( 2 ) 决策树：该方法是著名的规则方法之一2 0 0 0 年，c a r t c r a s 1 s l 提出 决策树算法用于邮件过滤，但对于基于决策树的方法，得到的查全率和准确 率不太高，因此后来d e s o u z a 1 9 j 进行改进，提出决策树的c 5 o 算法来建立决 策树形式的分类规则 ( 3 ) b o o s t i n g 方法：2 0 0 1 年c a t r c r a s 将b 0 0 s 伽一加】方法引入到垃圾邮 件过滤，获得了较高的性能b o o s t i n g 方法并不是一种特定的学习方法，一 般结合决策树等学习方法使用，是在已有学习方法基础上的进行“投票”的技 术它通过对已有的分类器进行加权求和得到最终的分类器，这里的每个分 类器称为弱规则或者弱假设，加权求和以后的分类器称为强规则b o o s t i n g 方法的最主要缺点在于训练速度较慢。 ( 4 ) 粗糙集( r o u g hs e t s ) 方法：r o u g hs e t s 理论是由p a w l a k 于上世纪 年代提出的一种研究不完整，不确定知识和数据的表达、学习、归纳的理 论方法。2 0 0 3 年，于洪、李志君等1 2 1 提出了基于粗糙集的邮件过滤系统模型。 它结合粗糙集对决策表进行分析形成决策属性，不同用户采用不同的属性值 来寻求规则。 2 基于概率统计的过滤方法 基于概率统计的方法是指根据统计理论，先对己分类的邮件训练样本进 行学习，提取出能表征各类邮件的特征向量及特征值，再将根据这些值对以 后的邮件进行计算，由此来完成分类过滤本质上，基于统计的方法可以看 成规则方法的一种推广，只不过统计方法中得到的规则是一种不被人轻易理 解的“隐式规则” ( 1 ) k 最邻近方法( k n n ) ：是常用的基于实例的方法a n d r o u t s o p o u l o s l 2 2 1 把k 邻近算法应用到了邮件过滤中，通过计算待分类邮件的距离来找出最相 近的k 个邮件，从而得出新邮件的类别 ( 2 ) r o c c h i o 方法：1 9 9 9 年，d u r c k 护j 把r o c c h i o 算法引入邮件过滤并 同s v m 、r i p p e r 等算法比较该算法使用两类向量的加权差来计算两类向量 的类别向量，通过对新邮件计算其与这两个类别向量的距离来判断归属于哪 一类。该算法的过滤较快，但过滤效果不太理想 ( 3 ) 基于质心的方法：2 0 0 2 年s o o n t h o m p h i s a jn 2 4 1 等人提出基于质心 算法的邮件分类，所谓质心算法是用质心向量总结了每一类邮件的普遍特征， 6 西华大学硕士学位论文 其中突出的维将反映在这些词出现频繁的邮件中，并通过使用简单函数说明 词之间的依赖性来进行比值计算。它对邮件特征的总结要比k 邻近方法执行 的更好它减少了分类错误的可能性，但对于把正常邮件过滤为垃圾邮件的 比率还是有待于提高 ， ( 4 ) 贝叶斯( b a y c s ) 方法：是当前使用最多的统计方法它是以著名 数学家托马斯贝叶斯命名，一种基于概率分析的可能性推论理论在1 9 9 8 年s a h a m im 瞄媳出用贝叶斯方法来过滤邮件。它是一种在条件独立假设下的 简化贝叶斯分类方法。通过贝叶斯的条件概率表c p t 来得到相关系数，若有： p ( c ，不感兴趣邮件”i x - - - x ) p ( c - “感兴趣邮件”i x ：习【) ，则邮件为用户感兴趣 邮件，否则为不感兴趣邮件。但是这种方法是基于最小错误率的决策方式， 当合法邮件被错分为垃圾邮件的可能性比较大时，会给用户带来较大的损失 1 9 9 8 年r c n n i c t m 在贝叶斯方法的基础上建立了一个邮件过滤的机器学习应 用系统i f l c 这种方法对于邮件的分类的速度很快，而且可以对其进行动态 的调整，但就如前面所说的误分率仍然比较高，用户还需要检测邮件中是否 存在错误分类。p a u lg r a m h a m 口l 于2 0 0 2 年提出了建立垃圾邮件和非垃圾邮 件单词的贝叶斯概率模型同年国内的石霞军网提出了基于最小风险的贝叶 斯邮件过滤算法，它既考虑后验概率的大小来傲决策也把是否损失最小作为 决策依据来考虑，虽然对分类的查全率有所提高，但垃圾邮件的招回率却有 所下降。2 0 0 3 年，蔡立军渊把遗传算法和贝叶斯相结合用于邮件过滤 ( 5 ) 支持向量机( s v m ) 方法：是统计学习理论p o ( s t a t i s t i c a lk m i n g t h e o r y , s l t ) 中最年轻的分支，由v a p n i kvn 博士提出在1 9 9 9 年d l m c r h 和v a p n i kvn 吲提出了电子邮件系统的支持向量机模型该方法从样本集 中选择一组特征子集，使得对于特征子集的划分等价于整个样本集的划分 它减少了训练样本数，具有很好的泛化能力后来b r u t l a g 和m c 羽3 l 】把线 性支持向量机用于邮件分类对其加以改进当前对于基于支持向量机的邮件 过滤还处于初步阶段，对于数据量过大的数据集，s v m 训练时间过长，并且 在邮件的分类过滤中垃圾邮件具有自身的一些特点，如错分合法邮件比错分 垃圾邮件要严重很多为此在2 0 0 4 年a l e k s a n d e r 3 2 等人提出了一种考虑特 定内容错分代价的s v m 邮件过滤算法，但无论怎样，s v m 具有其它方法无法 比拟的优点，如结构风险最小化、全局唯一解、在非线性和高维模式中也表 7 西华大学硕士学位论文 现出很好效果，是邮件过滤中很有前途的一种方法i 捌。 1 2 4 其他的垃圾邮件过滤方法 1 9 9 8 年h a l l 3 4 j 提出基于a g e n t 的邮件分类方法a g e n t 是将推理和表示 相结合的智能体以后许多人在其上面a g e n t 加以改进提出了基于多a g e n t 的邮件过滤系统。例如：刘贵全1 3 5 使用一种基于a g e n t 技术的邮件自动处理 系统，将邮件按重要程度定义为7 级，采用夹角余弦方法对邮件进行处理。 但由于解析a g e n t 对语言解析能力的限制，它制约了邮件过滤的精确化，但 随着语言解析能力的提高，这个方法可进一步完善 另外，还有文件类型过滤和邮件大小过滤，即对邮件的附件的接收和发 送进行控制和对超过一定字节的信件进行过滤目前针对这两种过滤方式的 技术还是不太实用，所以通常还是用人工的方法 最近还有一种基于p k i 3 6 1 的方式，它通过p k i 对邮件发送者进行验证， 对邮件信息进行加密，对收信人实现防抵赖机制域的所有者生成公钥和私 钥，私钥用于所有发送邮件的签名公钥通过d n s 发布授权用户可以的邮 件可以通过邮件服务器自动产生邮件的数字签名接收时，如果没有数字签 名，或签名失败，收件方可以拒绝、标记或隔离邮件 另外随着邮件过滤技术的发展除了上面介绍的方法外，还出现了一些其 他的方法 3 7 m q ，在这儿就不在一一详细介绍 1 3 支持向量机理论 基于内容的邮件过滤方法实质就是一个分类问题。在上面提到的方法中， 常用的贝叶斯方法、k 邻近等算法等传统的机器学习方法都是基于经验风险 最小化的，理论上讲，过滤器推广性能一般较差 支持向量机( s u p p o r tv e c t o rm a c h i n e 。s v m ) 是在统计学习理论【拇删基础 上发展起来的，是基于结构风险最小化原理的一种新的模式识别方法具有 8 西华大学硕士学位论文 小样本，良好的推广性能，全局最优等特点，已被成功地运用于许多分类问 题的研究如：语音识别，字符识别，目标检测，网络安全等。在垃圾邮件 过滤中，s v m 方法的运用研究也引起了一些研究者的兴趣【2 3 , 3 1 , 3 2 4 1 1 1 3 i 统计学习理论 统计学习理论是研究利用经验数据进行机器学习的一种理论，属 于计算机科学、模式识别和应用统计学相交叉与结合的范畴。基本内 容诞生于2 0 世纪6 0 7 0 年代，到9 0 年代中期发展得比较成熟并受到世界机 器学习界的广泛重视 1 经验风险最小化： 学习的目的是根据给定的训练样本求系统输入输出之间的依赖关系机 器学习问题就是根据n 个独立同分布的观测样本：“，y ，) ， ：，y ：) ，( k j ) ，) ， 在一组函数 f ( x w ) ) 中来寻求一个最优的函数啦w 觇对x 与y 的关系进行估 计，使期望风险： 胄( 曲- f l ( ) ，( b w ) ) d f ( x ，y ) ( 1 - 1 ) ， 最小 在传统的学习方法中，采用了经验风险最小化( e r m ) 准则，即用样本 定义经验风险： k ( 叻一；砉l ，“，嗍 ( i - 2 ) 经验风险最小化原则在有限样本时是不合理的，需要同时最小化经验风 险和置信范围实际上，传统方法中选择学习模型和算法的过程就是选择置 信范围的过程，如果模型比较适合现有的训练样本( 相当于h n 值适当) ， 则可以取得比较好的效果在模式识别中选定了一种分类器形式就确定了学 习机器的v c 维实际上这种作法是首先通过选择模型确定m ，在固定m 的 条件下，通过经验风险最小化来求最小风险比如在神经网络中，需要根据 问题和样本的具体情况选择不同的网络结构( 对应不嗣的v c 维) ，然后进行 经验风险最小化。由于缺乏理论指导，这种选择只能依赖先验知识和经验， 9 西华大学硕士学位论文 而且如果选择的v c 维较大，往往会出现过学习的现象 2 v c 维 统计学习理论中，一个重要的概念是v c 维( v a p n i k - c h e r v o n e n k i s d i m e n s i o n ) 它的直观定义是 4 2 1 ：对一个指示函数集，如果存在h 个样本能 够被函数集里的函数按照所有可能的2 h 种形式分开，则称为函数集能够把h 个样本打散。函数集的v c 维就是它能打散的最大样本数目h 如果对任意 数目的样本都有函数能将它打散，则函数集的v c 维是无穷大。有界实函数 的v c 维可以通过一定的阀值将它转化为指示函数来定义 v c 维反映了函数集的复杂性或学习能力。v c 维越大则机器学习越复杂 但对于给定的学习函数集，如何计算v c 维是当前统计学习中有待研究的问 题。 3 推广能力 统计学习理论系统地研究了对于各种类型的函数集。经验风险和实际风 险之间的关系，即推广性的界对于模式识别问题( 当然还包括回归问题和 密度估计问题) ，其结论是：对指示函数集中的所有函数( 包括使用经验风 险最小的函数) ，经验风险j t 一( 叻和实际风险r ( w ) 之间以至少l - r 的概率 满足如下关系i 柏1 ： r ( 叻r 栩( 叻+ h ( 1 n ( 2 n h ) + 1 ) - i n ( t 4 ) ( 1 - 3 ) -， 其中h 是函数集的v c 维，n 是样本数 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是 经验风险c i v i l 练误差) ，另一部分称作置信范围，它和学习机器的v c 维及 训练样本数有关它表明，在有限样本下，学习机器的v c 维越高，那么置 信范围越大，导致真实风险与经验风险之间可能的差别越大这就是为什么 会出现过学习现象的原因机器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好 的推广性 需要指出，推广性的界是对于最坏情况的结论，在很多情况下是宽松的， 尤其当v c 维较高时更是如此( 文献【4 0 】指出当h 恤，o 3 7 时这个界肯定是松 弛的，v c 维无穷大时这个晃就不再成立) 而且这种界只在对同一类学习 1 0 西华大学硕士学位论文 函数进行比较时有效，可以指导我们从函数集中选择最优的函数，在不同函 数集之问比较却不一定成立 4 结构风险最小化 为了克服传统方法的不足，我们要权衡( 1 3 ) 式中的经验风险和置信范围 的大小，使其共同趋于最小。统计学习理论提出的结构风险最小化原则解决 了这个问题，它提出了这样一种策略：首先把函数集s - f 伍w ) w o 分解 为一个函数子集序列( 或叫子集结构) ， s l c s 2c c s t c c s 使各子集能够按照垂的大小排列，也就是按照v c 维的大小排列，即 h i 2 h 2 2 = k = 这样在同一子集中置信范围相同，在每一个子集中寻找最小经验风险，选择 最小经验风险和置信范围之和最小的子集，就可以达到期望风险最小( 如图 1 1 ) ，这个子集中使经验风险最小的函数就是所要求的函数这种思想称作 有序风险最小化或结构风险最小化( s t r u c t u r a lr i s km i n i m i z a t i o n ) ，即s r m 准则。 图1 1 中给出了真实风险、经验风险与置信范围的函数变化曲线。随着h 的增加，经验风险r ，( w ) 递减 风险欠学习过学习 h g u r c1 1s t r u c t u r a lr i s km i n i m i z a t i o ns k e t c hm a p 图l - 1 有序风险最小化示意图 1 1 西华大学硕士学位论文 这是因为当h 增加时，根据v c 维的定义，对应的函数集合的描述能力 增加，学习机器的学习能力随之增强，可以使有限样本的经验风险很快地收 敛，甚至于变为o ；根据式( 1 - 3 ) ，置信范围西随着h 的增加而增加；这样， 真实风险r ( a ) 是一个凹型曲线所以，要获得最小的真实风险，就需要折衷 考虑经验风险与置信风险的取值。 根据这一分析我们可以得到两种运用结构风险最小化原理来构造学习 机器的思路： ( 1 ) 给定了一个函数集合，按照上面的方法来组织一个嵌套的函数结构， 在每个子集中求取最小经验风险，然后选择经验风险与置信风险之和最小的 子集。当子集数日较大的时候，此方法较为费时，甚至于不可行 ( 2 ) 构造函数集合的某种结构，使得在其中的各函数予集均可以取得最 小的经验风险( 例如，使得训练误差为0 ) ，然后在这些子集中选择适当的子 集使得置信风险最小，则相应的函数子集中使得经验风险最小的函数就是所 求解的最优函数支持向量机方法实际上就是这种思想的具体实现 1 3 2 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e s ) 是统计学习理论中最年轻的内容， 也是最实用的部分其核心内容是在1 9 9 2 到1 9 9 5 年提出的，目前仍处在不 断发展阶段m 支持向量机是v a p n i l 【l 删等人根据统计学习理论提出的一种新的机器学 习方法，它以结构风险最小化原则为理论基础，通过适当选择函数子集中的 判别函数使学习机的实际风险达到最小，保证了通过有限训练样本得到的小 误差分类器对独立测试集的测试误差仍然最小，得到一个具有最优分类能力 和推广泛化能力的学习机。该方法从样本集中选择一组特征集，使得对于特 征集的划分等价于对整个样本集的分割，这组特征集称为支持