网络入侵检测中K近邻高速匹配算法研究

摘要：

K近邻匹配算法被广泛应用于网络入侵检测工作,当样本数量和特征维度显著增加时,基于Ball-tree结构的K近邻匹配算法查询效率显著降低,不能满足实时性检测需求.针对这一问题,文章提出一种基于“裁剪树”的K近邻高速匹配算法.首先对全部样本集进行裁剪,构建一棵最小规模的“裁剪树”,同时保证“裁剪树”最大限度地保留原始样本集在多维空间内的分布形态;其次进行K近邻查找时,在“裁剪树”内快速定位K_g(2≤K_g≤K)个初始近邻点,利用初始近邻点与目标点的空间距离作为剪枝半径对搜索二叉树进行K近邻查询.与原始K近邻匹配算法相比,改进算法的初始近邻不在固定位置,而是动态位于目标点周边,有效缩短了剪枝距离,在查询过程中有更多的样本点被剪枝删除,显著减少计算量,提升了查询效率.实验结果表明,改进的K近邻高速匹配算法在处理高维、海量样本数据时,维持较高查询效率,部分样本集增速比达到93.81％.

关键词：入侵检测、K近邻、匹配、裁剪树、欧氏距离

分类号：TP309(计算技术、计算机技术)

资助基金：辽宁省自然科学基金[2019-ZD-0167,20180550841,2015020091;中央高校基本科研业务费[3242017013;公安部技术研究计划课题[2016JSYJB06

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

页数：共10页

页码：71-80