【摘要】负选择算法是人工免疫的分支，对自我和非我细胞区分过程进行计算模拟。由于负选择算法具有对于自我和非我较强的判别能力，可以模拟数据分类。本文在对特征提取算法，人工免疫系统以及负选择算法深入研究之后，将基于改进的负选择理论应用于数据分类。主要采用对检测器的改进提高负选择算法的检测率，采用自然计算方法优化负选择算法，通过其高效的全局搜索能力和局部搜索能力，优化负选择算法，并将其应用到数据分类，设计基于新算法的数据分类系统，检测该系统的效率。
【关键词】负选择算法；优化；数据分类
1.人工免疫系统概述
人工免疫系统（AIS）借鉴自然免疫系统的原理，将其应用于各种智能系统中，解决实际工程问题[2]。
许多研究人员已经利用免疫系统某一个或某些性质、功能、机制发展出各种人工免疫系统技术，被统称为人工免疫系统[1]。Jamey提出的人工免疫网络理论，阐述了自然免疫系统具有大量独特型及抗体独特型的抗体，由此形成了细胞间相互制约关系。免疫系统中B细胞和T细胞之间的相互反应被借鉴用于建立人工免疫网络模型。基于自然免疫系统检测抗原原理可以被应用于计算机安全等。人工免疫系统模型被广泛应用于模式识别、异常检测、数据分类计算机安全等领域，这些模型可以大体分为四类[2]：人工免疫网络（aiNet）、克隆选择算法、负选择算法以及一些其它的模型，比如危险理论[3][4][5]。
2.负选择算法及其改进
2.1 负选择基本算法
从生物学角度看，区分自我和非自我细胞是复杂免疫系统的主要机制之一。负选择算法是对自我和非我细胞区分过程的计算模拟。一般来说，在负选择算法中输入一个象征正常数据的字符串集合（自我集合），并在非我（non-self）区域产生一定数量的检测器。匹配检测器和自我字符串，如果检测器可以匹配，检测器则被丢弃；如果检测器和自我字符串不能匹配，保存检测器。
2.2 负选择算法的改进
2.2.1 检测器的改进
很多研究在检测器方面对负选择进行改进，我们在二维的基础上提出多维空间的超球体检测器以提高非我空间的覆盖率。
假设自我和非我空间为实数集合Rn的子集合[0，1]n。一个检测器（抗体）可以定义为Rn中的一个超球体，用n维向量表示圆点，用一个数值表示半径。检测器与抗体的欧几里德距离定义为：
如上式r表示检测器半径，表示匹配函数，也就是自我和非我区域的元素x与检测器的匹配程度。
检测器的控制：重复两个步骤，1）使检测器远离自我样本；2）使检测器相对独立，以此更新检测器的位置，得到最好的覆盖“非我”区域效果；
主要算法：产生覆盖“非我”区域的检测器，用向量集合表示；
输入表示：n维向量集合，即自我样本的表示；
此算法中，如果自我样本与中心点的距离小于r则认为检测器与自我样本匹配。检测器有成熟时间，如果时间大于t，生成新的检测器。
我们利用一个混淆矩阵来表示检测器的检测率和误报率。
我们在高的检测率和低的误报率之间找到一个平衡，也就是找到一个最优的检测器半径。
2.2.2 利用混合算法优化负选择算法
对于负选择算法，我们提出了用混合算法优化负选择算法。
在负选择算法中，检测器对非我空间的覆盖是一个关键的问题。为解决这一问题，引入动态克隆选择算法。由于检测器的位置是随机产生的，采用动态克隆选择算法进行优化，以实现用较少的检测器实现对非我空间的更大覆盖。在保证检测器尽可能小地覆盖自我空间的前提下，扩大检测器集合对非我空间的覆盖，提高了检测率，并且在这个过程中保持检测器的数目一定。
将这种方法用于网络入侵检测的实例中，应用动态克隆选择算法[15]优化负选择检测器。将检测器集分为“记忆检测器”、“成熟检测器”和“未成熟检测器”。记忆检测器负责检测曾经出现过的入侵方式，而成熟检测器负责检测新的入侵方式。算法在指定数目的“代”中实现以下几个功能模块：（1）首先利用记忆检测器检测收集到的数据集，将检测到的入侵数据删除，并产生协同刺激；如果是误报，则删除相应的记忆检测器。（2）利用成熟检测器检测数据集余下的数据，将检测到的入侵数据删除并累计信息，适当时产生协同刺激；如果确认是出现入侵，则将该成熟检测器加入到记忆检测器集，否则删除之。（3）利用数据集余下的数据，对未成熟检测器进行负向选择，若出现匹配则将相应的未成熟检测器删除。（4）生成充足的未成熟检测器。
3.负选择算法的应用
计算机安全领域的核心问题是识别异常状态，这与生物免疫系统所遇到的问题具有很大的相似性。因此，近年来，负选择算法被广泛应用于计算机安全领域，并取得了很大的进展。Dasgupta[2]提出了一种用户验证的新方法，负选择算法的使用显著地提高了验证系统对非法用户的过滤准确度。负选择算法在计算机领域的应用，特别是故障检测、网络入侵、数据分类等，将越来越受到人们关注。
将改进的负选择算法应用到数据分类：
基于上述提出的优化检测器和利用混合算法改进负选择算法的方法，我们提出一个算法模型，基于快速、高效检测器的负选择模型，在此算法中，利用层次匹配的方法加速检测器的生成。
算法采用二进制编码，全集空间U={0，1}，U=S∪N，S∩N=0，其中S和N分别表示自我集合和非我集合。检测器集合用D表示，满足DN。
设自我集合S有如下的形式：
将数据分类检测率和检测器生成耗费的时间作为算法的指标，在实验中，将模型与其它两种算法进行比较。两种算法分别是穷举生成算法]和位变异生成算法。实验运行100次，每10次的结果取平均值，得出10组数据。运行平台采用Matlab7.0.4.
（1）生成长度为L，规模为N的自体集合S；
（2）应用三种算法分别生成检测器；
（3）统计时间耗费和检测率。
实验结果比较：
在基于人工免疫原理的入侵检测系统中，标准的穷举检测器生成算法没有很好地消除重复检测器，从而造成失败率增高等问题。标准的穷举检测器生成算法采用的是链表存储结构。如果在链表存储结构的基础上消除重复检测器，是非常耗时的。位变异生成算法改进了遗传算法，该算法可有效地提高算法的全局搜索能力。新模型利用r连续匹配原则，将自体集合分解，在查找和搜索能力上都有优势。
实验数据统计：三种算法的时间耗费
从图2可以看出，新模型的时间复杂度优于其它两种算法，主要因为穷举和位变异采用的随机搜索，需要匹配大量的检测器，耗费了大量的时间。另外新模型在检测率上也有优势，主要是其从自体出发，得到补空间，这些补空间容易被检测器检测。
4.总结与展望
采用检测器改进以及自然计算方法对负选择算法优化，在数据分类，异常数据检测中能得到令人鼓舞的结果。将这种系统推广以及提高它的稳定性任重道远。通过上述实验我们可以发现，由于负选择算法的特点以及检测器设定的一些特点，该分类系统在一段时间内可以达到极高的召回率，但这种极高的召回率稳定性不够强。对该系统的研究还需进一步。优化负选择方法采用的是检测器形状、生成速度以及搜索能力的改进，对于其他更好地方法有待探索。算法复杂度是否代价太大也有待考虑，进一步探索最优的负选择优化方法需要进一步深入研究。
参考文献
[1]徐春鸽，章登科，葛红.人工免疫系统在数据挖掘中的应用[J].计算机技术与发展，2007，17（4）：34-37.
[2]Dipankar Dasgupta.Advances in Artificial Immune Systems[C].IEEE Computational Intelligence Magazine，2006.
[3]L.N.de Castro，F.J.V.Zuben.aiNet：An Artificial Immune Network for Data Analysis[C].Data Mining：A Heuristic Approach，H.A.Abbass，R.A.Sarker，and C.S.Newton，Eds.Idea Group Publishing，USA，2001：231-259.
[4]S.Forrest，A.S.Perelson，L.Allen，R.Cherukuri.Self-nonself Discrimination in A Computer[C].Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy，Los Alamitos，CA：IEEE Computer Society Press，1994.
[5]J.M.Shapiro，G.B.Lamont，Gilbert L.Peterson.An Evolutionary Algorithm to Generate Hyper-ellipse.
[6]Sankalp Balachandran，Dipankar Dasgupta，Fernando Nino，Deon Garrett.A General Framework for Evolving Multi-shaped DetectorsinNegativeSelection[C].Foundations of Computational Intelligence，2007：401-408.
[7]X.Wang，X.Z.Gao，S.J.Ovaska.AHybridOptimizationMethod for Fuzzy Classification Systems[C].8th International Conference on Hybrid Intelligent Systems，Barcelona，Spain，2008：264-271.
[8]汪慧敏，高晓智，黄显林，宋卓越.基于改进负选择算法的异常检测[J].计算机仿真，2007，23（5）.
[9]X.Wang，X.Z.Gao，S.J.Ovaska.AHybridOptimizationMethodfor Fuzzy Classification Systems[C].8th International Conference on Hybrid Intelligent Systems，Barcelona，Spain，2008：264-271.
[10]Jonatan Gómez，Fabio González，Dipankar Dasgupta.An Immuno-Fuzzy Approach to Anomaly Detection[C].The IEEE International Conference on Fuzzy Systems.
作者简介：吴丹（1983—），女，江苏江阴人，中国科学院国家天文台研究实习员，研究方向：数据分析、数据处理。
