垃圾邮件分类算法的研究与分析

垃圾邮件分类算法的研究与分析

西北工业大学计算机学院陕西西安710129

(School of Computer, Northwestern Polytechnic University Xi ' an 710129 China)

摘要：随着互联网的高速发展,电子邮件已经成为人们信息获取和信息交流的一个重要的渠道。与此同时垃圾邮件也成为互联网上的一个日益严重的安全问题,引起了越来越多的社会大众和研究人员的重视和关注。

为了有效的分辨垃圾邮件，本文通过对训练数据进行相应的预处理及特征提取，分别使用朴素贝叶斯、C4.5 决策树、支持向量机三种方法来对垃圾邮件进行分类，通过测试结果，比对各个分类算法的优劣，并进行了详细的分析。

关键词：垃圾邮件朴素贝叶斯 C4.5 决策树支持向量机

Abstract ：With the rapid development of the Internet, e-mail plays an important roles in people's information access and information exchange. At the same time, spam has become an increasingly serious security problem on the Internet, causing more and more attention of the community and researchers. In order to effectively distinguish the spam, this paper Pre-processings and extracts feature of the training data, and uses the NaiveBayes, C4.5 Decision Tree and SVM to classify the spam, Through the test results, compare and analysis the advantages and disadvantages of each classification algorithm.

Keywords: spam NaiveBayes C4.5 Decision Tree SVM

1 引言

Internet 的问世带来了电子邮件业务的出现，网络技术的飞速发展促进了邮件服务的广泛普及及繁荣，电子邮件已经成为生活在信息时代的人们日常生活一个重要部分。电子邮件不仅是一个信息交流的重要渠道，而且也是人们信息获取的重要途径之一。随着互联网的普及，不仅人们的日常事务可以通过电子邮件来进行处理，而且越来越多正式和重要的信息也通过电子邮件来进行传达和交流。

随着电子邮件越来越普及和重要性的持续增长，一些商家和不法分子开始利用垃圾邮件这种方式来进行广告信息的传播和用户消费行为信息的获取。根据无线服务机构Wireless Services Corporation 公司提供

的一份最新调查显示，目前美国移动通信市场上所有的电子邮件服务当中，43%的都是垃圾信息，而年前

垃圾邮件在电子邮件中的比例为18%。而在国内，据有关部门统计，国内的电子邮件用户，平均每天发送

的短信数量超过了 3 亿条。邮件甚至被称为继报纸、广播、电视、网络之后的第五媒体。不过在数量庞大的电子邮件背后，垃圾邮件的问题也愈加严重。

垃圾邮件可以说是因特网带给人类最具争议性的副产品之一，它的泛滥已经使整个因特网不堪重负，人们不得不花费大量时间来对付邮箱里的垃圾邮件。在这样的情势下，制定切实可行的反垃圾邮件方案无疑是Internet 的一个重要课题，而对于反垃圾邮件技术的研究也称为一个新的热点领域。本文根据现有邮件分类的知识，结合训练数据集的特点，选择合适的分类算法，来实现对垃圾邮件的分类。

2 相关工作本文垃圾邮件的分类工作主要包括以下三个部分：文本数据预处理，数据集特征选择，分类算法的应用及结果分析。

2.1 文本数据预处理

根据提供的训练数据集及测试数据集，编写程序，提取数据集中所有单词及对应的频率，并更改数据格式，以矩阵的形式存储。初步处理过后的训练数据集Pre-train1.csv 第一行表示数据集中出现的所有单词、字母和数字属性共1000 个，第2-9001 行代表之前的9000 条邮件训练数据集，对应第一行的单词，存储了

每个单词出现的频率。Pre-train1.csv 最后一列添加了label 标签，表明每一条数据的属性，ham 或spam。在

Pre-train1.csv 的基础上，我们开始对数据集中的属性进行筛选，去掉统计出来的单个字母，纯数字，以及无意义词汇属性143 条，得到最终的数据集Pre-train2.csv 共包含857 个可靠单词属性，如图 1 所示，基于

Pre-train2.csv 数据集，我们进行后续的特征提取。

1

2.2 特征提取

2.2.1 熵与信息增益

熵是信息理论中一个非常重要的概念，表示任何一种能量在空间中分布的均匀程度，能量分布越均匀，越不确定，熵就越大。Shannon 将熵应有于信息处理，提出了“信息熵”的概念。信息熵是信息的量化度量，是衡量一个随机变量取值的不确定性程度令X 为随机变量，如果X 随机变量的变化越多，通过它获取的信息量就越大，X 的信息熵定义为：

H(X) p(x i)lb(p(x i)) (2-1)

i

通过观察随机变量Y 获得的关于随机变量X 的信息熵定义为：

H(X |Y) p(y i) p(x i | y i )lb( p( x i |y j)) (2-2)

ji

信息增益是信息熵的差，表示在消除不确定性后获得的信息量，定义为：

IG(X,Y) H(X) H(X |Y) (2-3)

信息增益是信息论中的一个重要概念，被广泛应用在机器学习领域。对分类系统来说，计算信息增益是针对一个一个的特征项而言的，它通过统计某一个特征项t 在类别 C 中出现与否的文档数来计算特征项t 对类别 C 的信息增益[1]，定义为考虑出现前后的信息熵之差，某个特征项的信息增益值越大，表示其贡献越大，对分类也越重要。因此，在进行特征选择时，通常选取信息增益值大的若干个单词构造文本的特征向量。

本文中，训练数据集中有857 个属性，全部参与训练效率过低，因此需要提取出有代表性的词汇，故选用信息增益的方式来从数据集中提取特征。将处理过后的训练数据集导入到WEKA 软件中，并在预处理阶段使用AttributeSelection 界面中InfoGainAttributeEval 来进行信息增益特征提取，同时，将提取出来的特征属性按信息增益由高到低进行排列，结果如图 2 所示：

图 2 信息增益特征提取结果 根据特征提取结果，选择信息增

益排列前 400 的单词作为最终的训练集，并生成 Pre-train(3).arff 数据 集文件。 3 算法实验与分析

实验部分采用自主程序设计和 WEKA 数据挖掘工具相结合的方法，利用经过预处理的训练集，编写 MA TLAB 程序进行垃圾邮件分类，同时，利用 WEKA 软件中提供的多种常用的分类算法，进行实验。最

后对各种分类方法的优劣进行总结。

3.1 朴素贝叶斯算法

朴素贝叶斯分类器 [2]

是一种有监督的学习方法， 其假设属性的值对给定类的影响而独立于其他属性值。 用贝叶斯网表达朴素贝叶斯的分类器如图 3 所示。

朴素贝叶斯后验概率 [3]

的计算公式如式( 3-1)

P(C c k | X x) P(X x|C c k )P(C c k ) (3-1)

P(X x)

其中 X 表示单词序列， C 表示分类。其中 P(X x|C c k

)的计算公式如式( 3-2) P(X x|C c k )

P(X i x i |C c k ) i

(3-2) 则分类结果 C 的选择方式为式( 3-3)

C argmax (P(C c i | X x))

i 实验部分使用两种方法来实现贝叶斯分类算法，分

别是

NaiveBayes 算法。 MA TLAB 程序中， 根据朴素贝叶斯公式， 使用经过预处理的 4000 条数据作为训练集， 实MATLAB 编写程序和 (3-3) WEKA 平台提供的

所示：

在WEKA 件中，使用9000 条数据，400 条属性作为训练集，在Classify 条目下选择NaiveBayes 分类算法，并选择Supplied test set 作为训练模型评价方法，实验结果如表 2 所示：

表 2 基于weka 平台的朴素贝叶斯分类算法实验结果

ham spam total

ham 169 51 420

spam 61 519 580

total 230 570 1000

3.2 C

4.5 决策算法

C4.5 算法是目前最具影响的决策树算法, 已广泛应用于数据分类领域，C4.5算法是在ID3 算法的基础上改进过来的，不仅可以处理离散型描述属性，还可以处理连续性属性。C4.5 算法采用信息增益率作为选择分枝属性的标准，弥补了ID3 算法在使用信息增益选择分枝属性时偏向于取值较多的属性的缺陷。

作为ID3 算法的改进算法，C4.5 算法克服了ID3 算法的两大缺点：

(1)ID3 算法使用信息增益作为评价标准来选择根节点和各内部节点中的分枝属性，信息增益的缺点是倾向于选择取值较多的属性，在某些情况下这类属性可能不会提供太多有价值的信息，而C4.5 算法采用信息增益率作为评价标准，克服了ID3 算法的这点不足；

(2)(2) ID3 算法只能处理描述属性为离散的数据集，而C4.5 算法既可以处理离散型描述性，又可以处理连续型描述属性。

C4.5 算法也是一种基于信息论的机器学习方法，其核心思想是通过分析训练数据集，在整个数据集上递归地建立一个决策树。

使用WEKA数据挖掘软件提供的C4.5 算法进行分类，实验结果如表 3 所示

表 3 C4.5 决策树算法实验结果

ham spam total ham 411 9 420

spam 11 569 580

total 422 578 1000

3.3 支持向量机算法

支持向量机算法简称SVM( Support Vector Machine )算法[4]，该算法建立在统计学习理论中的VC 维和结构风险最小化基础之上，并结合最优化理论来得到分类决策函数的分类算法。其基本思想是寻找一个分类超平面，将两类样本分到超平面的两侧他在解决非线性问题、高维模式识别问题等许多问题中显示出许多优势，是统计学习理论中比较实用的算法之一，目前已在人脸

识别、手写数字识别、文本分类[5]、信息检索等领域得到成功应用。

支持向量机的数学模型如式（ 3-4 ）和式（ 3-5 ），该模型保证在满足条件下，超平面距离各样本点距

s.t .y i (w T

x i b) 1,i

1,2,...n (3-5)

利用 WEKA 软件实现支持矢量机（ SMO ）算法的实验结果如表 4 所示

4 3.4 实验结果评价与分析

3.4.1 实验评价方法

测试邮件集合中垃圾邮件、 非垃圾邮件的数量分别是 Ns 、Nh ，垃圾邮件中正确分类和被错分的邮件数 量分别为 Nss 、 Nsh ，非垃圾邮件中被正确分类和被错误分类的邮件数量分别为 Nhh 、

Nhs ，则垃圾邮件识

别算法的性能可以根据以下几个指标进行衡量。 （ 1 ）垃圾邮件召回率 （recall ）

垃圾邮件样本集中能被算法正确分类的样本所占比例，记为 r ，定义如式（ 3-6）

可见当垃圾邮件召回率反应了算法对垃圾邮件的检测能力，该值越大说明检测能力越强，被遗漏的 邮件越少。

2 ）垃圾邮件识别准确率 （precision ）

被正确识别分类的邮件数占所有样本的比例，记为 p ，定义如式（ 3-7）

N ss N hh N s N h

准确率反应邮件被正确分类的概率，准确率越高，说明被错误分类的邮件数量就越少

3.4.2 实验结果分析

WEKA 平台的实验结果存在一定的差异， 对比

结果如表 5

min 1

w,b

3-4 )

N

ss

Nss N sh

100%

3-6)

3-7)

MATLAB 编写程序实现的朴素贝叶斯算法结果与

所示

表5 基于MATLAB的朴素贝叶斯实验结果

算法实现环境准确率

MA TLAB 0.903

WEKA 平台0.888

实验结果存在差异的原因在于MATLAB程序仅仅是单纯使用朴素贝叶斯公式来进行结果

计算，

未考虑数

据集中的噪音等因素，WEKA平台的算法包括更进一步的预处理，噪音数据去除，以及算法的优化，导致实验结果的准确率低于MATLAB程序结果。

基于WEKA平台提供的三种分类方法，对比结果如表6 所示

表 6 三种算法分类效果对比

准确度召回率执行时间支持向量机97.0% 97.8% 8.24s

C4.5 决策树98.0% 98.1% 4.12s

朴素贝叶斯88.8% 89.5% 0.87s

对比三种分类方法的实验结果，可以发现朴素贝叶斯分类算法的准确率和召回率最低，

C4.5 决策树的准确率和召回率最高，在执行时间方面，朴素贝叶斯所需的执行时间最短，支持向量机的执行时间最长。

4总结

本文介绍了对数据集样本进行预处理及特征提取的方法，并使用支持向量机、朴素贝叶斯、C4.5 决策树这三种垃圾邮件分类方法对样本集中垃圾邮件进行识别，对比分析了它们的分类效果，朴素贝叶斯方法执行效率高，但实验准确率不够理想，SVM和决策树的实验准确率较高，但执行时间较长，这三种分类算法都有各自的优势和不足。在进行垃圾邮件分类的时候，可以考虑结合三种方法的优点，更快速准确的实现垃圾邮件识别。

本文在数据预处理阶段使用信息增益来进行特征提取，可以考虑使用卡方统计量的方式来提取特征，或者两者相互结合，得到更加合理的数据集特征信息。

参考文献：

[1] 刘庆和，梁正友.一种基于信息增益的特征优化选择方法[J]. 计算机工程与应用2011 ，47

(12):130-132.

[2] M. Sahami, S. Dumais, D. Heckerman. Bayesian Approach to Filtering Junk Email[J].

AAAI Technical Report, 1998.

[3]刘文. 基于聚类算法和支持向量机算法的文本分类算法研究[D]. 江苏科技大学硕士论文，2012:03-19

[4]Joachims T. Transductive inference for text classification using support vector

machines[C]//ICML. 1999, (99): 200-209.

[5]王龙龙.基于贝叶斯算法的垃圾邮件过滤系统设计与实现[D]. 吉林大学硕士论文，2014:04-26

本文来源：https://www.bwwdw.com/article/o2c4.html