基于人工免疫系统的单类分类算法研究

３１４４　２０１１，Ｖｏ１．３２，Ｎｏ．９　计算机工程与设计ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ　ａｎｄＤｅｓｉｇｎ　基于人工免疫系统的单类分类算法研究　陈岳兵，　（国防科学技术大学　冯　超，　张权，　电子科学与工程学院，　唐朝京　湖南长沙４１００７３）　摘　要：为了增加检测器的覆盖率，提高算法性能，对Ｖ－ｄｅｔｅｃｔｏｒ检测器生成算法进行改进，提出了一种不限定检测器中心点　位置的检测器生成算法。在检测器生成时，使大部分检测器中心点仍然在问题域内，覆盖问题域内的非我区域，少量检测器　中心点位于问题域之外，覆盖问题域边缘。改进后的检测器生成算法中，检测器中心点分量服从正态分布，检测器覆盖问题　域边缘的能力增强，检测器覆盖率更高。在基准数据集上的实验结果表明，改进后算法的性能有显著提高。　关键词：人工免疫系统：否定选择算法；单类分类；故障诊断；异常检测　中图法分类号：ＴＰ３９１　文献标识码：Ａ　文章编号：１０００．７０２４（２０１１）Ｏ９．３１４４．０４　Ｒｅｓｅａｒｃｈ　ｏｎ　ｏｎｅ—ｃｌａｓｓ　ｃｌａｓｓｉｔｉｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ａｒｔｉｆｉｃｉａｌ　ｉｍｍｕｎｅ　ｓｙｓｔｅｍ　ＣＨＥＮ　Ｙｕｅ—ｂｉｎｇ，ＦＥＮＧ　Ｃｈａｏ，ＺＨＡＮＧ　Ｑｕａｎ，ＴＡＮＧ　Ｃｈａｏ－ｊｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆＥｌｅｃｔｒｏｎｉｃ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｔｉｏｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＤｅｆｅｎｓｅ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４１００７３，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｏ　ｉｎｃｒｅａｓｅ　ｔｈｅ　ｄｅｔｅｃｔｏｒ　ｃｏｖｅｒａｇｅ　ａｎｄ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆｔｈｅ　ａｌｇｏｒｉｔｈｍ，ｍｏｄｉｆｉｃａｔｉｏｎ　ｔｏ　ｄｅｔｅｃｔｏｒ　ｇｅｎｅｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆＶ－ｄｅｔｅｃｔｏｒ　ｉｓ　ｍａｄｅ．Ａ　ｄｅｔｅｃｔｏｒ　ｇｅｎｅｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈｏｕｔ　ｌｉｍｉｔａｔｉｏｎ　ｏｆｐｏｓｉｔｉｏｎ　ｏｆｄｅｔｅｃｔｏｒ　ｃｅｎｔｅｒ　ｉｓ　ｐｒｅｓｅｎｔｅｄ．Ｉｎ　ｔｈｅ　ｄｅｔｅｃｔｏｒ　ｇｅｎｅ—　ｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ｍｏｓｔ　ｏｆｔｈｅ　ｄｅｔｅｃｔｏｒ　ｃｅｎｔｅｒｓ　ａｒｅ　ｗｉｔｈｉｎ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｄｏｍａｉｎ，ｗｈｉｃｈ　ｃｏｖｅｒ　ｎｏｎｓｅｌｆｒｅｇｉｏｎ　ｏｆｔｈｅ　ｐｒｏｂｌｅｍ　ｄｏｍａｉｎ．Ａ　ｆｅｗ　ｄｅｔｅｃｔｏｒ　ｃｅｎｔｅｒｓ　ａｒｅ　ｏｕｔｓｉｄｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｄｏｍａｉｎ，ｗｈｉｃｈ　ｃｏｖｅｒｓ　ｔｈｅ　ｅｄｇｅｓ　ｏｆｔｈｅ　ｐｒｏｂｌｅｍ　ｄｏｍａｉｎ．Ｔｈｅ　ｄｅｔｅｃｔｏｒ　ｃｅｎｔｅｒｓ　ａｒｅ　ｎｏｒｍａｌｌｙ　ｄｉｓｔｒｉｂｕｔｅｄ．Ｔｈｅ　ｃａｐａｂｉｌｉｔｙ　ｏｆｔｈｅ　ｄｅｔｅｃｔｏｒｓ　ｔｏ　ｃｏｖｅｒ　ｔｈｅ　ｅｄｇｅｓ　ｉｓ　ｅｎｈａｎｃｅｄ．Ｔｈｕｓ　ｔｈｅ　ｃｏｖｅｒａｇｅ　ｏｆｔｈｅ　ｄｅｔｅｃｔｏｒｓ　ｉｓ　ｉｎｃｒｅａｓｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｏｎ　ｂｅｎｃｈｍａｒｋ　ｄａｔａｓｅｔ　ｉｎｄｉｃａｔｅ　ｔｈａｔ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｎｃｒｅａｓｅｓ　ｓｉｇｎｉｆｉｃａｎｔｌｙ　ａｆｔｅｒ　ｍｏｄｉｆｉｃａｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：ａｒｔｉｆｉｃｉａｌ　ｉｍｍｕｎｅ　ｓｙｓｔｅｍ；ｎｅｇａｔｉｖｅ　ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ；ｏｎｅ—ｃｌａｓｓ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｆａｕｌｔ　ｄｉａｇｎｏｓｉｓ；ａｎｏｍａｌｙ　ｄｅｔｅｃｔｉｏｎ　０引　言　传统模式识别方法一般需要多个类别的样本，从而设计　两类和多类分类器。但是在某些情况下，训练样本中只有一　类目标数据，其它非目标数据采集代价过高，造成样本缺失。　两类分类方法的分类边界需由两类实例来“支持”，因此无法　直接用于解决此类问题。只能从已有的目标类样本中进行学　习，并形成一个对该类别的数据描述，然后根据给定或设计的　相似性度量，并设定阈值来判别新样本的归属。因只使用一　类实例，故称为单类分类（ｏｎｅ．ｃｌａｓｓ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ）“　。目标数据　又称为自我类、正常类或目标类，而非目标数据对应地称为非　我类、异常类或野类（ｏｕｔｌｉｅｒ）。针对单类分类问题所设计的单　类分类器，已被用于文本检测　、安全审计。　、故障诊断　、入侵　检测　、异常检测　等领域。研究和改进单类分类算法具有很　大的应用价值。　人工免疫系统是受人体免疫系统启发而建立的各种算　法和模型的统称。否定选择被认为是人体免疫系统的主要　机理　，它模仿胸腺中Ｔ细胞的选择过程。近似随机的基因　重组使得新生成的Ｔ细胞具有极大的多样性，在胸腺中，那些　识别自我细胞的Ｔ细胞被清除，剩余的Ｔ细胞用于对外部病　原体进行识别和应答。基于否定选择原理的算法称为否定选　择算法。否定选择算法利用一类数据（自我或正常）进行训练，　训练后可以对两类数据进行区分。否定选择算法是一种单类　分类算法。目前已被用于入侵检测和异常检测［１１１。否定选择　算法具有多种版本，文献［１２］对否定选择算法进行了综述。文　献［１３１提出一种基于可变尺寸检测器的否定选择算法（Ｖ－ｄｅｔｅｃ—　ｔｏｒ）。Ｖ－ｄｅｔｅｃｔｏｒ的独有特性在于它最大化单个检测器尺寸来　达到更好的覆盖效果。文献［１４】对Ｖ－Ｄｅｔｅｃｔｏｒ进行改进，引入　统计方法评估检测器覆盖率，利用假设检验来确定终止条件，　使得算法性能更稳定。当前Ｖ－Ｄｅｔｅｃｔｏｒ检测器覆盖问题域边　缘的能力受限，有必要进行改进。本文对Ｖ－ｄｅｔｅｃｔｏｒ检测器生　成算法进行改进，提高检测器的覆盖性能。在基准数据集ＫＤＤ　９９上的实验表明，改进后算法性能显著提高。　１　Ｖ－ｄｅｔｅｃｔｏｒ算法原理　Ｖ－ｄｅｔｅｃｔｏｒ通过自我样本进行训练，生成覆盖非我区域的　收稿１５ｔ期：２０１０　０９．０ｌ；修订日期：２０１０—１１－２５。　作者简介：陈岳兵（１９８０一），男，江苏江都人，博士研究生，研究方向为人工免疫系统、信息安全；　冯超（￣９８３一），男，江苏盱胎人，博士研　究生，研究方向为安全协议分析；　张权（１９７４一），男，上海人，副教授，研究方向为量子通信、信息安全；　唐朝京（１９６２一），男，江苏武进　人，教授，博士生导师，研究方向为网络攻防与对抗。Ｅ—ｍａｉｌ：ｍｉｌｐｅｔｅｒ＠ｈｏｔｍａｉｌ．

ｔｏｍ　陈岳兵，冯超，张权，等：基于人工免疫系统的单类分类算法研究　２０１１，Ｖｏ１．３２，Ｎｏ．９　３ｌ４５　检测器。图１在二维平面上描述了Ｖ－ｄｅｔｅｃｔｏｒ的核心思想。深　灰色区域代表自我区域，通常由训练数据（自我样本）和自我　“半径”￡决定。浅灰色圆形是用于覆盖非我区域的检测器。图　１（ａ）是固定尺寸的检测器。在此情况下，算法需要大量检测器　来覆盖非我区域。黑色区域描述的是存在的“空洞”。图１（ｂ）　是可变尺寸检测器，少量大尺寸检测器覆盖了非我区域的大　部分，小尺寸检测器可以覆盖“空洞”。　麓　（ａ）固定尺寸检测器　（ｂ）可变尺寸检测器　图１　否定选择和可变尺寸检测器　否定选择算法包括训练阶段（也称为检测器生成阶段）和　检测阶段。不同版本否定选择算法差别主要在检测器生成算　法。Ｖ－ｄｅｔｅｃｔｏｒｔ　检测器生成算法流程如图２所示。　图２　Ｖ．ｄｅｔｅｃｔｏｒ检测器生成算法　Ｖ－ｄｅｔｅｃｔｏｒ检测器生成算法采用生成　验证的策略，随机生　成检测器，并计算其与自我以及已有检测器之间的距离（如欧　几里德距离），根据被覆盖情况来确定此随机采样点的去留。　如果一个采样点不被自我覆盖且不被已有检测器覆盖，则保　存为候选检测器。　算法中引入统计方法，通过单侧Ｚ检验来确定检测器覆　盖率和算法终止条件。算法主要控制参数有覆盖率Ｐ和显著　性水平　。为了进行假设检验，根据覆盖率Ｐ计算需要的样本　数下限　。算法中包括两个计数器，Ｎ和　，分别表示采样的非　我点数和已被覆盖的点数。在算法流程中，Ｚ保持不变或不断　增加，如果在完成”点采样之前，出现Ｚ）　，则表明当前覆盖率　大于Ｐ。此时可以终止算法流程，也可以继续运行以达到更高　的覆盖率。　２算法改进　在Ｖ－ｄｅｔｅｃｔｏｒ中，检测器表示为＜　，其中ｄ是检测器中　心点，ｒ是检测器半径。假设算法输入数据决定的问题域具有　三维特征，则　＝　，　，…，冼】。文献［１３－１４】中，生成的随机点具　有均匀分布，即分量　，ｉ＝１，２，…上服从均匀分布。算法输入数　据是归一化到［０，１】之间的数据，因此，　在区间［０，１】上均匀分　布，记为　～　０，１），ｉ＝１，２，…上。Ｖ－ｄｅｔｅｃｔｏｒ将检测器中心点限制　在问题域内，这影响了检测器的性能。因此提出解除这种限　制，允许检测器中心点在问题域之外。　图３在二维平面上描述了两种情况下检测器对非我区域　的覆盖。方框表示问题域，包括自我区域和非我区域。图３（ａ）　是检测器中心点限制在问题域内的情况，此时需要较多检测　器来覆盖边缘。图３（ｂ）是不限定检测器中心点位置的情况，　少量检测器就可以较好地覆盖边缘。实际上，自我和非我都　不会出现在问题域之外，因此允许检测器中心点处于问题域　之外不会增加误检。　（ａ）检测器中心点在问题域内　（ｂ）不限定检测器中　ｔｈ，点位置　图３检测器中心点位置　在检测器生成时，使大部分检测器中心点仍然在问题域　内，覆盖问题域内的非我区域，少量检测器中心点位于问题域　之外，覆盖问题域边缘。因此提出让　，ｉ＝１，２，…工服从正态分　布，其概率密度函数为　１　“～　）＝—　＝－一Ｐ一—　，一ｏｏ＜ｄ￣＜＋ｏｏ　￣／２／ｒｔｒ　对于归一化到［Ｏ，１］的输入数据，　＝０．５，　：０．５，记为　￣Ⅳ　（０．５，０．５），概率分布如图４所示。　大部分检测器中心点（ｄ）分布在问题域［０，１　内，少量检测　器中心点（ｄ）分布在问题域【０，１】Ｌ外侧附近。文献［１４］中，检测　

器中心点在非我区域均匀分布，通过被覆盖的采样点比例来　！ｖ０１．３２，Ｎｏ．９　计算机工程与设计Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ　０．８　０．６　，、　０．４　０．２　０　Ｎ（０．５，０．５）概率密度函数　・１　０　１　２　ｄｉ　图４检测器分量概率分布　估计检测器覆盖率。在检测器中心点分量服从正态分布的情　况下，检测器覆盖边缘的能力增强，检测器覆盖率更高。改进　的Ｖ－ｄｅｔｅｃｔｏｒ称为ＥｎＶ－ｄｅｔｅｃｔｏｒ，下节将通过基准数据集上的比　较来显示改进对算法性能的影响。　３实　验　为了验证改进后的算法性能，采用基准数据集ＫＤＤ９９进　行实验测试。　３．１数据集　ＫＤＤ９９数据集是美国林肯实验室入侵检测数据集，也被　称为ＤＡＰＰＡ数据集。ＫＤＤ　９９数据集具有４１个属性（特征），　其属性值类型包括数值型和符号型。数据集中每一个数据项　末尾带有明确标记，表明是正常连接或者攻击。实验采用的　是１０％子集，它包括４９４　０２１个数据项。１０％子集与完整数据　集具有相似的统计特性，子集中正常连接与攻击的比值与完　整数据集相当。　ＫＤＤ９９数据集属性域较多，其中有些属性域对分类几乎　没有影响。根据基于信息增益的属性选择“　，选择了１０个属　性，分别为：属性１２，属性２３，属性２４，属性２５，属性２６，属性　２９，属性３１，属性３２，属性３８，属性４０。这些属性都是数值型　的，对选择的属性值进行归一化处理，所有属性映射到【０，１］。　利用ＫＤＤ　９９　１０％子集随机抽取１Ｏ％的数据构建１０个子　集，抽取时保持正常连接与攻击的比值。构建的数据集记为　Ｓ　，＆，…，　ｏ，每个数据集包括４９４０２个数据项，９７２８个正常连　接和３９６７４个攻击。　３．２实验设置　Ｖ－ｄｅｔｅｃｔｏｒ和ＥｎＶ－ｄｅｔｅｃｔｏｒ采用Ｍａｔｌａｂ　Ｒ２００９ａ编程实现。　覆盖率Ｐ和显著性水平６ｃ分别设为９９％和０．１。自我“半径”￡设　为０．０１，这表示与自我的欧几里德距离小于Ｏ．Ｏ１范围内的点　都是自我。实验中，每个数据　，ｉ：ｌ，…，１０集利用８０％正常　连接进行训练，剩余２０％的正常连接和攻击作为测试数据集。　实验在ＷｉｎｄｏｗｓＸＰ下运行（奔腾双核ＣＰＵＥ５２００，２Ｇ内存）１ｏｏ　次，结果取平均值。　单类分类问题根据测试样本的真实类别和分类结果构成　了如表１所示的混淆矩阵。　表１单类分类的混淆矩阵　真实类别　分类结果　自我　非我　自我　Ｔｒｕｅ　Ｐｏｓｉｔｉｖｅ（ＴＰ）　Ｆａｌｓｅ　Ｎｅｇａｔｉｖｅ（ＦＮ）　非我　Ｆａｌｓｅ　Ｐｏｓｉｔｉｖｅ（ＦＰ）　Ｔｒｕｅ　Ｎｅｇａｔｉｖｅ（ＴＮ）　从表１可看出单类分类有两类错误，即自我被错分为非　我（即）和非我被错分为自我（　ｖ）。定义两个指标　ＦＰＲ＝ＦＰ／（ＴＮ＋ＦＰ）　ＰＷＲ＝ＦＮ／（ＴＰ＋ＦＮ）　显然，这两个指标越小越好。除，ｍ，ＦＮＲ之外，还有一　个综合指标，称为Ｂａｌａｎｃｅｄ　Ｌｏｓｓ（ＢＬ）“　：ＢＬ：（　Ｒ＋ＦＮＲ）／２。　３．３实验结果及分析　实验结果如表２所示，　，ＦＮＲ和ＢＬ是１００次实验的平　均值。算法具有随机算法的特点，表中还给出了标准差。　从表２可看出，在基准测试数据集上同等条件的比较中，　ＥｎＶ－ｄｅｔｅｃｔｏｒ性能明显提高。就ＦＰＲ而言，对于测试的ｌＯ个数　据集＆，　，…，　－ｏ，改进前后差别不大，大多数情况下ＥｎＶ－ｄｅｔｅｃ—　ｔｏｒ具有略高的即Ｒ，　标准差差别很小。就ＦＮＲ而言，对于　测试的所有１Ｏ个数据集，改进后ＦＮＲ值大大减小，标准差也　大大减小。ＢＬ是ＦＰＲ和ＦＮＲ的平均值，由于ＦＮＲ显著降低，　而ＦＰＲ变化较小，导致ＢＬ显著降低。由于改进后ＦＮＲ标准　差大大减小，而即Ｒ标准差变化不大，ＢＬ标准差显著减小。从　综合指标看，改进后算法稳定性明显提高。　由表１可知，ＦＰ就是错误地将自我分类为非我。表２中　所有数据集下ＦＰＲ都不超过０．００５，这是一个很好的结果，表　示ＥｎＶ－ｄｅｔｅｃｔｏｒ保持了Ｖ－ｄｅｔｅｃｔｏｒ低ＦＰＲ的良好特性。这种特　性也被称为泛化能力或推广能力。对于单类分类算法而言，　泛化能力就是通过部分自我（训练样本）确定一个自我区域，只　要位于此区域内的样本，即使没有在训练样本中出现，也被认　为是自我样本。Ｖ－ｄｅｔｅｃｔｏｒ和ＥｎＶ－ｄｅｔｅｃｔｏｒ根据训练样本和自　表２　Ｖ－ｄｅｔｅｃｔｏｒ和ＥｎＶ－ｄｅｔｅｃｔｏｒ在ＫＤＤ　９９数据集上的性能比较　Ｖ－ｄｅｔｅｃｔｏｒ　ＥｎＶ－ｄｅｔｅｃｔｏｒ　数据集　ＦＰＲ（ＳＤ）　ＦＮＲ（ＳＤ）　ＢＬ（ＳＤ）　ＦＰＲ（ＳＤ）　ＦＮ　ＳＯ）　ＢＬｆＳＤ）　Ｓ　０．０００７（０．０００５）　０．４７０６（０．３３４８）　Ｏ　２３５７（０．１６７４）　Ｏ．００３９（０．０００６）　Ｏ．０１３６（０．０００８）　０．００８８（０．ｏｏｏ５）　＆　０．０００９（０．０００７１　０．４７８８（０．３３６２）　Ｏ．２３９９（０．１６８ｌ１　０．００２７（０．０００６）　０．０１２７（０．００１０）　０．００７７（０．０００６）　＆　０　００２９（０．ＯＯＬＯ）　０．４７１３（０．３４０６）　０．２３７１（ｏ．１７０３）　０．００３７（０．０００８１　０．０１４４（０．０００５）　Ｏ．００９０（０　０００５）　＆　０．００１７（０．０００６）　０．４２５１（０．３４９１）　０．２１３４（０．１７４５）　０．００１８（ｏ．０００４）　０．０１３３（０．０００７）　０．００７５（０．０００４）　＆　０．０叭９（０．０００８）　０．５０２９（０．３２４９）　Ｏ．２５２４（０．１６２５）　０．００２４（０．０００６）　０．０１４１ｆ０．０００６）　０．００８３（０．０００４）　＆　０．００３０（０．０００９）　Ｏ．４７４８（０．３３１８）　Ｏ．２３８９（０．１６５８）　０．００４９（０．００ｏ８）　０．０１４９（０．ＯＯＯ５）　０．００９９（０．０００４）　岛　０．００２２（０．００１　１）　Ｏ．４６２７（０．３４６２）　０．２３２５（０．１７３１）　０．００１６（０．０００５）　０．０１４２（０．０００８）　０．００７９（０．０００５）　＆　０．００１０（０．０００５）　０．４８２９（０．３３４５）　０．２４２０（０．１６７３）　Ｏ．００３１（０．０００７）　０．０１２６（０．ＯＯＬＯ）　０．００７８（０．０００６）　Ｏ．０ＯＯ７（Ｏ，０００５）　０．４５５６（０　３３５５）　０．２２８２（０．１６７７）　０．ｏｏ１７（ｏ．０００５）　Ｏ．ｏ１４８（ｏ．０００５）　０．００８３（０．０００３）　Ｓｌ０　０．００２３（０．０００９）　０　４２３３（０．３５０８）　０．２１２８（０．１７５４）　Ｏ．００２６（０．０００５）　０．０１４２（０，０００８）　０．００８４（０．０００５）