基于优化目标可调控的免疫网络算法的分析与应用

摘要:针对目前几种免疫网络模型在数据聚类方面应用的一些不足,在aiNet免疫算法的基础上结合函数优化的思想提出一种基于目标可调控的免疫模型。并在算法中给出目标控制函数,和细胞记忆库的概念。本算法提高了免疫学习质量并从整体上对免疫网络进行优化。

关键词:人工免疫算法;聚类;数据压缩

中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)10-2384-03

The Analysis and Application of Artificial Immune Algorithm Based on Object-controllable

WANG Fan, TIAN Yu-ling

(Computer and Software Department in Taiyuan University of Technology, Taiyuan 030024, China)

Abstract: At present several immune models is in the lack of data clustering. On the base of the aiNet Algeria, I proposed a new clustering algorithm of artificial immune network based on object-controllable. A function to control the learning object is proposed and the cells memory is defined .In this algorithm the quality of immunity learning is improved by adopting the cells memory strategy and the immune network is optimized on the whole..

Key words: artificial immune algorithm; clustering; data compression

人工免疫系统在数据挖掘中的应用目前更多集中在无监督学习即聚类方面,数据聚类实际是对大量数据的一种压缩。而现有的一些免疫网络模型在实际应用上多少都有些局限性[1]。突出表现在以下几点:1) 预设参数较多,操作比较复杂。2) 抗体在变异过程中大多使用随机的方式,这样容易出现“退化”的情况。3) 整个抗体网络迭代学习的终止条件太简单,没有引入一个对整体网络优劣进行评价的标准。4) 即便提出了记忆库的概念,但并没有充分利用它来进行迭代学习。5) 没有对聚类结果进行一个评价。

1 基于优化目标可调控的免疫网络算法

针对上面的一些不足,吸取现有模型的优点,提出一些改进的方法。本文算法主要是在aiNet算法[2-3]的基础之上进行的改进。吸取了RLAIS免疫模型里提出的对抗体进行评价的思想,提出一个对整体抗体网络进行评价的函数。在理解了opt-aiNet算法的基础上,提出细胞记忆库的概念,并将其用于迭代学习过程中。提高了网络的收敛效果。

aiNet该学习算法本质就是一个带权不完全联通图。目的就是建立一个记忆集合,识别和表示数据结构组织。我们希望网络细胞足够特异,网络简化程度足够低,同时细胞足够“通用”。最后训练出来的记忆网络我们希望它能够用最少的抗体识别最多的抗原,并且识别效果最好。这就是我们对数据压缩的好坏最主要的评价标准。

1.1 根据我们提出的这种要求给出相关概念的定义

定义1:抗体对抗原识别是指抗原对于网络里所有抗体的最大亲和力能够大于预先识别阈值。

max{nf(Ag,Abi)}≥σ5, i=1,2,3…n(1)

σ5是亲和力阈值。

定义2:识别率是指一个记忆网络能够识别的抗原的个数所占抗原集合的比例。

f(Ag,M)=(j/q)×100%(2)

定义3:压缩率指识别一个抗原集合所需要的所有抗体个数占所有抗原的比例

为了使压缩率与M成单调递增关系便于后面计算,给出下面公式:

g(Ag,M)=(1-n/q)×100% (3)

(q为抗原个数,n为学习后网络抗体个数)

定义4:识别强度指记忆网络中所有抗体与抗原集合的亲和力之和

(4)

结合上面三个评价标准,为了能综合考虑,特提出一个总体评价函数如下:

maxF(Ag,M)=a・f(Ag,M)+b・g(Ag,m)+c・t(Ag,M)(0

由于实际应用过程中,不可能让三个函数都达到最优。这样我们就引进三个权重系数,根据实际需求调节系数值进而调节网络细胞变异学习的方向。通过对权重系数的预定义,这样评价函数越大就说明记忆网络越优秀,也就是要高识别率、高压缩率、高识别强度。

在本文算法中为了在抗体网络迭代学习过程中,出现盲目学习。甚至“越学越差”情况,特别引入记忆库的概念。

定义5(记忆库):在每一轮学习后产生的网络中,选择与抗原亲和力最大的n个抗体,组成一个记忆库。这也就是对这批抗原集合本轮中识别最好的一批抗体。在下次循环中可以将次其加入初始抗体中。这样既保证网络始终向更好的方向发展,又保证了网络的多样性。

1.2 算法描述

先给出算法中要用到的一些公式:

抗原:

抗体:

记忆网络M:

欧氏距离:(6)

亲和力: (7)

Step1:随机初始化n个抗体,作为初始网络细胞。

Step2:设定循环控制参数。

Step3:输入待聚类数据作为抗原,对每个抗原进行如下操作:

Step3.1:计算抗原于抗体网络的距离度量矢量和亲和力矢量,抗原与抗体之间的距离用公式(6)。根据聚类分析的特点,抗原与抗体之间的亲和力采用式(7)定义:

Step3.2:按照opR(optimal selecting Rate)的比率从Ab中选择η个与Agj具有最高亲和力的抗体进行克隆增殖,产生对应的克隆细胞集合。根据克隆选择原理,抗体与抗原的亲和力越大,抗体产生的克隆细胞数量越多。对η个选择细胞按亲和力从小到大的顺序排序,克隆细胞的数量按(8)式计算:

(8)

式中:Nc为n个抗体产生的克隆细胞总数;a为乘数因子,用于控制克隆群体的规模lnt()为取整函数。假设a=l,N=100,与抗原亲和力最大的抗体(i=l)将产生100个克隆个体,而第二号抗体产生的克隆个体数为50个,以此类推。

Step3.3 应用式(9)对克隆的抗体进行随机变异操作,实现亲和力的成熟,产生具有更高亲和力的抗体细胞:C

(9)

式中:Rand()为随机函数,μ为抗体的变异率。亲和力越高,变异率越小。

Step.3.4 计算C的抗体细胞与抗原的亲和力。按照rsR(re一selecting Rate)的比率,选择若干个与抗原局具有最高亲和力的抗体,作为部分记忆细胞M1。

Step3.5 去除M1中相似度:大于阈值σd的抗体,实现免疫系统克隆抑制的效果。