（计算机软件与理论专业论文）垃圾邮件过滤技术研究.pdf

西华大学硕士学位( 毕业) 论文 垃圾邮件过滤技术研究 计算机软件与理论专业 研究生唐敏指导教师彭宏 摘要 随着i n t e r n e t 的发展，电子邮件已经成为人们重要的交流方式，许多重 要的信函也会通过电子邮件方式传送。但是，随着电子邮件的不断发展，这时 垃圾邮件也开始泛滥。垃圾邮件使得用户必须花费大量的时间和精力来处理它 们，并且由于还占用了大量的带宽和存储资源，造成了资源的浪费。因此，研 究垃圾邮件的过滤技术具有重要的现实意义。 当前解决垃圾邮件过滤问题有很多的方法和途径，其中基于内容的过滤就 是一个主要方法。而在基于内容的过滤方法中当前应用的晟为广泛是基于贝叶 斯的垃圾邮件过滤方法，但同基于支持向量机的邮件过滤方法相比，它的正确 率和刈凹率却相刑较低。 支持向量机是从统计学习理论上发展起来的一种新颖的模式识别方法，有 着其他机器学习方法无法比拟的优势，诸如：结构风险最小化、全局唯一解、 良好的推广能力、在非线性和高维模式中也表现出很好效果。但目前用于邮件 过滤的支持向量机方法中采用的是传统的支持向量机算法，在需要处理大量的 邮件数据的情况下，存在训练时间过长，精度和准确度随时间的推移健壮性不 太理想等问题；并且在实际应用中，由于收集合法邮件较垃圾邮件困难，这样 使得收集的训练集中垃圾邮件类与合法邮件类样本之间出现不平衡，而传统的 支持向量机在处理不平衡问题时，会造成分类面靠近训练样本较少的一类的问 题；传统支持向量机在处理分类问题时，要求训练集中的每个训练样本都应明 确归属一类，当出现训练样本不能明确地归属于类时它就无能为力，并且对 于干扰分类的噪声点的区分效果不是很理想，使得噪声点严重地影响分类的准 西华大学硕士学位( 毕业) 论文 确性。 针对支持向量机的以上缺点，本文提出了两种用于邮件过滤的支持向量机 方法：并行分层支持向量机邮件过滤方法和模糊支持向量机邮件过滤方法。 本文的研究工作主要包括如下两个方面： 第一，提出了并行分层支持向量机邮件过滤方法。其主要思想是将邮件样 本集划分为几个子样本集，采用分层形式在每一层并行地训练支持向量机。在 分层筛选中通过使用交叉合并方法来达到缩短训练时间又不降低邮件的分类 能力。而且采用的交叉合并方法同时又可以避免出现两类训练样本数量的不平 衡而导致分类信息的损失。在该邮件过滤方法中，同时使用主成分分析对邮件 的特征维数进行约简，来共同减少过滤器训练和测试时间。仿真实验表明：算 法在减少时间的同时也有较好的准确率和召回率。 第二，针对传统支持向量机无法处理当出现训练样本不能明确地归属一类 的情形，提出了基于误分损失的模糊支持向量机邮件过滤方法。在传统的支持 向量机方法中参数c 是固定的，也就是说，无论是合法邮件或是垃圾邮件，在 训练时，都给予平等地对待。但在邮件过滤中，错分合法邮件比错分垃圾邮件 更严重，通过在模糊支持向量机中引入不同邮件类的误分损失，确保合法邮件 尽可能不被错分。提出了一种通过计算邮件样本的分布密度的方法来解决邮件 样本的隶属度问题，这种方法同时可以较好地减轻噪声数据对支持向量机的影 响。对比实验表明，算法进一步提高了邮件过滤系统的正确率，可以改善过滤 器的性能。 关键词：垃圾邮件、主成分分析、支持向量机、模糊支持向量机、误分损失 i i 西华大学硕士学位( 毕业) 论文 t h er e s e a r c ho fs p a me m a il f il t e r i n gt e c h n o l o g y c o m p u t e rs o f t w a r e t h e o r y m d c a n d i d a t e ：t a n gm i ns u p e r v i s o r ：p e n gh o n g a b s t r a c t 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 e t ，t h et e c h n o l o g yo fe m a i lh a sb e c o m e o n eo ft h em o s te c o n o m i c a lw a y so fc o m m u n i c a t i o na v a i l a b l e , m o s ts e c r e tl e t t e r s a r ea l s os e n tb ye - m a i l h o w e v e r , s p a mi sa no n g o i n gp r o b l e mo nt h ei n t e m e t w h e ne - m a i li sd e v e l o p i n g s p a mc a u s e st h eg r e a tw a s t eo fu s e r st i m e ，e n e r g ya s w e l la sn e t w o r kb a n d w i d t ha n ds t o r a g es p a c e t h e r e f o r es p a mf i l t e r i n gi sas u b j e c t w i t hg r e a tr e a l i s t i cm e a n i n g n o w a d a y s ，m a n ym e a n sc a nb ea p p l i e dt or e s o l v et h ep r o b l e mo fs p a m f i l t e r i n g c o n t e n t b a s e de - m a i lf i l t e r i n gi so n e o ft h em a i n s t r e a mt e c h n o l o g i e su s e d s of a r a tp r e s e n t ，t h em a j o r i t yc o n t e n t b a s e de - m a i lf i l t e r i n gu s en a i v eb a y e s a l g o r i t h m ( n b ) b u tn b sp r e c i s i o na n dr e c a l la r el o w e rc o m p a r e dw i t hs u p p o r t v e c t o rm a c h i n e ( s v m ) s v mi san o v e lk i n do fm a c h i n el e a r n i n gm e t h o df r o ms t a t i s t i c a lt h e o r y a n d i th a sb e e ns h o w nt op r o v i d eh i g l l e rs u p e r i o r i t yt h a no t h e rl e a r n i n gm a c h i n e s ，s u c h a ss t r u c t u r a lr i s km i n i m i z a t i o n ，g l o b a lo p t i m a ls o l u t i o nw h i c hi su n o b t a i n a b l eb y u s i n go t h e rm a c h i n el e a r n i n gm e t h o d s ，v e r yg o o de f f e c tw h e nt r a i n i n gs a m p l ea r e i nt h en o n l i n e a r i t ya n dh i g hd i m e n s i o np a t t e r n s b u tt h e r ea r em a n yp r o b l e m st o c l a s s i f ye m a i li ft h ec l a s s i f i e ri st r a d i t i o n a ls u p p o r tv e c t o rm a c h i n e t r a i n i n gt i m e a r el o n ga n dt h er o b u s t n e s so ft h ea c c u r a c ya n dt h ep r e c i s i o na r en o tb e s ti na 1 1 1 西华大学硕士学位( 毕业) 论文 l a r g e s c a l eo p e r a t i o n t h a tl e g i te m a i l s a r ec o l l e c t e da r em o r ed i f f i c u l tt h a n c o l l e c t i n gs p a m s ol e g i te m a i lm a y b eb ef u l l ya s s i g n e dt os p a mb yt r a d i t i o n a l s v ma n dc l a s s i f i e df u n c t i o ni sn e a rt ot h el e s s s o m ei n p u tp o i n t sm a yn o tb e e x a c t l ya s s i g n e dt oc l a s s e sw h e nt r a d i t i o n a ls v m sc l a s s i f yi n p u tp o i n t ss ot h a t s v mc a n n o ts e p a r a t et h e s ep o i n t sm o r ec o r r e c t l y s o m ed a t ap o i n t sc o r r u p t e db y n o i s e sa r el e s sm e a n i n g f u la n dt h ep r e c i s i o n sa r ed r o p p e d i nt h i s p a p e r , t oo v e r c o m et h e s ep r o b l e m s ，w ep r o p o s et w oi m p r o v i n g m e t h o d so fs v mw h i c ha r eh i e r a r c h i c a la n dp a r a l l e ls u p p o r tv e c t o rm a c h i n ea n d f u z z ys u p p o r tv e c t o rm a c h i n eo ne m a i lf i l t e r i n g t h er e s e a r c ho ft h ep a p e rc o u l db ee m b o d i e di nt w or e s p e c t s ： t h i sd i s s e r t a t i o n p r e s e n t h i e r a r c h i c a lp a r a l l e ls v ma l g o r i t h mt o a n t i - s p a m f i r s t l y , t h ee n t i r ec l a s s i f i c a t i o np r o b l e mi sd i v i d e di n t os e v e r a l s m a l ls u b p r o b l e m st h a tc a nb eh a n d l e di na p a r a l l e lw a y h a v i n g h i e r a r c h i c a l l yf i l t e r e do u tt h en o n - s u p p o r tv e c t o rd a t aw ec a no b t a i nt h e f i n a lt r a i n i n gd a t as e t ，w h i c hi su s e dt ot r a i nt h ef i n a ls v m t h e c r o s s c o m b i n i n gp r i n c i p l ei si n t r o d u c e di nf i l t e r i n gt or e d u c et r a i nt i m e a n dk e e pt h ec a p a b i l i t yo fc l a s s i f i e r s f u r t h e r m o r e ，t h ec r o s s - c o m b i n i n g p r i n c i p l ec a nr e d u c et h ec o s t sd u et ot h ei m b a l a n c eo ft h en u m b e r s b e t w e e nt w oc l a s s e s a n dt h i s p a p e r d e d u c e dp r i n c i p a lc o m p o n e n t a n a l y s i sm e t h o dw h i c hi m p r o v e dt h ee f f i c i e n c yo fd e a l i n gw i t he m a i l f e a t u r ee x t r a c t i o n e x p e r i m e n t ss h o wt h a th p s v ma l g o r i t h mn o to n l y s p e e d su pt h et r a i n i n gb u t a l s oo b t a i nb e t t e rp r e c i s i o na n dr e c a l l t h i sd i s s e r t a t i o np r e s e n tan o v e la n t i - s p a r ee - m a i la l g o r i t h mb a s e df u z z y s u p p o r tv e c t o rm a c h i n ew i t hm i s c l a s s i f i c a t i o nc o s t s f s v ms o l v et h e c a s et h a t i n p u tp o i n t sm a yn o tb ee x a c t l ya s s i g n e dt o c l a s s e s ci s i n v a r i a b l ei nt r a d i t i o n a ls v m ，i e ，l e g i t i m a t ee m a i la n ds p a ma r ed e a l e d w i t he q u a l l yi ne m a i lf i l t e r i n g b u tt h el o s so fl e g i t i m a t ee m a i li sm u c h m o r es e r i o u s s ow ep r o p o s e dt h a tm i s c l a s s i f i c a t i o nc o s t st of u z z ys u p p o r t v e c t o rm a c h i n ei no r d e rt o p a s sa l ll e g i t i m a t ee m a i l s a tt h es a m et i m e i v 西华大学硕士学位( 毕业) 论文 t h i sp a p e rc a l c u l a t e sd e n s i t yo fd i s t r i b u t i o no ft h es a m p l e sa sf u z z y m e m b e r s h i p t h i sm e t h o dc a np r e v e n tn o i s yd a t ap o i n t sf o rt h ee f f e c t e x p e r i m e n t ss h o wt h a t t h i sa l g o r i t h mi m p r o v e st h ep r e c i s i o na n dt h e c a p a b i l i t yo f e m a i lc l a s s i f i e r k e y ：s p a m ，p r i n c i p a lc o m p o n e n ta n a l y s i s ，s u p p o r tv e c t o rm a c h i n e ，f u z z y s u p p o r tv e c t o rm a c h i n e m i s c l a s s i f ：i c a t i o n v 西华大学硕士学位( 毕业) 论文 1 引言 1 1 研究背景和意义 随着全球信息化的迅猛发展，上网人数的不断增加，互联网络已经成为人 们工作、学习和生活中不可或缺的一部分，而电子邮件又是通过互联网让人们 进行信息交流的重要手段。人们在网上可以轻松自如地收取、发送电子邮件以 满足个人的需求，确实这种高科技的手段为人们相互之问的交流节省了时间， 提供了更大的方便，但是经常使用电子邮件的用户可能都曾经收到许多不认识 的人发来的广告邮件或其他一些毫无关系的邮件，而要处理这些邮件使人烦不 盛烦。 事实上，人们在i n t e r n e t 没有完全建立起来时就已经意识到了垃圾邮件的 问题，并且在它诞生之日就遭到许多网络用户的强烈谴责。垃圾邮件最早源于 美国，在英文中有三个称呼：u c e 、u b e 和s p a m i ”。而我国，2 0 0 3 年2 月 2 6 号中国互联网协会反垃圾邮件规范1 2 中第三条也明确指出垃圾邮件的定 义： 1 ) 收件人事先没有提出要求或者拒绝接受的广告 2 1 收件人无法拒收的电子邮件 3 ) 隐藏发件人地址、身份标题等信息的电子邮件 4 ) 含有虚假信息源、发件人、路由等信息的电子邮件 在我国，中国互联网协会2 0 0 6 年第一次反垃圾邮件调查发现，从2 0 0 5 年 1 1 月到2 0 0 6 年3 月期间，中国互联网用户平均每周收到垃圾邮件数量为1 9 3 3 封，较2 0 0 5 年1 0 月的每周1 7 2 5 封上升了2 0 8 封。同时以2 0 0 5 中国国民经济 生产总值为依据，结合用户每周处理垃圾邮件所需时间，得出垃圾邮件将给中 国的国民经济( g d p ) 每年造成约为6 0 6 9 亿人民币的损失【3 j 。垃圾邮件造成 了巨大的经济损失，其严重影响了电子邮件服务的正常次序并造成了严重的网 西华大学硕士学位( 毕业) 论文 络堵塞。 垃圾邮件与其它的媒体不同，它的成本部分是追加到收件方的头上： 从用户层面看，它占用了收件人的宝贵时间，需要小心地判别垃圾邮件 和正常邮件，每天必须花大量的时间来处理他们，而且应该说垃圾邮件还侵犯 了他人的隐私权。 从整个网络资源利用层面看，它还占用了大量的带宽和存储的空间，垃 圾邮件里的信息几乎都没有什么价值，还会堵塞网络、中断部分线路的运营。 在垃圾邮件中约有4 6 是商业性的广告，其它还有3 2 的政治宣传和4 的色情宣传【l 】，而这些严重地危害了社会安全和带来大量社会不稳定因素。 另外，不得不提的是还有一类特殊的垃圾邮件，即病毒邮件，它不同于商业广 告和宗教宣传等性质的邮件，它有其自身的特点。因此人们无论从数量上还是 从危害上，都要对此引起足够的重视。对于带有恶意病毒代码的垃圾邮件，收 件人一旦打开邮件，就会对系统造成各种各样的破坏，例如：m y d o o m 就是通 过电子邮件传播的，它被认为是有史以来传播速度最快的蠕虫病毒。 由于垃圾邮件的大量泛滥，越来越多的国外组织放弃寻求解决的尝试，直 接屏蔽i p 。而中国就占有3 6 的垃圾邮件来源1 4 1 ，如果屏蔽口这无疑会对我 国的正常通信和其它业务造成很大的损失，所以防止垃圾邮件是一项刻不容缓 的事情。 反垃圾邮件技术有很多种，邮件过滤是反垃圾邮件的一种重要方法。正如 我们在不断地找寻新的方法来反垃圾邮件一样，发送垃圾邮件的人也在不断地 改进他们的技术。他们采用更为复杂的软件技术，使发给每位收件人的邮件更 个性化从而增加检测的难度，甚至使用收件人的密钥对信件的内容进行加密， 因此相应地邮件过滤技术只有不断地改进才能保证有效性。而邮件过滤技术不 仅能过滤垃圾邮件，而且也可以从大量邮件中寻找到感兴趣的邮件。当从经济 和法律的手段都无法有效的抑制垃圾邮件的蔓延时，过滤技术是对付它们的最 有效手段。当前有些过滤方法已经用到了各种邮件服务器上，但它们在技术上 都又有其自身的优缺点，怎样把这些方法更好地结合起来，更好地增加其效率 和精度，减少误分率，具有重要的意义。 2 西华大学硕士学位( 毕业) 论文 1 2 邮件过滤技术方法及发展 垃圾邮件是用专门的邮件地址搜索软件和邮件群发软件来完成电子邮件 地址收集和垃圾邮件散发的，一个邮件地址搜索软件每次可以搜索到几万至十 几万个有用的邮件地址，一个邮件群发软件每天可以发送百万封同样或不同内 容的垃圾邮件。 对于垃圾邮件过滤技术，从电子邮件体系结构来说，可以分为：邮件传输 代理过滤、邮件投递代理过滤和邮件用户代理过滤【5 】；从过滤依据来看又可分 为：基于邮件地址或域名的邮件过滤和基于内容的邮件过滤【“。 1 2 1 基于邮件地址或域名的邮件过滤 基于邮件地址或域名的邮件过滤当前主要有白名单过滤、黑名单过滤和反 向域名验证等技术。 白名单过滤方法是由h a l l l 7 在1 9 9 8 年提出，就是在邮件过滤系统中维持 一张白名单表，其中收录了用户许可的邮件地址，当收到的邮件其发送者在用 户的白名单表中，该邮件就被判定为正常邮件。如果不在其中，就会产生一个 特殊的质询发给相应的发送者，并且等待发送者的答复，以便将其加入到白名 单中，如果邮件发送者能正确给出答复，就将新的发送者加入到白名单中 8 | 。 但白名单技术给合法邮件发送者和邮件服务器带来了许多额外的负担，并且会 有较高的误判率。 黑名单过滤一j ，即利用国内外有很多组织提供垃圾邮件制造者或策源地的 “黑名单”，服务器接收到邮件后，先到“黑名单”上去查找，如果邮件来自 “黑名单”中的地址，则认为该邮件是垃圾邮件。目前有专门的反垃圾邮件网 站或i t 部门定期提供实时黑名单表r b l ( r e a lb l a c kl i s t ) ，如美国的“邮件 滥用预防系统( m a p s ) 。在2 0 0 3 年，杨锋i l0 j 等人提出了一个基于d n sb l a c k l i s t s 的反垃圾邮件系统，他利用d n s 技术、开放性中继器( o p e nr e l a y ) 测试技 术，以及策略分级过滤规则技术，实现了国内教育网的垃圾邮件过滤。 当然对于黑名单和白名单也常常结合起来使用，这样可以进行动态的更 西华大学硕士学位( 毕业) 论文 新，但它的误判率还是太高。 反向d n s 查询【1 1 】是对发送者的i p 地址进行逆向域名解析，通过d n s 查 询判断发送者的i p 与其声明的名字是否一致。但反向d n s 查询需要耗费大量 的系统和网络资源。当前t o m 邮箱的反向d n s 记录是1 6 3 n e t ，对于这种方法 在国内使用非常有局限性。 1 2 2 基于内容的邮件过滤 基于内容的邮件过滤技术是当前电子邮件过滤技术的主流技术。由于通常 垃圾邮件的发送者是经常变换的，并非是几个固定的人( 帐号) 。而且同一个 垃圾邮件发送者也可以通过申请不同的免费邮箱来进行垃圾邮件的传播，所以 基于邮件地址或域名的邮件过滤技术存在很大的局限性。因此就有了通过对垃 圾邮件的内容进行分析、检查的过滤方法。基于内容的邮件过滤方法又可以分 为基于规则分析的过滤方法、基于概率统计的过滤方法和其它些新的过滤方 法。 1 ) 基于规则的邮件过滤由用户或系统设置若干过滤规则，系统根据这些 规则对邮件信息进行检测，符合其中一条或多条的就认为是垃圾邮件。r i c h a r d 和j e a s o n 1 2 】提出了关键词匹配的邮件过滤，它是基于关键词匹配( 匹配模式) 的电子邮件检索，检查进出邮件的主题、内容甚至附件中是否有关键词，如果 有就删除。但这种方法很单一而且要有人工参与，存在较大的虚警率，导致大 量的邮件丢失。后来出现了一些解决方法，有人提出对敏感的关键词出现的单 旬进行语义分析，根据结果进行分流处理。在国内，因为中文邮件的特殊性， 2 0 0 0 年陈华辉i l3 】提出了一种基于潜在语义索引的垃圾邮件过滤，它是对前面 关键词匹配的改进，它的基本思想就是把词与词的内在联系表示出来，规定将 己过滤向量与其它邮件进行相似度计算，若相似度超过某个值就删除。 1 9 9 6 年c o h e nww 【1 4 j 提出了基于学习规则的方法来进行邮件分类，其中 心思想是反复向初始为空的规则集中加入规则直到所有正例被覆盖。基于规则 的优点是它所具有的先验知识易于理解和更新，但当存在大量的训练数据和存 在噪声时，效果不好。 2 0 0 0 年，c a r r e r a s l l 5 1 提出决策树算法用于邮件过滤，但对于基于决策树的 4 西华大学硕士学位( 毕业) 论文 方法，得到的查全率和准确率不太高，因此后来d e s o u z a l l 6 j 进行改进，提出决 策树的c 5 0 算法来建立决策树形式的分类规则。 2 0 0 1 年c a r r e r a s 和n i c h o l a s “】又提出a d a b o o s t i n g 算法用于邮件过滤系 统。通过把已经存在的弱规则分类器进行加权求和来得到强规则分类器，以形 成个总的分类器。这样可以得到较高的正确率和查全率，但训练时间过长。 2 0 0 3 年，于洪、李志君等【1 7 提出了基于粗糙集的邮件过滤系统模型。它 结合粗糙集对决策表进行分析形成决策属性，不同用户采用不同的属性值来寻 求规则。 2 ) 基于概率统计的过滤方法 当前基于概率统计方法使用最多的是贝叶斯方法。在1 9 9 8 年s a h a m im 【1 8 1 提出用贝叶斯方法来过滤邮件。它是一种在条件独立假设下的简化贝叶斯分类 方法。通过贝叶斯的条件概率表c p t 来得到相关系数，若有：p ( c = “感兴趣 邮件”l x = x ) sp ( c = “感兴趣邮件”l x - - x ) ，则邮件为用户感兴趣邮件，否则为 不感兴趣邮件。但是这种方法是基于最小错误率的决策方式，当合法邮件被错 分为垃圾邮件的可能性比较大时，会给用户带来较大的损失。1 9 9 8 年r e n n i e ”j 在贝叶斯方法的基础上建立了一个邮件过滤的机器学习应用系统i f i l e 。这种方 法对于邮件的分类的速度很快，而且可以对其进行动态的调整，但就如前面所 说的误分率仍然比较高，用户还需要检测邮件中是否存在错误分类。p a u l g r a m h a m i 加j 于2 0 0 2 年提出了建立垃圾邮件和非垃圾邮件单词的贝叶斯概率模 型。同年国内的石霞军【”】提出了基于最小风险的贝叶斯邮件过滤算法，它既 考虑后验概率的大小来做决策也把是否损失最小作为决策依据来考虑，虽然对 分类的查全率有所提高，但垃圾邮件的召回率却有所下降。2 0 0 3 年，蔡立军【2 2 l 把遗传算法和贝叶斯相结合用于邮件过滤。 1 9 9 9 年，d u r c k e r l 2 3 】把r o c c h i o 算法引入邮件过滤并同s v m 、r i p p e r 等算 法比较。该算法使用两类向量的加权差来计算两类向量的类别向量，通过对新 邮件计算与这两个类别向量的距离来判断归属于哪一类。该算法的过滤较快， 但过滤效果不太理想。 a n d r o u t s o p o u l o s 2 4 】把k 邻近算法应用到邮件过滤中，通过计算待分类邮件 的距离来找出最相近的k 个邮件，从而得出新邮件的类别，并同贝叶斯算法比 西华大学硕士学位( 毕业) 论文 较，其得到与贝叶斯基本一样的效果。 2 0 0 2 年s o o n t h o m p h i s a jn 【冽等人提出基于质心算法的邮件分类，所谓质 心算法是用质心向量总结了每一类邮件的普遍特征，其中突出的维将反映在这 些词出现频繁的邮件中，并通过使用简单函数说明词之间的依赖性来进行比值 计算。它对邮件特征的总结要比k 邻近方法执行的更好。它减少了分类错误的 可能性，但对于把正常邮件过滤为垃圾邮件的比率还是有待于提高。 2 0 0 3 年，j c l a r k 2 6 】等人把神经网络应用到邮件分类上，从而提高邮件过 滤的正确率和误分率，但它的缺点是训练时间太长。 在1 9 9 9 年d r u n k e r h 和v a p n i k v n 【矧提出了电子邮件系统的支持向量机 模型。该方法从样本集中选择一组特征子集，使得对于特征子集的划分等价于 整个样本集的划分。它减少了训练样本数，具有很好的泛化能力。后来b r u t l a g 和m e e k l 2 7 1 把线性支持向量机用于邮件分类对其加以改进。当前对于基于支 持向量机的邮件过滤还处于初步阶段，对于数据量过大的数据集，s v m 训练 时间过长，并且在邮件分类过滤中垃圾邮件具有自身的一些特点，如误分合法 邮件比误分垃圾邮件要严重很多。为此在2 0 0 4 年a l e k s a n d e r ”j 等人提出了一 种考虑特定内容误分损失的s v m 邮件过滤算法，但无论怎样，s v m 具有其它 方法无法比拟的优点，如结构风险最小化、全局唯一解、在非线性和高维模式 中也表现出很好效果，是邮件过滤中很有前途的一种方法。 3 ) 其他的些过滤方法。1 9 9 8 年h a l l l ”1 提出基于a g e n t 的邮件分类方法。 a g e n t 是将推理和表示相结合的智能体，可以独立运行于一定的环境中，并与 环境进行交互，通过相应的学习机制来提高自身的能力。以后许多人在其上面 加以改进提出了基于多a g e n t 的邮件过滤系统。通过设置多个a g e n t 来自动对 用户的邮件有选择的接收，并通过学习机制来进一步了解用户的喜好。但由于 解析a g e n t 对语言解析能力的限制，它制约了邮件过滤的精确化，但随着语言 解析能力的提高，这个方法可进一步完善。 另外，还有文件类型过滤和邮件大小过滤，即对邮件的附件的接收和发送 进行控制和对超过一定字节的信件进行过滤。目前针对这两种过滤方式的技术 还是不太实用，所以通常还是用人工的方法。 最近还有一种基于p k l ”】的方式，它通过p k i 对邮件发送者进行验证， 6 西华大学硕士学位( 毕业) 论文 对邮件信息进行加密，对收信人实现防抵赖机制。域的所有者生成公钥和私钥， 私钥用于所有发送邮件的签名。公钥通过d n s 发布。当授权用户发送邮件时， 邮件服务器自动产生邮件的数字签名。接收时，如果没有数字签名或签名失败， 收件方可以拒绝、标记或隔离邮件。 1 3 支持向量机相关基本理论 统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。 统计学习理论的主要内容包括：经验风险最小化原则下的统计学习一致性的条 件；在这些条件下的边界理论；在这些界的基础上建立的结构风险最小化原理： 以及实现这些原理的方法 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是构建在统计学习理论上的 一种新的机器学习方法f 3 1 】【3 2 1 。大多数传统的方法都是基于经验风险最小化原 则的，但这种原则有很大的不足：( 1 ) 这种原则没有可靠的理论依据，只是直 观上合理的想当然做法1 3 3 】。( 2 ) 一味地追求经验风险最小化并不是总能达到好 的预测效果，反而会发生过学习的现象。人们将学习机器对未来输出进行正确 预测的能力称为推广性，当训【练误差过小时反而会导致推广能力下降，这就是 过学习问题( o v e f f i t t i n g ) 。统计学习理论研究经验风险与期望风险的关系并提 出结构风险最小化理论，有效地克服了传统方法中经验风险最小化的缺点。 当然支持向量机也存在一些缺陷和问题，比如当一部分数据比另一部分数 据更重要时，应怎么把重要的数据进行正确分类等。 1 3 1 经验风险最小化 学习的目的是根据给定的训练样本求系统输入输出之间的依赖关系。机器 学习问题就是根据n 个独立同分布的观测样本：( x 1 ，y - ) ，( x 2 ，y 2 ) ，( x 。，y n ) ，在一 组函数 f ( x ，w ) 中来寻求一个最优的函数f ( x ，w o ) ，对x 与y 的关系进行估计， 使期望风险最小。期望风险定义如下： r ( w ) = f l ( y ，f ( x ，w ) ) a f ( x ，y ) ( 卜1 ) ， 在传统的学习方法中，采用了经验风险最小化( e r m ) 准则，即用样本 西华大学硕士学位( 毕业) 论文 定义经验风险 1n r e r n p ( w ) ；罗l ( y i ，f ( x i ，w ) ) ( 1 2 ) n 筒 经验风险最小化原则在有限样本时是不合理的，需要同时最小化经验风险 和置信范围。实际上，传统方法中选择学习模型和算法的过程就是选择置信范 围的过程，如果模型比较适合现有的训练样本( 相当于h n 值适当) ，则可以 取得比较好的效果。在模式识别中选定了一种分类器形式就确定了学习机器的 v c 维。实际上这种作法是首先通过选择模型确定中，在固定m 的条件下，通 过经验风险最小化来求最小风险。比如在神经网络中，需要根据问题和样本的 具体情况选择不同的网络结构( 对应不同的v c 维) ，然后进行经验风险最小 化。由于缺乏理论指导，这种选择只能依赖先验知识和经验，而且如果选择的 v c 维较大，往往会出现过学习的现象。 1 3 2v 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 ) 。它的直观定义是【3 4 j ：对一个指示函数集，如果存在h 个样本能 够被函数集里的函数按照所有可能的2 “种形式分开，则称为函数集能够把h 个样本打散。函数集的v c 维就是它能打散的最大样本数目h 。如果对任意数 目的样本都有函数能将它打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过一定的阀值将它转化为指示函数来定义。 v c 维反映了函数集的复杂性或学习能力，v c 维越大则机器学习越复杂。 对于给定的学习函数集，如何计算v c 维是当前统计学习中有待研究的问题。 1 3 3 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险 之间的关系，即推广性的界。对于模式识别问题( 当然还包括回归问题和密度 估计问题) ，其结论是：对指示函数集中的所有函数( 包括使用经验风险最小 的函数) ，经验风险m p ( w ) 和实际风险r ( w ) 之间以至少1 一玎的概率满足如下 西华大学硕士学位( 毕业) 论文 关系3 ”： r ( w ) sr 。p ( w ) + 、h ( 1 n ( 2 n h ) + 1 ) - l n ( q 4 ) ( i - 3 ) v n 其中h 是函数集的v c 维，n 是样本数。 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经 验风险( 训练误差) ，另一部分是置信范围，它和学习机器的v c 维及训练样 本数有关。它表明，在有限样本下，学习机器的v c 维越高，那么置信范围越 大，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学 习现象的原因。机器学习过程不但要使经验风险最小，还要使v c 维尽量小以 缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。 需要指出，推广性的界是对于最坏情况的结论，在很多情况下是宽松的， 尤其当v c 维较高时更是如此( 文献 3 2 1 指出当h n o 3 7 时这个界肯定是松弛 的，v c 维无穷大时这个界就不再成立) 。而且这种界只在对同一类学习函数 进行比较时有效，可以指导我们从函数集中选择最优的函数，在不同函数集之 间比较却不一定成立。 1 3 4 结构风险最小化 为了克服传统方法的不足，我们要权衡( 1 3 ) 式中的经验风险和置信范围的 大小，使其共同趋于最小。统计学习理论提出的结构风险最小化原则解决了这 个问题，它提出了这样一种策略：首先把函数集s = f ( x ，w ) ，w q ) 分解为个 函数子集序列( 或叫子集结构) ， s 1 c s 2c cs k c c s 使各子集能够按照中的大小排列，也就是按照v c 维的大小排列，即 h 1 h 2 h 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 准则。 9 西华大学硕士学位( 毕业) 论文 图1 1 中给出了真实风险、经验风险与置信范围的函数变化曲线，随着h 的增加，经验风险r 。( w ) 递减。这是因为当h 增加时，根据v c 维的定义， 对应的函数集合的描述能力增加，学习机器的学习能力随之增强，可以使有限 样本的经验风险很快地收敛，甚至于变为o ：根据式n 3 ) ，置信范围中随着h 的增加而增加；这样，真实风险r ( a ) 是一个凹型曲线。所以，要获得最小的真 实风险，就需要折衷考虑经验风险与置信风险的取值。 风险欠学习过学习 f i g u r e l 1s k e t c hm a p o fs t m c t u r a lr i s km i n i m i z a t i o n 图1 1 有序风险最小化示意图 根据这一分析，我们可以得到两种运用结构风险最小化原理来构造学习机 器的思路： 1 ) 给定了一个函数集合，按照上面的方法来组织一个嵌套的函数结构，在 每个子集中求取最小经验风险，然后选择经验风险与置信风险之和最小的子 集。但是当子集数目较大的时，此方法较为费时，甚至于不可行。 2 ) 构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小的 经验风险( 例如，使得训练误差为0 ) ，然后在这些子集中选择适当的子集使 得置信风险最小，则相应的函数子集中使得经验风险最小的函数就是所求解的 最优函数。支持向量机方法实际上就是这种思想的具体实现。 西华大学硕士学位( 毕业) 论文 1 4 本文研究内容 邮件过滤是一个活跃的、有趣的研究课题，吸引了众多的研究者，特别是 近年来基于内容的邮件过滤研究。 支持向量机是一个新颖的机器学习方法，已在多种模式识别领域取得了成 功。支持向量机方法本身有其它方法无法比拟的优点，有几位研究者将该方法 应用于邮件过滤研究中，结果表明该方法具有比其他机器学习方法更好的性 能。但这些研究中主要采用标准的支持向量机算法，仍然具有一些不足或缺陷： 比如：( 1 ) 标准的支持向量机算法将邮件分类问题转化为二次规划问题来求 解，在处理大数据邮件样本训练时处理速度很慢。( 2 ) 当邮件样本的不同类 的规模差异较大时，即出现不平衡问题时，会使分类精确度不太理想。 ( 3 ) 对噪声比较敏感。( 4 ) 无法处理出现训练样本不能明确地归属一类的情形。 当然，还存在其他的一些问题。 如何发挥支持向量机方法在邮件过滤中的优势并克服目前存在的一些问 题是基于支持向量机的邮件过滤方法研究的一个主要方向。本论文的研究工作 将体现在为解决上述目前基于支持向量机的邮件过滤方法存在的四个问题而 开展的详细地研究。具体提出了两种改进的支持向量机的邮件过滤方法，体现 在如下方面： l 、针对上述问题( 1 ) 与( 2 ) ，提出了一种并行分层支持向量机的垃圾 邮件过滤方法，并结合主成分分析( p c a ) 对特征向量进行压缩。该方法将邮件 样本集划分为几个子样本集，采用逐层并行训练支持向量机，并且在分层筛选 中使用交叉合并方法以缩短训练时间，同时保证不降低邮件的分类能力。这种 交叉合并方法还可以避免出现两类训练样本数量的不平衡而导致的分类信息 损失。 2 、针对上述问题( 3 ) 与( 4 ) ，提出一种模糊支持向量机的邮件过滤方 法，通过模糊支持向量机重新计算支持向量，使不同的输入点对决策面有不同 的贡献，来提高分类的正确率，并在计算支持向量的同时区别出没有多大用处 的噪声点和局外点，减少对它们对分类的干扰。通过在模糊支持向量机中引入 不同邮件类的误分损失，确保合法邮件尽可能不被错分，从而提高邮件过滤的 西华大学硕士学位( 毕业) 论文 正确率，降低误分和漏报率。 1 5 论文结构 全文以下各章的内容安排如下： 第二章邮件相关知识和预处理技术，系统地介绍邮件系统的组成和相应工 作原理，并进一步回顾了有关邮件特征表示、向量空间模型表示、特征提取和 约简方法。 第三章在回顾支持向量机算法的基础上，提出并行支持向量机的邮件过滤 方法，讨论其分层并行的主要思想以及交叉合并的原理。通过仿真试验对比了 它与标准支持向量机和其他机器学习方法的性能。 第四章引入模糊