一种基于动态识别邻域的免疫网络分类算法及其性能分析

邓泽林谭冠政何 锫李 峰

①（长沙理工大学计算机与通信工程学院 长沙 410076）

②（中南大学信息科学与工程学院 长沙 410083）

③（广州大学计算机科学与教育软件学院 广州 510006）

一种基于动态识别邻域的免疫网络分类算法及其性能分析

邓泽林*①谭冠政②何 锫③李 峰①

①（长沙理工大学计算机与通信工程学院 长沙 410076）

②（中南大学信息科学与工程学院 长沙 410083）

③（广州大学计算机科学与教育软件学院 广州 510006）

针对传统免疫网络分类算法在记忆细胞确定上缺乏有效的指导，该文提出一种基于动态识别邻域的免疫网络分类算法。算法采用核函数表示机制来描述抗体-抗原之间的亲和度；利用抗原对构造动态识别邻域来指导抗体群体的进化，并选择邻域中距离对偶抗原最近的抗体为记忆细胞。算法被应用于多分类问题及高维分类问题来进行算法性能分析，同时，算法被应用于多个标准数据集的分类来评估算法的整体性能。分类结果表明该算法对于标准测试数据集有良好的分类性能，这说明基于动态识别邻域的训练方法能够有效地指导记忆细胞的生成，显著地改善分类器的性能。

人工智能；人工免疫系统；免疫网络；抗原对；动态识别邻域

1 引言

人工免疫系统 （Artificial Immune Systems，A IS）在过去的十多年间得到了长足的发展，成为一门比较成熟的软计算技术。A IS启发于自然免疫理论，遵从免疫原理和模型，适用于问题求解［1］。AIS强大的信息处理能力被成功应用于各种复杂问题的求解。文献［2］提出基于A IS的学习算法进行字符的识别、函数优化以及组合优化问题的求解；文献［3，4］提出使用免疫算法来求解混合多目标优化问题；文献［5］提出构建免疫分类器来分析保险行业数据，该分类器利用多层免疫系统来创建和存储抗体群体，并利用遗传算法对抗体的学习过程进行优化；文献［6］提出用于银行业数据分析的免疫分类器；文献［7］提出利用决策超平面信息来指导记忆细胞的生成，构建高效的免疫分类器；文献［8］提出用于SAR图像分割的AIS算法，算法基于高斯核聚类指数来搜索SAR图像的优化分割，并使用直方图统计来加速SAR图像的分割；文献［9］利用A IS和多目标优化算法进行SAR图像的改变检测；文献［10］提出基于协同策略的模糊A IS来防御无线感知网络中的阻断服务攻击。

AIS主要包括人工免疫网络、克隆选择和阴性选择这3个理论和模型，这些理论和模型适用于分类问题求解。人工免疫网络是通过训练抗体群体并确定少数记忆细胞来表示较大训练空间的一种方法，因此，免疫网络是否有效地归纳抗原空间对于改善分类性能是至关重要的。文献［11］提出人工免疫网络分类器 （Artificial Immune Network Classifier，A INC）。 在AINC中，每个类用单个B细胞表示，这样细胞群体中就不存在冗余的B细胞，节省了计算时间并降低了网络复杂度。然而，每个类采用单个B细胞的表示机制难以有效地表示复杂的问题。文献［12］ 提出了基于局部特征选择的免疫分类算法（Artificial Immune System w ith Local Feature Selection， AISLFS）。A ISLFS 通过局部特征选择有效地进行了局部维数压缩，显著地降低分类所需的数据量。文献［13］ 提出了基于抗原对的免疫网络分类算法（Pair w ise antigens based Immune Network Classifier， PINC）。PINC利用抗原对指导抗体群体进化，使得记忆细胞能够靠近类域分界线，从而具备较好的预测能力。但PINC中抗体群体的进化缺乏优化机制，难以有效地进行记忆细胞群体的搜索。文献［14］基于免疫网络和模因算法（Memetic algorithm）提出了混合算法（Modified op t-aiNet w ith Local Search Strategy of Mem etic A lgorithm，M op t-aiNetLS）。文献［15］进行了克隆选择学习能力的研究，提出了基于克隆选择的精简免疫系统分类算法（Simp le A IS， SA IS）。在SAIS中，整个分类器用一个B细胞表示，在B细胞中为每个类别维持固定数量的抗体，这样就不需要进行抗体群体规模控制。其主要问题是算法缺乏跳出局部最优点的机制，使得算法难以搜索到全局优化的分类器。文献［16］在SAIS模型的基础上提出基于粒群智能的免疫分类器（A rtificial Immune Classifier w ith Swarm Learning， AICSL）。在AICSL中，抗体通过粒群智能的指导在抗原空间中移动，搜索最优化的抗体群体组合。目前，使用阴性选择原理来设计分类器的研究很少，主要的研究是阴性选择分类器（Artificial Negative Selection Classifier， ANSC）［17］。ANSC由人工淋巴细胞组成，这些细胞通过训练来完全覆盖训练空间。显然，完全覆盖训练空间是一件非常耗时的工作。

通过分析已有分类器的问题，本文发现高效的抗体群体进化特别是有指导的记忆细胞生成策略对于改善免疫分类器的性能是非常重要的，为此，提出了一种基于动态识别邻域的分类算法。算法的性能通过对标准数据集的分类测试结果来进行评估，并与其他著名分类器进行对比以显示算法的性能。

2 算法关键技术

记样本，x=［x1， x2，…， xl］其中l表示样本的属性数量，样本中每个属性为实数编码。算法中，抗体与抗原的编码方式与样本x的编码方式相同。所有样本构成数据集S。对于∀x∈ S，按式（1）进行属性归一化处理。

其中yi和zi分别表示S中所有样本第i个属性的最小值和最大值。

2.1 亲和度计算及免疫操作

2.1.1 亲和度计算 亲和度是用于量化抗体-抗原之间相互作用力的表示方法。一般的亲和度量化机制是采用抗体与抗原之间的欧式（Euclid）距离来表示的，其问题在于Euclid距离是线性空间表示方法，这不仅影响了算法的非线性能力，而且对于不同的问题，抗体-抗原的亲和度仅由两点坐标决定，不能根据不同问题进行亲和度优化来对免疫进化过程产生积极的影响。为此，引入基于径向基核函数（Radial Basis Function， RBF）的距离测量方法，如式（2）所示。

从式（3）可知，通过优化核参数c可以实现对抗体-抗原之间亲和度的优化，从而对后续免疫操作施以积极的影响。

2.1.2 免疫操作 人工免疫系统的主要操作包括克隆、变异。对于训练抗原g，计算抗体群体B中每个抗体b与g的亲和度。克隆操作中每个抗体b应克隆的数量为

其中参数α表示克隆速率，fb表示抗体b与训练抗原的亲和度值，round（·）表示四舍五入取整。

抗体b被克隆Nb个后代抗体，每个后代抗体在克隆的过程中根据式（5）进行变异操作。其中 b（t）表示进化过程中的第t代抗体。

2.2 基于动态识别邻域的训练方法

2.2.1 动态识别邻域的构建与记忆细胞的确定 免疫分类器由记忆细胞群体组成，群体中靠近类域分界线的细胞对分类器的性能有显著的影响，因此，搜索类域分界线附近的优良细胞对于改善分类器性能是至关重要的。为此，算法需要知道类域分界线位置并在其附近产生记忆细胞。对于训练抗原g，确定距离g最近的不同类别的抗原g'为其对偶抗原，g与g'称为抗原对。显然，类域分界线存在于抗原对之间的位置。

定义1 记识别训练抗原g的抗体群体构成g的动态识别邻域H（ g）， H（ g）根据式（6）确定。

其中θ为邻域控制因子。显然，对于不同的训练抗原，其动态识别邻域的大小是不同的，因此，H（ g）是一种范围可变的识别邻域。图1是一个动态识别邻域示例，其中以g为中心、r为半径的圆标示了该邻域的最大范围。

H（ g）中任意抗体细胞都能识别抗原g，在进化的过程中，当H（ g）中出现抗体细胞时，抗原g即可被识别，此时，根据式（7）来确定记忆细胞m。

图1 动态识别邻域示

在图1所示的动态识别邻域H（ g）中，抗体细胞m被确定为抗原g的记忆细胞。显然，m是H（ g）中距离分界线最近的抗体细胞。

参数θ是一个优化参数，它能通过控制动态识别邻域大小来实现对记忆细胞质量的优化，以图2、图3所示情形来说明，其中θ1＞θ2。

图2中g与g'互为对偶抗原，g'的记忆细胞为m1。当θ较大时，抗体群体能快速进入H（ g），但抗体群体经历克隆、变异的次数少，容易导致记忆细胞离分界线较远，如图2中的记忆细胞m2。因为m1和m2与分界线的距离差别较大，当使用它们进行分类时比较容易造成误分。而当θ取值较小时，抗体群体难以快速进入H（ g），因此，抗体群体需要在g的附近进行较多的克隆、变异操作，导致识别邻域H（ g）中存在较多的抗体细胞，如图3所示。

此时，在H（ g）中可能获得更靠近分界线的记忆细胞m3，比较易知m3的质量高于m2的质量。由此可知，通过优化参数θ可以搜索类域分界线附近的优良记忆细胞群体，实现对分类器的优化。

图2 较大的动态识别邻域

图3 较小的动态识别邻域

3 算法描述

参数：抗体群体大小s， 选择抗体数量σ， 克隆速率α， 重新选择系数ξ， k近邻，核函数参数c，网络抑制因子β，邻域控制因子θ。

步骤1 初始化。读取数据集S，归一化样本属性。初始化M=φ，加载训练集至G中，T= S- G为测试集。随机产生s个抗体来初始化抗体群体B。

步骤2 循环。如果所有抗原训练完毕，跳至步骤3执行分类，否则选择一个抗原为当前训练抗原g按如下步骤训练。

（a）抗体选择。对于∀b∈ B，其与g的亲和度依式（3）计算得到。从集合B中选出与g同类且亲和度最高的σ个抗体形成临时集合P。如果P=φ，置M= M∪｛ g｝，B= B∪｛ g｝，跳至步骤2继续训练。

（b）克隆与变异。对于∀b∈ P，其克隆数量根据式（4）得到。将克隆体全部放入集合P中。对于每个克隆体，根据式（5）进行变异。

（c）记忆细胞的确定及网络抑制。定义空集Q，找出g的对偶抗原g'，并构造H（ g）。如果∃b∈ P且b∈ H（ g），置Q= Q∪｛ b｝。 如果Q≠φ，据式（7）确定记忆细胞并进行网络抑制，然后跳至步骤2继续训练。

（d）抗体重新选择。选择P中ξ%个亲和度最高的抗体放入B，并随机产生s个抗体放入B中。跳至步骤（a）继续训练。

步骤3 分类。对于任意测试样本t∈ T， 使用M进行k近邻分类。当所有测试样本分类完毕，即可得到分类准确率。

4 实验与讨论

本文实验使用的数据集都来自UCI（Irvine machine learning repository of California University）机器学习数据库，这些数据集包括Iris，W ine， Sonar，威斯康星乳腺癌数据集（W isconsin Breast Cancer Dataset， WBCD）和Diabetes。本文所有实验使用10折交叉验证（10-fold crossvalidation）获取分类结果。

4.1 多分类问题

选择Iris来测试算法对多分类问题的分类性能。Iris共有150个样本，3个类别，每个类别有50个样本。Iris的3个类别分别是Setosa， Versicolor和V irginica。为了解免疫分类器中细胞群体的空间分布特征，对Iris全集进行分类训练，关键参数设置为c=0.6， θ=0.93， α=13， k=3。抗原群体及记忆细胞群体采用3维点图的形式输出，绘图时使用样本集的3个属性：花瓣宽度（petalw idth）、花瓣长度（petallength）和萼片宽度（sepalw idth），这些属性值通过属性归一化后成为［0， 1］之间的标量。Iris的抗原群体及记忆细胞群体分布特征如图4所示。

同时，对Iris进行10折交叉验证，10次独立分类运算将Iris中的每个样本分类测试1次。最终150个样本中有149个样本被正确分类，分类准确率为99.33%，标准差为2.0。

4.2 高维数据集

为了评估算法对高维数据集的分类性能，选择60维数据集Sonar来测试算法的分类性能。Sonar是一个2分类问题，两个类别分别记为R和M。评价2分类问题分类性能的标准除了分类准确率外，还广泛使用敏感度（Sen）和特异性（Spe），它们可以分别依据式（8）和式（9）计算得到。

其中，TP， FP， TN和FN分别表示真阳性样本数量、假阳性样本数量、真阴性样本数量和假阴性样本数量［18］。

实验时主要参数设置：c=1.7， θ=0.93， α=21，k=1。对Sonar 的分类混淆矩阵如表1所示。

表1 对Sonar分类得到的混淆矩阵

由此可得敏感度和特异性：分类准确率为90.38%。由此可知，算法不仅获得了较高的分类准确率，而且敏感度和特异性数值比较接近，说明算法为阳性样本和阴性样本进行了较为均衡的分类。

图4 Iris的训练抗原群体及记忆细胞群体的空间分布特征

4.3 算法整体性能评估

4.3.1 与免疫网络分类器的比较 免疫网络分类算法性能比较见表2，其中参与比较的分类算法为A INC［11］、A ISLFS［12］、PINC［13］和M op t-aiNetLS［14］。

表2 与免疫网络分类算法的比较（%）

4.3.2 与其他免疫原理分类器的比较 算法与克隆选择分类算法A ICSL［16］和阴性选择分类算法ANSC［17］进行了比较，结果见表3。

表3 与克隆选择分类器和阴性选择分类器的比较（%）

4.3.3 与其他分类器的比较 同时，将本文算法与k近邻分类算法（k-Nearest Neighbor， KNN）、随机森林算法（Random Forest， RF）和支持向量机（Support Vector Machine， SVM）进行比较。比较结果如表4所示，参与比较的算法获得的分类准确率来自文献［12］。

表4 与其他分类器性能比较（%）

4.4 参数敏感性分析

本文算法中，对分类性能有重要影响的参数包括RBF函数参数c和邻域控制因子θ。

图5显示了参数c对分类性能的影响。从图5可知，当c取值较小时，分类准确率有较大幅度的变化，这说明当c较小时，RBF核函数具有较强的非线性能力，使得算法能够有效地搜索记忆细胞群体组合，最终搜索到优化的分类器；而当c取值过大时，分类准确率之间仅存较小的差异，这说明当c过大时，RBF核函数的非线性能力减弱，算法表现出较强的线性特征而失去了优化的能力。

同时，邻域控制因子θ能够有效地控制抗体动态识别邻域的大小，从而影响最终分类器的质量。本文实验中参数θ的取值范围在［0.90， 1.00］之间，θ与分类准确率之间的关系如图6所示。

5 结束语

传统的免疫分类算法在抗体群体进化和记忆细胞确定时缺乏有效的指导，影响了算法的性能。为了改善这一问题，本文提出了一种基于动态识别邻域的免疫网络分类算法。算法被应用于多分类问题，3维分布图显示了组成分类器的记忆细胞群体有效地归纳了抗原空间，从而获得了很高的分类准确率；同时，算法被应用于高维问题的分类，混淆矩阵显示算法不仅获得了理想的分类准确率，而且算法为阴性样本和阳性样本进行了较为均衡的分类；最后，算法对多个数据集进行了分类，分类结果与其他著名的分类算法进行了广泛的比较，结果显示本文算法表现出了较好的分类性能和有力的竞争能力。

图5 核函数参数c与分类准确率之间的关系

图6 邻域控制因子θ与分类准确率之间的关系

为了充分挖掘本文训练方法的潜力，接下来我们将对算法进行深入的分析和改进，如对于不同的问题引入不同的核函数、通过空间几何的知识来确定更好的记忆细胞等。最后，改进的算法将会被应用于图像分类等类别更多、样本数量更大的问题，进一步验证分类器的分类性能。

［1］ T imm is J， Honec A， Stibord T， et al.. Theoretical advances in artificial immune system s［J］. Theoretical Com puter Science，2008， 403（1）: 11-32.

［2］ De Castro L and Von Zuben F. Learning and op tim ization using the clonal selection p rinciple［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（3）: 239-251.

［3］ 戚玉涛， 刘芳， 刘静乐， 等. 基于免疫算法和EDA的混合多目标优化算法［J］. 软件学报， 2013， 24（10）: 2251-2266. Qi Yu-tao， Liu Fang， liu Jing-Le， et al.. Hybrid immune algorithm w ith EDA for multi-ob jective optim ization［J］. Journal of Software， 2013， 24（10）: 2251-2266.

［4］ Lin Qiu-zhen and Chen Jian-yong. A novel m icro-population immune multiob jective optim ization algorithm［J］.Computers & Operations Research， 2013， 40（6）: 1590-1601.

［5］ M lungisi D， Tsh ilidzi M， and Bhekisipho T. Partial im putation of unseen records to imp rove classification using a hybrid multi-layered artificial immune system and genetic algorithm［J］. Applied Soft Computing， 2013， 13（12）: 4461-4480.

［6］ Chang S and Yeh T. An artificial immune classifier for cred it scoring analysis［J］. Applied Soft Com puting， 2012， 12（2）: 611-618.

［7］ Deng Ze-lin， Tan Guan-zheng， He Pei， et al.. A decsision hyper p lane heuristic based artificial immune network classification algorithm［J］. Journal of Cen tral South University， 2013， 20（7）: 1852-1860.

［8］ Yang Dong-dong， Wang Lei， Hei Xin-hong， et al. An efficient autom atic SAR im age segm entation fram ework in A IS using kernel clustering index and histogram statistics［J］. Applied Soft Computing， 2014， 16（3）: 63-79.

［9］ Shang Rong-hua， Qi Li-p ing， Jiao Li-cheng， et al.. Change detection in SAR im ages by artificial immune multi-ob jective clustering［J］. Engineering Applications of Artificial Intelligence， 2014， 31（1）: 53-67.

［10］ Shahaboddin S， Nor B， M iss L， et al.. Co-FAIS: Cooperative fuzzy artificial immune system for detecting intrusion in w ireless sensor networks［J］. Journal of Network and Com puter Applications， 2014， 42（1）: 102-117.

［11］ 刘若辰， 钮满春， 焦李成. 一种新的人工免疫网络算法及其在复杂数据分类中的应用［J］. 电子与信息学报， 2010， 32（3）: 515-521. Liu Ruo-chen， Niu M an-chun， and Jiao Li-cheng. A new artificial immune network algorithm for classifying com p lex data［J］. Journal of E lectronics & Inform ation Technology，2010， 32（3）: 515-521.

［12］ G rzegorz D. An artificial immune system for classification w ith local feature selection［J］. IEEE Transactions on Evolutionary Computation， 2012， 16（6）: 847-860.

［13］ Deng Ze-lin， Tan Guan-zheng， and He Pei. An imm une network classifier based on pair w ise antigens［J］. ICIC Express Letters， 2014， 8（6）: 1547-1552.

［14］ Ayse M and Ahmet A. A novel app roach for designing adap tive fuzzy classifiers based on the combination of an artificial immune network and a memetic algorithm［J］. Inform ation Sciences， 2014， 264（1）: 158-181.

［15］ Leung K， Cheong F， and Cheong C. Generating com pact classifier system s using a sim p le artificial imm une system［J］. IEEE Transactions on System s， Man， and Cybernetics-Part B: Cybernetics， 2007， 37（5）: 1344-1356.

［16］ Aydin I， Mehmet K， and Erhan A. Artificial immune classifier w ith swarm learning［J］. Engineering Applications of Artificial Intelligence， 2010， 23（8）: 1291-1302.

［17］ Igawa K and Ohashi H. A negative selection algorithm for classification and reduction of the noise effect［J］. Applied Soft Computing， 2009， 9（1）: 431-438.

［18］ Stephen V. Selecting and interpreting measures of thematic classification accu racy［J］. Rem ote Sensing of Environment，1997， 62（1）: 77-89.

邓泽林： 男，1977年生，博士，讲师，研究方向为人工免疫系统、模式识别.

谭冠政： 男，1963年生，博士，教授，研究方向为智能机器人系统与控制、人工智能与认知系统.

何 锫： 男，1963年生，博士，教授，研究方向为软件工程、人工智能.

李 峰： 男，1964年生，博士，教授，研究方向为图像处理与模式识别.

A Dynam ic Recognition Neighborhood Based Immune Network Classification A lgorithm and Its Performance Analysis

Deng Ze-lin①Tan Guan-zheng②He Pei③Li Feng①①（Schoo l of Com puter and Comm unication Engineering， Changsha University of Science and Technology， Changsha 410076， China）
②（School of Information Science and Engineering， Central South University， Changsha 410083， China）
③（School of Computer Science and Educational Software， Guangzhou University， Guangzhou 510006， China）

For lack of effective methods used by the trad itional immune network algorithm s to guide the m em ory cell determ ination， a dynam ic recognition neighborhood based immune network classification algorithm is proposed. The algorithm uses a kernel function rep resentation scheme to describe the antibody-antigen affinity，and constructs dynam ic recognition neighborhood w ith using pair wise antigens to guide the antibody popu lation evolution， in which the antibody nearest to the pairing antigen is determ ined as the memory cell. The algorithm is app lied to mu lti-class problem and high dim ensional classification problem to analyze the classification performance. Furthermore， the algorithm is used for many standard datasets classification to evaluate the algorithm overall performance. The resu lts show that the proposed algorithm can achieve better classification performance， which indicates that the dynam ic recognition neighborhood based training method is able to guide the memory cell generation effectively and im prove the algorithm performance significantly.

Artificial intelligence； Artificial immune system； Immune network； Pair w ise antigen； Dynam ic recognition neighborhood

TP301

： A

：1009-5896（2015）05-1167-06

10.11999/JEIT141077

2014-08-14收到，2014-12-25改回

国家自然科学基金（61170199）和湖南省教育厅重点项目（11A004）资助课题

*通信作者：邓泽林 zl_deng@sina.com