Co-Evolutionary Feature Selection Algorithm Based on Variable-Length Particle and Multi-Behavior Interaction
-
摘要: 针对大规模数据集上的特征选择问题,一种变长表示的粒子群特征选择方法(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 will result in certain blindness in the initial stage. Meanwhile, the single updating mechanism of VLPSO and the information isolation among subpopulations also affect the classification performance. In order to cope with the defect of VLPSO, this paper proposes a co-evolutionary feature selection method based on variable-length particle and multi-behavior interaction(M-CVLPSO). 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 then 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 integrated into the fitness function to further enhance the performance of the algorithm on some datasets. The convergence of the proposed algorithm is proved theoretically. Finally, the experimental analysis is carried out on the classification accuracy, dimension reduction and calculation time based on 11 large-scale feature selection data sets, which show that the proposed model has better comprehensive performance than the four comparison algorithms.
-
表 1 实验数据集
Table 1. Experiment 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 4 435 50 4 14 30 表 2 参数设置
Table 2. Parameter setting
Parameters Setting Population size Features/20 Maximun iterations 100 c1=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) 表 3 平均测试结果
Table 3. Average test results
Algorithms LSVT Carcinom SRBCT Time Size Best Mean 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 0.8 63.7 100.00 99.70 VLPSO 0.7 33.2 83.14 80.19 46.2 136.0 87.76 85.38 1.6 51.1 100.00 99.58 ECLPSO 2.0 138.0 83.63 78.99 311.8 4182.2 84.13 81.47 8.4 1051.0 90.83 86.08 CLPSO 1.7 137.7 79.67 76.49 234.1 4157.0 88.97 86.79 6.6 1056.4 100.00 98.95 PSO 2.0 141.3 81.24 77.86 360.4 2174.7 77.20 73.83 9.4 1103.2 92.50 88.94 Full / 310.0 76.80 / / 9182.0 73.65 / / 2308.0 86.96 / Algorithms Leukemia1 Leukemia2 DLBCL Time Size Best Mean Time Size Best Mean Time Size Best Mean M-CVLPSO 4.5 48.7 98.06 95.49 12.1 29.8 95.56 92.94 4.6 30.9 94.00 89.56 VLPSO 7.0 57.9 95.83 92.94 16.2 34.1 95.56 91.66 7.5 52.8 91.33 86.51 ECLPSO 41.5 2432.1 84.44 82.22 182.6 5123.2 90.56 87.44 47.3 2500.3 84.83 81.69 CLPSO 32.5 2435.7 95.56 94.65 88.9 5117.1 93.33 91.66 37.2 2487.9 96.50 93.98 PSO 47.1 2601.5 87.36 80.97 163.8 5427.7 92.22 89.67 52.7 2682.5 86.33 83.54 Full / 5327.0 79.72 / / 11225.0 88.78 / / 5469.0 84.12 / Algorithms 9Tumor Brain1 Brain2 Time Size Best Mean Time Size Best Mean Time Size Best Mean M-CVLPSO 4.1 43.7 66.67 58.00 7.3 33.2 80.42 75.56 8.9 61.0 80.00 69.54 VLPSO 6.2 39.9 58.33 53.33 10.8 26.6 77.08 70.74 13.4 81.8 79.58 68.29 ECLPSO 39.0 2621.4 45.00 42.83 67.4 2721.4 80.00 74.17 76.0 4703.7 69.58 64.24 CLPSO 32.1 2604.4 58.33 53.83 53.7 2679.5 77.50 75.12 58.2 4706.5 82.08 79.95 PSO 44.1 2787.9 45.00 41.67 71.5 2921.0 77.08 73.33 84.7 5089.0 67.08 62.13 Full / 5 726.0 37.23 / / 5 920.0 71.67 / / 10367.0 62.50 / Algorithms Lung GLIOMA Time Size Best Mean Time Size Best Mean M-CVLPSO 9.6 154.5 93.40 91.03 2.5 64.89 78.75 73.29 VLPSO 27.6 369.4 93.20 91.28 4.3 148.2 77.50 69.91 ECLPSO 78.1 1517.7 93.07 91.01 19.5 2033.9 80.00 73.95 CLPSO 62.4 1506.5 94.25 92.02 15.3 1991.1 82.08 76.16 PSO 84.7 1613.7 93.18 90.43 23.4 2207.8 73.56 68.28 Full / 3312.0 86.83 / / 4434.0 74.50 / 表 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 表 5 加入新适应度函数的平均测试结果
Table 5. Mean test results with new fitness function
Model DLBCL Brain2 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 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 表 6 层次初始化单轮迭代平均测试结果
Table 6. single-round iteration average test results
Datasets Strategy Gbf Gbs Avf SRBCT With 0.90 149.2 0.82 Without 0.87 200.7 0.78 Leukemia1 With 0.87 221.1 0.78 Without 0.83 209.1 0.74 Leukemia2 With 0.83 448.8 0.76 Without 0.83 365.5 0.76 DLBCL With 0.85 218.4 0.76 Without 0.81 195.4 0.72 9Tumor With 0.52 218.9 0.38 Without 0.51 224.5 0.38 Brain1 With 0.71 265.8 0.62 Without 0.67 257.4 0.59 Brain2 With 0.73 689.9 0.65 Without 0.74 892.0 0.65 Lung With 0.87 435.7 0.83 Without 0.83 1465.7 0.79 GLIOMA With 0.79 531.0 0.72 Without 0.75 601.5 0.68 LSVT With 0.75 44.5 0.67 Without 0.71 43.6 0.63 Carcinom With 0.83 428.4 0.77 Without 0.80 333.7 0.73 表 7 层次初始化策略消融实验结果
Table 7. Ablation experiment results with hierarchical initialization strategy
Model SRBCT Leukemia1 Leukemia2 Time Size Best Mean 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 16.1 34.3 93.89 92.33 I' 1.4 51.7 100.00 99.25 7.6 45.5 98.06 93.33 22.4 32.9 91.67 90.22 Model DLBCL 9Tumor Brain1 Time Size Best Mean Time Size Best Mean Time Size Best Mean VLPSO 7.9 59.6 90.67 88.03 6.0 39.0 58.33 52.33 11.7 29.8 77.08 70.08 I' 7.6 52.0 92.50 89.00 6.8 46.0 58.33 54.00 11.1 28.2 77.92 70.59 Model Brain2 Lung GLIOMA Time Size Best Mean 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 4.3 181.2 77.50 69.41 I' 14.2 99.5 78.75 73.33 28.6 422.0 94.32 91.86 4.5 130.4 75.42 70.00 Model LSVT Carcinom Time Size Best Mean Time Size Best Mean VLPSO 0.7 32.3 79.60 78.48 44.9 145.9 87.76 85.08 I' 0.7 37.8 79.11 77.13 54.1 145.7 92.29 88.29 表 8 多行为交互策略消融实验结果
Table 8. Ablation experiment results with multi-behavior interactive strategy
Model SRBCT Leukemia1 Leukemia2 Time Size Best Mean 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 16.1 34.3 93.89 92.33 II' 0.9 65.6 100.00 99.42 4.2 47.6 95.83 91.25 12.3 29.7 93.89 92.00 Model DLBCL 9Tumor Brain1 Time Size Best Mean Time Size Best Mean Time Size Best Mean VLPSO 7.9 59.6 90.67 88.03 6.0 39.0 58.33 52.33 11.7 29.8 77.08 70.08 II' 6.8 31.6 92.33 87.50 4.0 46.3 56.67 55.67 7.5 35.4 75.00 71.33 Model Brain2 Lung GLIOMA Time Size Best Mean 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 4.3 181.2 77.50 69.41 II' 9.1 63.6 77.92 71.67 10.0 197.5 92.61 89.88 2.3 58.3 82.92 74.08 Model LSVT Carcinom Time Size Best Mean Time Size Best Mean VLPSO 0.7 32.3 79.60 78.48 44.9 145.9 87.76 85.08 II' 0.4 35.4 82.33 78.69 35.9 148.6 91.02 88.07 -
[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] 初蓓, 李占山. 基于森林优化调整选择算法的改进研究[J]. 软件学报, 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. -