关于冬天的诗歌-2013河南高考作文

138
2009
，
45
（
16
）
C omputerEngineeringandApplications
计算机工程与应用
粗 糙集与决策树在电子邮件分类与过滤中的应用
3
邓春燕
1
，
，陶多秀
2
，吕跃进
3
3
，
DENGChun- yan
1
，
TAODuo-xiu
2
，
LVYue-jin
3
广西宜州
5463001.
广西河池学院计算机与信息科学系，
南 宁
5300042.
广西大学电气工程学院，
南宁
5300043.
广西大学数学与信息科学学院，
1．DepartmentofComputerandInforma tionScience
，
HechiUniversity
，
Yizhou
，
Guangxi546300
，
China
eofElectri calEngineering
，
GuangxiUniversity
，
N anning530004
，
China
GuangxiUniversity
，
Nanning530004
，
eofMathematicsandInfor mationScience
，
E-mail
：
dchy7072@
DENGChun-yan
，
TAODuo- xiu
，
ationofroughsetanddecisiontreeine-mail classificationand
（
16
）：
erEngineerin gandApplications
，
2009
，
45138-140.Abstract
：
roughsetisanewdataanalysistoolt odealwith
ambiguityanduncertaintyofknowledge
；
ingroughsetswith
（
RS-DT
）
sibil ityofthesolutionaspamfilteringsolutionbasedonrough setsanddecisiontreedecisiontree
，
isonexperi mentswerealsomadebetweenSVMclassifier
，
ults showthattheRS-DTmodelcannotonlyreducetheerrorrateo fjudgingthe
normalemailasspam
，
butalsoim proveadaptivelearningofthefiltrationsystem.
Key words
：
spam
；
roughset
；
datami ning
；
decisiontree
摘要：垃圾邮件的识别与过滤是目前研究的热点 问题之一。而粗糙集是一种新的处理模糊和不确定性知识的数据分析工具，已
被成功地应用到许多有关分 类的领域。将粗糙集与决策树结合，提出一个基于
RS-DT
的邮件分类方案与模型，并进行了 实验及结
果分析。通过与朴素贝叶斯模型及
SVM
的比较，表明提出的基于
R S-DT
的模型可以降低把正常邮件错分为垃圾邮件的比率，提
高过滤系统的自学习能力。关键词：垃圾邮件；粗糙集；数据挖掘；决策树
文章编号：（
2009
）文献标识 码：中图分类号：
DOI
：
.1002-8331.2009.16.0401002 －833116-0138-03ATP182
1
引言
随着计算机技术的迅猛发展，网 络覆盖与应用的范围日
病毒程序或带有病毒的网络连接，甚至可获得用户的私人信息
或者导致用 户机器中毒；另一方面还影响了网络的正常运行，
垃圾邮件大量占用带宽，严重影响邮件服务器工作效率 ，甚至
造成网络阻塞。国内外研究的垃圾邮件过滤的方法主要有：查
表法（黑白名单，）、溯源 法、统计法（如贝叶斯分类器
[1]
）、质
RBL
询
-
回应 技术，但这些方法都缺少自学习能力，而文献
[2]
则只考
虑邮件头，忽略了邮件内容 的一些重要特征。
粗糙集理论是
20
世纪
80
年代初
Paw lak
首次提出
[3]
的一
种新的处理模糊和不确定性知识的数据分析工具。 由于在应用
中不需要先验知识等特点，目前它已成为国内外学术研究的热
点，在理论研究、图像 处理、模式识别、机器学习、知识获取、数
据挖掘和决策分析等许多领域得到了广泛应用
[4- 5]
。
本文提出一种基于粗糙集
-
决策树（
RS-DT
）的 邮件分类方
益广泛，电子邮件正被越来越多的人所使用。然而，电子邮件
在给人们带来极大便利 的同时，也带来了不少干扰，比如：垃
圾邮件的不时侵袭。垃圾邮件（
Spam
或JunkMail
），也称为
（
UnsolicitedCommercialE -mail
，不请自来的商业邮件）
UCE
或
UBE
（
Un solicitedBulkE-mail
，不请自来的大量电子邮件），
一般被概括为：向新 闻组或他人电子信箱发送的未经用户准
许、不受用户欢迎的、难以退掉的电子邮件或电子邮件列表。从< br>事此类活动的人员叫作垃圾邮件制造者（
Spammer
），其主要来
源为：商 业广告，站点宣传、恶意攻击的病毒携带邮件等。垃圾
邮件一方面影响用户的工作和生活，因为垃圾邮件 会大量吞食
用户的邮箱空间，占用用户的时间，而且会带来负面信息、一些
基金项目：国家自然 科学基金（
theNationalNaturalScienceFoundationofChin aunderGrantNo.70861001
）；广西研究生科研创新项目（
the
）。
InnovativeScientificResearchProjectofGuangx iGraduateNo.2
作者简介：邓春燕（
1971－
），女，讲师，主要研究 领域为数据挖掘、粗糙集理论与方法；陶多秀（
1985－
），女，在读硕士研究生，主要研究 领域为数据挖
掘、商业智能、管理决策；吕跃进（
1958－
），男，教授，主要研究 领域为数据挖掘、预测与决策。
收稿日期：
2008-12-15
修回日期：
2009-02-25

邓春燕，陶多秀，吕跃进：粗糙集与决策树在电子邮件分类与过滤 中的应用
案，将邮件头的特征和邮件文本的特征结合进行分析，扩展了
现有的条件属性，随后进 行粗糙集属性约简，降低向量空间维
数，减少了特征数，降低了待分类邮件数据集测试数据集的向
量空间的生成时间，从而提高分类速度，然后采用决策树算法
建树，提取规则，对邮件进行分类，识别 出垃圾邮件并进行过
滤，以提高分类正确率，降低把正常邮件错划为垃圾邮件的比
率，提高过滤 系统的自学习能力。
2009
，
45
（
16
）
13 9
树型结构的知识表示，便于直接转换为决策规则。决策树构造
的输入是一组带有类别标记的例 子，构造的结果是一棵二叉树
内部节点是属性，边是该属性的所有取值，有几个属或多叉树。
性 值，就有几条边，树的叶子节点是类别标记。决策树的生成是
一个从根节点开始、从上到下的递归过程， 一般根据分而治之
的思想，通过不断地将训练样本分割成子集来构造决策树。
5
2电子邮件机理
电子邮件是半结构化的文件。
RFC2822
规定了电子邮件在网络传输中的基本格式，
RFC1341
在
RFC822
的基础上又扩充
了多用途因特网邮件扩展
MIME
（
MultipurposeIntern etMail
）协议，这二者定义了目前正广泛使用的邮件格式。
Extensions
电子邮件通常包括邮件头和正文。
RFC2822
为邮件头定义了
20
多个 标准字段，主要有：
Message-ID
邮件的唯一标识符，
From
表示 邮件的发送方地址，
To
表示邮件收件人，
Subject
表
示邮件 的主题，
Date
表示邮件的创建时间等。这些字段表征了
一封邮件的属性，可用于识 别和分类邮件。
RS-DT
邮件过滤解决方案
对邮件样本集进行数据预处理，包括：分 词处理、特征选
取、生成向量空间；然后用粗糙集属性约简，进行数据降维，形
成新的向量空间 ，把这新空间作为决策表，当作输入，用决策树
进行分类，提取规则，达到分类邮件，识别和过滤垃圾邮 件的目
的。方案如图
1
所示。
邮件样本数据库
数据预处理
分 词处理特征选取生成向量空间
3
粗糙集基本理论简介
决策表
3.1
信 息系统、
信息系统是粗糙集理论及其应用紧密相关的一个概念。
一个信息系统
[4]< br>定义为一个四元组
S=
（
U
，），其中
UA
，
V
，
f
是对象的非空有限集合，称为论域；
A
为属性的非空有限集 ；
V=
∪
V
a
，
V
a
是属性
a< br>的值域；
f
：
U×A→V
是一个信息函数，
a∈A
R S
属性约简
离散化属性约简生成新的向量空间
决策树分类
训练、建树
测试评估
提取规则
邮件分
类器
垃圾邮件
过滤器
（）
坌a∈A
，
x∈U
，
fx
，
a∈V
a
。这 种定义方式使对象的知识可以方
便地以数据表格的形式描述。
若在四元组
S=
（
U
，）中，且
C疑D=覫
，
A
，
V
，< br>fA=C∪D
，
C
为
条件属性集，
D
为决策属性集， 则将这样的信息系统称为决策
表或决策信息系统。
图
1
模型结构示意图
5.1
邮件决策表
样本邮件经过邮件头特征提取、附件特征提取以及正文特
3.2< br>不可区分关系
不可区分关系（或称不分明关系
[5]
）在
S=
（
U
，）中，设
A
，
V
，
f
且
P ≠覫
，
P哿A
，
P
中所有等价关系的交集
疑P
称为
P
上的一种
不可区分关系（或称不分明关系），记作
IND
（
P
），即
（
P
）（
x
，）（
x
）（y
），
IND={y∈U×U
：
a=a坌a∈P}
[x]
IND
（
P
）
=
疑
[x]
a
a∈P征提取（其中在提取正文特征时先经过邮件解码）后，选取了
25
个特征属性。
根 据粗糙集对信息系统的定义，将邮件的集合作为论域，
每篇邮件作为论域中的对象，特征项集作为条件属 性集，即各
特征项为条件属性，特征项在邮件文本中的权重作为该属性在
对象上的属性值，邮件 所属类别作为决策属性，则这样的决策
表就是一个待分类的电子邮件决策系统。其中每行代表一封邮件，每列代表一个属性，
C
1
到
C
n
的值代表邮件的条 件属性，
D
代表决策属性，取值
V
D
={0
，分别表示正常 邮件、可疑邮
1
，
2}
，
件、垃圾邮件。示例如表
1
所示。
表
1
邮件分类决策表示例
C
1
C
2
C
3
C
4
1
0
0
1
1
2
3
2
1
5
4
2
0
1
2
1
C
5
1
1
0
1
C
6
0
2
1
…
1
C
7
0.12
0.80
0.20
…
0.76
…
…
…
…
…
…
C
25
0
5
5
…
6
D
0
1
1
…
2
其中
[x]
a
表示属性（关系）
a
中包含元素< br>x∈U
的概念或等价类。
3.3
属性约简
粗糙集属性约简是将决策表中 对决策分类不必要的属性
进行约简，在一定程度上去掉决策表中的冗余信息，对于每一
条实例来 说可能仍然有不必要的属性存在，因此在不引起冲突
的条件下，可将每一条实例中的该属性删除。
把邮件向量空间模型看成是决策表，作为粗糙集处理模块
的输入，通过离散算法对连续性数据进行离散 化，再通过约简
算法对新生成的决策表进行约简，降低向量空间维数，减少了
特征数，降低了待 分类邮件数据集测试数据集的向量空间的生
成时间，从而提高分类速度。
……………
发 送者域名与
IP
是否一致，取值
V
C
={1
，分别表示C
1
：
0}
，
1
一致、不一致。
4
决 策树简介
决策树
[6]
是一个可以自动对数据进行分类的树型结构，是
发送者 地址，按邮箱所在服务器进行编码。新浪的
C
2
：
163
、
可分别编为
1
、
2
等。

140
2009，
45
（
16
）
ComputerEngineeringan dApplications
计算机工程与应用
同时收到该封邮件的收件人个数，取值为整数。
C
3
：
邮件类型，取值
V
C
={0
，回复 、转发。
C
4
：
1
，
2}
表示直接发送、
4
5.5
垃圾邮件过滤评价指标说明
标题是否包含有意义的词，
有。
C
5
：
V
C
={0
，
1}
表示无、
5
附件数目，取值为整数。
C
6
：
字符
!
出现的 频度。
C
7
：
字符
$$
出现的频度。
C
8< br>：
…
正文
http
连接数。
C
25
：
D
，召回率
Recall
：系统发现垃圾邮件的能力，即垃
Re=
B+D
圾邮件检出率。这个指标反映了发现垃圾邮件的能力，召回率
越高，漏网的垃圾邮件就越 少；
D
；垃圾邮件的检对率
Precision
：
Pre=
C+D
精确率
Accuracy
：所有判别正确的邮件数与所有进行分类
的邮 件数的比率
Accur=
A+D
，
N
为邮件总数；
N
错误率
Errorrate
：
Err=1-Accur
等。
为了衡 量将正常邮件划分为垃圾邮件的比率，还采取了一
即
F1=
C
。
种新 的评估指标
F1
：
A+C
表
2
垃圾邮件过滤评价指标说明< br>垃圾邮件过滤评价指标说明
分类判定为正常邮件
分类判定为垃圾邮件
实际为正常 邮件
A
C
实际为垃圾邮件
B
D
5.2
数据预处理< br>决策表离散化：由于粗糙集较适合于处理离散化的属性
值，故对上述的一些取值较多的属性需要进 行离散化处理。为
了与分类的决策树结合较好，采用信息熵的方法
[7]
来离散化。< br>条件属性约简：为使空间降维，采用基于可辨识矩阵的
Johnson
算法
[8 ]
进行属性约简。
5.3
决策树建树算法
采用自顶向下方法递归地构造决策树 。按照经典的
ID3
建树算法思想，根据信息熵的原理，选取使信息增益最大者
[6]
作为分裂属性进行建树。目的是使得决策树对划分的不确定
程度减小。
）
由给定的
Generate_decision_tree
（
Si
，attributelist
，
test_attribute
训练数据产生一棵 邮件分类决策树
输入：邮件训练样本集
samples
，候选条件属性的集合
attributes_list
，
即
C
1
到
C
n
输出：一棵决策树
基本步骤如下：
（
1
）创建节点
N
；
）（
2if
邮件训练样本集
samples
都在同一个类
Cthen
；
（
3
）返回
N
作为叶节点，以类
C
标记：
）（
4ifattributes_list
为空
then< br>；

算法终止的一个条件
（
5
）返回
N
作为叶 节点，标记为
samples
中最普通的类，即出现最
多的类；
）选择
attributes_list
中具有最高信息增益的属性作为
test_
（6
attribute
；
（
7
）标记节点
N
为
test_attribute
；
（
8
）
foreacht est_attribute
中的己知值
ai
；
（
9
）由节 点
N
长出一个条件为
test_attribute=ai
的分枝；
）设
Si
是
samples
中
test_attribute=ai
的样本的集合；

一个（
10
划分
（
11
）
ifSi
为空
then
算法终止的另一个条件
（
12
）加上一个叶节点，标记为
samples
中最普通的类；
（
13
）（
Si
，
else
加上一个由
Generate_decisio n_treeattributelist
，
test_
）返回的节点，继续分裂节点 。

递归划分
attribute
DataSet
（
100< br>）
SpamE-mail
Database
语料
Recall
Precision
Accuracy
F1
Recall
Precision
Accuracy
F1
6
实验及结果分析
实验数据集采用
U CI
机器学习数据库
[9]
中的垃圾邮件数据
库
SpamE-mai lDatabase
。数据集包含
4601
个实例，每个实
例分别用
58
个特征属性来描述，其中
57
个为邮件特征属性，
1
个为类别标 识，即最后一列，其中垃圾邮件
1813
封。决策表离
散化、属性约简等均按文中所述 的对应方法。实验中将样本划
分为训练集和测试集，采用
10
折
-
交 叉验证，进行多次实验，取
平均结果。
此外，作者还收集了
3
个常用个人邮箱 的
100
封邮件。其
中正常邮件
70
封，垃圾邮件
20封，可疑邮件
10
封。按文中提
取邮件的特征属性来构造决策表，记为
D ataSet
（
100
）。
由实验结果（如表
3
所示）可知 ，将粗糙集与决策树结合，
能较大限度地降低属性空间维数，而且正确率、召回率、精确率
变化 不大，而将正常邮件划分为垃圾邮件的比率
F1
有较大程
度的降低。
表
3
实验结果
评价指标
（
%
）
SVM
86.53< br>79.67
86.00
8.22
94.80
92.58
94. 60
4.62
（
%
）
RS-DT
85.87
84. 10
85.33
5.23
94.24
94.71
94.20
2.67
贝叶斯（）
%
86.21
85.22
84．97
6 .58
92.79
94.20
92.70
4.85
5.4
规 则提取
决策树建立后，可以从中导出分类规则，称为规则抽取。
分类规则以“
IF-T NEN
”形式表示。从根到叶节点的每条路径创
建一个规则，规则的前件（“
IF”部分）是从根节点出发到达该叶
节点路径上所有的中间节点构成的一个“与”判断（沿着给定路< br>），而规则的后件（“
THEN
”径上的每个属性
-
值对的一个合取项
部分，结论）就是叶节点的类别。规则举例说明，如：
rule1
：
IFC< br>1
=0andC
8
≥0.8thenD=2
其实际意义为：如果发送者 域名和
IP
地址不一致且字符
$$
出现
的频度
≥0.8
，则这封邮件为垃圾邮件。
7
结束语
垃圾邮件过滤是目前的一个热点问题，本文研究 了基于粗
糙集和决策树结合的垃圾邮件过滤技术，将邮件头的特征和邮
件文本的特征结合进行分 析，扩展了现有的条件属性，提出了
一种
RS-DT
邮件分类方案，并进行了实验，给 出结果及其与
朴素贝叶斯的比较，实验表明基于
RS-DT
的模型能有效
SV M
、
降低错误识别率，尤其是将正常邮件判为垃圾邮件的比率。
（下转
184
页）

184
2009
，
45
（
16
）
12
ComputerEngineeringandApplications< br>计算机工程与应用
256×256
。实验中对图像加入的是
SNR=6
的高斯白噪声。自适
应高斯平滑滤波与几种常见去噪方法结果见图
3
。通过实验结果可以看到自适应高斯平滑滤波能够较好地对医学图像去噪。
这里
Z
x
（ ·）和
Z
x
（·）是沿
x
1
、
x
2
方向的一阶偏导数，
w
i
是待估计
点周围的局部分析窗。梯度的局部主方向 与这个矩阵的特征向
量有关。
比较式（
6
）、（
7
）和（< br>8
），似乎可以由局部协方差矩阵来估计
以确定如图
1
所示的平均区域 及各像矩阵
∑
及参数
ρ
、
σ
1
、
σ
2
，
素权值。然而协方差矩阵的估计结果可能是欠秩或不稳定的，
在这种情况下难以 直接求矩阵的逆。对于这个问题，有两种方
法解决：（
1
）使用矩阵算法中的迭代分解 技术求解；（
2
）使用局
部多尺度技术来估计局部方向
[5]
。该滤波器很好地满足了像素及权值选择的
3
个准则，兼顾
其代价是计算开销了图像 平滑去噪和边缘保护的问题。当然，
的增加。
（
a
）原始图像（
b< br>）有噪图像（
c
）样条平滑
5
实验
为验证结合空间和像素距离 加权的自适应高斯平滑滤波
（
d
）双边滤波
图
3
（
e
）小波去噪（
f
）自适应高斯平滑
器的效果因素，以下分别进行了几个实验 。
实验
1
前述三种算法的比较。图
2
（
a
）是256×256
的原始
在其上加入均值为
0
，方差
25
的高斯白噪声，得到
Lena
图像，
图
2
（
b
）的 有噪图像。图
2
（
c
）、（
d
）、（
e
） 分别是经高斯平滑滤波、
梯度倒数加权滤波、自适应高斯平滑滤波等三种平滑去噪方法
后得到的 结果。可以看出，图
2
（
e
）中图像的恢复比较好。
不同去噪方法的 实验比较
6
结语
本文研究了结合空间和像素距离加权的自适应高斯平滑
滤波器 ，其结合了高斯平滑滤波器和梯度倒数加权滤波器的特
点，充分考虑了图像的局部空间距离和像素距离。 因而，在降噪
的同时，自适应地保留了图像的局部边缘特性。分析和实验显
示该方法是有效的。
对于如何确定二维高斯函数的参数，以及如何简化确定局
部边缘的方向的计算量，都是需要进一 步研究和探讨的问题。
参考文献：
（
a
）原始图像（
b
）有 噪图像（
c
）高斯平滑滤波
彭天强，彭波
．
智能图像处理技术
[M]．
北京：电子工业出版
[1]
李弼程，
社，
2004.电子工业出版社，
[2]
阮秋琦
．
数字图象处理
[M]．2版
.
北京：
2007.
谢胜利
．
基于人类视觉系统的各 向异性扩散图像平滑方法
[J]．[3]
余庆军，
电子学报，（
1
） ：
2004
，
3217-20．
陈淑珍，陈彬，等
．
梯度倒 数加权平滑算法的改进与实现
[J]．
计
[4]
魏丹，
（
d
）梯度倒数加权滤波
图
2
（
e
）自适应高斯平滑滤波
算机应用研究，（
3
）：
2005153－154.
[5]FengX，
MilanfarP．Multi-scaleprincipalcomponentsana lysisfor
imagelocalorientationestimation[C]Proc eedingsofthe36th
AsilomarConferenceonSignals
，
SystemsandComputers
，
Pacific
CA
，

，
CyberneticsandSystems
，
1998< br>，
29
：
661-688.
科学出版社，
2002.[4]< br>张文修
.
粗糙集理论与方法
[M].
北京：
西安交通大学出版 社，
[5]
王国胤
.Rough
集理论与知识获取
[M].
西安：
2002.
李军
.
数据挖掘与知识发现
[M].
北京 ：高等教育出版社，
[6]
李雄飞，
2004.
-intervaldisc rerizationofcontinuous-[7]FayyadUM
，
valueda ttributesforclassificationlearning[C]Proceedingsof the
13thInternationalJointConferenceonArtificia lIntelligence
，
MorganKaufmann
，
1994< br>：
1022-1027.
[8]
：
~aleksthesis.
[9]
：
~mlearnMLRepository.
html.
张德运， 李金库
.
基于朴素贝叶斯和层次聚类的两阶段垃
[10]
廖明涛，
（
8
）：圾邮件过滤方法
[J].
微电子学与计算机，
2007
，
241-3
，
7.
三种滤波去噪效果
实验
2
与 其他方法的比较。这里对医学图像应用自适应
高斯平滑滤波与几种常见去噪方法进行比较，实验图片大小 为
（上接
140
页）
在今后的工作，将对以下方面进行进一步研究：
（
1
）文本特征的选取，结合文本数据挖掘，选取更能反映邮
件特征、有助于分类正常 邮件和垃圾邮件的条件属性。
（
2
）实验数据的规模问题。收集更具规模的数据集，尝 试将
此方法应用到更多的数据集中来进行实验和改进。
（
3
）考虑将粗糙集与 其他方法的结合以提高性能。
参考文献：
[1]SaharniM
，
Duma isS
，
HeckermanD
，
ianapproachto
fi lteringjunke-mail[C]ProceedingofAAAIWorkshoponIxam ing
1998
：
tCategorization
，
王国胤，吴渝
.
基于
RoughSet
的电子邮件分类系统
[J].
计算
[2]
李志君，
机科学，（
3
）：
200458-60，
66.
[3]ettheoryanditsapplicationstodataa nalysis[J].