支持向量机在垃圾邮件过滤系统中的应用

支持向量机在垃圾邮件过滤系统中的应用 II 摘 要 随着互联网的快速普及与发展，电子邮件逐渐成为了Internet应用最广的服务，电子邮件成为了人们日常生活中信息交流的重要手段之一，但随之而来的垃圾邮件也越来越猖獗。在日益泛滥的垃圾邮件给我们的互联网带来麻烦的同时，垃圾邮件过滤技术的研究也在如火如荼的展开，但是当前的基于IP地址和基于手工规则的过滤方法存在着误判率过高以及过滤能力有限等局限性， 因此基于内容的垃圾邮件过滤技术就成了目前研究的热点。基于统计学习理论的支持向量机，在解决有限样本、非线性及高维模式识别问题中表现出许多特有的优势。并且支持向量机具有其他各种过滤方法无法比拟的优点，如结构风险最小化、全局唯一解等，是邮件过滤中很有前途的一种方法。 本文旨在通过引入支持向量机方法构建垃圾邮件过滤系统， 研究支持向量机在两类数据识别方面的效果， 并与现有的分类方法进行比较，进而分析支持向量机在垃圾邮件过滤系统中的有效性和可行性。 关键词 ： 垃圾邮件，过滤，支持向量机，分类，效果比较 支持向量机在垃圾邮件过滤系统中的应用 III Abstract With the rapid popularization and development of the Internet, e-mail has gradually become the most widely services on the Internet and one of the important means for the exchange of information in daily life. But the spam becomes increasingly rampant. In the growing flood of junk e-mail, which causes trouble for the Internet at the same time, spam filtering technology is also progressing well. Because of the current IP address and the limitations that the filtering rules using manual methods has a very high rate of misjudgment and limited capacity, content-based spam filtering technology has become the main stream of research in this field. Based on Statistical Learning Theory, the support vector machines owns many unique advantages in resolving the limited samples, nonlinear high-dimensional pattern recognition and performance problems. Support Vector Machine possesses incomparable advantages, such as structural risk minimization, globally unique solution. It is the only promising way among all the methods of filtering e-mails. This paper aims to introduce the spam filtering systems aided by Support Vector Machine, study the effects of support vector machine in the two types of data to identification and compare the existing classification methods, further analyses the effectiveness and feasibility of support vector machine in spam filtering system. Key words： Spam, Filter,Support Vector Machine,Classification,Compare of Effect 支持向量机在垃圾邮件过滤系统中的应用 IV 目 录 第一章 前言 . 1 1.1 垃圾邮件过滤技术研究背景及意义 . 1 1.2 现有的垃圾邮件过滤技术 . 1 1.3 研究支持向量机分类识别的目的和意义 . 2 第二章 电子邮件概述 . 3 2.1 电子邮件系统工作原理 . 3 2.2 垃圾邮件的危害性 . 4 第三章 支持向量机简介 . 6 3.1 机器学习 . 6 3.2 支持向量机相关的基本概念 . 7 3.3 支持向量回归机 . 9 3.4 支持向量分类机 . 9 第四章 基于支持向量机的垃圾邮件过滤系统 . 12 4.1 电子邮件的预处理 . 12 4.2 语料库的选择 . 13 4.3 支持向量分类机对邮件的过滤分类 . 13 4.4 结果的比较与分析 . 14 第五章 结论与展望 . 16 5.1 分析与结论 . 16 5.2 对进一步研究的展望 . 16 参考文献 . 18 致 谢 . 20 支持向量机在垃圾邮件过滤系统中的应用 - 1 - 第一章 前 言 1.1 研究背景及意义 互联网技术的发展深刻地影响着人们，网络已成为人们获取信息、传递信息的一种重要手段，电子邮件以其方便，快捷的特点已逐渐受到人们的青睐，许多重要的商业信函也会通过电子邮件的方式传送。通过网络的电子邮件系统，用户可以用非常低廉的价格（无论发送到哪里，只需要负担电话费和网费即可），以非常快速的方式（几秒钟之内可以发送到世界上任何你指定的目的地），与世界上任何一个角落的网络用户联系，这些电子邮件可以是文字、图像、声音等各种方式。这是任何传统的方式也无法相比的。更重要的是，电子邮件是整个互联网以至所有其他网络系统中直接面向人与人之间信息交流的系统，它的数据发送方和接收方都是人，所以极大的满足了大量存在的人与人通信的需求。 但在人们享受电子邮件带来的方便、快捷的同时，也在不断的忍受着垃圾邮件的骚扰。 垃圾邮件的泛滥，不仅耗费网络资源，而且对企业正常运作和用户的正常工作造成严重干扰，对国家利益造成严重损失。经过综合计算，垃圾邮件给国民经济每年造成 60.69 亿元人民币的损失1。因此对于垃圾邮件过滤方法的研究已成为刻不容缓的重要课题，具有深刻的意义。 从电子邮件的结构出发， 寻找垃圾邮件的特征是垃圾邮件过滤常采用的基本方法。目前世界上 50%的邮件都是垃圾邮件，只有少数组织承担责任。很多反垃圾邮件的措施都被提出出来，但是只有非常少的被实施了。不幸的是，这些解决办法都既不能完全阻止垃圾邮件， 也对正常的邮件来往产生了影响。 所以在这种背景之下，研究一种更加新型高效的，快速的垃圾邮件过滤系统仍具有特别的现实意义。 1.2 现有的垃圾邮件过滤技术 在日益泛滥的垃圾邮件给我们的互联网带来麻烦的同时， 垃圾邮件过滤技术的研究也在如火如茶的展开，专家和研究者提出了各种垃圾邮件的过滤方法。从邮件过滤的执行方法来说大致可以分为以下三类:一是基于 IP 地址的方式，根据发送方的邮件地址或 IP 地址，拒绝接收不正当的邮件攻击;二是基于手工规则的过滤，手工设置一些规则，只要符合这些规则的一条或几条，就认为是垃圾邮件;三是基于支持向量机在垃圾邮件过滤系统中的应用 - 2 - 邮件内容的过滤，通过对邮件内容进行识别和检查，来决定是否接收邮件2。另外随着邮件过滤技术的发展还出现了一些其他的方法。 为了对付已泛滥成灾的垃圾邮件，各种反垃圾邮件技术也不断涌现。早期有安全认证的方法，基于规则的方法，而当前的研究主要是基于统计的方法，即通过对已有邮件的统计学习来获得垃圾邮件与合法邮件的不同特征， 并通过这些特征对新邮件进行区分。 统计学习理论是一种专门处理小样本的统计理论， 为研究有限样本情况下的统计模式识别和更广泛的机器学习问题建立了一个较好的理论框架。 1995 年，V.Vapnik 对小样本统计学理论进行了系统化， 并在此基础上发展了一种通用的学习方法支持向量机（ SVM）。其在解决有限样本、非线性及高维模式识别问题中表现出许多特有的优势。它不仅考虑了对推广能力的要求，而且追求在有限信息的条件下得到最优结果。 1.3 研究支持向量机分类识别的目的和意义 支持向量机算法是近年来一种应用很广泛的可用于分类的算法， 在已有的应用领域（人脸检测和手写数字识别）有很好的识别效果。支持向量机的基本思想可以概括为：首先通过非线性变换将样本空间变换到一个高维空间，然后在新空间中求取最优线性分类面，此非线性变换通过定义适当的核函数实现。支持向量机具有其他各种过滤方法无法比拟的优点，如结构风险最小化、全局唯一解、在非线性和高维模式中也表现出很好的效果，是邮件过滤中很有前途的一种方法3。 支持向量机在垃圾邮件过滤系统中的应用 - 3 - 第二章 电子邮件概述 2.1 电子邮件系统工作原理 2.1.1 电子邮件投递流程 电子邮件与普通邮件有类似的地方，发信者注明收件人的姓名与地址（即邮件地址），发送方服务器把邮件传到收件方服务器，收件方服务器再把邮件发到收件人的邮箱中。用户通过 MUA（ Mail User Agent）等书写电子邮件，然后通过 MUA把邮件发送到 MTA（ Mail Transport Agent） ， MTA 利用 SMTP（ Simple Mail Transfer Protocol）协议经多个 MTA 的接力式传递，到达目的地 MTA。最后，利用 POP3（ Post Office Protocol Version 3）协议通过 MDA（ Mail Delivery Agent）把邮件发送到目的用户邮箱4。 图 1.电子邮件工作原理示意图 2.1.2 电子邮件过滤模型 本文设想的电子邮件过滤系统是处于用户的邮件服务器和邮件接收软件（如：Outlook）之间的一个过滤层，是基于客户端的垃圾邮件过滤系统。系统模型主要由以下几个部分组成：邮件接收模块、预处理模块、向量化模块、内容过滤模块和邮件后处理模块。邮件接收模块用来读取新邮件的内容；预处理模块完成对邮件关键字段的提取；邮件向量化模块完成对邮件的向量化表示，包括禁用词处理等；而内容过滤模块设计了一个基于支持向量机的过滤模型，是整个系统的重心，主要完支持向量机在垃圾邮件过滤系统中的应用 - 4 - 成过滤工作；邮件的后处理模块则完成对垃圾邮件的标注，并将其移入专门的文件夹，用户仍可对其进行查看或转移5。 本文主要涉及到的是向量化模块和内容过滤模块，试图把 IP 地址、主题和内容中的关键词、附件信息等作为属性，一起构成表示邮件的特征向量，根据这个特征向量构造邮件分类器，对垃圾邮件进行过滤。 2.2.垃圾邮件的危害性 电子邮件（ Electronic Mail）是 Internet 技术发展的产物，与其它先进技术一样，在为人类服务的同时，不可避免的被另外一些人用作相反目的。首次关于垃圾邮件的记录是 1985 年 8 月一封通过电子邮件发送的链锁信，一直持续到 1993 年。历史上比较著名的事件是 1994 年 4 月份， Canter 和 Siegel 的法律事务所把一封信发到 6000 多个新闻组，宣传获得美国国内绿卡的法律支持。这是第一次使用 Spam（垃圾邮件）一词，用来描述新闻或电子邮件的主动性发布。同时，垃圾邮件也开始引起了人们的注意和反感。一些触觉敏锐的商人立刻意识到了电子邮件带来的商机，许多人开始利用电子邮件作商业广告， 95 年 5 月有人写出了第一个专门的应用程序 Floodgate，一次可以自动把邮件发给很多人。紧接着在 8 月份，就有人拿两百万个邮件地址出售。垃圾邮件越来越多与商业联系起来6。 自从 2003 年垃圾邮件的大肆泛滥以来，它现在已成为互联网上最让人头疼的一件事。据中国互联网协会发布的最新统计数字，中国互联网用户收到的垃圾邮件占所收邮件总数的 63.97%，平均每天收到的垃圾邮件数量超过 2.7 封，并且用户平均每周要花 13.15 分钟处理垃圾邮件1。 垃圾邮件主要危害有以下几点： 1、占用大量传输、存储和运算资源，造成邮件服务器拥堵，降低了网络的运行效率，严重影响正常的邮件服务； 2、垃圾邮件以其数量多、反复性、强制性、欺骗性、不健康性和传播速度快等特点，严重干扰用户的正常生活，侵犯收件人的隐私权和信箱空间，并耗费收件人的时间、精力、金钱； 支持向量机在垃圾邮件过滤系统中的应用 - 5 - 3、垃圾邮件一旦被黑客利用，危害更大。 2000 年 2 月，黑客侵入并控制了一些高带宽的网站，集中众多服务器的带宽能力，然后用数以亿计的垃圾邮件发动猛烈攻击，造成部分网站瘫痪； 4、严重影响电子邮件服务商的形象。收到垃圾邮件的用户可能会因为服务商没有建立完善的垃圾邮件过滤机制，而转向其他服务商； 5、妖言惑众、骗人钱财、传播色情、反动等内容的垃圾邮件，己经对现实社会造成危害7。 支持向量机在垃圾邮件过滤系统中的应用 - 6 - 第三章 支持向量机简介 3.1 机器学习 当计算机应用到实际问题中时， 通常可以显式地描述出给定一组输入如何推出所需要的输出，但是由于很多问题比较复杂，有时不知道如何给定输入计算出期望的输出，或者这种计算可能要付出很高的代价。解决此类问题的一种策略就是让计算机自己从样例中学习输入到输出的对应函数关系。 机器学习问题就是通过某种训练手段，根据给定的训练样本集将系统的输入和输出之间的依赖关系估计出来，并且希望这一估计可以对任意给定的输入进行尽量精确的输出预测， 这样使用样本来合成计算机程序的过程称为学习方法，其中有关输入 /输出函数关系的样本成为训练数据。 支持向量机（ SVM， Support Vector Machine）是在高维特征空间使用线性函数假设空间的学习系统，它由一个来自最优化理论的学习算法训练，该算法是一个准则性的并且强有力的方法。在它提出后的若干年来，在范围广大的应用中， SVM的性能胜过其他大多数的学习系统。 线性学习器是系统的主要构件；核函数用于定义隐式的特征空间，是有效运用高维特征空间的关键所在；统计学习理论能够解决高维易产生过拟合的危险，还避免了局部最小值的问题，因此即使对于包含上万条样本的训练集，总是可以找到有效的解。而假设的简洁表示意味着在新的输入上求值将非常迅速。因此，训练的效率、测试的效率。过拟合以及算法参数调节这四个困难都将在 SVM 中避免8。 机器学习包含了很多特殊的问题，主要分为三类：模式识别、概率密度估计和回归估计。不同类型的机器学习问题有不同的损失函数