一种使用最近邻自体耐受的否定选择算法

杨韬++邓红莉

摘要：本文提出一种采用最近邻自体耐受的否定选择算法（Nearest Neighbor Self Tolerance Negative selection algorithm， NST-NSA），该算法在通过数据预处理阶段将所有样本压缩进单位特征空间，并利用N维数组记录自体位置；在训练阶段根据候选检测器坐标在N维数组中搜索最近近邻自体进行计算。实验结果表明，想对于传统的否定选择算法NST-NSA能以更短的时间达到更高的检测率。

关键词：人工免疫 否定选择算法 检测器

中图分类号：TP274.5 文献标识码：A 文章编号：1007-9416（2014）12-0124-01

1 引言

受到生物免疫系统的启发，计算机人工免疫系统利用检测器来代替抗体，在计算机系统内来区分自体与非自体抗原。传统的否定选择算法在自体耐受阶段（消除免疫自反应），每一个新生成候选检测器要进化成为成熟检测器必须要与所有自体进行距离计算，这样的距离计算耗费了大量的时间代价极大地降低了算法的效率，限制了否定选择算法的应用。而事实上，候选检测器只要没有覆盖距离自己空间距离最近。自体样本就必然不会覆盖更远距离的自体样本，因此本文利用N维数组在预处理阶段记录下训练样本的空间信息，当候选检测器生成时根据检测器的空间信息直接在数组中查找最近邻自体来进行距离计算，这将有效地缩短计算时间提高算法效率。

2 NST-NSA实现策略

本文采用线性函数转化将所有抗原（数据样本）归一化到[0，1]n特征空间在归一化全部完成之后，根据最小归一化精度与训练数据维度，生成N维数组A用于记录训练样本的空间信息。例如样本有2维， 即N=2；在每一位上归一化后小数取值均为小数点后1位，即精度为0.1，因此空间数组应为10*10的2维数组。为了方便快速遍历，数组A中有样本点的位置将置“1”，其余位置将置“0”，当空间数组A生成后，根据候选检测器的实际位置就能够快速检索到最邻近自体距离，假设有候选检测器d（x，y），首先在根据检测器的第一位坐标在数据A中查找非零位置（可能最近邻点）， 如果没有发现根据第二维继续查找；均未发现的情况下开始近邻区域查找。

需要说明的是，虽然NST-NSA在计算前经过了多次遍历，然而这些遍历操作仅仅是简单的查找并不涵盖复杂的数值计算。特别地，若采用欧式距离公式，当样本数量M巨大，样本维度N偏高时，传统的否定选择算法将进行M*N次乘方运算，而NST-NSA最坏情况下只进行（M+N）/2次0/1比较运算，与M0*N次乘方运算，其中M0为可能近邻点数量，由于M0远小于M因此NST-NSA的时间复杂度迅速下降。同时使用NST-NSA，候选检测器仅仅被限制在了局部范围进行比较，从而有效地减少了“孔洞“，在一定程度上提高算法检测率。

3 实验设置

本节通过实验验证NST-NSA算法性能。实验数据集采用UCI标准数据集中广泛应用于模式识别与异常检测等研究的BCW数据集。为说明算法性能，NST-NSA将与经典的V-Detector算法在上述数据集上进行对比实验，实验独立重复20轮，每轮实验在两种数据集上均随机采用60%的自体样本作为训练集，余下40%的自体样本以及全部非自体样本作为测试集，相关实验结果取均值，最后用检测率DR与训练时间TR-T作为衡量算法性能的指标。

如图1所示，与V-Detector算法相比NST-NSA在相同的期望覆盖率下都能达到较高的检测率。如图2所示，当期望覆盖率上升时，否定选择选择算法需要产生更多的检测器来覆盖非自体空间，此时候选检测器数量迅速上升，因此距离运算的时间代价也随之上升。可以看出V-Detector算法在期望覆盖率增加的情况下，训练时间呈指数级增加；而NST-NSA由于事先记录了样本空间信息，每次只需要与最近邻自体进行距离运算，从而训练时间受期望覆盖率影响不大，拥有更高的计算效率。

4 结语

否定选择算法是人工免疫理论中重要的检测器生成算法，单传统的否定选择算法需要进行大量的计算才能消除候选检测器免疫自反应，巨大的时间代价限制了否定选择算法的应用。为此，本文提出了最近邻自体耐受的否定选择算法，在预处理阶段利用N维数组来记录训练样本的空间信息，在训练阶段可以帮助候选检测器迅速搜索到最近邻自体，从而极大地降低了消除免疫自反应的计算代价。理论分析与实验结果表明NST-NSA相较于经典的V-detector算法能以较低的时间代价达到更高的检测率。

参考文献

[1]BRETSCHER P， COHN M.A， A theory of self-noself discrimination[J].Science， 1970，169：1042-1049.

[2]A. S. PERELSON，G. WEISBUCH.Immunology for physicists[J].Reviews of Modern Physics，1997，69（4）：1219-1267.

[3]陈文，李涛，刘晓洁.一种基于自体集层次聚类的否定选择算法[J].中国科学：信息科学，2013，43（5）：611-625.

[4]李涛.计算机免疫学[M].电子工业出版社，2004.endprint