基于梯度和颜色特征的图像垃圾邮件过滤
计 算 机 工 程 第 36 卷 第16期
Vol.36 No.16 Computer Engineering ·人工智能及识别技术·
文章编号:1000—3428(2010)16—0157—04
文献标识码:A
2010年8月
August2010
中图分类号:TP391
基于梯度和颜色特征的图像垃圾邮件过滤
刘 芬,帅建梅
(中国科学技术大学自动化系,合肥 230027)
摘 要:提出以图像的梯度直方图和颜色直方图作为分类特征,分析最小二乘支持向量机(LS-SVM)算法以及该算法与传统SVM算法的区别,比较传统分类算法与LS-SVM算法的分类准确度,将LS-SVM算法用于图像垃圾邮件过滤。实验结果表明,该方法能提高图像垃圾邮件的检测率。
关键词:图像垃圾邮件;最小二乘支持向量机;支持向量机;分类特征
Image Spam Filtering Based on Gradient and Color Feature
LIU Fen, SHUAI Jian-mei
(Department of Automation, University of Science and Technology of China, Hefei 230027)
【Abstract】This paper proposes uses gradient histogram and color histogram as classification feature to analyze the difference between Least Square-Support Vector Machine(LS-SVM) algorithm and Support Vector Machine(SVM) algorithm. It compares the LS-SVM algorithm with several traditional algorithms and introduces LS-SVM algorithm into image spam filtering. Experimental results show that the method can improve the detection rate of image spam.
【Key words】image spam; Least Square-Support Vector Machine(LS-SVM); Support Vector Machine(SVM); classification feature
1 概述
垃圾邮件给人们带来了很大的经济损失和危害,自20世纪90年代以来,学者们进行了大量研究,并先后提出一些文本垃圾邮件的过滤方案。为了规避过滤机制,越来越多的垃圾邮件将目的消息嵌入到图像中,出现了图像垃圾邮件。根据赛门铁克的垃圾邮件现状报告,图像垃圾邮件量在2007年1月达到顶峰,占所有垃圾邮件的52%,随后逐渐减少,但从2008年10月起,图像垃圾邮件的比例又开始不断增加,至2009年5月初,图像垃圾邮件已占所有垃圾邮件量的20%。
图像垃圾邮件过滤方法主要包括基于光学文字识别(Optics Character Recognization, OCR)的图像文本分析、元数据分析和图像特征分析。
OCR通过扫描和摄像等光学输入方式获取纸张上的文字图像信息,利用各种模式识别算法分析文字形态特征,判断出图像所载的文字内容,并利用文本过滤器对垃圾邮件进行识别和过滤。文献[1]使用OCR提取图像中的文本,利用基于支持向量机(Support Vector Machine, SVM)算法的文本分类器识别垃圾邮件,该方法在图像中的文本没有噪音或噪音不明显的情况下实现。为了规避基于OCR的过滤,垃圾邮件发送者(spammers)在图像中使用多种混淆技术,如旋转文本、使用波形文字、增加噪声背景等。在此类情况下,OCR检测率会降低,且OCR的处理速度通常很慢。
元数据分析法使用邮件头信息和图像的元数据(如图像的帧数、每像素的比特数、图像逻辑高宽等)过滤图像垃圾邮件。该方法不需要解析邮件内容,处理速度很快,但检测率较低。
图像特征分析法使用图像相关特征过滤垃圾邮件。如对图像中的文本进行定位,利用文本区域的特征识别图像垃圾邮件。文献[2]提出基于边缘筛选的文本定位方法来定位图像
垃圾邮件中的文本区域,并给出相关文本区域特征表示,通过SVM算法验证了这些特征的分类能力。由于人眼可以容易地将正常邮件图像与垃圾邮件图像区分开,因此研究人员提出利用视觉特征来识别图像垃圾邮件的方法。视觉特征包括颜色特征、形状特征和纹理特征。文献[3]将这3种特征构成一个联合特征,使用SVM算法训练过滤器。与其他2种方法相比,图像特征分析方法的检测准确度最高。
本文提出一种基于图像梯度直方图的垃圾邮件过滤方法。利用组合分类器,克服了单个特征单个分类器分类准确度不高且容易出现过度拟合的缺点,提高了分类器的检测率。分类算法使用基于RBF(Radial Basis Function)核的最小二乘支持向量机(Least Square-Support Vector Machine, LS-SVM)算法。
2 分类特征
垃圾邮件图像在很多方面区别于正常图像,从两者之间的区别出发,研究人员已提出很多图像垃圾邮件过滤方法:
(1)通过提取图像中的文本,使用传统文本分类器过滤图像垃圾邮件。垃圾邮件图像中包含文本消息以便传递spammers的意图,虽然正常邮件图像中也可能包含文本,但这2种文本之间有很大区别,即垃圾邮件图像中的文本会包含已经被列入黑名单的词条。
(2)使用重复检测的方法来过滤图像垃圾邮件。垃圾邮件图像都是基于模板的,spammers一般会先构造一个模板,利用模板生成大量垃圾邮件图像,然后结合混淆技术对图像做较小的改动,而在人眼看来,大部分垃圾邮件图像都是较相
基金项目:国家“863”计划基金资助项目(2006AA01Z449)
作者简介:刘 芬(1984-),女,硕士研究生,主研方向:模式识别,信息安全;帅建梅,高级工程师
收稿日期:2010-03-25 E-mail:[email protected]
—157—
似的。
(3)检测图像中使用的混淆技术。垃圾邮件图像从外观上看基本相似但又各不相同,因为spammers在图像中增加了随机噪音,如果能找到用来衡量垃圾邮件图像中噪音的物理量,就可以用该物理量将这2种图像区别开。在精神物理学中,使用周长复杂度(perimetric complexity)来衡量一幅图像对人类而言的复杂程度,该参数定义为图像中黑白像素之间边界的平方除以黑像素所占面积。文献[4]指出垃圾邮件图像与正常邮件图像周长复杂度取值位于不同的范围之内,并提出利用该参数来检测不同类型的噪音。
(4)视觉特征过滤图像垃圾邮件。垃圾邮件图像与自然图像相比有突出的对象且颜色分布不均匀,针对此类特点可以使用视觉特征对邮件进行分类。
本文根据垃圾邮件图像中包含突出的文字对象以及颜色分布不均匀等特点选择梯度直方图和颜色直方图作为分类 特征。
2.1 梯度特征
图像垃圾邮件将所要传递的目的消息都包含在图像中。
这些图像一般都包含较突出为了准确传达spammers的意图,
的文字对象。图1为垃圾邮件图像,其中包含大量文字信息,虽然该图像中也使用了混淆技术,但文字对象与背景之间仍然有很强的对比度。图2是正常邮件图像。从视觉分析上来看,垃圾邮件图像中的突出对象是由于图像中的背景与文本之间有较明显的灰度差而导致,在数字图像处理中,图像灰度的变化是通过梯度值来反映的,因此可以通过统计图像的梯度特征来识别图像垃圾邮件。
理加入了随机噪音,因此本文选择Sobel算子计算图像梯度。
图像f(x, y)在(x, y)点处的梯度定义为如下向量:
⎡∂f⎤
⎡Gx⎤⎢∂x⎥
∇f=⎢⎥=⎢⎥ (1)
⎣Gy⎦⎢∂f⎥
⎢∂y⎥⎣⎦
根据向量分析可知,梯度向量指向在坐标(x, y)处的f的最大变化率方向,而梯度向量的模值则是指(x, y)处的最大变化率,通常都将该模值称为梯度。本文通过计算梯度向量模值的统计直方图来识别图像垃圾邮件。
梯度向量的模值定义为
22
mag(∇f)=⎡⎣Gx+Gy⎤⎦
2
(2)
Sobel算子用来计算Gx、Gy,将原始图像转换成灰度图像。首先利用Sobel算子构造2个3×3的滤波器,一个突出水平边缘,另一个突出垂直边缘,用2个滤波器分别获得Gx、
Gy。式(1)所示梯度的计算包含了平方和以及开方运算,计
算量非常大,所以,本文使用一种简化的近似计算,即
mag(∇f)=Gx+Gy (3)
对于获得的梯度图像,统计其D维梯度直方图,将归一化的直方图作为图像的特征向量,图3、图4分别是图1、 图2的32维的梯度直方图。
图3 垃圾邮件图像梯度直方图
图1 垃圾邮件图像
图2 正常邮件图像
图4 正常邮件图像梯度直方图
从图3和图4可以看出,正常邮件图像的梯度直方图分布较均匀,反映到视觉上就是正常邮件图像的灰度变化较平滑,而垃圾邮件图像由于包含突出的对象,因此灰度变化较剧烈,且相当一部分灰度值在垃圾邮件图像中可以忽略。
为了获取图像的梯度特征,首先需要获取原始图像的梯度图像。计算梯度时最常用的算子是Prewitt算子和Sobel算子,Prewitt算子实现起来较简单,但Sobel算子在噪声抑制方面优于Prewitt算子。由于很多垃圾邮件图像都经过混淆处 — —158
2.2 颜色特征
颜色直方图被广泛应用在基于内容的图像检索中,这种方法效率高,且对于视点的细微变化不敏感。垃圾邮件图像是由spammers利用计算机构造得到的,与自然图像不同,这些人造图像颜色分布较单一。基于颜色直方图的优点以及垃圾邮件中的图像具有上述特殊性,因此本文提出将图像的RGB颜色直方图作为分类特征,图5和图6分别给出了图1和图2的32维RGB直方图。
其中,αi为Lagrange乘子;α∗i为非零的Lagrange乘子(由于标准SVM是一个在不等式约束下的二次函数寻优问题,
∗因此存在唯一解且只有一小部分αi不为零,记作α∗i);b为
分类阈值。
标准SVM算法可以很好地解决非线性分类和回归问题,
文献[5]但对QP(Quadratic Programs)问题可能会得到稀疏解,
对标准SVM分类器做了改进,获得的算法可以处理线性方程,这一改进为很多研究领域提供了便利,改进的LS-SVM分类器描述如下:
T
f(x)=sgn⎡⎣ωϕ(x)+b⎤⎦ (6)
其约束条件为
T
k=1,2,",N (7) yk⎡⎣ωϕ(xk)+b⎤⎦=1−ek,
其中,ϕ(⋅):Rn→Rnh类似于标准SVM中的特征向高维空间的映射。
以线性分类为例,使用LS-SVM算法可以很容易地解决初始化问题,但由于ω通常是无穷维,因此需要给出LS-SVM非线性分类器表达式的对偶问题,建立该问题的拉格朗日方程,通过求解方程可以得到在原始特征空间的对偶空间中的分类器:
图5 垃圾邮件图像RGB直方图
N
f(x)=sgn⎡∑αkykK(x,xk)+b⎤ (8)
⎢⎥⎣k=1⎦
其中,K(x,xk)=ϕ(x)Tϕ(xk)。
根据上述介绍可知,LS-SVM与标准SVM相同,因此,
可选的核函数也有4种。在二分类问题上使用径向基函数获得的分类器性能优于其他核函数,且LS-SVM的平均分类准确度高于标准SVM。两者分类结果的ROC曲线分别如图7和图8所示,分类特征是图像64维梯度特征。
图6 正常邮件图像RGB直方图
图7 SVM算法ROC曲线
通过图5和图6的比较可以看出,正常图像的颜色较丰富,而垃圾邮件图像的直方图只是集中在几种颜色上。本文使用的视觉特征是归一化的RGB统计直方图。
3 LS-SVM算法
标准SVM算法的主要思想可以概括为2点:(1)针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化到高维输入空间使其线性可分,从而使得在高维特征空间中采用线性算法对样本的非线性特征进行线性分析成为可能;(2)基于结构风险最小化理论,在特征空间中构造最优分割超平面,使学习器得到全局最优化,并使整个样本空间的期望风险以某个概率满足一定上界。
标准SVM分类器描述如下:
∗ (4) f(x)=sgn{∑α∗iyiK(xi,x)+b}
i=1n
图8 LS-SVM算法ROC曲线
其约束条件为
i=1
i=1,2,",n (5) ∑yiαi=0, 0,αi≥
n
图7中ROC曲线下的面积为50%,说明此时SVM分类
器基本不能区分正常邮件和垃圾邮件,而LS-SVM分类器可以识别部分垃圾邮件。使用其他特征同样会发现LS-SVM算法训练得到的分类器性能优于SVM分类器。
对64维梯度特征降维,并分别使用LS-SVM、SVM、RBF-Network、ID3、Winnow分类算法,比较它们的分类准确度,统计结果如表1所示。
—159—
表1 不同算法错误率比较
算法 错误率/(%)
RBF-Network 41
SVM 34 ID3 33 Winnow 68 LS-SVM 33
而越低,且误报率也在降低。基于垃圾邮件过滤的特点,本文选择64维梯度直方图和64维颜色直方图作为分类特征,并对提取的特征进行特征选择,用最终获得的特征训练2个分类器,对分类结果用“或(OR)”组合,最终的分类性能见图9。
从表1可以看出,在常用的分类算法中,Winnow算法
的识别率最低, LS-SVM和ID3的识别率相当,其次是SVM和RBF-Network。如果能改进特征,训练多个分类器就可以提高分类的准确度,达到比较好的分类效果。
4 实验
本文使用的图像包括Dredze收集的spam图像和ham图像以及来自SpamArchive的垃圾邮件图片集,选择了其中的4 478幅图像。
先为基于RBF核的LS-SVM分类器确定相应的参数,将实验数据分为2个集合:训练集(40%),验证集(60%)。训练集用于训练LS-SVM分类器,选取性能最好的参数用于最终的分类,验证集用于交叉验证,本文使用5折交叉验证。
判断一个分类算法的分类效果必须有统一的标准,通常使用误报率、漏报率、准确率、精确率等。
FP
误报率:FP Rate=。
FP+TNTP
准确率:TP Rate=。
TP+FN
TP+TN
精确率:Accuracy=。
TP+TN+FP+FN
图9 组合分类器ROC曲线
从图9可以看出,分类准确度可以达到97.44%,误报率为5.29%,且此时ROC曲线下的面积达96.079%,分类效果较好。
5 结束语
图像垃圾邮件是垃圾邮件的一个变种,在垃圾邮件中占有很大比例,但目前图像垃圾邮件的识别率不高。因此,本文使用了具有良好区分能力的特征,并用LS-SVM算法验证其有效性。
参考文献
[1] Fumera G, Pillai I, Roli F. Spam Filtering Based on the Analysis of
Text Information Embedded into Images[J]. Journal of Machine Learning Research, 2006, 7: 2699-2720.
[2] 耿 技, 万明成, 程红蓉, 等. 基于文本区域特征的图像型垃圾
邮件过滤算法[J]. 计算机应用, 2008, 28(8): 1904-1906.
[3] Bhaskar M, Saurabh N, Manish G, et al. Detecting Image Spam
Using Visual Features and Near Duplicate Detection[C]// Proceedings of the 17th International Conference on World Wide Web. Beijing, China: [s. n.], 2008: 497-506.
[4] Biggio B, Fumera G, Pillai I, et al. Image Spam Filtering by Content
Obscuring Detection[C]//Proc. of the 4th Conference on Email and Anti-spam. California, USA: [s. n.], 2007: 2-3.
[5] Suykens J A K, Gestel T Y, Brabanter J D, et al. Least Square
Support Vector Machines[M]. Singapore: World Scientific Publishing Co., Pte. Ltd, 2002.
由于邮件服务的特殊性,在垃圾邮件识别中,用户可以忍受自己的收件箱中有少量垃圾邮件,但不能接受其正常邮件被过滤器误判为垃圾邮件,因此垃圾邮件检测对误报率的要求较严格,即要求在误报率很低的情况下提高检测的准确率和精确率。
对同样的特征维数,不同分类的结果会大不相同,表2是不同维数的特征分类结果的比较,其中,Area表示ROC曲线下的面积,曲线下的面积越大通常说明分类效果越好。
表2 不同特征的比较
特征 128维梯度 64维梯度 32维梯度 128维颜色 64维颜色 32维颜色
FP Rate 0.003 2 0.018 3 0.019 4 0.119 7 0.146 7 0.138 1
TP Rate 0.819 4 0.847 8 0.901 8 0.837 0 0.829 1 0.860 3
Area 0.913 29 0.923 37 0.928 78 0.858 64 0.841 18 0.861 11
从表2可以看出,特征维数越高分类准确率和精确率反
编辑 陈 晖
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(上接第153页)
参考文献 技术[J]. 计算机应用, 2008, 28(2): 535-537.
[1] Oehlert P. Violating Assumptions with Fuzzing[J]. IEEE Security &
Privacy, 2005, 3(2): 58-62.
[2] 刘 坤. 结合逆向工程和Fuzz技术的Windows软件漏洞挖掘模
型研究[J]. 成都信息工程学院学报, 2008, 23(2): 178-181. [3] 任春钰, 舒 辉, 瞿 进. 一种改进的针对复合文档的Fuzz测试
[4] Adobe Systems Inc. PDF Reference[EB/OL]. (2008-04-15). http://
www.adobe.com/devnet/pdf/pdfs/PDFReference13.pdf.
[5] CVE. CVE安全公告[EB/OL]. (2009-03-24). http://cve.mitre.org/
cve/index.html.
编辑 任吉慧
— —160