基于统计的垃圾邮件过滤器的设计与实现.doc

杭州电子科技大学本科毕业设计摘 要随着Internet的发展， 电子邮件已成为用户最便捷和经济的交流方式之一，由于发送电子邮件非常容易、 成本又非常之低， 使得电子邮件成为一种电子化的手段被人利用，垃圾邮件制造者出于商业性或其它各种目的而大量向用户发送电子邮件。我们呼吁有关人士必须逐渐从立法、行政和规范角度出发采取全面有效的措施，但目前主要依靠的还是反垃圾邮件技术。典型的邮件过滤技术有黑白名单、规则过滤、概率统计分类等。为了降低误判，更好的适应多变和形式多样的垃圾邮件，本文采用基于统计（Bayes算法）的反垃圾邮件技术。利用已知的邮件，建立垃圾邮件和非垃圾邮件关键词的贝叶斯概率模型，然后利用该模型判断邮件是否为垃圾邮件。为了提高过滤模块性能，本系统采用支持首字Hash的分词算法。对于词首字的查找，根据汉字机内码编码规律，GB2312编码表中的每一个汉字在首字Hash表中都有唯一的一项与其对应。关键词：Bayes算法；邮件过滤；反垃圾邮件ABSTRACTWith the development of Internet, e-mail has become the user the most convenient and economical means of communication is one of very easy as sending e-mail, the cost and very low, making the e-mail as a means of being used, spam manufacturer for commercial purposes or a large number of various other e-mail to the user. We call on people to be gradually shifted from the legislative, administrative and normative point of view to take comprehensive and effective measures, but still rely mainly on the anti-spam technology. The typical black and white list of email filtering technology, rules filtering, probability and statistics classification. In order to reduce false positives and better adapt to changing and diverse forms of spam, this paper, based on statistics (Bayes algorithm) of the anti-spam technology. Using the known e-mail, the establishment of spam and non-Bayesian spam probability model keywords and then use the model to determine whether the message is spam. To improve the performance of filter modules, the system uses to support the first sub-word word Hash Algorithm. Find the first word for word, according to Chinese law machine coding, GB2312 encoding table in the first word of each character has a unique Hash table with the corresponding one.Keywords: Bayes algorithm；mail filtering； anti-spam目 录1 绪论11.1 论文背景11.2 课题研究的意义21.3 课题研究的主要内容21.4 本文的主要结构22 电子邮件相关内容42.1 电子邮件系统42.2电子邮件相关的协议52.3 电子邮件常用的编码标准73 需求分析和系统设计103.1 需求分析103.2 系统的流程103.3 系统相关技术介绍113.4 系统框架143.5 系统设计144 基于Bayes的反垃圾邮件系统实现174.1 预处理模块的实现174.2 过滤模块的实现194.3 数据模块中对汉语字典的加载235 测试及测试结果显示245.1主界面介绍245.2训练245.3 选择测试邮件255.4测试结果显示265.5 添加合法（非法）邮件库27结论29致谢30参考文献311 绪论1.1 论文背景1.1.1 垃圾邮件的现状随着Internet的发展,电子邮件已经成为人们相互交流、获取信息的重要渠道。但是，电子邮件给人们带来诸多方便的同时，也被一些别有用心的人所利用。主观上，垃圾邮件由此产生。Internet的开放性和邮件传输协议本身的缺陷是导致垃圾邮件泛滥的客观因素。迄今位置，垃圾邮件在国际上并没有一个标准的定义。同时，垃圾邮件的判定和邮件的接收者有很大的关系，不同用户对同一封邮件的判断结果可能会存在很大的差异。其基本特征是“不请自来”，而大部分带有商业或者其他宣传目的。近些年来，垃圾邮件问题日益严重。2007年1月，CNNIC（中国互联网络信息中心）发布的第十九次中国互联网发展状况统计报告显示：在网民对互联网最反感的方面，垃圾邮件排在第四位（前三位为网络病毒、网络入侵/攻击、弹出式广告/窗口），占7.8%。1.1.2 垃圾邮件的危害垃圾邮件带来的危害主要体现在：1)对用户的影响垃圾邮件的常见类型主要是商业宣传邮件、政治宣传邮件、非法色情邮件和病毒邮件，具有数量多、反复性、强制性、欺骗性、不健康和传播速度快等特点，严重干扰了用户的正常生活，侵犯收件人的隐私权和邮箱空间，并耗费收件人的时间、精力和金钱。特别是非法色情邮件和不健康邮件将严重侵害青少年的身心健康，给社会主义精神分明建设造成不良的影响。2) 对ISP的影响占用大量网络、存储和运算资源，造成邮件服务器拥堵，严重影响了运营商的服务质量和用户的满意度。3)对社会的影响垃圾邮件的蔓延，容易被不法黑客所利用，它通过大面积的病毒传播和突发性的邮件攻击，造成服务器、网络的瘫痪，特别是非法反动、色情暴力邮件的传播，给社会经济带来严重的损失、给政府行政安全管理带来极大的隐患，给人们日常生活带来严重的影响，给社会造成一定的不稳定性。另外，由于国内垃圾邮件的泛滥现状导致我国许多IP网段遭受国外反垃圾邮件组织的封杀，严重影响了国内邮件服务的正常通信。从2004年到2006年3月上旬，中国被国外反垃圾邮件组织列入黑名单的IP地址段共计2527个。而自2005年11月至2006年3月上旬期间，中国被国外反垃圾邮件组织列入黑名单的IP地址段共计479个，比2005年最后一次调查的结果被封的323个多出156个。我们可以通过一些权威组织发布的垃圾邮件统计数据来看出垃圾邮件来说明问题：根据中国互联网信息中心的中国互联网络发展状况统计调查第十七次对用户每周收发邮件数量和收到的垃圾邮件数量的统计结果是，2006年1月中国网民平均每周收到27.8封电子邮件(不包括垃圾邮件)，收到垃圾邮件57.5封，发出电子邮件12.1封。这些数字足以表明近几年来垃圾邮件迅猛增加，网民每周收到的垃圾邮件比非垃圾邮件还要多得多，这就在一定程度上给网民造成了严重的困扰。图1-1是摘自中国互联网协会反垃圾邮件中心2006年第一次的反垃圾邮件状况调查报告，统计了从2004年4月到2006年3月期间中国网民收到垃圾邮件的增长情况。此次调查还统计了各个邮件服务商，根据规模不同，每天服务商收到的垃圾邮件从15万封-3800万封不等，垃圾邮件站总邮件的比例也都近乎80%以上。1.2 课题研究的意义随着垃圾邮件的泛滥，反垃圾邮件技术越来越被人们所重视，出现了很多的过滤技术和过滤系统；基于服务器端的过滤；基于客户端的过滤；基于内容的过滤；基于地址的过滤；基于信封和信头的过滤等等。这些技术都在处理垃圾邮件问题上发挥了一定的作用。基于服务器端和基于客户端的垃圾邮件过滤各有优势，但是相对来说基于服务器端的过滤更能解决垃圾邮件泛滥的问题，因为等到了垃圾邮件到达客户端，就已经造成了资源的浪费，对垃圾邮件的处理越早实施，就越能减少它带来的损失。本文主要介绍Bayes邮件过滤系统是基于服务器端进行过滤的垃圾邮件过滤系统的一部分，其中内容过滤采用Bayes算法进行过滤。1.3 课题研究的主要内容在全面系统学习、总结了国内外在反垃圾邮件领域的研究成果的基础上，深入细致地研究了反垃圾邮件技术，本文提出了一种基于Bayes算法的垃圾邮件过滤系统，并采用一种支持首字Hash的分词算法。同时，介绍了电子邮件的工作原理，邮件过滤系统的设计和实现。1.4 本文的主要结构第2章 将介绍电子邮件的相关内容，包括电子邮件系统的介绍，电子邮件常用协议，电子邮件常用编码标准。第3章 将介绍系统的设计，包括设计的目的流程，相关技术的介绍，具体模块的设计。第4章 将介绍系统的实现，包括几个模块的具体实现。第5章 将介绍系统的具体操作和测试以及测试结果的显示。2 电子邮件相关内容电子邮件（简称Email）是一种用电子手段提供信息交换的通信方式。它萌芽于Internet出现的早期，1972年，Ray Tomlinson写了第一个电子邮件程序SNDMSG，在Internet的前身APPANET上使用。随着电子邮件技术与标准不断改进和成熟，Internet的飞速发展和普及，电子邮件以其简单，快捷，方便，低成本的特点，得到了广泛的应用，成为Internet上应用最广的服务。2.1 电子邮件系统要设计出好的垃圾邮件过滤方案，首先要对电子邮件系统有深入的了解。从理论上讲，电子邮件系统主要由四个主要部分组成：信件、邮件传送代理（MTA:Mail Transmit Agent）、邮件投递代理（MDA:Maik Deliver Agent）和用户代理（MUA：Mauk User Agent）。信件即写信的信纸，MTA用于路由信件，MDA用于投递信件，MUA提供用户创建和处理邮件的界面。邮件服务器是有MTA和MDA架设而成，是电子邮件系统的基础和根本。2.1.1 电子邮件系统的传输流程电子邮件的传输流程如图2-1所示。图2-1 电子邮件传输流程在邮件传输过程中，MTA、MDA、MUA都有自己的功能职责，完成各自的特定任务，下面将分别对MTA、MDA、MUA这三个代理进行叙述。2.1.2 电子邮件系统涉及到的代理 邮件传送代理MTA从各种来源接收邮件。每收到一封邮件，MTA就确定这封邮件要路由到哪里和如何路由。必要的话，还会改写地址，然后把邮件交给MDA投递。控制Inetenet邮件路由的主要机制是DNS域名服务协议，DNS提哦那个一个分布式的数据库，把域名映射到几个类型的信息中，包括邮件路由指令。大多数的MTA还提供他们自己的机制直接控制路由作为DNS路由的补充，这对于解决临时的DNS路由问题是有作用的。 邮件投递代理当MTA处理完一封邮件，兵确定了他的路由之后，就把它交给MDA。MDA负责把该邮件投递到另外一个位子，这个位置可以是令一个MDA，也可以死用户的信箱或者执行特殊任务的程序。根据这次投递是成功还是产生永久或临时的故障，MDA决定这次事务是完成、产生一个错误返回给发信人，还是在将来重新发送。最简单类型的MDA是一些系统用于投递到本地信箱的MDA，他简单的把到达信件放到本地用户的收件箱。但是，在投递时，可以对信件做一些其他的事。一些MDA不是简单地附加到达的电子邮件，而是提供过滤特性，而是提供过滤特性，对到达的信件提供额外的操作。其他MDA可以把电子邮件传递到另外一个及其。如果一个MTA决定信件需要路由到另外一个MDA，它把信件提交给一个使用SMTP简单邮件传输协议的MDA，这个协议定义一组把信件传递到远程MDA的命令，这样的MDA常常在MTA中创建。邮件用户代理MTA和MDA负责信件的路由和传送，而邮件用户代理负责为用户提供管理邮件的见面。这个管理通常包括查看信件、管理邮件夹、写和发送新信件，以及回复信件和把现有的信件发送给其他用户。它通常是与信件直接打交道的唯一程序。在早期的电子邮件中，MUA通常在用户接收邮件的相同机器上，最终创建了两个协议：POP协议和IMAP协议，允许使用MUA阅读位于远程机器上的电子邮件。POP为MUA提供一个协议，从远程服务器下载用户的收件箱，允许用户使用不总是连接到网络的机器；IMPA为MUA提供一个协议，操作远程服务器上的邮件文件夹。实现该协议的MUA可以连接到远程IMAP服务器，兵执行对信箱和信件需要做的各种任务。这允许用户的邮件文件夹和MUA放在不同的机器上。2.2电子邮件相关的协议2.2.1 SMTP协议SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议，是一种提供可靠且有效电子邮件传输的协议。SMTP是建立在FTP文件传输服务上的一种邮件服务，主要用于传输系统之间的邮件信息并提供与来信有关的通知。SMTP目前已是事实上的在Internet传输E-Mail的标准，是一个相对简单的基于文本的协议。在其之上指定了一条消息的一个或多个接收者（在大多数情况下被确定是存在的），然后消息文本就传输了。可以很简单地通过Telnet程序来测试一个SMTP服务器，SMTP使用TCP端口25。要为一个给定的域名决定一个SMTP服务器，需要使用MX(Mail eXchange）DNS。SMTP的基本结构SMTP协议是为了保证电子邮件的可靠和高效传送。TCP/IP 协议的应用层中包含有SMTP协议，但事实上它与传输系统和机制无关，仅要求一个可靠的数据流通道。它可以工作在TCP上，也可以工作在NCP, NITS 等协议上。在TCP上，它使用端口25进行传输。SMTP的一个重要特点是可以在可交互的通信系统中转发邮件。SMTP的模型SMTP提供了一种邮件传输的机制，当收件方和发件方都在一个网络上时，可以把邮件直传给对方；当双方不在同一个网络上时，需要通过一个或几个中间服务器转发。SMTP首先由发件方提出申请，要求与接收方SMTP建立双向的通信渠道，收件方可以是最终收件人也可以是中间转发的服务器。收件方服务器确认可以建立连接后，双发就可以开始通信。下图2-2是SMTP的模型示意图。图2-2 SMTP的基本模型SMTP协议命令：DATA、EXPN、HELO、HELP、MAIL FROM、NOOP、QUIT、RCPT TO、REST、SAML FROM、SEND FROM、SOML FROM、TURN、VRFY。2.2.2 POP3协议POP的全称是 Post Office Protocol，即邮局协议，用于电子邮件的接收，它使用TCP的110端口。现在常用的是第三版 ，所以简称为POP3。POP3仍采用Client/Server工作模式，Client被称为客户端，一般我们日常使用电脑都是作为客户端，而Server（服务器）则是网管人员进行管理的。举个形象的例子，Server（服务器）是许多小信箱的集合，就像我们所居住楼房的信箱结构，而客户端就好比是一个人拿着钥匙去信箱开锁取信一样的道理。一起来看看电子邮件软件收取电子邮件的过程，一般我们在电子邮件软件的账号属性上设置一个POP服务器的URL（比如），以及邮箱的账号和密码。这个在收信过程中都是用得到的。当我们按下电子邮件软件中的收取键后，电子邮件软件首先会调用DNS协议对POP服务器进行解析IP地址，当IP地址被解析出来后，邮件程序便开始使用TCP协议连接邮件服务器的110端口，因为POP服务器是比较忙的，所以在这个过程中我们相对要等比较长的时间。当邮件程序成功地连上POP服务器后，其先会使用USER命令将邮箱的账号传给POP服务器，然后再使用PASS命令将邮箱的密码传给服务器，当完成这一认证过程后，邮件程序使用STAT命令请求服务器返回邮箱的统计资料，比如邮件总数和邮件大小等，然后LIST便会列出服务器里邮件数量。然后邮件程序就会使用RETR命令接收邮件，接收一封后便使用DELE命令将邮件服务器中的邮件置为删除状态。当使用QUIT时，邮件服务器便会将置为删除标志的邮件给删了。通俗地讲，邮件程序从服务器接收邮件，其实就是一个对话过程，POP协议就是用于电子邮件的一门语言。2.2.3 IMAP协议Internet Mail Access Protocol(交互式邮件存取协议)IMAP是斯坦福大学在1986年开发的研发的一种邮件获取协议。它的主要作用是邮件客户端（例如MS Outlook Express)可以通过这种协议从邮件服务器上获取邮件的信息，下载邮件等。当前的权威定义是RFC3501。IMAP协议运行在TCP/IP协议之上，使用的端口是143。它与POP3协议的主要区别是用户可以不用把所有的邮件全部下载，可以通过客户端直接对服务器上的邮件进行操作。2.3 电子邮件常用的编码标准2.3.1 编码的必要性Email只能传送ASCII码(美国国家标准信息交换码)格式的文字信息，ASCII码是7位代码，非ASCII码格式的文件在传送过程中就需要先编成7位的ASCII代码，然后才能通过Email进行传送；如果不经过编码，则在传送过程中会因为ASCII码7位的限制而被分解，分解之后只会让收信方看到一堆杂乱的ASCII字符。经过编码后的文件，在传送过程中可顺利传送，不会有“被截掉一位”的危险。但是收信方必须具有相应的解码程序，将这份经过编码的东西还原，才能看到发信人要传送的信息是什么。有一点要注意：大部分的人认为“文本文件不需要编码”，但我们的中文是属于8位代码的文字，并不是标准的ASCII码格式，由于在国内中文是通行的文字，所以大部分的邮件服务器都已能够处理GB内码的文件，因而不需要做这种编码/解码的操作，可以直接传送。但如果要送中文邮件到国外，就需要经过这种转换才能传送，因为国外的邮件服务器是无法辨认中文内码的。中文码在经过一些不支持中文内码的传递主机时，依然会被截掉一位，造成文件支离破碎无法读龋而经过编码的中文邮件，收信人收到后将文件解码还原，也需要有中文系统才能看所写的中文信息。2.3.2 UU编码(UnixtoUnixencoding)uuencode和uudecode原来是unix系统中使用的编码和解码程序，后来被改写成为在DOS中亦可执行的程序。在早期传送非ASCII码的文件时，最常用的便是这种UU编码方式。使用的方法是：发邮件前，在DOS下先用uuencode.exe程序将原文件编码成ASCII码文件，然后将邮件发出。收信人收到邮件后，用uudecode.exe程序将文件还原。基于Windows的类似程序有wincode和winzip等。wincode的使用原理和DOS下的uuencode和uudecode没什么两样，只是在Windows的界面下操作更为简便。wincode除支持UU编码外也支持MIME、Binhex等编码格式，应用范围颇为广泛。以上介绍的UU编码并非只能编中文文字。任何你要寄送的文件包括exe等二进制文件都可以按照编码发送收信方收信解码还原的步骤传送。2.3.3 MIME标准(Multipurpose Internet Mail Extentions)UU编码解决了Email只能传送ASCII文件的问题。但这种方式其实并不是很方便，因而又发展出一种新的编码标准，其全名是Multipurpose Internet Mail Extentions，一般译作“多媒体邮件传送模式”。顾名思义，它可以传送多媒体文件，在一封电子邮件中附加各种格式文件一起送出。MIME标准现已成为Internet电子邮件的主流。它的好处是以物件作为包装方式，可将多种不同文件一起打包后传送。发信人只要将要传送的文件选好，它在传送时即时编码，收信人的软件收到也是即时解码还原，完全自动化，非常方便。当然先决条件是双方的软件都必须具有这种功能，要不然发信人很方便地把信送出去了，但收信人的软件如果没有这种功能，无法把它还原，看到的也就是一大堆乱码了。使用这种方式，用户根本不需要知道它是如何编码/解码的。即使只是用文字写的信，一样是打好包便寄出。如果是要寄多媒体文件，只要做选文件的动作，选完后寄出，其余的工作由电子邮件软件自动完成。由于MIME的方便性，愈来愈多的电子邮件软件采用这种方式。(我们现在最常使用的电子邮件软件Eudora、NetscapeMail、InternetMail等就是采用MIME方式，所以我们才能如此轻松地收发电子邮件。)MIME定义的是一种规格，也可以说是一种统称。其实能够符合这种规格的编码方式并不是单一的一种，只要符合这种MIME规格便可顺利传送。以货运作为比喻，若货运公司规定送交货运的规格是1立方米大小的箱子便可托运，它并没有限制一定要用木箱或是铁皮箱，只要是1立方米大小，货运公司就帮你送达。至于箱子里你是装食品或是书本或是衣服或是混合着装也没有限定，也就是说，多种格式的文件可以一起寄送。2.3.4 Binhex编码Binhex的编码方式常用于Mac机器，在PC上是较少使用的一种编码方式。一般PC上的电子邮件软件，亦多数支持MIME的规格，很少有支持Binhex格式。在常用的电子邮件软件中，唯Eudora具有这种功能，可直接解读Binhex的编码，如果你收到了这种由Binhex所编码的邮件，而且你的mail软件并不是Eudora或其他支持Binhex格式的软件。那也得用一个解读Binhex的程序解码。有一个共享软件Binhex3.exe具有这个功能，它在许多FTP站点都能找到。在Windows下，你还可以用我们前面所介绍的wincode来解码。本文介绍的UU编码、MIME以及Binhex都可以用它来处理。但可惜的是，对于MIME，它只处理Base64的编码。如果能再加上QP的功能，真的可以靠它走遍天下了。在MIME几乎已成标准规格的现在，用一套支持MIME的软件来做收发Email的工作，这些编码/解码工作就会自动完成，不会给你带来麻烦。3 需求分析和系统设计3.1 需求分析3.1.1 系统需求从业务和全局来分析，应有以下需求：(1)系统的设计思想应围绕算法的具体实现和改进，已达到降低误判的要求；(2)系统的设计工具应该具有先进性、稳定性；(3)设计时候必须考虑到能够处理非常大的事务量，保证系统长时间高效快速运转；(4)系统必须支持对邮件库进行增加，修改等功能；(5)系统各模块必须能够统一执行；(6) 一旦系统出现故障，必须能在最短时间内恢复；3.1.2 性能需求在性能需求这部分，我们根据成本和效率要求，定义系统的特性及实现的约束和限制条件。 产品需求法规：根据相关的商业软件条例实行。可用性(Usability)基本要求：人机界面友好、使用舒适、可理解性好：用户界面美观大方，一目了然，系统实时响应。可靠性(Reliability)基本要求：每千行代码错误率(Defects/KLOC)不超过2个。强大故障处理和系统恢复能力，提供数据备份功能。可移植性(Portability)操作系统：Windows XP。性能(Performance)要求：降低系统的误判，减少合法邮件被判为垃圾邮件的概率，提高准确性。3.2 系统的流程首先对邮件进行解码，提取正文，进行分词处理，构造特征向量，然后进行邮件过滤。系统流程如3-1图所示：图3-1系统流程图3.3 系统相关技术介绍3.3.1 贝叶斯算法贝叶斯算法是以著名数学家托马斯.贝叶斯（Thomas Bayes）(1702-1763)命名的一种基于概率分析的可能性推理理论，通过分析过去事件的知识，来预测未来的事件。贝叶斯过滤对大量用户已经判定的垃圾邮件和合法邮件进行学习，根据垃圾邮件和合法邮件中相同词语以及短语出现的概率对比来确定垃圾邮件的可能性。贝叶斯定理：贝叶斯定理是决策逻辑学的一个分支，使用理论统计学研究概率推论，即根据已经发生的事件来预测将来可能发生的事件。被意思理论假设，如果过去试验中事件出现的概率已知，那么根据数学方法可以计算出来未来试验中时间出现的概率。贝叶斯理论指出，如果事件的结果不确定，那么量化它的唯一方法就是时间的发生概率。 垃圾邮件过滤其实就是邮件分类问题，把邮件分为垃圾邮件和正常邮件。这就可以应用贝叶斯定理，通过对已经正确分类的邮件来预测新接收的邮件是否为垃圾邮件。贝叶斯定理的描述如下：对于一个统计试验，样本中间s是所有可能结果的集合,并且B1,B2.Br是s的一个划分，令p(A):AS表示定义在s中所有事件上的一个概率分布，则对于s中的任意事件A和B，都有p(A)0，p(B|A)=p(AB)/p(A)表示条件概率，即在已知A发生的情况下B发生的概率。贝叶斯定理可以表示为： 公式(3-1)其中p(A)0，由全概率公式可得 公式(3-2)在公式(3-1)中,p(BI/A)为后验概率，p(A|Bi)为似然概率，p(Bi)为先验概率。先验概率是指根据以往经验和分析得到的概率，如全概率公式,它往往作为“由因求果”问题中的“因”出。后验概率是信息理论的基本概念之一，在一个通信系统中,在收到某个消息之后，接收端所了解到的该消息发送的概率称为后验概率。3.3.2 分词的实现本系统使用了常用词词典、停用词词典和常用词首字Hash表（简称Hash表）。其中，常用词词典和Hash表在内存中的格式如图3-2所示：图3-2 词典组织结构对首字Hash表的结构稍作改动。在词典正文中保存所有的词及单独成词的汉字，首字Hash表中保存词典正文中出现的所有首字，及这些首字的属性。1） Hash表GB2312中出现的每一个汉字在Hash中均有唯一的一项与其对应，Hash表中每一项的结构如下：CPonMax其中，C：该汉字，Po：首字为该字的首词在词典中的位置，n：首字为该字的词的所有数目，Max：首字为该字的词的最大长度。如果Max和n均为1，表示C单独成词。2） 常用词词典正文词典正文是以词为单位的有序表，相同首字的词聚集在一起，按字母先后顺序排列。构造常用词词典，词典采用一行一词的模式以文件的形式保存，并且要将首字相同的词排列在一起。按照词的长度排列，将多字词排列在前面；长度相同，首字也相同的词按照字母顺序排列。分词时，将词典载入数组。对于Hash表，其构造过程如下所示：1） 将常用词词典载入内存；2） 依次读词典中的词，判断该词是否为相同首字的一组词中的第一个词。如果是，计算首字的Hash值作为该字在Hash表中的偏移值：Offset（C）=（C1-176）*94+(C2-161)，C表示词的首字，C1表示C的高字节，C2表示C的低字节；将该词的位置存入Po。否则，继续读词。3） 将相同首字的一组词的词数存入n，将长度最大的词的长度存入Max，继续读其余首字的词。4） 保存Hash表。继续2）直到词典结束。停用词词典主要包括对邮件特征表现无用的词，例如虚词（了、的）、常用的人名、地名、国家名等。由于它们不能表达具体的意思，对文本分词结果影响不大，因此需要在分词时首先去掉。3.3.3 系统分词流程将解码后的邮件读入内存，同时将Hash表和停用词词典也读入内存。首先判断首字节的数值，如果不是属于16-87区（汉字区）的汉字，则直接输出后，跳过，解析下面的邮件内容；否则，首先在停用词词典中查找，如果找到，则删除查找到的词，继续解析下面的内容；否则，进行分词。计算首字Hash值，从Hash表中得到此字所有可能组词的偏移位置，以及最长词长度等属性；在常用向右减字法进行查找。具体如下：查找前Max个字的词是否在词典中出现，如果完全匹配，则找到该词；否则，查找前Max-1个字的词，知道Max为2。特定词条查找采用上述算法。如果找到该词，记录下来，并从邮件内容中移去，继续解析；否则，跳过该字，继续解析其余内容。直到邮件内容结束。3.3.4 文本分类中特征值提取在介绍文本分类特征值提取前，首先介绍向量模型（Vector Space Model，VSM），因为很多的文本分类方法都采用这个模型表示文本，在这个模型中，文档被表示成向量的形式：d = d 或 d = ,其中ti是词条，wi是ti在文档中的词频或者仅用权值“0、1”表是特征项是否在文档中。如果wi表示词频，词频可分为绝对词频和相对词频，绝对词频是特征项在文档中出现的频率，相对词频是归一化的词频。文本分类中的特征选择（Feature Selection）和特征抽取（Feature Extraction）就是通过构造一个特征评价函数，把测量空间的数据投影到特征空间，得到在特征空间的值，然后根据特征空间中的值对每个特征进行评估，特征选择就是选择值最高的若干个特征。它是用机器学习方法进行文本分类的首要任务和关键问题。3.4 系统框架综合系统需要完成的目标和处理流程，设计出系统的框架，邮件截获模块完成截获邮件数据包、数据包编解码和邮件转发的功能；预处理模块完成邮件正文提取和分词、特征提取、以及构造特征向量的功能；过滤模块采用Bayes分类器将邮件过滤；数据模块是系统下所用到的词典、关键词表、训练样本集、规则库等信息。图3-3所示为系统的框架：图 3-3 系统的框架3.5 系统设计3.5.1 预处理模块 因为过滤器是基于VSM模型（Vector Space Model），需要对邮件进行预处理得到。在该模型中，我们把邮件的内容形式化为多维空间的一个点，以向量的形式给出，向量的元素可以是词、IP地址、文本格式等能够判断邮件是否是垃圾邮件的特征属性。该模块主要完成的工作包括：信头、信体分离，分词处理，特征向量生成。 信头、信体处理：电子邮件的格式包括信头、信体，两者之间用空行来分隔，可以分别提取信头和信体的信息。电子邮件的信头包括：发件人地址、收件人地址、主题、邮件列表等信息，这些信息常可以判断一封邮件是否是垃圾邮件。如商业广告垃圾邮件的主题通常包含“Buy”、“Save”和“Free”等特征。信封和信头的内容并不完全一致，信封的内容比较可靠，因为信头的内容是可以通过客户端进行伪造的，所以可以通过比较信封和信头的内容进行过滤。 分词处理：对于主题和信体中的内容，需要经过分词处理。分词的精度是影响系统准确率的一个重要因素。我们采用机械匹配法（向右减字最大匹配和向左增字最小匹配）相结合，然后再用互信息消除歧义得到比较精确的分词结果，这个过程需要借助分词词典。 特征向量生成：这个过程分为两种，一种是根据训练样本库取得表示垃圾邮件类的特征向量，这个过程是对信封、信头、信体等部分得到的信息进行处理，得到分类器所需要的特征向量。因为各部分所得到的特征属性所构成的向量维数太大，需要进行降维处理，对信封、信头的属性进行比较和合并，而对信体中得到的属性则进行筛选，也就是特征值选择。首先通过剔除词词典将对分词没有贡献的助词、连词、冠词等剔除，然后按照特征向量选择算法计算每个词的重要度，按照由高到低的顺序选择一定数量的特征词，和前面由信封、信头中的属性一起组成特征向量。另一种是根据由训练文本库得到的表示垃圾邮件类的特征向量构造待分类电子邮件的特征向量。 3.5.2 过滤模块 这个模块是整个系统的核心模块，它要完成的功能是对邮件信息进行处理，判断邮件是否是垃圾邮件，并对结果进行处理。因为邮件被表示成由“属性”组成的向量空间，这些属性包括：IP地址、附件大小、附件扩展名、群发地址个数、文本中的关键词等等信息，根据这些信息完成传统的基于IP、基于信封、信头和基于内容的过滤。 贝叶斯算法因为其简单快捷得到广泛应用，这里采用贝叶斯算法来提高过滤精度。过滤的结果分为正常邮件和垃圾邮件。对于正常邮件交给协议代理模块进行编码和转发，对于垃圾邮件的处理有： 丢弃：对于不需要保存到数据库中的数据包，做丢弃处理，节约资源； 存储：对于某些邮件存入数据库，作为训练样本集； 回复：对于一些邮件进行自动回复，通知发件人该邮件被过滤。 3.5.3 数据模块 系统中需要的分词词典、剔除词词典等等数据资源需要一个单独的模块来进行维护管理，提供增加、修改、查询、统计等功能，这个模块就是数据模块。这个模块包括七个部分。 分词词典：由于分词算法采用的是机械匹配的方法，需要分词词典提供辅助； 剔除词词典：在提取特征词之前，根据剔除词词典剔除部分词汇，提高效率； 特征属性表：基于Bayes算法的过滤方法需要根据垃圾邮件特征属性的概率统计信息进行过滤，因此系统需要维护垃圾邮件特征关键词的概率信息； 训练样本集：作为训练过滤器的样本，它的大小和时间性影响过滤的精度； 垃圾邮件表：保存一些过滤掉的邮件的数据库表格，在存储邮件的源IP和目的IP、邮件的发件人、主题、发送时间和邮件体的信息。便于事后统计分析； IP地址黑名单：保存经常发送垃圾邮件的IP地址； 规则表：保存生成属性表过程中需要的一些对信头特征进行提取的规则。4 基于Bayes的反垃圾邮件系统实现4.1 预处理模块的实现4.1.1 分词的实现本文设计垃圾邮件过滤系统是针对中文垃圾邮件的识别，中文分词模块是系统中的一个主要模块，是特征提取和分类器构造的重要数据供给模块，本节将给出一种具体的中文分词算法实现。中文分词的代码表述如下： public int wordSegment(String Sentence) int senLen = Sentence.length(); int i = 0, j = 0; int M = 12; String word; boolean bFind = false; FileAppender fa=new FileAppender(vocabulary.txt); while (i senLen) int N = i + M i; j-) word = Sentence.substring(i, j); if (dic.Find(word) if (j i + 1) if (!vocabulary.containsKey(word) vocabulary.put（word，new Float（0）； totleNumber+; fa.append(word); bFind = true; i = j; break; if (bFind = false) i = j + 1; return 1; 4.1.2 特征向量的构造我们主要介绍训练样本的特征提取。这些特征是指邮件中的可以判别邮件是否是垃圾邮件的关键字，关键字可以由系统根据统计结果进行自动设定，也可由管理员设定。首先提取训练集中文本中的关键词，并保存在特征向量表中。经过分词的邮件训练集中的每封邮件都变成一个把词以空格分隔得文本，统计每个词条在垃圾邮件类和正常邮件类中出现的频率，保存在两个链表中。词的长度指向表结点的指针头结点的结构是：关键词词的频度指向表结点的指针表结点的结构是：这样根据词的长度，分别查找相应的链表，就可以得到各关键词的频率。但是这样得到的关键词表中很多关键词对分类的贡献不大，需根据一定的特征选择函数来进行特征选择，达到降维的目的，我们采取的是计算期望交叉熵，将各期望交叉熵按从大到下排列，选取前N个（根据试验结果进行调整）词作为该类的特征向量。期望交叉熵的计算公式定义为：公式(4-1) P（Ci|t）的计算公式为为： 公式(4-2)则期望交叉熵的计算公式变为： 公式(4-3)其中，P（Ci|t）是文本中出现词条t时，文本属于Ci的概率，P（Ci）是类别Ci出现的概率，P（t|Ci）是Ci类中词条t出现的概率，P（t）是所有类中词条t出现的概率。交叉熵反映了文本类别的概率分布和在出现了某个特地词的条件下文本类别的概率分布之间的距离，词条t的交叉熵越大，对文本类别分布的影响也越大。这样原来的两个词表经过精简就可以得到两个新的词表，其中的关键词就是该类的特征向量。接着把非文本特征词组成一个新的链表加入以上的两个表中，其表头项的值为0，表中属性用字段表示，其中各项属性的概率计算公式为： 公式(4-4) 其中N（doc（tj）|Ci）为Ci类文本中出现特征tj的文本数，|Dc|为训练集包含的总文档数.最后得到的表中的各项就是表示各类的特征属性，结构如图4-1所示：012N 免费98%图4-1 特征属性结构图4.2 过滤模块的实现本文前面介绍了Bayes算法在文本分类中的应用，下面介绍它在垃圾邮件过滤模块中的应用。4.2.1 Bayes算法在垃圾邮件过滤器中的应用由于邮件可以当作是特殊的文本，垃圾邮件处理实质上就是将邮件分为两类，一类是合法邮件，一类是垃圾邮件。Bayes过滤算法的基本步骤：（1） 收集大量的垃圾邮件和非垃圾邮件，建立垃圾邮件集和非垃圾邮件集。（2） 提取邮件主题和邮件体中的独立子串例如ABC32，￥22等作为TOKEN串并统计提取出的TOKEN串出现的次数即字频。按照步骤2的方法分别处理垃圾邮件集和非垃圾邮件集中的所有邮件。（3） 每一个邮件集对应一个Hash表，hashtble_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。（4） 计算每个Hash表中TOKEN串出现的频率P=（某TOKEN串的字频）/(对应Hash表的长度)（5） 综合考虑hashtable_good和hashtable_bad，推断出当新来的邮件中出现某个TOKEN串时，该新邮件为垃圾邮件的概率。数学表达式：A 事件 -邮件为垃圾邮件t1，t2.tn代表TOKEN串 则P（A|ti）表示在邮件中出现TOKEN串ti时，该邮件为垃圾邮件的概率。设P1（ti） = （ti在hashtable_good中的值）P2（ti） = （ti在hashtable_bad中的值）则P（A|ti）= P1(ti)/P1(ti) + P2(ti); (6) 建立新的Hash表hashtable_probability存储TOKEN串ti到P（A|ti）的映射。(7) 至此，垃圾邮件集和非垃圾邮件集的学习过程结束。根据建立的Hash表hashtable_probability可以估计一封新到的邮件为垃圾邮件的可能性。当新到的一封邮件时，按照步骤（2）生成TOKEN串。查