改进麻雀搜索算法的入侵检测特征选择

刘 涛，蒙学强

(1.西安科技大学 通信与信息工程学院，陕西 西安 710600；2.西安科技大学 西安市网络融合通信重点实验室，陕西 西安 710600)

0 引 言

随着互联网技术的发展，网络威胁也在逐步增加，为了提高网络的安全性，入侵检测技术一直是网络安全研究的热点。由于入侵检测数据集特征数量大，存在冗余特征，其不仅降低了分类的准确率并且增加了计算时间[1]。近年来，受自然现象启发的群智能优化方法为解决特征选择问题提供了一种新方法。网络入侵检测的特征选择问题可以转化为优化问题，利用优化算法获取特征子集进行入侵检测[2]。Alzub等[1]提出了二进制灰狼优化结合SVM的特征选择算法。Singh等[3]使用混沌花朵授粉算法进行相关性特征选择。Alsaleh等[4]将樽海鞘群算法结合XGBoost和Naïve Bayes进行特征选择。Liu等[5]使用并行计算的改进群集蜘蛛优化算法进行特征选择。

Xue等[6]提出了麻雀搜索算法(SSA)，该算法具有求解精度高、收敛速度快的优势，但也存在容易陷入局部最优的缺陷，对此众多学者提出了不同的改进方法。吕鑫等[7]利用改进Tent映射和高斯变异提升算法的全局寻优性能。Yang等[8]利用佳点集初始化种群，提出一种博弈掠夺机制和自毁机制的更新方式，充分利用种群最优个体的信息。Yuan等[9]使用重心反向学习初始化种群，加入可变学习系数和突变因子进行位置更新，增强了全局搜索能力。Ma等[10]提出了统一多样化定向策略初始化种群，使用危险转移策略和动态进化策略增强全局探索能力。

以上文献从多个方面对SSA进行了改进，但针对不同优化问题存在收敛精度低，收敛速度慢等不足，本文提出一种混合策略改进的麻雀搜索算法(HISSA)，将其应用于入侵检测的特征选择问题中，在CIC-IDS2017数据集上进行实验，对原有的77个特征进行提取，平均保留了7.6个特征，并且准确率平均达到了99.5%，验证了改进算法更好的寻优能力。

1 原始麻雀搜索算法

麻雀搜索算法是根据麻雀群居行为提出的智能优化算法，通过模拟麻雀捕食和被捕食行为建立模型。根据分工的不同将麻雀分成发现者、跟随者和警戒者。

假设由N只麻雀组成的空间为X=[x(1，i)，x(2，i)，…，x(N，i)]T， 其中，i=1，2，…，d，d为维度。

发现者位置更新描述如式(1)所示

(1)

跟随者位置更新描述如式(2)所示

(2)

警戒者位置更新描述如式(3)所示

(3)

2 改进麻雀搜索算法

2.1 改进的Circle映射初始化种群

在初始化阶段，麻雀个体随机生成，种群分布不均匀，容易在某一区域出现聚集现象，导致彼此间麻雀个体差异较小，加入混沌映射初始化可以使该问题得到改善。常见的映射方法包括Logistic混沌映射、Tent混沌映射、Sine映射、Circle映射等。由于Logistic映射在(0，1)区间内呈切比雪夫分布[11]，在(0.9，1)区间内分布密集，在整个空间内分布不均匀。Tent映射虽然在(0，1)区间内分布均匀，但是存在小周期和不稳定周期点[12]。Sine映射在(0，1)区间内集中分布在(0，0.1)和(0.9，1)内，其处于混沌状态的参数空间较窄[13]。Circle映射相对而言更加稳定，且均匀性也较好。

传统的Circle映射主要集中分布在(0.2，0.5)内，如图所示，在此对Circle映射稍作改进，使其分布更为均匀。

原Circle映射表达式如式(4)所示

(4)

改进后的Circle映射如式(5)所示

(5)

式中：n为解的维度，取n=2000，原始Circle映射和改进Circle映射解维度分布图如图1所示。

由图1可知，改进后的Circle映射分布更为均匀，使用改进Circle映射初始化麻雀种群，能够使种群分布更为均匀，增加种群分布差异性的同时减少了陷入局部最优的概率。

2.2 发现者位置更新的改进

原始麻雀搜索算法中，随着迭代次数的增加，搜索范围不断减小，发现者在每一维上都在变小，在搜索初期容易陷入局部最优。

本文结合秃鹰搜索算法中搜索阶段鹰的移动模型[14]，采用螺旋飞行的方式对发现者位置进行更新。如式(6)所示

(6)

改进后的公式如式(7)所示

(7)

其中，γ为动态自适应权重，其随着迭代次数的增加不断增加。通过不断迭代对发现者位置更新算子进行调节，在搜索前期γ值较小，位置更新较慢，便于全局搜索；在后期γ值变大，算子下降速率变快，搜索精度得到提升。并且加入螺旋移动方式，增加发现者在每次位置更新时的搜索路径，提升算法的全局寻优能力。

2.3 单纯形法

单纯形法是一种直接、快速的求解最优值的方法，具有收敛速度快，适用范围广的优点。基本思想是在一个搜索域内寻找一个点，判断是否为最优解，如果不是则由当前解生成一个新解，再进行判断，不断迭代直到找到最优值。

用单纯形法对麻雀位置进行优化，能够进一步提升麻雀算法的搜索能力[15]。首先按适应度值对麻雀种群进行排序，选择最优位置和次优位置Xbest和Xnext，计算其中点位置Xmedium。同时记录对应位置的适应度值fbest和fnext，其中Xmedium=((Xbest+Xnext))/2。

其次记录适应度最差的n个麻雀的位置Xworst，进行反射操作，让其向相反方向移动，增大搜索范围。反射点的位置为Xreflex，适应度为freflex

Xreflex=Xmedium+α·(Xbest-Xworst)

(8)

其中，α为反射系数，这里设为1。

对反射点的适应度值进行判断，分为以下3种情况：

(1)如果freflex

Xexpand=Xmedium+γ·(Xreflex-Xmedium)

(9)

其中，γ为扩张系数，这里设为2。

如果fexpand

(2)如果freflex>fworst， 说明反射方向不正确，对该位置麻雀进行外收缩，让较差位置的麻雀更接近最优位置，增强局部探索能力。记外收缩后麻雀的位置为Xec，适应度为fec

Xec=Xmedium+β·(Xworst-Xmedium)

(10)

其中，β为收缩系数，这里设为0.5。

如果fec

(3)如果fbest

Xic=Xmedium+β·(Xreflex-Xmedium)

(11)

其中，β为收缩系数，这里设为0.5。

如果fic

本文通过单纯形法对适应度较差的麻雀个体进行优化，避免其陷入停滞状态，提升了搜索性能，增强算法的全局寻优能力。

2.4 小孔成像反向学习策略

为了解决多数群智能优化算法容易陷入局部最优的问题，有学者提出了反向学习的方法。对于当前解取其反向解，在已有解决方案的同时，又考虑到了相反的解决方案。本文选用一种小孔成像的反向学习策略[16]，求得当前最优解的反向解，增大解空间的范围，增强算法逃离局部最优的能力。

小孔成像反向学习的原理如图2所示。

图2 小孔成像原理

由小孔成像的原理可得

(12)

(13)

通过调整小孔屏与接收屏之间的距离，改变n的大小，可以得到位置更优的解，逃离局部最优。

通过小孔成像反向学习策略，对每次迭代后产生的最优个体麻雀位置进行更新，不仅扩大了最优个体的搜索区域，同时也减小了陷入局部最优的问题。

2.5 HISSA算法流程

步骤1 利用改进的Circle映射初始化种群，设置种群数量N，发现者比例PD，警戒者比例SD，最大迭代次数itermax，预警值ST，搜索上界ub，搜索下界lb，维度d。

步骤2 计算麻雀个体适应度，并进行排序，记录最优位置、次优位置和最差位置的麻雀分Xbest、Xnext和Xworst，其适应度分别为fbest、fnext和fworst。

步骤3 根据式(7)更新发现者位置。

步骤4 根据式(2)更新跟随者位置。

步骤5 根据式(3)更新警戒者位置。

步骤6 进行单纯形法操作。首先记录最优和次优的中点位置Xmedium及其适应度值，选择适应度较差的n个麻雀，按照式(8)进行反射操作，记录适应度freflex。

步骤7 比较fbest、fnext、fworst和freflex的大小，如果freflexfworst，按照式(10)进行外收缩操作；如果fbest

步骤9 计算更新后的适应度值，如果优于当前位置，则进行替换。

步骤10 判断是否达到最大迭代循环次数，如果是则进行下一步，否则跳转到步骤2。

步骤11 算法结束，输出并记录最优结果。

2.6 时间复杂度分析

时间复杂度是衡量算法性能和计算成本的重要指标之一。假设空间维度为d，求解适应度函数所需时间为f(d)， 则SSA的时间复杂度为O(f(d)×d)。 HISSA的时间复杂度分析如下：

(1)假设麻雀种群数量为N，初始化参数的时间为t1，在每个维度中生成混沌值的时间为t2，时间复杂度为：O1=O(t1+N×(f(d)+t2×d))。

(2)发现者比例为PD，每个维度位置更新所需时间为t3，改进发现者位置更新方式的时间复杂度为：O2=O(PD×N×t3×d)。

(3)跟随者和警戒者更新方式未做更改，因此时间复杂度与SSA相同，分别为O3和O4。

(4)假设每个维度的反射、扩张、外收缩和内收缩所需的时间是t4、t5、t6、t7，单纯形优化后的时间复杂度为：O5=O(N×(t4+t5+t6+t7)×d)。

(5)假设为每个维度生成反向解所需的时间为t8，小孔成像反向学习策略优化后的时间复杂度为：O6=O(N×t8×d)。

设最大迭代次数为itermax，则HISSA的时间复杂度为：O′=O1+itermax×(O2+O3+O4+O5+O6)=O(f(d)×d)。 因此，HISSA和SSA具有相同的时间复杂度。

3 实验与结果分析

3.1 算法测试

3.1.1 参数设置说明

为了验证HISSA的性能，本文选用基本灰狼优化算法(GWO)、鲸鱼优化算法(WOA)、正余弦优化算法(SCA)、粒子群算法(PSO)和麻雀搜索算法(SSA)进行对比实验。将种群规模N和最大迭代次数itermax作为每种算法共同的参数。设N=30，itermax=500，且每种算法均独立运行30次。每种算法各自的参数见表1。

3.1.2 基准测试函数介绍

为了验证改进算法的性能，本文选取6个基准测试函数进行实验，见表2，其中f1～f4为单峰函数，f5～f6为多峰函数。

表2 基准测试函数

3.1.3 算法性能结果对比分析

表3为6种算法在6个基准测试函数上30维的寻优实验结果。

表3 基准测试函数优化结果对比

由表3可知，对于单峰函数f1、f2、f3、f4及多峰函数f5，HISSA可以达到理论最优解0。对于f1、f2、f3、f4的求解，SSA虽然能够达到理论最优解，但并不稳定，HISSA在保持原算法性能的基础上极大提高了稳定性；对于f5，SSA达到了理论最优解，HISSA仅在收敛速度上有所提升；对于f6，WOA、SSA和HISSA均能够达到理论最优解，但WOA稳定性逊于后两者。通过分析可知，HISSA在收敛速度，收敛精度和稳定性等方面均高于其它算法，因此本文提出的HISSA具有明显优势。

3.1.4 收敛曲线分析

各算法独立运行30次的收敛曲线如图3所示。

图3 收敛曲线

由图3可知，对于多数函数的求解，SSA的求解精度优于其它算法。HISSA在其基础上大幅提高了收敛速度，且更容易跳出局部最优范围。

3.1.5 Wilcoxon秩和检验

本文采用Wilcoxon秩和检验对每一次计算结果进行独立分析，在P=5%的显著性水平下对比与其它算法的差异。当P值小于5%时，拒绝假设，表明两种算法之间存在明显差异；当P值大于5%时，接收假设，表明两种算法寻优能力较为相似。表4为在6个基准测试函数下，HISSA与其它算法之间的优化结果对比，如果两种算法同时得到最优值，无法进行比较，则使用NaN表示不适用。C表示对比结果，“+”表示HISSA优于其它算法，“=”表示HISSA等同于其它算法，“-”表示HISSA劣于其它算法。

表4 基准测试函数优化结果对比

3.2 入侵检测特征选择问题

3.2.1 数据预处理

本实验选用CIC-IDS2017数据集，原始文件包含5天的数据流量，分为8个文件。首先将其合并为1个文件，文件共计2 830 743条流量数据。除去时间戳，端口信息等共包含77个特征，及1个标签列。标签包含正常类型和14种攻击类别，主要分布情况见表5。

表5 数据集分布

(1)由于数据集中存在部分NaN值和Infinity值，在训练时会报错，但其所占比例极小，因此直接删除进行数据清洗，处理后的数据大小为2 827 876。

(2)为了方便模型分类，将所有的Dos攻击、Web攻击和暴力攻击归为一类，按0～9进行编码。

(3)由于不同特征之间数据差值较大，容易造成特征空间内部分样本点受较大特征值的影响，将特征数值按式(14)归一化到[0，1]区间内

(14)

其中，x′i表示归一化后的值，xi表示初始值，xmin表示该特征的最小值，xmax表示该特征的最大值。

(4)由于数据集存在不平衡现象，正常数据达到了200多万条，而最少的攻击类型仅为11条。直接训练时容易过度拟合多数类样本忽略少数类样本的特征，从而导致分类器性能不佳。因此本文使用随机欠采样抽取多数类样本，使用SMOTE过采样生成少数类样本，最终抽取50 000条数据进行实验。

3.2.2 特征选取标准

在改进麻雀算法的特征选择方法中，麻雀种群初始化位置对应一个随机的特征，麻雀个体在特征空间内随机搜索，对获得的特征子集进行评估。如果原始位置的值大于0.5，则选择该特征，表示为“1”；否则放弃该特征，表示为“0”。如果所有值都小于0.5，则选择值最大的麻雀位置。将特征数量与F1分数相结合做为适应度函数，在保证F1分数高的情况下，特征数量尽量少。最后将选择的特征子集使用CatBoost进行分类，得到最终的分类结果。

3.2.3 CatBoost算法

CatBoost算法是继XGBoost、LightGBM之后第三个基于GBDT改进的算法，其训练参数少且准确率较高，并且能够高效合理地处理类别型特征，充分利用特征之间的联系，并且使用对称树结构，有效的减少了过拟合现象，具有较好的鲁棒性。

参数设置见表6。

表6 CatBoost参数

3.2.4 实验结果分析

SSA特征选择结果和HISSA特征选择结果见表7和表8，图4为两种算法选择的特征对比。

表7 SSA特征选择结果

表8 HISSA特征选择结果

图4 两种算法特征选择对比

从表7和表8可知，SSA算法平均保留了13.3个特征，平均准确率为97.97%，平均F1分数为97.14%；HISSA算法平均保留了7.6个特征，准确率达到了99.5%，F1分数达到了98.48%，与原算法相比减少了5.7个特征，提升了1.53%的准确率与1.34%的F1分数。综合上述指标来看，改进算法在模型中能够取得更优的目标函数值，加快了分类效率，在减少特征维度的同时进一步提高了准确率。

4 结束语

本文针对入侵检测中数据特征维度高的问题，提出了一种改进麻雀算法的特征选择方法。利用改进的Circle映射初始化种群；在位置更新机制中引入螺旋探索更新方式；最后使用单纯形法及小孔成像法分别更新较差和最优麻雀位置，有效改善了原算法收敛速度慢、精度低、容易陷入局部最优等问题。通过与其它5种算法的对比测试，表明改进算法的收敛性能更佳，鲁棒性更强。在CIC-IDS2017数据集上进行特征选择实验，结果表明该算法极大减少了特征维度，并且达到了极高的准确率，验证了算法的可行性，对特征选择问题有着重要的参考价值。