（计算机软件与理论专业论文）一种基于内容分析的邮件过滤模型的研究与实现.pdf

东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 摘要 电子邮件已经成为人们日常生活中通信、交流的重要手段之一。然而，大量出 现的垃圾邮件，给用户造成时间和资源的浪费，同时极大地消耗了网络传输资源以 及邮件服务器的存储空间，并对网络安全构成威胁，针对这一问题尽快寻找解决方 案的需求也更加迫切。目前，应对垃圾邮件的主要方法和手段通过反垃圾邮件立法 和使用邮件过滤技术进行处理，现己相继出现了多种邮件过滤技术。目前，常用的 包括黑名单与白名单技术、基于关键词搜索以及设定过滤规则等方法。在实际使用 中已逐渐不能满足过滤需求，基于内容分析的文本分类技术正逐步进入邮件过滤 技术当中，并成为当前研究热点，其中，基于内容分析的邮件过滤方法中的典型 方法是基于贝叶斯模型。 本文结合文本分类技术以及贝叶斯( b a y e s ) 理论，构造基于贝叶斯分类的垃 圾邮件过滤模型，研究实现邮件过滤器的关键技术与方法，并给出核心过滤算法在 邮件分类中的具体实现方法和过程，最后完成垃圾邮件自动过滤的全过程。为减少 邮件的误判对用户造成的损害及垃圾邮件漏判造成的影响，提出了相应的改进措施： 使用最小风险贝叶斯决策减少误判；通过垃圾邮件反馈，对分类系统进行自适应调 整，以改善垃圾邮件的漏判问题。最后给出基于贝叶斯及其改进算法的邮件过滤模 型及基于该框架的垃圾邮件过滤原型系统的实现。 关键词：电子邮件，垃圾邮件，邮件过滤，贝叶斯理论 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 e - m a i li sb e c o m i n gac o n v e n i e n ta n dr a p i dc o m m u n i c a t i v et 0 0 1 b u tm o r ea n d m o r es p a m sb r i n gg r e a tp r o b l e m s ，t h e yw o u l du s eu po u rr e s o u r c e s ，s u c ha ss t o r a g e s p a c e si ne m a i ls e l y e r s ，a n dt h e yw o u l da f f e c tt h es a f e t yo f o u rn o t w o r k i ti su r g e n tt o s o l v et h e “s p a r e p r o b l e m a tp r e s o n t , t h ep r i m a r ym c t h o do f p r e v e n t i n gs p a mi s f i l t e r i n g n o w a d a y s ，a n t i s p a mm e a s u r e m e n t so f t e ni n c l u d eb l a c ko rw h i t el i s t t e c h n i q u e ，m a n u a lr u l e sa n dk e y w o r db a s e dc o n t e n tf i l t e r i n g t h e s em e a s u r e m e n t sa r e b e c o m i n gs i c ki nf i r e r i n g c o n t e n t - b a s e df i l t e r i n gi sb e c o m i n gah o t s p o t t h et y p i c a l m e t h o do f c o n t e n t b a s e ds p a mf i l t e r i n gi st h a to f b a y e s i a nm o d e lb a s e ds p a m f i l t e r i n g b a s e d0 1 1t e x tc a t e g o r i z a t i o nt e c h n i q u e sa n db a y e s i a nt h e o r y , w ee s t a b l i s ht h e e - m a i lf i l t e r i n gm o d e lo nb a y e s i a nc l a s s i f i e ra r e ra n a l y z i n gt h ek e y t e c h n i q u e sa n d m e t h o d so f c o n t e n t - b a s e df i l t e r i n g ，a n dw ep r o v i d et h ee f f e c t i v ew a ya n dk e y a l g o r i t h mi nf i l t e r i n ga n dc o m p l e t et h e j u d g m e n to f s p a m s i no r d e rt or e d u c et h e d a m a g e so f w r o n ge - m a i lc l a s s i f y i n g ，w ep r o v i d et h ei m p r o v e dm e t h o d so f u s i n gt h e r i s km i n i m i z a t i o nb a y e s i a nd e e i s i o na n ds e l f - a d j u s t m e n to f c a t e g o r i z a t i o ns y s t e m w e f i n a l l yd e s c r i b eas p a r ef i r e r i n gm o d e la n dr e a l i z a t i o no f t h ep r o t o t y p eb a s e do n b a y e s i a nm o d e lw i t hi e l a t e di m p r o v e m e n t s k e y w o r d s ：e - m a i l ，s p a r e ，f i l t e r i n g ，b a y e s i a nt h e o r y h 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 7w 匣叁 日期。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：盔：量导师签名：研究生签名：墨导师签名： m 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 1 1 研究背景及其意义 第一章绪论 现代网络中广泛应用的电子邮件服务，由于在传送信息方面具有快捷、方便、 高效等优点己经成为了现代通信技术方式的重要组成部分之一；但是电子邮件在为 人们提供极其方便的通信手段的同时也为用户未请求接受的邮件，甚至病毒、黑客 程序的传播提供了重要的载体。 垃圾邮件的英文名称为s p a r e 或j u n km a i l ，一般使用s p a 一词，将垃圾邮 件与“s p a r e ”一词正式联系在起源于起在互联网上以“g r e e nc a r ds p a ”为 标题兜售绿卡生意的事件。2 0 0 3 年，中国互联网协会在中国互联网协会反垃圾 邮件规范中对垃圾邮件作了以下定义“。： 1 ) 收件人事先没有提出要求或者不同意接收的广告、电子刊物以及各种形式 的宣传邮件。 2 ) 收件人无法拒收的电子邮件。 3 ) 隐藏发件人身份、地址、标题等信息的电子邮件。 4 ) 含有虚假的信息源、发件人、路由等信息的电子邮件。 从以上界定的邮件内容上看，目前可以将垃圾邮件归纳为具有以下几类特征 的邮件：带有商业广告性质的邮件；色情、暴力邮件；带有政治目的的邮件以及带 有病毒的邮件。 作为垃圾邮件的发送方来说，由于其操作简单、成本低廉、可以通过各种方式 群发，使得它极易成为一种电子化的手段被人利用；而对邮件服务提供商和用户而 言，垃圾邮件却给他们带来很大的危害和损失。大量出现的垃圾邮件，给用户造成 时间和资源的浪费，同时也极大地消耗了网络传输资源以及邮件服务器的存储空 间，并对网络安全构成威胁。据中国互联网络信息中心近年公布的中国互联网络发 展状况统计报告显示，中国网民每周收到的垃圾邮件数量已经超过了正常邮件数 量并有进一步增长的趋势。因此，针对这一问题尽快寻找解决方案的需求也更加迫 切。 面对垃圾邮件问题日益严重的现状，人们开始从多方面寻找解决办法。目前主 要从法律层面和技术层面来应对和缓解垃圾邮件问题，前者可以依据立法，对 垃圾制造者进行法律制裁，目前，美、英、法等国家和地区已确立了反垃圾邮件相 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 关法案和法规，但更多的国家尚未出台相关立法，中国互联网协会反垃圾邮件协调 小组也发出加快“反垃圾邮件立法”进程的倡议，但在最终立法的道路上，仍有许 多路要走；后者在技术层面上解决垃圾邮件问题目前是现实可行的，相关的研究投 入也越来越大，相继出现了多种垃圾邮件过滤技术，对垃圾邮件过滤技术的研究从 开始兴起，到目前逐步成为研究热点。 1 2 从邮件系统的角色结构来看，邮件过滤可以分为基于服务器端的过滤和基于 客户端的过滤。i n t e r n e t 邮件系统中接受邮件部分包括以下几个层次( 如图1 1 ) ， 路由器、m t a ( m a i l t r a n s f e r a g e n t ，邮件传送代理) 、m d a ( m a i l - d e l i v e r y a g e n t ， 邮件投递代理) 、m u a ( m a i l - u s e r a g e n t s ，邮件用户代理1 ，最后到达接收用户。 其中枷限负责邮件路由，i v l d a 负责邮件投递，m i j a 负责编辑和管理邮件。在这5 个 层次中的任意一层次都可以进行过滤，过滤越往外层，将越有效地减轻内层的压力。 但实际上，每个层次的过滤都有其各自的特点，经常是多个层次同时进行。所以按 照实施过滤的主体来分，可分为路由器过滤、m t a 过滤、m d a 过滤、m u a 过滤 和用户过滤五种，广义上分就是基于服务器端的过滤和基于客户端的过滤两种。 m t a 和m d a 过滤都是邮件服务器端的过滤，而m u a 过滤是邮件用户的客户 端的过滤。 医习 亟悃_ 困1 由器 图卜1 垃圾邮件过滤层次漠型 但无论是基于客户端的过滤，还是基于服务器端的过滤，都需要对邮件本身进 行分析，过滤垃圾邮件。垃圾邮件过滤技术是反垃圾邮件技术的重要方法之一。要 想研究垃圾邮件过滤技术，必须要对邮件的各部分结构进行分析。因此，从邮件结 构出发，寻找垃圾邮件特征，是垃圾邮件过滤常采用的基本方法。 从电子邮件结构来看，电子邮件通常具有几个重要部分：电子邮件地址( 包括 收发件人邮箱名、收发人邮箱服务器i p 地址或域名) 、主题、信件内容( 包括正文、 关键字、附件) 等相关字段，这些特征是过滤技术判断、分析、统计和提取的依据。 按照这些过滤的依据，过滤可以分为基于i p 地址的过滤、基于内容的过滤( 包括 基于规则的过滤和基于统计的过滤) 等。 2 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 目前常用的过滤技术，如以上提到的基于坤地址的过滤、基于邮件内容 分析的过滤等技术，一般都同时适用于服务器端和客户端的邮件过滤。 针对不同形式的垃圾邮件，目前，各大邮件服务提供商或邮件客户端大多提 供了一定的垃圾邮件过滤功能，主要以基于i p 地址的过滤和基于规则的过滤为主。 例如，对于信头部分带有垃圾特征的邮件采用基于关键词搜索以及设定过滤规则等 方法。有些系统使用了收集垃圾邮件地址列表，人工建立垃圾邮件的过滤规则，删 除有明显特征的垃圾邮件地址所发送的邮件等过滤措施。但由于构建过滤规则的时 间和经验限制，并且由于垃圾邮件发送方为躲避过滤机制而采用不断变换地址等方 式，使得过滤规则需要经常被调整，既花费大量时间，又影响过滤效果，在实际使 用中已逐渐不能满足过滤需求。 为改善过滤的准确性和提高过滤的效率，直接针对邮件正文内容进行分析， 完成邮件的过滤，将是本文的重点研究内容。 下面分别讨论目前对于垃圾邮件的过滤主要使用的几种方法“。 1 基于地址( 内容) 的方法。类方法是服务器在未得到对方认证前拒绝连接， 如实时黑名单技术，即邮件服务器拒绝黑名单中i p 地址的连接请求；主机名反向 验证技术，即由邮件服务器验证发送方服务器的域名和i p 是否与d n s 符合来拒绝 连接。另一类是基于人工设定的规则，根据所列邮件地址信息判断垃圾邮件和正常 邮件，如黑白名单过滤法。 2 基于规则的过滤方法。该类方法通过训练得到规则，通过考查一个个训练 样本，归纳出规律性的规则，通过生成的规则集进行决策，对邮件进行分类。如关 键词匹配法就是将文本关键词和规则集中已有的规则进行匹配，根据匹配结果判断 邮件类型。常见的基于规则方法有：r i p p e r 方法，决策树”。算法和b o o s t i n g 方 法等。对于邮件头部和正文内容过滤都可以采用基于规则的过滤方法。 3 基于概率统计的方法。是基于内容过滤的主要方法，是当前邮件过滤中的 主要研究趋势，也是本文重点研究的方法。该类方法将文本分类方法应用于电子邮 件过滤中，将邮件分类为合法邮件和垃圾邮件，该类方法运算速度，分类精度较高。 主要的统计方法有：k n n ( k - n e a r e s t - n e i g h b o rk 最近邻法) 方法、s ( 支 持向量机) 方法“和b a y e s ( 贝叶斯) 方法。k n n 与s v m 方法都是比较优秀的传统 分类方法，他们有各自的优势和特点，在邮件过滤分类处理中都可以使用，但也有 他们的局限性，由于它们各自的特点，在邮件过滤中并不能很好体现它们的优势， 而朴素贝叶斯方法( n a i v eb a y e s ) 的运算速度快，且具有较高的精确度，对于 东南大学硕士学位论文 一种基于内容分析的邮件过滤模型的研究与实现 对速度有一定要求的、需对大量邮件进行实时处理的操作比较有优势，因此，在垃 圾邮件过滤中，它的使用更合适，效果也更好。 以上各类方法在应用过程中，还有以下问题值得关注： 基于邮件地址等方法虽然具有较高的安全性，但在实施中需对邮件地址信息等 限定条件进行人工设定，一旦情况发生变化，用户修改量会增大，随着电子邮件数 量的增多，以及垃圾邮件地址的经常变换，已经逐渐难以适应现在发展的需求。 对于基于规则的过滤方法，建立规则和样本集时间较长，且规则需要根据用户 的情况进行变更，再重新进行学习。该方法对邮件的判别类似于二值判断，即把邮 件分为垃圾邮件和合法邮件，合法邮件的判别率较低，尤其在规律不明显的应用领 域，效果更差。例如关键词匹配过滤方法中，关键词库的最初构造是人工设定的， 由于方法的主观性，容易造成大量的合法邮件的误判和垃圾邮件的漏判。另一方面， 基于规则的过滤方法主要是分析邮件的头部信息，以及主题和正文的关键字匹配， 它对于头部信息和主题的过滤效果更好，而对于正文内容的判别还有相当的局限 性，仅仅根据有限的规则库内容进行判别是不够的。 基于概率统计的过滤方法中，目前贝叶斯分类方法表现出很好的性能，对于这 类方法的研究和使用也在不断进行，贝叶斯方法的本质是基于对邮件中的特征词进 行统计来判别垃圾邮件。s a h a m i ( 1 9 9 8 ) 最早提出贝叶斯分类算法在邮件过滤中 的应用，使用朴素贝叶斯算法，构造垃圾过滤器，使用该方法对邮件内容部分做统 计也易于操作和实现，但朴素贝叶斯方法是基于最小错误率的决策方法，对于合法 邮件的误判损失没有纳入特别考虑，而实际应用中，对合法邮件的误判造成的影响 和损失往往比垃圾邮件的漏判更大，由于这种因素的存在，使得实际应用中的邮件 系统采用基于贝叶斯方法进行自动过滤的方式有相当大的阻碍，因为将合法邮件判 为垃圾邮件这种错误是用户不能容忍的，邮件服务商也会顾虑承担这样的风险。因 此，本文基于这种实际情况，提出对于传统的朴素贝叶斯方法仍需要进行改进，将 重点研究改进方法，以减少误判带来的损失。 另外，关于基于服务器端和客户端过滤，其中对于基于服务器过滤来讲，前面 曾经提到，在邮件过滤模型的层次中，过滤越往外层，就越能减轻内层的压力。邮 件服务器位于邮件系统的外层，因此在这里过滤保障了邮件服务器的安全，减少了 内层压力，也间接保障了客户端的安全，但是由于过滤器和邮件服务器紧密集成， 系统开销大，对硬件配置的要求较高；而对基于客户端的过滤，过滤特点是个性化 强，用户可以根据自己的需要定制自己的过滤机制，灵活机动，保障客户端系统安 4 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 全；系统开销小，成本低。但是由于过滤器设置在客户端，它不能保证服务器的安 全。 经以上对垃圾邮件过滤技术的分析和比较，本文将进行基于邮件文本内容分析 的过滤模型构建，给出经邮件预处理、邮件向量化和训练学习后的贝叶斯算法的实 现，并对朴素贝叶斯算法进行改进，采用风险决策判断，实现算法，最后，设计和 实现一种基于客户端的垃圾邮件过滤器。 1 3 研究目标与内容 本文的研究目标是基于内容分析的贝叶斯分类的过滤算法，构造垃圾邮件过滤 模型，并对相关算法进行分析、比较、验证和测试，最后基于改进的贝叶斯算法， 实现对垃圾邮件的过滤。 本文的主要工作是研究探讨基于内容分析的邮件过滤方法，分析贝叶斯算法及 其改进算法的原理和实现方法，并研究过滤原型系统的设计、实现方法。主要工作 内容如下： 1 对当前现有过滤技术发展现状、基本原理、基本方法和过程进行研究和分 析，并对主要过滤技术的优缺点进行比较，提出基于贝叶斯原理的邮件过滤模型 ( s f 惦b ，s p a r ef i l t e rm o d e lb a s e do nb a y e s i a na r i t h m e t i c ) 。 2 基于上述模型s f 船b ，对实现过滤器的关键技术进行研究，给出邮件判别 过滤前的邮件文本处理过程，解决基于向量空间模型的邮件文本信息表示、文本词 切分的实现、文本分类中的特征向量的选择、提取和降维处理等问题，作好邮件文 本判别前的预处理工作。 3 在对实现过滤器的关键技术中，主要针对基于朴素贝叶斯方法及在其基础 上改进的基于风险决策的贝叶斯方法进行深入研究，并使用以上算法进行邮件的分 类和过滤，给出算法实现流程和具体步骤，给出朴素贝叶斯算法和基于风险的贝叶 斯算法效果及可行性验证。 4 基于以上算法和过滤模型s f m b b ，以j a v a 为平台，设计和实现一个过滤原 形系统，完成邮件的过滤全过程。 1 4 研究方法与路线 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 对于邮件正文内容的分析判别，主要是在预处理的基础上运用贝叶斯原理，将 经预处理的邮件进行训练和分类。 对邮件预处理的方法是将邮件正文内容作为文本，通过文本分析技术进行文本 特征向量抽取，并进行特征向量降维处理，为下一步的分类打好基础。 为提高垃圾邮件的判别正确率，在原有实现朴素贝叶斯方法判别基础上，给出 基于最小风险的贝叶斯方法的判别策略和实现过程。 通过动态更新特征库，为改善垃圾邮件的漏判起到一定作用。 对于模型实现，是基于j a v a 平台实现邮件过滤的原型系统。 1 5 本文结构安排 本文共分为六章，结构安排如下： 第一章：介绍本文的研究背景、意义、内容及其技术路线。 第二章：构建基于文本分析技术的邮件过滤模型，主要介绍了邮件文本的结 构和基于文本分析的垃圾邮件过滤实现的关键技术。 第三章：对本文邮件过滤中使用和改进的主要技术方法进行理论分析和研究， 主要对邮件过滤中使用的主要算法进行详细分析。 第四章：给出基于最小风险决策贝叶斯方法的邮件过滤实现过程以及对算法 的效果和可行性进行验证。 第五章：介绍原形系统的设计与实现。 第六章：总结本文所作的研究工作，指出有待改进的问题。 6 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 第二章基于文本分析技术的垃圾邮件过滤模型 通常，基于规则的邮件过滤方法主要是根据邮件头信息进行。为了进一步 提高邮件过滤的有效性和正确性，还需要对电子邮件正文内容进行分析。对于 正文内容的分析，其主要方法是基于文本分析技术，特别是文本分类和过滤技 术。本章的主要工作是：首先分析电子邮件组成结构，然后介绍实现垃圾邮件 过滤的关键技术和处理过程，最后给出基于文本分析技术的垃圾邮件过滤模 型。 2 1 电子邮件及组成结构 电子邮件有其特定的结构特点，邮件的协议和内容格式也是由r f c ( r e q u e s t f o r c o m m e n t s ) 的几个文档规定的。r f c8 2 1 规定了s m t p ( s i m p l e m a i l t r a n s f e r p r o t o c o l ，简单邮件传输协议) ，定义发送邮件的机制。r f c1 7 2 5 规 定了p o p 3 ( p o s to f f i c ep r o t o c o l3 ，邮局协议版本3 ) ，定义从p o p 3 服务器收 取邮件的机制。r f c8 2 2 定义邮件格式。随着电子邮件的广泛使用，邮件系统 不仅需要传输各种字符集的文本内容，而且还需要传送各种非文本文件( 例如 图像文件、w o r d 文件、p d f 文件、z i p 文件等) ，根据这个需求，又出现了m i m e 标准，作为r f c8 2 2 的补充。m i m e 即m u l t i p u r p o s ei n t e m e tm a i le x t e n s i o n s ， 多用途互联网邮件扩展协议，它由c 1 5 2 1 和r f c l 5 2 2 这两个标准构成。目 前几乎所有的邮件服务系统都支持m i m e 标准。 一封完整的电子邮件有多个首部字段和正文组成，它们中间由一个空行分 割。参见如下电子邮件结构示意图2 1 。 首部是由一个冒号( ：) 分开的一些名值对。首部名不区分大小写，但是其 中有的值区分大小写。一般说来，首部可以有以下形式：必选首部、可选首部、 动态首部及用户自定义的首部。每个r f c 8 2 2 消息都有多个首部是必须填的， 即只有包括这些首部，消息才能具有足够的信息以进入邮件系统，才能在邮件 系统中传送。必选首部有：d a t e 、f r o m 、t o 等。d a t e 首部给出了发送消息的 时间和日期；f r o m 首部提供了发件人的姓名；t o 首部用来识别消息的收件人。 可选首部有c c ，s u b j e c t 等。可选的c c 可以使一条消息复制给其他的收件人； 可选的s u b j e c t 表示消息的主题。动态首部由m t a ( m a i l t r a n s f e ra g e n t 邮件 7 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 传输代理) 自动创建。动态首部有：m e s s a g e e d 、r e c e i v e d r e t u r n p a t h 等。一 个用户t l 定义的首部应该由一个“x _ ”来打头。 f r o m发件人姓名 首 t o 收件人信息 d a t e 发送时间和日期 部 s u b j e c t主题( 可选项) 正正文文本包含a s c i i 字符型和各 种数据类型的纯文本 文 附件w o r d 、图象、音频等非文 本文件 图2 1 电子邮件结构示意图 消息的正文与其首部相隔一个空行。对于消息正文来说，除了a s c i i 字符 型之外，还可以包含各种数据类型。用户可以使用m i m e 增加非文本对象，譬 如图象、音频、格式化的文本。 通过对电子邮件结构的分析，为下一步根据邮件结构特点进行过滤提供了 依据。本文将针对邮件正文内容进行分析和判别邮件类型。 2 2 基于文本分析的垃圾邮件过滤实现的关键技术 垃圾邮件过滤实现的关键是分析邮件特征，涉及到的主要技术是文本分析 技术，主要包括：文本切分词、特征向量的生成以及基于内容分析的文本分类 技术。下面介绍相关技术。 2 2 1 文本自动分词 文本的词语切分对最终的查全率、准确率、运行效率起着重要的作用。 文本分词方法与其基于的语言相关，通常有中、英文两种。对于英文分词， 主要以非字母符号隔开，如空格、标点符号等，其分词方法是连续读字母符号 直至非字母符号为止；对于中文分词相对情形较复杂，中文词间没有明显的界 限，并且中文文本具有多样性、复杂性、上下文干扰等因素，所以中文分词的 难度要远大于英文分词。采用不同的方法进行分词，也会有不同的效果，准确率、 8 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 查全率等指标也会有不同影响。分词的精度也是影响系统准确率的一个重要因素。 文本分词的研究相对比较成熟，主要有以下几种研究方法n 伽恻：基于规则的 方法( 也称基于词典“”的分词法，例如最大匹配法( m a x i m u mm a t c h i n g ) 、最优路 径法等) 、基于统计的方法( 也称无词典分词法，如基于h m m ( h i d d e nm a r k o v m o d d s 隐马模型“”) 和肌删( h i e r a r c h i c a lh i d d e nm a r k o vm o d e l 多级隐马模 型“”) 等方法) 、基于规则和基于统计相结合的方法。 常用的具体分词方法主要有：最大匹配啪】嘲( 包括向前、向后以及前后 相结合) 、最短路径方法、全切分方法制以及最大概率方法d “。下面分别进行 介绍并对比分析如下： 1 、最大匹配分词法 它是一种基于规则的方法，简单易行。该切分过程依赖于机器词典进行， 该词典中较少涉及语法、语义、句法知识等关于语言自身的信息。该方法实现 过程为：对于给定的待分词的汉字串，按照某种确定的规则( 这里按每次匹配 是优先考虑长词) 切取其子串，若该子串与词典中的某词条相匹配，则该子串 是词，继续分割其余部分，直到剩余部分为空。按切取子串的方向来分，可分 为正向( 向右) 匹配法和逆向( 向左) 匹配法。但是该方法由于基于纯词典的方法 不涉及太多语法语义信息，会产生歧义字段等问题( 如交叉歧义、组合歧义) ， 而且字典本身具有不完备性，因此最终的准确率不会太高，适于粗分过程的预 处理，为保证最终的分词质量，常与其他方法配合使用。 2 、最短路径方法 该方法采取的规则是使切分出来的词数最少，符合汉语自身的语言规律， 能够取得较好的效果，但是同样不能正确切分许多不完全符合规则的句子。如 果最短路径有多条，往往只保留其中一个结果，容易产生舍弃在其他同样符合 要求的路径中可能存在的正确结果，造成分词的不准确。 3 、全切分 该方法列举出所有可能的切分结果，有一定合理性。但是，全切分产生的 切分结果数会随着句子长度的增大而成指数级增大，而且大多数是无效结果， 对正确结果的生成没有太大帮助，求取切分结果，非常困难而且费时。因此该 方法和实际需求还有一定差距。 4 、最大概率分词方法 是一种基于统计的方法。基于统计的方法一般只需进行字频统计，不需要 9 东南大学硕士学位论文 种基于内容分析的邮件过滤模型的研究与实现 切分词典，通过计算相邻字出现的概率，计算它们的互信息( 互信息体现了汉 字之间结合关系的紧密程度) ，当互信息值高于某一个阀值时，便可认为这个 字组可能构成了一个词。这里最大概率分词方法通过计算各个词的词频相乘的 联合概率求取最终的切分结果，是一种效果较好的分词方法。最大概率分词方 法实质上是一种简单变形的最短路径方法。 本文采用n 最短路径法进行文本分词。该方法将最短路径方法和全 切分方法进行有机结合。根据切分的目标，先快速找出包含正确结果在内的n ( n 1 ) 种粗分结果。然后综合考虑速度和召回率，确定n 的最佳值，最终 得到涵盖最终结果在内的尽量小的粗分结果集。其实现的基本思想是：根据词 典，找出字串中所有可能的词，构造词语切分有向无环图。每个词对应图中的 一条有向边，并赋给相应的边长( 权值) 。然后针对该切分图，在起点到终点 的所有路径中，求出长度值按严格升序排列( 任何两个不同位置上的值一定不 等，下同) 依次为第l ，第2 ，第i ，第n 的路径集合作为相应的粗 分结果集，n 为选取的最佳路径数值。在n = l ( 只能选择唯一的路径) 和n = 一时， 该方法还原成最短路径方法和全切分方法。 该方法的出发点是尽量减少切分出来的词数，同时又要尽可能的包含最终 结果，这分别综合了最短路径分词方法和全切分的优势。通过这种综合，一方 面避免了最短路径分词方法大量舍弃正确结果的可能，另一方面又较大改善了 全切分搜索空间过大，运行效率差的情景。本文采用该方法进行分词，即将最 短路径方法和全切分做有机结合，进行文本自动分词。 2 2 2 文本特征表示 i 、文本表示及去词处理 目前，在文本分类领域中，广泛采用向量空间模型( v 涮，v e c t o rs p a c e m o d e l ) 来表示文本信息“，在这种表示方法中，一篇文本可以表示为个n 维 向量，即d ( w 。，耽砜) ，其中，w i 为第i 个特征项( t e r m ) 的权值，n 是特征 项的个数，特征项可以是字、词、短语或者某种概念，本文采用词作为特征项。这 样文本表示就转化为先进行文本分词，再由这些词作为向量的维数来表示文本。 文本经过分词处理后，将得到一个庞大的词库，在使用向量空间模型表示 文本之前，必须经过一系列的去词处理过程，留存能够较好表达文本特征的词。 1 0 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 首先，要将一些在语言中经常被使用但又没有实际意义的词，例如“的，是， 这”等虚词去除，因为它们对文本的类别是不具有表现力的。这些词被称作停 用词( s t o p - w o r d s ) ，通常有一个普遍适用的停用词表( s t o p - w o r d sl i m ) ，依据 该表进行去停用词处理，以减小词库。其次，合并重复或对分类无取向意义的 词，如数字、人名等词，去除表现力不强的词汇，而只截取词干。 本文选取词作为特征项，为体现词在文本中的作用程度，需对词频进行统 计，以更好地描述向量。一般v s m 中的权值计算可以采用基于数值型空间模型的 词频t f ( t e r mf r e q u e n c y ，表示该特征词在文本中出现的次数) 表示和基于布尔 型空间模型方法表示。t f - i d f ( t f - i n v e r s ed o c m a e n tf r e q u e n c y1 f _ 倒排词频) 表示方法目前较多用于基于数值型空间模型的权值计算。本文采用基于数值型空间 模型进行权值计算，因为相对于基于布尔型空间模型方法，它的精确度更高。 在本文的工作中，将邮件正文作为文本，文本经分词程序分词后，经去除 停用词，截取词干等预处理步骤后减少词库大小，最终将邮件文本描述为向量。 2 、文本内容的特征项选择和提取 文本经过预处理后，使用特征向量表示的文本的向量空间维数仍相当大，为提 高程序效率和运行速度，需要进一步解决向量压缩问题，提取出有针对性的特征项 集合，因此需要做迸一步的特征项选择和提取工作。 文本分类中的特征选择( f e a t u r es e l e c t i o n ) 和特征提取( f e a t u r ee x t r a c t i o n ) 就是通过构造一个特征评价函数，把钡i 试空间的数据投影到特征空间，得到在特征 空间的值，然后根据特征空间中的值对每个特征进行评估，特征选择就是选择值最 高的若干个特征。常用的特征项选择的方法有以下几种“： 1 ) t f i d f 方法“ 该方法是s a l m n 和m c g i l l 在1 9 8 3 年针对向量空间信息检索范例( v e c t o r s p a c ei n f o r m a t i o n r et r i c v a l p ar a d i g n ) 提出的文档特征表示方法。其中，t f ( t c r m f r e q u c n c y ) 称为词频，指给定词在给定文档中出现的次数，它反映了特征相对 于某文档的重要程度，默认出现的次数越多越重要；f ( i n v e r s ed o c u m e n t f r e q u e n c y ) 称为倒排词频，是反映一个特定的词项在一个文件集中按文件统计 出现的频繁程度的指标，它表示包含某特征的文档越多，则该特征越不重要。 它们的计算方法表示如下： i d f ( t i 户l o g ( i d i d f ( t i ) ) ； 东南大学硕士学位论文 一种基于内容分析的邮件过滤模型的研究与实现 t f ( t i ，d ) ：项t i 在文档d 中出现的次数； d f ( t i ) ：d 中包含项t i 的文档总数； i d i ：d 中的文档总数。 可以看出，t f i d f = i f ( t i , d ) + i d f ( t i ) 。某个词的表现力与t f 成正比，与 d f 成反比，这在一定程度上减少了常用词的影响，突出了某些特殊的词。 t f - i d f 方法是基于特征与文本自身相关联的，本文使用该方法进行特征 提取，找出对类别区分有较强表现力的特征项。 2 ) 互信息 t f - i d f 方法仅考虑了特征与文档间的关系，而没有反映特征与类别的关系， 而互信息、信息增益等方法都反映了特征与类别的关系，互信息( m u t u a l i n f o r m a t i o n ) ，简称m i ，定义如下： 旭= 墨 1 - 旭=百 i v ， ( 公式2 1 ) 上式中p ( c i ) 表示第i 类文本在训练文本集合中出现的概率，p ( t ) 表示词 t 在训练文本集合中出现的概率，p ( ti c i ) 表示在第i 类的文本中t 的出现概率。 m i 越大，词和类的共现程度也越大。 通常的互信息定义为：变量t 和c 的 m i ( t ，c ) = l o g ( p ( t ，c ) ( p ( t ) 卯( c ) ) ) = l o g ( p ( t c ) p ( t ) ) 3 ) 信息增益 信息增益( i n f o r m a t i o nc a i n ) ，简称i g ，定义如下： l c ll q l c - ( t ) = - z 即。) l o g p ( c j + p ( t ) 酏1 0 1 0 9 p ( c , i t ) a - ip 日 i c l 一 + 跗p 纯l t ) l o g p ql f ) “ ( 公式2 2 ) i g ( t ) 反映了该词为整个分类所提供的信息量。 上式中，p ( t ) 表示词t 不出现的概率，p ( c i l t ) 表示词t 出现的情况下文 本属于类c i 的概率，p ( c it - ) 表示词t 不出现的情况下文本属于类c i 的概率。 下面的公式中相应变量的含义与此相同。 4 ) k l 距离( k u l l b a c k - l e i b l e rd i v e r g e n c e ) 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 i 0 = c e ( o 昙p ( c ，1 0 0 8 等 p ( c ，等等 扣i p i ， ( 公式2 3 ) 也称为相对熵，反映了文本类别的概率分布和在出现了某个词的条件下文本 类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。 在以上多种特征值抽取方法的算法中，在判断函数上有所差别，但主要过程基 本类似。 为使特征提取更有利于最后的文本分类，通常将几种特征选择方法根据各自的 特点结合使用，以取褥更理想的分类结果。 在本文中主要使用了t f 与i d f 相结合的方法进行邮件文本特征选择和提取。 2 2 3 基于内容分析的垃圾邮件过滤的文本分类方法 大多数文本分类方法都可以应用于垃圾邮件过滤，在基于内容的邮件过滤的处 理方式上，主要有以下两大类： 1 ) 基于规则的过滤方法。该类方法通过训练得到规则，通过考查个个训练 样本，归纳出规律性的规则，通过生成的规则集进行决策，对邮件进行分类。常见 的基于规则方法有：r i p p e r 方法，决策树方法和b o o s t i n g 方法等。对于邮件头部 及主题和正文内容过滤都可以采用基于规则的过滤方法 2 ) 基于概率统计的方法。该方法将文本分类方法应用于电子邮件过滤中， 将邮件分类为合法邮件和垃圾邮件，该方法运算速度快，分类精度高。主要的统 计方法有：k n n ( k - n e a r e s t - n e i g h b o r k 最近邻法) 方法、s v m ( 支持向量机) 方法和b a y e s ( 贝叶斯) 方法等。 下面分别介绍几种常用的文本分类方法并对其优缺点进行比较： l 、基于规则的过滤方法 1 ) r i p p e r 方法嘲 r i p p e r 是w i l l i a mw c o h e n 提出的一种基于规则的方法。它不是基于文本 中所有词语的权值做决策，而是使用r i p p e r 算法学习训练集中的所有正例，形 成一个正例的规则集，然后利用所有反例对规则集中的关键字加入约束条件， 最后使用这个新生成的规则集来做出决策。 这种方法对基于邮件内容进行一般分类时具有一定作用，但在过滤在线邮 件时仍有许多缺陷：由于需要对规则集进行人工处理，对构建过滤规则的用户 要求较高；另外，由于垃圾邮件的属性也在不断改变，需要用户重新进行训练 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 和调整规则，因此在训练样本集和建立规则集的过程中，需消耗大量的时间， 不适应于电子邮件的过滤。 2 ) 决策树方法( d e c i s i o nt r e e ) 决策树方法是典型的基于规则的方法。它是从训练集中学习得到以决策树 的形式表示的分类规则。分类时，将待分类的文本按照属性值自树根向下逐步 比较判断，到叶子结点时，就可以确定文本所属类别。 决策树实际上就是一系列规则的形式化表示，训练的过程就是从样本中学 习决策树或者说是学习规则，分类的时候就是沿着决策树往下走到叶子，找到 类别归属。 决策树的学习有i d 3 、c 4 5 、c 5 o 等著名算法。c a r r e r a s ”。曾使用决策树算 法过滤垃圾邮件，采用t f - i d f 方法描述特征，效果一般，目前决策树方法效 果不突出，它更适应于训练集中邮件数较小、待分类邮件中的非法邮件较多的 情况。当对大量的邮件过滤，或邮箱中有较多的合法邮件时，基于决策树的邮 件过滤器对合法邮件的查全率和查准率都较低。它本身也并不常被用于垃圾邮 件过滤，而是作为b o o s t i n g 方法的弱学习器来使用。 3 ) b o o s t i n g 方法 准确地说b o o s t i n g 方法不是一种特定的学习方法，它通过对已有分类器 ( 弱规则) 进行加权求和得到最终分类器( 强规则) ，理论上说，任何机器学 习方法都可以作为b o o s t i n g 的弱学习器，但实际中常常使用基于规则的方法， 如以上决策树法，因此，也将它归为基于规则的方法。其中，“强规则”为准 确率很高的分类规则，“弱规则”为准确率不高、仅比随机猜测略好的分类规则。 最简单的弱假设h 可以这样定义： f + l ，如果硝燕足菜个断蓑 l 一1 ，王不满足p 弱规则比较好寻找，而强规则较难。b o o s t i n g 方法就是通过一定的训练方 法逐步将一系列弱规则集合提升为强规则。b o o s t i n g 方法的基本思想是：给每 个训练样本都赋予一个权重，进行t 次迭代，每次迭代后，对分类错误的样本 加大权重，使得下一次的迭代更加关注这些样本。 b o o s t i n g 方法有多种形式，如a d a b o o s t 、a d a b o o s t m 1 、a d a b o o s t m h 等。 b o o s t i n g 方法的最主要缺点是训练速度较慢，对于实时处理和大量信息文 本处理会有一定影响。 1 4 东南大学硕士学位论文一种基于内容分析的邮件过滤模型的研究与实现 2 、基于统计的过滤方法 1 ) k 近邻( k n n ，k - n c a r c s tn e i g h b o r ) 方法 近邻法是c o v e r 和h a r t 于1 9 6 8 年提出的，k 近邻法是最近邻法的一种推 广 k 近邻法在最近邻法的基础上，取未知文本向量d 的k 个近邻，看这k 个 近邻多数属于哪一类，就把d 归为哪一类。具体说就是首先在n 个已知样本的 训练集中，找出k 个近邻；然后计算出这k 个近邻中属于c l ，c 2 ，c m 类的样本 数，分别为k l k 2 ，k m ，k 近邻法的决策规则为： 如果卸吲2 m a x * , 。2 1 名”、。则d 属于c i 类。 k 近邻也是m e m o r y - b a s e d 中最常用的一种分类方法，它没有训练过程， 而是直接利用训练集分类，分类过程如前所述。 k