垃圾邮件过滤技术探讨

垃圾邮件过滤技术探讨第1页，共40页。垃圾邮件过滤技术探讨第2页，共40页。问题的提出：垃圾邮件泛滥随着Internet的普及，电子邮件日益得到了广泛的应用，成为日常生活中人与人之间通信、交流的重要手段。但是随之而来的垃圾邮件也越来越猖獗。据统计每年美国因垃圾邮件造成的损失高达10亿美元，全球的损失更高达20亿美元（资料来源：中国反垃圾邮件联盟）中国互联网络信息中心（CNNIC)2003年7月公布的《中国互联网络发展状况统计报告》显示，中国网民平均每周收到16.1封电子邮件，其中垃圾邮件占据了8.9封，垃圾邮件数量超过了正常邮件数量，并有进一步增长的趋势第3页，共40页。问题的提出：垃圾邮件的危害浪费电子邮件用户的时间占用网络、系统资源，降低了网络的运行效率。如，大量的垃圾邮件占用网络带宽，占用邮件服务器的磁盘空间对网络安全形成威胁。传播有害信息，危害社会；成为“黑客”的工具，利用数以亿万计的垃圾邮件造成被攻击目标瘫痪；传播计算机病毒第4页，共40页。问题的提出：解决的手段反垃圾邮件立法垃圾邮件过滤技术无论对于电子邮件服务提供商还是用户个人，都迫切需要行之有效的反垃圾邮件技术第5页，共40页。内容提要问题的提出国内外研究现状研究路线已完成的实验及得到的结果下一步计划第6页，共40页。常用的垃圾邮件过滤技术（1）白名单和黑名单

如果邮件的发送地址在白名单中，将不进行垃圾邮件检查；反之，如果发送地址在黑名单中则直接当作垃圾邮件处理对邮件的标题、内容进行关键词匹配，识别垃圾邮件设定其他的规则将垃圾邮件过滤看作二类的文本分类或文本过滤问题，对邮件文本内容进行计算—文本分类、过滤技术的应用第7页，共40页。常用的垃圾邮件过滤技术（2）按照邮件系统的角色结构，将邮件过滤分为三类：MTA（邮件传输代理）过滤

MTA过滤是指MTA在会话过程中对会话的数据进行检查，对于符合过滤条件的邮件进行过滤处理；MDA（邮件递交代理）过滤

MDA过滤是指MDA在从MTA中接收到信件，在本地或远程进行递交时进行检查，对于符合过滤条件的邮件进行过滤处理。很多的MDA都支持在这个过程进行过滤，如Procmail、Maildrop和Cyrus-IMAP等MUA（邮件用户代理）过滤

MTA和MDA过滤都是邮件服务器端的过滤，而MUA过滤是邮件用户的客户端的过滤。第8页，共40页。常用的垃圾邮件过滤技术（3）具有反垃圾邮件功能的产品，比较常用的有邮件客户端Outlook2003、OutlookExpress6、Foxmail5.0、Eudora6等这些产品大多采用白名单、黑名单、关键词匹配和规则匹配等方法识别垃圾邮件。Foxmail5.0中使用了贝叶斯过滤，是一个亮点，需用户提供正反各1000篇以上的邮件用来训练第9页，共40页。常用的垃圾邮件过滤技术（4）和一般的二类文本分类、过滤问题相比较，垃圾邮件有自身的特点：

--电子邮件有自己的内容结构，如发件人、收件

人、邮件头、标题等；

--实时性要求较高；

--效果要求上，人们最不希望将正常邮件误判为垃圾

邮件，因此首先要保证分类的精确律（precision），

在此基础上尽量提高召回率（recall）；

--对客户端邮件过滤而言，要给用户提供操作简便、速

度快的反馈学习机制本文结合邮件过滤问题的上述特点，主要讨论内容过滤第10页，共40页。内容过滤技术（1）贝叶斯过滤（NaïveBayes)

贝叶斯过滤是目前最为广泛采用的邮件过滤方法，如希腊的IonAndroutsopoulos(2000)，Stanford的MehranSahami等人第11页，共40页。内容过滤技术（2）MemoryBasedApproach

也叫InstanceBased，无训练阶段，基于实例的，如k-近邻（k-NN）方法。这种方法分类速度比较慢Boost、AdaBoost方法决策树DecisionTree第12页，共40页。常用语料（1）PU1（2000）

--英文

--来源于提供者一段时间内的真实邮件

--共1099篇，包含481篇垃圾、618篇非垃圾

--分为10份，每份约110篇，每次使用其中的9份为训

练集，另一份为测试集，共10次交叉

--保留标题和正文，将词汇编码为整数id

--提供了4种形式的语料：bare(Lemmatiserdisabled,

stop-listdisabled)、lemm(Lemmatiserenabled,

stop-listdisabled)、lemm_stop(Lemmatiserenabled,

stop-listenabled)和stop(Lemmatiserdisabled,stop-

listenabled)第13页，共40页。常用语料（2）Ling-Spam

--英文

--共2893篇文本，481篇垃圾邮件，2412篇非

垃圾邮件

--也是分为10份，包含4种形式bare、lemm、

lemm-stop和stop

--与PU1不同的是，邮件内容是原始词汇，没

有编码为整数idPU123A

--PU1的2003版本，只有bare形式，与PU1略有不同第14页，共40页。中文通用邮件语料建构设想构建中文垃圾邮件的真实语料为垃圾邮件分类器提供训练集和测试集半结构化的标识方法，如<from></from>,<to></to>,<subject></subject>…作为开放资源的一部分，供评测、交流?第15页，共40页。内容提要问题的提出国内外研究现状研究路线已完成的实验及得到的结果下一步计划第16页，共40页。研究路线（1）实现NaïveBayes垃圾邮件分类器。使用PU1语料作训练集和测试集，和以前的结果作比较实验目的：

--验证NaïveBayes方法的效果

--在常用语料上详细比较特征选择方法、特征

数量、阈值、语料的预处理层次（如去停用

词、词干还原）等对效果的影响，为实际应

用作积累第17页，共40页。研究路线（2）Winnow分类器是一种简单的线性分类器，在TREC2003Novelty中我们实验了它的效果。应用于大量特征和稀疏向量时性能较好，而且由于简单，如果用于垃圾邮件过滤时效果比较好，则实用性很大。因此使用Winnow分类器实验在PU1语料上的效果。积累了在英文语料上NaïveBayes和Winnow方法的实验结果以后，将他们应用在中文邮件语料上第18页，共40页。研究路线（3）结合电子邮件自身的结构特点和经验中的垃圾邮件常见特征，采用多特征空间的邮件模型，即把这些非“词”一级的特征融合到邮件的特征空间中，在自己建立的中文语料上实验这种方法的效果根据实验得出的算法性能特征，考虑其应用场景垃圾邮件过滤工具工程实现的设想第19页，共40页。内容提要问题的提出国内外研究现状研究路线已完成的实验及得到的结果下一步计划第20页，共40页。NaïveBayes基本思想是应用贝叶斯公式，利用先验概率和类条件概率来估计后验概率待估计的后验概率类条件概率先验概率第21页，共40页。NaïveBayes:Multi-variateBernoulliModel(MBM)P(cj)和P(wt|cj)是训练过程中需计算的统计量第22页，共40页。NaïveBayes:MultinomialModel(MM)P(cj)和P(wt|cj)是训练过程中需计算的统计量第23页，共40页。NaïveBayes:特征选择平均互信息（AveragemutualInformation）第24页，共40页。NaïveBayes:PU1语料上IonAndroutsopoulos的结果

（SIGIR2000）第25页，共40页。我使用NaïveBayes（MBM）方法在PU1语料上交叉训练测试取平均recall和precision的结果使用的语料阈值特征数量Recall（平均）Precision（平均）PU1bare0.505000.8770.9780.902000.9420.9670.905000.8480.9770.992000.8920.976PU1lemm0.505000.8830.9600.902000.9440.9550.905000.8650.9750.995000.8360.981PU1lemm_stop0.505000.9250.9680.902000.9670.9530.905000.8980.9760.992000.9380.971PU1stop0.505000.9130.9760.902000.9630.9640.992000.9290.9770.995000.8420.988第26页，共40页。PU1语料上阈值和特征数对NaïveBayes（MBM)方法的影响比较Recall横轴为特征数Precision横轴为特征数以PU1bare语料为例，其它形式的PU1语料也有类似结果第27页，共40页。PU1语料上阈值和特征数对NaïveBayes（MBM）方法的影响比较recall有所下降precision在特征数较少时上升比较明显，特征数较多时，上升不明显特征数量逐渐增多的过程中，recall呈下降趋势特征数量逐渐增多的过程中，precision呈上升趋势，但当特征达到一定数量时，precision的上升趋势就不明显了第28页，共40页。PU1语料的预处理程度对NaïveBayes（MBM）方法的影响比较：recall阈值0.50阈值0.90阈值0.99第29页，共40页。PU1语料的预处理程度对NaïveBayes（MBM）方法的影响比较：precision阈值0.50阈值0.90阈值0.99第30页，共40页。PU1语料的预处理程度对NaïveBayes（MBM）方法的影响比较去停用词、词干还原对recall的影响很明显，lemm_stop、lemm和stop比bare要好，lemm_stop最好去停用词、词干还原对precision的影响规律并不明显第31页，共40页。Winnow分类器（1）一种线性分类器我们在TREC2003Novelty中实验了它的性能这种分类器的训练策略是基于错误率的反馈调整训练和分类过程都比较简单，易于计算已有实验证明winnow方法比Rocchio和NaïveBayes要好（第32页，共40页。Winnow分类器（2）第33页，共40页。Winnow分类器应用于垃圾邮件过滤（1）我使用的是balancedwinnow(Littlestone,1988)，与上面不同的是，用wi+-wi-代替wi，训练时，如果要提高权重，则wi+=αwi+，wi-=βwi-

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