（计算机应用技术专业论文）基于改进贝叶斯模型的中文邮件过滤系统.pdf

l p 摘要 摘要 随着电子邮件在世界范围内的广泛应用，垃圾邮件作为商业广告、恶意程 序或敏感内容的载体，对系统安全和人类生活所造成的影响越来越严重，反垃 圾邮件问题作为一个全球性的课题具有重要的现实意义。另据统计表明，目前 我国已经成为第二大垃圾邮件受害国，因此，针对于中文垃圾邮件的识别与过 滤更显得尤为重要。 邮件过滤技术是反垃圾邮件的重要手段，目前的垃圾邮件过滤技术主要分 为两种：基于规则的过滤和基于概率的过滤。基于规则的过滤从邮件的结构出 发，通过对垃圾邮件特征的总结制定相应的过滤规则，但是垃圾邮件的表现形 式变化迅速，规则的维护并非易事。 基于概率的过滤技术是从邮件信体包含的内容出发，利用文本分类方法对 邮件类别进行判断。由于信体是垃圾邮件信息的最终载体，因此基于概率的过 滤具有较高的准确性，成为当前邮件过滤技术的主流。 论文对基于概率的邮件过滤技术进行讨论，其中着重研究贝叶斯算法及其 相关模型，详细介绍了朴素贝叶斯方法，最小风险贝叶斯方法的原理。论文在 贝叶斯方法现有的二项独立模型和多项式模型的基础上，结合最小风险贝叶斯 方法的思想，提出一种新的更加完善的贝叶斯分类器构造模型：改进贝叶斯模 型。实验表明，此模型具有较好的分类准确率和查全率。 论文结合邮件分类器的实现与测试，给出一种垃圾邮件过滤系统的设计结 构及具体实现。系统以分类器为核心，利用l i n u ) 【环境下的开源软件s e n d m a i l 作为邮件服务器的主体，通过对s e n d m a i l 提供的m i l t e r 接口的开发和扩展实现 邮件过滤的功能；邮件分类器模块以插件形式嵌入m i l t e r ，并可根据需要更换 或添加其他分类算法；系统采用先进的实时中文分词技术和邮件解码技术，使 其更好的适用于中文邮件的分类工作。论文最后对系统的整体性能进行了联机 测试，给出系统在分类性能以及时间效率两方面的测试结果。 关键字：垃圾邮件，中文邮件分类，贝叶斯，m 订t e r 接口 ip l a b s t r a c t a b s t r a c t a l o n gw i t ht h ee x t e n s i v e 印p i i c a t i o no fe m a i l ，s p a i t l sa c t i n ga st h ec a r r i e ro f b u s i n e s sa d v e r t i s e m e n t s ，t h em a l i c ep r o g m m so rs o m es e n s i t i v em a i l sa r et 1 1 r e a t e n i n g t h es a f e t yo f t h ec o m p u t e rs y s t e m sa 1 1 dt h ed a i l yl i f eo f p e o p l em o r ea 1 1 dm o r ef i e r c e l y n o wt h ep r o b l e ma b o u ta 1 1 t i s p 锄h a sa l r e a d yb e c o m ea ni n t e m a t i o n a l ，s i g n i f i c a n t a n dp r a c t i c a lt o p i c a c c o r d i n gt os t a t i s t i c s ，t o d a yc h i n ah a sb e c o m et h es e c o n do n e 帅o n gt h ec o u n t r i e st h o s ev i c t i m i z e db ys p a r n t h e r e f o r e ，i d e n t i 母i n ga 1 1 df i l t e r i n gf o r t h es p 锄i nc h i n e s es e e m e dt ob ev e r yi m p o n a n t 1 1 1 em a i lf i l t e ri so n eo ft h ek e yt e c h n o l o g i e sf o ra n t i s p a n l ，c u r r e n t l y ，t h e r ea r e t o wm a i n l yk i n d so fm e t h o df o ra 1 1 t i s p a r n o n ei st h em e t h o db a s e do nr u l e sa 1 1 dt h e o t h e ri sb a s e do np r o b a b i l i t y t h ew o r k i n gp r i n c i p l eo ft h en r s tm e t h o di sm a t ， a 1 1 a l y z i n g m es t m c t u r eo fs p 帅s ，s u m m 撕z i n gt h ec h a r a c t e r sf o mt h e m ，t h e n d e f l n i n gt h em l e sb yt | l ec h a r a c t e r s b u t ，t h ec h a r a c t e r so fs p 锄sa r eo r e nc h a l l g e ，i t i sv e r yd i f f i c u l tt o 丘n i s ht h em a i n t a i n i n go fm l e sc o l l e c t i o n n l em e 山o dw h i c hb a s e do np r o b a b i l i t yi sm o r eu s e m ln o w a d a y t h ep r i n c i p l e o fi ti sa b s t r a c t i n gt h ec o n t e x ti ne m a i lf r o mt h em a i lb o d y ，a n a l y s i n gt h ec o n t e n t sb y t e x tc l a s s i f i c a t i o nm e t h o d a sw ea l lk n o w 山ec o n t e x to fe m a i li st h ef i n a lc a 玎i e ro f t h em e s s a g et 1 1 a ts p a r nm a k e rw a i l tt os p r e a d f o rt 1 1 i sr e a s o n ，t h ef i l t e r l e s sm e t h o d b a s e do np r o b a b i l i t ya l w a y sh a sg o o dp e r f o 册a i l c ei nt | l ea r e ao fs p 锄f i l t e r t h et r e a t i s ed i s c u s st h ep o p u l a rt e x tc l a s s i f i c a t i o na l g o r i t s ，t 1 1 e r e i n ，m a i l l l y w o r ko nt h eb a y e s i a l la l g o r i t l l i t l 1 1 1 et r e a t i s ei n d u c et h en a i v e b a y e s i a i la l g o r i t h r n a n dt h em i i l i m i z a t i o nb a y e s i a na l g o r i t h mt h o m u g h l y ，a l s og i v eo u tan e wm o d e l ， w h i c hi sb a s e do nt h eb i n a r yi n d e p e n d e n c em o d e la n dm u l t i n o m i a lm o d e l ，m et w o m a i n l ym o d e lt oc o n s t r u c tt h eb a y e s i a nc l a s s i f i e r ，c o m b i n ew i t ht h em i n i m i z a t i o n b a y e s i a i la l g o r i m m e x p e r i m e n t sp m v e dt h a t ，t h i sm o d e lh a dg o o dp e r f b 啪a n c eb o t l l i nr e c a l la j l dp r e c i s i o n f o ri m p l e m e n t i n ga n dt e s t i n gt h eb a y e s i a nc l a s s i f i e r ，t h et r e a t i s eg i v eo u tr c a i i t y m o d e lf o rs p 嘲f l i t e rs y s t e m n l ek e m e lo f 血es y s t e mi st h eb a y e s i a nc l a s s i f i e r r a b s t r a c t b a s e do nt l l en e wm o d e l ，i tu s es e n d m a i ls u p p o r t e db yl i n u xa st h ep l a t f o r mo ft h e e m a 订s e r v e r ；b yd e v e l o p i n gt h em i l t e ra p ii ns e n d m a i l t h em o d u l eo fc l a s s i f i e ri s a d d e dt ot h em a i ls e r v e r ；t h ec l a s s i 行e ri su s e da sp l u g i n ，i tc a nb ee x c h a n g e db y o m e ra l g o r i t h n s ；a p p l y i n gw i t l lt h er e a l t i m ec h i n e s ep a n i c i p l ea 1 1 dd e c r y p t i o no f t h ee m a i l ，t h es y s t e ma d a p tt oc l a s s i f yt h ee m a i li nc h i n e s ew i d e l y ；a tt h ee n do f t h et r e a t i s e ，t e s t i n gr e s u l to ft h ew h o l es y s t e mo n l i n eh a sb e e ng i v e no u tb o t ha st h e c l a s s m cp e r f b n i l a i l c ea n dt i m ee m c i e n c yo ft h es y s t e m k e yw o r d s ：s p 锄，e m a i lc l a s s i 匆i nc h i n e s e ，b a y e s i a j l ，m i l t e ra p i 第一章引言 第一章引言 第一节现代社会与垃圾邮件 伴随着网络的迅速普及，电子邮件在现代社会中扮演着越来越重要的角色， 它成为继书信、电报、电话之后的又一主要通讯方式，并大有取代前者之势， 无论是普通用户或是企业公司都会同时拥有一个或几个电子邮件地址。同时正 是由于电子邮件的这种普遍性，以及发送成本的低廉性使其成为一些广告商和 不法分子的利用工具。垃圾邮件开始充斥着人们的电子邮箱，甚至影响正常的 生活与工作，对垃圾邮件的处理已经达到刻不容缓的地步。 据邮件过滤服务商m e s s a g el a b s 公司统计，目前平均每2 6 封邮件就有一封 垃圾邮件，每一封垃圾邮件造成的损失至少是一美元，这包括占用的带宽资源、 上网费用以及病毒破坏等。a o l 、雅虎以及h o t m a i l 等i s p 所处理的邮件中，垃 圾邮件的数量已经过半；美国b r i 曲tm a i l 公司的报告显示，垃圾邮件占电子邮 件的比例已上升至4 0 ，2 0 0 2 年美国人平均会收到2 2 0 0 封垃圾邮件，若按垃 圾邮件每月增长2 的速度递增，到2 0 0 7 年这一数字将达到3 6 0 0 封；垃圾邮件 将占到全球电子邮件流量的6 5 “1 。 另据s b l d a t a b a s e 著名垃圾邮件对比资料库统计，全球1 0 大垃圾邮件最严 重的国家和地区，亚洲占了绝大部分。中国的6 8 0 0 万网民每年收到的垃圾邮件 为4 6 0 亿封，占全球的1 0 4 ，并且这一数字每五个月会翻一番。我国已成为 仅次于美国的全球第二大垃圾邮件受害国“3 3 。据第十三次c n n i c 调查结果显 示，目前，中国网民平均每周收到正常电子邮件5 8 封，收到垃圾邮件7 9 封， 这一数字虽然与半年前的8 9 封相比有所降低，但网民每周收到的垃圾邮件仍然 超过非垃圾邮件。据业内专家估计，即使是保守地测算，垃圾邮件每年给中国 网民造成的损失也超过亿元。 我国成为垃圾邮件第二大受害国，由此造成的直接危害有六点： ( 1 ) 大量浪费我国的社会资源，占用了大量的传输、存储和运算资源，造成 邮件服务器拥塞，降低网络的运行效率，严重影响正常的邮件服务。 ( 2 ) 我国开始被其他国家视为垃圾邮件的温床，许多i p 地址存在遭受封杀 第一章引言 的危险，长期下去可能使我国成为“信息孤岛”。 ( 3 ) 垃圾邮件以其数量多、反复性、强制性、欺骗性、不健康性和传播速度 快等特点，严重干扰了用户的正常生活，侵犯收件人的隐私权，侵占收件人信 箱空间，耗费收件人的时间、精力和金钱。邮箱里塞满来历不明的垃圾邮件是 最让邮件用户头疼的事了，如果全是垃圾邮件还好，但往往里面同时又混杂着 同事、朋友和用户来的来信。处理这些邮件耗费大量的时间，影响工作效率， 令人困扰。 ( 4 ) 垃圾邮件被黑客利用，成为助纣为虐的工具。如在2 0 0 0 年2 月，黑客 首先侵入并控制了一些高带宽的网站，集中众多服务器的带宽能力，然后用数 以亿万计的垃圾邮件猛烈袭击目标，造成被攻击网站网路堵塞，最终瘫痪。 ( 5 ) 严重影响i s p 的服务形象。在国际上，收到垃圾邮件的用户会因为i s p 没有建立完善的垃圾邮件过滤机制，而转向其他i s p 。一项调查表明：i s p 每年 因为垃圾邮件要失去7 2 的用户。 ( 6 ) 妖言惑众、骗人钱财、传播色情、反动等内容的垃圾邮件，已经对现实 社会造成了危害。 因此，如何有效解决垃圾邮件造成的危害已经成为中国信息化建设的当务 之急。 第二节反垃圾邮件的研究现状 面临着垃圾邮件问题日益严重的现状，人们开始从多方面寻找解决方案。 例如，一些“邮箱运营商”成立了专门的部门处理垃圾邮件，并设立“首席垃 圾邮件官”，有些邮件客户端工具也提供了一定的垃圾邮件过滤功能。 解决、缓解垃圾邮件问题的方法和手段一般有： ( 1 ) 反垃圾邮件立法。例如，一旦确认某个团体或个人是垃圾邮件的发送者， 那他就面临着法律的制裁与处罚：或者规定发送任何邮件都要付出一定的“邮 票”代价，以此来制约垃圾邮件发送者大规模重复的发送邮件。针对目前垃圾 邮件泛滥的现状，反垃圾邮件立法的呼声日益渐高，中国互联网协会反垃圾邮 件协调小组2 0 0 4 年2 月1 8 日在北京发出关于加快“反垃圾邮件立法”进程的 倡议，得到了众多组织机构和邮件用户的响应。 但立法面临着一系列的问题。首先是垃圾邮件的概念之争，到底什么是垃 第一章引言 圾邮件，像宣传品、电子期刊等这类邮件是不是垃圾邮件很难界定，垃圾邮件 发送者会想尽一切办法逃脱法律的惩罚；其次是法律的执行问题，给予什么样 的处罚，而且如果缺少国际合作，即使发现来自境外的垃圾邮件，也无法制裁。 如果规定发送邮件都需要一定的额外代价，在现阶段显然很难得到广大邮件用 户的认可。 ( 2 ) 利用垃圾邮件过滤技术。近年来，有关垃圾邮件过滤技术的研究开始逐 步兴起，相关的投入也越来越大，涌现了一大批相关产品。垃圾邮件过滤技术 主要有基于规则的过滤和基于概率的过滤两种”1 。 垃圾邮件过滤技术，主要是依据电子邮件自身的结构特点进行设计。邮件 的协议和内容格式是由r f c ( r e q u e s tf o rc o m m e n t s ) 的几个文档规定的。r f c 8 2 l 规定了s m t p ( s i m p l em a i lt r a j l s f e rp r o t o c o l ，简单邮件传输协议) ，定义发 送邮件的机制。r f c1 7 2 5 规定了p o p 3 ( p o s t o m 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 ( 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 ，多用途互联 网邮件扩展协议) 标准，作为r f c8 2 2 的补充。它由r f c1 5 2 l 和r f c1 5 2 2 这 两个标准构成。目前几乎所有的邮件服务系统都支持m i m e 标准。 从电子邮件的结构出发，寻找垃圾邮件的特征，在发件人、收件人、邮件 头等各方面展开邮件过滤工作，是垃圾邮件过滤常采用的基本方法，这些方法 主要包括：s m t p 用户认证，实时黑名单过滤，可信白名单，设定过滤规则( 信 头分析，群发过滤，关键字匹配) 等，它们在一定程度对垃圾邮件的泛滥起到 的抑止作用。 但是，基于规则的过滤方法也有其不足之处。例如，通常情况下，并不仅 仅是某几个固定的发件人在发送垃圾邮件，发送者在不断地变化，这样使用黑、 白名单方法就有局限性。基于规则的方法需要人们不断去发现和总结、更新规 则，人为因素较多，一些没有经验的用户可能很难提供有效的规则。而且，手 工制定规则比较耗时，准确率也受到了限制。随着时间的变化，垃圾邮件的特 征也在变化，让用户维护这些规则也不是一件易事。 一个很自然的想法是，对电子邮件的内容( 如正文文本) 进行分析，识别 出垃圾邮件。发送垃圾邮件者的致命缺陷就是他们的邮件，迄今为止，他们可 第一章引言 以绕过任何反垃圾邮件技术所设下的其他障碍，但他们必须通过邮件的正文传 达一定的信息。基于概率的过滤方法正是可以通过对这些信息的分析，来达到 识别和过滤垃圾邮件的目的。 所谓的基于概率的过滤，指的是采用文本分类算法分析邮件正文中所包括 的文本信息，计算该文本属于不同类别的概率，进而对邮件属性进行判断的方 法。 i b m 的研究报告指出：“文本信息占现存电子邮件信息总量的8 0 以上”。 随着因特网的发展，多媒体信息数量日益增加，但是文本信息依然是人们在因 特网中获得信息的最主要途径。因此，利用文本信息处理技术( 主要是文本分 类方法) 对垃圾邮件的内容进行识别的基于概率的邮件过滤方法逐渐成为反垃 圾邮件技术的主流。 第三节本文研究内容 近年来，许多统计学习的方法和机器学习的方法被用于文本分类，包括： 决策树、决策规则、回归模型、k 近邻、贝叶斯方法、神经网络、符号规则学习、 归纳学习算法、休眠专家方法和支持向量机等等，其中，以贝叶斯方法的应用 最为广泛。 国外市场上的几种基于概率的反垃圾邮件工具，普遍采用贝叶斯分类器作 为其核心辨识模块。然而，由于贝叶斯分类器的先天的弱点( 分类性能不稳定) ， 使得这些工具在实际的网络环境中的表现并不如他们所宣称的那样好，而且， 中文信息处理又有不同于英文处理的特点( 它需要中文分词) ，所以国外的这些 反垃圾邮件工具对中文垃圾邮件的处理效果并不是很好，很难达到在我国实际 应用的要求。 针对上述问题，本文研究分析了现有的贝叶斯方法及实现模型，并着重在 提高贝叶斯分类方法的性能上作了相关的研究，提出一种改进贝叶斯模型，同 时结合中文处理技术及其他网络和计算机技术，实现一个反垃圾邮件系统。 系统采用基于概率的邮件过滤方法构造分类器作为系统的核心，充分利用 了l i n u ) ( 平台上的技术资源搭建系统，如：s e n d m a i l 邮件服务器、m i l t e r 可编程 接口等；在系统框架不变的情况下可以更换分类器算法，达到对不同的文本分 类方法的测试与比较；系统同时结合先进的实时中文分词技术和邮件解码技术， 第一章引言 适用于中文邮件的处理。 除了对系统的设计与实现以及相关技术的讨论，文中还对相关的文本分类方 法，邮件服务平台进行了介绍和分析。 第四节论文结构 本文共分七个部分，具体结构为： 第一章介绍当前垃圾邮件泛滥的现状，已有方案存在的缺点以及本文的研究 方向： 第二章就常用于垃圾邮件过滤的文本分类算法进行介绍： 第三章简述在邮件过滤过程中，应用文本分类算法所需要的准备工作； 第四章提出本系统分类器的构造，及分类性能等方面的实验结果； 第五章根据系统设计目标，选择适合的系统结构及系统模块关系； 第六章详细讨论系统各模块的实现方法，给出系统联机测试的结果； 第七章对系统的特点加以总结并给出了进一步完善的建议。 第二章文本分类方法的研究 第二章文本分类方法的研究 基于概率的邮件过滤方法，其核心内容是将文本分类算法应用到对邮件内 容的识别当中。目前，在邮件分类领域中使用的分类算法主要有贝叶斯方法、k 近邻方法、支持向量机、神经网络。其中，贝叶斯方法以其良好的分类准确性， 分类速度成为应用最为广泛的方法，下面本章将对这几种算法的原理进行简要 的介绍。 第一节贝叶斯分类方法 贝叶斯分类方法是一种以贝叶斯定理5 1 为核心的分类方法。贝叶斯方法的吸 引力在于它的简单性，它可以根据己知事件推断出未知，而这种预测完全取决 于收集到的数据，“获得的数据越多，结果就越好”；贝叶斯方法的另一个优点 在于贝叶斯模型能够自我纠正，也就是说“数据变化了，结果也就跟着变化”。 贝叶斯方法的这些特性，使得其在需要处理多个变量的系统中尤其有用。正因 为如此，贝叶斯方法已经成为基于概率的垃圾邮件过滤技术的基础。 2 1 1 贝叶斯定理 贝叶斯定理是一种基于统计学原理的概率计算方法，即认为一个事件会不 会发生取决于该事件在先验分布中已经发生过的次数。贝叶斯定理指出，对于 事件x 和y 已知，的概率时x 发生的概率( 用p ( 圈y ) 表示) 等于已知x 的概 率时l ，发生的概率( 用p ( y l y ) 表示) 乘以x 的概率( p 0 的) 再除以，的概率( j p ( y ) ) ， 或者用公式表述如下： 删m = 幽篇塑 这一公式更常用的表述为： p ( z iy ) ：善型盟 p ( 置) j p ( y l 五) 第二章文本分类方法的研究 举例说明： 假设要维护一个有3 个配置选项的软件包用户中用到a 选项的有4 0 ， 用到b 选项的有3 0 ，用到c 选项的有3 0 ( 假定用户每个时刻只能使用一种 选项) 。 如果假设每个选项可能导致的技术支持请求的百分比是一样的，比如说， 每个选项发生支持请求的用户数都是1 ，那么很明显，我们就将根据发生支持 请求用户数最多的那个选项去集中人力对其加以改进，这样的假定意味着我们 可能应该集中人力去改进a 选项，然后才会去改进b 或c 选项。 但是在此情形下的支持请求比率完全是假设的。通过对该软件包支持经验 的不断积累发现，a 选项用户出现问题的比率为o 5 ，b 用户为0 7 5 ，而c 用户为0 9 5 。那么现在我们的人力该投向哪个选项呢? 根据上面公式，计算由于a 选项而发生一个问题的概率( 用p ( n 问题) ) 实 际取值。根据贝叶斯定理： 删懈) = 而丽丽斋群器躲而而 这里，j p ( a ) 等于4 0 ：p ( b ) 等于3 0 ：p ( c ) 等于3 0 。从支持经验积累中 已知| p ( 问题l a ) 等于0 5 ，p ( 问题1 b ) 等于o 7 5 ，而j p ( 问题i c ) 等于0 9 5 ，于 是有： 附懈) = 而丽斋揣羔丽= 牒瑙 进行同样的计算可以得出在其他选项下的p ( b l 问题) 等于3 2 和p ( c i 问题) 等于4 0 。 现在我们就知道了应该将人力集中起来去改进c 选项。假定我们改进了c 选项，使得j d ( 问题l c ) 下降到0 0 5 ，这就意味着现在p ( c i 问题) 等于3 ，而p ( a l 问题) 变成了4 5 ，p ( b 问题) 变成了5 1 。 2 1 2 一般贝叶斯方法 一般贝叶斯方法将贝叶斯定理应用于文本分类领域，计算文本分属于某一 类别的概率，其结构如图2 1 所示。其中包含一个表示类变量的结点c 和表示类 特征项的结点w ，( f - 1 ，2 ，肝) ，任意两个结点问都有箭头相连，属性间存在着紧密 l ly，【，ilry-，rr ll o_r，l【 第二章文本分类方法的研究 的相互依赖关系。 w 图2 1 一般贝叶斯结构图 用d 表示文本向量，它共有”个特征项( w ，”，w 。) ：样本空间共有m 个类 ( c ，g ，c _ ) ，则给定文档d 属于类c f 的贝叶斯概率公式为： 粥= 警 ( 2 1 ) p ( d ) = p ( d 旧) p ( g ) ( 2 2 ) p ( d l e ) = p ( w l ，w 2 ，嵋l c ) ( 2 3 ) 根据贝叶斯概率公式( 2 1 ) 可知，要判断一个待标识邮件的类别，可以通过计 算| p ( c j 的值来完成，它根据该文档中出现的单词与向量空间模型中特征项的 匹配情况，决定浚文档属于第g 类的概率。如果能计算出真实的条件概率值 j p ( g 协，则可以通过最优化理论，比较各个类的条件概率值，把文档分到具有最 大后验概率值尸( c f 胁的类中去，得到最佳分类结果。可通过先验概率p ( c ，) 和条 件概率j p ( 卅c ) ，根据公式( 2 1 ) 计算出给定向量d 属于第c j ( i _ 1 ，2 ，m ) 类的条件 概率值p ( c j 田。 对于给定的类集合，公式( 2 1 ) 中的概率值p ( 是一定的，因此它对于分类没 有什么作用，在分类过程中可以忽略，只需计算出先验概率j p ( c j ) 和条件概率 j p ( 棚c j ) 这两个值，便可以比较各个类的条件概率值的大小，对文档进行分类。 先验概率p ( c j ) 的值可以通过训练集得知，而条件概率p ( 翻c ，) 的计算相对比 第二章文本分类方法的研究 较复杂，很难确定。因为在一般贝叶斯结构中，任意特征项之间都可以相互依 赖，极端情况下，所有特征项都可以相互依赖，如一篇千字的中等长度的文章， 它的计算复杂度可能达到2 1 0 0 0 1 ，要学习得到所有特征项的条件概率值是不可能 的。因此，必须对一般贝叶斯方法进行简化处理。 2 1 3 朴素贝叶斯方法 根据贝叶斯概率公式( 2 1 ) ，对于给定的文档向量赤 w ，) 属于第 g ( i - 1 ，2 ，m ) 类的概率为： 粥= 竖篇掣 ( 2 1 ) 其中，j d ( g ) 表示从文档空间中随机抽取一个文档其类别是g 的概率：p ( 翻c j ) 表示文档d 对于给定类c f 的条件概率：p ( 奶表示从文档空问中随机抽取一个文 档是d 的概率。 朴素贝叶斯方法，在一般贝叶斯方法的基础上加入了“独立性假设”：假定 对于给定的类，实例中包含的所有属性之间是相互独立的”刊。朴素贝叶斯结构 如图2 2 所示，其中，表示类特征项的结点w d o c 0 l + 1 ) ，门什a i n d o c n u m 【0 】+ 2 ) ： s t a n 卜p r o b a 【1 l = 柙t ) ( s t a 牡 d o c 【1 】+ 1 ) ，f r 啊m d o c n u m + 2 ) ： 其中，t r a i n d o c n u m 【o 】和t r a i n d o c n u l l l 【1 】分别表示正常邮件训练样本和垃 圾邮件训练样本的总数。 对于多项式模型( m m ) ，见公式( 4 7 ) ： s t a n 卜p r o b a 【0 卜( n t ) ( 姒卅 v a i u e 【0 】+ 1 ) ，( a n 曲u t e v a l u e 【0 】+ a n 曲u t e n u m ) ： s t a n 卜p r o b a l l 】= ( n o a l ) ( g t a 卅- v a i u e 【1 】+ 1 ) ，( a n 曲u t e v a i u e 【1 l + a n 曲u t e n u m ) ： 对于混合模型( h m ) ，见公式( 4 9 ) 第六章基于改进贝叶斯模型的中文自口件过滤系统的实现 s t a n 卜p r o b a l 0 】= ( 日t ) ( s t a n 卜，d o c 【o 】+ 1 ) ，( t r a i n d o c n u m 【0 】+ a n 曲u t e n u m ) ： s t a n 卜p r o b a 【1 】= ( 月0 a t ) ( s t a n 卜 d o c 】+ 1 ) ，f r r a i n d o c n u m 【1 】+ a n 曲u t e n u m ) ： 其中，a t t r i b u t e n u i l l 代表选取的不同特征属性的数目，a t t m u t e v a l u e 【0 和 a t t r i b u t e v a l u e 【l 】分别表示正常邮件样本和垃圾邮件样本中出现所有属性特征的 总次数( 包括重复出现的特征属性) 。 3 模块输出 训练模块利用属性链表保存所有的特征属性，这与s t w o r d 数据结构的保存 方式类似。属性链表可直接用于测试子模块以测试分类性能。同时，为了方便 实时分类模块随时调用特征属性及其概率信息，训练器子模块将以戗t 文件的形 式输出属性值。 属性链表和6 个戗t 文件共同组成特征库， 分别是： b a v e sb i ma t t l t x t ：二项式模型( b i m ) 特征属性文件： b a y e sb i mp r o b t x t ：二项式模型( b i m ) 先验概率文件： b a v e sm ma n l t x t ：多项式模型( m m ) 特征属性文件； b a y e sm mp m b t x t ：多项式模型( m m ) 先验概率文件： b a v e sh v b r i da n l t ) ( t ：混合模型( h m ) 特征属性文件； b a y e sh y b r i dp r o b t ) 【t ：混合模型( h m ) 先验概率文件。 其中，特征属性文件保存了所有通过特征提取从单词库中选出的作为属性 的单词；先验概率文件按照特征属性文件中属性的出现顺序，存放属性分别属 于正常邮件类和垃圾邮件类的先验概率。 为了实现系统作为不同分类模型测试平台的功能，如需采用某种模型，只 要从特征库读取与该模型对应的特征属性文件和先验概率文件即可。例如，实 时分类模块欲采用多项式模型( m m ) 进行邮件的分类，那么实时分类模块只需 从特征库读入b a y e s _ m m a n l t ，( t 和b a y e s _ m m _ p m b t ) ( t 这两个文件的信息即可。 6 1 2 测试子模块 测试子模块的功能是利用训练器子模块输出的属性链表对测试样本进行测 试，从而判断大致的分类查全率和准确率；同时测试风险值的设定对分类效果 的影响。 第六章基于改进贝叶斯模型的中文邮件过滤系统的实现 测试予模块首先需要从分词后的邮件样本集中读入测试样本，然后根据每 一个样本中所出现的特征属性进行计算，得出样本的系统分类。通过比较系统 分类与实际的人工分类结果，统计分类查全率和准确率。 系统的测试方法与所选择的分类算法有关。通过计算测试文档属于不同类 别的后验概率进行测试。“0 】表示文档属于正常邮件的后验概率，p 【1 】表示属于 垃圾邮件的后验概率。 二项式模型( b i m ) ，p i ( i = o ，1 ) 计算过程如下： p 【i 】= 0 ： s t n j ds t a 咐。c u r l a n r ： ，根据公式进行计算，由于是要求最大值，因此把连乘式取对数以简化计算， f o r ( c u r l a h r = a 钍r r t ：c u r r - a n r = c u r l a n 卜 n e ) ( t ) i i m e s = 1 ) n o a t t2 c u n 二- a n 卜p r o b a 川，( 1 - c u n - a n 卜p r o b a d 】) ： 邮】+ = 均( q ： ) 多项式模型( m m ) 和混合模型( h m ) ，“i ( i = 0 ，1 ) 计算过程如下： p 【i 】= n ； n = i o g ( p ( c - ) ) ，参见公式( 46 ) s l r u ds t a n r 。伽n 二a n r ： ，根据公式进行计算，由于是要取最大值，因此把连乘式取对数以简化计算。， f o r ( c u n ，n r = a n r r o o t ：c u r l a n r2c u r r _ a n p n e ) ( t ) ( _ o a l t = c u r l a n 卜 t i m e s l o g ( c u r r _ a n p p r o b a d 】) ： 参见公式( 46 ) d + = i ： ) 得到某个测试样本的“0 】和“1 后，计算把该样本归类为正常邮件的风险值 r i s k o 和归类于垃圾邮件的风险值r i s k 1 。其计算方法如下： 笙查皇苎! ：丝垄墨堕堑堡型盟! 苎塑堡垫塑墨竺塑壅塑 n s k 【o 】= p 【1 】+ i o g ( 1 ) ： n s k 【1 】- p 【o 】+ i o g ( r i s k f o r s p a m ) ： 在这里，鼬s i ( f o r s p a m 是事先定义的将正常邮件误判为垃圾邮件的风险值 ( 即a ( 口a c ，) 与 ( o o ) 的比值，见4 3 2 ) 。 如果r i s k 【o 】r i s k 【1 ，则系统把该测试样本判为正常邮件：否则系统把该测 试样本判为垃圾邮件。 系统在判定每一个测试样本的分类之后，程序统计对测试样本分类的查全 率( r e c a l l ) 和准确率( p r e c i s i o n ) ，以此作为系统测试的评价标准。 广根据公式以及与人工分类的比较统计值计算查全率和准确率。， 悖= ( n o a t ) n o m a i s p a m 川【1 l ，( n o m a i s p a m 【1 】【0 l + n o r m a i s p a m 【1 】【m p 陀c i s i o n = 柙o a i ) n o m a i s p a m f l 】【1 l ，( n o r m a i s p a m 【0 】【1 】+ n o r m a i s p a m 【1 】【1 1 ) = 其中， n o n n a l s p a r n 0 】 o 】表示人工分类为正常邮件，并且系统将其划分为正常邮件 的样本数目。 n o m a i s p a m 【0 】【1 表示人工分类为正常邮件，并且系统将其划分为垃圾邮件 的样本数目： n o m a l s p 帅【l 】【0 】表示人工分类为垃圾邮件，并且系统将其划分为正常邮件 的样本数目。 n o m a l s p 锄 1 【1 表示人工分类为垃圾邮件，并且系统将其划分为垃圾邮件 的样本数目。 6 1 3 邮件样本训练模块的应用 邮件样本训练模块主要包含文件：仃面n i n g c ，g e n e r e a l l i b h ，g e n e r a l _ i i b c ， b a y e s _ l i b h ，b a y e s - l i b c ，s g n l t - r n a ，s g n l t - i i b h ，s g m u i b c ，m a l ( e f i l e g e n e m l l i b h ，g e n e m l l i b c 是通用算法库文件和实现文件，包含申明的全局 变量和可用于所有算法的公共变量和函数。b a y e s - l i b h ，b a y e s l i b c 实现了与贝 叶斯算法相关的所有的函数。s g m l l i b h ，s g m l i i b c 包含了训练阶段的分词函数。 s g m tm a i l c 是用于完成对邮件分词的主程序文件；t r a i n i n g c 是用于训练及测试 的主程序文件。m a k e f i l e 用于编译运行训练模块的各个程序文件。 进行邮件集的训练时，首选要将待训练的已分类邮件样本放入邮件样本训 第六章基于改进贝叶斯模型的中文邮件过滤系统的实现 练模块下的n o m a ls a m p l e 和s p 锄s a r l l p l e ( 分别用来存放正常邮件和垃圾邮件 样本) 目录下，使用m a l ( e 命令编译训练模块的各个程序文件。运行s g m i m a i l ， 将样本目录下的邮件分词，并将分词的结果以同名文件的形式放到n 0 肿a l 和 s p a r n 文件夹下。执行t r a i n i n g ，实现对已分词邮件样本的训练和测试工作。t r a i n i n g 的运行方式如下： r a i n i n g 一【m o d e 】【r i sk 】 其中， m o d e ：用于选择不同的算法，b 表明使用二项式模型( b i m ) ，m 表示使 用多项式模型( m m ) ，h 表示使用混合模型( h m ) 。 r i s k 】：风险值，该值大于0 。 为了运行方便，编写脚本文件t r a i n s h ， # ! ，b l n ，s h 托o m p i i ea 6 i e so f t 阳i n i n g m a k e 撑s e g m e n tw o r df o ra m a m p i e s ，s g m tm a 搬r a i n i n ga n dt e s t i n gw i t hb i m n s kv a 吣ei s1 a r a i n i n 口b1 # i n s t a a i h ea n 曲u t e l ei o a r ，d j c t i o n a r y m a k ei n s t a # c i e a na t h eu n u s e d 自i e s m a k ed e a n m a l ( ei n s t a l l 命令可以将所有生成的特征属性文件c o p y 到v a r d i c t i o n a r y 目录 下，该文件将作为特征库，供实时分类模块调用。 第六章基于改进贝叶斯模型的中文邮件过滤系统的实现 6 1 4 邮件样本训练模块工作流程图 图6 2 邮件样本训练模块：【作流程幽 第六章基于改进贝叶斯模型的中文邮件过滤系统的实现 第二节邮件实时分类处理模块 邮件实时分类处理模块实现对于网络中到达邮件的实时分类，并对分类后 的邮件进行相应处理。 邮件实时分类处理模块首先对邮件进行解码、分词，通过黑白名单模块进 行初步的判断，不能判别的邮件进入分类子模块，通过所选择的实时分类算法 对邮件属性进行判断，并送交邮件处理子模块作出相应处理。下面主要介绍邮 件实时分类处理模块中的分类子模块和邮件处理子模块。 6 2 1 分类子模块 分类子模块以训练器的训练结果为基础，对待分类的邮件进行实时分类。 在分类算法的实现上该模块与训练阶段的测试模块基本类似，不同的是其输入 由文本变为实时的分词后的邮件内容。通过用户所选择的分类算法对邮件类别 进行判断，标识其是否为垃圾邮件并交给邮件处理模块进行处理。 分类子模块中所使用的基本数据结构与训练模块中基本相同，其过程如下： 根据训练器给出的先验概率文件( 参见6 1 1 ) 和用户指定的算法，将对应 算法的先验概率文件装入数组结构，称之为属性表数组( w o r d _ a n r 口 2 】) ，其中 w o r d _ a t t r 【】【o 】存放属性属于正常邮件的概率，w o r d - a 咐口 1 存放属性属于垃圾邮 件的概率。 将待分类邮件在中文分词模块中根据与所选用算法相关的特征属性文件进 行分词，分词后得到每个词汇在特征属性文件中的顺序编号，并将其存入一个