基于反馈的人工负选择分类算法

沈彤　关毅　董喜双

摘要：人工免疫系统是受人体免疫系统启发的一种智能算法，负选择算法作为人工免疫系统的核心算法之一，在各领域被广泛研究和应用。从两方面对负选择算法进行了改进，首先对记忆细胞数量对识别准确率的影响进行了研究，提出一种反馈学习的思想来进行记忆细胞数量的优化，实现提高分类过程中的识别准确率。然后为了解决传统负选择算法存在检测器覆盖空间存在交集、整体覆盖空间较低的问题，提出通过记忆细胞识别半径的自动调整，减少检测器数量，提高整体覆盖空间的方法，这种方法避免了“交叉识别（overlap）”和“识别洞（hole）”现象的出现。最后，实验结果表明算法在解决文本分类问题是有效可行的，其在路透社文本分类数据集上分类准确率达到了93.89%。

关键词：负选择算法； 人工负选择分类； 反馈学习

中图分类号：TP391 文献标识码：A 文章编号：2095-2163（2013）05-0061-05

0引言

“负选择（Negative selection，NS）”是免疫系统中自体/非自体区分机制的基础。负选择过程是指在T细胞发育过程中，在其表面通过随机遗传重排产生了对于特定抗原决定基高度特异的抗原识别受体来识别抗原的过程。T细胞在胸腺成熟的过程中，生物免疫系统将与自体蛋白质相结合的T细胞消除，保留未结合的T细胞，从而确保T细胞在体内循环时不会识别自体细胞[1]。负选择算法（Negative Selection Algorithm，NSA）模拟了免疫系统识别自体和非自体细胞的负选择过程，首先随机产生候选检测器，然后与自体样本数据集进行识别判断，生成非自体检测器，最后使用非自体检测器对非自体数据进行识别[2]，完成自体与非自体数据的分类。负选择算法作为人工免疫系统的核心算法之一，其研究成果涉及诸多领域，例如入侵检测[3]、数据分类[4]聚类[5]和异常检测[6，7]等，但仍存在以下两个问题：一方面，负选择算法中记忆细胞数量选择的不当会对识别精度产生一定的影响；另一方面，由于负选择算法在匹配过程中通常使用K连续位匹配规则，该规则的特殊性使得负选择算法带来的检测器在其覆盖空间出现交集，因而检测器集合整体覆盖空间较低的问题。

在负选择算法中，记忆细胞数量的不同会对算法的识别精度产生影响。由于在传统的负选择算法中，记忆细胞数量是固定值，无法比较判断当前记忆细胞数量是否为最佳值。为了解决记忆细胞数量选择不当对识别精度的影响，本文通过开展记忆细胞数量对识别准确率的影响的研究，提出一种通过反馈学习思想进行记忆细胞数量的优化，从而达到最佳分类效果的方法。

覆盖空间出现交集在将负选择算法应用于分类的过程中体现为“交叉识别”现象。“交叉识别”现象指样本数据未被分配到任何类别。与此对应的“识别洞”现象，是指样本被标记为多个类别，其时则无法判断应属哪一类别。为了解决传统负选择算法存在检测器覆盖空间出现交集、整体覆盖空间较低的问题，本文提出一种通过记忆细胞识别半径的自动化调整，减少检测器覆盖空间交集，提高整体覆盖空间的方法，避免了“交叉识别”和“识别洞”现象的出现。其中，解决“交叉识别”现象的方法是缩小识别半径，避免被多种记忆细胞识别。解决“识别洞”现象的方法是增大识别半径，扩大记忆细胞覆盖空间。

全文共分为五部分，其内容具体安排为：第一部分引言，主要介绍了生物免疫系统的负选择原理，以及课题的研究背景和研究意义，又给出了本文主要研究内容和文章结构。第二部分相关工作，首先分析了负选择算法的国内外研究现状，然后介绍了常用的文本分类算法和基于人工免疫系统的分类算法。第三部分人工负选择分类，首先对负选择算法的原理进行了系统描述，提出负选择算法待解决的问题，其次介绍人工负选择分类算法的具体流程，然后对其中每一部分进行具体论述，并针对负选择算法中出现的问题提供了详细解决方案。第四部分实验结果与分析，针对提出的新算法在两个方面的改进分别进行了试验，证明算法改进后的正确性和优越性。全文第五部分则是论文的结论及对下一步研究工作的展望。

1相关工作

负选择算法已广泛应用到数据分类聚类、异常检测、网络入侵检测等诸多领域。刘锦伟等人[8]通过分析已有实值负选择算法检测率不高的原因，提出一种通过鉴别边界自体样本以提高对“识别洞”的覆盖率的改进负选择算法，并采用人工合成数据集2DSyntheticData和实际Biomedical数据集对算法进行验证，结果表明，该算法针对夜晚视频进行目标检测是准确有效的，对于实现智能交通系统的全天候监控有现实意义；汪慧敏等人[9]为解决基于负选择的异常检测算法中检测器数目和检测器对非我空间的覆盖二者之间的矛盾问题，采用粒子群优化算法（PSO）来优化负选择算法中随机产生的检测器的位置，从而实现利用较少的检测器就能达到对非我空间的更大覆盖；仲巍[10]在分析了影响负选择算法性能的因素后，提出了一种基于切割的负选择算法，算法中使用新型的元素定义标准和匹配规则，结合一种多级检测器生成思想，有效解决了负选择算法中检测效率及检测率低下等问题。同时设计了基于层次型的检测器组织策略和基于优先级的检测器管理策略，并提出了一套快速检测器更新机制，可动态修改检测器信息，而且减少了环境变动时所造成的系统开销；曹霞[11]提出了一种应用于入侵检测系统的实值负选择改进算法，该算法通过估算“非自体”空间大小和优化抗体分布来产生最优化抗体集合，从而提高系统的检测率和降低误报率。国外很多研究学者对负选择算法也展开了研究。Bereta等人[12]将负选择算法与免疫K-means算法相结合应用于数据分析和聚类，研究首先对原始数据进行负选择，使用进化的负选择检测器生成一组人工样本。然后将原始数据与人工样本相结合来构建训练数据，并使用免疫K-means算法训练得到记忆细胞以用于数据聚类，取得了较好的聚类效果；Fernando Esponda等人[13]提出一种通用框架用来分析正负选择在近似匹配背景下的不同，该框架可以应用于异常入侵检测，例如，检测在局域网中异常TCP连接或者检测执行程序的系统调用中的异常模式；Laurentys等人[14]提出了一种基于人工免疫系统的负选择算法原理的故障检测系统的设计方法——多操作算法。

常用的文本分类算法包括贝叶斯分类、神经网络分类、支持向量机、TFIDF算法、粗糙集方法和模糊集（Fuzzy Set）方法等[15]。其中，基于人工免疫系统的分类算法的研究已获得了丰硕成果，例如，Alves等人提出的基于规则的模糊规则归纳算法（Induction of Fuzzy Rules with an Artificial Immune System，IFRAIS）[16]；邱小宁对IFRAIS 算法进行了改进，在IFRAIS 算法的规则进化研究中对抗体的克隆选择过程增加了抗体抗原间的交叉，以提高分类准确率，提出了抗体抗原交叉的规则归纳算法（Induction of Rule with Antibody-Cross-Antigen of Artificial Immune System， IRAA），并通过实验对改进算法进行了验证[17]；Watkins在克隆选择和有限资源人工免疫系统等基础上提出了人工免疫识别系统（Artificial Immune Recognition System，AIRS）分类器模型[18，19]；彭凌西等人对AIRS进行了改进，提出了一种基于免疫的监督式分类算法，有效减少了记忆细胞数量，提高了分类准确率[20]；刘芳等人提出了一种基于免疫克隆算法的搜索机制以及Michigan方法模型的规则提取和分类方法——免疫克隆分类算法（Immune Clonal Algorithm for Classification，ICAC）[21]；K.lgawa等人对负选择算法进行了改进，将负选择算法应用于多类别分类问题，并提出一种“裁剪”的思想来减弱噪声对分类结果的影响[22]。

2人工负选择分类器

首先对基于人工免疫系统的负选择算法进行介绍，负选择算法借鉴了生物免疫系统中胸腺T细胞生成时的“负选择”过程，其主要算法流程如图1所示。

在产生检测器阶段，负选择算法随机产生候选检测器，并判断其是否与“自体”样本数据集中每个数据进行匹配，若与任一数据匹配，则将该检测器从候选集合中删除，反之，不与任一“自体”数据匹配的候选检测器加入“非自体”检测器集。在检测阶段，将待检测数据与“非自体”检测器集合中的“非自体”检测器进行匹配，若有任一“非自体”检测器可识别该数据，则认定该数据为“非自体”数据，即异常数据，反之，不与任一“非自体”检测器相匹配的数据即可认为是“自体”数据，即正常数据。本研究将传统负选择算法中的“非自体”检测器定义为“记忆细胞”，如果被记忆细胞识别，表明样本不属于该类别。相反，如果无法被记忆细胞有效识别，表明样本属于该记忆细胞所代表的类别。

人工负选择分类器对负选择算法进行了改进，其总体流程如图2所示。算法的主要思想是在学习过程中通过训练数据集获得可用来识别非自体数据的记忆细胞，然后使用反馈学习的思想来调整记忆细胞数量，获得可进行预测的最终非自体记忆细胞集合。最后，在预测分类过程中对待分类数据进行预测分类。

2.1学习过程

传统的负选择算法过程中，记忆细胞的识别半径会影响产生的记忆细胞数量（即非自体检测器数量）。其中，识别半径指随机生成的检测器（即记忆细胞）能够识别样本的最大距离，本文采用欧氏距离计算，在系统初始化时设定。记忆细胞数量的不同会对算法的识别精度产生影响。在传统的负选择算法中，由于记忆细胞数量是固定值，无法判断比较当前记忆细胞数量是否为最佳值。为了解决这一问题，本文在算法的学习过程中增加了反馈机制，通过当前记忆细胞数量对识别精度的反馈信息来调整决定记忆细胞识别半径的参数α，从而对记忆细胞数量进行优化，达到最佳分类效果的方法。

人工负选择分类算法的学习过程主要由获取最佳记忆细胞和反馈调整两部分组成。学习过程旨在通过训练数据集获取记忆细胞，借鉴生物免疫系统的克隆和变异过程对记忆细胞进行优化，并通过使用记忆细胞对训练数据进行识别的过程获得反馈信息，同时根据反馈信息对记忆细胞数量进行调整，从而用数量适当的最佳记忆细胞来对待检测数据进行分类预测，以达到提高识别精度的目的。具体过程如图3所示。

在获取最佳记忆细胞的过程中，首先设置识别半径，然后设置“激活”等级，“激活”等级是指可被该检测器识别的非自体数据的数量，激活等级的值为刺激水平值和次刺激水平值之和。刺激水平是指可被该检测器识别，但不可被自体检测器（即自体记忆细胞集）识别的非自体数据的数量，次刺激水平是指既可被该检测器识别，又可被自体检测器识别的非自体数据的数量。接着，判断随机生成的检测器是否具有成为记忆细胞的条件，只有随机生成的检测器达到最低“激活”等级后才能成为记忆细胞。对于没有达到最低“激活”等级的检测器则需要进行克隆与变异。在克隆过程中，每一个未达到最低“激活”等级的检测器将以一定的克隆数量（初始化时设定）完成克隆后加入检测器集合。变异过程则是借鉴遗传算法中的单点变异，设定变异率为一个常数，在系统初始化时设定，若随机产生的变异概率低于变异率，则该检测器发生变异。经过克隆和变异过程后将产生新的检测器，如果这些新的检测器达到最低“激活”等级，则作为最佳记忆细胞。

在反馈过程中，首先使用当前非自体记忆细胞集对训练样本数据进行预测分类，然后将其分类结果与训练样本数据的实际类别进行比较获取分类准确率，并根据准确率调整决定记忆细胞识别半径的参数α，即间接调整记忆细胞数量，重新获取最佳记忆细胞。如此迭代循环，直至调整至最佳记忆细胞数量值，则将当前的非自体记忆细胞集作为最终非自体记忆细胞集对待分类数据集进行预测分类。

2.2预测分类过程

传统负选择算法在分类过程中存在两种现象——“交叉识别”现象和“识别洞”现象。“交叉识别”现象指待分类样本数据没有被分配到任何类别。当所有记忆细胞都能识别该样本时，表示该样本不属于现有全部记忆细胞所代表的任何类别，即现有记忆细胞无法判断该样本真正属于哪一个类别；“识别洞”现象是指当样本被标记为多个类别时，无法判断属于哪一个类别。当一种记忆细胞无法识别该样本时，表示该样本属于该类别。若多种记忆细胞无法识别该样本，则空间中即出现一个无法识别样本的“空洞”。

预测分类过程是根据学习过程中生成的非自体记忆细胞集对待分类数据集进行分类识别的过程。在此过程中，通过对记忆细胞识别半径的自动化调整，减少了检测器数量，并提高了整体覆盖空间，同时解决了传统负选择算法带来的检测器覆盖空间存在交集、整体覆盖空间较低的问题，更进一步地避免了“交叉识别”和“识别洞”现象的出现。其具体流程如图4所示。

根据传统负选择算法，若样本可被该记忆细胞（即非自体类识别器）识别，表明样本不属于该类别。相反，若无法被该记忆细胞识别，表明样本属于该记忆细胞所代表的类别。在利用获得的记忆细胞判断样本类别的分类过程中，会出现“识别洞”和“交叉识别”现象，这两种现象导致无法判断样本属于哪一类别，此时，可通过调整记忆细胞的识别半径直至有且仅有一种记忆细胞无法识别该样本时，[JP3]即将该样本的类别标记为此类，由此而完成样本分类。其具体调整算法如下：