一种基于自体集层次聚类的否定选择算法

摘要：

否定选择算法是用于产生人工免疫检测器的重要算法,然而传统的否定选择过程需要将随机生成的候选检测器与全部自体数据进行匹配以排除识别了自体的无效检测器,该匹配过程导致检测器的生成效率过低,极大地限制了免疫算法的应用.为此,文中提出了一种基于自体集层次聚类的否定选择算法CB-RNSA.算法首先对自体数据进行层次聚类预处理,然后用聚类中心取代自体数据点与候选检测器进行匹配,以减少距离计算代价.在生成检测器的过程中,候选检测器被限定在非自体空间的低覆盖率区域内,以降低检测器冗余.对检测器的非自体空间覆盖率进行了概率分析,给出了中止生成检测器的条件,该条件较传统的预设检测器数量的中止条件更为合理.理论分析表明CB-RNSA的时间复杂度与自体集规模无关,从而解决了经典的否定选择算法的时间复杂度随自体数量呈指数增长这一难题,极大地提高了大自体样本空间下的检测器生成效率.对比实验结果表明:在相同的实验数据集与期望覆盖率下,CB-RNSA的检测率比经典的RNSA与V-detector算法分别提高了12.3％与7.4％,误警率分别降低了8.5％与4.9％,产生检测器的时间代价分别降低了67.6％和75.7％.

关键词：人工免疫系统、否定选择算法、人工免疫检测器、聚类、覆盖率

所属期刊栏目：43

资助基金：国家自然科学基金60873246;教育部重大项目培育基金708075;教育部博士点基金20070610032

在线出版日期：2014-03-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：611-625