基于自适应遗传算法的混合特征选择方法

裴作飞 李兆玉 王云锋 姚立霜

(重庆邮电大学通信与信息工程学院 重庆 400065)

0 引 言

随着大数据时代的到来，有许多新兴的应用出现，如社交媒体服务、高分辨图像、文档数据分析等。这些大数据应用不仅包含冗余数据和低相关性的特征，并且维度过高导致维度灾难使得数据处理的复杂程度急剧增加，严重影响和限制数据分析和挖掘的性能[1]。为了解决上述问题，特征选择在不降低预测模型性能的前提下，按一定的选择标准从输入特征中选择相关特征子集，减少数据维度，消除分类性能差的特征，提高学习算法的性能[2]。

特征子集选择方法可分为过滤式、封装式和嵌入式。过滤式方法是在分类算法训练之前根据数据集自身的特性选择一个最优的特征子集，去除不必要的特征[3]。封装式方法利用分类算法的分类结果作为评价特征子集的指标，选择特征子集[4]。嵌入式方法将特征选择的过程作为分类算法的一部分，例如分类与回归树算法[5]。此外通过结合遗传算法(GA)[6-8]、蚁群算法(ACO)[9]、人工蜂群算法(ABC)[10]和模拟退火算法[11]等搜索策略，加快搜索进程选择最优特征子集。Sheen等[12]利用决策树作为分类算法，对比了三种过滤方法(CS、IG和Relief-F)选择出来的不同特征子集在KDDCUP99上的分类正确率，实验表明三种算法将KDDCUP99数据集的特征约减到15维度时检测率最好。陈友等[13]比较了过滤方法和封装方法，实验表明采用基于SVM分类器作为封装方法在TPR、FPR上的性能优于基于CFS的Filter特征选择方法。CFS过滤方法则在模型构建时间上更短，耗用更少的计算资源与存储资源。Schenkel等[14]提出将互信息与基于贝叶斯分类算法的封装方法组成混合特征选择算法，该方法对于复杂模式效果较好，在分类性能和对特征数目约减能力上有较好表现。

基于上述研究背景，针对数据中冗余和相关度低的特征，首先通过卡方统计方法对数据集进行过滤。其次采用LightGBM分类器结合自适应遗传算法的封装方法，搜索分类效果好的特征子集，提高入侵检测的检测效果并缩短SVM分类算法检测时间。CS-GA混合特征选择算法如图1所示。

图1 基于CS-GA的混合特征选择流程

1 CS-GA混合特征选择算法

1.1 基于CS过滤算法

在CS过滤算法特征选择之前，对入侵检测数据集中离散型特征进行one-hot编码，对连续型特征进行标准化处理，即每个特征值featurei减去每个特征的平均值μi再除以特征值的标准差σi，计算公式如下：

(1)

数据预处理之后，采用CS算法对数据特征进行过滤。针对入侵检测问题,通过χ2检验每个特征与类别之间的独立性并将入侵检测中每个特征按χ2的统计值进行降序排列，每个特征所得到的χ2统计值越大，说明该特征在入侵检测中分类效果越好且与类的相关性越强。因此，将每个特征与类别c之间的卡方公式表示为：

(2)

(3)

式中：f表示入侵检测中某一个特征的有或无；c表示类别，c等于0表示正常类型，1表示异常类型；N是观察值，例如在入侵检测数据集中N11表示选择该特征且为异常类型的样本数量；E是期望值，假设在入侵检测数据中的特征与类别c互相独立；Rf是其特征f在数据集中的样本数；Ic是特征f在类别c中的样本数。式(2)-式(3)只支持入侵检测正常和异常的2分类研究。

CS算法可以去除相关性低的特征，但没有考虑特征之间的交互作用，为了进一步降低特征维度，提高算法的性能，将过滤后的特征子集采用LightGBM作为封装方法进一步约减特征。

1.2 基于LightGBM结合自适应遗传算法的封装方法

1.2.1 种群个体编码

通过CS过滤算法对入侵检测相关性低的特征过滤之后，对剩余特征数据集进行随机初始化种群，采用二进制编码对种群个体进行编码。入侵检测数据中有41个特征，所以染色体的大小为41。其中染色体上的每个基因值可以为0或1。0表示染色体中该基因不存在，没有选择该基因对应的特征；1表示染色体中该基因存在，即表示选择该基因对应的特征。如一条染色体g=[1,0,1,0,1,0,…,0]，表示选择第一个、第三个和第五个特征。

1.2.2 适应度函数计算

遗传算法本身就可以作为一种特征选择算法，能够发现并消除冗余特征，但遗传算法性能的好坏往往取决于适应度函数的定义。为了更大化减少特征，获得分类效果更好的特征，可以采用LightGBM算法作为GA的适应度函数计算。LightGBM分类算法在入侵检测问题上不需要注重特征值的大小，只需要将字符映射成数值型就可以进行训练[15]。因此该算法作为封装算法具有更快的训练效率和更好的准确率。为了在获得较高分类效果的同时降低特征维度，改进的适应度函数定义如下：

(4)

式中：L(x)为LightGBM分类算法对于所选特征向量x的分类准确率；Fn表示特征维度个数；α∈[0,1]，当α等于1时表明适应度函数值取决于L(x)，当α等于0时适应度函数值取决于Fn。因此可以调节α的值来获得L(x)与Fn之间的平衡，选择分类效果好并且维度相对较低的特征子集。

1.2.3 选择算子

传统遗传算法选择算子采用轮盘赌策略，该策略有一定概率选择到分类效果差的种群个体，导致选择的特征子集不好，影响遗传算法性能。因此，采用锦标赛选择策略，选择适应度好的种群个体。该策略从种群中一次选择出3个个体，选择最优的1个种群个体进入后代种群。重复此操作，直到新的种群大小达到原始种群大小。

1.2.4 交叉和变异算子

交叉的目的是将父代种群个体中的优秀基因遗传给子代保证遗传算法的搜索能力和稳定性，变异的目的是防止遗传算法过早收敛并且可以让遗传算法在局部的随机搜索能力更强。在CS-GA中使用单点操作方法对种群个体进行交叉和变异。GA交叉率和变异率往往根据实际情况和经验取值，但问题是交叉率和变异率取值过大，会导致个体适应度波动较大。交叉率和变异率取值小，会导致搜索缓慢早熟收敛。因此，采用自适应的思想对交叉算子与变异算子进行改进：

(5)

(6)

式中：Pc1、Pc2是交叉率；Pm1、Pm2是变异率；fmax和favg为每代群体中最大适应度值和平均适应度值；f′为2个交叉个体中较大的适应度值；f为变异个体的适应度值。由式(5)-式(6)可知当f和f′小于favg时，使用取值大的Pc1和Pc2提高遗传算法的搜索能力。当遗传算法到后期和f大于favg时通过自适应方法降低交叉率和变异率，保证遗传算法的稳定性并逐渐向最优解靠近。因此，采用自适应的思想改进交叉和变异算子可以使遗传算法具有更好的适应度和全局收敛性。

1.2.5 算法终止条件

当CS-GA达到最大迭代次数，或者当前种群适应度值达到0.999 9时，算法终止。

2 实验及结果分析

2.1 实验数据

实验使用KDDCUP99 10%数据集，在入侵检测数据中将类标识属于正常记录的数据设置为0，其他攻击类型数据设置为1。训练样本与测试样本分别提取自训练数据集kddcup.data_10_percent_corrected.gz和测试数据集corrected.gz。将全部训练数据集作为输入数据用于三种算法进行特征选择，此外在训练数据集与测试数据集中随机抽样出2组10 000条训练数据和6组6 000条测试数据用于测试特征子集的性能。

2.2 实验设置

实验的编程环境为Ipython Notebook，硬件环境为Intel Core i5-7500@3.40 GHz，RAM 8 GB，Windows 10 64位操作系统， CS-GA算法的参数设置如表1所示。

表1 CS-GA算法的参数设置

表1中遗传算法种群大小一般在20～50之间，这里根据数据集的大小取50，染色体基因数与数据特征维度个数均取41。如图2所示，最大进化代数选择80时，种群评价适应度值最好。自适应遗传算法的交叉率和变异率根据经验数据设定，在前期Pc1和Pm1取值大一些，保证算法搜索能力，在后期Pc2和Pm2小一些，保证算法稳定性。

图2 CS-GA算法进化曲线

2.3 实验结果及性能对比

2.3.1 CS-GA、GA、Gini-GA选择结果对比

为了验证CS-GA在特征选择上的优势，首先将全部训练数据集作为输入数据，用于CS-GA、GA、Gini-GA进行特征选择实验。GA采用未改进的自适应遗传算法用作特征选择，Gini-GA采用Gini(基尼系数)对全部特征过滤，然后通过未改进的自适应遗传算法搜索特征子集，未改进的自适应遗传算法的参数和CS-GA一致。由于遗传算法为不确定搜索算法，所以对3种算法进行20次选择实验，并将得到的特征子集保存。最后，将第一组训练数据和第一组测试数据作为输入数据，通过SVM分类器测量特征子集的检测率、误报率和测试时间。表2给出了3种算法20次特征选择结果的平均性能参数。

表2 3种算法20次特征选择结果平均性能参数

可以看出，CS-GA作为一种相关性过滤算法，在特征选择上速度较快，比其他两种算法具有更短的建模时间。总的来说，CS-GA作为混合特征选择算法在特征维度的约减能力上好于GA和Gini-GA，在检测率和误报率上也比GA和Gini-GA要好。传统自适应GA作为特征选择算法，选择出来的特征子集在检测率、误报率、维度等性能指标上无明显优势。

2.3.2 特征选择结果及性能对比

在CS-GA、GA和Gini-GA 20次特征选择结果中结合检测率、误报率和维度，选择出一组综合性能最好的特征序列用于入侵检测问题研究，如表3所示。为了充分验证最终选择的特征子集的好坏，通过第2组训练数据和6组测试数据作为输入数据，采用支持向量机分类算法分别测试3种算法特征子集在6组测试数据中的性能。

表3 特征选择结果

如图3、图4所示，All-SVM表示选择全部41个特征，通过SVM分类器测量其检测率和误报率。结果显示，入侵检测采用全部特征时其检测率和误报率效果最差。GA虽然可以对特征进行降维，但是在检测率和误报率上与All-SVM使用全部特征子集性能相当。Gini-GA中基尼系数对于入侵检测问题中处理连续型数值特征的约减能力上不如CS-GA，CS-GA在特征约减能力上效果最好。CS-GA选择出来的特征子集在6组不同的测试集上的检测率和误报率上也明显优于其他对比算法。

图3 6组测试样本的检测率

图4 6组测试样本的误报率

图5比较了4种特征子集在SVM分类器上的测试时间。结果显示，采用全部特征的All-SVM需要更长的测试时间，而CS-GA将入侵检测数据集中41个特征维度约减到5维，极大地降低分类器的训练难度。CS-GA选择出来的特征子集相对于其他算法在基于SVM算法上测试时间最短，在一定程度上解决入侵检测实时性问题。

图5 6组测试样本的测试时间/s

3 结 语

本文通过卡方算法对入侵检测数据集中冗余特征进行过滤，采用LightGBM分类器结合自适应遗传算法构成混合特征选择方法，搜索分类效果好的特征子集。实验结果表明：CS-GA能够缩减SVM分类算法的测试时间，有效删除冗余特征和相关度低的特征，提高入侵检测的检测性能，降低误报率。后续会考虑将CS-GA和其他过滤算法结合，处理不同类型数据特征，进一步提高算法的特征约减能力。