文摘

负选择算法是人工免疫系统的主要算法之一。然而,候选人探测器随机生成通过传统的负选择算法需要进行自我耐受性训练集,以消除所有的自我免疫反应。匹配过程是主要的时间成本,导致探测器生成效率低和应用免疫算法的局限性。一种新颖的算法,GB-RNSA命名。自我的算法分析分布在真实空间和问候n维[0,1]空间最大的网格。然后最大的网格划分为有限数量的子网格,和自我的同时相应的宫。随机生成的候选检测器只需要匹配的自我网格中的探测器在哪里和在其邻居网格,而不是自我,这降低了时间成本距离计算。和之前添加候选检测器为成熟检测器集合,采用一定的方法减少探测器之间的重复覆盖,而达到减少检测器覆盖尽可能多的异物空间。理论分析和实验结果表明,GB-RNSA降低探测器的数量,时间复杂度和误警率。

1。介绍

在过去的十年中,人工免疫系统造成了巨大的关注作为一种新的方法来解决复杂的计算问题。目前,有四个主要领域在人工免疫系统的研究1]:负选择算法(NSA) (2人工免疫网络(皇家)[],3),克隆选择算法(CLONALG) [4),危险理论(5),和树突状细胞算法(6]。通过模拟生物系统的免疫耐受t细胞成熟过程中,国家安全局移除反应候选人探测器来有效地识别异物抗原,并成功地应用于模式识别、异常检测、机器学习、故障诊断等7,8]。

福勒斯特提出的否定选择算法是et al。7]。该算法采用字符串或二进制字符串编码抗原(样品)和抗体(探测器)和r-continuous-bit匹配方法计算抗原和探测器之间的亲和力,这是表示SNSA [7]。工作(9,10)指出,在SNSA检测器的生成效率很低。候选人探测器通过消极的选择变得成熟。考虑到训练集的大小,抗原和抗体之间的匹配概率是随机的,然后呢是故障率;然后候选人探测器的数量,这是指数,SNSA的时间复杂度。

因为许多问题在实际应用中很容易被定义和研究在现实空间,实值否定选择算法(RNSA)提出11]。该算法采用n维向量在现实空间编码抗原和抗体和闵可夫斯基距离来计算亲和力。实值否定选择算法与大小可变检测器(V-Detector)提出了12,13),导致更好的结果。算法动态地确定检测器生成成熟的半径,通过计算最近的候选检测器和自体抗原的中心之间的距离。这个算法也提出了一个计算方法基于概率检测器的覆盖率。在的工作14),会负选择算法提出了,在工作的15),克隆提出文中针对负选择算法。探测器需要处理这两个算法的优化算法,以获得更大的异物的报道空间。介绍了Superellipsoid探测器(16在负选择算法和superrectangular探测器(17),达到相同的覆盖率减少探测器与球体。一个自我探测器分类方法提出了(18]。在这种方法中,自我被视为自我探测器与初始半径和自我的半径是动态决定的ROC分析在训练阶段,提高检出率。负选择算法的基础上提出自我设置的层次聚类(19]。该算法进行层次聚类预处理的自我提高检测器的生成效率。

因为成熟检测器的生成效率低,负选择算法的时间成本严重限制了他们的实际应用18,19]。实值否定选择算法基于网格提出了本文GB-RNSA表示。自我的算法分析分布形状空间,介绍了网格中设置机制,以减少时间成本距离计算和探测器之间的重复覆盖。本文的其余部分组织如下。实值否定选择算法的基本定义,还介绍了本文的背景部分2。的基本思想、实现策略和分析GB-RNSA节中描述3。GB-RNSA的有效性验证使用合成数据集和加州大学欧文分校(UCI)数据集4。最后,给出的结论是在上一节。

2。RNSA的基本定义

SNS(自我/异物)理论指出,身体依赖于抗体(T细胞和B细胞)认识到自我抗原和异物抗原,以排除外国人和保持身体的平衡与稳定2,8]。受这一理论,被定义为探测器识别异物抗原的抗体在人工免疫系统中,和他们的质量决定了检测系统的准确性和有效性。然而,随机生成的候选检测器可能识别自我抗原和提高免疫self-reaction。根据免疫耐受机制和成熟的过程生物免疫系统的免疫细胞,福勒斯特提出的负选择算法去除探测器可以认识自我7]。本文所讨论的算法是基于真正的价值。的基本概念RNSA如下。

定义1(抗原)。 总样本空间的问题。在一组抗原。是数据维度,的归一化值吗th属性示例代表这个职位在现实空间,的半径代表的变化阈值。

定义2(自我)。 代表所有抗原的正常样本集。

定义3(异物)。 代表所有抗原的异常样本集。自我/异物各领域有不同的含义。网络入侵检测,异物代表网络攻击,自我代表正常的网络访问;为病毒检测,异物代表病毒代码,自我是合法的代码。

定义4(训练集)。 是的一个子集自我和是先天的检测知识。训练集的大小。

定义5(探测器)。 。的检测器集合。是th属性检测器,探测器的半径,检测器集的大小。

定义6(匹配规则)。 ,是抗原之间的欧几里得距离吗和探测器。在检测器的生成过程,如果,探测器产生免疫self-reaction,不能成为一个成熟检测器。在探测器的测试过程,如果,探测器认识到抗原作为一个异物。

定义7(检出率)。博士意味着异己分子样品的比例由探测器正确确定总自样品和由(2)。TP是真阳性的简称,这意味着异物的数量正确识别的探测器。FN是假阴性的缩写,意思是异己分子的数量是错误的识别:

定义8(误警率)。远意味着自我的比例错误地认定为异己分子的样品样品和整体自我是由(3)。《外交政策》是假阳性,这意味着自我的数量由探测器,错误地识别和TN是真阴性的简称,这意味着数量正确的自我鉴定:

一般来说,检测器的生成过程的基本思想RNSA算法所示1。

RNSA算法,随机生成候选检测器需要做计算与训练集的所有元素,随着自我的数量的增加在指数增长,执行时间,而探测器之间的覆盖重叠的概率也增加,导致大量无效的探测器和低效率。上述问题极大地限制负选择算法的实际应用。

3所示。的实现GB-RNSA

本节描述该算法的实现策略。节中描述的算法的基本思想3所示。1。部分3所示。2,3所示。3和3所示。4算法的详细描述。介绍了网格生成方法3所示。2。非自我空间的覆盖率计算方法介绍了部分3所示。3。和候选人的筛选方法探测器介绍部分3所示。4。算法的性能分析部分3所示。5。算法的时间复杂度分析部分3所示。6。

3.1。该算法的基本思想

实值否定选择算法提出了基于网格GB-RNSA。算法采用可变大小的探测器和预期的报道异己分子的空间探测器探测器的终止条件的一代。自我的算法分析分布设置在现实空间和问候空间最大的网格。然后,通过部门逐步直到达到网格的最小直径和采用树存储网格,得到有限数量的的宫,同时自我抗原填写相应的子网格。随机生成的候选检测器只需要与自我网格中的探测器在哪里和在邻国网格,而不是所有的自我,这减少了时间距离计算的成本。当添加到成熟检测器集合,候选检测器将匹配探测器在网格内的探测器在哪里,邻居网格,来判断探测器是否在现有探测器的覆盖范围或其覆盖空间完全包含其他探测器。这个过滤器操作降低探测器之间的冗余覆盖,达到减少探测器的异己分子空间尽可能多。所示GB-RNSA是算法的主要思想2。

Iris数据集是一个经典的机器学习的数据集由加州大学欧文出版(20.),广泛应用于模式识别、数据挖掘、异常检测、等等。我们选择类别“setosa”数据集的数据记录虹膜作为自我抗原,选择“sepalL”和“sepalW”作为第一个维度的抗原特性和第二维度,并选择排名前25位的记录自我抗原作为训练集。在这里,我们只使用两个记录的特点,对二维地图直观的说明了思想,这并不影响比较结果。图1说明了思想GB-RNSA RNSA和V-Detector和经典的负选择算法。RNSA生成检测器与固定半径。V-Detector生成动态确定探测器的半径大小可变的探测器,通过计算最近的候选人探测器的中心之间的距离和自我抗原。检测器生成的两种算法需要进行公差自我抗原,这将导致冗余覆盖的异己分子之间的空间成熟检测器与覆盖率的增加。GB-RNSA首先分析自我设定在空间的分布,并形成网格。然后,随机生成候选检测器只需要执行宽容了自我在网格内的探测器在哪里,邻居网格。某些策略进行探测器通过宽容,避免重复覆盖,确保新探测器发现非自我空间。

3.2。网格生成方法

在网格生成过程,自顶向下方法的选择。首先,算法方面维空间空间最大的网格。如果有自我在这个网格,每个维度划分为两个部分,子网格。然后,继续法官和每个子网格划分,直到网格不包含任何自我或网格的直径达到最小值。最终,网格结构的空间,然后每个网格算法搜索得到邻居的结构。这个过程算法所示3和4。

定义9(网格的最小直径)。 ,在那里自我半径和吗探测器的最小半径。假设一个网格的直径小于,然后划分网格;子网格的直径小于。如果有自己的子网格,它可能是不可能产生检测器的子网格。所以,设置网格的最小直径。

定义10(邻居网格)。如果两个网格相邻的至少在一个维度,这两个网格是邻居,这被称为基本的邻居网格。如果自己邻居的网格是空的,添加它在同一方向的基本网格的邻居连接相邻网格。一个网格的邻居包括基本的邻居网格和附加的。

邻居的灌装过程网格算法所示5。

图2描述了网格的划分过程。自我训练集也从记录的类别选择“setosa”的虹膜数据集。选择“sepalL”和“sepalW”作为抗原第一维度和第二维度的属性。如图2,二维空间分为四子网格在第一次分裂,然后继续分裂子网格的自我并不是空的,直到潜艇不能分裂。

图3是邻居的示意图网格和网格用斜杠是网格的邻居吗在空间的全面爆发。

3.3。覆盖异物空间的计算方法

非自我空间覆盖率等于体积的比例由探测器和总量异物的空间(12,如下面所示:

因为探测器之间存在冗余覆盖,它是不可能计算(4直接)。本文采用概率估计方法计算检测器覆盖。探测器组的概率抽样的异己分子空间由探测器服从二项分布(13]。的概率抽样服从二项分布。

定理11。当异己分子连续抽样样本的数量,如果,可对空间探测器到达的报道。是百分比标准正态分布,是异己分子连续抽样样本的数量由探测器,然后呢是最小的正整数大于和。

证明。随机变量。集。我们考虑两种情况。(1)如果异己分子连续抽样样本的数量,从德Moivre-Laplace定理可知,当和。也就是说,。做假设:探测器的异己分子空间覆盖率≤;:探测器的异己分子空间覆盖>。给定显著性水平,。然后,拒绝域。所以,当,属于拒绝域,拒绝,接受。即异己分子空间探测器的报道>。(2)如果异己分子连续抽样样本的数量,不是太大,近似服从泊松分布相当于。然后。当,可对空间探测器的报道>。证明了。

从定理11检测器生成的过程中,只有异己分子连续抽样样本的数量和异己分子标本的数量由探测器需要被记录下来。采样后非自我空间,确定异物标本被探测器的覆盖。如果不是,生成一个候选人探测器的位置向量这个异己分子标本,然后将其添加到候选检测器集合。如果是这样的话,计算是否大于。如果是更大的比,可对空间覆盖率达到预期的报道,抽样过程停止。如果不是,增加。当是,把候选人的探测器为探测器组改变非自我空间覆盖,然后设置,重新启动新一轮的抽样。连续添加候选检测器,检测器集的大小增长,非自我空间覆盖率逐渐增加。

3.4。过滤候选检测器的方法

当抽样的数量乘以自空间中达到候选人探测器,探测器将被添加到检测器集合。在这个时候,并不是所有的候选检测器将加入,将为这些探测器进行过滤操作。过滤操作由两部分组成。

第一部分是减少候选检测器之间的冗余覆盖。首先,在候选人探测器探测器探测器设置在降序排列的半径,然后判断候选人探测器的序列已经被前面的覆盖。如果是这样,这个异己分子空间的采样是无效的,候选检测器产生的位置矢量的取样应删除。之间没有完全覆盖候选人探测器幸存下来第一个过滤操作。

第二部分是减少冗余覆盖成熟检测器与候选人之间的。候选检测器将匹配探测器在网格内的探测器在哪里,邻居网格当添加到检测器集,来判断它是否完全覆盖一些成熟检测器。如果是这样,成熟检测器是多余的,应该被删除。过滤操作确保每个成熟检测器将覆盖发现非自我空间。

候选检测器所示的过滤过程的算法6。

3.5。性能分析

本节从概率理论分析了算法的性能。假设所有的样品的数量问题空间,抗原在自我设置的数量,抗原在训练集的数量和探测器的数量。之间的匹配概率检测器和抗原,这是与特定的相关匹配的规则(7,9]。被定义为事件的发生概率(21]。

定理12。匹配一个未定的概率自我抗原的探测器是通过自我耐受性。

证明。从命题,一个给定的探测器通过自我耐受性表明该检测器不匹配任何抗原自我训练集,让事件是“给定的探测器不匹配任何抗原自我设定,”事件“给定的探测器匹配至少一个抗原不描述”。在这次事件中的次数,自我设置探测器匹配抗原符合二项分布,。因此,。在这次事件中探测器匹配的次数未定自我抗原符合二项分布,。然后,。
所以,。证明。

定理13。正确识别异物抗原的概率是,错误的概率识别异物抗原。正确识别自我抗原的概率是错误的概率,为自我抗原识别。

证明。让事件是“给定的异己分子抗原匹配探测器组中的至少一个探测器。”的事件的次数,可对抗原匹配探测器符合二项分布,。因此,,。
让事件是“给定的自我抗原不匹配任何探测器探测器集中。”事件的次数,一个自我抗原匹配探测器符合二项分布,。因此,,。证明。

大体上是常数为特定匹配规则(7,9]。假设和,那么图4显示的变化, , ,的影响下和。从图可以看出,当自我的训练集的数量和探测器的数量正确识别的概率更大,对于任意给定的异己分子抗原是更大的,错误的识别的概率小,变异的倾向和不是大而和改变。因此,当非自我空间的覆盖检测器集的确定,不同算法的检出率相对较近。当和正确识别的概率更大,对于任意给定的自我抗原是更大的,错误的识别的概率小,变异的倾向和大,而和改变。所以,当非自我空间的覆盖检测器集的确定,GB-RNSA较小的误警率,该算法显著降低了探测器的数量。

3.6。时间复杂度分析

定理14。检测器生成过程的时间复杂度GB-RNSA,在那里训练集的大小,检测器集的大小,探测器的平均反应速率。

证明。GB-RNSA,生成一个新的成熟检测器的主要时间成本包括调用的时间支出FindGrid找到网格,自我耐受性的时间支出候选人探测器,和时间支出的电话过滤器屏幕上的探测器。
从部分3所示。2的深度树是。因此,对于一个新的探测器,发现网格的时间复杂度探测器在哪里。是空间维度,是自我的半径,探测器的最小半径。所以,是相对稳定的。
计算新探测器需要的半径计算网格中的最近的距离与自我检测器和邻居。时间复杂度是,在哪里自我的数量吗和邻居。
的时间复杂度计算新的探测器是否覆盖现有的探测器,在那里探测器的数量吗和邻居。
打电话的时间复杂度过滤器屏幕探测器包括排序候选检测器的时间支出和判断是否存在冗余覆盖;也就是说,。
假设是候选检测器生成检测器的数量吗,然后取样的时间复杂度。和,所以,生成检测器集的时间复杂度如下:
所以,检测器生成过程的时间复杂度GB-RNSA。证明。

SNSA、RNSA V-Detector是主要的检测器生成算法和领域的广泛应用人工免疫模式识别、异常检测、免疫优化,等等。表1显示这些消极的比较选择算法和GB-RNSA。从表1传统算法的时间复杂度是指数级,自我的大小。当自我的元素数量的增加,时间成本将迅速增加。GB-RNSA消除了影响指数的影响,减少规模增长自我的时间成本。所以,GB-RNSA降低了原算法的时间复杂度,提高了检测器生成的效率。

4所示。实验结果和分析

本节通过实验验证GB-RNSA的有效性。选择两种类型的数据集的实验研究中常用的实值否定选择算法,包括2 d合成数据集(22[]和UCI数据集20.]。2 d合成数据集权威在实值否定选择算法的性能测试13,19,22),这是由Dasgupta教授的孟菲斯大学的研究团队。UCI数据集是经典的机器学习的数据集,广泛应用于探测器的测试性能和发电效率(11,18,19,23]。在实验中,两个传统的实值否定选择算法RNSA和V-Detector选择比较。

成熟检测器的数量DN检测率博士误警率远和探测器几代人的时间成本DT采用测量算法的有效性的实验。由于传统算法RNSA使用预设数量的探测器作为终止条件,本文修改RNSA和使用预期的异己分子空间覆盖率作为终止条件,为了确保三个算法在相同的实验条件下进行有效的比较。

4.1。2 d合成数据集

这些数据集包含几种不同的subdatasets。我们选择环、条纹和五角星形subdatasets测试探测器代GB-RNSA的性能。图5显示了这三个数据集的分布在二维真实的空间。

自我设置的三个数据集的大小。训练集由数据点随机选择从自我设定,和测试数据从二维随机选择空间。实验重复20次,平均价值。实验结果如表所示2和3括号内,价值观差异。表2列表比较GB-RNSA检测率和误报率的三个数据集在相同预期覆盖率为90%,同样的训练集,不同的自我半径。可以看到,该算法具有较高的检测率和误警率下自我半径小,而算法具有较低的检测率和误警率在大我半径。表3列表比较GB-RNSA检测率和误报率的三个数据集在相同预期覆盖率为90%,同样的自我半径不同大小的训练集,检出率逐渐增加和误警率逐渐减少而训练集的规模增长。

4.2。UCI数据集

三个UCI标准数据集包括虹膜,哈伯曼的生存和鲍鱼,选择做实验,实验参数如表所示4。三个数据集,自集和自组随机选择,并记录训练集和测试集的随机选择。实验重复20次,平均价值。

4.2.1。准备探测器的数量比较

数据6,7,8显示的数量成熟检测器RNSA, V-Detector, GB-RNSA三个数据集。从这些数据,与预期的覆盖率的增加,探测器的数量需要满足覆盖要求的三个算法相应地增加。但GB-RNSA效率明显优于RNSA V-Detector。虹膜的数据集,实现预期的覆盖率99%,RNSA需要13527成熟检测器,V-Detector需要1432,和GB-RNSA需要1166年减少约91.4%和18.6%,分别。鲍鱼的更大的数据集,实现预期的覆盖率99%,RNSA需要11500成熟检测器,V-Detector需要620,和GB-RNSA需要235年减少约98%和62.1%,分别。因此,在同样的预期范围,不同的数据维度,不同的训练集,GB-RNSA生成的成熟检测器的数量与RNSA V-Detector相比显著降低。

4.2.2。比较成本的探测器的一代

数据9,10,11显示探测器的时间成本代RNSA、V-Detector GB-RNSA三个数据集。从这些数据,预期的覆盖率的增加,RNSA的时间成本和V-Detector急剧增加,而GB-RNSA缓慢增长。虹膜的数据集,实现预期的90%,覆盖RNSA的时间成本是350.187秒,V-Detector是0.347秒,和GB-RNSA是0.1秒减少约99.97%和71.2%,分别;当预期的覆盖率是99%,RNSA的时间成本是1259.047秒,V-Detector是40.775秒,和GB-RNSA是3.659秒减少约99.7%和91.0%,分别。其他两种数据集,实验结果是相似的。因此,相比之下,RNSA V-Detector,探测器的一代GB-RNSA推广的有效性。

4.2.3。比较的检测率和误报率

数据12,13,14显示RNSA的检测率和误报率,V-Detector, GB-RNSA三个数据集。从这些数据,当预期的覆盖率超过90%大,三种算法的检测率相似,和RNSA略低,而GB-RNSA的误警率明显低于RNSA V-Detector。数据集的哈伯曼的生存,当预期的覆盖率是99%,RNSA的误警率是55.2%,V-Detector是30.1%,和GB-RNSA 20.1%减少约63.6%和33.2%,分别。鲍鱼的数据集,当预期的覆盖率是99%,RNSA的误警率是25.1%,V-Detector是20.5%,和GB-RNSA 12.6%减少约49.8%和38.5%,分别。因此,在同样的预期范围,GB-RNSA的误警率和RNSA V-Detector相比显著降低。

中华民国曲线图形方法分类模型使用真正的阳性率和假阳性。》一书,真阳性检出率和假阳性利率是误警率。图15显示了RNSA的ROC曲线、V-Detector GB-RNSA三个数据集。一个好的分类模型应该尽可能接近左上角的图形。可以看到从图15,GB-RNSA比RNSA V-Detector。

5。结论

太多的探测器和高时间复杂度的主要问题是现有的负选择算法,它限制》的实际应用。还有一个冗余覆盖的问题》一书的异己分子的空间探测器。实值否定选择算法基于网格的异常检测GB-RNSA提出。自我的算法分析分布设置在现实空间,将空间划分为网格通过特定的方法。随机生成的候选检测器只需要匹配的自我是谁在检测器的网格和邻国网格。并添加到候选检测器之前成熟检测器集合,采用一定的方法来减少重复报道。理论分析和实验结果表明,GB-RNSA具有更好的时间效率和探测器质量与古典负选择算法和人工免疫算法是一种有效的为异常生成检测器检测。

确认

这项工作一直是由中国国家自然科学基金支持下批准号下61173159,中国国家自然科学基金批准号60873246,和培养基金的关键科学和技术创新项目,中国教育部批准号下708075年。