发布时间 : 星期二 文章“垃圾邮件”的智能分析、过滤和Rough集讨论更新完毕开始阅读f6bae7fdc8d376eeaeaa318a
“垃圾邮件”的智能分析、过滤及Rough集讨论
刘洋1 杜孝平2 罗平3 侯志辉1 郭晨4 骆焕林1
1 重庆邮电学院99＃信箱 重庆 400065
（lycqydxy@eyou.com）
2 北京大学信息科学中心视觉与听觉国家重点实验室 北京 100871
3 中国科学院计算所 北京 100080
4 南京大学计算机科学与技术系第二研究室 南京 210093
摘 要 Internet的迅速发展，电子邮件的应用变得十分广泛，但是许多无用、有害信息
随之而来。本文通过对“垃圾邮件”的分析、处理，讨论了电子邮件的智能过滤问题，并进行了基于粗糙集理论的邮件信头分析和实验。最后，介绍了下一步的工作。
关键词 电子邮件 垃圾邮件 过滤
1、前言
Internet的迅速发展，人与人的交往更加快捷方便，电子邮件（E-mail，Electronic mail）成为信息交互的重要工具，人们用它交流思想、传输文件、发表意见等。据IDC调查，2000年全球日平均发送邮件超过100亿封，到2005年将达350亿封以上。E-mail的日益普及，我们注意到网络管理面临着新问题——垃圾邮件的泛滥。所谓垃圾邮件主要有两类，一类是名目繁多的商业广告，另一类是非法团体为其政治、经济等目的，进行的“网络宣传”。后者的危害性显然远远大于前者。垃圾邮件耗费了有限的网络资源，反动邮件严重破坏了社会稳定。另外，它还侵犯了个人隐私，浪费了用户大量时间。所以垃圾邮件的智能分析、自动过滤，是目前研究的一个热点。
目前邮件过滤主要的方法有如下三种：（1）安全认证方法，也就是用户A向用户B发送邮件时，必须到用户B的邮件服务器上先进行登记，得到授权，否则邮件服务器拒绝接收。虽然有效地防止未经认证的用户发来邮件，具有很高的安全性，但影响了邮件的易用性；(2)基于规则的方法，很多时候是基于关键词匹配的邮件过滤，虽然能够处理邮件头和正文，但是实质还是生硬的二值判断，局限在二维空间上进行处理，缺少可信度的知识，同时要求用户自己定义规则，对用户的素质要求高，用户需要花费很多时间定义自己的规则，如果用户的兴趣发生变化，规则也要进行很大的改变，另外规则的纯粹人工定制，可能考虑并不周全；（3）统计的方法，可以不考虑具体的语义环境，但是只能区分合法邮件和垃圾邮件，很难进行分类。基于上述情况，本文从电子邮件的体系结构及传输协议入手，设计了基于“用户个性化”的垃圾邮件智能分析过滤概念系统模型，充分考虑到了现有方法的优点和缺陷。
2、电子邮件的体系
2.1 电子邮件的结构及传输
电子邮件可以视为半结构化的文本文件，包括邮件头和正文。RFC822标准邮件头则包括发信者的IP地址、邮件地址和邮件标题等信息。邮件的标题一般概括了其主要内容，正文则是该邮件的全部内容。通常情况下，一封E-mail的收发是从用户发出，通过发送邮件
本文得到了重庆邮电学院科创基金和课题组项目启动经费的资助。
刘洋（1980——）男 汉族 四川泸州人 学士，IEEE会员，计算机科学与技术研究所助理研究员，发表论文10余篇，主要研究方向：信息检索，通信中的人工智能。杜孝平，博士后，主要研究方向：数据挖掘。
1
客户端程序送到SMTP服务器，再转发到目的信箱。最后，由POP3服务器程序配合帐号、口令接收信箱的邮件。 2.2 相关网络协议
支持基于Internet的电子邮件服务协议主要有：SMTP、POP3、IMAP、MIME、HTTP等。其中SMTP和POP3配合完成简单的邮件收发。SMTP协议（Simple Mail Transfer Protocol，简单邮件传输协议）定义了传输普通正文文本（ASCII文本）的标准，提供了全双工通信，缺点是安全性不高。后来出现了ESMTP（扩展的SMTP协议）加以改进。现有大部分C/S都支持SMTP，故我们现有的研究是基于该协议的。另外，对于图像、声音、二进位格式等的非文本信息，MIME协议规定了相应的标准，这是复杂邮件过滤的基本原理，这里不作详细讨论。[1]
3、垃圾邮件过滤系统分析与设计
训练邮件 一 次 过 滤
邮件流 测试邮件 邮件自动分类预处理向量空间模型过 用 滤 户 分类词典 手工归档 图1 垃圾邮件智能分析、过滤系统框图
整个系统的概念化设计如图1所示，它基于“用户个性化兴趣”，用户首先随机抽取一定量的邮件进行人工训练，建立用户个性化安全模型，自动学习用户在邮件处理方面的特征，并利用测试邮件调整，生成相关规则，同时兼及人为定义规则（特别注意的是，不同用户兴趣
需求不同，其训练邮件和测试邮件相应不同，由于是自动生成规则，对系统本身影响不大，所以扩展性比较好）。通过分类词典对邮件自动分类，以便更好地进行预处理和建立向量空间模型，根据
用户需求和兴趣的变化自适应的调整向量空间模型，由此过滤出邮件，另外有选择地手工归档，进行二次过滤，提高处理效率，整个过程中系统可以进行自动的邮件回复。而且，该系统由于分类词典和对关键词进行标引，所以可以很好地支持中英文垃圾邮件过滤。具体包括以下几方面的工作： 3.1 邮件自动分类
邮件的自动分类，目的是：（1）建立邮件的关键词索引，使后续操作更明确、清楚，便于用户查询，避免了邮件虽经过滤，但由于没有分类造成的杂乱无章，给用户的处理造成巨大的的消耗；（2）这里对邮件向量的定义有机地和3.3节规则向量的定义统一起来，支持了向量空间模型，有利于系统实现和运行。
根据邮件头或正文的特征信息进行关键词标引，计算出与其相关程度最大的一个或多个
二次过滤 2
子类，将邮件划归到这些子类中，使用户可以通过浏览分类体系直接查询到该邮件。分类词典对于业务广的大客户可以使用北京大学计算语言所的“人民日报”语料库，个人用户也可以自己制定。而无法进行关键词标引（即系统不能识别）的邮件定义归属同一类，在邮件预处理阶段直接过滤，以提高处理速率补偿有效率的损耗。
邮件经过自动标引处理后，得到文档中最主要的m个关键词及其权值构成的关键词标引结果，构成如下被称为本地权值的向量L＝{ l1，l2，??lm }。给出一封邮件向量表示的具体步骤为：（1）找出邮件中所有词；（2）删除高频出现但没有实际意义的词，如但是、然而等；（3）对于未被删除的词计算权值。从分类词典中提取与这m个关键词相关的n个分类的关系系数gij，可以构造出如下的全局相关矩阵：
G＝ 通过运算得到整个邮件相对于n个分类的归属度向量C＝L.G＝{ c1，c2???cn}。最后将邮件归并到满足ci ≥cmin（cmin是预先设定的某个阀值）的分类中，实现邮件自动分类。[2]
“关键词标引表示法”来表示WWW上待学习的邮件时，表示邮件的特征向量可能会达到千维以上。如此高维的特征将大大增加机器的学习时间，而仅产生与之小得多的特征向量集相关的学习分类结果，显然是不适宜的。因而可以构造一个评价函数，对特征向量集的每个特征进行独立评估、打分，然后对所有特征按其评估分大小进行排序，选取用户自定义数目的最佳特征作为结果的特征子集——即邮件向量子集。文献[3]提出了互信息（Mutual Information）评价函数，效果较好：
g11 g12??????g1n g21 g22??????g2n ???????????? gm1 gm2??????gmn MutualInfoText(F)??P(Ci)logiP(Ci/W)P(W)F－关键词W的特征； P(W)－关键词W出现的概率； P(Ci)－第i类值的出现概率；
P(Ci/W)－关键词W出现时属于第i类的条件概率。
3.2 预处理
邮件的预处理主要包括两方面的内容，一是将半结构化邮件的无用结构信息去掉，只包含标题、内容和发送者；二是由用户制定和系统自主学习获得“恶意地址等构成的规则库”，进行简单的地址过滤或地址过滤加简单的关键词匹配过滤。这里说明的是，目前很多邮件过滤系
统对“地址过滤加简单关键词匹配过滤”的处理是“硬匹配”，凡是包含恶意地址和垃圾关键词，即认为非法，需要过滤掉，这样有效率显然损害很大。我们是综合考虑各种可能的情况，对于简单的邮件可以采用上述方法，相对复杂的化实际是放弃匹配判断。因此，系统收集的源信息包括：IP主机或网络地
址、域名、Mail－From字段，以及标题、正文、附件处理得到的关键词。对于无法判断的邮件，则建立向量空间模型进一步处理。[4]
3
3.3 向量空间模型
向量空间模型（the Vector Space Model）已被人们普遍认为是一种非常有效的检索模型，它具有自然语言界面，表示直观，使用方便，可以借鉴用到信息过滤系统中。在以向量空间模型构造的邮件过滤模型中，根据“自动分类”得到的本地权值向量L＝{ l1，l2，??lm }（见3.1），同时，过滤规则是以自然语言表示的，采用表示邮件向量的方法表示规则向量，故一个规则向量P表示为：P＝{ u1，u2，??um }（ui表示权值）。衡量一封邮件的向量表示与规则向量表示的相似度，也就是判决该邮件是否需要过滤，一般通过求两个向量夹角的余弦值来计算，即：
D*P sam（L,P）＝cos（L,P）＝ ＝ [D]*[P] ?l*uii?1m2ii?1mi ?[0,1]2i
?l*?ui?1m该值越大，表明它们的相似度越大，反之则越小。然后，人为设定一个阀值，过滤掉相似度小于该阀值的邮件。[5]很多情况下由于将一封有用邮件归为垃圾邮件所带来的危害远大于将一封垃圾邮件归为有用邮件，所以根据用户的需要，阀值的设定可以相对较小(如0.50)。 3.4 二次过滤
对于一次过滤出的邮件，可能存在一些有价值邮件，例如基于关键词“法轮功”的邮件可能是上级机关函发的批判法轮功重要文件，或者是反动组织鼓吹其罪恶的流毒。后者必须过滤，但是很多时候，在简单关键词匹配或相似度计算值较小的情况下很可能把前者一起过滤掉了，更糟糕的是我们很可能还不知道这种情况的发生，这对于有特殊要求的用户（如政府机关）损害是很大的。所以，我们设计了一次过滤出的邮件进行手工归档来提取被错误过滤的邮件。
对一次过滤出来的已经分类的邮件，建立相应的数据库，采用“排队”策略，相似度相对较高的邮件排在前面，无法判别的邮件，其相似度定义为0，排在队尾。同时建立关键词索引，用户可以很方便地了解邮件的类属及各类属的邮件数量，并查询按相似度排列和类属的邮件列表，灵活、有针对地进行归档，减少了工作量，挽救了错误过滤的邮件，提高了垃圾邮件处理的效率。另外，手工归档是可以选择的，特别是对青少年用户而言，该功能的权限完全可以设置为禁止，防患于未然，隔离有害信息侵蚀。这样系统的功能就比较完善，而且扩展性也有提高。 3.5 邮件的自动回复
邮件过滤时，过滤系统内部有时也需要产生特定邮件：（1）将垃圾邮件过滤后，发送邮件通知用户（在信体中需要描述被过滤邮件情况）；（2）自动回复部分邮件（其内容和地址由用户自主定义）。文献[6]提供了一个较好的创建邮件自动回复方法，程序修改如下：[6]
# Mail head
{ print newmail (“From: $to\\n”); print newmail (“To: $from\\n”);
print newmail (“Subject: Auto Reply From < $ to >!!!\\n”); print newmail (“LoopFlag, Done\\n”);} ## Mail body
4