《融合布谷鸟搜索和k均值算法的入侵检测方案》由会员分享，可在线阅读，更多相关《融合布谷鸟搜索和k均值算法的入侵检测方案（11页珍藏版）》请在金锄头文库上搜索。
1、融合布谷鸟搜索和 K 均值算法的入侵检测方案 魏万云 兰州资源环境职业技术学院 摘 要： 针对传统 K 均值聚类算法全局搜索能力差、需要设定初始聚类个数等问题, 提出一种结合新型布谷鸟搜索 (CS) 算法和自适应 K 均值算法的入侵检测模型 (NCS-AKM) , 为提高布谷鸟搜索算法的种群多样性, 引入类似差分进化策略有选择地对种群进行变异重组。利用 KDD Cup99 数据集构造训练数据和包含 4 个阶段的在线测试数据, 在第 3、4 阶段分别引入新的攻击。结果表明, 该检测模型能够准确地识别出新入侵, 对测试集中 4 种攻击类型的总体检测率高达 83.4% (各阶段:70.8% 89.9
2、%) , 误报率为 6.3% (各阶段:3.0% 11.5%) , 具有较高的检测性能和具有说服力的聚类结果。关键词： 布局鸟搜索算法; K 均值聚类算法; 入侵在线检测; 自动聚类数; 差分进化; 作者简介：魏万云 (1971-) , 女, 甘肃景泰人, 兰州资源环境职业技术学院副教授, 学士, 研究方向:电子技术, 通信技术。收稿日期：2017-02-27基金：国家 863 计划项目 (2012AA010904) Construction of Automatic Intrusion Detection Model Using K-means Algorithm Based on Nove
3、l Cuckoo Search OptimizationWEI Wan-yun Lanzhou Resources & Environment Voc-Tech College; Abstract： In consideration of the shortcomings of traditional K-means clustering algorithm, such as poor global search ability and artificial initial cluster number, an intrusion detection system using adaptive
4、 K-means algorithm optimized by novel Cuckoo Search algorithm (NCS-AKM) was proposed.In order to increase the diversity of CS algorithm, a similar differential evolution strategy was introduced to complete the individual variation.The KDD Cup99 dataset was applied to rebuild the training data and th
5、e fourphase testing data where a new attack was introduced respectively in third and fourth phase.The experiment indicates that NCSAKM system is sensitive to new attacks, obtaining satisfied detection performance as well as convincing clustering result, and the overall detection rate of four attacks
6、 is as high as 83.4% (range:70.8%89.9%) , while the false positive rate is 6.3% (range:3.0% 11.5%) .Keyword： cuckoo search (CS) algorithm; K-means; intrusion online detection; automatic clusters number; differential evolution; Received： 2017-02-270 引言近年来, 网络安全问题伴随着网络的广泛应用而日渐突出, 入侵数量迅猛增长, 入侵危害不断扩大, 为
7、了及时有效地发现入侵行为, 大量的入侵检测系统 (Intrusion Detection System, IDS) 也相继出现1。入侵检测技术通常分为误用检测和异常检测 2 类。误用检测方法基于已知攻击的特征信息对入侵行为进行检测, 难以识别未知攻击;异常检测技术通过学习用户行为习惯特征建立特征库, 根据用户当前行为与特征库中样本之间的相似性判断是否入侵, 能够检测未知攻击类型。对于大量的网络数据, 若要实现入侵检测, 根据数据之间的相似性对数据进行聚类很有必要。自适应 K 均值 (Adaptive K-means, AKM) 聚类算法是一种在入侵检测中应用广泛的异常检测技术2, 该方法根据数
8、据的相似程度将数据划分到不同类中, 从而标明网络数据是否正常。然而, 该算法对初始聚类中心敏感, 全局寻优能力较弱。因此, 学者将各类优化算法与 K 均值算法相融合来构建入侵检测系统, 以此提高 K 均值算法的速度。常用的优化算法有遗传算法3、粒子群算法4-5、人工鱼群算法6和模拟退火算法7等。然而, 这些优化算法都具有一些自身的缺陷, 且运算量较大, 不能很好地应用在实时入侵检测系统中。布谷鸟搜索算法 (Cuckoo Search, CS) 是 Yang 和 Deb 提出的一种新兴的元启发式算法8, 通过模拟布谷鸟寻窝产卵的行为而快速寻得最优解, 具有结构简单、全局寻优能力强、控制参数少等优
9、点, 在工程和自然科学领域中有着广泛应用9。本文针对传统的布谷鸟算法在收敛速度和精度等方面存在的不足, 提出基于类似差分进化算法的新型布谷鸟算法, 然后结合样本归类加速算法和自动决定聚类数算法并应用到在线入侵检测中。仿真实验表明, 该方法能有效避免早熟收敛问题, 其局部搜索能力显著提高, 对新攻击的识别能力大幅提升, 极大改善了入侵检测的效果。1 K 均值算法和布谷鸟搜索算法1.1 K 均值算法对于聚类样本 X=XiR, i=1, 2, , n, K 均值算法把其划分为多个不同类别 C=C1, C2, , Ck, 使得如下目标函数最小:其中, M j为类 Cj的聚类中心, d (X i, Mj
10、) 为样本 Xi到聚类中心 Mj的距离, J为所有样本到对应聚类中心的距离 (类内距离) 之和。1.2 CS 算法CS 算法初始时, 一定数量的鸟巢位置随机落在目标函数的可行解空间中, 迭代进化时, 适应度值最优的鸟巢位置得以保留, 鸟巢位置按照莱维机制进行更新得到新的鸟巢位置, 在此过程中, 有一定概率的鸟巢会被抛弃并另建新巢。设 Yl= (yl1, yl2, , ylp) (l=1, 2, , N) (p 为优化问题的维数) 为第 l 个鸟巢在第 t 次进化时的鸟巢位置, 每一次迭代中, 鸟巢位置按下式更新:其中, 为步长调节因子, 通常情况下取 =1。符号 为点对点乘法, L () 为服
11、从莱维分布的随机搜索向量, 即:进而可得:其中, Y best为当前时刻最优的鸟巢位置, u 和 v 为正态分布随机数, 即 uN (0, u) , vN (0, 1) , 且:位置更新后, 会随机生成一个随机数 r0, 1, 与鸟窝的主人发现外来鸟的概率 Pa对比, 若 rPa, 则对 Yl进行随机改变, 否则不变。本文中, 设定概率Pa=0.25。2 NCS-AKM 入侵检测模型本文基于自适应 K 均值算法 (AKM) 和一种新型 CS 算法 (NCS) 提出用于在线入侵检测的 NCS-AKM 模型, 其基本流程如图 1 所示。该模型主要包含样本归类加速算法和 NCS-AKM 算法 2 部
12、分, 具体描述如下。图 1 NCS-AKM 入侵检测模型流程图 下载原图2.1 样本归类加速算法传统 K 均值算法通过计算样本到各聚类中心的距离从而划分样本到不同类中, 事实上, 若已知任意 2 个聚类中心的距离, 则仅需计算样本到其中任意一个类中心的距离, 即可推出该样本一定不属于的那个类, 即:推论 1 对于样本 X 和 2 个聚类中心 Ma, Mb, 若 d (Ma, Mb) d (X, Mb) 。算法的实现步骤为:1) 从已有聚类中心中随机选取聚类中心 Mc, 计算样本 X 到 Mc的距离 d (X, Mc) ;2) 计算其他类的聚类中心 M 到 Mc的距离 d (M, Mc) , 若
13、 d (M, Mc) 2d (X, Mc) , 则舍弃该类;3) 重复步骤 1步骤 2, 直到找出聚类中心离样本 X 最近的类 Cbest;4) 将 X 归为此类并重新计算类 Cbest的聚类中心。2.2 NCS-AKM 算法本文提出的入侵检测模型的核心是 NCS-AKM 算法, 该算法对传统 CS 算法进行改进, 并结合 K 均值聚类个数自动确定算法10。2.2.1 改进型 CS 算法 (NCS) 传统 CS 算法受随机行走策略影响较大, 存在后期收敛速度慢、精度低、易陷入局部极小等不足11。为此, 文献12引入相应的变异机制可以提高其全局搜索的能力, 但是其引入的变异、交叉和选择操作过程较
14、为复杂, 不利于提高算法执行效率。本文受到差分进化方法的启发, 采用一种简化方式, 即在构建新鸟巢位置公式中融入其他鸟巢位置, 以此实现类似交叉变异的操作, 来提高种群的多样性。另外, 引入一个惯性权重 w 来降低迭代次数, 提高全局寻优的速度。在 t 次迭代时, 随机选取 q (qm) 个鸟巢Y j, j=1, 2, , q, 对于鸟巢 Yj, 在所有鸟巢中随机选取 4 个与之不同的鸟巢 Yr1, Yr2, Yr3, Yr4, 用于构建新巢, 其位置为:其中, rand (0, 1) 为0, 1上服从均匀分布的随机数, Y best为当前最优鸟巢位置, 。惯性权重 w 的引入, 可使 CS
15、算法有扩展搜索空间的趋势, 有能力搜索新的区域, 实验表明, 较大的惯性权重 w 有利于跳出局部最优, 进行全局寻优;较小的 w 值有利于局部寻优, 加速算法收敛。为了平衡算法的全局和局部搜索能力, 惯性权重 w 的值应随着迭代次数的增加而递减。然而, CS 算法在实际搜索过程中是非线性的, 惯性权重线性递减策略不能反映实际的优化搜索过程。因此, 本文设定惯性权重根据迭代次数非线性递减: , 其中 iter 为当前迭代次数。然后, 对选取的种群Y j及其变异种群 进行个体间交叉操作:其中 CR0, 1为交叉概率, 本文设定交叉概率 CR=0.85。令备选鸟巢, 利用下式通过适应度值评估备选鸟巢
16、是否优于 Yj:2.2.2 NCS 算法中的个体编码和适应度函数本文中鸟巢位置由 k 个聚类中心构成, 为 kp 维矩阵, 每个鸟巢有一个适应度函数。鸟巢的编码结构为:其中, z ij为第 i 个聚类中心的第 j 维变量。为寻求最优聚类结果, 要同时实现类中距离最小和类间距离最大, 故本文选用的适应度函数为:其中, J 为 K 均值算法的目标函数, 表示类内距离。d (Z) 为惩罚因子, 表示各聚类中心的距离之和, 用于使适应度函数能平衡类中距离和类间距离:2.2.3 自适应 K 均值聚类数的确定本文采用文献10中提出的 BWACR 指标来自动获取 K 均值算法的最佳聚类数, 该指标为:其中, BWACR (r, i) 为第 r 类的第 i 个样本的聚类有效性, n r, ns分别表示第r, s 类的样本个数, X iq表示第 r 类的第 i 个样本的第 q 维, 通过比较不同聚类数的平均 BWA
