改进动态克隆选择算法在邮件过滤中的应用研究

维普资讯

第２６卷第６期

兰州交通大学学报（自然科学版）

Ｖｏ１．２６ Ｎｏ．６

２００７年１ ２月

Ｊｏｕｒｎａｌ ｏｆ Ｌａｎｚｈｏｕ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅｓ）

Ｄｅｅ．２００７

文章编号：１００１—４３７３（２００７）０６—０１０３—０４

改进动态克隆选择算法在邮件过滤中的应用研究

麻小强， 伍忠东， 王静， 王轶群

（兰州交通大学ＦＵ子 信息工程学院，¨‘肃兰州７３００７０）

摘要：提出了可控变异和随机变异方法，改进了动态克隆选择算法，建立并实现一种改进的基于人工免疫系统的

邮件过滤算法．并采用ＳｐａｍＡｓｓａｓｓｉｎ垃圾邮件样本对算法性能进行测试．实验结果表明，引入改进的动态克隆选

择算法后，该算法对具有变异特性的垃圾邮件能保持较高的正确识别率，具有较好的自适应性和多样性．

关键词：动态克隆选择算法；垃圾邮件；人工免疫；抗原／抗体

中图分类号：ＴＰ３９３．０８ 文献标识码：Ａ

电子邮件是人们在网上进行信息交流的一种必

示，抗体与抗原具有相同的数据结构，都是等长的符

不可少的工具．但是一些垃圾、非法邮件甚至携带病 号串，它有产生、成长、进化等生理过程，相应阶段分

毒的邮件日益猖獗，困扰着人们正常使用Ｅ—ｍａｉｌ进

别称为未成熟检测器（Ｎｏｎ—Ｍａｔｕｒａｔｉｏｎ Ｄｅｔｅｃｔｏｒ）、

行通信交流．如何有效地自动过滤、删除这些有害邮

成熟检测器（Ｍａｔｕｒａｔｉｏｎ Ｄｅｔｅｃｔｏｒ）和记忆检测器

件成为一个热点问题．现有的反垃圾邮件系统大多 （Ｍｅｍｏｒｙ Ｄｅｔｅｃｔｏｒ），抗体具有属性ａｂ．ａｇｅ，表示抗

是基于概率统计的原理对邮件进行过滤，这种方法 体年龄．成熟检测器识别抗原（即检测到垃圾邮件），

需要较多的人工干预，在对垃圾邮件的多样性、变异 在计算机免疫学上叫做初次免疫应答（Ｐｒｉｍａｒｙ

性上反应较慢，缺乏自适应性和自动学习的功能．因 Ｉｍｍｕｎｅ Ｒｅｓｐｏｎｓｅ），记忆检测器识别抗原，叫做二

此，对于隐蔽性、变异能力日益增强的新型垃圾邮

次免疫应答（Ｓｅｃｏｎｄａｒｙ Ｉｍｍｕｎｅ Ｒｅｓｐｏｎｓｅ）．检测器

件，必须采用具有自适应、自学习和记忆能力的分类

识别抗原可以通过计算二者的亲和力ｆ（ｘ， ）来实

系统，而生物免疫系统［１］良好的多样性，免疫记忆、

现，亲和力的计算公式为ｆ（ｘ， ）一，．／Ｎ，其中，ｚ为

自学习、自适应和鲁棒性等特点则恰好为反垃圾邮 抗体； 为抗原；，．为二者字符串之间相同位置上相

件技术提供了一个非常重要且有意义的研究方向． 同字符的个数；Ｎ为二者字符串的字符个数．识别函

本文提出了一种全新的方法——基于改进的动态克 数ｄｅｃｔ（ａｇ）值可由下式计算．

隆选择免疫算法［２］来构建反垃圾邮件系统，并在实

ｄｆ１，ｆ（ｘ， ）≥Ａ—ｍａｔｃｈ

一 、

际环境中验证了它的优良特性．

ｅｃｔ（ａｇ 一１０＇ｏｔｈｅ ｓｅ

１基本概念定义

其中，Ａ＿ｍａｔｃｈ为激活阈值，即当ｆ（ｘ， ）≥

Ａ

—

ｍａｔｃｈ时，系统认为抗体识别了抗原．Ａ—ｍａｔｃｈ是

借用生物免疫系统（Ｂｉｏｌｏｇｉｃａｌ Ｉｍｍｕｎｅ

一

个经验值．

Ｓｙｓｔｅｍ，ＢＩＳ）中的概念，邮件样本中提取的特征向

量被定义为抗原（Ａｇ），特征向量片断被定义为基因

２ 改进动态克隆选择免疫算法

（Ｇｅｎｅ）．在人工免疫系统（Ａｒｔｉｆｉｃｉａｌ Ｉｍｍｕｎｅ ２．１ 动态克隆选择算法

Ｓｙｓｔｅｍ，ＡＩＳ）中，设问题空间记为Ｐ，垃圾邮件特征

动态克隆选择算法有如下几个步骤：

向量集合被定义为非自体Ｎ，正常邮件特征向量集

１）初始化：随机生成一个属性串（免疫细胞）的

合被定义为自体Ｓ，则有Ｓ ｎ Ｎ—Ｏ，Ｓ Ｕ Ｎ—Ｐ．

群体．２）群体循环：对每一个抗原，（１）ｙ选择那些

Ｓ和Ｎ具有相同的结构，都是符号串．在计算机免疫 与抗原具有更高亲和力的细胞进行检测；（２）变异

系统中，抗体（Ａｂ），通常用检测器（Ｄｅｔｅｃｔｏｒ）来表

产生的新免疫细胞，遗传上代免疫细胞的特性，同时

收稿日期：２００７—０４—２９

作者简介：麻小强（１９８１一），男，甘肃定西人，硕士研究生