二次否定选择算法  

Dual negative selection algorithm

作　　者：郑旭飞[1] 方永慧[2] 李涛[3] 

机构地区：[1]西南大学计算机与信息科学学院,重庆400715 [2]西南大学电子信息工程学院,重庆400715 [3]四川大学计算机学院,成都610065

出　　处：《中国科学：信息科学》2013年第4期529-544,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61173159;60873246);教育部重大培育基金(批准号:708075)资助项目

摘　　要：否定选择算法(NSA)是人工免疫系统应用于异常检测生成检测器的重要算法,传统NSA随机产生候选检测器与全部训练集进行耐受以消除免疫自反应,该匹配过程是NSA的主要时间开销,由于候选检测器在自体耐受过程中未考虑其与已有成熟检测器集的相互覆盖,导致生成的成熟检测器与已有检测器重复覆盖,经历不必要的自体耐受,从而导致NSA生成检测器数量过多,检测器的生成效率过低,限制了人工免疫系统在异常检测中的应用.为此,本文提出了二次否定选择算法(2-NSA),算法包括两次否定选择过程,分别耐受检测器集和训练集.每个随机产生的候选检测器先与已有成熟检测器集耐受为第一次否定选择,清除识别已有成熟检测器的候选检测器,耐受成功的候选检测器成为半成熟检测器;半成熟检测器在已有成熟检测器覆盖之外进行训练集的自体耐受为第二次否定选择,清除识别自体的半成熟检测器,耐受成功的半成熟检测器成为成熟检测器加入检测器集合.2-NSA算法有效避免了候选检测器在已有成熟检测器覆盖范围之内的自体耐受,大大减少了成熟检测器的数量,提高了成熟检测器集的生成效率,降低了算法的时间复杂度.此外,2-NSA算法按检测器半径从大到小优先产生覆盖范围更大的检测器,进一步避免与已有成熟检测器的重复覆盖,减少成熟检测器的数量.理论分析表明2-NSA算法有效减小了成熟检测器数量、提高了检测器生成效率,降低了系统的误报率.对比实验结果表明:在标准数据集Iris和期望覆盖率为99%的情况下,与经典的RNSA和V-Detector等实值否定选择算法相比,2-NSA算法需要成熟检测器的数量分别减少了99.84%和95.69%,误报率分别降低了60.13%和50.90%,产生成熟检测器集的时间代价分别缩减了99.79%和66.84%.A negative selection algorithnl （NSA） is an important method of generating artificial immune de- tectors for anomaly detection. However, traditional NSAs aim at eliminating seff-recognized invalid detectors by matching randomly generated candidate detectors with the whole self-training set. The matching process of the training set （self-tolerance） contributes the main time cost of such NSAs. The self-tolerance of these NSAs only considers the relationship between candidate detectors and the self-training set, and does not consider the candidate detectors＇ repetitive coverage with the existing detector set, which leads to unnecessary self-tolerance of candidate detectors and thus an excessive count of detectors and much lower efficiency of detector generation. In this paper, we put forward the dual negative selection algorithm （2-NSA）, which includes two negative selection processes. In the first negative selection process, each randomly generated candidate detector first tolerates with the existing detector set and becomes a semi-mature detector when it does not match with any existing mature detector in the existing detector set. In the second negative selection process, the semi-mature detector outside the mature detectors＇ coverage tolerates with the self-training set and becomes a mature detector when it does not match with any element in the self-training set. The 2-NSA avoids the time-consuming self-tolerance process of the candidate detector within the coverage of existing mature detectors, and thus greatly reduces the size of the detector set and improves detector generation efficiency. Theoretical analysis shows that 2-NSA effectively improves the efficiency of detector generation, reduces the time cost of the algorithm and reduces the false-positive rate of the detection system. The experimental results show that, for the Iris dataset and 99% expected coverage, 2-NSA has 99.84% and 95.69% fewer detectors, a 60.13% and 50.90% lower false-alarm rate, and a 99.79% and 66.84% lower time cost

关 键 词：人工免疫系统 否定选择算法 检测器 变半径检测器 二次否定选择算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]