改进的人工免疫识别系统及其性能分析

邓泽林，谭冠政，何锫

1.长沙理工大学计算机与通信工程学院，长沙 410076

2.中南大学信息科学与工程学院，长沙 410083

3.广州大学计算机科学与教育软件学院，广州 510006

改进的人工免疫识别系统及其性能分析

邓泽林1，谭冠政2，何锫3

1.长沙理工大学计算机与通信工程学院，长沙 410076

2.中南大学信息科学与工程学院，长沙 410083

3.广州大学计算机科学与教育软件学院，广州 510006

为了改善人工免疫识别系统的非线性能力,进一步优化分类器性能，提出了一种改进的人工免疫识别系统。新算法采用混合核函数来提升算法的非线性能力，同时，对记忆细个体进行适应度评估，淘汰低适应度的细胞来优化免疫分类器。改进的算法被应用于复杂UCI数据集的分类，分类结果与其他经典的分类算法的结果进行比较，结果显示该算法具有更好的分类性能。

人工免疫识别系统；混合核函数；适应度；复杂数据

1 引言

人工免疫系统（Artificial Immune Systems，AIS）启发于脊椎动物的免疫系统，遵从免疫系统功能、原理和模型[1]，其主要特点是学习和记忆[2]。由于具有强大的学习能力，AIS被广泛应用于各种问题，如优化[3-4]、聚类[5-6]、异常检测[7-8]、图像处理[9-10]等。

AIS具有众多的理论和模型，目前的研究主要集中于免疫网络、克隆选择和阴性选择这3种理论[11]。基于这3种理论的算法被广泛应用于不同的领域，尤其是机器学习中的分类问题。由于免疫网络具有强大的学习能力，大多数分类器都是基于免疫网络模型来设计的。不同的免疫网络分类算法在分类表示机制上采用不同的方法，其中免疫网络分类器（Artificial Immune Network Classifier，AINC）[12]采用固定数量B细胞来表示分类器，该分类器虽然在具有混合特征数据的分类中表现出良好的性能，但每个类采用单个B细胞来表示难以有效地表示比较复杂的问题。另一种表示方法采用不固定数量的B细胞来表示分类器，代表性的算法是人工免疫识别系统（Artificial Immune Recognition System，AIRS）[13]。AIRS是一个强大的免疫分类器，在与其他经典的分类算法，如支持向量机SVM、随机森林等，比较时表现出强大的竞争能力。AIRS算法的主要问题有两个：（1）AIRS中样本之间的相似度通过两者之间的Euclidean距离来量化，由于Euclidean距离是线性空间的测量方法，这使得算法的非线性能力受到限制。为了改善算法的非线性能力，文献[14]提出使用核函数来改善免疫算法的非线性能力，核函数将输入空间中非线性可分样本映射至高维空间，使得样本在高维空间中线性可分[15]。大量的研究只关注使用单一核函数的效果，这样虽然利用了单个核函数的优点，但不能同时发挥多个核函数的优势来更好地提高算法性能。（2）AIRS在刺激度计算时采用相对刺激度，这导致少数相对刺激度高的细胞可能距离训练抗原距离较远，不能很好地表示训练样本，从而造成样本误分。

针对AIRS算法的这两个问题，本文提出了改进的方法。通过将多个核函数进行结合来构造新的混合核函数，这样就可以同时利用多个核函数的优势。同时，对记忆细胞群体中的个体细胞进行适应度评估，通过剪切适应度低的细胞来优化分类器。这个改进的算法记为KPAIRS，并将KPAIRS应用于复杂数据的分类，将得到的结果与AIRS、AINC和SVM等算法的结果进行比较来评估算法的性能。

2 KPAIRS算法

2.1 混合核函数

对于复杂的分类问题，样本空间呈现非线性特征，使得样本难以被有效地分类。对于非线性可分的数据，通过找到一个合适的映射函数φ将样本映射至高维特征空间H，使得样本在H中可以进行线性分类。设x，y∈X，X属于Rn空间，非线性函数φ实现输入空间X到高维特征空间H的映射，其中H属于Rm，n＜m。

定义1对于输入空间中的向量x，y∈X，核函数K定义为[15]：

这里＜·＞表示内积。式（1）说明输入样本x和y在高维特征空间中的内积可以通过核函数计算得到，而不需要知道具体的φ映射或者是H的维数，从而避免了高维特征空间中的“维数灾难”等问题。

在核函数应用时，同时使用多个核函数可以利用多个核函数的优点，相比于使用单一核函数来说能更好地发挥核函数的优势，进一步改善算法性能。文献中介绍了多种核函数，本文采用两个核函数，即高斯径向基核函数和逆多元二次核函数[14]来构造混合核函数：

（1）高斯径向基核函数（Radial Basis Function，RBF）

（2）逆多元二次核函数（Inverse M ultiquadratic Kernel Function，IMKF）

选择这两个核函数构造混合核函数的原因有两个：

（1）这两个核函数都只有一个参数，方便搜索到优化的参数。

（2）这两个核函数都可以通过x，y的欧氏距离计算得到，方便算法的实现。

将RBF核函数与IMKF核函数进行组合，得到如下混合核函数，其中θ是加权系数。

通过引入核函数，输入空间被映射至高维核空间，此时，输入空间中的样本x，y在核空间中的相似度D(x，y)可根据式（5）计算得到。

其中υ是用户定义的系数用于控制D(x，y)≤1。此处定义υ=，可得输入空间中样本x，y在核空间中的相似度为：

显然，通过使用混合核函数，样本之间的相似度会根据参数的不同而有所不同，这必然会影响到分类决策，从而实现对分类决策的优化。因此，引入多个核函数可以扩大算法的搜索空间，进一步优化分类器性能。

2.2 细胞剪切

AIRS在计算抗体的刺激度时进行了归一化处理，处理方法如式（7）所示。

其中，sb表示抗体b的真实刺激度，表示归一化刺激度，smax表示抗体群体中刺激度的最大值，smin表示抗体群体中刺激度的最小值。

显然，归一化刺激度是一种相对刺激度，不能反映抗体与抗原之间真实的距离，可能导致算法确定的记忆细胞与训练抗原的距离过远而失去归纳能力，这将会降低分类器的预测能力，显著影响分类器的分类性能。因此，需要对记忆细胞个体进行质量评估并淘汰识别能力较差的细胞。

定义2中M表示记忆细胞群体。根据定义2可知，抗原g被距离最近的细胞识别。如果cm=cg，则说明抗原g被记忆细胞m正确识别，否则，错误识别。其中cm和cg分别表示m与g的类别。

定义3记忆细胞m的正确识别邻域为：

定义4记忆细胞m的错误识别邻域为：

定义5记忆细胞m的适应度为：

计算每个记忆细胞的适应度，如果细胞fm＜γ，说明细胞m的适应度低于阈值，则从细胞群体M中删除细胞m。其中γ是剪切阈值。

2.3 KPAIRS算法描述

记G表示抗原群体，B表示抗体群体，g∈G表示训练抗原样本，M表示记忆细胞群体。

步骤1初始化。归一化数据集中所有样本的属性，使得任何两个样本的距离不大于1。亲和度阈值f根据式（11）计算得到。

然后，随机选择若干抗原放入记忆细胞群体M中，并从G任意选择一个抗原为当前训练抗原g。

步骤2记忆细胞的发现和抗体的产生。根据式（13）找出与训练抗原g刺激度最高的记忆细胞m。

记g与m的刺激度为s，按式（15）计算克隆细胞数量σ。

其中μ是超级克隆速率，λ是克隆速率。并以概率η来变异每个克隆体，克隆体放入B中。

步骤3竞争资源并形成候选记忆细胞。计算B中每个抗体b与g的刺激度，并按式（16）为每个抗体b分配资源。

步骤4记忆细胞的确定。确定与g刺激度最高的抗体b′，如果刺激度sm＜sb′，则把b′加入至M中成为记忆细胞。如果affinity(m，b′)＜δf，则执行网络抑制，删除m，其中δ是亲和度标量。

步骤5循环。选择未训练的抗原为训练抗原g，从步骤2开始循环训练。当抗原群体训练完毕，跳至步骤6。

步骤6细胞剪切。计算每个细胞的适应度，如果细胞的适应度低于剪切阈值，则执行细胞剪切。

步骤7分类。对于∀t∈T，找出与之最近的k个记忆细胞，t的类别由这k个细胞投票决定。

3 实验与讨论

为了获得更客观的分类性能，分类结果采用10次交叉验证（10-fold cross-validation）方法获得。

3.1 数据集

用于测试的复杂数据集是German Credit Data（GC）、Australian Credit（AC）、Cleveland Heart Disease（CHD）和Hepatitis（HP），这4个数据集来自UCI。这4个数据集不仅包含连续属性，还包含离散属性、名义属性，这些不同类型的属性构成了复杂的具有混合特征的数据集，能很好地检验分类器的性能。数据集详情见表1所示。

表1 数据集信息

3.2 参数设置

对于4个实验数据集，KPAIRS在测试时设置了相应的参数，其中克隆速率λ、变异概率η、剪切阈值γ等参数设置相同，分别为10、0.1和0.5，其他重要的参数设置如表2所示。

表2 参数设置

3.3 核函数对分类性能的影响

为了比较不同的核函数对分类性能的影响，分类实验使用了不同的核函数，得到的分类结果进行了比较，包括准确率、细胞数量和算法运行时间的比较，具体情况见表3所示。

表3 核函数对分类性能的影响

从表3可知，对于AC、GC、HP和CHD这4个问题，算法在采用混合核函数时达到了最高的分类准确率，而相应的细胞数量和运行时间只与使用单一核函数时存在微小的差异。表3的比较说明混合核函数能够更有效地搜索优化的分类器，因此，分类准确率有一定程度的提高。

3.4 分类性能比较

同时，KPAIRS与其他分类算法进行了比较，这些算法包括AIRS、SVM和AINC。比较结果见表4所示。其中AIRS和AINC对4个数据集的分类结果直接来自文献[12]，SVM对AC和GC的分类结果来自文献[16]，SVM对HP和CHD的分类结果通过运行Weka中的SMO算法得到，其中对HP分类时采用多项式核函数，关键参数是C=3.0，E=1.0；对CHD分类时采用RBF核函数，关键参数是C=1.0，G=0.07。

表4 分类算法准确率比较（%）

从表4的比较可知，采用混合核函数的免疫识别系统KPAIRS的性能显著优于采用线性表示机制的免疫识别系统AIRS；从AINC与KPAIRS的比较可知，KPAIRS对具有混合特征样本的复杂问题具有更高的分类准确率；从KPAIRS与SVM的比较可知，相对于优秀的分类器SVM而言，KPAIRS也表现出了相当的竞争能力。

4 结论

针对人工免疫系统AIRS的问题，提出了相应的改进方法。通过构造混合核函数来更好地改善算法的非线性能力，通过记忆细胞个体质量评估来淘汰适应度低的细胞，进一步优化分类器。将改进的算法应用于GC、AC、HP和CHD这4个具有混合特征的复杂问题，比较使用不同核函数时算法的分类性能，结果表明算法在使用混合核函数时达到了最高的分类性能。同时，将改进的算法与AIRS、AINC和SVM分类器进行比较，结果表明改进的算法获得了非常具有竞争力的分类结果，说明相应的改进策略很好地提升了算法的性能，使得KPAIRS成为一个非常具有潜力的分类器。

[1]Timmis J，Hone A，Stibor T，et al.Theoretical advances in artificial immune systems[J].Theoretical Computer Science，2008，403（1）：11-32.

[2]de Castro L N，Von Zuben F J.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Computation，2002，6（3）：239-251.

[3]Li Zhonghua，Zhang Yunong，Tan Hongzhou.IA-AIS：an improved adaptive artificial immune system applied to complex optimization problems[J].Applied Soft Computing，2011，11（8）：4692-4700.

[4]赵云丰，付冬梅，尹怡欣，等.一种改进的人工免疫网络优化算法及其性能分析[J].自然科学进展，2009，19（4）：434-445.

[5]Graaff A J，Engelbrecht A P.Clustering data in an uncertain environment using an artificial immune system[J].Pattern Recognition Letters，2011，32（2）：342-351.

[6]陶新民，付丹丹，刘福荣，等.基于多尺度并行免疫克隆优化聚类算法[J].控制与决策，2012，27（6）：819-825.

[7]Laurentys C A，Ronacher G，Palhares R M，et al.Design of an artificial immune system for fault detection：a negative selection approach[J].Expert Systems with Applications，2010，37（7）：5507-5513.

[8]Gong Tao，Cai Zixing.Normal model and BPNN-based immunization of anti-worm Web system[J].International Journal of Multimedia and Ubiquitous Engineering，2006，1（3）：23-26.

[9]Oguz F，Ismail B，Erkan U.A color image watermarking scheme based on artificial immune recognition system[J].Expert Systems with Applications，2011，38（3）：1942-1946.

[10]Konstantinos K D，Pantelis A A，George K M.Automatic point correspondence using an artificial immune system optimization technique for medical image registration[J].Computerized Medical Imaging and Graphics，2011，35（1）：31-41.

[11]Aydin I，Karakose M，Akin E.Artificial immune classifier with swarm learning[J].Engineering Applications of Artificial Intelligence，2010，23（8）：1291-1302.

[12]刘若辰，钮满春，焦李成.一种新的人工免疫网络算法及其在复杂数据分类中的应用[J].电子与信息学报，2010，32（3）：515-521.

[13]Andrew B W.AIRS：a resource limited artificial immune classifier[D].Mississippi State：Department of Computer Science and Engineering，Mississippi State University，2001.

[14]Ozsen S，Gunes S，Kara S，et al.Use of kernel functions in artificial immune systems for the nonlinear classification problems[J].IEEE Transactions on Information Technology in Biomedicine，2009，13（4）：621-628. [15]Muller K R，Mika S，Ratsch G T，et al.An introduction to kernel-based learning algorithms[J].IEEE Trans on Neural Network，2001，12（2）：181-201.

[16]Chang S Y，Yeh T Y.An artificial immune classifier for credit scoring analysis[J].Applied Soft Computing，2012，12（2）：611-618.

DENG Zelin1,TAN Guanzheng2,HE Pei3

1.School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410076, China
2.School of Information Science and Engineering, Central South University, Changsha 410083, China
3.School of Computer Science and Educational Software, Guangzhou University, Guangzhou 510006, China

In order to improve the nonlinearity of Artificial Immune Recognition System（AIRS）and optimize the classifier,an improved AIRS algorithm is proposed. The new algorithm adopts hybrid kernel function to improve its nonlinearity,moreover, the individual memory cell is evaluated by its fitness score and the cells with low fitness scores are pruned to optimize the classifier. The improved algorithm has been applied to the complex UCI datasets classification, the results have been compared with the results achieved by other classic classifiers. The comparison shows that the algorithm achieves better classification performances.

artificial immune recognition system; hybrid kernel function; fitness score; complex data

DENG Zelin, TAN Guanzheng, HE Pei. Improved artificial immune recognition system and its performance analysis.Computer Engineering and Applications, 2014, 50（17）：16-19.

A

TP301

10.3778/j.issn.1002-8331.1402-0247

国家自然科学基金（No.61170199）；湖南省教育厅重点项目（No.11A 004）。

邓泽林（1977—），男，工学博士，主要研究方向：人工免疫系统、模式识别；谭冠政（1962—），男，工学博士，教授，博士生导师，研究方向：智能机器人系统与控制、人工智能与认知系统；何锫（1963—），男，博士，教授，研究方向：软件工程、人工智能。E-mail：zl_deng@sina.com

2014-02-24

2014-04-28

1002-8331（2014）17-0016-04

CNKI网络优先出版：2014-05-05,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0247.htm l