“垃圾邮件”的智能分析、过滤和Rough集讨论.doc

“垃圾邮件”的智能分析、过滤及Rough集讨论
刘洋1 杜孝平2 罗平3 侯志辉1 郭晨4 骆焕林1
1 重庆邮电学院99＃信箱 重庆 400065
（lycqydxy@）
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余篇，主要研究方向：信息检索，通信中的人工智能。杜孝平，博士后，主要研究方向：数据挖掘。
客户端程序送到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节规则向量的定义统一起来，支持了向量空间模型，有利于系统实现和运行。
根据邮件头或正文的特征信息进行关键词标引，计算出与其相关程度最大的一个或多个子类，将邮件划归到这些子类中，使用户可以通过浏览分类体系直接查询到该邮件。分类词典对于业务广的大客户可以使用北京大学计算语言所的“人民日报”语料库，个人用户也可以自己制定。而无法进行关键词标引（即系统不能识别）的邮件定义归属同一类，在邮件预处理阶段直接过滤，以提高处理速率补偿有效率的损耗。
邮件经过自动标引处理后，得到文档中最主要的m个关键词及其权值构成的关键词标引结果，构成如下被称为本地权值的向量L＝{ l1，l2，……lm }。给出一封邮件向量表示的具体步骤为：（1）找出邮件中所有词；（2）删除高频出现但没有实际意义的词，如但是、然而等；（3）对于未被删除的词计算权值。从分类词典中提取与这m个关键词相关的n个分类的关系系数gij，可以构造出如下的全局相关矩阵：
g11 g12………………g1n
g21 g22………………g2n
………………………………
gm1 gm2………………gmn
G＝

通过运算得到整个邮件相对于n个分类的归属度向量C＝L.G＝{ c1，c2………cn}。最后将邮件归并到满足ci ≥cmin（cmin是预先设定的某个阀值）的分类中，实现邮件自动分类。[2]
“关键词标引表示法”来表示WWW上待学习的邮件时，表示邮件的特征向量可能会达到千维以上。如此高维的特征将大大增加机器的学习时间，而仅产生与之小得多的特征向量集相关的学习分类结果，显然是不适宜的。因而可以构造一个评价函数，对特征向量集的每个特征进行独立评估、打分，然后对所有特征按其评估分大小进行排序，选取用户自定义数目的最佳特征作为结果的特征子集——即邮件向量子集。文献[3]提出了互信息（Mutual Information）评价函数，效果较好：

F－关键词W的特征； P(W)－关键词W出现的概率； －第i类值的出现概率；
－关键词W出现时属于第i类的条件概率。
3.2 预处理
邮件的预处理主要包括两方面的内容，一是将半结构化邮件的无用结构信息去掉，只包含标题、内容和发送者；二是由用户制定和系统自主学习获得“恶意地址等构成的规则库”，进行简单的地址过滤或地址过滤加简单的关键词匹配过滤。这里说明的是，目前很多邮件过滤系统对“地址过滤加简单关键词匹配过滤”的处理是“硬匹配”，凡是包含恶意地址和垃圾关键词，即认为非法，需要过滤掉，这样有效率显然损害很大。我们是综合考虑各种可能的情况，对于简单的邮件可以采用上述方法，相对复杂的化实际是放弃匹配判断。因此，系统收集的源信息包括：IP主机或网络地址、域名、Mail－From字段，以及标题、正文、附件处理得到的关键词。对于无法判断的邮件，则建立向量空间模型进一步处理。[4]

3.3 向量空间模型
向量空间模型（the Vector Space Model）已被人们普遍认为是一种非常有效的检索模型，它具有自然语言界面，表示直观，使用方便，可以借鉴用到信息过滤系统中。在以向量空间模型构造的邮件过滤模型中，根据“自动分类”得到的本地权值向量L＝{ l1，l2，……lm }（见3.1），同时，过滤规则是以自然语言表示的，采用表示邮件向量的方法表示规则向量，故一个规则向量P表示为：P＝{ u1，u2，……um }（ui表示权值）。衡量一封邮件的向量表示与规则向量表示的相似度，也就是判决该邮件是否需要过滤，一般通过求两个向量夹角的余弦值来计算，即：
[D]*[P]
D*P

sam（L,P）＝cos（L,P）＝ ＝

该值越大，表明它们的相似度越大，反之则越小。然后，人为设定一个阀值，过滤掉相似度小于该阀值的邮件。[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
{ print newmail (“$ rebody\n”);
close (newmail);}
system (“cat $ newmail path/var/qmail/bin/qmail-inject”); //回复邮件注入qmail-queue队列
4、基于粗糙集（Rough集）理论的垃圾邮件分析、过滤
4.1 Rough集简介
Rough集理论是由波兰华沙理工大学Pawlak教授于20世纪80年代初提出的一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，具有无需提供问题所需处理的数据集合之外的任何先验信息的特点。Rough集的研究对象是由一个多值属性集合描述的一个向量集合，对于每个对象及其属性都有一个值作为其描述符号，对象、属性和描述符构成表达决策问题的3个基本要素。给定对象间的一个等价关系，即导致由等价类构成的近似空间的不分明关系。Rough集就用不分明对象类形成的上近似和下近似来描述，对应了确定属于给定类的最大对象集合和可能属于给定类的最小对象集合。上近似和下近似的差是一个边界集合，包含了所有不能确切判定是否属于给定类的对象。因而在质量分类，决策规则等方面具有巨大的应用前景。
4.2 目前的研究进展情况
很多情况下，邮件头包含了整封邮件的主要特征，我们希望通过对邮件头的处理，获得较好的处理结果。根据Rough集理论，其流程如下：
（1）理解领域知识和相关的先验知识，明确系统目标，人工定义条件属性和决策属性，得到决策表的框架结构；
（2）收集大量样本，填充决策表（注意样本的一般性，去除明显错误的冗余噪音数据）；
（3）进行数据的预处理：数据补齐和数据的离散化；
（4）属性约简，即考察条件属性相对于决策属性的分类能力，使条件属性个数最少而不改变其分类能力；
（5）值约简，去掉无用的属性，获得初步的知识库；
（6）将归纳出的知识应用于实践，检验其正确性，相应改进前面的操作。
4.2.1 决策表条件属性和决策属性描述
在人工分析了大量信头样本的基础上，结合邮件收发的理论知识，我们归纳出了以下决策表的条件属性：
属性一：邮件中继次数，它实际上就是信头中“Received:”项的个数；
属性二：收件人个数；
属性三：邮件路由信息的中断次数，若前一条“Received：”信头中接收站点的域名和ip与后一条“Received：”信头中发送站点的域名和ip均不相同，则被视为路由信息中断；
属性四：“Received：”项中的各个域名与其IP不匹配的次数，由于域名的动态性和网络资源的限制，无法获得域名与IP的匹配信息；所以这一属性都缺省为0；保留此属性，以备以后有条件时应用；
属性五：“Received：”中from项缺少域名的次数，我们规定：若最后一个Received中（即第一个中继的SMTP服务器添加的路由信息）没有from项的域名，且发信的地址与此Received中的by项匹配，则此处缺少域名是合理的；
属性六：“Received：”中的by项缺少域名的次数；
属性七：“Received：”中的from项没有ip的次数，我们规定：若最后一个Received中（即第一个中继的SMTP服务器添加的路由信息）没有from项的ip和域名，且发信的地址与此Received中的by项匹配，则此处缺少ip是合理的；
属性八：“From：”中的原始发送地址是否与“Received：”中的原始发送地址一致，若“From：”中的原始发送地址或“Received：”中的原始发送地址不规范，则视为不一致；若最后一个“Receiced：”中有from项，则它的内容是原始发送地址；否则最后一个“Receiced：”中的by项的内容是原始发送地址；
属性九：“To：”中的目的地址是否与“Received：”中的实际收信人的地址一致；若“To：”中的目的地址或“Received：”中的实际收信人的地址不规范，则视为不一致；实际收信人地址是第一个“Received：”（最后一个SMTP服务器添加的信息）中的by项；
属性十：若存在“Delivered-To：”一项则比较它和“To：”是否一致，这一属性值的缺省值为1；
属性十一：若存在“Return_Path：”则比较和“From：”是否一致，属性值缺省值为1。
决策表的决策属性描述：
邮件类型
决策编号
普通邮件
1
广告邮件
2
反动邮件
3

4.2.2 处理所用的较优算法
数据离散化算法（改进的贪心算法1（启发式算法））：
步骤1：根据原来的信息系统S构造新的信息系统；
步骤2：初始化断点集CUT＝空集；
步骤3：选取所有列中1的个数最多的断点加入到CUT中，去掉此断点所在的列和在此断点上值为1的行；当有一个以上的断点的1的个数相同时，把对应的断点所在的列值为1的对应的行的1的数目相加，取和最小的断点；
步骤4：如果信息系统中的元素不为空，则转第3步，否则停止，此时CUT即是得到的断点集。
属性约简算法（基于信息熵的算法1）:
步骤1：计算决策表T中决策属性集D相对条件属性集C的条件熵H(D/C);
步骤2：计算条件属性集C中相对决策属性集D的核属性集，将非核条件属性记入集合At中，即At＝C-；
步骤3：令B＝，
（1）如果！＝0，则计算条件熵H(D/B)，转（4）；
（2）对每个属性，计算决策属性集D相对条件属性集的条件熵H(D/)；
（3）选择使H(D/)最小的属性（若同时有多个属性达到最小值，则从中选取一个与B的属性值组合数最少的属性作为），并且At＝At－，B＝B ；
（4）若H(D/B)＝H(D/C)则终止，否则转（2）。

值约简算法（启发式值约简算法）：
算法输入：信息系统T包含n条记录，m-1个条件属性，1个决策属性。
算法输出：T的值约简。
步骤1：对信息表中的条件属性进行逐列考察。若删除该列后产生冲突，则保留冲突记录的原该属性值；否则，如果出现重复记录，可将该记录的原属性值标为“*”；对于其它记录，将属性值标为“？”；
步骤2：删除可能产生的重复记录，并考察每条含有标为“？”的记录。如果仅由未被标记的属性值即可以判断出决策，我们将符号“？”改为“*”，否则将“？”改为原来的属性值。若某条记录的所有条件属性均被标记，则标记“？”改为原属性；
步骤3：删除所有条件属性均被标为“*”的记录及可能产生的重复记录（card（）＝）；
步骤4：如果两条记录仅有一个条件属性值不同，且其中一条记录的属性被标记为“*”，那么对该记录如果可由未被标记的属性值判断出决策，则删除另外一条记录，否则删除本记录。
知识匹配时，采用多数优先的匹配。
4.2.3 实验
随机获取一定数的样本（开始为40封邮件），每次实验递增4个样本，共做11次。性能指标主要通过正确率、错误率和未识别率来判断。实验平台是重庆邮电学院计算机科学与技术研究所开发的RIDAS（Rough Set Intelligent Data Analysis System），集成了有关Rough集30余种经典算法。性能测试如表1，性能图如图2：
编号
获取知识样本数
正确识别数
正确率
错误识别数
错误率
未识别数目
未识别率
1
40
33
82.50%
7
17.50%
0
0
2
44
37
84.09%
7
15.91%
0
0
3
48
41
85.41%
7
14.58%
0
0
4
52
45
86.54%
7
13.46%
0
0
5
56
49
87.50%
7
12.50%
0
0
6
60
49
81.67%
11
18.33%
0
0
7
64
53
82.81%
11
17.19%
0
0
8
68
55
80.88%
13
19.12%
0
0
9
72
59
81.94%
13
18.06%
0
0
10
76
58
76.31%
18
23.69%
0
0
11
80
61
76.25%
19
23.75%
0
0

图2 性能图
表1 性能测试表

结论：利用Rough集理论对垃圾邮件分析、过滤实践证明是可行的，效果较好，而且具有处理速度快，人——机交互简单的优点。[7] [8]
5、现有方案讨论及下一步的工作
经过电子邮件理论分析以后得出的11个决策表的条件属性是比较完善的，除了知识获取算法本身的问题外，还有如下影响性能的因素：
（1）对邮件分类的定义不太明确，主要是没有明确定义广告邮件和一般邮件间的差异，如某网站成功注册的认证信件和朋友发送的电子贺卡，这些信件从内容看是一般信件，但往往这些信件的信头信息有诸多疑点，严重影响决策性能；
（2）很多SMTP邮件服务器添加的“Received：”信头不规范，它们不能完整的填写该信头的各项内容，带来原来并不存在的信头疑点；
（3）利用正当路由，发送广告或反动邮件，会导致决策错误。
因此，我们下一步的工作：一是将3节讨论的概念系统架构与Rough集理论进一步有机结合，寻求更优解决方法；二是研究邮件描述语言的替换（如XML），获得更有效的向量、决策表示。

参考文献：
1、Internet电子邮件资源及应用大全 Will Salidle著 清华大学出版社 1996
2、王兰波等 国内信息导航系统中的信息自动分类子系统的设计与实现 计算机工程与应用 2002年3期
3、Yang. Y ete. A Comparative Study on Feature Selection in Text Categorization. In: Proc. Of the 14th Intl. Conf. on Machine Learning ICML97, 1997
4、罗万伯等 E-mail的数据安全和内容安全 计算机应用 2002年3期
5、张晓冬等 信息过滤的模糊聚类模型 计算机工程与应用 2002年9期
6、陈细谦等 基于Qmail的邮件过滤系统的设计与实现 现代计算机（下半月刊） 2001年9期
7、王国胤 Rough集理论与知识获取 西安交通大学出版社 2001
8、张 弋 粗集智能数据分析系统——RIDAS 重庆邮电学院硕士学位论文 2002.5
9、Y.Y.Yao Information-Theoretic Measures for Knowledge Discovery and Data Mining

Analysis and discussion about Spam filtering & anything
based on Rough set
Liu Yang1 Du Xiaoping2 Luo Ping3 Hou Zhihui1 Guo Cheng4 Luo Huanlin1
1 ChongQing University of Posts & Telecommunications 99# ChongQing 400065
（lycqydxy@）
2 Center for Information Science National Laboratory on Machine Perception, Peking University ,Beijing 100871 3 Institute of Computing Technology, The Chinese Academy of Science, Beijing 100080
4 Dept. of Computer Science, Nanjing University Nanjing 210093
Abstract：With the rapid development of Internet, E-mails have become widely applied, yet along goes a great deal of useless and harmful information. This paper, through the analyzing and processing of Spam, discusses E-mail intelligent filtering, engages in Rough Set Theory based analysis and experiment on E-mail-header and the introduction of the following research work is mentioned finally.
Keywords：E-mail, Spam, filter

9