一种优化黑洞覆盖的阴性选择算法*

傅龙天，徐 戈，陈滕林

(闽江学院)

0 引言

丹麦学者Jeme［1］在1974年提出了一个人工免疫模型，Forrest等［2-3］后来提出了阴性选择算法和计算机免疫学概念，从此推动了计算机免疫学的全面发展，例如Lee等［4-5］学者利用免疫学原理实现计算机病毒检测．虽然人工免疫原理在各个领域获得很大的成功，但本身仍然存在一些不足之处，例如自体耐受过程在初始阶段学习不充分，匹配规则采用固定阀值导致黑洞问题等．Watkins和 Timmis［6］对阴性选择算法(Negative Selection Algorithm)进行了并行性改造，增强了算法的并行能力;舒才良等［7］提出了在数据不完备情况下的改进算法，引入了分类器融合投票决策思想;翟宏群等［8］利用模糊思想，采用最优搜索原理对降低黑洞数量起了一定的作用;伍海波［9］通过改进成熟检测器的生成机制及改变匹配阀值，来解决成熟检测器生成效率低和容易产生黑洞问题．上述学者的各种改进措施都起到了一定的效果，但多数只考虑了问题局部，未做全局考虑，例如黑洞的产生根源不只是匹配阀值的问题，还和训练样本来源有关系．该文首先扩展训练样本来源;其次在自体耐受学习中过程引入集成学习中的Stacking算法;匹配规则调整为可变阀值．通过三个方面的改进来提高检测精度，优化黑洞覆盖空间．

1 阴性选择算法及其分析

自然界的生物经过进化大部分形成了天然的免疫机制，当抗原第一次入侵免疫系统时，生物体产生应激反应作出第一次应答，并学习完成自体耐受过程，产生免疫记忆;当抗原再次入侵时激发二次应答，识别该抗原［10］．这种学习防御机制引入计算机领域后，形成了人工免疫识别系统(AIRS)，阴性选择算法是其核心算法之一，算法描述如下:

步骤1:从系统自动随机生成初始化训练样本，形成初始的未成熟检测器，当未成熟检测器与自体集中的样本匹配，如果匹配成功则淘汰，否则存活，形成若干成熟检测器．

步骤2:经过步骤1的多次重复迭代，生成数量足够的成熟检测器．

步骤3:利用步骤2获得的成熟检测器检测待检样本，采用r-连续位匹配规则检测待检样本，如果匹配成功，则认为识别了该待检样本．

阴性选择算法从诞生到现在成功地应用到了各行各业，取得了良好的效果，但也暴露出了其不足之处，主要表现在三个方面:首先训练样本较少时生成的成熟检测器也较少，这对检测精度有很大的影响，只有在成熟检测器越来越多的情况下，检测精度才令人满意;其次未成熟检测器的来源是随机生成的，训练样本不够典型，代表性不强，这样将不可避免地产生黑洞;再次阴性选择算法采用r-连续位(r-contiguousbits)匹配规则，匹配阀值固定不变，这也是产生黑洞的重要原因．该文针对阴性选择算法的不足提出一个改进模型E-NSA，即在训练学习过程引入集成学习(Ensemble Learning)算法的Stacking算法，改善自体耐受学习过程;扩展训练样本来源，把非自体抗原加入到训练样本中，使训练样本更具代表性;把原算法的固定匹配阀值改成阀值可变，使得匹配过程更灵活，降低黑洞数量．

2 改进模型E-NSA

2．1 模型定义

Stacking算法分为两层［11］，第一层首先构造多个弱分类器，产生一个与原数据集大小相同的新数据集，用这个新数据集和一个新算法构成第二层的强分类器，然后融合．该文把自体集和非自体集作为训练样本，其形式化定义如下所示:

定义1 训练样本数据集D(其中包含了自体集和非自体抗原集中的数据样本)，作为多分类器融合算法的输入，描述如下所示:

D={(x(1)，y(1))，(x(2)，y(2))，…，(x(N)，y(N)}其中N为样本的数量

定义2 构造Stacking算法的第一层弱分类器h1，表示第t个不同的分类器，用于对训练样本数据集D进行预测分类．其中Lt函数表示通过训练样本集D的学习得到第t个分类器ht，描述如下所示:

定义3 构造矩阵Zit为Nxt的矩阵，用于计算样本x(i)对于分类器ht的分类结果，该结果可以是样本x(i)属于分类ht的概率，描述如下所示:

定义4 构造一个新数据集D'，通过定义3的循环迭代计算，可获得样本x(i)对于分类器ht的预测结果，数据集D'用于记录预测结果，描述如下所示:

定义5 构造Stacking算法的第二层强分类器h'，即利用数据集D'形成新的分类器，用于融合弱分类器的预测结果，描述如下所示:

定义6 分类器融合，即利用第二层的强分类器h'，对第一层分类器的预测结果再进行一次的预测分类，即分类器融合，描述如下所示:

定义7 匹配度，设I是长度为L的二进制字符，P和Q是长度相等的二进制字符串，描述如下所示:

其中MatchRate(P，Q)表示P和Q的匹配程度，Len(Pi，Qj)表示P在Q上相应位置上匹配的长度，Len(P)表示字符串 P的长度，当MatchRate(P，Q)的值为1是，表示P和Q完全相等，即完全匹配．

定义8 连续匹配度con_MatchRate(P，Q)，函数max(Len(Pi，Qj))表示字符串P在字符串Q上相应位置连续匹配的最大长度，描述如下所示:

定义9 字符匹配函数，Match(P，Q)表示两字符串P和Q的匹配操作函数，其中r表示匹配阀值，描述如下所示:

当匹配函数Match(P，Q)为1时表示两个字符串匹配，在匹配操作过程中，匹配阀值r是可变的，当连续匹配度大于r/len(P)时，调整ri=ri-1+1．

2．2 模型算法实现

该模型由学习训练算法和匹配算法组成，学习算法引入Stacking算法用于改善耐受过程;匹配算法目的在于调整匹配阀值，实现灵活匹配降低黑洞数量．

学习训练算法是阴性选择算法的重要组成部分，首先把自体集合非自体抗原集作为训练样本，根据式(1)循环t次构造分类器(弱分类器)，利用式(2)循环计算概率矩阵，即计算样本x(i)的分类结果;然后把分类结果构造成新的数据集D'，并构造新的分类器(强分类器);最后根据式(5)利用新构造的分类器进行融合，从而得到熟检测器．

匹配算法采用自适应模糊策略，首先根据式(6)(7)计算匹配度和连续匹配度;再根据式(8)判断是否匹配．在实际应用中，出现连续匹配时(即循环执行本算法)，匹配阀值可自动调整，即当连续匹配度大于r/len(P)时，匹配阀值调整为ri=ri-1+1．

3 仿真实验

为了验证本模型的有效性，该文做了两组实验用于比较阴性选择算法和E-NSA模型的性能，并分析实验现象．

3．1 实验环境

使用IBM服务器X3650M4 7915i31作为实验机，主要配置:CPU为Intel至强E5-2600，内存 8GB，500GB硬盘，操作系统为 Microsoft Windows2003，云平台使用 Google Compute Engine，开发工具为Visual Studio2010．为了保证实验机纯净环境，除操作系统自带软件外，不再安装其他软件．

该文选取美国哥伦比亚大学的数据测试集(2D Synthetic Data)［12］，从中选取 2000 个病毒样本作为非自体抗原集合，1500个正常程序样本作为自体集合．从自体集合随机选取500个样本，从非自体抗原集合随机抽取500个样本，共同组成训练样本集合;从病毒样本中随机选取1500个，再从正常程序样本中随机选取1000个作为待检测样本集合．

3．2 实验结果及分析

为了得到真实可靠数据，进行了两组实验，每组实验进行50次，取平均值．第一组实验从训练样本集合中随机选取200个样本，用于比较阴性选择算法和E-NSA模型的检测率和误检率，实验结果如图1所示．

从图1(a)可以看出该文提出的E-NSA模型相对阴性选择算法检测率更高，特别是在成熟检测器数量较少时检测率的差距较大．因为ENSA模型引入了Stacking算法，改善了学习过程，并且训练样本加入了非自体抗原，使得训练样本更具有代表性，提高了检测精度阴性选择算法的斜率，随着成熟检测器数量增加斜率减小程度越来越少，说明成熟检测器的数量对检测精度的影响很大，而E-NSA模型的检测精度对成熟检测器的数量的依赖明显更小，因为其斜率变化较小．从图1(b)可以看出E-NSA模型的误检率也相对低的多．

图1 检测率和误检率比较图

第二组实验从训练样本集合中随机选取200个样本，用于比较阴性选择算法和E-NSA模型的黑洞数量，实验结果如图2所示．

图2 黑洞覆盖空间比较图

从图2可以看出E-NSA模型相对阴性选择算法黑洞覆盖空间更高一些，这是因为E-NSA模型采用了可变匹配阀值，在获得成熟检测器和样本检测这个两个过程中都有明显的优势;另外E-NSA模型扩展了学习训练样本，生成的成熟检测器更具代表性，黑洞覆盖空间自然也更高．

4 结语

针对性阴性选择算法的不足提出了一个改进模型 E-AIRS，该模型引入集成学习的Stacking算法;扩展了训练样本来源，使训练样本更具代表性，改善了训练学习过程;采用可变匹配阀值，使得黑洞覆盖空间明显提高．通过仿真实验证明E-AIRS模型相对于阴性选择算法，具备检测精度较高、误检率较低、黑洞覆盖空间更高的优势;另外本模型对训练样本的要求较低(把自体集和非自体抗原集作为训练样本)更贴近现实，增加了进一步应用推广的可能性．

［1］ Aydin I，Karakose M ，Akin E．An adaptive artificial immune system for fault classification ［J］．Journal of Intelligent Manufacturing，2012，23(5):1489-1499．

［2］ Chang S Y，Yeh T Y．An artificial immune classifier for credit scoring analysis［J］．Applied Soft Computing，2012，12(2):611-618．

［3］ Nicholas，W．，Pradeep，R．，Greg S．，Lundy，L．Artificial immune systems for the detection of credit card fraud:an architecture，prototype and preliminary results［J］．Information Systems Journal，2012，22(1):53-76．

［4］ Binh L N，Huynh T L，Pang K K．Combating Mobile Spam through Botnet Detection using Artificial Immune Systems［J］．Journal ofUniversal Computer Science，2012，18(6):750-774．

［5］ Samigulina G A．Development of decision support systems based on intellectual technology of artificial immune systems［J］．Automation and Remote Control，2012，73(2):397-403．

［6］ Watkins A，Timmis J．Exploiting parallelism inherent in AIRS，an artificial immune classifier ［EB/0L］． (2012)［2012-01］．http://www．cs．kent．ac．uk/?abw5/．

［7］ 舒才良，严宣辉，曾庆盛．不完备数据下的免疫分类算法［J］．计算机工程与应用，2012，48(20):172-176．

［8］ 翟宏群，冯茂岩．一种改进的变阈值阴性选择免疫算法［J］．南京师范大学学报:工程技术版，2011，11(3):78-82．

［9］ 伍海波．一种改进的否定选择算法在入侵检测中的应用［J］．计算机应用与软件，2013，30(2):174-176．

［10］郭蓉，姜童子，黄葵．Aβ3-10s基因疫苗免疫AD小鼠诱导Th2型免疫反应的研究［J］．中风与神经疾病杂志，2013，30(5):112-118．

［11］ 侯勇，郑雪峰．集成学习算法的研究与应用［J］．计算机工程与应用，2012，48(34):17-22．

［12］ 程春玲，柴倩，徐小龙，熊婧夷．基于免疫协作的P2P网络病毒检测模型［J］．计算机科学，2011，38(10):60-63．