APP下载

融合AHP和贝叶斯算法的邮件过滤模型

2015-08-08李苑曾莉

电脑知识与技术 2015年15期

李苑 曾莉

摘要:在大数据时代的背景下,电子邮件给人们带来了前所未有的机遇与挑战。该文对现有的垃圾邮件过滤系统进行了补充。基于AHP方法的多级检索与建立在贝叶斯算法之上的词库匹配,由逐级检索的量化结果综合判定其是否为垃圾邮件。该文提出的基于贝叶斯算法建立的多级检索模型具有定量分析与定性分析相结合的优点。该模型为垃圾邮件过滤系统的完善提供了新思路。

关键词:AHP分层分析;多级检索;贝叶斯算法

中图分类号:TP18 文献标识码:A 文章编号:1009-3044(2015)15-0158-03

Abstract: E-mail brings unprecedented chances and challenges with the development of big data.This thesis supplements the existing filtering spam system. The multistage retrieval based on AHP matches with the lexicon of affixes and words which is built up by Bayesian algorithm. Then we decide whether it is spam by the quantitative results of stepwise retrieval. The layered retrieval model based on Bayesian algorithm has an advantage of combination between quantitative and qualitative analysis. This model provides a new idea for improving the filtering spam system.

Key words: Analytic Hierarchy Process(AHP);Multistage Retrieval;Bayesian Algorithm

电子邮件是指用电子手段传输信息,其中包括了信件、数据、图片等内容,随着用户的需求不断增加,大量的电子邮件涌现。电子邮件是在网络上备受喜爱的一种沟通方式,由于接受者和发送者都是人,所以人们更期望达到人性化的服务方式。在虚拟网络世界中的电子邮件的工作方式与现实生活中的邮寄包裹快递的方式十分相似,电子邮件服务由专门的服务器系统提供。

如今电子邮件发展迅猛,给我们带来机遇的同时也带来了挑战。垃圾邮件的出现给人们带来了巨大的困扰。其中可能包含木马病毒、盗取信息、广告等内容,因此人们对于此类邮件的处理十分关注。垃圾邮件的危害不言而喻,占用网速拉低有效信息的传输效率;木马病毒降低电脑中信息安全性,这一系列的问题都亟待解决[1]。本文建立的邮件过滤模型可以将邮件进行多级检索与建立的词库匹配,判定是否为垃圾邮件[2]。

1相关理论

1.1 AHP分层分析

层次分析法是在20世纪70年代中期时被提出的,是一种定性和定量分析相结合的层次化、系统化的分析方法。在处理较为复杂得多决策问题上的实用性较高。AHP通过分析复杂问题包含的因素及其相互联系,将问题分解为不同要素,并将这些要素归并为不同的层次,从而形成多层次结构,在每一层次上可按照某一规定准则,对该层要素进行逐对比较,建立判断矩阵,通过计算判断矩阵的最大特征值和对应的正交化向量,得出该层要素对于该项准则的权重,在这个基础上计算出各层次要素对于总体目标的组合权重。从而得出不同设想方案中的权值,为最终结果提供可靠依据[3]。

1.2贝叶斯过滤技术

贝叶斯分类算法是基于概率统计原理的一种分类方法,它具有简单、运算速度快、分类精度高的优点,被广泛地应用在反垃圾邮件的产品中[4]。使用贝叶斯统计分析,需要初始化其数据库。根据需求收集适合系统的垃圾邮件和正常邮件词汇集,通过“贝叶斯数据库初始化”功能进行贝叶斯数据初始化。通过“白名单”降低误报率,“黑名单”降低漏过率。两种方法较为有效但仍存在不足,使垃圾邮件过滤达不到令人满意的效果。垃圾邮件发送者为躲避过滤技术的过滤,不断更新策略使垃圾邮件层出不穷。基于概率统计的过滤技术可以自动适应垃圾邮件的变化。对邮件的内容特征进行提取并制定规则,或是计算该特征出现的概率来确定邮件是否是垃圾邮件。但基于内容的垃圾邮件过滤方法要随着垃圾邮件的特征改变,重新设定或再次训练来适应垃圾邮件新策略。贝叶斯算法提供了推理的一种概率手段,是一种后验概率。它是基于如下假定,即待考察的数据的量遵循某种概率分布,且可根据这些概率及已观察到的数据进行推理。

2邮件过滤模型建立

2.1多级检索模型

在英文邮件过滤的过程中对于建立一个适当的数学模型是十分必要的。由于每个英文单词是由空格或者标点符号进行划分的,较容易区分单词所在位置同时减少了关于语义的歧义性。在英文中单词有两大基本部分组成:词缀和词根。一般单词均符合这样的构成,在记忆单词时经常根据相应的前缀和后缀进行。在构词法中词缀均代表一定的含义,例如“un”表示“不、无、非、没有”等意思。因此对于任意某一个单词可根据相应的前缀或后缀进行词义的大概猜测,同样也可以根据这个方法对单词进行初步划分。即根据词缀对文本中的单词进行初步检索,将此过程的检索结果作为二级检索基础。

为提高检索速度,可从开头和结尾两部分同时对全文检索,分别针对前缀和后缀。将对于前缀和后缀检索设为一级检索。本次检索得到的结果将作为下一级检索的重要基础。经过一级词缀检索后的单词在相对应的词缀下重新进行检索为二级检索。由于单词的自然划分可以减少对于单词的歧义划分等。多级检索模型是基于AHP分层分析方法进行改进而建立的。待检索的文本为系统,文本中的各个单词是最小的要素,词缀和单词为所划分的层次。在完整的系统下,建立不同的层次划分可以得到相应的矩阵以及各要素的权重。通过权重可显示该单词出现的时候,文本为垃圾邮件的可能性大小。将具体的量化判定是否为垃圾邮件的过程。该模型也可对用其他方法分类处理的邮件进行检查,验证已使用的方法是否判定准确。

2.2贝叶斯后验概率方法建立词库

邮件过滤模型需重新建立词库,本文采用改进后的贝叶斯算法建立。具体建立步骤如下:

1) 统计并整理已分类的电子邮件,分别统计垃圾邮件与正常邮件的英文文本中所含单词总数[S]、[N]。

2) 将邮件中的单词按词缀分类整理统计词缀首字母为[a,b,...,z]的单词总数,按照数量由多到少的顺序建立hashtable_spam哈希表与hashtable_normal哈希表[10]。

3) 统计垃圾邮件与正常邮件中各词缀所含单词总数,计算出各词缀在垃圾邮件、正常邮件中的概率。设[m1]:该词缀[wi]在垃圾邮件中所含单词总数,[M1]:垃圾邮件中单词总数[S]; [m2]:该词缀[wi]在垃圾邮件中所含单词总数,[M2]正常邮件中单词总数[N].[pi=m1M1]、[Pi=m2M2,]。按词缀在邮件中出现的概率由大到小排序并存储于树中。

4) 统计并计算在垃圾邮件、正常邮件中各单词在其所属词缀下出现的概率。设[m3]:该单词在垃圾邮件中出现的次数,[M3]:该单词所属的垃圾词缀中单词总数,[m4]:该单词在正常邮件中出现的次数,[M4]:该单词所属的正常词缀中单词总数 [qi=m3M3],[Qi=m4M4]。按单词在其所属词缀下出现的概率由大到小排序存储于树中。

5) 通过哈希表存储数据,查找根节点的地址。根据该地址进入树进行比较配对,从而得到确定的垃圾单词的概率进而推断,该邮件是垃圾邮件的概率。设[A]为垃圾邮件、[B]为正常邮件,根据整理的已分类邮件计算出垃圾邮件的概率。设[t]:垃圾邮件数目,[T]:邮件总数。[PA=tT],正常邮件的概率[P(B)=1-P(A)]。[w1,w2,...,wn]为相应的词缀,则[P(Awi)]是在邮件中出现词缀[wi]时,该邮件为垃圾邮件的条件概率[P(Awi)=pi×P(A)pi×P(A)+Pi×P(B)]。[d1,d2,...,dn]是该词缀下对应的单词,则[P(widj)]为邮件中出现单词[dj]时,该单词包含在垃圾词缀[wi]中的条件概率[P(widj)=pi×qjpi×qj+Pi×Qj]。

(6)建立新的哈希表与树:根据词缀首字母建立新的hashtable_probably哈希表,并建立新的树存储[P(Awi)]、[P(widj)]。

2.3邮件过滤系统的建立

预处理部分:对于文本的预处理可以为邮件的过滤节约较多的时间和精力。1) 过滤掉冠词、介词、连词如“the、to、and”等;2)过滤特定的标点如《》、[]、{}等;3)过滤数和其他语言; 4)将大写全部转化为小写;5)保留句号、逗号、叹号等可分割句子的标点。

多级检索部分:将接收到的邮件进行多级检索,从文本的开头和结尾同时进行,降低检索所消耗的时间,多级检索是建立在AHP基础上的。第一级检索:将统计垃圾邮件、正常邮件得到的词缀分别列成判定方阵,以各词缀的后验概率大小作为其重量并两两作比,所得比值为该词缀在本层分析中的权重。因词缀的数量是确定的,所以词缀的两两之比是确定可以得到的。第二级检索:每一个词缀下的单词分别建立单词判定矩阵,以各单词的后验概率为重量并两两作比,得到的比值为本单词在二级检索中所占权重[5]。多级检索为邮件过滤系统的建立奠定了基础。

与词库匹配部分:待检索的文本与贝叶斯算法建立的词库匹配,由于词库是配合多级检索而建立的。因此在匹配过程中同样分为两级进行。第一级匹配:词缀匹配。根据已划分的正常邮件词缀库、垃圾邮件词缀库,分别统计这些词缀在待检索的文本中出现的次数并记录。第二级匹配:单词匹配。在第一次的统计结束后,对文本中出现的词缀,统计其下所包含的每个单词的个数。两级匹配后的统计结果按照多级检索的权重进行处理,所得每一级的最终结果作为判定文本是否为垃圾邮件的标准。

结果判定部分:设计判定阈值。假设阈值为a。当计算所得结果大于阈值a时,可判定为垃圾邮件,结果小于等于a时,为正常邮件。由于阈值的确定需满足不同人群的需求,因此可以根据特定的要求修改。例如时尚杂志的推送对于服装设计师是其工作的一部分,而对科研工作者来说需求性并不大。因此要进行相关统计方可设定阈值,而不能以偏概全,忽略人群需求。

3 结束语

在电子邮件广泛应用的今天,对于垃圾邮件的处理十分关键,本文利用较为成熟的贝叶斯过滤技术建立词库,在AHP 分层分析理论的基础上建立多级检索模型。由于搜集关于个人邮件信息存在困难,因此导致所统计的概率不是十分准确。未来的工作中,首先将对邮件的搜集和概率的统计结果需做进一步的完善,将统计结果精确化。其次,对收件人的各项需求做进一步研究讨论,确立符合个人需求的邮件过滤系统。人们需不断完善邮件过滤系统,以期减少垃圾邮件给我们带来的困扰。

参考文献:

[1] 张明旺. 电子邮件安全技术探讨[J]. 计算机安全,2012(6):76-79.

[2] 郭永健,郑麟,郭杰. 大数据时代背景下的海量电子邮件分析[J]. 警察技术,2015(1):42-45.

[3] 徐涛,史开泉. 基于粗糙集理论的AHP层次分析法[J]. 三明学院学报,2006(4):416-421

[4] 王龙龙. 基于贝叶斯算法的垃圾邮件过滤系统设计与实现[D].吉林大学,2014.

[5] 史晶. 基于粗糙集和贝叶斯算法的邮件过滤系统的研究与应用[D].电子科技大学,2011.

[6] 劳兆利. 基于层次分析法与模糊综合评判法的集中运维点选择优化研究[D].上海交通大学,2007.

[7] 范彦勤. 基于贝叶斯分类器的个人信用评估研究[D].西安电子科技大学,2014.

[8] 施轶青. 监督学习下的贝叶斯分类器研究[D].西安电子科技大学,2011.

[9] 李发旭. 电子邮件病毒传播网络的建模与分析[J]. 微型电脑应用,2011(2):46-48.

[10] 朱芳芳,李训根. 改进的哈希表查找算法[J]. 杭州电子科技大学学报,2013(5):46-49.