垃圾邮件过滤技术探讨

1、垃圾邮件过滤技术探讨垃圾邮件过滤技术探讨软件室LCC组 潘文锋2004.3.20内容提要内容提要 问题的提出 国内外研究现状 研究路线 已完成的实验及得到的结果 下一步计划 可能的创新点问题的提出：垃圾邮件泛滥问题的提出：垃圾邮件泛滥 随着Internet的普及，电子邮件日益得到了广泛的应用，成为日常生活中人与人之间通信、交流的重要手段。但是随之而来的垃圾邮件也越来越猖獗。据统计每年美国因垃圾邮件造成的损失高达10亿美元，全球的损失更高达20亿美元（资料来源：中国反垃圾邮件联盟http:/www.anti-） 中国互联网络信息中心（CNNIC)2003年7月公布的中国互联网络发展状况统计报告显

2、示，中国网民平均每周收到16.1封电子邮件，其中垃圾邮件占据了8.9封，垃圾邮件数量超过了正常邮件数量，并有进一步增长的趋势问题的提出：垃圾邮件的危害问题的提出：垃圾邮件的危害 浪费电子邮件用户的时间 占用网络、系统资源，降低了网络的运行效率。如，大量的垃圾邮件占用网络带宽，占用邮件服务器的磁盘空间 对网络安全形成威胁。传播有害信息，危害社会；成为“黑客”的工具，利用数以亿万计的垃圾邮件造成被攻击目标瘫痪；传播计算机病毒问题的提出：解决的手段问题的提出：解决的手段 反垃圾邮件立法 垃圾邮件过滤技术 无论对于电子邮件服务提供商还是用户个人，都迫切需要行之有效的反垃圾邮件技术内容提要内容提要 问题

3、的提出 国内外研究现状 研究路线 已完成的实验及得到的结果 下一步计划常用的垃圾邮件过滤技术（常用的垃圾邮件过滤技术（1） 白名单和黑名单如果邮件的发送地址在白名单中，将不进行垃圾邮件检查；反之，如果发送地址在黑名单中则直接当作垃圾邮件处理 对邮件的标题、内容进行关键词匹配，识别垃圾邮件 设定其他的规则 将垃圾邮件过滤看作二类的文本分类或文本过滤问题，对邮件文本内容进行计算文本分类、过滤技术的应用常用的垃圾邮件过滤技术（常用的垃圾邮件过滤技术（2）按照邮件系统的角色结构，将邮件过滤分为三类： MTA（邮件传输代理）过滤MTA过滤是指MTA在会话过程中对会话的数据进行检查，对于符合过滤条件的邮件

4、进行过滤处理； MDA（邮件递交代理）过滤MDA过滤是指MDA在从MTA中接收到信件，在本地或远程进行递交时进行检查，对于符合过滤条件的邮件进行过滤处理。很多的MDA都支持在这个过程进行过滤，如Procmail、Maildrop和Cyrus-IMAP等 MUA（邮件用户代理）过滤MTA和MDA过滤都是邮件服务器端的过滤，而MUA过滤是邮件用户的客户端的过滤。常用的垃圾邮件过滤技术（常用的垃圾邮件过滤技术（3） 具有反垃圾邮件功能的产品，比较常用的有邮件客户端Outlook 2003、Outlook Express 6、Foxmail 5.0、Eudora 6等 这些产品大多采用白名单、黑名单、

5、关键词匹配和规则匹配等方法识别垃圾邮件。Foxmail 5.0中使用了贝叶斯过滤，是一个亮点，需用户提供正反各1000篇以上的邮件用来训练常用的垃圾邮件过滤技术（常用的垃圾邮件过滤技术（4） 和一般的二类文本分类、过滤问题相比较，垃圾邮件有自身的特点：- 电子邮件有自己的内容结构，如发件人、收件 人、邮件头、标题等；- 实时性要求较高；- 效果要求上，人们最不希望将正常邮件误判为垃圾 邮件，因此首先要保证分类的精确律（precision）， 在此基础上尽量提高召回率（recall）；- 对客户端邮件过滤而言，要给用户提供操作简便、速 度快的反馈学习机制 本文结合邮件过滤问题的上述特点，主要讨论

6、内容过滤内容过滤技术（内容过滤技术（1） 贝叶斯过滤（Nave Bayes)()()|()|(ijjiijdPcPcdPdcP独立性假设）()|()|(1rkjikjicwPcdP贝叶斯过滤是目前最为广泛采用的邮件过滤方法，如希腊的Ion Androutsopoulos(2000)，Stanford的Mehran Sahami等人内容过滤技术（内容过滤技术（2） Memory Based Approach也叫Instance Based，无训练阶段，基于实例的，如k-近邻（k-NN）方法。这种方法分类速度比较慢 Boost、AdaBoost方法 决策树Decision Tree常用语料（常用语

7、料（1） PU1（2000）- 英文- 来源于提供者一段时间内的真实邮件- 共1099篇，包含481篇垃圾、618篇非垃圾- 分为10份，每份约110篇，每次使用其中的9份为训 练集，另一份为测试集，共10次交叉- 保留标题和正文，将词汇编码为整数id- 提供了4种形式的语料：bare(Lemmatiser disabled, stop-list disabled)、lemm(Lemmatiser enabled, stop-list disabled)、lemm_stop(Lemmatiser enabled, stop-list enabled)和stop(Lemmatiser disab

8、led, stop- list enabled)常用语料（常用语料（2） Ling-Spam- 英文- 共2893篇文本，481篇垃圾邮件，2412篇非 垃圾邮件- 也是分为10份，包含4种形式bare、lemm、 lemm-stop和stop- 与PU1不同的是，邮件内容是原始词汇，没 有编码为整数id PU123A- PU1的2003版本，只有bare形式，与PU1略有不同中文通用邮件语料建构设想中文通用邮件语料建构设想 构建中文垃圾邮件的真实语料 为垃圾邮件分类器提供训练集和测试集 半结构化的标识方法，如, 作为开放资源的一部分，供评测、交流 ?内容提要内容提要 问题的提出 国内外研究现

9、状 研究路线 已完成的实验及得到的结果 下一步计划研究路线（研究路线（1） 实现Nave Bayes垃圾邮件分类器。使用PU1语料作训练集和测试集，和以前的结果作比较 实验目的：- 验证Nave Bayes方法的效果- 在常用语料上详细比较特征选择方法、特征 数量、阈值、语料的预处理层次（如去停用 词、词干还原）等对效果的影响，为实际应 用作积累研究路线（研究路线（2） Winnow分类器是一种简单的线性分类器，在TREC 2003 Novelty中我们实验了它的效果。应用于大量特征和稀疏向量时性能较好，而且由于简单，如果用于垃圾邮件过滤时效果比较好，则实用性很大。因此使用Winnow分类器实

10、验在PU1语料上的效果。 积累了在英文语料上Nave Bayes和Winnow方法的实验结果以后，将他们应用在中文邮件语料上研究路线（研究路线（3） 结合电子邮件自身的结构特点和经验中的垃圾邮件常见特征，采用多特征空间的邮件模型，即把这些非“词”一级的特征融合到邮件的特征空间中，在自己建立的中文语料上实验这种方法的效果 根据实验得出的算法性能特征，考虑其应用场景 垃圾邮件过滤工具工程实现的设想内容提要内容提要 问题的提出 国内外研究现状 研究路线 已完成的实验及得到的结果 下一步计划Nave Bayes 基本思想是应用贝叶斯公式，利用先验概率和类条件概率来估计后验概率)()()|()|(ijj

11、iijdPcPcdPdcP待估计的后验概率类条件概率先验概率Nave Bayes: Multi-variate Bernoulli Model(MBM)|1)|(1)(1 ()|()|(VtjtitjtitjicwPBcwPBcdP类总的文档数类中的文档频次在jjtjtccwcwP21)|(|1)|()()(CjjijicdPcPdPP(cj)和P(wt|cj)是训练过程中需计算的统计量不出现；中出现在表示；，；特征，文本/0/1|,.,2 , 1|,.,2 , 1itittidwBVtwDidNave Bayes: Multinomial Model(MM)|1!)|(|!|)(|)|(Vt

12、itNjtiijiNcwPddPcdPit|1)|()()(CjjijicdPcPdP |1|1|1)|(|)|(1)|(VsDiijisDiijitjtdcPNVdcPNcwPP(cj)和P(wt|cj)是训练过程中需计算的统计量中出现的词频在表示类；不属于属于表示训练文本ititjiijdwNcddcP/0/1)|(Nave Bayes: 特征选择特征选择 平均互信息（Average mutual Information） 1 , 0,1 , 01 , 01 , 01 , 0)()(),(log),()|(log()|()()(log()()|()();(cwcwccCPwWPcCwWPc

13、CwWPwWcCPwWcCPwWPcCPcCPWCHCHWCINave Bayes: PU1语料上语料上Ion Androutsopoulos的结果的结果（SIGIR 2000）我使用我使用Nave Bayes（MBM）方法在方法在PU1语料上交叉训练测试取平均语料上交叉训练测试取平均recall和和precision的结果的结果使用的语料阈值特征数量Recall（平均）Precision（平均）PU1 bare0.505000.8770.9780.902000.9420.9670.905000.8480.9770.992000.8920.976PU1 lemm0.505000.8830.96

14、00.902000.9440.9550.905000.8650.9750.995000.8360.981PU1 lemm_stop0.505000.9250.9680.902000.9670.9530.905000.8980.9760.992000.9380.971PU1 stop0.505000.9130.9760.902000.9630.9640.992000.9290.9770.995000.8420.988PU1语料上阈值和特征数对语料上阈值和特征数对Nave Bayes（MBM)方法的影响比较方法的影响比较0 . 50 . 60 . 70 . 80 . 911 0 02 0 05 0

15、 01 0 0 01 5 0 0阈 值 0 . 5阈 值 0 . 9阈 值 0 . 9 9Recall横轴为特征数0 . 50 . 60 . 70 . 80 . 911 0 02 0 05 0 01 0 0 01 5 0 0阈 值 0 . 5阈 值 0 . 9阈 值 0 . 9 9Precision横轴为特征数以PU1 bare语料为例，其它形式的PU1语料也有类似结果PU1语料上阈值和特征数对语料上阈值和特征数对Nave Bayes（MBM）方法的影响比较方法的影响比较 阈值从0.50、0.90到0.99，recall有所下降 阈值从0.50、0.90到0.99，precision在特征数较

16、少时上升比较明显，特征数较多时，上升不明显 特征数量逐渐增多的过程中，recall呈下降趋势 特征数量逐渐增多的过程中，precision呈上升趋势，但当特征达到一定数量时，precision的上升趋势就不明显了PU1语料的预处理程度对语料的预处理程度对Nave Bayes（MBM）方法的影响比较：方法的影响比较：recall1100200500100015001100200500100015001100200500 1000 1500barelemmlemm_stopstop阈值0.50阈值0.90阈值0.99PU1语料的预处理程度对语料

17、的预处理程度对Nave Bayes（MBM）方法的影响比较：方法的影响比较：precision0.91100200500100015000.91100200500100015000.91100200500 1000 1500barelemmlemm_stopstop阈值0.50阈值0.90阈值0.99PU1语料的预处理程度对语料的预处理程度对Nave Bayes（MBM）方法的影响比较方法的影响比较 去停用词、词干还原对recall的影响很明显，lemm_stop、lemm和stop比bare要好，lemm_stop最好 去停用词、词干还原对precision的影响规律并不明显Winnow分类

18、器（分类器（1） 一种线性分类器 我们在TREC 2003 Novelty中实验了它的性能 这种分类器的训练策略是基于错误率的反馈调整 训练和分类过程都比较简单，易于计算 已有实验证明winnow方法比Rocchio和Nave Bayes要好（P.P.T.M. van Mun “Text Classification in Information Retrieval using Winnow”）Winnow分类器（分类器（2）Winnow分类器应用于垃圾邮件过滤分类器应用于垃圾邮件过滤（1） 我使用的是balanced winnow(Littlestone,1988)，与上面不同的是，用wi+

19、 - wi-代替wi，训练时，如果要提高权重，则wi+ = wi+ ， wi- = wi- ；若要降低权重，则wi+ = wi+ ， wi- = wi- 。其中1， 01 虽然Winnow很适合于大规模特征的稀疏向量，但若不进行特征降维，会带来比较多的噪声，也给计算速度和存储量带来压力，因此将特征选择也应用于winnow方法中Winnow分类器应用于垃圾邮件过滤分类器应用于垃圾邮件过滤（2） 我实验了几种特征选择方法：互信息（MI)、文档频次（DF）和优势率（Odds） Winnow分类器的阈值定为训练集中平均每篇文本包含的特征数目 1.5， 0.5 使用PU1语料的10份交叉训练测试，取平均结果 为了减少错误率，通常要在训练集上多次训练。结果发现，当训练次数达到4-5次时，对训练集分类的错误率就降到很小，如果再训练多次，对测试集的分类效果反而有所下降，即存在“训练过度”问题。因此将训练次数定在4-5次Winnow分类器应用于垃圾邮件过滤分类器应用于垃圾邮件过滤（3）：与）：与boost的结果比较（的结果比较（1）这是我找到的在PU1 bare语料上取得的最好的结果，使用boost方法Winnow分类器应用于垃圾邮件过滤分类器应用于垃圾邮件过