（计算机软件与理论专业论文）惰性学习分类法在垃圾邮件过滤中的应用研究.pdf

上海师范大学硕士研究生学位论文 摘要 摘要 惰性学习( l a z yl e a r n e r ) 分类法有别于决策树归纳、贝叶斯分类、基于规 则的分类、后向传播分类等的急切学习分类技术。当给定训练集时，惰性学习法 只是简单的存储它，而不像急切分类法一样马上构造范化模型( 即分类) ，要一 直等到给定一个检验元组时才对训练集进行范化，进而根据训练元组的相似性对 检验元组进行分类。惰性学习分类法的最大优点就是自然地支持增量学习，并且 能对超多边形形状的复杂决策空间建模，或者说其比较适合对高维数据集进行分 类。 本文在分析比较了当前主要的垃圾邮件过滤技术后，实现了将一种典型的惰 性学习分类法，即k 最近邻( k n n ) 分类法，运用于垃圾邮件过滤。k 最近邻分 类法自然支持增量学习的特性刚好能满足垃圾邮件过滤中要求训练集不断更新 的要求。同时，当k 的取值足够大的时候，其分类准确性也很高，接近于贝叶斯 分类。另外，本文还针对k n n 分类法计算量比较大的缺点进行了改进，即利用 一种鲁棒的层次聚类方法r o c k 聚类，对训练集先进行聚类，以达到压缩数据 集的目的，从而减少后续分类的计算量。 为了验证k 最近邻分类法的可行性，这里基于v b 6 0 + a c c e s s 2 0 0 3 平台和 s p a r e 数据集设计了一个“k n n 分类器”，以便比较在不同参数下的分类器性能。 实验结果表明：这种由于采用惰性学习分类法而自然地支持增量学习的分类器， 其准确率比较理想；同时，r o c k 聚类对数据集的压缩在不影响后续分类准确 率的前提下能大大地减少k n n 分类过程中的计算量。 关键词：垃圾邮件过滤，分类，惰性学习，r o c k 聚类 上海师范大学硕士研究生学位论文 摘要 a b s t r a c t l a z yl e a r n e rc l a s s i f i c a t i o ni san e wt y p ec l a s s i f i c a t i o nw h i c hi sd i f f e r e n t t h a nt h o s ee a g e rl e a r n e rm e t h o d sl i k ec l a s s i f i c a t i o nb yd e c i s i o nt r e ei n d u c t i o n ， b a y e s i a nc l a s s i f i c a t i o n ，a s s o c i a t i o n - b a s e dc l a s s i f i c a t i o na n dc l a s s i f i c a t i o nb y b a c kp r o p a g a t i o n 。t h ee a g e rl e a r n e rc l a s s i f i c a t i o nb u i l d st h em o d e li n s t a n t l y w h e ni ta c c e p t sa s a m p l es e t ，w h i l el a z yl e a r n e rc l a s s i f i c a t i o nj u s ts t o r e si ta n d d o e sn o tb u i l dam o d e lo rc l a s s i f yt h es a m p l eb a s e do nt h es i m i l i t u d eu n t i li t a c c e p t sat e s t i n gs a m p l e t h eb i g g e s ta d v a n t a g eo fl a z yl e a r n e rc l a s s i f i c a t i o n i st h a t ，i ts u p p o r t si n c r e m e n t a ll e a r n i n g n a t u r a l l ya n dc a nb u i l dam o d e lo f c o m p l i c a t e dd e c i s i o ns p a c ew h i c hi sa nu l t r ap o l y g o n t h i sp a p e ri m p l e m e n t e da d o p t i n gat y p i c a ll a z yl e a r n e rc l a s s i f i c a t i o n - k - n e a r e s tn e i g h b o rc l a s s i f i e r i n t os p a m sf i l t e r i n ga f t e rw ea n a l y z e dt h e c u r r e n tm a j o rs p a mf i l t e r i n gt e c h n i q u e s a sw ek n o w , i n c r e m e n t a ll e a r n i n gi s s u p p o r t e db yk - n e a r e s tn e i g h b o rc l a s s i f i c a t i o nn a t u r a l l y , i ti sj u s tt om e e tt h e r e q u i r e m e n t so fu p d a t i n gt h et r a i n i n gs a m p l es e ti nt h ec o u r s eo ff i l t e r i n g s p a m s a tt h es a m et i m e ，t h ec l a s s i f i c a t i o na c c u r a c yo fk n ni sa l s oh i g h ，j u s t c l o s e rt ot h eb a y e s i a nc l a s s i f i e r , w h e nt h ev a l u eo fki s l a r g ee n o u g h i n a d d i t i o n ，t h i sp a p e ra l s oi m p r o v e dk n nb yc l u s t e r i n gt h ed a t as e tu s i n gr o c k b e f o r ec l a s s i f y i n g a n dt h e n ，w ec a nr e d u c ec o m p u t a t i o n a ll o a do ft h e f o l l o w i n gc l a s s i f y i n g i no r d e rt ov e r i f yt h ef e a s i b i l i t yo fk n na n dc o m p a r et h ep e r f o r m a n c eo f d i f f e r e n tc l a s s i f i e r sw i t hd i f f e r e n tp a r a m e t e r s ，id e s i g n e dak n nc l a s s i f i e r b a s e do nv b 6 0a n dad a t as e tn a m e d s p a m t h ee x p e n m e n t a lr e s u l t ss h o w t h a t ，t h ea c c u r a c yo fk n nc l a s s i f i e ri sg o o da n dr o c kc l u s t e r i n gc a ng r e a t l y r e d u c ec o m p u t a t i o n a i i o a do fk n nc l a s s i f i c a t i o no nt h ep r e m i s et h a tr o c k s h o u l dn o tr e d u c ek nn sa c c u r a c y 。 k e y w o r d s ：s p a mf i l t e r i n g ，c l a s s i f i c a t i o n ，l a z yl e a r n e r , r o c kc l u s t e r i n g 上海师范大学硕士研究生学位论文 声明 学位论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 储答名：互别 日期唧红岁1 7 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 储样：卅刷磁径陬醐彤莎岁| 上海师范大学硕士研究生学位论文 第一章绪论 第一章绪论 1 1 论文研究的背景 随着i n t e r a c t 技术的发展，电子邮件( e m a i l ) 作为它最初的也是当前最流 行的应用得到了广泛的认可。在中国，每个互联网个人邮箱平均每周收到3 0 封 电子邮件。但是，电子邮件在给大家带来方便的同时也产生了一些问题，那就是 垃圾邮件。 由中国互联网协会反垃圾邮件中心承办的2 0 0 8 年第四次中国反垃圾邮件状 况调查结果显示：中国网民平均每周收到垃圾邮件数量为1 7 5 5 封，占到邮件总 数的5 7 8 7 。而在之前的几年中，这个比例更高，最高的时候达到6 0 多。也就 是说，大家收到的邮件中的大部分是垃圾邮件。 垃圾邮件危害极大，它会浪费用户时间，传播病毒，影响用户使用邮件的兴 趣。因此，遏止垃圾邮件就成为网络安全防护中的重要方面。 反垃圾邮件措施主要有两个方面，一个是政策措施，另一个是垃圾邮件过滤 技术。政策方面，2 0 0 4 年1 月3 0 日，公安部、教育部、信息产业部和国务院新 闻办部委联合发出关于开展垃圾电子邮件专项治理工作的通知，从而标志着 中国正式揭开反垃圾邮件战争的序幕。技术方面，现在也有很多非常成熟的垃圾 邮件过滤技术正在被使用和不断改进着，比如说：黑白名单、关键词过滤、贝叶 斯过滤等。 ， 但是，上述大部分的过滤技术都存在这样一个问题，就是形成判断模式的过 程( 既学习过程) 不支持增量学习。当有新类型的垃圾邮件出现或者垃圾邮件中 的垃圾信息被有意隐藏而排除在关键词词典之外时，上述过滤技术将可能无法将 其过滤，而需要人工过滤，并将其放入训练集，进行重新训练，从而形成新的判 断模式。这样就会严重影响过滤器的性能和效率。 基于此，本文尝试用一种自然地支持增量学习的惰性学习分类技术一k 最近 邻分类法一来实现垃圾邮件的过滤。 上海师范大学硕士研究生学位论文 第一章绪论 1 2 论文的研究思路及意义 当前对于垃圾邮件过滤技术的研究主要集中在以贝叶斯分类器为代表的基 于客户端的及内容的分类技术方面。其它的分类技术还有：决策树归纳、基于规 则的分类、后向传播分类、支持向量机和基于关联规则挖掘的分类，这些分类技 术都是急切学习法( e a g e rl e a r n e r ) 的例子。当给定训练集时，急切学习法将 在接收待分类的新元组之前构造泛化模型，此时学习后的模型已经就绪，并急于 对先前未见过的元组进行分类。 而惰性学习法( 1 a z yl e a r n e r ) 相反，当给定一个训练元组时，惰性学习法 简单地存储它，只有当看到检验元组时它才进行泛化，以便根据存储的训练元组 的相似性对该元组进行分类。 这里研究用一种典型的惰性学习分类法一k 最近邻分类法来对垃圾邮件进 行过滤( 分类) 。并预期能对该方法进行改进，克服该方法的一些不足之处。同 时设计一个k n n 分类器，通过实验验证该方法的可行性。 一般的分类算法分为两个过程：学习( 训练) 阶段和分类( 检验) 阶段。 急切学习分类法的大部分工作都集中在学习阶段，而分类相对来说是件很轻松的 工作；惰性学习分类法在做完训练数据的预处理后，更多的工作放在了分类阶段； 所以，为了提高惰性学习分类法的效率，我们应该尽可能地在数据预处理方 面多做点工作，“一劳永逸 地减轻分类时的工作量。所以这里研究的一个主要 方向就是希望能在数据预处理阶段对心n 算法做些改进。 基于k n n 方法的不足之处，这里所做的研究预期能在以下两方面做出改进： 1 、计算量大：然后以这n 个簇的簇中心作为后续k n n 分类的训练集进行 分类，这样可以大量减少分类过程的计算量。这里考虑用的聚类算法为r o c k ( r o b u s tc l u s t e r i n gu s i n gl i n k s ) 聚类，即基于链接的鲁棒聚类。 2 、利用多数决原则判断检验元组归属太过武断：结合多数决与相似度和两 种方法进行判断。这样更谨慎，结果更准确。这一部分将在4 3 4 介绍 通过以上的研究与实验，希望这种基于惰性学习分类法的过滤技术能在尽量 不降低分类器准确率和执行效率的前提下使分类器具有增量学习的特性。从而为 垃圾邮件过滤技术的研究提供一条新的思路。 2 上海师范大学硕士研究生学位论文第一章绪论 1 3 论文工作 论文的工作主要集中在以下四个方面： 1 、介绍了当前主流的垃圾邮件过滤技术的概念、特点和优缺点，并做了对 比分析。 2 、将惰性学习分类法k n n 应用到垃圾邮件过滤中，解决了现有垃圾邮件过 滤技术不支持增量学习的缺点，并对k n n 算法进行了改进。 3 、程序设计及代码编写。基于v b 平台实现了k n n 分类器。 4 、测试与评价。利用k n n 分类器，通过调整不同的输入参数，对分类结果 进行分析对比，得出结论。 根据上述主要工作，论文的章节安排如下： 第一章：绪论。介绍了垃圾邮件问题的现状，基于这个现状提出了论文的研 究思路，并且介绍了研究的主要工作和论文安排。 第二章：垃圾邮件过滤技术分析。介绍了当前垃圾邮件过滤技术的研究现状， 分析对比了当前主流垃圾邮件过滤技术的优缺点。 第三章：分类与k 最近邻分类法。主要介绍了分类的概念、分类在数据挖掘 中的地位、分类技术种类以及各种分类算法的性能和优缺点。而其中以k n n 分 类算法为介绍重点，同时提出了一些对k n n 分类法的改进。 第四章：k n n 分类器的设计与实现。本章在分析了k n n 分类器的功能后给 出了分类器的系统结构图和数据流程图，并介绍了每个模块的功能及实现方式。 第五章：实验与结构分析。这一章根据论文的主要关注点，设计出实验方案， 记录实验结果，并对结果进行了分析。 第六章：总结与展望。总结了论文的主要论点和主要工作，并对相关领域的 后续研究进行了展望。 3 上海师范大学硕士研究生学位论文第二章垃圾邮件过滤技术分析 第二章垃圾邮件过滤技术分析 2 1 关于垃圾邮件 在现今的日常工作生活中，垃圾邮件几乎无处不在，大家肯定不陌生，也都 有各自形象的理解。但是，对垃圾邮件的定义至今还没有一个比较明确的描述， 然而它们的诸多表征已经得到了业界人士的广泛的认可，例如：垃圾邮件通常是 未经收件人主动请求又无法拒收的、大量的邮件内容相似并且隐藏或伪造发件人 身份、地址、标题信息等。垃圾邮件的内容形形色色，常见的包括广告、色情信 息，还有病毒或蠕虫引起邮件深度扩散等诸多类型。由于垃圾邮件数量多，具有 反复性、强制性、欺骗性、不健康性或传播速度快等特点，严重干扰了人们正常 生活，浪费用户的时间、精力甚至造成很多额外的经济支出和信息安全隐患。因 此，垃圾邮件过滤技术的研究已经成为影响互联网发展的重要课题之一。 2 2 垃圾邮件过滤技术发展历史 回顾垃圾邮件过滤技术的发展历程，可以将其分为三个阶段： 一、触发阶段( 1 9 9 3 年一1 9 9 7 年) ：1 9 9 4 年1 2 月，s p a m 一词开始用于表 示垃圾邮件；1 9 9 5 年1 0 月，国际上开始为垃圾邮件设定专门的邮件帐户 a b u s e d o m a i n ，用于收集、讨论垃圾邮件；同时开始利用“黑名单 ( 把一些 已知的发送垃圾邮件i p 或邮件地址列入其中，用来过滤垃圾邮件) 技术实施反 垃圾邮件工作。 二、推进阶段( 1 9 9 7 年1 9 9 9 年) ：1 9 9 7 年5 月，国际上成立了c a u c e ( c o a l i t i o na g a i n s tu n s o l i c i t e dc o m m e r c i a le m a i l ) 组织，主要从倡议立 法的角度出发，力图唤醒有志者共同参与，一起抵制垃圾邮件。1 9 9 8 年4 月， i n t e r n e t 协会i s o c 针对垃圾邮件问题召开了专项会议，讨论有效的实施垃圾邮 件过滤方式等等。在这一阶段中，许多国际组织和服务单位例如m a p s 、s p a n h a u s 、 o r b s s p a m c o p 也相继成立，对垃圾邮件问题( 尤其是对i s p ) 提出了很多建议和 解决方案。尤其重要的是，1 9 9 8 年我国成立了第一家开展垃圾邮件与反垃圾邮 件技术研究单位“中国教育与科研网紧急响应小组( c c e r t ) ，他们积极地与 国际组织接触并建立联系，成为这一阶段我国接受和处理国际投诉的主要窗口。 4 上海师范大学硕士研究生学位论文第二章垃圾邮件过滤技术分析 三、发展阶段( 1 9 9 9 年至今) ：1 9 9 9 年2 月，r f c 2 5 0 2 ，a n t i s p a m r e c o m m e n d a t i o n sf o rs m t 0m t a s 的正式发布标志着垃圾邮件过滤技术研究的蓬 勃发展。许多国际知名大学和研究机构都组织人员开始了垃圾邮件过滤技术的研 究。随着垃圾邮件过滤技术的发展和建立统一标准等工作的推进，这一研究领域 更是吸引了许多从事交叉学科研究的技术人员的关注。机器学习、神经网络和遗 传算法等先进的研究经验都被引入到这一领域。这一阶段的研究成果成为近几年 国内外开发反垃圾邮件产品的主要技术依据。本文要研究的k n n 分类法就是在 这一个阶段提出的。 2 3 现有技术分析 对垃圾邮件过滤技术的应用和研究在推进和发展阶段主要集中在三个方面： 其一，利用邮件地址、i p 或域名“黑白名单 进行的邮件限制或过滤。典 型应用诸如：结合d n s 的实时黑名单( r b l ) 过滤，用户自定义邮件黑白名单的 过滤方法等。 其二，基于数据挖掘技术进行的邮件过滤研究，利用文本分类与统计算法进 行垃圾邮件检测。比较有代表性的是贝叶斯过滤器。它是以自学习、自适应和极 高的准确率占据了过滤器这个领域的主导地位。而k 一最近邻分类法( k n n ) 就是 我将要采用的另一种文本分类法。 其三，基于垃圾邮件的特征分析、规则提取的规则匹配过滤方法。 s p a m a s s a s si n 就是其中一个典型代表。 下面就以上提到的各种过滤技术进行简要分析对比。 2 3 1 黑白名单 黑白名单是在垃圾邮件过滤技术发展的触发阶段就开始使用的一种主流技 术，它以已知的垃圾邮件( 合法邮件) 为经验基础，将垃圾邮件( 合法邮件) 的 邮件地址、d 地址及域名放入相应的“黑名单 ( 白名单) ，当接收到新邮件时， 优先放行白名单上的邮件，而将黑名单上的邮件过滤掉。如众所周知的实时黑名 z 单( r e a lb l a c kl i s t ) 。实时黑名单通过第三方提供的实时黑名单数据库可快速 检查发送d 地址的合法性，这样有利于垃圾邮件样本资源的共享，使得过滤器 可以过滤来自不同地域、不同领域的垃圾邮件，提高了过滤效率。 但是，这种黑白名单技术也有着显而易见的缺陷。 5 上海师范大学硕士研究生学位论文第二章垃圾邮件过滤技术分析 首先，最致命的是，它无法处理既不在白名单也不在黑名单上的邮件。而不 幸的是，绝大部分的邮件都是属于这一类的，因为你无法将所有可能给你发合法 邮件的发件邮箱地址放入白名单，而新的垃圾邮件发送者( 邮箱地址) 却是每天 在大量增加。所以，怎样处理这部分垃圾邮件就成为关键。 其次，垃圾邮件发送者会经常修改他们的i p 地址，并且采用一个广泛的i p 地址区间以逃避反垃圾邮件手段的检测。这样一些垃圾邮件采用的技术很容易就 逃过了黑名单的筛选。同时，盗用他人邮箱进行垃圾邮件传播的手段也使白名单 失去了作用。 最后，黑白名单的更新维护需要耗费大量的资源和时间成本。而且目前实时 黑名单提供者多为国际组织( 如大名鼎鼎的s p a m h a u s ) ，国内工p 地址错误列入 后投诉相对困难。 因此，在目前垃圾邮件技术层出不穷的情况下，单一的黑白名单过滤技术显 然已经力不从心。所以，在实际应用中，一般将黑白名单作为一种辅助的垃圾邮 件过滤技术。利用其执行效率高的优点，先过滤掉那些显性的垃圾邮件，减轻核 心过滤技术的负担。于是，黑白名单成为了现今过时而未被淘汰，并被广泛应用 的一种邮件过滤技术。 2 3 2 关键词过滤 关键词过滤是一种基于内容和规则的过滤技术。关键词过滤分两个步骤：第 一步，利用数据挖掘技术挖掘出频繁模式( 关联规则) ；第二步，匹配过滤。关 键词过滤可以识别包含特定关键字( 词) 的所有邮件，比如“免费”、“色情 等 在垃圾邮件中经常发现的词语。因为关键词过滤是基于邮件内容的，所以比起只 关注口地址等邮件外部特征的黑白名单来说，适应性更强，它可以阻断绝大多 数垃圾邮件。 但是，随着垃圾邮件数量的增加和形式的多样化，关键词过滤也逐渐暴露出 一些不足。 首先是关键词的选取越来越困难。因为垃圾邮件涉及到的内容越来越广泛，= 已经不仅仅局限在“免费”、“色情”等这些常见的违法信息上，现在的垃圾邮 件信息涉及广告、色情、反政府、病毒、非法链接等。再者，即使邮件内容相对 固定，选取什么样的关键词作为过滤依据也是相当繁复的工作。 6 上海师范大学硕士研究生学位论文 第二章垃圾邮件过滤技术分析 其次，内容伪装与替代。既垃圾邮件发送者在不影响读者理解的情况下将一 些垃圾关键次进行改造伪装，比如改成“免六费 。最近还出现了很多图片垃圾 邮件，他们以图片的形式发送，而不是用文本。这些图像之所以能够蒙蔽一些过 滤器是因为不太容易发现一个图像文件所含的内容是朋友生日聚会的照片、还是 内嵌某公司股票信息的图片。图片垃圾邮件还会加重电子邮件系统的负担，因为 每封图片垃圾邮件所占空间大约是普通垃圾邮件的7 5 倍。要过滤这样的垃圾邮 件，必须结合图象识别等技术，将“关键词概念扩展到包括图像特征在内的一 个范畴。这种技术在梭子鱼垃圾邮件防火墙上有集中的体现。 2 3 3 贝叶斯过滤 贝叶斯过滤以著名数学家托马斯贝叶斯( 英国，1 7 0 2 1 7 6 3 ) 命名，是一种 基于概率分析的可能性推论理论。贝叶斯过滤法强大，是阻断垃圾邮件最为精确 的技术，理想情况下过滤准确率可达到9 9 。是目前研究和应用最广泛的技术。 它通过比较待考察邮件中出现的词语在训练集中的垃圾邮件及合法邮件中的出 现概率来确定垃圾邮件的可能性。 为完成邮件的分类，需构造反映邮件是否是合法邮件的一组特征向量( x1 ， x 2 ，xn ) ，其中每个x i 可定义为最能体现合法或“垃圾 邮件特征的字、 词( 如“免费 、“f r e e ”、“欢迎”等) 或特殊的字符串( 如“! ! ! ”、“$ $ $ ) 。 这样对某个邮件x = ( x l ，x 2 ，x n ) 来说： f1 ，z ，所对应的词在邮件中出现 一1o ，x 。所对应的词在邮件中没有出现 邮件x 为垃圾邮件的概率为：( 公式2 1 ) f i p ( x ，= tc = “垃圾邮件，) 幸p ( c = “垃圾邮件，) 尸( c = “垃圾邮件防= 功= 上l 瓦夏= j 广一 类似地，计算出邮件x 是畲法邮件的概率尸( c = “合法邮件 l x = x ) 其中，c 是邮件x 的类别，p ( c = ”合法邮件”) 和p ( 置= t i c = “垃圾邮件，) ，即 贝叶斯网的条件概率表c p t ( c o n d i t i o n a lp r o b a b i l i t yt a b l e ) ，均可通过从 预分类的训练集中学习得到。 7 上海师范大学硕士研究生学位论文第二章垃圾邮件过滤技术分析 如果p ( c = “合法邮件”i x = x ) p ( c = “垃圾邮件”l x = x ) ，则判定x 是合法 邮件，否则为垃圾邮件。 贝叶斯过滤器的优点是准确率高，但也存在以下缺点： 第一，过滤准确性依赖大量的历史数据； 第二，当训练集中元组相对较少而属性相对较多时，会出现大量零值属性， 他们会消除其它属性对结果的影响。具体的，如果待检邮件x 中某个词x i 在训 练集中所有垃圾邮件中都没有出现，则j p ( 置= x tc = “垃圾邮件，) = o ，结果是 算出x 是垃圾邮件的概率为o ，就此判断这个邮件是合法邮件，这显然是不合理 的和武断的。所以，一般会在数据准备阶段对有零值的属性进行预处理。 第三，贝叶斯过滤是建立在属性条件独立性假设的基础上的，即认为属性 x ，( 这里理解成邮件中的关键字、词) 是相互独立的，而这种假设在实际应用中 经常是不成立的。比如，如果将“免费 和“f r e e ”同时作为考察属性，显然它 们在邮件中的出现与否是有某种相关性的。这样就一定程度上限制了它的应用领 域。 2 3 4 惰性学习分类法 惰性学习分类法就是本文重点研究的方法，这里将使用其中的一种典型方法 一k 最近邻分类法一来设计一个k n n 分类器，同时对该方法做出一些改进。k 最近 邻分类法以接近贝叶斯过滤的准确率和自然地支持增量学习的优点进入了本文 的研究视野。具体的算法、性能分析、方法改进以及编程实现安排在后面的第三 章和第四章进行详细介绍。 2 4 技术发展方向 时至今日，网民及各界人士对垃圾邮件造成的问题日益关注，网络服务商和 邮件运营商们纷纷提出了自己的技术方案：雅虎的“d o m a i n k e y s ”，它利用公 私钥加密技术为每个电子邮件地址生成一个唯一的签名，实现对邮件发送者的身 份验证；微软的“电子邮票 有偿发送邮件方案；。a o l 正在试验一种名为 “s e n d e rp e r m i t t e df r o m ”( s p f ) 的新电子邮件协议，禁止通过修改域名系统 ( d n s ) 伪造电子邮件地址。反垃圾邮件技术的研发和产品的推广也成为商家继 防火墙技术以及入侵检测技术之后的又一热点，各种反垃圾邮件产品基本上都对 8 上海师范大学硕士研究生学位论文 第二章垃圾邮件过滤技术分析 以上各阶段的研究技术进行了产品转化，也设计了一些基于s m t p 连接的动态过 滤规则，例如相同i p 的并发连接限制以及连接频度限制等等。然而，仅仅这样 做还不够，邮件过滤技术的研究还有待进一步拓宽思路。垃圾邮件的过滤技术必 然由单一基于静态规则和统计分类向着基于行为模式分析的动态过滤技术相结 合的方向进行转变，例如，可以考虑把网络流量的时空特性分析以及对通信连接 过程中的行为模式，尤其是异常行为模式识别和分析等技术手段结合起来综合利 用，开发新的研究路线。 随着业界对反垃圾邮件技术的进一步研究和普及应用，我们应该充分调动各 方的资源，共建、共享、共同研究、协调合作。针对我国的垃圾邮件情况，建立 协作式的反垃圾邮件技术体系是非常必要的：一方面，它将成为中国反垃圾邮件 公共服务管理体系的技术支撑平台，可以集成邮件信息分析、特征提取、整合取 证、分发等一系列的运算；另一方面，对垃圾邮件特征的分析，尤其是对多源的 信息分析、融合以及有效规则的生成需要调动大量的运算资源。采用协作的分布 式结构有利于资源的结构体系，也有利于对大规模的垃圾邮件泛滥进行快速响 应。当然，各节点间应当以可信连接或专用的安全通道进行通信，保证协调合作 的可靠性、有效性及安全性。 垃圾邮件是全球性的问题，且已经成为一种社会现象，单靠反垃圾邮件技术 的发展或是纯粹的技术手段是无法解决的，还是应当采用管理与技术相结合的 方式，以先进的技术手段为基础，以完善的管理制度和法律法规为依托，对社会 各主体的邮件活动进行规范，通过建立国家级的反垃圾邮件公共服务体系，完善 国内的垃圾邮件举报平台，促进各运营商和邮件服务商的协调合作，再次推动垃 圾邮件过滤技术的更新和快速发展。 9 上海师范大学硕士研究生学位论文第三章分类与k 最近邻分类法 第三章分类与k 最近邻分类法 本章介绍了分类和预测的相关概念以及一些常见的分类算法；并对k 最近邻 分类法进行了着重分析；提出了对k 最近邻分类法的一系列改进。 3 1 分类和预测 分类和预测是两种重要的数据分析形式。 分类的任务就是要确定对象属于哪个预定义的目标类。分类问题是一个普遍 存在的问题，有许多不同的应用。除了本文研究的垃圾邮件过滤外，还有：根据 核磁共振扫描的结果区分肿瘤是恶性还是良性的，根据星系的形状对它们进行分 类，根据动物的多种特征属性判断它们的类属 而预测的任务是根据已知( 历史) 数据来预测未知( 将来) 的数据。比如， 根据历史环境数据来预测未来几天的天气，超市通过分析历史销售记录预测下一 阶段的进货量等。 事实上，我们是可以将分类和预测两个概念统一起来的。因为，分类就是预 测对象的类标号( 离散的、无序的) 。从这个角度讲，分类是一种特殊的预测。 我们可以对银行贷款的历史数据建立预测模型，预测当前的某一笔贷款的风险大 小( 连续值) ，也可以建立相应的分类模型，对这笔贷款进行风险分类( 高、中、 低，离散值) 。所以，目标属性( 上面例子中的“风险 ) 的类型是分类和预测的 关键特征。 这一节重点介绍分类的相关概念。 3 1 1 分类的一般方法 分类技术是一种根据输入数据集( 训练集) 建立分类模型，并用这个模型来 判断未知新样本的类别的系统方法。因此，分类任务一般分成两个阶段：学习( 训 练) 阶段和分类( 检验) 阶段。 1 0 图3 1 ( a ) 学习阶段 上海师范大学硕士研究生学位论文第三章分类与k 最近邻分类法 匡一叵一犀 图3 1 嘞分类阶段 分类技术都使用一种学习算法确定分类模型，该模型能够很好地拟合输入数 据中类标号和属性集之间的关系( 函数) 。学习算法得到的模型不仅要很好地拟 合输入数据，还要能够正确地预测未知样本的类标号。因此，学习算法的主要目 标就是建立具有很好泛化能力的分类模型，即建立能够准确地预测未知样本类标 号的模型，而整个分类任务的工作量也主要集中在这一阶段。可以说，学习阶段 的工作决定了分类的效率和性能，学习算法的选择至关重要。 3 1 2 准备分类数据【1 】 为了提高分类过程的准确性、有效性和可规模性，有必要先对样本数据做下 列预处理步骤： ( 1 ) 数据清理：是旨在消除或减少数据噪音( 例如，使用平滑技术) 和处理 遗漏值( 例如，用该属性最常出现的值，或根据统计，用最可能的值替换遗漏值) 的数据预处理。尽管大部分分类算法都有处理噪音和遗漏值的机制，但该步骤有 助于减少学习时的混乱。 ( 2 ) 相关性分析：数据中许多属性可能是冗余的。例如，记录银行贷款星期 几签署的数据可能与应用的成功不相关。此外，还有一些属性之间是强相关的， 比如属性a 1 和a 2 之间有类似a 1 - - - f ( a 2 ) 的关系，f i x ) 是多项式函数。在这种情 况下，可以使用相关分析和特征子集选择的方法，探查对分类任务不起作用的属 性。因为包含这些属性可能减慢甚至误导学习步骤。 理想地，用在相关分析上的时间，加上从“压缩的 结果子集上学习的时间， 应当少于由原来的数据集合上学习所花的时间。因此，这种分析可以帮助提高分 类的有效性和可规模性。 ( 3 ) 数据变换与规约：数据可以泛化到较高层概念。对于连续值属性，这一 步非常有用。例如，属性i n c o m e 的取值可以泛化为离散的区间，如l o w ，m e d i u m 和 h i g h 。类似地，标称值，如s t r e e t ，可以泛化到高层概念，如c i t y 。由于泛化压缩 了原来的训练数据，学习时的输入，输出操作将大大减少。 上海师范大学硕士研究生学位论文第三章分类与k 最近邻分类法 除了属性的泛化，数据也可以规范化。特别是在学习阶段使用神经网络或涉 及距离度量的方法时。规范化涉及将属性的所有值按比例缩放，使得它们落入较 小的指定区间，如1 o 到1 0 ，或o o 到1 o 。例如，在使用距离度量的方法中， 这可以防止具有较大初始域的属性( 如i n c o m e ) 相对于具有较小初始域的属性( 如 “工龄”) 权重过大。 在第四章中会介绍的本次实验用的数据源s p a m b a s e 中的数据就预先进行了 规范化，数据取的是关键词( 属性) 在样本邮件中出现的百分数，范围在o 到 1 0 0 。 3 1 3 分类的评估标准 上面介绍了几种常见的分类技术，也对它们的技术特点、性能有了大概的认 识。但是，当面对某个实际应用时，我们可能会在没有先验经验的情况下同时设 计出多个分类器，它们可能是采用不同分类技术学习产生的，也可能是采用了同 一种分类技术，但是具体参数不同。那么，到底哪个分类器最优，应该用哪个分 类器来对未知样本进行分类呢? “实践是检验真理的唯一标准”，我们将已知类 别号的样本数据集v 按照比例分成两部分，分别是训练集v l 和检验集v t ， v = v luv t 。我们在v l 上进行训练，产生分类器，用v t 中的样本进行测试， 用测试结果来评价分类器的好坏。 1 、准确率度量 准确率是分类器正确分类的检验集元组所占的百分比。在模式识别领域也称 作识别率( r e c o g n i t i o nr a t e ) 。如果使用训练集v l 或者其子集来检验分类器的 准确率，则该准确率称为再代入准确率，是准确率的一种乐观估计。 混淆矩阵( c o n f u s i o nm a t r i x ) 是分析分类器识别不同类元组情况的一种有 用工具。表3 1 是一张有n ( n = 1 0 0 0 0 ) 个检验元组的预测客户是否会买电脑的两个 类的混淆矩阵。 类 预测会买( 人)预测不会买( 人) 合计 准确率( ) 实际买了( 人) t p = 6 9 5 4 f n = 4 6 7 0 0 0 9 9 3 4 实际没买( 人) f p = 4 1 2t n = 2 5 8 83 0 0 08 6 2 7 合计 7 3 6 62 6 3 41 0 0 0 09 5 4 2 表3 1 混淆矩阵 其中，将应用中比较感兴趣的主类( 比如这里的“会买电脑”，垃圾邮件过 1 2 上海师范大学硕士研究生学位论文第三章分类与k 最近邻分类法 滤中的“是垃圾邮件 ) 称作正元组，另一类为负元组。真正( t r u ep o s i t i v e s ) 指分类器正确分类为正元组的数目，即t p ；真负( t r u en e g a t i v e s ) 是分类器正 确分类为负元组的数目，即t n ；假正( f a l s ep o s i t i v e s ) 是分类器错误分类为正 元组的数目，即f p ；假负( f a l s en e g a t i v e s ) 是分类器错误分类为负元组的数目， 即f n 。 于是，我们从混淆矩阵中总结得出下列一些常用的数字评价标准，其中包括 准确率。 ( 1 ) 准确度( a c c u r a c y ) ：定义为正确分类的元组个数占测试元组总数的比 例，即a c c u r a c y ：t p + t n ( 2 ) 假正率( f p r a t e ) ：为错误分类的负元组占元组总数的比例，即 f p r = f n + f p ( 3 ) 查准率( p r e c i s i o n ) 定义为正确分类的正元组个数占分类为正元组的元 r r n 组个数的比例，且pp r e c i s i 。n2 芴而1 1 ( 4 ) 查全率( r e c a l l ) 定义为正确分类的正元组个数占实际正元组个数的比 t p 例，即r e c a l l = 二l 一 t p + f n 除了上述度量，事实上我们还可以根据不同应用要求，设计出其它的度量。 假设已经训练的分类器将医疗数据元组分类为“c a n c e r ”或“n o t c a n c e r ”，9 0 的准确率使该分类器看上去相当的理想，但是，实际情况是只有3 一4 的训练 元组是“c a n c e r ，显然仅仅满足这样准确率的分类器是不能接受的。这时候， 删 就又要弓f 入特效性( s p e c i f i c 毗s p e c i f i c i t ) ，= 鼎。 上述的评价体系同样也可以用于评估与分类模型想关联的代f i r 收益分析。 我们将与假负( 错误地将非垃圾邮件判断为垃圾邮件) 及假正( 错误地将垃圾邮 件判断为非垃圾邮件) 相关联的实际应用中的代价做加权和，作为模型( 分类器) 的总代价，将真正及真负作为模型的收益，这样就有了下面的“代价收益曲线 图”。我们希望分类器的性能尽可能达到最上面那条曲线的状态，即曲线下放 的面积尽可能的大。 1 3 上海师范大学硕士研究生学位论文第三章分类与k 最近邻分类法 收益 代价 图3 2r o c 曲线 基于以上理论，下面介绍一种特殊的“代价收益曲线图 一r o c 曲线图。 2 、r o c 曲线【1 】 r o c 曲线是一种比较分类模型优劣的可视化工具。r o c 表示r e c e i v e r o p e r a t i n gc h a r a c t e r i s t i c ( 接收者运行特征) 。r o c 曲线源于信号检测理论，是二 战期间为雷达图象分析开发的。r o c 曲线显示了给定模型的真正率( 查全率) 与假正率之间的比较评定。真正率的增加以假正率的增加为代价。r o c 曲线下 方的面积就是模型广义准确率的度量，面积越大，模型的广义准确率越高。在第 五章中，将会用r o c 曲线来分析不同参数设置下的k n n 分类器的性能。 3 、其它评估标准 除了准确率外，评估分类方法的优劣的标准还有下列几项： 1 、速度：这涉及产生和使用模型的计算花费。 2 、鲁棒性( 强壮性) ：这涉及给定噪音数据或具有遗漏值的数据，模型正确 预测的能力。 3 、可伸缩性：这涉及给定大量数据，有效地构造模型的能力。 4 、可解释性：这涉及学习模型提供的理解和洞察的层次。 在下面几节讨论几种常见的分类方法的过程中将参照以上评估标准对分类 法进行分析比较。 3 1 4 决策树归纳分类1 】 1 、概念 决策树( d e c i s i o n t r e e ) 是一个类似于流程图的树结构。其中，每个内部结 点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表 类或类分布。树的最顶层结点是根结点。一棵典型的决策树如图3 4 所示。它表 示概念b u y s _ c o m p u t e r ，即它预测a l l e l e c t r o n i c s 的顾客是否可能购买计算机。内 1 4 上海师范大学硕士研究生学位论文第三章分类与k 最近邻分类法 部结点用矩形表示，而树叶用椭圆表示。 为了对未知的样本分类，样本的属性值在决策树上测试。路径由根到存放该 样本预测的叶结点。决策树结构很容易就可以转换成分类规则。 决策树已在诸如医疗、游戏理论和商务等应用领域广泛使用。决策树是一些 商业规则归纳系统的基础。 n 7 、。 ( y e s ) | 图3 3 ：概念b u y s _ c o m p u t e r 的判定树，指出a l l e l e c t r o n i c s 的顾客是否可能购买计算机。每 个内部( 非树叶) 结点表示一个属性上的测试，每个树叶结点代表一个类( b u y s _ c o m p u t e r = y e s ，或b u y s _ c o m p u t e r = n o ) 2 、算法 在2 0 世纪7 0 年代后期和8 0 年代初期，机器学习研究者j r o s eq u i n l a n 开 发了决策树算法，称作i d 3 ( i t e r a t i v ed i c h o t o m i s e r ，迭代的二分器) 。q u i n l a n 后来又提出了c 4 5 ( d 3 的后继) 。 在整个决策树分类过程中，显然其学习阶段，既决策树构造阶段是核心阶段。 所以，下面主要研究决策树构造的算法。 原则上讲，对于给定的属性集，可以构造的决策树的数目是指数级的。尽管 某些决策树比其它决策树要更准确，但是由于搜索空间是指数级的，从中找出最 优的决策树几乎是不可能的。尽管如此，还是有一些比较有效的算法能够在合理 的时间内构造出具有一定准确率的次最优决策树。这些算法通常都采用贪婪策 略，在选择划分数据的属性时，采用一系列的局部最优决策策略。h u n t 算法就 是这样一种典型算法。h t m t 算法是许多决策树算法的基础，包括i d 3 、c 4 5 等。 h u n t 算法的主要思想是：通过将训练元组相继划分成较纯的子集_ 以递归 方式建立决策树。 设s a m p l e s 是训练集，而c = c 1 ，c 2 ，) 是t 个类标号的集合，h u n t 算法的 递归定义如下： 上海师范大学硕士研究生学位论文第三章分类与k 最近邻分类法 ( 1 ) 对于给定的节点t ，如果s