推荐星级:
- 1
- 2
- 3
- 4
- 5
改进的朴素贝叶斯算法在垃圾邮件过滤中的研究
资料介绍
提出了一种利用支持向量机改进的朴素贝叶斯算法——TSVM-NB算法。首先利用NB算法对样本集进行初次训练,利用支持向量机构造一个最优分类超平面,每个样本根据与其距离最近样本的类型是否相同进行取舍,这样既降低样本空间规模,又提高每个样本类别的独立性,最后再次用朴素贝叶斯算法训练样本集从而生成分类模型。仿真实验结果表明,该算法在样本空间进行取舍过程当中消除了冗余属性,可以快速得到分类特征子集,提高了垃圾邮件过滤的分类速度、召回率和正确率。
部分文件列表
文件名 | 大小 |
改进的朴素贝叶斯算法在垃圾邮件过滤中的研究.pdf | 1M |
部分页面预览
(完整内容请下载后查看)第 38 卷第 4 期
2017 年 4 月
通
信
学
报
Vol.38 No.4
April 2017
Journal on Communications
doi:10.11959/j.issn.1000-436x.2017084
改进的朴素贝叶斯算法在垃圾邮件过滤中的研究
1
1
1,2
1
杨雷 ,曹翠玲 ,孙建国 ,张立国
(1. 哈尔滨工程大学计算机科学与技术学院, 黑龙江 哈尔滨 150001;
2. 中国科学院信息工程研究所, 北京 100093)
摘 要:提出了一种利用支持向量机改进的朴素贝叶斯算法——TSVM-NB 算法。首先利用 NB 算法对样本集进
行初次训练,利用支持向量机构造一个最优分类超平面,每个样本根据与其距离最近样本的类型是否相同进行取
舍,这样既降低样本空间规模,又提高每个样本类别的独立性,最后再次用朴素贝叶斯算法训练样本集从而生成
分类模型。仿真实验结果表明,该算法在样本空间进行取舍过程当中消除了冗余属性,可以快速得到分类特征子
集,提高了垃圾邮件过滤的分类速度、召回率和正确率。
关键词:邮件过滤;朴素贝叶斯;支持向量机;修剪策略
中图分类号:TP309
文献标识码:A
Study on an improved naive Bayes algorithm in spam filtering
1
1
1,2
YANG Lei , CAO Cui-ling , SUN Jian-guo , ZHANG Li-guo
1
(1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China;
2. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China)
Abstract: A method of improved support vector machine naive Bayes algorithm was proposed——TSVM-NB algorithm.
First using NB algorithm to initial sample set, constructing an optimal classification by SVM, each sample according to
its distance from the sample was the same type of recent choice, so as to reduce the size of the sample space, but also im-
prove the independence of each sample the last category, again with naive Bayes algorithm training set to generate the
classification model. Simulation results show that the algorithm selection process to eliminate the redundant attributes in
the sample space, the classification feature subset can be got quickly and improve spam filtering classification speed, re-
call rate and accuracy of the same algorithm.
Key words: spam filtering, naive Bayes, SVM, trim strategy
[2]
1) 黑白名单过滤 。该方法分为黑白 2 个名单
1 引言
列表,如果一个 IP 频繁发送垃圾邮件,就将该 IP
放入黑名单中,此后该地址发送的邮件都将默认为
垃圾邮件,白名单与其相反,都视为正常邮件。还
有实时黑白名单技术,该技术的黑白名单列表交由
第三方来维护,该方法是通过 DNS 的方式来动态
地查询某个 IP 地址是否在列表中。如果对方采用动
态或隐藏 IP,该方法将受到限制。
近年来,网络通信技术飞速发展,电子邮件成
为人们日常生活和工作的主要沟通方式之一,但垃
圾邮件问题也接踵而来。根据中国互联网协会最新
[1]
调查报告显示 ,用户电子邮箱平均每周收到邮件
38.6 封,其中,垃圾邮件 12.8 封,占比高达 33.1%。
大量的垃圾邮件不但浪费了网络带宽和资源,也造
成了时间和金钱上的损失,因此,人们对于垃圾邮
件过滤技术的发展需求强烈。
2) 基于规则的过滤技术。决策树是基于规则过
滤技术的代表,1966 年,Hunt 研制了一个关于概
念学习的系统(CLS,concept learning system),这是
目前,垃圾邮件过滤方法主要分为以下 3 类。
收稿日期:2016-12-30;修回日期:2017-02-22
基金项目:国家自然科学基金资助项目(No.61202455, No.61472096)
Foundation Item: The National Natural Science Foundation of China (No.61202455, No.61472096)
2017084-1
第 4 期
·141·
最早出现的决策树相关的学习系杨统雷,等为:改后进人的决朴素策贝树叶斯算法在垃圾邮件过滤中的研究
P(x , x ,… , x | C )
1
2
n
j
P(C | x , x ,… , x ) =
(1)
j
1
2
n
模型的学习打下了基础。1979 年,Quinlan 提出了
P(C ,C ,… ,C )
1
2
n
迭代分类器 ID3 算法,这是决策树算法的代表。4
其中, P(C ) 表示属于类别C 的概率; P(x , x ,… ,
j
j
1
2
[3]
年后,他又提出了 C4.5 算法 ,C4.5 算法针对 ID3
x | C ) 表示在待处理文本属于类别C 的条件下,该
n
j
j
不能处理连续值属性的数据的缺点进行了改进。除
此之外也可以用在增量式学习上,该算法根据数据
的不断增加而加以调整,弥补了 ID3 算法在该方面
文 本 含 有 属 性 向 量 x , x , x ,… , x 的 概 率 ;
1
2
3
n
P(C ,C ,… ,C ) 是给定的所有文本类别的联合概率;
1
2
n
由于 P(C ,C ,… ,C ) 通过训练为已知的常数,因此,
[4]
1
2
n
的不足之处,此外,Ruggieri 提出了对 C4.5 的改
可以将式(1)最大求解过程简化为式(2)。
进算法 EC4.5。这些算法虽然在一定程度上能够
满足需求,但是其根本原理都是根据与预设规则
比较结果来判定是否为垃圾邮件,并且这些规则
一般都是静态设置的,缺少可信度的知识学习策
略,在规律不明显的应用领域中过滤效果很差,
准确度很低。
C
= arg max P(x , x ,… , x | C )P(C )
(2)
NB
1
2
n
j
j
C ∈C
j
朴素贝叶斯算法分类模型建立在属性之间相
互 独 立 性 的 基 础 上 , 即 在 类 别 C 中 属 性 项
j
x , x , x ,… , x 之间不存在任何依赖关系,属性节
1
2
3
n
点的关系是相互独立的。根据朴素贝叶斯的类条件
3) 基于内容统计的过滤技术。这种算法速度较
快、效率较高、耗费较少,在文本过滤方面得到广
泛的应用,垃圾邮件过滤中最常用的算法是朴素贝
独立假设,则有
P(x , x ,… , x | C ) =
P(x | C )
(3)
∏
1
2
n
j
i
j
[5]
叶斯算法和支持向量机算法 。朴素贝叶斯算法实
其中,条件概率 P(x | C ) 可以从训练集中求得,依
[6]
i
j
现简单、分类快速 ,使用较少的训练集就可以获
据式(3),对于一个未知类别的待处理文本 X(x ,
1
取一个文本类型预测的估计概率值,但它依赖于一
个常用的错误假设,一个属性对全局的影响与其他
属性是相互独立的,而这样的假设在实际应用当
中往往是不成立的,因此,算法准确率和召回率
有所下降。SVM 通过最大化决策边界的边缘来控
x ,… , x ) ,可以分别求出 X 归属各项类别 C 的概
2
n
i
率 P(X | C )P(C ) ,然后选择其中最大值作为该文
i
i
本类别,将式(3)代入式(2)得到朴素贝叶斯求解式
C
= argmax P(C ) P(x | C )
(4)
∏
NB
j
i
j
[7]
C ∈C
j
制模型的能力 ,但这是在线性可分的情况下,
当输入的数据不是线性可分的时候就要用到核函
数,利用核函数将低维空间不可分的属性映射到
了多维空间,在多维空间中再次用原有的方式对
属性进行分类,但是这无疑增加了计算量以及空
间时间复杂度。除此之外,SVM 还致力于类别是
2 个类型的数据,当类别有多个类型时,算法也
受到了限制。
朴素贝叶斯模型的实现主要可以分为 4 个步骤。
1) 设 X(x , x ,… , x ) 为一个待分类处理文本,
1
2
m
而每个 x 为 X 的一个特征属性向量。
2) 类别集合C = (C ,C ,… ,C ) ,该集合是预先
1
2
n
已得到的。
3)计算 P(C | X) , P(C | X) ,…, P(C | X) 。
1
2
n
4) 如果存在 P(C | X) = max{P(C | X), P(C | X),
k
1
2
… , P(C | X)} ,则 X ∈C 。
n
k
2 朴素贝叶斯分类模型
从图 1 可以看出,整个算法的核心部分就是训
练集的学习训练过程,训练之后所形成的分类器可
直接应用。
朴素贝叶斯算法分类模型之所以备受人们关注,
[8~10]
是因为它实现简单且性能较好,由 于 计算的高效性和
高精度,朴素贝叶斯分类模型在文本分类领域得到了
由上述原理可以看出,先根据训练集计算某一
类已知文本分类的先验概率,得到计算结果的后验
概率后,对后续收到的新的文本类型进行分析预
料,在已经得知的分类概率条件下,得到待处理文
本属于某一类别的概率值,并取其中最大值,则将
该文本归类到最大值的那一类当中,由于条件独立
性假设,该算法模型得到收敛。
广泛的应用
。朴素贝叶斯分类原理是求解向量
X(x , x ,… , x ) 属于类别 C(C ,C ,… ,C ) 的概率值
1
2
n
1
2
j
(P, P ,… , P ) ,其中, P 是向量 X(x , x ,… , x ) 属
1
2
j
j
1
2
n
于类别 C 的概率,则 max(P, P ,… , P ) 对应的就是
j
1
2
n
文本 X 所属类别,因此,分类问题转换为求解式(1)
的最大值过程。
2017084-2
全部评论(0)