基于多行为交互的变维协同进化特征选择方法

李腾飞; 冯翔; 虞慧群

doi:10.14135/j.cnki.1006-3080.20201207001

基于多行为交互的变维协同进化特征选择方法

doi: 10.14135/j.cnki.1006-3080.20201207001

李腾飞^1,2,,
冯翔^1,2, ,,
虞慧群^1,2

1.
华东理工大学信息科学与工程学院，上海 200237
2.
上海智慧能源工程技术研究中心，上海 200237

基金项目: 国家自然科学基金（61772200；61772201，61602175）；上海市浦江人才计划（17PJ1401900）；上海市经信委“信息化发展专项资金”（201602008）

详细信息

作者简介:
李腾飞(1996-)：硕士生，主要研究方向为演化计算、人工智能。E-mail：tyrandesal@163.com

通讯作者:
冯　翔，E-mail：xfeng@ecust.edu.cn

中图分类号: TP18
计量
- 文章访问数: 177
- HTML全文浏览量: 189
- PDF下载量: 1
- 被引次数: 0
出版历程
- 收稿日期: 2020-12-07
- 网络出版日期: 2021-03-24

Co-Evolutionary Feature Selection Algorithm Based on Variable-Length Particle and Multi-Behavior Interaction

LI Tengfei^{1,2
,},
FENG Xiang^{1,2
, ,},
YU Huiqun^1,2

1.
School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China
2.
Shanghai Engineering Research Center of Smart Energy, Shanghai 200237, China

摘要

摘要: 针对大规模数据集上的特征选择问题，一种变长表示的粒子群特征选择方法（VLPSO）表现出了良好的性能。然而，其完全随机的粒子生成方式导致初始化阶段具有一定的盲目性。同时，VLPSO单一的更新机制和种群间的信息隔离也影响了模型的分类性能。为了解决VLPSO的缺陷，提出了一种基于多行为交互的变维协同进化特征选择方法(M-CVLPSO)。首先，为了改善随机初始化带来的盲目性，采用连续空间上的层次初始化策略，从期望上缩短了初始解与最优解之间的距离。其次，将粒子根据适应度分为领导者、追随者与淘汰者，在迭代过程中采用多种更新策略动态平衡算法的多样性与收敛性。同时，将维度缩减指标加入到适应度函数中，进一步增强了算法在部分数据集上的性能。从理论上证明了该算法的收敛性，并基于11个大规模特征选择数据集在分类精度、维度缩减和计算时间上进行实验分析。实验结果表明，本文算法相较于4种对比算法具有更好的综合表现。
- 行为交互 /
- 协同进化 /
- 变维表示 /
- 特征选择 /
- 粒子群优化
Abstract: A variable-length particle swarm optimization (VLPSO) shows good performance for feature selection on large data sets. However, its completely random particle initialization leads to certain blindness in the initial stage. At the same time, the single updating mechanism of VLPSO and the information isolation between subpopulations also affect the classification performance. In order to solve the defect of VLPSO, a co-evolutionary feature selection method based on variable-length particle and multi-behavior interaction(M-CVLPSO) is proposed. Firstly, to improve the blindness caused by random initialization, the multidirectional initialization strategy in continuous space is adopted to shorten the distance between the initial solution and the optimal solution from the perspective of expectation. Secondly, particles are divided into leaders, followers and weeders according to fitness, and multiple updating strategies are adopted in the process of iteration to balance the diversity and convergence of dynamic algorithms. At the same time, the dimension reduction index is added to the fitness function to further enhance the performance of the algorithm on some datasets. The convergence of the proposed algorithm is proved theoretically, and the experimental analysis on the classification accuracy, dimension reduction and calculation time based on 11 large-scale feature selection data sets is carried out. The results show that the proposed model has better comprehensive performance than the four comparison algorithms.
- behavior interaction /
- co-evolution /
- variable-length representation /
- feature selection /
- particle swarm optimization

HTML全文

图 1 基于CLPSO的变长粒子表示示意图

Figure 1. Clpso-based variable-length particle representation

下载: 全尺寸图片幻灯片

图 2 层次初始化

Figure 2. Hierarchical initialization

下载: 全尺寸图片幻灯片

图 3 多行为交互策略下的粒子更新示意图

Figure 3. Particle update under multi-behavior interaction strategy

下载: 全尺寸图片幻灯片

图 4 5种算法在11个数据集上的各项指标排名

Figure 4. ranking of the five algorithms on eleven data sets

下载: 全尺寸图片幻灯片

图 5 种群平均维度随迭代变化情况

Figure 5. The average particle dimension varies with iteration

下载: 全尺寸图片幻灯片

图 6 最优粒子适应度变化曲线

Figure 6. Curves of optimal particle fitness

下载: 全尺寸图片幻灯片

表 1 实验数据集

Table 1. Datasets

Dataset	#Features	#Ins.	#Class	%Smallest class	%Largest class
SRBCT	2308	83	4	13	35
Leukemia1	5327	72	3	13	53
Leukemia2	11225	72	3	28	39
DLBCL	5469	77	2	25	75
9Tumor	5726	60	9	3	15
Brain1	5920	90	5	4	67
Brain2	10367	50	4	14	30
LSVT	310	126	2	33	66
Lung	12600	203	5	3	68
Carcinom	9182	174	11	3	15
GLIOMA	4435	50	4	14	30

下载: 导出CSV

表 2 参数设置

Table 2. Parameter setting

Parameter	Setting
Population size	Features/20
Maximun iterations	100
c₁=c	1.49445
w	0.9−0.5×(curr_iter/max_iter)
Threshold for selected feature	0.6
Data set partitioning	10 cross-fold
Max iterations for renew	7(CLPSO，ECLPSO，VLPSO)
Number of divisions	12(M-CVLPSO,VLPSO)
Max iterations for length changing	9(M-CVLPSO,VLPSO)

下载: 导出CSV

表 3 平均测试结果

Table 3. Average test results

Algorithm	LSVT				Carcinom
Algorithm	Time	Size	Best	Mean	Time	Size	Best	Mean
M-CVLPSO	0.4	35.5	86.89	80.22	35.9	152.5	90.07	87.78
VLPSO	0.7	33.2	83.14	80.19	46.2	136.0	87.76	85.38
ECLPSO	2.0	138.0	83.63	78.99	311.8	4182.2	84.13	81.47
CLPSO	1.7	137.7	79.67	76.49	234.1	4157.0	88.97	86.79
PSO	2.0	141.3	81.24	77.86	360.4	2174.7	77.20	73.83
Full	/	310.0	76.80	/	/	9182.0	73.65	/
Algorithm	SRBCT				Leukemia1				Leukemia2
Algorithm	Time	Size	Best	Mean	Time	Size	Best	Mean	Time	Size	Best	Mean
M-CVLPSO	0.8	63.7	100.00	99.70	4.5	48.7	98.06	95.49	12.1	29.8	95.56	92.94
VLPSO	1.6	51.1	100.00	99.58	7.0	57.9	95.83	92.94	16.2	34.1	95.56	91.66
ECLPSO	8.4	1051.0	90.83	86.08	41.5	2432.1	84.44	82.22	182.6	5123.2	90.56	87.44
CLPSO	6.6	1056.4	100.00	98.95	32.5	2435.7	95.56	94.65	88.9	5117.1	93.33	91.66
PSO	9.4	1103.2	92.50	88.94	47.1	2601.5	87.36	80.97	163.8	5427.7	92.22	89.67
Full	/	2308.0	86.96	/	/	5327.0	79.72	/	/	11225.0	88.78	/
Algorithm	DLBCL				9Tumor				Brain1
Algorithm	Time	Size	Best	Mean	Time	Size	Best	Mean	Time	Size	Best	Mean
M-CVLPSO	4.6	30.9	94.00	89.56	4.1	43.7	66.67	58.00	7.3	33.2	80.42	75.56
VLPSO	7.5	52.8	91.33	86.51	6.2	39.9	58.33	53.33	10.8	26.6	77.08	70.74
ECLPSO	47.3	2500.3	84.83	81.69	39.0	2621.4	45.00	42.83	67.4	2721.4	80.00	74.17
CLPSO	37.2	2487.9	96.50	93.98	32.1	2604.4	58.33	53.83	53.7	2679.5	77.50	75.12
PSO	52.7	2682.5	86.33	83.54	44.1	2787.9	45.00	41.67	71.5	2921.0	77.08	73.33
Full	/	5469.0	84.12	/	/	5726.0	37.23	/	/	5920.0	71.67	/
Algorithm	Brain2				Lung				GLIOMA
Algorithm	Time	Size	Best	Mean	Time	Size	Best	Mean	Time	Size	Best	Mean
M-CVLPSO	8.9	61.0	80.00	69.54	9.6	154.5	93.40	91.03	2.5	64.89	78.75	73.29
VLPSO	13.4	81.8	79.58	68.29	27.6	369.4	93.20	91.28	4.3	148.2	77.50	69.91
ECLPSO	76.0	4703.7	69.58	64.24	78.1	1517.7	93.07	91.01	19.5	2033.9	80.00	73.95
CLPSO	58.2	4706.5	82.08	79.95	62.4	1506.5	94.25	92.02	15.3	1991.1	82.08	76.16
PSO	84.7	5089.0	67.08	62.13	84.7	1613.7	93.18	90.43	23.4	2207.8	73.56	68.28
Full	/	10367.0	62.50	/	/	3312.0	86.83	/	/	4434.0	74.50	/

下载: 导出CSV

表 4 5种算法在特征集上的Friedman排名

Table 4. Average Friedman ranking of the five algorithms on the feature set

Algorithm	Time	Size	Best	Mean	Comprehensive
M-CVLPSO	1.00	1.45	1.45	1.54	5.44
VLPSO	2.00	1.55	2.63	2.91	9.09
ECLPSO	4.09	3.82	3.91	3.91	15.73
CLPSO	3.00	3.36	2.09	2.00	10.45
PSO	4.90	4.82	3.91	4.54	18.17

下载: 导出CSV

表 5 加入新适应度函数的平均测试结果

Table 5. Mean test results with new fitness function

Model	DLBCL				Brain2
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
ALL-Best	4.6	30.9	96.50	93.98	8.9	61.0	82.08	79.95
I	4.6	30.9	94.00	89.56	8.9	61.0	80.00	69.54
II	5.1	31.1	97.5	91.03	9.3	65.9	82.50	73.63

Model	Lung				GLIOMA
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
ALL-Best	9.6	154.5	94.25	92.02	2.5	64.9	82.08	76.16
I	9.6	154.5	93.40	91.03	2.5	64.9	78.75	76.67
II	10.1	149.0	94.27	90.96	2.6	71.0	76.67	70.04

下载: 导出CSV

表 6 层次初始化单轮迭代平均测试结果

Table 6. single-round iteration average test results

Dataset	Strategy	Gbf	Gbs	Avf
SRBCT	With	0.90	149.2	0.82
SRBCT	Without	0.87	200.7	0.78
Leukemia1	With	0.87	221.1	0.78
Leukemia1	Without	0.83	209.1	0.74
Leukemia2	With	0.83	448.8	0.76
Leukemia2	Without	0.83	365.5	0.76
DLBCL	With	0.85	218.4	0.76
DLBCL	Without	0.81	195.4	0.72
9Tumor	With	0.52	218.9	0.38
9Tumor	Without	0.51	224.5	0.38
Brain1	With	0.71	265.8	0.62
Brain1	Without	0.67	257.4	0.59
Brain2	With	0.73	689.9	0.65
Brain2	Without	0.74	892.0	0.65
Lung	With	0.87	435.7	0.83
Lung	Without	0.83	1465.7	0.79
GLIOMA	With	0.79	531.0	0.72
GLIOMA	Without	0.75	601.5	0.68
LSVT	With	0.75	44.5	0.67
LSVT	Without	0.71	43.6	0.63
Carcinom	With	0.83	428.4	0.77
Carcinom	Without	0.80	333.7	0.73

下载: 导出CSV

表 7 层次初始化策略消融实验结果

Table 7. Ablation experiment results with hierarchical initialization strategy

Model	SRBCT				Leukemia1
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	1.6	52.3	100.00	99.67	6.6	53.1	95.83	92.83
I'	1.4	51.7	100.00	99.25	7.6	45.5	98.06	93.33

Model	Leukemia2				DLBCL
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	16.1	34.3	93.89	92.33	7.9	59.6	90.67	88.03
I'	22.4	32.9	91.67	90.22	7.6	52.0	92.50	89.00

Model	9Tumor				Brain1
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	6.0	39.0	58.33	52.33	11.7	29.8	77.08	70.08
I'	6.8	46.0	58.33	54.00	11.1	28.2	77.92	70.59

Model	Brain2				Lung
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	16.1	77.8	75.42	66.75	27.6	381.0	92.56	91.41
I'	14.2	99.5	78.75	73.33	28.6	422.0	94.32	91.86

Model	GLIOMA				LSVT
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	4.3	181.2	77.50	69.41	0.7	32.3	79.60	78.48
I'	4.5	130.4	75.42	70.00	0.7	37.8	79.11	77.13

Model	Carcinom
Model	Time	Size	Best	Mean
VLPSO	44.9	145.9	87.76	85.08
I'	54.1	145.7	92.29	88.29

下载: 导出CSV

表 8 多行为交互策略消融实验结果

Table 8. Ablation experiment results with multi-behavior interactive strategy

Model	SRBCT				Leukemia1
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	1.6	52.3	100.00	99.67	6.6	53.1	95.83	92.83
II'	0.9	65.6	100.00	99.42	4.2	47.6	95.83	91.25

Model	Leukemia2				DLBCL
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	16.1	34.3	93.89	92.33	7.9	59.6	90.67	88.03
II'	12.3	29.7	93.89	92.00	6.8	31.6	92.33	87.50

Model	9Tumor				Brain1
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	6.0	39.0	58.33	52.33	11.7	29.8	77.08	70.08
II'	4.0	46.3	56.67	55.67	7.5	35.4	75.00	71.33

Model	Brain2				Lung
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	16.1	77.8	75.42	66.75	27.6	381.0	92.56	91.41
II'	9.1	63.6	77.92	71.67	10.0	197.5	92.61	89.88

Model	GLIIOMA				LSVT
Model	Time	Size	Best	Mean	Time	Size	Best	Mean
VLPSO	4.3	181.2	77.50	69.41	0.7	32.3	79.60	78.48
II'	2.3	58.3	82.92	74.08	0.4	35.4	82.33	78.69

Model	Carcinom
Model	Time	Size	Best	Mean
VLPSO	44.9	145.9	87.76	85.08
II'	35.9	148.6	91.02	88.07

下载: 导出CSV

参考文献(22)

[1]	赵鸿山, 范贵生, 虞慧群. 基于归一化文档频率的文本分类特征选择方法[J]. 华东理工大学学报(自然科学版), 2019, 45(5): 809-814.
[2]	GUYON I, ELISSEEFF A. An introduction to variable and feature selection[J]. Journal of Machine Learning Research, 2003, 3(6): 1157-1182.
[3]	DASH M, LIU H. Feature selection for classification[J]. Intelligent Data Analysis, 1997, 1(1/4): 131-156.
[4]	KENNEDY J, EBERHART R. Particle swarm optimization[C]// International Conference on Neural Networks. Australia: IEEE, 1995: 1942-1948.
[5]	XUE B, ZHANG M, BROWNE W N. Particle swarm optimisation for feature selection in classification: Novel initialisation and updating mechanisms[J]. Applied Soft Computing Journal, 2014, 18: 261-276. doi: 10.1016/j.asoc.2013.09.018
[6]	LIANG J J, QIN A K, SUGANTHAN P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295. doi: 10.1109/TEVC.2005.857610
[7]	QIAN W, HUANG J, WANG Y, et al. Label distribution feature selection for multi-label classification with rough set[J]. International Journal of Approximate Reasoning, 2021, 128: 32-55. doi: 10.1016/j.ijar.2020.10.002
[8]	ZHOU Y, LIN J, GUO H. Feature subset selection via an improved discretization-based particle swarm optimization[J]. Applied Soft Computing, 2021, 98: 106794. doi: 10.1016/j.asoc.2020.106794
[9]	HUDA R K, BANKA H. New efficient initialization and updating mechanisms in PSO for feature selection and classification[J]. Neural Computing and Applications, 2020, 32(1): 3283-3294.
[10]	FISTER D, FISTER I, JAGRI T, et al. Swarm, Evolutionary, and Memetic Computing and Fuzzy and Neural Computing[M]. [s.l.]:[s.n.], 2020: 135-154.
[11]	JI B, LU X, SUN G, et al. Bio-inspired feature selection: An improved binary particle swarm optimization approach[J]. IEEE Access, 2020, 8: 85989-86002. doi: 10.1109/ACCESS.2020.2992752
[12]	CHEN K, XUE B, ZHANG M, et al. Hybridising particle swarm optimisation with differential evolution for feature selection in classification[C]// IEEE Congress on Evolutionary Computation (CEC). UK: IEEE, 2020: 1-8.
[13]	GUAN B, ZHAO Y, YIN Y, et al. A differential evolution based feature combination selection algorithm for high-dimensional data[J]. Information Sciences, 2020, 547: 870-886.
[14]	NGUYEN H B, XUE B, LIU I, et al. PSO and statistical clustering for feature selection: a new representation[C]/ / Proceedings of the 10th International Conference on Simulated Evolution and Learning. Dunedin: Springer, 2014: 569-581.
[15]	GU S, CHENG R, JIN Y. Feature selection for high-dimensional classification using a competitive swarm optimizer[J]. Soft Computing, 2016, 22: 811-822.
[16]	TRAN B, XUE B, ZHANG M. Variable-length particle swarm optimization for feature selection on high-dimensional classification[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(3): 473-487. doi: 10.1109/TEVC.2018.2869405
[17]	初蓓, 李占山. 基于森林优化调整选择算法的改进研究软件学报, 2018, 29(9): 2547-2558.
[18]	CHENG R, JIN Y. A social learning particle swarm optimization algorithm for scalable optimization[J]. Information Sciences, 2015, 291: 43-60. doi: 10.1016/j.ins.2014.08.039
[19]	FERNANDEZ-MARTINEZ J L, GARCIA-GONZALO E. Stochastic stability analysis of the linear continuous and discrete PSO models[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(3): 405-423. doi: 10.1109/TEVC.2010.2053935
[20]	TRELEA I C. The particle swarm optimization algorithm: Convergence analysis and parameter selection[J]. Information Processing Letters, 2003, 85(6): 317-325. doi: 10.1016/S0020-0190(02)00447-7
[21]	Sastry. S, Nonlinear Systems: Analysis, Stability, and Control[M], New York: Springer, 1999.
[22]	YU X, LIU Y, FENG X, et al. Enhanced comprehensive learning particle swarm optimization with exemplar evolution[C]// Asia-Pacific Conference on Simulated Evolution and Learning. UK: Springer, 2017: 929-938.