垃圾邮件新特点的关系开发

时间:2022-05-04 11:23:00

垃圾邮件新特点的关系开发

摘要:传统反垃圾邮件产品,大多是基于关键字过滤技术的。这种技术最大的缺陷就是在分词时对新出现的潜在特征词(组)识别能力较低。本文提出了一种基于关联分析的垃圾邮件潜在特征词(组)挖掘方法,能够弥补传统邮件过滤技术在文本特征项识别方面存在的不足,起到对垃圾词典进行动态更新的作用。实验表明,该方法在中英文垃圾邮件特征项挖掘方面具有很好的效果。

关键词:垃圾邮件;特征词;关联分析

1引言

随着Internet的发展,垃圾邮件的泛滥不仅浪费邮件接收者的大量时间,还极大地消耗网络传输资源、邮件服务器的存储空间,给邮件用户、网络管理员和ISP带来了无尽的烦恼。面对垃圾邮件带来的日益严重的危害,如何有效地过滤掉垃圾邮件,已成为当前计算机网络安全方面的一个新的研究热点和难点。

目前,国内外反垃圾邮件技术主要有:利用IP或域名“黑白名单”进行的邮件限制或过滤,利用以贝叶斯算法为代表的数据挖掘技术进行邮件过滤和基于关键词规则匹配的内容过滤。这些技术基本上都脱离不了“词典+匹配”的模式,其瓶颈在于垃圾邮件新词词典的编篡明显落后于形势需要。很多垃圾邮件制造者针对传统过滤技术的弱点,不断地开发出新的垃圾邮件生成技术,致使反垃圾邮件产品的性能不断下降。如:一些垃圾邮件发送者对文本中的关键词进行拆分或是变形,把“”篡改为“氵去车仑功”;一些垃圾邮件制造者将邮件中的敏感加入一些符号或标点隔开(或是英文中用相似的字母进行替换),如“☆打#造&赚%钱$新*境※界∷”、“drµg”等等。这些都致使现行的反垃圾邮件过滤系统不能有效地识别。

本文提出的新词挖掘模式,不需要词典支持,引入关联分析中的支持度、置信度等概念来筛选潜在特征词,能够自动、准确、高效地挖掘中英文垃圾邮件中的潜在特征词(组),是一项非常有意义和实用价值的研究。

2关联规则挖掘的理论前提

在垃圾邮件特征词(组)的挖掘中,文本的特征表示是挖掘工作的基础。邮件文本实际上可以看作是由众多的特征词条构成的多维信息空间。矢量空间向量模型(VectorSpaceModel,VSM)是目前应用较多且效果较好的特征表示方法之一,即用V(doc)={(t1,w1),(t2,w2),…,(tn,wn)}表示文档doc,其中:ti为词条项,wi指第i个词条在文档中的权重(这里用第i个词条出现的频率pi表示第i个词条在文档中的权重wi)。这样就把邮件文档信息的表示转化为对N维向量空间中向量表示来处理。这样就可以运用关联分析方法对表示成多维向量空间的向量进行统计分析,达到关联强规则的就是发现的垃圾邮件潜在特征词(组)。为了更好地理解本文,下面先理解几个概念。

2.1关联规则挖掘

关联分析,又称关联规则挖掘,是Agrawal于1993年首先提出的,常用于发展大量数据中项集之间的相互联系,是数据挖掘领域中的一个重要问题。现在许多学者已将关联分析应用于文本特征提取,并取得了很好的效果[1~6]。

不妨令I={i1,i2,…,im}是项的集合,D是事务的集合,D中的每个事务T是项的集合,并且TI。设A是一个I中项的集合,如果AT,则称事务T包含A。则一个关联规则是形如AB的蕴涵式,这里AI,BI,并且A∩B=Φ。关联规则AB在事务集D中的支持度(Support)是事务集中包含A和B的事务数与所有事务数之比,记为support(AB),即support(AB)=|{T∶A∪BT,T∈D}|/|D|。关联规则AB在交易集中的置信度(Confidence)是指包含A和B的事务数与包含A的事务数之比,记为confidence(AB),即confidence(AB)=|{T∶A∪BT,∈D}|/|{T∶AT,T∈D}|。

2.2几个相关概念

词条共现:对于给定的邮件D,存在一表现主题的基本单位w,使得词条TERM1,…,TERMn在w中出现,TERM1,…,TERMn在文本D共现。

词条共现规则:如果TERM1,…,TERMn满足蕴涵式TERM1,…,TERMnco(TERM1,…,TERMn),这里TERMi是词,1≤i≤n,co为词条共现操作符,则称TERM1,…,TERMn满足词条共现规则。

词条共现规则的支持度support(TERM1,…,TERMnco(TERM1,…,TERMn))是邮件文本中TERM1,…,TERMn共现的概率,即

support(TERM1,…,TERMnco(TERM1,…,TERMn))=P(TERM1∪…∪TERMn)

可表示为:

词条共现规则的置信度是当TERM1,…,TERMn出现的条件下,满足co(TERM1,…,TERMn)的条件概率,表示为:

,其中:是词TERM在文本中出现的频数,是词TERM1,…,TERMn在文本中共现的总数。

强词条共现规则:给定最小支持度阈值min_sup与最小置信度阈值min_conf,同时满足min_sup与min_conf的词条共现规则称为强词条共现规则。

3垃圾邮件特征词(组)关联挖掘的处理步骤

本文提出的邮件特征词关联规则挖掘方法,可用图1表示其处理流程。

图1垃圾邮件特征词关联挖掘处理流程图

3.1文本预处理

为了提高垃圾邮件新词(组)挖掘的召回率和准确率,本文先对邮件样本进行样本邮件的聚类分块预处理。文本聚类,就是把一个文档集分成若干称为集簇的子集,每个集簇的成员之间有较大的相似性,而集簇之间的文档具有较小的相似性。本文采用时间和文本相似度为尺度来进行文本的聚类。我们认为出现时段越吻合的两封邮件相似度越大,出现时间相近的邮件样本应属同一块;对于矢量化的两封邮件文档的相似度与两者之间的角度成反比【7,8】。这里采用夹角余弦值来表示为(定义两篇文本d1,d2∈D):

3.2词条切分,词频统计

利用机械分词方法,对所有的垃圾邮件样本进行词条切分,并对所得到的词条进行词频统计,同时采用特定规则进行降维处理,从而得到强规则的候选词条集。

①以“我”、“的”、“是”等成词能力低的高频字和“,”、“。”为标志对每封邮件样本进行断句切分。像“我”、“的”、“是”等一些功能性词,本身成词能力很弱,但出现频率很高。另外,垃圾邮件制造者无论怎样用格式符或标点隔开垃圾字眼,但总不能破坏其完整语义,使用的格式符或者标点一般都是空格、“*”、和“/”等符号,而不会使用象“,”、“。”此类明显的自然切分标志。以成词率低的高频字和“,”、“。”为断句标志,不仅可以减少计算开销,降低词条向量的维数,而且还大大提高词条过滤的准确率。对每个断句单元(w1,w2,w3,…,wn),从w1开始到wn进行(w1,w2),(w1,w2,w3),…,(w1,w2,w3,…,wn);…,(wi,wi+1),(wi,wi+1,wi+2),…,(wi,wi+1,…,wn);…,(wn)模式的切分。如:“激情影视”可切分为“激情”、“情影”、“影视”三个2字词条,“激情影”、“情影视”两个3字词条和“激情影视”一个4字词条。并分别统计所得到的词条出现频次,将在每封邮件中出现2次以上的所有词条加入潜在特征词候选词条集中。以下是部分实现代码:

②对于切分所得词条集中,如果前一词条是后一词条的子串的,例如:在所得词条集“w1,w2,w3,…,wn”中,若是wi后面紧跟词wj,记为wiwj。wiwj组成新词(组)的可信度定义为wi后出现词wj的概率:

。其中,dfij代表词wi和wj共现频次,dfi代表wi出现频次。当80%≤confidence(wiwj)时,认为两词条出现频率基本一致,去掉词条wj;当confidence(wiwj)<80%时,则认为wj和wjwj可以分别单独成词。这样可去除候选词条集中的大量冗余项。

③对聚类所得同一块的邮件切分所得词条集进行累计(前面按规则已加入频繁项集的词条不再累计),执行②中的去除冗余项,对于达到频率大于30%的词条,全部加入到频繁项集。根据金翔宇等人的研究,当文档长度增加到一定程度时(10K以上),切分词条数目不再随文档长度的增加而线性增长,基本上稳定在3000左右[9]。所以分词统计时,我们采用缓存建立词条Hash表方法加快频繁项的提取速度。

以下是部分实现代码:

StructIndexItem{

Charcc[3];//汉字,以’\0’结束

IntnOcurrence=0;//该汉字出现的次数,初始化为0

BoolbHasProcessed=false;//该汉字是否己经被处理,初始化为false

Int*pPosArray=Null;//指向存放出现位置的数组指针,初始化为空

};

IndexItemindexArray[87][94];//用87×94二维矩阵存放所有索引节点

Char*pCndSep=“我的是……”;//成词力低的高频断句标记字

Char*pAbsSep=“。,”;//“,”和“。”断句标记

ReadTextProcess(char*pText,IndexItemindexArray[87][94])

//实现将邮件文档按字索引方式读入内存

structStrItem{

char*pStr=NULL;//字串内容,初始化为空

intnFre=0;//出现频次,初始化为0

};

GetStrFre(char*pText,IndexItemindexArray[87][94],StrItem**strArray,StrItem**HeighFrestrArray)//实现机械切分及字串频次统计,对频

//次>2加入到高频字串集

DelReduItemProcess(StrItem**strArray)//实现去除冗余项功能

3.3人工选择

经过上述三步后,就可以得到候选的词条集,最后经过人工干涉进行选择和判别,得到新的垃圾邮件特征词(组)。

3.4试验结果

为了评价测试结果,这里引入召回率Recall和准确率Precision两个测试指标。其中:Precision=T/W*100%。T是被挖掘方法正确识别的变形词(组)数,W为被挖掘方法输出的总变形特征词(组)数;Recall=T/A×100%。T是被挖掘方法正确识别的变形特征词(组)数,A是邮件文档中经过变形操作的特征词(组)数。

笔者从兰州理工大学邮件服务系统获得7572封用户举报的垃圾邮件,并分成3组进行了该方法性能测试。测试结果表明:该新词自动识别模型的词条切分平均速度29828词/秒,新词挖掘召回率、准确率较高,分别达到81.5%和92.1%。当然也发现该方法对一些特征词(组)变形十分严重的邮件文档挖掘不太理想。

表1性能测试结果

邮件数目抽词速度(词/秒)变形关键词(个)识别的特征词(个)正确识别数(个)召回率准确率

一组1571279471271019379.5%92.1%

二组24642970723118917681.8%93.1%

三组35373183044637133883.2%91.1%

合计/平均757229828268220.3202.381.5%92.1%

4.结论

关联分析技术是一种具有极大应用价值的数据挖掘方法,通过寻找数据项之间的有趣联系进行知识的获取。本文介绍的垃圾邮件新特征词(组)挖掘方法同样可以用于其它领域的专业特征新词的自动识别,但是该方法很多人为制定的规则不太好把握,而且对低频率新词的识别准确率不够高。

参考文献:

[1]罗宇辉.因特网经济学未登录词计算机辅助挖掘试验.理论与探索,2005,28-5:478-481;

[2]梁刚.基于机械分词与统计学的新词识别研究.理论与探索,2005,28-5:475-477;

[3]冯长远.Web文本特征选择算法的研究.计算机应用研究2005,7:37-38;

[4]贾自艳.基于概率统计技术和规则方法的新词发现.计算机工程,2004,30-20:19-21;

[5]李宝林.用关联分析技术识别不良信息特征项的新方法.计算机工程与应用,2003,28:39-41;

[6]韩客松.无字典高频字串快速提取和统计算法研究.中文信息学报,2001.15-2:23-30;

[7]许建潮.中文web文本的特征获取与分类.计算机工程,2005,31-8:24-25;

[8]刁力力.计算文本相似度阈值的方法.清华大学学报(自然科学版),2003,43-1:108-111;

[9]金翔宇.一种中文文档的非受限无词典抽词方法.中文信息学报,2001,15-6:33-39;