基于否定选择变异算法的电子邮件过滤器-上海联兵环保免费电话：400-600-5030

摘　要:为提高智能邮件过滤系统的识别能力和抗欺骗能力,设计并实现了一种基于否定选择变异算法的电子邮件过滤器。其机理是应用人工免疫算法使得过滤系统具有自学习、自适应能力,同时采用双层过滤方式来提高系统过滤准确性。试验表明该过滤器在正确率、漏报率、误报率三方面具有良好的性能,达到了预期目的。
关键词:电子邮件过滤器;否定选择算法;变异
中图分类号:TP309;TP393. 098　　文献标识码:A
引言
基于内容的电子邮件过滤技术是当前的一个研究热点。文献[1, 2]等采用的贝叶斯算法以其极高的准确率在过滤技术中具有重要地位,但贝叶斯模型对于未知样本,特别是对已有样本的变异样本和利用贝叶斯模型生成的垃圾邮件样本的分类结果不佳。文献[3]采用神经网络技术来实现邮件过滤,但是这种方法有效的控制模型的复杂度和数据过拟合问题。文献[4, 5]设计了一种遗传算法和神经网络相结合的过滤器,它相对前面的几种过滤系统在各方面都有一定程度的改进,但还是没能解决对于变异样本的过滤问题。文献[6]利用克隆选择变异算法来实现垃圾邮件过滤,其结果说明基于人工免疫原理的邮件过滤器能够获得较好的过滤结果。
本文以提高邮件过滤系统的识别能力和抗欺骗能力为目标,构造了一种基于否定选择变异原理的双层邮件过滤模型。试验证明该过滤系统在准确率、漏报率、误报率方面性能良好。
1　基于否定选择变异原理的垃圾邮件过滤器
在人类免疫系统中,淋巴细胞的作用是区分“自我”和“非自我”。“自我”是指人体自身的细胞,而“非自我”是指病原体、毒性有机物和内源的突变细胞或衰老细胞。淋巴细胞能对“非自我”成分产生应答,以消除它们对机体的危害;但对“自我”成分,则不产生应答,以保持内环境动态稳定,维持机体健康。
1. 1　邮件过滤器的模型
利用人工免疫原理,将基因库生成、否定选择、遗传变异应用到邮件过滤系统中,根据它们各自的特点,改进成熟检测集的准确性,采用双层过滤模式提高邮件过滤的准确性。

本文设计的过滤器工作机理为:通过对基因库中随机生成的染色体进行否定选择,生成初始的检测集SN。设计两个自身集合S,S1,其中S用来检测随机生成的初始抗体和经过了遗传交叉变异等过程生成的新抗体是否属于自身正常细胞;S1则为一个大小为L(L不能过大)的自身集,它的作用是在过滤邮件时作为第一轮过滤时的检测集,引入的原因是:在某段时间内人们收到的邮件可能具有更多的共性,尤其是一些公函,它们的格式固定,内容也基本相近,因此,通过这么一个容量不大的自身检测集可以迅速判断出这些邮件的性质,而减少与容量大的垃圾邮件检测集进行否定选择的待过滤邮件数目。这两个自身集以及检测集SN在运行过程中也都处在自我更新状态。图1是邮件过滤器的结构。
1. 2　数据预处理
电子邮件内容特征向量是由文中提取出来的词、词组和它们在文中出现的频率构成。构成邮件特征向量的特征词汇数很多,且它们的频率值都是实数,变化范围也较大,因此,为减少计算量,加快运算速度,需要对这些数据进行编码预处理。将每个属性项的值散列到n个不同的区间,通过编码,数据全部转化为0~n -1的整数值。区间的划分是通过对训练集中样本进行统计分析获得。以UCI machine learningDatabase的SPAM E-mailDatabase中的一条邮件样本数据为例,见表1和表2。


1. 3　否定选择过程
否定选择原理为机体内先产生大量随机抗体,其中对“自我”,抗原物质产生破坏的将被清除(否则将导致自身免疫功能疾病),剩余的抗体可以检测一切外来抗原物质。在我们的系统中分阶段使用两个过程:根据保留数据挖掘出异常模式,并根据经验知识补充,以这些模式作为父代抗原,经编码后利用遗传算子对它们进行变异和增殖,生成一个大的候选抗体库,对其中每一个个体进行适应度测定,计算与现有抗原的相似度,这样做是因为假设所有新生成的个体都是以现有异常模式为基础的,而非一种不可能存在的模式,这样做有利于保障检测效率,节约存储空间;再进行否定选择,删除其中的自我模式,最后生成一个较完备的非自我模式库。否定选择算法包含两个部分:检测对象集(非自我模式库)的生成和检测。图2分别描述了这两个过程。
在进行否定选择之前,需要生成大量的随机串。这些随机串通过基因重组进行组合,形成各种不同的抗体,构成初始抗体集。这种抗体集合中不仅包含异常的染色体,也还包含正常染色体。


1.4　检测集和自身集的生成与更新
在否定选择算法中检测集生成的好坏是衡量整个算法性能的关键。将基因库中随机生成的染色体与自身集进行匹配,消除匹配者,不匹配的染色体成为成熟检测对象。在训练过程中对这些对象进行成熟度考核,通过者继续保留在检测集中,未通过者淘汰。通过不断的训练,使得检测集达到最佳状态。
在测试使用过程中,检测集是动态变化的,而且检测集的大小也是有限的,这有利于保持系统的高效性和准确性。确定一个检测集最大容量M,当检测集中抗体数目达到M时进行更新。既要保障检测集的更新能力,又要让检测集具有最佳性能,为此对SN内部的每一条检测抗体增加一个属性项用来表明该条抗体的成熟度,该属性项初值为0,每通过它检测出一个异常细胞,该值加1。根据检测集中抗体的成熟度属性项值来决定如何更新检测器。检测集更新时,将检测集中该属性值位于后n%的抗体删除,以更新检测器。
自身集S1作为过滤的第一轮检测集,它的大小必须受到严格限制,同时,作为训练检测集的自身集S也不可能为无穷大的。所以设定自身集S的大小固定为MS,自身集S1的大小为L,L小于MS,它们的更新按照LRU算法实现。
2　基于否定选择变异原理的过滤算法
生物免疫系统通过否定选择和变异过程来辨别未知抗原属于“自我”或“非自我”,在本文中则采用否定选择变异原理来实现电子邮件的分类过滤。
匹配阈值通过实验选取。定义如下记号:L:串的长度; r:匹配阈值;NS:自身数据集;NR:胜任的检测对象集;Nt:测试对象集;Pf:检测非自身失败的概率;Pm:检测一个非自身的概率。

3　实验结果
试验使用的数据来自UCImachine learning数据库,该数据库中的SPAM E-mailDatabase共提供了4 601个邮件样本,其中垃圾邮件样本1813,占整个比例为39. 4%。每条样本数据由58条属性组成,其中最后一个属性值表明样本属于正常或是垃圾邮件。57条属性全部是根据邮件文本内容特征获取的。该过滤器是针对邮件内容特征过滤方式设计的,因此完全符合试验要求。
本文设计了五组实验。每一组实验抽取3 000条样本组成训练集(其中1000条是垃圾邮件样本和2 000条是正确邮件样本),其余为测试数据集。每一组的实验数据都是对SPAM E-mailDatabase中样本的重新分组获得。实验参数中匹配阈值均为对各训练集进行实验选取获得。参数设定如表3,过滤器分类过滤结果见表4。
准确率指邮件正确分类率,误报率指将正常邮件归为垃圾邮件的邮件数目占正常邮件总数的比率,漏报率指将垃圾邮件归为正常邮件的邮件数目占垃圾邮件总数的比率。五组实验虽是对同一样本集操作,但由于每次都进行了重新分组,因此可以认为是对不同样本集的实验。这五组实验的结果以及五组实验结果的平均值清楚的说明了该过滤器具有良好的分类准确率、误报率和漏报率,并且具有较好的自适应能力和稳定性。由此说明使用这一方法实现的过滤器具有良好的过滤性能。

4　结语
本文设计的这种基于否定选择变异原理的电子邮件过滤器,作为一种基于内容过滤的过滤器,在准确率,误报率,漏报率三方面表现出了很好的性能,说明具有免疫记忆、自适应、自学习能力的过滤器的优越性。在反垃圾邮件系统中采用人工免疫原理,可使过滤系统具备更强的自适应能力和稳定性及多样性,这对于开发针对变异能力极强的垃圾邮件进行过滤的智能邮件过滤器具有较强的启发意义。

上海联兵环保科技有限公司
地址：上海市松江区工业区茸北分区茸阳路69号
总机：021-51691929
传真：021-57784244
免费电话：400-600-5030
技术支持：13641659499
E-mail：zhanglianbing@126.com
http://www.shlbhb.com