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

A negative selection algorithm based on hierarchical clustering of self set

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

Negative selection algorithm（NSA） is an important method of generating arti-cial immune detectors.However,the traditional NSAs aim at eliminating the self-recognized invalid detectors,by matching candidate detectors with the whole self set.The matching process results in extremely low generation e-ciency and signi-cantly limits the application of NSAs.In this paper,an improved NSA called CB-RNSA,which is based on the hierarchical clustering of self set,is proposed.In CB-RNSA,the self data is-rst preprocessed by hierarchical clustering,and then replaced by the self cluster centers to match with candidate detectors in order to reduce the distance calculation cost.During the detector generation process,the candidate detectors are restricted to the lower coverage space to reduce the detector redundancy.In the paper,probabilistic analysis is performed on nonself coverage of detectors.Accordingly,termination condition of the detector generation procedure in CB-RNSA is given.It is more reasonable than that of traditional NSAs,which are based on prede-ned detector numbers.The theoretical analysis shows the time complexity of CB-RNSA is irrelevant to the self set size.Therefore,the di-cult problem,in which the detector training cost is exponentially related to the size of self set in traditional NSAs,is resolved,and the e-ciency of the detector generation under a big self set is also improved.The experimental results show that：under the same data set and expected coverage,the detection rate of CB-RNSA is higher than that of the classic RNSA and V-detector algorithms by 12.3% and 7.4% respectively.Moreover,the false alarm rate is lower by 8.5% and 4.9% respectively,and the time cost of CB-RNSA is lower by 67.6% and 75.7% respectively.