基于机器学习的多级垃圾邮件过滤系统研究与设计[摘要] 传统的垃圾邮件过滤方法只是单方面的从邮件系统管理员的角度
将邮件理解为“垃圾邮件”和“合法邮件”两类进行二元处理，很少考虑不同用户对垃圾邮件概念的不同理解和定义，没有更多的从用户角度来过滤和处理垃圾邮件。

本文设计了一种面向用户的多层过滤系统，该系统融合了多种机器学习方法，能够在服务器端针对不同的用户采取不同的过滤方案，使用户收到垃圾邮件的概率更小，提高邮件系统的服务质量。

[关键词] 垃圾邮件机器学习系统设计
1.0B0B引言
随着Intemet的快速发展，电子邮件作为一快捷、经济的通信方式得到了普及，已成为人们日常交流沟
通的手段和企业运转的重要组成部分。

然而当前网络中垃圾邮件的泛滥，引起了广大研究者的极大关注，并提出了垃圾邮件问题的多种解决方法。

其中基于内容的垃圾邮件过滤主要借鉴机器学习的方法具有一定的“自我学习”能力，是解决垃圾邮件的重要方法[1]。

然而当前的垃圾邮件过滤产品琳琅满目，反垃圾邮件系统很少考虑不同用户对垃圾邮件的不同认定，垃圾邮件数量并没有减少。

针对垃圾邮件泛滥的现状和当前垃圾邮件产品存在的上述不足，本文设计了一种面向用户的多层过滤系统，该系统融合了多种机器学习方法，能够在服务器端针对不同的用户采取不同的过滤方案。

并且本系统不直接依赖具体的邮件系统，能够和不同邮件系统实现简单集成，具有较强的可移植性。

2.系统研究与设计
2.1系统工作流程
系统工作流程图如图1所示，邮件过滤包括初步过滤、个性化过滤两个主要模块。

在初步过滤阶段系统将到达的邮件分为确定合法的邮件、不确定的邮件、确定的垃圾邮件三大类。

个性化模块再对不确定的邮件进行分级，将分级后的邮件送入用户邮箱中。

同时个性化过滤模块也从用户邮箱中提取用户信息，以指导分级。

2.2 初步过滤模块工作流程
在初步过滤模块，邮件到达系统后，先根据邮件发送者的地址进行黑名单/白名单过滤。

黑名单/白名单可以从Spamhaus、RBL服务器获取。

邮件预处理模块先对邮件进行分词，英文邮件分词较为容易，中文邮件则由于中文的特殊性使得分词较为困难。

本系统采用文献[2]介绍中文实时分词算法，该算法采利用TRIE
树进行中文分词，效果比较理想。

完成分词后，邮件预处理模块再根据邮件特征库中保存的合法邮件、垃圾邮件特征选择信息量较大的n个特征（n可以根据不同规模的邮件系统来设定）对邮件做向量化表示。

关于特征提取，Yang在文献[3]中介绍了5种不同的特征提取方法，本系统选择性能较好的信息增益（Information Gain）作为特征选择算法。

邮件的向量化表示形式为，其中表示相应的特征项，表示对应特征项的权值（比如词频）。

向量化表示邮件的好处在于它能够被贝叶斯分类器、SVM分类器直接使用，有利于提高系统执行效率。

在初步过滤的最后阶段，我们采用的是贝叶斯过滤方法。

常用的贝叶斯方法有朴素贝叶斯算法[4]、Paul Graham提出的基于贝叶斯规则的垃圾邮件过滤算法(PG贝叶斯算法I)[5][6]以及Gary Robinson针对PG贝叶斯算法I的改进算法(PG 贝叶斯算法II)[7]。

它们各有特点，可以组合使用。

由于这只是初步过滤，所以我们不一定要一次性查找出所有垃圾邮件和合法邮件。

贝叶斯过滤器能够给出一封邮件是垃圾邮件的概率（即垃圾邮件近似度app），我们根据这个概率可以将app比较大（大于d）的判为垃圾邮件，比较小的（小于a）的判为合法邮件。

d 和a的初始值设为100和0,当图1中垃圾区邮件淘汰（长期不处理）率比较高时，表示垃圾邮件漏报率比较高，可以逐步增大d。

相反，当合法区邮件淘汰(不处理)率很低时表示合法邮件判断率很高，可以逐步增大a。

通过a、d值的调整，系统将逐步找到最佳贝叶斯分类阈值。

2.3 个性化过滤模块工作流程
经过初步过滤阶段处理后，我们将每一封邮件进行了向量化。

并且通过贝叶斯过滤得到了每一封邮件的近似垃圾邮件的概率app。

然而由于每个用户兴趣爱好不同，这个app的值还需要调整。

个性化过滤模块过滤的目标，就是将app进行修改，使得邮件的app值正确反映用户的兴趣度。

个性化过滤的基本思想是：先根据用户信息库的用户信息，对所有用户做一次KNN[8]分类，将所有用户分成K类。

由于用户数量相对邮件而言要少的多，所以KNN算法是容易实现的。

同时，以每一个用户的邮箱中所存储的处理过的邮件为训练样本，训练出每个用户的SVM分类器，并将其保存至相应用户的信息库中。

当用户A有新的不确定邮件到达时，系统从用户信息库中取出所有与A 同类(临近)的用户的SVM[9]分类器，依据AdaBoosting[10]算法的思想，我们可以将将这些SVM视作弱分类器。

又由于A的所有同类用户与A都有一个距离，我们把这个距离量化后容易得到A的所有同类用户的投票的一个权值表。

于是，有了弱分类器和每个分类器的权值，我们就可以用AdaBoosting算法计算新的不确定邮件的app值了。

这个app值可以量化表示为：
App=投正例票的票数－总票数/2
同时，类似于AdaBoosting算法中的迭代赋值调整，系统还将根据用户对该邮件的具体处理方式来修改临近表，使分类精度逐步提高。

SVM分类器构造如图2所示。

其中，正例为用户回复过的邮件和邮箱中用
户阅读过的且没有删除的邮件。

反例则是用户举报的垃圾邮件、垃圾区内的邮件。

通过构造最优分类面，可以得到用户A的SVM分类器。

用户临近信息表计算过程则如图3所示，根据用户信息库里存储的用户信息，用信息增益提取用户特征向量，再做KNN分类。

根据每个用户距离的不同在用户信息库中添加每个用户的同类临近信息表，用以生成AdaBoosting算法所需要的权值表。

3.结束语
本文分析并设计了一种基于用户个人兴趣的中英文电子邮件自动过滤系统，该系统融合了多种机器学习方法系统，能够在服务器端针对不同的用户采取不同的过滤方案。

在实用垃圾邮件系统研发中，综合各种方法(包括各种机器学习方法、黑白名单人工规则方法甚至图片分析方法等)和各种特征是我们接下来进一步研究的方向。

参考文献:
[1]王申. 基于内容的垃圾邮件过滤技术若干研究[D].北京：中国科学院,2005.
[2]申庆永，张建忠，何云，等. 中文垃圾邮件过滤系统中的实时分词算法设计.计算机工程与应用，2007，43(3).
[3] Y Yang，Pedersen. A Comparative Study on Feature Selection in Text Categorization [A]. In InternationalConference on Machine Learning (ICML) [C], 1997.
[4] SAHAMI M,DUMAIS S,HECKERMAN D,et a1．A Bayesian approach to filtering Junk e-mail[c]//AAAI Workshop on Learning for Text Categorization．Madison，Wisconsin：[s.n.]，1998：55-62．
[5] GRAHAM P. A plan for spam[EB／OL]．URL: ／spam．htm1．
[6] GRAHAM P. Better Bayesian filtering[EB／OL]．URL：／better．htm1．
[7] ROBINSON G．A statistical approach to the spare problem[J／OL]．Linux Journal,2003 (107).URL:/artcle.php?sid=6467.
[8] Han Jiawei.数据挖掘概念与技术.机械工业出版社，2001，6.
[9] 涂承胜,刁力力,鲁明羽,等.Boosting家族AdaBoost系列代表算法. 计算机科学,2003V ol.30,No3.
[10] Harris Drucker,Vladimir Vapnik，and Dongui Wu.“support vector machines for spam categorization，”IEEE.。