搜索
面向大数据环境的检测器快速筛选算法蔡涛倪晓蓉王伟生牛德姣(江苏大学计算机科学与通信工程学院江苏镇江212013)(caitao@ujs.edu.cn15905287603)摘要筛选成熟检测器是决定人工免疫系统的性能和效率的关键因素，在大数据环境下由于初始检测器的数量极其庞大，造成现有检测器筛选算法时间开销过大的问题。本文针对海量的初始检测器，设计海量初始检测器的分布存储模式，为提高筛选初始检测器的效率提供基础；利用Map/Reduce模型，设计了新型的海量初始检测器快速筛选算法，给出了混合式初始检测器快速筛选架构、海量初始检测器分区检查策略和成熟检测器集优化策略，提高筛选初始检测器的效率，优化成熟检测器。最后在Hadoop集群中，实现了面向大数据环境检测器快速筛选算法原型系统，使用CERTsynthethicsendmaildata数据集进行了测试与分析，验证了算法能减少58.87%的时间开销，并在初始检测器数量不断增加时保持时间开销的稳定。关键字检测器生成算法，大数据系统，人工免疫算法，Map/Reduce中图法分类号TP391文献标识码ATheFastDetectorGenerationAlgorithmfortheBigDataSystemCaiTao,NiXiaorong,WangWeisheng,NiuDejiao(SchoolofComputerScienceandTelecommunicationEngineering,JiangSuUniversity,Zhenjiang,Jiangsu212013)AbstractThedetectorgenerationalgorithmisimportantfortheperformanceandefficiencyofartificialimmunesystem.Butthetimeoverheadofcurrentdetectorgenerationalgorithmistoobigduetothelargenumberofinitialdetectorinthebigdatasystem.Inthispaper,thenewdistributedinitialdetectorstoragestrategyisdesignedtoprovidethebasisforimprovingthemassiveinitialdetectorselectionefficiency.Then,thenewfastdetectorgenerationalgorithmforthebigdatasystemisgivenbyanalyzingthedifferentcharacterofmapandreducestageinMap/reducemodel,anditisusedtoimprovetheinitialdetectorselectionefficiencyandoptimizethematuredetectorset.Itincludeshybridinitialdetectorselectionarchitecture,massiveinitialdetectionpartitioninspectionalgorithmandmaturedetectorsetoptimizationalgorithm.Atlast,thefastdetectorgenerationalgorithmprototypeforbigdatasystemisrealizedinHadoopsystem.CERTsynthethicsendmaildatasetisusedtoevaluateandcomparewiththecurrentdetectorgenerationalgorithm.Theresultshowsthe58.87%timeoverheadisreduced,andtimeoverheadcanbeenmaintainedstabilitywiththenumberofinitialdetectorincreasing.KeyWordsDetectorgenerationalgorithm,Bigdatasystem,Artificialimmunealgorithm,Map/Reduce1引言检测器生成算法是影响人工免疫系统（AIS，ArtificialImmuneSystem）检测性能和效率的重要因素之一。检测器生成算法的主要工作从初始检测器中筛选成熟检测器，使用匹配算法检查初始检测器与自体是否匹配，选择与所有自体均不匹配的初始检测器作为成熟检测器。Forrest等研究者给出了经典的检测器生成算法，并不断有研究者进行各种改进；为保证所选择成熟检测器对非自体的覆盖率，需要计算全部初始检测器与自体的匹配度后进行筛选，这使得筛选检测器的时间和空间开销与初始检测器的数量密切相关，在初始检测器数量较少的情况下，检测器生成算法能较快的完成筛选检测器的工作。将人工免疫算法用于大数据系统时，初始检测器的数量会达到几十万、甚至上亿的规模，筛选检测器所需的时间与空间开销将非常巨大，导致无法使用现有的人工免疫算法。现有检测器生成算法的研究中，主要是针对如何提高对非自体的识别率，优化自体和检测器的匹配规则，缺乏针对海量初始检测器时可计算性的考虑。因此在大数据系统中应用人工免疫算法时，如何提高筛选检测器的效率是急需解决的重要问题。并行化是提高算法执行速度的常用手段，通基金项目：国家自然科学基金(61300228)，浙江省自然科学基金(LY13F020012)，江苏省科技支撑项目(BE2013103)，深圳市科技项目(JCYJ20130401095947222)，作者简介：蔡涛，男，上海南汇人，1976年生，副教授，博士，主要研究领域为大数据、人工智能，CCF会员（E20-0012153M）。倪晓蓉，女，江苏盐城人，1989年生，硕士研究生，研究方向为人工智能逆光、大数据系统。王伟生，男，广东汕头人，1990年生，硕士研究生，研究方向为信息存储、大数据系统。牛德姣，女，河南叶县人，1978年生，硕士，博士研究生，副教授，研究方向为信息存储。过将复杂的计算过程分解为多个可以并行执行的部分，并分布到在多个处理核心上运行以提高执行的速度。但检测器生成算法中匹配规则的计算复杂度较低，传统并行计算方法所提高的计算效率很有限。而在初始检测器数量庞大时，影响筛选检测器时间和空间开销的主要因素是海量初始检测器所导致的巨大匹配检查次数，这是很典型的大数据应用。因此通过构建分布式的海量初始检测器存储系统，引入Map/Reduce模型设计新型的检测器快速筛选算法，利用分布存储节点的并行计算能力提高筛选海量初始检测器的效率是良好的选择。本文首先分析初始检测器数量巨大时，影响检测器生成算法执行速度的因素，在此基础上构建混合式的海量初始检测器快速筛选架构，设计海量初始检测器分区检查策略和成熟检测器集优化策略，实现对海量初始检测器的快速筛选，并实现面向大数据环境检测器快速筛选算法的原型系统，使用通用数据集进行测试与分析。2相关工作文献[1、2]给出了人工免疫系统中经典的否定选择算法、贪心检测器生成算法、r连续位匹配规则等；文献[3]引入多种群遗传算法，提高所生成检测器对非自体的覆盖率；文献[4、5]给出了检测器克隆选择算法；文献[6]设计了动态的克隆选择算法；文献[7、8]给出了抗独特型克隆选择算法，提高了生成检测器的效率；文献[9]引入聚类算法提高检测器的生成速度；文献[10]针对基于海明距离的匹配规则，给出了启发式检测器生成算法；文献[11]通过改变初始检测器的生成方法，提高生成成熟监测器的效率，提高成熟检测器检测非自体的效率和准确性。文献[12]设计了Map/Reduce计算模型，用于解决分布式存储系统中海量数据的计算问题；文献[13]给出了大数据系统的特征，针对流式计算系统，分析了目前大数据流式计算在低延迟、高吞吐、持续可靠运行方面存在的技术挑战；文献[14-16]给出了大数据流式计算系统的架构，以及大数据流式计算与复杂事件处理的关键技术；文献[17]介绍了Map/Reduce和传统数据库技术的融合。3海量初始检测器快速筛选算法检测器生成算法中需要使用匹配规则检查每个自体和每个初始检测器，才能选择出成熟的检测器，因此筛选检测器的效率与初始检测器和自体数量密切相关，所需进行匹配检查的次数与初始检测器和自体数量之间呈指数级递增关系。在大数据环境下，必然出现海量的初始检测器或自体，现有检测器生成算法无法在有限时间内完成筛选初始检测器的任务。因此在大数据环境下提高筛选检测器的效率是急需解决的关键问题。人工免疫算法中，自体与初始检测器是两个互补的集合；因此在大数据环境下，当自体的数量较少时，初始检测器必然非常巨大，反之亦然。我们针对初始检测器数量巨大的情况，设计快速的初始检查器筛选算法，利用多个节点的分布式计算能力提高与自体匹配检查的速度，再进行汇总，从而快速构建成熟监测器集。我们首先给出海量初始检测器快速筛选算法的结构，再给出各阶段的具体流程。3.1混合式海量初始检测器快速筛选架构我们针对大数据环境下海量初始检测器和有限自体的特点，适应初始检测器筛选算法的要求，通过初始检测器和自体的合理冗余与分布，构建适合快速筛选海量初始检测器的环境。首先改变现有检测器生成算法中集中存储初始检测器的方式，将海量初始检测器分散存储到Hadoop集群中的各个存储与计算节点中，为快速筛选初始检测器奠定基础。同时改变自体的存储方式，在每个存储与计算节点中均存储数量较小的自体集，为筛选初始检测器提供依据。由此我们设计了混合式的海量初始检测器快速筛选架构，如图1所示。初始检测器分区检查模块1自体集海量初始检测器分块1初始检测器分区检查模块2自体集海量初始检测器分块2初始检测器分区检查模块n自体集海量初始检测器分块n海量初始检测器集分布分布分布自体集冗余冗余冗余...海量初始检测器分区检查成熟检测器集优化图1混合式海量初始检测器快速筛选架构在Hadoop集群中分散存储海量的初始检测器，能利用存储与计算节点的并行计算能力提高检查初始检测器与自体匹配的效率；而在各个存储与计算节点中冗余保存数量相对较少的自体，能使得各个存储与计算节点都能分担检查初始检测器的任务。使用Map/Reduce模型，能将海量初始检测器筛选算法分为分区检查和汇总优化两个阶段，首先利用Hadoop集群中的存储与计算节点分布式检查海量初始检测器是否与自体匹配，并将相应结果提交给优化节点，优化节点再根据检查结果挑选最优的若干初始检测器构成成熟检测器集。3.2海量初始检测器分区检查策略利用Map/Reduce模型中Map阶段在各存储与计算节点中分布式并发执行的特点，在将海量初始检测器子集保存到各存储与计算节点的基础上，设计海量初始检测器分区监测策略。首先将数量有限的自体保存到存储与计算节点的内存中，依据匹配规则，与该存储与计算节点海量初始检测器子集中的检测器进行匹配检查，判断该海量初始检测器子集中的那些初始检测器能成为候选成熟检测器，同时将候选成熟检测器以及与自体之间的最大匹配值发送给优化节点，具体步骤如图2所示。其中detector_subset表示某个存储与计算节点中保存的海量初始检测器子集，self_set表示自体集。图2海量初始检测器分区检查策略海量初始检测器分区检查策略利用了Map/Reduce模型中Map阶段分布式执行的特点，在将海量初始检测器分区分布存储到集群中不同存储与计算节点的基础上，每个存储与计算节点中分别检查对应分区中初始检测器是否能成为候选成熟检测器，能利用大量存储与计算节点的分布式并行计算能力提高检查初始检测器效率；同时各存储与计算节点仅将候选成熟检测器提交给优化节点，能有效减少网络通信量。3.3成熟检测器集优化策略人工免疫系统中一般仅仅使用一定数量的成熟检测器检测非自体，各存储与计算节点筛选的候选成熟检测器通常远多与检测非自体所需的成熟检测器，但