基于改进蝗虫优化算法的特征选择方法

图1 IGOA算法流程图

Fig.1 Flow chat of IGOA algorithm

3 基于IGOA的特征选择方法

特征选择问题可理解为一个多目标优化问题，即选择尽可能少的特征数使分类器获得尽可能高的分类准确率.本文利用IGOA算法来解决这一实际优化问题，提出一种基于IGOA的特征选择方法，具体算法流程如图2所示.

图2

图2 基于IGOA的特征选择流程图

Fig.2 Flow chart of feature selection based on IGOA

在特征选择问题中，IGOA种群中的每个个体都代表数据集中的一组特征组合，也即是所谓的特征子集.个体维度则由数据集中的原始特征数决定，并且每个个体向量均由0和1组成，1表示选取了对应的特征属性，0则表示该特征属性未被选取.在IGOA种群初始化时个体各维度的取值为[0,1]的随机数，因此为使种群中的个体向量均为0和1组成，本文取个体各维度值大于0.65的值为1，其余值置0，得到由0和1组成的个体向量.为了以尽可能少的特征数获得尽可能高的分类准确率，评价个体好坏的适应度函数需同时考虑这两个因素，因此本文采用的适应度函数定义如下^[14]：

F i t n e s s = α ⋅ γ_{R}^{D} (D) + β ⋅ \frac{|R|}{|N|}

（10）

其中， $γ_{R} (D)$ 为分类器错误率(本文采用KNN分类算法来评价特征子集的优劣（取K=5）)， $|R|$ 为当前个体所包含特征数， $|N|$ 为数据集中原始特征数， $α$ 和 $β$ 为平衡分类准确率及特征子集长度的协调参数，且 $β = 1 - α$ ， $α ∈ [0,1]$ ，本文取 $α = 0.99$ .

为了评价基于改进蝗虫优化算法的特征选择方法的优劣，本文选用分类器准确率、特征选择个数及特征选择率作为衡量指标.

分类准确率的定义如式（11）所示：

A c c u r a c y = \frac{T P + T N}{P + N}

（11）

其中，TP，TN，P，N分别表示真正例、真负例、正和负样本数.

特征选择率的定义如式（12）所示：

F s R a t i o = \frac{1}{M} \overset{M}{∑_{i = 1}} \frac{s i z e ({\hat{g}}^{i})}{D}

（12）

其中，M为特征选择算法运行次数，D为数据集中原始特征数， ${\hat{g}}^{i}$ 为算法每次运行得到的最优特征子集，size(x)是向量x中元素1的个数.

4 实验结果及分析

仿真测试环境：Intel(R) Core(TM) i5⁃6500 CPU 3.2 GHz内存8 GB Windows7(64位)操作系统，所有算法均采用Matlab R2015b实现.为证明本文所提出的IGOA算法比传统蝗虫优化算法的寻优精度及收敛速度都有所提升，引入如表1所示的六个基准测试函数进行测试.为证明基于IGOA的特征选择方法的有效性，在七个UCI数据集上对算法进行测试.

表1 基准测试函数

Table 1 Benchmark functions

函数名	表达式	维度（Dim）	搜索空间
Sphere	$F_{1} = \overset{D i m}{\sum_{i = 1}} x_{i}^{2}$	5/30	[-100,100]
Schwefel 2.22	$F_{2} = \overset{D i m}{\sum_{i = 1}} \|x_{i}\| + \overset{D i m}{\prod_{i = 1}} \|x_{i}\|$	5/30	[-10,10]
Schwefel 1.2	$F_{3} = {\overset{D i m}{\sum_{i = 1}} (\overset{i}{\sum_{j - 1}} x_{j})}^{2}$	5/30	[-100,100]
Schwefel 2.21	$F_{4} = m a x_{i} \{\|x_{i}\|, 1 \leq i \leq D\}$	5/30	[-100,100]
Rastrigin	$F_{5} = [x_{i}^{2} - 10 c o s (2 π x_{i}) + 10]$	5/30	[-5.12,5.12]
Ackley	$F_{6} = - 20 e x p (- 0.2 \sqrt[]{\frac{1}{D i m} \overset{D i m}{\sum_{i = 1}} x_{i}^{2}}) - e x p (\frac{1}{D i m} \overset{D i m}{\sum_{i = 1}} c o s (2 π x_{i})) + 20 + e$	5/30	[-32,32]

4.1　IGOA算法性能测试

本文在不同维度（Dim=5，30）的搜索空间中，利用六个基准测试函数测试IGOA算法性能，设置种群规模为30，最大迭代次数为500次.为获得更为客观真实数据，取算法独立运行30次后得到的最优解的均值和方差，与相同条件下的传统蝗虫优化算法以及李洋州和顾磊^[12]提出的最新的改进蝗虫优化算法（CAGOA2，SA⁃CAGOA2）进行对比，测试结果如表2所示(表中黑体字表示对比算法得到的最优值).为证明IGOA算法比传统蝗虫优化算法的收敛速度更快，通过对比两种算法的收敛曲线，验证本文提出的IGOA算法的有效性及优越性，实验结果如图3和图4所示.

表2 算法寻优性能对比

Table 2 Optimization performance of IGOA and other algorithms

函数

Dim

GOA

文献[12]

IGOA

F₁

Mean

Std.Dev

1.74E-008

1.97E-008

2.55E-013

5.68E-013

2.03E-035

8.82E-036

Mean

Std.Dev

3.86E+001

2.97E+001

6.62E-019

8.53E-019

1.21E-034

2.86E-035

F₂

Mean

Std.Dev

2.36E+000

2.88E+000

1.49E+000

2.06E+000

3.85E-019

5.83E-020

Mean

Std.Dev

1.68E+001

1.91E+001

3.64E-010

3.63E-010

2.70E-018

4.66E-019

F₃

Mean

Std.Dev

8.27E-006

2.51E-005

7.17E-008

2.38E-007

4.96E-035

4.58E-035

Mean

Std.Dev

2.60E+003

1.67E+003

6.78E-016

9.99E-016

1.02E-033

1.17E-033

F₄

Mean

Std.Dev

1.71E-004

2.71E-004

1.17E-006

3.92E-006

2.82E-018

8.14E-019

Mean

Std.Dev

1.50E+001

4.05E+000

1.93E-010

2.15E-010

3.89E-018

4.29E-019

F₅

Mean

Std.Dev

1.11E+001

7.57E+000

7.85E+000

5.19E+000

0.00E+000

Mean

Std.Dev

9.45E+001

3.30E+001

0.00E+000

F₆

Mean

Std.Dev

1.04E+000

2.52E+000

7.42E-001

1.08E+000

8.88E-016

0.00E+000

Mean

Std.Dev

5.50E+000

1.76E+000

2.06E-010

2.03E-010

8.88E-016

0.00E+000

图3

图3 IGOA和GOA算法的收敛曲线（Dim=5）

Fig.3 Convergence curve of IGOA and GOA algorithm (Dim=5)

图4

图4 IGOA和GOA算法的收敛曲线（Dim=30）

Fig.4 Convergence curve of IGOA and GOA algorithm (Dim=30)

由表2可知，IGOA算法无论是在5维或是30维的搜索空间中，针对六个基准测试函数，算法的寻优精度及稳定性都明显优于传统蝗虫优化算法.通过与李洋州和顾磊^[12]提出的最新的改进蝗虫优化算法（包含CAGOA2与SA⁃CAGOA2两种方法，本文所对比的方法为原文中在D=5及

D=30条件下对应的最优方法）相比较，IGOA同样能在函数F₅取到全局最优解，而且对函数F₆所求最优解的标准差也取到了0；而对于其余函数，IGOA所取得的最优解的均值及方差都明显优于该改进算法，也证明本文所提出的IGOA算法的有效性及优越性.此外，由图3和图4可知，IGOA算法仅在五维搜索空间中对于函数F₅的收敛速度提升不太明显，而在其余不同维度的搜索空间中，IGOA在六个基准测试函数上的收敛速度都明显优于传统蝗虫优化算法.

传统蝗虫优化算法采用线性递减系数，所以无法有效平衡算法在迭代过程中的全局探索和局部开发能力.而本文的IGOA算法不仅采用非线性递减系数，同时还引入非线性权重系数和个体扰动策略，不仅能有效地平衡算法的全局探索和局部开发能力，提高算法的收敛速度，还可以避免算法陷入局部最优，提高算法寻优精度.因此，IGOA算法无论是寻优精度还是收敛速度都明显优于传统蝗虫优化算法，而且比李洋州和顾磊^[12]提出的最新的改进算法也有明显优势.

4.2　基于IGOA的特征选择方法

为证明本文提出的基于IGOA的特征选择方法的有效性，在如表3所示的七个数据集上对算法进行测试.首先比较基于IGOA的特征选择方法（IGOA⁃FS）、基于传统蝗虫优化算法的特征选择方法（GOA⁃FS）以及采用全特征进行训练的KNN算法的性能.设置种群规模为30，算法最大迭代次数为100次，所有算法独立运行10次，取分类准确率均值及所选择的特征数来评价算法性能，测试结果如表4所示(表中黑体字为所对比算法中的最优值).

表3 实验数据集

Table 3 Experimental datasets

Datasets		特征个数	实例数
D1	BreastCancerEW	30	569
D2	Zoo	16	101
D3	Heart	12	270
D4	Parkinson	22	197
D5	Congress	16	435
D6	Wine	13	178
D7	Colon	2000	62

表4 算法在七个数据集上的特征选择性能的比较

Table 4 Feature selection performance of algorithms on seven datasets

数据集

FULL

GOA⁃FS

IGOA⁃FS

Accuracy

Features

0.951

0.959

11.2

0.976

13.5

Accuracy

Features

0.961

0.931

6.6

0.963

7.1

Accuracy

Features

0.763

0.768

6.6

0.801

6.4

Accuracy

Features

0.908

0.949

8.9

0.949

8.4

Accuracy

Features

0.940

0.945

5.5

0.970

3.3

Accuracy

Features

0.944

0.951

6.2

0.960

5.8

Accuracy

Features

0.677

2000

0.745

675.2

0.833

691.9

由表4可知，本文提出的IGOA⁃FS方法所选特征子集的长度仅在D1，D2及D7数据集上略多于GOA⁃FS方法，但其分类准确率明显优于GOA⁃FS以及未进行特征选择的KNN算法.并且，在其余四个数据集上，IGOA⁃FS无论是分类准确率还是所选特征子集的长度都在三种方法中均为最优.尤其和未进行特征选择的KNN算法相比，IGOA⁃FS不仅提高了算法的分类准确率，还能大幅减少算法训练所需的特征数.IGOA⁃FS算法将特征选择问题转化为函数最优解的求解问题，由于其函数优化效果已被证明明显优于GOA算法，因此和GOA⁃FS算法及采用全特征的KNN算法相比，IGOA⁃FS能找到最佳特征子集，提高分类精度，证明IGOA⁃FS方法能有效地进行特征选择，减少冗余特征对分类器性能的影响.

为了比较本文提出的IGOA⁃FS方法与其他基于群智能优化的特征选择方法的性能优劣，将其与Mafarja and Mirjalili^[14]提出的基于鲸鱼优化的特征选择方法、Emary et al^[15]提出的基于蚁狮优化的特征选择方法以及Sayed et al^[16]提出的基于混沌乌鸦搜索的特征选择方法相对比，分类准确率对比结果如表5所示(表中黑体字为对比算法得到的最优值，“—”表示参考文献未给出相应数据)，算法的平均特征选择率如图5所示.

表5 IGOA⁃FS与其他算法的性能对比

Table 5 Performance of IGOA⁃FS and other algorithms on seven datasets

Data set	ALO^[15]	CCSA^[16]	WOA⁃ CM^[14]	IGOA⁃ FS
D1	0.930	0.903	0.971	0.976
D2	0.909	0.937	0.980	0.963
D3	0.826	0.788	0.807	0.801
D4	—	0.908	—	0.949
D5	0.929	—	0.956	0.970
D6	0.911	—	0.959	0.960
D7	—	—	0.909	0.833

图5

图5 IGOA⁃FS和其他算法在七个数据集上的平均特征选取率对比

Fig.5 Average feature selection ratio of IGOA⁃FS and other algorithms on seven datasets

由表5可知，在特征数较少的数据集上，IGOA⁃FS的分类准确率仅在D2，D3，D7数据集上略劣于Mafarja and Mirjalili^[14]和Emary et al^[15]提出的方法，而在其余四个数据集上的分类准确率均明显高于其他对比算法.根据图5可知，IGOA⁃FS的特征选取率仅在D2及D3数据集上略高于WOA⁃CM以及CCSA，而在其余数据集上的特征选择率均低于其他对比算法，也就是说，IGOA⁃FS在其余数据集上不仅能获得更高的分类准确率，而且所选择的特征子集的长度比其他对比算法更低，特征选择性能更好.

而在特征数较多的数据集D7上，IGOA⁃FS的分类精度及特征选择率虽然略劣于WOA⁃CM，但与GOA⁃FS及采用全特征进行训练的KNN算法相比仍具有明显优势，证明IGOA⁃FS算法能在特征数较多的数据集上进行有效的特征选择，而且在特征维度较高的情况下^[17]，算法的性能仍具有一定的提升空间.

综上所述，本文提出的IGOA⁃FS算法能够有效地进行特征选择，降低数据维度，提高算法分类性能，和其他特征选择算法相比有明显的优势.

5 结论

首先针对传统蝗虫优化算法寻优精度低、收敛速度慢的问题，采用三种策略进行改进，并通过基准测试函数证明所提出的改进算法IGOA在寻优精度和收敛速度方面均有明显提升.将改进算法应用于特征选择问题，提出了一种基于改进蝗虫优化算法的特征选择方法IGOA⁃FS，并在七个数据集上对算法进行了测试，证明该方法能够有效地进行特征选择，提高分类器性能.最后，通过与其他特征选择算法进行对比，证明本文提出的方法确实具有一定优势.如何对算法进行改进，使其能够在更高的特征维度下仍具备优异性能将是下一步的主要研究内容.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

李炜，巢秀琴.

改进的粒子群算法优化的特征选择方法

计算机科学与探索，2019，13(6)：990-1004.

Li W，Chao X Q.

Improved particle swarm optimization method for feature selection

Journal of Frontiers of Computer Science and Technology，2019，13(6)：990-1004.

[2]

张震，魏鹏，李玉峰等.

改进粒子群联合禁忌搜索的特征选择算法

通信学报，2018，39(12)：60-68.

Zhang

，Wei

，Li

Y F

，et al.

Feature selection algorithm based on improved particle swarm joint taboo search

Journal on Communications，2018，39(12)：60-68.

[3]

Gao

W F

，Hu

，Zhang

，et al.

Feature selection by integrating two groups of feature evaluation criteria

Expert Systems with Applications，2018，110：11-19.

[4]

Mafarja

M M

，Mirjalili

Hybrid whale optimization algorithm with simulated annealing for feature selection

Neurocomputing，2017，260：302-312.

[5]

Kennedy

，Eberhart

Particle swarm optimization

∥Proceedings of ICNN'95⁃International Conference on Neural Networks. Perth，Australia：IEEE，1995：1942-1948.

[6]

Mirjalili

The ant lion optimizer

Advances in Engineering Software，2015，83：80-98.

[7]

Mirjalili

，Lewis

The whale optimization algorithm

Advances in Engineering Software，2016，95：51-67.

[8]

Saremi

，Mirjalili

，Lewis

Grasshopper optimisation algorithm：theory and application

Advances in Engineering Software，2017，105：30-47.

[9]

Ewees

A A

，Elaziz

M A

，Houssein

E H

Improved grasshopper optimization algorithm using opposition⁃based learning

Expert Systems with Applications，2018，112：156-172.

[10]

Luo

，Chen

H L

，Zhang

，et al.

An improved grasshopper optimization algorithm with application to financial stress prediction

Applied Mathematical Modelling，2018，64：654-668.

[11]

Arora

，Anand

Chaotic grasshopper optimization algorithm for global optimization

Neural Computing and Applications，2019，doi：10.1007/s00521⁃018⁃3343⁃2.

[12]

李洋州，顾磊.

一种基于曲线自适应和模拟退火的蝗虫优化算法

计算机应用研究，2019，

doi：10.19734/j.issn.1001⁃3695.2018.07. 0580. (Li Y Z，Gu L

Grasshopper optimization algorithm based on curve adaptive and simulated annealing. Application Research of Computers，2019，doi：10.19734/j.issn.1001⁃3695. 2018.07.0580.

[本文引用: 5]

[13]

杨菊蜻，张达敏，何锐亮等.

基于Powell搜索的混沌鸡群优化算法

微电子学与计算机，2018，35(7)：78-82.

Yang

J Q

，Zhang

D M

，He

R L

，et al.

A chaotic chicken optimization algorithm based on powell search

Microelectronics & Computer，2018，35(7)：78-82.

[14]

Mafarja

，Mirjalili

Whale optimization approaches for wrapper feature selection

Applied Soft Computing，2018，62：441-453.

[本文引用: 4]

[15]

Emary

，Zawbaa

H M

，Parv

Feature selection based on antlion optimization algorithm

∥2015 3^rd World Conference on Complex Systems (WCCS). Marrakech，Morocco：IEEE，2015：1-7.

[本文引用: 3]

[16]

Sayed

G I

，Hassanien

A E

，Azar

A T

Feature selection via a novel chaotic crow search algorithm

Neural Computing and Applications，2019，31(1)：171-188.

[本文引用: 2]

[17]

，Liu

Feature selection for high⁃dimensional data：a fast correlation⁃based filter solution

∥Proceedings of the 20^th International Conference on Machine Learning. Washington DC，USA：AAAI Press，2003：856-863.