（计算机科学与技术专业论文）改进的knn算法在过滤垃圾邮件中的应用研究.pdf

t h er e s e a r c ha b o u tt h ea p p l i c a t i o no fi m p r o v e dk n n a l g o r i t h m s s p a mf i l t e r i n g b y l i nw e n x i a n g b e ( c e n t r a ls o u t hu n i v e r s i t yo ff o r e s t r ya n dt e c h n o l o g y ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o m p u t e ra p p l i c a t i o n i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r a s s o c i a t ep r o f e s s o rc h e nh a o n o v ，2 0 1 0 3 -删86 09 m胛丫 学 性声明 在导师的指导下独立进行研究所 引用的内容外，本论文不包含任 作品。对本文的研究做出重要贡 标明。本人完全意识到本声明的 日期：加历年( 胡日 用授权书 留、使用学位论文的规定，同意 文的复印件和电子版，允许论文 本学位论文的全部或部分内容编 缩印或扫描等复制手段保存和汇 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打c c 、f ”) 作者签名： 导师签名： 日期：加加年f 五月日 日期：l ，年f 乙月 6 日 改进的k n n 算法在过滤垃圾邮件中的应用研究 摘要 随着互联网的广泛普及，电子邮件已经成为人们日常生活中最便捷、最经济 的通信手段。但是电子邮件给用户带来便捷的同时，也带来了不可避免的副产品 垃圾邮件。由于实现比较简单以及受到利益的驱使，一些企业和个人采用了 这种最经济的方式进行商业广告，一些黑客也采用发送电子邮件进行违法行为： 盗窃用户的机密资料，攻击用户的电脑等。电子邮件用户几乎每天都要收到几十、 几百封垃圾邮件，每天都需要花费一定的精力与时间来判断是否为垃圾邮件，并 进行清除。垃圾邮件不仅影响到了电子邮件用户，对网络运营提供商和网络管理 员也带来了无尽的烦恼。这些所谓的垃圾邮件会占用用户的带宽、时间和存储资 源，如果泛滥严重甚至会对网络通信造成堵塞，使得正常邮件不能正常发送和接 收，垃圾邮件严重阻碍了互联网的健康发展。因此对垃圾邮件过滤技术的研究具 有很大的实用价值，也是亟待解决的问题。 本文全面分析当前垃圾邮件的主要特点以及垃圾邮件过滤技术的发展状况； 深入讨论了各种反垃圾邮件技术的相关理论和各自的优缺点。针对当前效果较好 的k n n 算法进行了深入的研究，针对k n n 算法的不足：传统的k n n 算法只考 虑到相似度之和，或者简单的利用相似度个数的多少来进行判断；将k n n 算法 应用于垃圾邮件的过滤中，而没有考虑到垃圾邮件本身的偏依赖特性，即用户情 愿多收到一封垃圾邮件，也不愿意让垃圾邮件过滤系统将自己的正常邮件误判为 垃圾邮件过滤掉；传统的k n n 分类算法进行分类时，每次都需要将待测样本和 训练样本集中的每个样本进行比较，计算相似度，计算量十分的大，不适合实时 性要求比较高的垃圾邮件过滤系统。 本文针对上述k n n 算法的不足之处进行改进，提出并设计一种考虑了偏依 赖特性的基于平均相似度和相似度个数的k n n 算法。该算法首先通过计算平均 相似度而不是相似度之和来表示类权重值，同时考虑到相似样本的个数对分类性 能的影响；其次引入了两个表示垃圾邮件本身的偏依赖特性的参数；最后，为了 解决k n n 算法的计算量大的缺点，本文利用类中心向量法的思想，通过将将原 始样本转化为一个个小类，并计算每个小类的中心向量，以代表原始训练样本建 立分类模型，这就相当于将大样本转化为小样本，减少了比较次数，大大降低了 k n n 分类算法的计算量。实验表明，与传统的k n n 算法进行对比，本文提出的 a p c k n n 算法应用于垃圾邮件的过滤，具有高正确率，低误报率等优点；并且 能够更好的实现垃圾邮件的过滤，起到了保护电子邮件用户以及节省宽带等效果。 关键词：垃圾邮件；k n n 算法；偏依赖特性；类中心向量 i i 硕卜学位论文 a b s t r a c t w i t ht h ew i d es p r e a do ft h ei n t e r n e t ，e - m a i lh a sb e c o m et h em o s tc o n v e n i e n t a n de c o n o m i c a lm e a n so fc o m m u n i c a t i o ni no u rd a i l yl i f e w h i l et h ee o m a i lp r o v i d e t h ec o n v e n i e n c et ot h eu s e r ，i ta l s ob r i n g so u ta ni n e v i t a b l eb y - p r o d u c tw h i c hi st h e s p a m a st h er e a l i z a t i o n o fs p a r ei ss i m p l ea n dd r i v e nb yt h ei n t e r e s t s ，s o m e c o m p a n i e sa n di n d i v i d u a l s u s et h em o s te c o n o m i c a lw a yo fs u c hc o m m e r c i a l a d v e r t i s i n ga n dh a c k e r sh a v eu s e dt os e n di l l e g a le - m a i l ：s t e a lu s e rc o n f i d e n t i a l i n f o r m a t i o n ，a t t a c kt h eu s e r sc o m p u t e r sa n ds oo n e m a i lu s e r sr e c e i v e dh u n d r e d s o fs p a r em e s s a g e se v e r yd a ya n dt h e yh a v et ot a k es o m ee f f o r ta n dt i m et od e t e r m i n e w h e t h e rt h es p a m ，a n dc l e a rt h e m s p a mn o to n l ya f f e c t se - m a i lu s e r s ，b u ta l s o p r o v i d e st h en e t w o r ko p e r a t o r sa n da d m i n i s t r a t o r se n d l e s st r o u b l e t h e s es o c a l l e d j u n km a i lw i l lt a k et h eu s e r sb a n d w i d t h ，t i m ea n ds t o r a g er e s o u r c e s ，e v e ni fs e r i o u s f l o o d i n gw i l lc a u s en e t w o r kt r a f f i cc o n g e s t i o n ，m a k i n gt h en o r m a ls e n d i n ga n d r e c e i v i n g e - m a i ld o e sn o t w o r k ，s p a mh a ss e r i o u s l y h i n d e r e dt h e h e a l t h y d e v e l o p m e n to ft h ei n t e r n e t t h e r e f o r e ，s p a mf i l t e r i n gt e c h n o l o g y0 nt h er e s e a r c ho f g r e a tp r a c t i c a lv a l u e ，b u ta l s op r o b l e m st ob es o l v e d t h i sp a p e ra n a l y s i so ft h em a i nf e a t u r e so ft h es p a ma n ds p a mf i l t e r i n g t e c h n o l o g yd e v e l o p m e n t ，a n dd i s c u s st h ev a r i o u sa n t i - s p a mt e c h n o l o g yw i t hr e l e v a n t t h e o r i e sa n dt h e i rr e s p e c t i v ea d v a n t a g e sa n dd i s a d v a n t a g e si n d e p t h w eg i v et h e d e e ps t u d yi nb e t t e ra l g o r i t h mo fk n n ，a n dt h es h o r t a g eo fk n n ：t r a d i t i o n a lk n n a l g o r i t h mo n l yt a k e i n t oa c c o u n tt h es i m i l a r i t y ，o rs i m p l yu s et h en u m b e ro f s i m i l a r i t yt oju d g e ，a n dn e g l e c tt h e i rp a r t i a ld e p e n d e n c eo fs p a mf e a t u r e s ，t h a tu s e r s w o u l dr a t h e rr e c e i v eas p a r e ，d on o tw a n tt os p a mf i l t e r i n gs y s t e mw i l lb ey o u r n o r m a lm a i la ss p a mt of i l t e ro u tf a l s ep o s i t i v e s t h et r a d i t i o n a lc l a s s i f i c a t i o nk n n c l a s s i f i c a t i o na l g o r i t h mn e e d st oc o m p a r et e s ts a m p l ea n dt r a i n i n gs a m p l es e te a c h t i m ea n dc a l c u l a t et h es i m i l a r i t y , f o rt h el a r g ec a l c u l a t i o n ，i tm a k e st h ek n nn o t s u i t a b l ef o rr e a l t i m eh i g hd e m a n ds p a mf i l t e r i n gs y s t e m i nt h i sp a p e r ，t h ei n a d e q u a c yo fk n na l g o r i t h mi sp r o p o s e dt oi m p r o v ea n dt o d e s i g nab i a sd e p e n d e n tc h a r a c t e r i s t i c si n t oa c c o u n ts i m i l a r i t ya n ds i m i l a r i t yb a s e d o nt h ea v e r a g en u m b e ro fk n na l g o r i t h m f i r s t l y , b yc a l c u l a t i n gt h ea v e r a g e s i m i l a r i t yr a t h e rt h a ns i m i l a r i t yt or e p r e s e n tt h ec l a s so fw e i g h t s ，a l g o r i t h mt a k i n g i n t oa c c o u n tt h en u m b e ro fs a m p l e ss i m i l a rt ot h ei m p a c to nt h ec l a s s i f i c a t i o n i i i 改进的k n n 算法在过滤垃圾邮件中的应用研究 p e r f o r m a n c e ；s e c o n d l y ，t h ei n t r o d u c t i o no ft w op a r a m e t e r st or e p r e s e n tt h e i rp a r t i a l d e p e n d e n c es p a r ec h a r a c t e r i s t i c s ；f i n a l l y ，i no r d e rt os o l v et h el a r g ec a l c u l a t i o no f k n n a l g o r i t h m ，t h ep a p e rb yt h eo r i g i n a ls a m p l ei n t oas m a l lc l a s s ，a n dc a l c u l a t et h e c e n t e rv e c t o ro fe a c hs u b c l a s so ft h ec l a s st or e p r e s e n tt h eo r i g i n a lt r a i n i n gs a m p l e s t oe s t a b l i s hc l a s s i f i c a t i o nm o d e l ，w h i c hi se q u i v a l e n tt ot h el a r g es a m p l ei n t oas m a l l s a m p l e ，r e d u c i n gt h en u m b e ro fc o m p a r i s o n s ，a n dg r e a t l yr e d u c e st h ea m o u n to f c o m p u t a t i o no fk n nc l a s s i f i c a t i o na l g o r i t h m e x p e r i m e n t ss h o wt h a tt h ek n n a l g o r i t h mw i t ht r a d i t i o n a lc o n t r a s t ，t h ep r o p o s e da p c - k n na l g o r i t h mi sa p p l i e dt o s p a mf i l t e r i n g ，w i t hh i g ha c c u r a c y ，l o wf a l s ea l a r mr a t e ，e t c ；a n dc a na c h i e v eb e t t e r s p a mf i l t e r i n g ，p l a y e dap r o t e c te m a i lu s e r s ，a n ds a v eb a n d w i d t ha n do t h e re f f e c t s k e yw o r d s ：s p a m ；k n na l g o r i t h m ；p a r t i a ld e p e n d e n c e ；c a t e g o r yc e n t e rv e c t o r i v 硕士学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要u a b s t r a c t i i i 插图索引：v i i 附表索引v i i i 第1 章绪论1 1 1 研究背景与意义l 1 2 国内外研究现状和热点3 1 2 1 垃圾邮件简介3 1 2 2 垃圾邮件研究现状4 1 2 3 小结6 1 3 研究内容。一6 1 4 论文结构安排：6 第2 章垃圾邮件过滤技术的研究基础8 2 1 电子邮件的工作原理8 2 2 邮件传输协议1 0 2 3 邮件的特征选取与提取1 1 2 3 1 中文分词1 1 2 3 2 特征向量空间1 3 2 3 3 特征项的提取1 4 2 4 基于内容的垃圾邮件过滤相关技术15 2 5 小结2 0 第3 章k n n 算法的改进与实现2 1 3 1 k n n 算法基本原理一2 l 3 2 基于平均相似度和相似样本个数的k n n 算法2 2 3 3 基于偏依赖特性的k n n 算法设计2 4 3 3 1 偏依赖特性的引入2 4 3 3 2 偏依赖和k n n 算法的拟合2 4 3 3 3 惩罚因子的讨论2 5 3 4 改进的k n n 算法效率的提升2 6 3 5 改进的k n n 算法过滤系统的构建与实现2 8 v 改进的k n n 算法扭：过滤垃圾邮件中的应用研究 3 5 1 改进的k n n 算法过滤系统的构建2 8 3 5 2 改进的k n n 算法过滤系统的实现3 2 3 6 小结3 5 第4 章实验测试与分析：3 6 4 1 垃圾邮件的评价体系一3 6 4 2 实验环境3 6 4 3 实验数据3 7 4 4 实验设计3 7 4 5 实验的结果与分析3 8 4 5 1 特征维数对分类性能的影响实验一3 8 4 5 2 不同k 值对分类性能的影响实验3 9 4 5 3 不同，值的选取对分类性能的影响实验4 0 4 5 4 不同h 值的选取对分类性能的影响实验4 2 4 5 5 传统的k n n 算法和a p c k n n 算法的对比实验4 2 4 6 爿、结4 3 结论j 4 4 参考文献4 6 致j 射51 附录a 攻读硕士学位期间所参与的项目一5 2 v i 硕l 学位论文 插图索引 图1 1 用户收到垃圾邮件内容前十名2 图2 1 电子邮件传输过程9 图2 2i c t c l a s 系统中文分词流程图13 图3 1k n n 分类简单示意图一2 2 图3 2 传统k n n 算法分类示意图2 3 图3 3 训练样本的伪聚类过程2 7 图3 4 原始样本分成小类过程2 8 图3 5a p c k n n 分类算法整体流程图一2 9 图3 6a p c k n n 过滤系统模块规划图2 9 图3 7a p c k n n 过滤系统训练流程图3 0 图3 8a p c k n n 过滤系统分类流程图_ 3 l 图3 9a p c k n n 过滤系统工作流程图3 2 图3 1 0 特征提取算法流程图3 4 图4 1 不同特征维数三组实验的f 1 值对比3 9 图4 2 不同特征维数对分类结果的影响3 9 图4 3 不同k 值三组实验的f 1 值对比4 0 图4 4 不同k 值对分类结果的影响4 0 图4 5 不同7 值对正确率的影响一4 l 图4 6h 值对分类结果的影响4 2 图4 7 不同h 值a p c k n n 和k n n 的f 1 值对比4 3 图4 8 不同h 值a p c k n n 和k n n 的分类时间对比4 3 v i i 改进的k n n 算法在过滤垃圾邮件中的应用研究 附表索引 表2 1 邮件头的常用字段及其说明一一9 表2 2 几种自动分类算法的比较1 9 表2 3 四种分类算法比较1 9 表4 1 过滤垃圾邮件系统判定情况公布3 6 表4 2 不同) ，值对分类结果的影响4 1 v i i i 硕j ：学位论文 第1 章绪论 本章首先简述了基于内容的垃圾邮件过滤的研究目的及其意义，其次简要介 绍了过滤垃圾邮件技术国内外的研究现状，然后阐明了本文的主要研究内容，最 后给出了文章的组织结构。 1 1 研究背景与意义 在互联网技术迅速发展的背景下，电子邮件逐渐在人们的生活中扮演着不可 或缺的角色，给我们的工作和生活带来了极大的便利。但同时电子邮件中垃圾邮 件的泛滥也给电子邮件的用户和邮件运营商带来了烦恼。中国反垃圾邮件中心的 调查数据显示：2 0 0 9 年第一季度中国网民每周平均收到1 2 5 封垃圾邮件，占总 邮件数量的3 8 3 【lj ，且增长趋势日益明显。大部分的垃圾邮件以推销和欺诈为 主题，这在一定程度上给电子邮件用户的生活和工作造成了影响。 垃圾邮件是指未经用户许可而被发送垃圾邮件者强行发送到邮箱中的电子 邮件。这些垃圾邮件不是用户自己订阅的，也不是用户希望收到的，其中大部分 内容是广告、欺诈信息等。垃圾邮件的发送者主要通过网上收集或通过一定的途 径购买电子邮件的用户列表，然后盗用他人的服务器，利用他人的带宽强行将垃 圾邮件发送至用户的邮箱，一般是一次发送给多个用户。只要你是电子邮箱的用 户并且使用电子邮箱，就必然会受到垃圾邮件的骚扰，这种骚扰不仅影响到电子 邮箱的用户，更对正常的互联网通信造成困扰，给i n t e r n e t 的正常运行带来了危 害。 电子邮件的使用是免费的或者说是低成本的，例如网易邮箱就是提供给用户 免费注册使用，用户只需交纳一定的宽带费。但也正是其低成本、匿名性等特点， 使得越来越多的个人、企业采用发送垃圾邮件的方式进行产品广告、钓鱼攻击、 欺诈等违背电子邮件用户自身意愿的违法行为。专业i t 安全与保护公司s o p h o s 的高级技术顾问g r a h a mc l u l e y 表示，网络犯罪者受金钱等利益的驱使，除了向 电子邮箱用户发送垃圾邮件进行商品广告骚扰用户外，更严重的是窃取用户的账 号、密码等个人敏感信息。今年以来，垃圾邮件数量有上升的趋势，特别是欧洲 的垃圾邮件数量呈现了明显的增长趋势【2 】。发送电子邮件成本低的特点只是相对 于这些广告商而言，而互联网服务提供商、电子邮件运营商和收到垃圾邮件的用 户却承担了其他的成本。目前垃圾邮件所造成的危害主要有： ( 1 ) 影响电子邮件用户的日常工作与生活 随着i n t e r n e t 的飞速发展，使用电子邮箱的人越来越多，并随着使用时间的 改进的k n n 算法在过滤坨圾邮件中的应用研究 增长，电子邮箱中垃圾邮件的数量也随之增长，用户要花费时间和精力来处理这 些垃圾邮件；同时垃圾邮件还会占用电子邮箱空间，如果不及时进行清理，就可 能会影响正常邮件接收，在一定程度上影响了用户的工作和生活。从社会层面来 说，用户花费在垃圾邮件中的时间也是社会上一笔宝贵的财富。 图1 1 是中国互联网协会垃圾邮件研究中心调查显示的今年第一季度普通用 户收到的垃圾邮件的内容j 。从图中可以看出，在用户收到的垃圾邮件中，内容 为“零售业推销”的邮件数量占51 2 ，其次是“欺诈类”和“旅游、交通业推销”， “欺诈类 占3 3 7 ，比上期调查结果增长了5 ，必须引起重视。这说明了垃 圾邮件不仅给我们带来了烦恼，如果用户稍不注意，点击那些欺诈性的邮件，就 会给用户带来一定的经济损失和精神损失。 零售业推销 欺诈类 旅 6 ，交通业推销 互联网产品或服务推广 房地产推销 教育培训类 反动、段治谣言 琏法出售票据、证件 计算机瘸孽 垒融傈睑业推销 用户收到垃圾郄件内容赘十名 o l o 2 0 3 0 4 0 5 0 6 0 n = 6 9 4 0 中匿互联髑协会反垃圾邮件串心( w w w a n t i - 印a m 。a a ) 2 0 1 0 0 4 图1 1 用户收到垃圾邮件内容前十名 f i g 1 1t h et o p1 0o fs p a mc o n t e n tu s e r sg e t ( 2 ) 影响互联网的正常运行 垃圾邮件是没有任何价值的信息邮件，虽然一封垃圾邮件对于互联网的运行 几乎没有任何影响，但是当数以亿计的垃圾邮件在网络中穿梭时，就会严重影响 网络的正常运行。s o p h o s 发布的最新统计报告显示，在2 0 10 年第二季度，来源于 美国的垃圾邮件数量占全球垃圾邮件总量的15 2 ，比第一季度增长了1 6 ，仍 居世界首位1 3j 。 从邮件运营商的角度考虑，如果有大量的垃圾邮件不停的往邮件服务器中发 送并接收，就会导致花巨资购买的邮件服务器的大部分空间被垃圾邮件占用。不 仅严重浪费了服务器的存储资源，也浪费了运营商大量的人力物力成本进行维 2 硕上学位论文 护，还给用户带来了不好的影响。对用户来说，不仅浪费了时间，而且在使用过 程中带来了诸多不便。结果可想而知，用户弃用邮箱，用户数减少，运营商的付 出没有得到应有的回报。 从网络运营商的角度考虑，当数以亿计的垃圾邮件在网络中来回发送、接收 时，会占用很大的带宽资源，严重时会造成网络拥挤、堵塞。就目前中国的网络 状况来看，现在的网络带宽资源也是非常有限的，无法满足日益增长的信息、文 化、娱乐等网络应用的需要。如果有大量的垃圾邮件在网络中，造成网络堵塞， 不仅会影响网络上其他的应用，而且还会增加运营的成本。二十一世纪已经是信 息时代，当信息的应用出现阻碍时，就会严重影响国家经济社会的发展。 因此，垃圾邮件会影响互联网的正常运行，阻碍信息时代经济、社会的发展。 ( 3 ) 成为黑客发送病毒、木马的工具 如图1 所示，以计算机病毒为内容的垃圾邮件已经占了1 7 2 ，进入垃圾邮 件内容的前十名【l 】。这说明垃圾邮件已经成为黑客发送病毒和木马的主要平台。 用户只要点击病毒程序，它就可能在用户电脑自动进行安装、执行，轻则加重 c p u 的负担，使电脑运行速度下降，影响用户的工作；重则使系统崩溃、窃取用 户的银行卡号、密码以及其他敏感信息等，造成严重后果。最终造成病毒的泛滥， 危害互联网的正常运行。例如，2 0 0 8 年，出现一次典型的黑客攻击事件：黑客利 用微软办公软件e x c e l 存在的漏洞，编制了具有病毒的e x c e l 文件，利用电子邮件 的方式发送给用户，当用户打开此e x c e l 文件时，病毒就会立刻在用户的电脑中 自动运行，同时该电脑就会被黑客所控制，进而获取用户的个人隐私等信息。 随着电子邮件在日常生活中的普及，作为其副产品的垃圾邮件也层出不穷， 其目的明确：发送广告、诈骗或者钓鱼站点的链接等，其发送量大，给用户带来 损失、堵塞网络，对互联网的正常运行构成了巨大威胁。如果不能及时采取有效 措施来防范垃圾邮件，就会使用户对电子邮件使用的信任度逐渐降低，最终导致 所有的互联网用户都受到伤害，从而对人们的正常工作、生活造成极大的影响。 因此，研究垃圾邮件的过滤方案具有重大意义。 本文的研究目的是对基于内容的垃圾邮件过滤算法进行研究，并对其中应用 广泛、效果较好的k n n 算法进行改进。最终实现垃圾邮件的过滤，减少垃圾邮 件对用户的骚扰，维护电子邮件以及互联网的正常运行，提高电子邮件的使用率， 这在一定程度上减少了电子邮件供应商以及国家的经济损失，对我国互联网的健 康发展有着广泛而深远的意义。 1 2 国内外研究现状和热点 1 2 1 垃圾邮件简介 目前基于商业利益的驱使，很多广告公司、企业或者犯罪分子发送低成本的 改进的k n n 算法在过滤垃圾邮件中的应用研究 垃圾邮件至用户的电子邮箱，给用户造成困扰，妨碍了网络的正常运行。 垃圾邮件最早起源于美国，英文一般称为s p a m ，是互联网发展到一定程度 必然产生的副产品。其主要内容是商业广告、欺诈信息、病毒和其他一些与用户 无关的信息。其发送方式是批量的，一次性给多个电子邮箱用户发送垃圾邮件。 垃圾邮件的发送者主要是盗用别人的服务器，使用他人宽带发送垃圾邮件，成本 是由互联网运营商或者收件人承担。这和我们平时在街上收到的宣传单是不一样 的，这些宣传单也是以商业广告为目的，但是它的印刷、分发等成本确是由产品 公司自己承担，这可能是垃圾邮件比现实中的宣传单更受到谴责的原因。 垃圾邮件的定义在国际上没有一个统一的标准。在反垃圾邮件规范中中 国互联网协会对垃圾邮件给出了这样的界定【l 】： ( 1 ) 收件人事先没有提出要求或者不同意接收的广告、电子刊物以及各种形 式的宣传邮件。 ( 2 ) 收件人无法拒收的电子邮件。 ( 3 ) 隐藏发件人身份、地址、标题等信息的电子邮件。 ( 4 ) 含有虚假的信息源、发件人、路由等信息的电子邮件。 近年来，由于发送有病毒、木马的邮件导致安全事件时常发生，数量也不断 的增加，由于其特征基本与垃圾邮件符合，因此也归为垃圾邮件。 实际上判断一封电子邮件是否为垃圾邮件没有确切的界定，因为同一邮件对 不同的用户影响也不同，其判定结果肯定会存在差异。但大部分的垃圾邮件还是 存在一些共同特点：都是不请自来的具有某些商业目的或者政治目的；为了共同 的目的，垃圾邮件发送者和一些企业联合，发送具有商业广告、非法信息的邮件； 发送不是一封两封，而是通过一定的途径，获取电子邮件的用户列表，批量发送。 1 2 2 垃圾邮件研究现状 从19 9 4 年1 2 月大家接受s p a m 代表垃圾邮件时开始，全世界就进入了反垃圾 邮件的斗争中。反垃圾邮件技术就是在和制作垃圾邮件技术的不断斗争中发展起 来的。所谓“道高一尺，魔高一丈”的不断较量，反垃圾邮件技术也有了不同历程 的发展，从传统的反垃圾邮件技术，比如：基于i p 的黑名单或者白名单技术的反 垃圾邮件；到现在的基于内容的反垃圾邮件技术，主要有基于规则和基于统计的 两种过滤算法；比较新的技术是基于行为的过滤垃圾邮件技术。现在还出现了一 些技术的相互集成，将某两种或几种技术结合在一起实现更好的过滤垃圾邮件。 在实际应用中，不同的技术各有优缺点。下面就从这几方面来了解一下垃圾邮件 的研究现状： ( 1 ) 传统的垃圾邮件过滤技术 对于传统的反垃圾邮件过滤技术来说，最为典型的就是基于黑白名单的过滤 技术，它是最早也是最常用的一种技术。黑白名单为反垃圾邮件技术提供了强有 4 硕j j 学位论文 力的支持，在黑名单中的任何邮件都是垃圾邮件，可以直接删除或者放到垃圾邮 件夹中；反之，在白名单中的任何邮件都是正常邮件，允许通过。黑白名单的判 断依据可以是基于i p 地址，也可以是d n s ，它们的原理类似。对i p 地址的黑白名 单过滤系统来说，当用户收到一封新的电子邮件时，过滤系统对邮件头部发送方 的i p 地址进行实时检查，如果这个i p 地址在白名单中，就认为是正常邮件，进行 正常接收；反之，如果是在黑名单中，则进行删除或者直接拒绝。 基于黑白名单的过滤技术比较简单、明确，并节约系统资源；但是它的正确 率不高，当接收的邮件不在黑白名单库中，则容易造成误判，并且需要对黑白名 单库不断进行更新和维护。世界上存在一些反垃圾邮件组织不断对黑白名单库进 行更新和管理，并且可以提供给互联网上服务提供商使用，用来拒绝垃圾邮件。 另外，用户自己也可以提供黑白名单列表。 ( 2 ) 基于人工规则的过滤技术 基于人工规则的过滤技术也是传统过滤技术中的一种，是人工根据一定的规 则进行设置的。一般来说，过滤规则主要从以下几个方面进行设置：关键词匹配、 信头分析、群发策略以及邮件内容的其它特征等。系统根据这些规则对邮件进行 检测。文献【4 】主要是研究关键词匹配的设置规则，在传统的过滤技术基础上提 出了一种改进的关键词匹配算法。该算法首先找出关键词的不同变形体，然后将 找到的变形体和目标文本进行匹配。它的优点是灵活性和执行效率比传统的关键 词匹配算法高。基于人工规则的过滤方法执行效率比较高，并且人工设置的这些 规则可以和多人、多服务器共享，具有很强的推广性。但这种方法的过滤规则都 是由人工创建和维护，受人为因素的影响较大，因此对用户提出的要求较高。 ( 3 ) 基于内容的垃圾邮件过滤技术 基于内容的垃圾邮件过滤技术是从邮件的主题和正文来分析判断是否为垃 圾邮件，主要是将机器学习中的一些算法应用到垃圾邮件过滤中，分为基于规则 的和基于统计的两种主要技术。基于规则的方法主要是在训练阶段生成显式规则 1 5 】。该方法首先对训练样本进行学习，然后归纳总结出具有规律性的内容形成规 则，这种方法的优点在于生成的规则便于理解。但在某些规律性不明显的领域其 效果不尽人意。这种基于规则的方法常见的有决策树6 1 、b o o s t i n g 7 1 、r i p p e r 8 1 和r o u g hs e t s 别等。而基于统计的方法在训练过程生成的是隐式规则【5 1 。按照这 些规则对邮件正文的内容进行分词处理，再根据一定的算法提取邮件特征，将邮 件向量化；在训练阶段将训练样本中的邮件作为输入，对文本分类器进行训练， 然后利用训练后的分类器对邮件进行分类，最终实现垃圾邮件的过滤。常见的统 计方法有k 个最近邻法( k n n ) 1 0 】、支持向量机( s v m ) 【1 1 】和贝叶斯( b a y e s ) 等。本 文在2 4 节中对基于内容的垃圾邮件过滤的相关技术进行介绍。 基于内容的垃圾邮件过滤技术主要是通过分析垃圾邮件的内容，能够及时获 r 一 改进的k n n 算法在过滤垃圾邮件中的应用研究 得垃圾邮件的特征和变化，是一种精确的垃圾邮件过滤技术【1 2 】。与其他成熟的 过滤技术相比较，在识别垃圾邮件方面有较高的召回率和准确率，目前该技术是 识别垃圾邮件的主要手段。然而该方法的准确性还要依赖于大量的训练样本，因 此最好能够通过自我学习来弥补自身的不足。 ( 4 ) 基于行为的垃圾邮件过滤技术 我国在2 0 0 5 年提出了基于行为的垃圾邮件过滤技术。由于垃圾邮件发送者的 目的不同、一i i , 理不同所造成的行为也不尽相同，这种技术是通过对这些行为特征 建立识别模型来区分垃圾邮件和正常邮件，而不是考虑邮件内容的本身。文献 13 】 对邮件在接收时间、发送过程、每封邮件的收件人数量、邮件大小的分布等方面 的差异进行分析，据此来判断邮件是否是垃圾邮件。国内，对于垃圾邮件发送行 为规则研究也用到了数据挖掘方法【l4 1 。该技术不需要对内容进行分析，节省了 网络带宽，准确率高，但也可能存在误判，造成危害。 虽然上述的过滤技术都发挥了很大的作用，但是每一种单独的技术都有自己 的缺点，都有一定的漏报率和误报率。因此有的研究员利用集成的方法将两种或 几种过滤算法进行集成来提高垃圾邮件过滤的准确率。文献【1 5 】就是将具有很强 学习能力的支持向量机作为分量学习机应用到集成学习中。重点训练容易被 s v m 错误分类的样本，通过反复迭代中多次学习该类样本来降低错误分类率。 1 2 3 小结 上述主要介绍了各种过滤技术的工作原理及其研究现状，在某些方面还是有 不尽入意的地方。比如：误报率比较高，这就会造成一封正常邮件被误判为垃圾 邮件，对用户来说损失是比较大的，最终会造成用户的不信任；其次是实时性和 及时性等问题。本文通过对k n n 算法进行改进提高分类的性能和效率，然后将 其应用于基于内容的垃圾邮件过滤系统，达到更好的垃圾邮件过滤效果。 1 3 研究内容 本文对反垃圾邮件的相关技术进行研究，分析垃圾邮件的主要特点和危害， 同时详细分析当前基于内容的垃圾邮件过滤技术，针对基于机器学习的k n n 分 类算法进行了深入的研究。针对传统的k n n 分类算法简单的通过相似度之和进 行分类，忽略了电子邮件本身的偏依赖特性以及计算量大的不足，本文对传统 k n n 算法的这三个缺点进行改进，提出以及实现了a p c k n n 算法。实验数据 表明改进后的k n n 算法不管是在性能上还是在效率上都具有一定的提高。 1 4 论文结构安排 第一章先介绍了本文的选题背景和科学意义，进而简要的介绍了垃圾邮件的 定义，从国内外两个方面阐述了垃圾邮件的研究现状和热点。最后给出了本课题 6 硕1 ：学位论文 的组织结构。 第二章主要是对电子邮件的预处理进行概述。首先概述了电子邮件的工作原 理和邮件的传输协议，然后详细介绍了邮件的特征选取，包括电子邮件的中文分 词技术，特征向量空间的构造以及特征的提取算法，并概括了各种特征提取算法 的优缺点。最后介绍了基于内容的反垃圾邮件的一些基于机器学习的常见过滤算 法，并分析了它们的优点及缺点。 第三章对k n n 算法进行详细的介绍，并提出了k n n 算法的改进方法。首 先分析了传统的k n n 分类算法的优缺点，针对其不足，提出了改进后的算法 a p c k n n 分类算法。并详细介绍了其关键部分的实现内容。 第四章在第三章的基础上，对前面的改进算法进行仿真实验。通过分析得出 相应的结论。 最后，对全文进行总结并指出下一步工作。 7 改进的k n n 算法在过滤垃圾邮件中的戍用研究 第2 章垃圾邮件过滤技术的研究基础 电子邮件是i n t e r n e t 上重要的通信手段，是应用最广的服务之一。它可以让 用户实现和世界的任何一个角落的用户联系，同时还可以订阅大量的诸如体育、 新闻等专题邮件，实现信息的搜索。虽然电子邮件系统和现实世界中的邮政系统 是类似的，但它有其自身独特