改进的变长检测器产生算法

1 概述

负选择算法是人工免疫系统的主要算法之一，已经在不同的领域，尤其是异常检测领域得到了广泛的应用。

负选择算法一般由2个阶段组成。首先是检测器集的生成，在此阶段，凡是匹配自体的样本全部被抛弃；然后是使用检测器集对新样本的检查，此时与检测器匹配的样本即为非自体。

由此可见，检测器集的好坏直接影响检测结果。如何更有效地生成检测器一直是一个研究热点[1-2]。

文献[3]提出了随机的实值负选择算法，使用定长检测器半径；由于很难准确估计检测器的半径，导致检测率不高；文献[4]提出了可变半径的负选择算法(V-detector)，提高了检测率，但通过随机产生候选检测器，检测器的成熟效率较低，影响了检测性能。

基于此，本文提出一种改进的检测器生成算法，使用检测器的覆盖率估计值作为算法结束运行的控制参数，减少了直接设定运行次数可能带来的检测器覆盖率不高的问题；并采用随机生成和基因库结合的候选检测器生成机制，既保证了检测器的多样性，也提高了检测器的成熟效率。理论分析和实验结果表明：本文算法减少了所需的检测器数量，提高了检测率，整体检测性能得到了提高。

2 算法基本步骤和分析

2.1 算法基本步骤

算法基本步骤如下：

步骤 1 产生候选检测器x(这里采用从基因库产生[5]和随机产生相结合的方式)。

步骤 2 计算x与检测器集合中已有的检测器di(i=1,2,…,n)的欧氏距离

步骤3 如果距离Ldi 小于检测器di的半径r( di)，说明点x已经被检测器覆盖，则计数器t=t+1；否则转步骤5。

步骤4 如果t≥1/(1−a)，则说明覆盖率已经足够，结束算法；否则，转步骤1；其中，a表示所期望的覆盖率。

步骤5 计算点x与自体样本集合S中的自体点si的欧氏距离Li =Euclidean( si, x)，x的半径r由最近的自体元素决定，取与自体不重叠的最大值。

步骤6 将(x, r)作为新的检测器加入到检测器集合D。

步骤 7 如果检测器集合达到最大检测器数量Nmax，则结束；否则，转步骤1。

2.2 算法优势分析

算法优势分析如下：

(1)与文献[3]相比，本文算法中由于每个检测器的半径可变，算法具有更好覆盖检测“黑洞”的能力。

(2)与文献[4]相比，本文算法在候选检测器的选取上，提出了采用随机生成和基因库相结合的方式。随机选取方式保证了检测器的多样性，基于基因库的生成方式提高了检测器的生成效率。检测器生成效率的提高，进一步使检测率得到提高。

(3)本文算法采用集成了点估计的覆盖率估计方法作为算法的终止条件，而不是简单决定于预设的检测器最大数量，可以有效避免冗余检测器的生成。

2.3 算法基本流程

算法基本流程如图1所示。

图1 算法基本流程

3 实验和结果分析

为了验证算法的性能，在合成数据和真实数据上均进行了实验验证[8-9]，并与相关算法作了比较。

3.1 使用合成数据的实验

用合成的二维数据集来验证本文算法，采用交叉的自体区域[4]。训练数据和测试数据分别是 200个随机选取的自体点和1 000个随机分布的数据点(包括自体和非自体)。进行了100次重复实验作为最终的实验结果。检测性能使用检测率(detection rate)和虚警率(false alarm rate)以及所需的检测器数量来衡量[4-6]。由于自体半径和覆盖率都对算法性能有较大影响，本实验测试了其对检测结果的影响。实验结果得知：自体半径越小，检测率越高，但虚警率也越高；当自体半径较大时，检测率和虚警率都较低。因此，必须根据实际情况，选择合适的自体半径。同时，在自体半径相同的情况下，期望的覆盖率值越大，检测率越高；但虚警率也越高。自体半径和期望覆盖率对所需检测器数量的影响如下：当自体半径过小时，需要的检测器数量较多；期望的覆盖率越高，所需的检测器数量越多。经过比较，选择自体半径在0.1，覆盖率为99%作为最终参数，此时得到比较满意的结果。

3.2 在真实数据上的实验结果

为了验证此算法的性能，同时使用著名的Fisher’s Iris数据集与其他相关算法作了比较[9]。实验时，一种数据被作为正常数据，其他2种作为异常数据。正常数据用来训练系统。其中，Setosa 50%表示：Setosa被认为正常数据，其他2种类型(versicolor and virgnica)被当作异常数据，50%的Setosa数据被当作训练数据，所有3种类型的数据(包括已经作为训练数据)作为测试数据。与其他算法设置相同的实验参数，以便进行比较。实验结果如表1所示。从表中可以看出，本文算法与RNSA相比[3]，检测率相当，但虚警率较低。另一个较大优势是，需要的检测器数量较少，可有效提高检测效率。与 V-detector算法相比[4]，本文算法检测率较高，主要原因在于：采用随机生成和基因库相结合的方式，减少了与自体样本重叠的概率，提高了检测率；但同时虚警率也稍有上升，原因在于：检测器和自体空间比较接近，落在自体和非自体边界上的检测器概率增加。同时，本文算法使用覆盖率估计减少了冗余检测器的产生，所需的检测器数量减少。因此，本文算法有一定的优越性。

表1 相关算法检测性能比较(Iris数据集)

4 结束语

本文提出了一种改进的实值负选择算法。采用随机生成和基因库相结合的候选检测器生成机制，从而提高了检测率，并集成覆盖率评估作为算法的结束条件，减少了冗余检测器的生成。实验结果表明了本文算法的有效性。在实际使用中，具体参数的取值依赖于具体的应用问题。下一步的研究工作主要是：如何自动地决定这些参数，比如自体半径、覆盖率等。