高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

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

    作者简介: 李腾飞(1996-):硕士生,主要研究方向为演化计算、人工智能。E-mail:tyrandesal@163.com;
    通讯作者: 冯翔, xfeng@ecust.edu.cn
  • 中图分类号: TP18

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

    Corresponding author: FENG Xiang, xfeng@ecust.edu.cn ;
  • CLC number: TP18

  • 摘要: 针对大规模数据集上的特征选择问题,一种变长表示的粒子群特征选择方法(VLPSO)表现出了良好的性能。然而,其完全随机的粒子生成方式导致初始化阶段具有一定的盲目性。同时,VLPSO单一的更新机制和种群间的信息隔离也影响了模型的分类性能。为了解决VLPSO的缺陷,提出了一种基于多行为交互的变维协同进化特征选择方法(M-CVLPSO)。首先,为了改善随机初始化带来的盲目性,采用连续空间上的层次初始化策略,从期望上缩短了初始解与最优解之间的距离。其次,将粒子根据适应度分为领导者、追随者与淘汰者,在迭代过程中采用多种更新策略动态平衡算法的多样性与收敛性。同时,将维度缩减指标加入到适应度函数中,进一步增强了算法在部分数据集上的性能。从理论上证明了该算法的收敛性,并基于11个大规模特征选择数据集在分类精度、维度缩减和计算时间上进行实验分析。实验结果表明,本文算法相较于4种对比算法具有更好的综合表现。
  • 图 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
    SRBCT23088341335
    Leukemia153277231353
    Leukemia2112257232839
    DLBCL54697722575
    9Tumor5726609315
    Brain15920905467
    Brain2103675041430
    LSVT31012623366
    Lung126002035368
    Carcinom918217411315
    GLIOMA44355041430
    下载: 导出CSV

    表 2  参数设置

    Table 2.  Parameter setting

    ParameterSetting
    Population sizeFeatures/20
    Maximun iterations100
    c1=c1.49445
    w0.9−0.5×(curr_iter/max_iter)
    Threshold for selected feature0.6
    Data set partitioning10 cross-fold
    Max iterations for renew7(CLPSO,ECLPSO,VLPSO)
    Number of divisions12(M-CVLPSO,VLPSO)
    Max iterations for length changing9(M-CVLPSO,VLPSO)
    下载: 导出CSV

    表 3  平均测试结果

    Table 3.  Average test results

    AlgorithmLSVTCarcinom
    TimeSizeBestMeanTimeSizeBestMean
    M-CVLPSO0.435.586.8980.2235.9152.590.0787.78
    VLPSO0.733.283.1480.1946.2136.087.7685.38
    ECLPSO2.0138.083.6378.99311.84182.284.1381.47
    CLPSO1.7137.779.6776.49234.14157.088.9786.79
    PSO2.0141.381.2477.86360.42174.777.2073.83
    Full/310.076.80//9182.073.65/
    AlgorithmSRBCTLeukemia1Leukemia2
    TimeSizeBestMeanTimeSizeBestMeanTimeSizeBestMean
    M-CVLPSO0.863.7100.0099.704.548.798.0695.4912.129.895.5692.94
    VLPSO1.651.1100.0099.587.057.995.8392.9416.234.195.5691.66
    ECLPSO8.41051.090.8386.0841.52432.184.4482.22182.65123.290.5687.44
    CLPSO6.61056.4100.0098.9532.52435.795.5694.6588.95117.193.3391.66
    PSO9.41103.292.5088.9447.12601.587.3680.97163.85427.792.2289.67
    Full/2308.086.96//5327.079.72//11225.088.78/
    AlgorithmDLBCL9TumorBrain1
    TimeSizeBestMeanTimeSizeBestMeanTimeSizeBestMean
    M-CVLPSO4.630.994.0089.564.143.766.6758.007.333.280.4275.56
    VLPSO7.552.891.3386.516.239.958.3353.3310.826.677.0870.74
    ECLPSO47.32500.384.8381.6939.02621.445.0042.8367.42721.480.0074.17
    CLPSO37.22487.996.5093.9832.12604.458.3353.8353.72679.577.5075.12
    PSO52.72682.586.3383.5444.12787.945.0041.6771.52921.077.0873.33
    Full/5469.084.12//5726.037.23//5920.071.67/
    AlgorithmBrain2LungGLIOMA
    TimeSizeBestMeanTimeSizeBestMeanTimeSizeBestMean
    M-CVLPSO8.961.080.0069.549.6154.593.4091.032.564.8978.7573.29
    VLPSO13.481.879.5868.2927.6369.493.2091.284.3148.277.5069.91
    ECLPSO76.04703.769.5864.2478.11517.793.0791.0119.52033.980.0073.95
    CLPSO58.24706.582.0879.9562.41506.594.2592.0215.31991.182.0876.16
    PSO84.75089.067.0862.1384.71613.793.1890.4323.42207.873.5668.28
    Full/10367.062.50//3312.086.83//4434.074.50/
    下载: 导出CSV

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

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

    AlgorithmTimeSizeBestMeanComprehensive
    M-CVLPSO1.001.451.451.545.44
    VLPSO2.001.552.632.919.09
    ECLPSO4.093.823.913.9115.73
    CLPSO3.003.362.092.0010.45
    PSO4.904.823.914.5418.17
    下载: 导出CSV

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

    Table 5.  Mean test results with new fitness function

    ModelDLBCLBrain2
    TimeSizeBestMeanTimeSizeBestMean
    ALL-Best4.630.996.5093.988.961.082.0879.95
    I4.6 30.994.0089.568.961.080.0069.54
    II5.131.197.591.03 9.365.982.5073.63
    ModelLungGLIOMA
    TimeSizeBestMeanTimeSizeBestMean
    ALL-Best9.6154.594.2592.02 2.564.982.0876.16
    I9.6154.593.4091.032.564.978.7576.67
    II10.1149.094.2790.962.671.076.6770.04
    下载: 导出CSV

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

    Table 6.  single-round iteration average test results

    DatasetStrategyGbfGbsAvf
    SRBCTWith0.90149.20.82
    Without0.87200.70.78
    Leukemia1With0.87221.10.78
    Without0.83209.10.74
    Leukemia2With0.83448.80.76
    Without0.83365.50.76
    DLBCLWith0.85218.40.76
    Without0.81195.40.72
    9TumorWith0.52218.90.38
    Without0.51224.50.38
    Brain1With0.71265.80.62
    Without0.67257.40.59
    Brain2With0.73689.90.65
    Without0.74892.00.65
    LungWith0.87435.70.83
    Without0.831465.70.79
    GLIOMAWith0.79531.00.72
    Without0.75601.50.68
    LSVTWith0.7544.50.67
    Without0.7143.60.63
    CarcinomWith0.83428.40.77
    Without0.80333.70.73
    下载: 导出CSV

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

    Table 7.  Ablation experiment results with hierarchical initialization strategy

    ModelSRBCTLeukemia1
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO1.652.3100.0099.676.653.195.8392.83
    I'1.451.7100.0099.257.645.598.0693.33
    ModelLeukemia2DLBCL
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO16.134.393.8992.33 7.959.690.6788.03
    I'22.432.991.6790.227.652.092.5089.00
    Model9TumorBrain1
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO6.039.058.3352.33 11.7 29.877.0870.08
    I'6.846.058.3354.0011.128.277.9270.59
    ModelBrain2Lung
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO16.177.875.4266.75 27.6381.092.5691.41
    I'14.299.578.7573.3328.6422.094.3291.86
    ModelGLIOMALSVT
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO4.3181.277.5069.41 0.732.379.6078.48
    I'4.5130.475.4270.000.737.879.1177.13
    ModelCarcinom
    TimeSizeBestMean
    VLPSO44.9145.987.7685.08
    I'54.1145.792.2988.29
    下载: 导出CSV

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

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

    ModelSRBCTLeukemia1
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO1.652.3100.0099.676.653.195.8392.83
    II'0.965.6100.0099.424.247.695.8391.25
    ModelLeukemia2DLBCL
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO16.134.393.8992.33 7.959.690.6788.03
    II'12.329.793.8992.006.831.692.3387.50
    Model9TumorBrain1
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO6.039.058.3352.33 11.7 29.877.0870.08
    II'4.046.356.6755.677.535.475.0071.33
    ModelBrain2Lung
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO16.177.875.4266.75 27.6381.092.5691.41
    II'9.163.677.9271.6710.0197.592.6189.88
    ModelGLIIOMALSVT
    TimeSizeBestMeanTimeSizeBestMean
    VLPSO4.3181.277.5069.41 0.732.379.6078.48
    II'2.358.382.9274.080.435.482.3378.69
    ModelCarcinom
    TimeSizeBestMean
    VLPSO44.9145.987.7685.08
    II'35.9148.691.0288.07
    下载: 导出CSV
  • [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.
  • 加载中
图(6)表(8)
计量
  • 文章访问数:  76
  • HTML全文浏览量:  122
  • PDF下载量:  0
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-12-07
  • 网络出版日期:  2021-03-24

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

    作者简介:李腾飞(1996-):硕士生,主要研究方向为演化计算、人工智能。E-mail:tyrandesal@163.com
    通讯作者: 冯翔, xfeng@ecust.edu.cn
  • 1. 华东理工大学信息科学与工程学院,上海 200237
  • 2. 上海智慧能源工程技术研究中心,上海 200237

摘要: 针对大规模数据集上的特征选择问题,一种变长表示的粒子群特征选择方法(VLPSO)表现出了良好的性能。然而,其完全随机的粒子生成方式导致初始化阶段具有一定的盲目性。同时,VLPSO单一的更新机制和种群间的信息隔离也影响了模型的分类性能。为了解决VLPSO的缺陷,提出了一种基于多行为交互的变维协同进化特征选择方法(M-CVLPSO)。首先,为了改善随机初始化带来的盲目性,采用连续空间上的层次初始化策略,从期望上缩短了初始解与最优解之间的距离。其次,将粒子根据适应度分为领导者、追随者与淘汰者,在迭代过程中采用多种更新策略动态平衡算法的多样性与收敛性。同时,将维度缩减指标加入到适应度函数中,进一步增强了算法在部分数据集上的性能。从理论上证明了该算法的收敛性,并基于11个大规模特征选择数据集在分类精度、维度缩减和计算时间上进行实验分析。实验结果表明,本文算法相较于4种对比算法具有更好的综合表现。

English Abstract

  • 近年来,特征选择技术已经成为数据预处理特别是高维数据预处理中的一个重要技术。随着大数据时代的到来和网络技术的发展[1],在许多机器学习应用中收集的特征数量变得越来越大。由于“维数诅咒”[2-3]的存在,传统的机器学习方法往往不能很好地处理高维数据。值得注意的是,随着维数的增加,数据空间中可能存在的实例数量也在极速膨胀,使得可用数据变得稀疏, 而这些数据的增长通常与有限元的数量成指数关系。更重要的是,并不是所有的特征都有用,与提供有用信息的特征不同,不相关特征提供误导信息,导致学习性能的下降。而冗余特征提供了与其他特征相同或相似的信息,浪费了大量计算资源,严重影响了学习效率。因此,越来越多的学者开始探究更好的特征选择方法,进而从高维的原始特征集中剔除不相关的冗余特征以减少数据的维数,简化学习模型和提高算法的性能[3]

    粒子群优化算法(PSO)[4]是一种基于群体的全局搜索能力较强的算法,是用作特征选择的一种有效技术。目前,PSO在特征选择中展现出了良好的应用前景[5]。然而,它的大多数应用通常是低维的,在具有数千个或更多特征的高维数据上的性能依然有限。

    Liang等[6]提出的综合学习粒子群算法(CLPSO)是连续粒子群优化算法的一种变体。该算法为每个粒子维持了一个样本池,粒子的每个维度参照样本池中的粒子编号进行学习,保持了种群的多样性,缓解了粒子群普遍存在的提前收敛问题。Qian等[7]将概率模型和粗糙集嵌入标签重要性中,根据特征依赖和粗糙集,设计了一种新的多标签分类特征选择算法。Zhou等[8]对每个特征进行基于熵的切点优先级排序,同时采用概率指导的局部搜索策略提升算法的性能。Huda等[9]提出了新的初始化与更新方式,有效地提升了粒子群算法在特征选择上的性能。

    Fister等[10]将自适应差分算法与神经网络进行结合,取得了令人鼓舞的进展。Ji等[11]提出了改进的PSO算法(IBPSO),引入了局部搜索因子、全局搜索因子,同时采用变异策略维持种群多样性,取得了较大的性能改善。Chen等[12]将PSO算法与差分算法(DE)结合,提出了混合粒子群算法(HPSO-DE),差分算法用于维持群体多样性,提升算法的探索能力。Guan等[13]提出了一种搜索历史导向的差分进化算法(HGDE),该方法利用存储在二叉空间划分树中的搜索历史来增强其选择特征组合的能力。Nguyen等[14]提出由期望的最大特征数目确定每个粒子的维度,该方法所选出的特征子集远远小于典型解,不过难以确定期望的特征数量。Gu等[15]提出的竞争粒子群算法(CSO)引入了粒子竞争行为,在大规模优化上展现出了良好的效果,然而算法的计算效率还有待优化。Tran等[16]提出了可变维度的粒子表示方式,大大缩小了搜索空间。利用维度划分机制令PSO可以跳出局部最优,取得了更小的特征子集和更高的计算效率。

    本文受Tran等[16]提出的变长粒子维度表示思想的启发,提出了一种基于多行为交互的变维协同进化特征选择算法(M-CVLPSO)。针对VLPSO初始化阶段的盲目性,采用连续空间上的层次初始化策略,使粒子分布更加均匀,从期望上缩短了初始解与最优解的距离。在更新阶段,通过适应度将粒子分为领导者、追随者与淘汰者,不同角色的粒子采用不同的更新方式,动态平衡算法各个阶段的多样性与收敛性。领导者的合作行为将群体知识从低维传向高维,有效解决了VLPSO的信息隔离缺陷。最后,将维度缩减率加入适应度函数中,进一步加强了M-CVLPSO在部分数据集上的表现。

    • 全局优化问题可描述为在一个有限对象构成的解空间中找出最优解的一类问题。根据优化函数的优化目标,全局优化问题可以被分为最小值优化问题和最大值优化问题,而这两类问题又可以相互转换。

      假设优化函数$f(x)$具有$m$维变量$({x_1},{x_2},\cdots,{x_m})$,令${{ X}_1} = ({x_{11}},{x_{21}},\cdots,{x_{m1}})$$m$维变量的一个可行解,${ S} = \{ {X_1},{X_2},\cdots,{X_n}\}$为所有可行解构成的解空间,则全局优化问题可以表示为求解$f(x)$的最小值。

      其目标是找到一个可行解${X^*}$满足公式:

      特征选择可以被表述为如下的最小全局优化问题:

      其中,${ \chi} \in {{\bf R}^N}$表示潜在可行解集。为了表示被选择的特征集,${ x}$采用长度为$N$的连续编码,$N$为原始特征集中的特征总数。对于${ x}$中的每一维,如果该维度上的值大于阈值,则代表该特征被选择,反之则为遗弃特征。这样,特征选择就变为了寻找最佳特征子集${{ x}^*}$的组合优化问题,以最小化所选特征训练的分类模型的错误率。

    • VLPSO采用基于CLSPO的变长粒子表示方法。基于变长表示,粒子的维度可以小于原始特征数目,该表示方法依然基于向量,不同种群的粒子具有不同长度的表示。图1示出了VLPSO模型的粒子表示方式。

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

      Figure 1.  Clpso-based variable-length particle representation

    • 由于不同种群的粒子具有不同的维度,因此需要对原始特征进行合理的划分。采用对称不确定度(SU)来计算特征与类标签的相关程度。假设原始特征数目为$D$,期望划分的种群数目为$M$,待初始化的粒子总数为$N$,从第一个维度开始依次计算特征$X$与类标签$Y$的对称不确定度${S_i}$${\rm{SU}}(X|Y)$定义为

      ${\rm{IG}}(X|Y)$为变量$X$$Y$之间的依赖度,定义为

      其中:$H(X)$为变量$X$的信息熵;$H(X|Y)$为变量$X$在给定$Y$下的条件熵。${\rm{SU}}(X,Y) \in [0,1]$$X$$Y$的相关性与对称不确定度成正比。

      按照${S_i}$从大到小对原始特征进行排序,并根据式(6)计算第$m$个种群的粒子维度:

      每个种群的粒子数目为

      在排序后的原始特征中从前向后依次选择${D_m}$个特征作为第$m$个子种群的原始特征空间。

    • 模型采用CLPSO的更新过程,其中,粒子可以向群内的任意粒子学习,在每个维度上通过概率${P_{{c_i}}}$决定粒子$i$选择自身还是另一个粒子作为学习样本,计算公式为

      其中:$S$为种群规模;${\rm rank}{_i}$为该粒子在种群中的适应度排名。

      利用大小为2的锦标赛机制为每个维度确定学习样本,一个粒子的学习样本将保持不变,直到该粒子连续未更新的代数超过设定的阈值。此时,将重新替换该粒子所有维度上的样本序号。CLPSO速度更新公式如下:

      其中:${r_{id}}$$[0,1]$上的随机数;${\rm Examplar}_{id}^t$为粒子$i$的学习样本在$d$维度上的值。

    • 为了使粒子群优化算法跳出可能的局部最优解,当${\rm gbest}$在预先设定的迭代次数下没有变化时,计算每个群体中所有粒子的平均适应度,标记当前最优种群为${\rm Swar{m_{best}}}$,保持${\rm Swar{m_{best}}}$粒子的维度${\rm BestLen}$不变,其余种群按照式(10)更新自身的维度:

      其中:$ k $为种群的序号,且不包括${\rm Swar}{{\rm m}_{best}}$$M$为种群数目。

      若新维度小于原维度的种群,按照降序从末尾删除指定个数的特征;若新维度大于原维度的种群按照升序从尾部挑选指定个数的特征加入。

    • VLPSO模型采用完全随机的粒子初始化方式,导致初始粒子在解空间内的分布盲目且不均匀,降低了初始种群的探索能力。由于算法的后续求解都依赖于初始粒子在高维特征空间的探索,因此,初始群体的生成策略对后续的寻优过程有着潜在且深远的影响。初蓓等[17]在离散空间上提出了一种二向初始化策略,但其搜索方向仅为前向和后向,仍不能保证初始点在搜索空间的多向均匀分布。其次,本文采用的是连续表示的粒子群方法,需要提出一种连续空间上的多向初始化策略。为此,本文提出了一种层次初始化策略。

      在种群进行初始化时,假设每个种群粒子数目为$N$,当前种群粒子的特征维度为$D'$,预期差异群体数目为${M_{\rm div}}$,则依次随机选中$\left\lfloor {D'/M_{\rm div}} \right\rfloor$$\left\lfloor {2D'/M_{\rm div}} \right\rfloor$、…、$\left\lfloor {({M_{\rm div}} - 1)D'/{M_{\rm div}}} \right\rfloor$维度的特征进行差异群体的粒子初始化。因为采用连续表示,不能简单地将维度置为1或0,而是加入选择阈值${\rm Thre}$来帮助初始化。设某粒子待初始化维度为${D_i}$,则有

      其中:${\rm{Rand}} (a,b)$表示区间${\rm{[a,b]}}$上的随机数。

      每个差异群体的粒子数目均为$N/{M_{\rm div}}$图2示出了层次初始化策略下的粒子分布,红点代表理论最优解,层次初始化策略将初始群体均匀散布在不同维度的搜索空间,增强了初始粒子群体的多样性以及后续的探索能力,一定程度上降低了随机带来的盲目性。

      图  2  层次初始化

      Figure 2.  Hierarchical initialization

    • VLPSO模型在进化过程中对所有粒子采用单一的更新策略。然而,多项研究表明适应度较差的粒子应该加强其全局探索行为的比重,而适应度较好的粒子应该加强其局部探索行为的比重,因此,不同适应度排名的粒子所需要的更新行为是不同的。本文根据适应度排名将粒子分为领导者(排名在前20%)、追随者(排名在20%~75%)与淘汰者(排名在后25%),提出了一种包含竞争、合作与同化的多行为更新策略。根据进化过程中粒子适应度排名的变化,自适应采取不同行为来完成粒子的更新。

    • 淘汰者采用竞争行为进行更新。在每一代进化结束后,环境均会对粒子的适应度进行评判,并淘汰部分粒子,这样更加有利于维护进化群体的质量,以快速寻找到最优解。新生粒子的产生可以借鉴已有的知识,站在“巨人”的肩膀上能够保证新生粒子的质量。

      因为采用变长表示,因此不同种群探索的解空间不同,粒子与粒子的竞争主要存在于单个种群的内部,设第$m$个种群内的粒子数目为${N_m}$,在具有淘汰行为的种群中,对于淘汰粒子$k$的每个维度,在领导者中随机选取两个粒子${x_i}$,${x_j}$,设${\rm Ran}{{\rm k}_{{x_i}}} > {\rm Ran}{{\rm k}_{{x_j}}}$,更新公式如下:

      其中:${f_1}$${f_2}$为自适应系数;${\rm Ran}{{\rm k}_{{x_i}}}$${\rm Ran}{{\rm k}_{{x_j}}}$分别为粒子${x_i}$${x_j}$在种群中的适应度排名。

      这种粒子更替策略使目标粒子不会完全被单一粒子所吸引,增强了生成粒子的多样性和群体的全局探索能力。同时由于目标粒子对群体中优秀粒子知识的继承性,保证了新生粒子的质量。

    • 领导者采用合作行为进行更新。VLPSO采用了多种群寻优,却完全隔离了彼此间的信息,浪费了大量的优秀知识。由于低维群体探索更小的特征空间,相同迭代次数内在交叉维度上通常较高维群体能够找到更优的特征子集,因此,为了有效利用已有知识,让高维群体的领导者借鉴低维群体领导者的交叉维度,将知识从低维传向高维。

      首先,将所有种群按照粒子维度从小到大排序,设待更新种群序号为$i$,将序号为$i - 1$的种群按照粒子适应度进行排序,得到${\rm Swarm}_{\rm sort}^{i - 1}$。选定待学习的高维粒子${X_{\rm HV}}$,假设排名为$k$,将${\rm Swarm}_{\rm sort}^{i - 1}$中所有适应度高于${X_{\rm HV}}$的粒子加入到样本池中,如果这样的低维粒子共有$c$个,则设样本池${\rm Exampla}{{\rm r}_{{X_{\rm HV}}}} =\{ {X_1}, $$ {X_2},\cdots,{X_{c - 1}},{X_c}\}$。若${\rm Exampla}{{\rm r}_{{X_{\rm HV}}}}$为空,且满足$p_r^i < p_c^i$,则按照式(14)对${X_{\rm HV}}$所有维度进行更新:

      其中:${c_1}$为常数;${r_1}$${r_2}$$[0,1]$之间的常数;${\rm Pbes}{{\rm t}_d}$为粒子$i$历史最优值$d$维度上的值;$p_c^i$为利用式(8)计算的学习概率;$p_r^i$$[0,1]$上的随机数。

      $p_r^i < p_c^i$,利用所属种群样本池进行更新。如式(15)所示

      其中:${\rm Exampla}{{\rm r}_d}$为学习样本$d$维度的值。

      ${\rm Exampla}{{\rm r}_{{X_{\rm HV}}}}$不为空,对${X_{\rm HV}}$与低维样本池交叉的维度利用低维度种群生成的样本池进行更新,并且概率判断总是成立;对${X_{\rm HV}}$独有的维度,利用所属种群样本池进行更新。两种情况下的更新公式均同式(15)。

      可以看出,仅当低维群体存在适应度优于待更新个体的粒子时,才会将交叉维度的样本池替换为低维群体,否则,仍然利用待更新粒子在所属种群中生成的样本池更新所有的维度。

    • 追随者采用同化行为进行更新。在种群进化的过程中,劣势粒子更加倾向于向种群内部的其他优秀粒子学习。本文借鉴社会学习粒子群算法(SL-PSO)[18]的思想,引入社会平均影响的概念。其实验已经表明该因子能有效平衡粒子的多样性和收敛性。设待更新的粒子为${X_i}$,所属种群为${\rm Swar}{{\rm m}_j}$,则该种群的社会平均影响为

      其中:${N_j}$为该种群的粒子数目。

      对当前种群进行适应度排序,序号越低的粒子适应度越大,不同种群的序号独立,排序后的种群为${\rm Swar}{{\rm m}_{{\rm sort}\_j}}$,生成${X_i}$的样本池${\rm Exampla}{{\rm r}_{{X_i}}} = \{ {X_1},{X_2},\cdots, $$ {X_{{\rm ran}{{\rm k}_{{X_i}}} - 2}},{X_{{\rm ran}{{\rm k}_{{X_i}}} - 1}}\}$,设待更新为维度$d$,若满足$p_r^i > p_c^i$,则有:

      $p_r^i < p_c^i$,则从${\rm Exampla}{{\rm r}_{{X_i}}}$中随机选择一个学习样本${\rm Exampla}{{\rm r}^i}$,粒子更新公式为

      其中:${r_1}$${r_2}$${r_3}$$[0,1]$之间的常数;${\rm Pbest}_d^i$为粒子$i$历史最优值$d$维度的值;$\varepsilon $为引诱系数;$\beta $为常数;${\rm ParSiz}{{\rm e}_i}$为粒子$i$的维度,粒子$i$属于种群$j$${N_j}$为第$j$个种群的粒子个数。

      图3示出了多种行为在不同维度群体间的作用方式。种群内部进行淘汰和同化行为,种群间由领导者进行合作行为,共同完成种群的迭代更新。

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

      Figure 3.  Particle update under multi-behavior interaction strategy

    • 虽然分类精度可以度量特征子集的性能,但是仍有许多潜在的局限性。 Tran等[16]在2016年提出了结合分类精度与实例间距离度量的适应度函数评估方法,考虑了特征子集区分各类别实例的程度,定义为

      针对类间距离${D_b}$的计算公式,以实例到类外粒子的最小距离作为参考,取其平均值来评估该特征子集对不同类别实例的分离程度,定义为

      而类内距离${D_w}$以实例到类内粒子的最大距离作为参考,取其平均值来评估同一类粒子间的聚合程度:

      该适应度函数旨在最大化不同类别实例之间的距离,最小化同类别实例之间的距离。

      维度缩减也是特征选择问题中需要关注的,更少的特征意味着更小的冗余、更高的计算效率。基于此,本文提出了一种新的适应度函数,定义如下:

      其中:$\gamma $$\alpha $为待设定的参数;${\rm VDesc}$为维度缩减率;${V_{\rm sub}}$为特征子集的维度;${V_{\max }}$为当前所有种群中的最大特征维度。

      该适应度函数在分类精度与实例类间距离相近的状况下,会优先选择维度较小的粒子。因此,在维度重划分时,低维种群更容易成为最优种群,从而在一定程度上更快地降低群体的平均维度,加速模型的迭代进程。但是,分类精度与类间距离仍然是主要的选择标准,因此后期应分配更小的权重。

    • 与大多数粒子群优化算法理论收敛性分析相似[19-20],本文从理论上分析M-CVLPSO模型的收敛性。应该指出的是,证明并不保证收敛到全局最优。

      在不失一般性的前提下,整个群体的收敛可以更具体地看作是任意粒子行为向量中各维的收敛。理论上,应该存在一种平衡来诱导这种收敛[21]。考虑粒子$i(1 \leqslant i \leqslant m)$$d(1 \leqslant d \leqslant n)$个维度的更新。一旦满足$p_r^i < p_c^i$$X_d^i(t)$将会通过式(26)进行更正:

      式(14)与式(15)的区别在于是向${\rm Pbest}_d^i$还是${\rm Examplar}_d^i$学习,而粒子本身也属于样本池的一部分,因此式(15)是更具有一般性的表达方式。如果将式(15)代入式(26),并替换所有随机参数为其期望值,可以得到:

      同理,将式(18)代入式(26),并替换所有随机参数为其期望值,可以得到:

      其中:$\dfrac{1}{2}$${r_1}$${r_2}$${r_3}$的期望值。

      定理1 式(27)与式(28)描述的动态系统收敛于平衡状态

      证明 对式(27),令$\theta = \dfrac{{{c_1}}}{2}$$p = {\rm Examplar}_d^i(t)$,则式(27)可以被重写为

      对式(28),令$\theta = \dfrac{{1 + \epsilon }}{2}$$p = \dfrac{1}{{1 + \epsilon }}{\rm Examplar}_d^i(t) + $$ \dfrac{\epsilon }{{1 + \epsilon }}{\bar X_d}(t)$,则式(28)可以被重写为

      可以发现,两式的基本形式是一致的,因此可以统一验证其收敛性。式(30)中描述的搜索系统可以看作是一个动态系统,因此可以利用动态系统稳定性理论对系统进行收敛性分析。为此,将式(30)描述的系统重述为

      其中:${ A}$在动力系统理论中称为状态矩阵;${ p}$为外部输入,驱动粒子行为向量到达特定状态;${ B}$为输入矩阵,控制外部环境对粒子动力学的影响。

      如果存在一个平衡${{ y}^*}$对任意$ t $满足${{ y}^*}(t + 1) = $$ {{ y}^*}(t)$,可以从式(31)和式(32)中计算出:

      收敛性取决于状态矩阵${ A}$的特征值:

      其特征值为

      平衡点是一个稳定吸引子,其收敛的充要条件是$\left| {{\lambda _1}} \right| < 1$并且$\left| {{\lambda _2}} \right| < 1$,可以得到:

      对于式(27),因为$\theta = \dfrac{{{c_1}}}{2}$,而${c_1}$总是大于0,该式恒成立。

      对于式(28),将$\theta $利用等式$\theta = \dfrac{{1 + \epsilon }}{2}$替换为$\epsilon $,得到:

      $\epsilon $利用$\varepsilon = \beta \times ({\rm ParSiz}{{\rm e}_i}/{N_j})$替换为${\rm ParSiz}{{\rm e}_i}$,条件转换为

      由于${\rm ParSiz}{{\rm e}_i} > 0 > - \dfrac{{{N_j}}}{\beta }$恒成立,则系统总是收敛于平衡状态。

    • 本文针对VLPSO随机初始化的盲目性、更新策略的单一性问题,分别提出了层次初始化策略和多行为交互策略。M-CVLPSO算法的伪代码如下:

      输入:最大迭代轮数T,种群个数NbrDiv,最大未改进轮数k

      输出:特征子集向量

      Begin

      (1)根据式(4)计算特征与类别间的SU值并降序重排

      (2)While Div<NbrDiv:

         {

      (3) 根据式(7)计算该种群的规模DivSize

      (4) 根据式(6)计算该种群粒子的维度ParLen

      (5) 层次初始化策略生成DivSize个ParLen长度的粒子

      (6) 计算适应度fitness与历史最优值pbest

      (7) Div++

          }

      (8)通过式(8)为所有粒子计算更新概率pc

      (9)while T < Tmax

          {

      (10)  从维度最低的种群:

              {

      (11)    通过fitness排序将粒子角色分为淘汰者、追随者与领导者

      (12)    淘汰者根据策略3.3.1进行淘汰行为

      (13)    追随者根据策略3.3.2进行同化行为

      (14)    领导者根据策略3.3.3进行合作行为

              }

      (15)  If gbest已经k轮未更新:

              {

      (16)    进行维度重划分

      (17)    更新粒子的fitness和pbest

              }

          }

      (18)输出最优特征子集向量

      End

    • 实验环境:实验中所用编程语言为java,JDK版本为1.8。实验计算机配置为CPU:Intel Core i7(2.2GHz)、内存大小:16GB、固态大小:512GB。

    • 在11个UCI公开数据集上对M-CVLPSO算法的性能进行测试,表1给出了数据集的具体信息。其中,Features表示数据集的维度,#Ins表示实例数量,#Class表示类别数目,%Smallest class和%Largest class分别表示实例数量最少和最多的类别占总实例数的比重。对每个数据集的划分采用10交叉验证方式。以测试集的分类准确率(Classification Accuracy,CA)和平均类间距离(Classification Mean-Distance,CMD)作为评价准则。CA是正确分类的实例数占总实例数的比例,即分类精度;CMD是两两分类实例间的平均间距,代表了分类模型的鲁棒性及泛化能力。

      Dataset#Features#Ins.#Class%Smallest class%Largest class
      SRBCT23088341335
      Leukemia153277231353
      Leukemia2112257232839
      DLBCL54697722575
      9Tumor5726609315
      Brain15920905467
      Brain2103675041430
      LSVT31012623366
      Lung126002035368
      Carcinom918217411315
      GLIOMA44355041430

      表 1  实验数据集

      Table 1.  Datasets

    • 为了验证M-CVLPSO算法的性能,将其与目前表现最好的同领域算法进行对比,其中,具有代表性的有原始粒子群算法(PSO)[4]、综合学习粒子群算法(CLPSO)[6]、增强综合学习粒子群算法(ECLPSO)[22]、可变维度粒子群算法(VLPSO)[16]等。在大规模以及超大规模的数据集上从寻优精度、维度缩减能力以及计算效率3个方面验证每个算法的特征选择能力。各个算法的公共参数保持一致,以确保实验的公平性,详细参数设置如表2所示。

      ParameterSetting
      Population sizeFeatures/20
      Maximun iterations100
      c1=c1.49445
      w0.9−0.5×(curr_iter/max_iter)
      Threshold for selected feature0.6
      Data set partitioning10 cross-fold
      Max iterations for renew7(CLPSO,ECLPSO,VLPSO)
      Number of divisions12(M-CVLPSO,VLPSO)
      Max iterations for length changing9(M-CVLPSO,VLPSO)

      表 2  参数设置

      Table 2.  Parameter setting

    • 由于粒子群优化算法是一种随机算法,因此针对每种方法在每个训练集上分别运行10个10交叉验证。一个10交叉验证包含10次完整的运行结果,取这10次完整运行结果的均值作为该次10交叉验证的结果。算法单次10交叉验证均采用不同的随机数种子,但不同算法间保持随机数种子的一致,100次实验结果的均值如表3所示。其中,Time表示算法在该数据集上的单次平均运行时间,更少的时间代表更高的运算效率;Size表示最优特征子集的平均维度,越小的维度代表更高的维度缩减能力;Best表示10次10交叉验证中出现的最优单次10交叉验证平均分类精度;Mean则为10次10交叉验证的平均分类精度。表4示出了各个算法在4个性能指标上的friedman排名,图4示出了各个算法在11个数据集上的详细性能指标排名情况。

      AlgorithmLSVTCarcinom
      TimeSizeBestMeanTimeSizeBestMean
      M-CVLPSO0.435.586.8980.2235.9152.590.0787.78
      VLPSO0.733.283.1480.1946.2136.087.7685.38
      ECLPSO2.0138.083.6378.99311.84182.284.1381.47
      CLPSO1.7137.779.6776.49234.14157.088.9786.79
      PSO2.0141.381.2477.86360.42174.777.2073.83
      Full/310.076.80//9182.073.65/
      AlgorithmSRBCTLeukemia1Leukemia2
      TimeSizeBestMeanTimeSizeBestMeanTimeSizeBestMean
      M-CVLPSO0.863.7100.0099.704.548.798.0695.4912.129.895.5692.94
      VLPSO1.651.1100.0099.587.057.995.8392.9416.234.195.5691.66
      ECLPSO8.41051.090.8386.0841.52432.184.4482.22182.65123.290.5687.44
      CLPSO6.61056.4100.0098.9532.52435.795.5694.6588.95117.193.3391.66
      PSO9.41103.292.5088.9447.12601.587.3680.97163.85427.792.2289.67
      Full/2308.086.96//5327.079.72//11225.088.78/
      AlgorithmDLBCL9TumorBrain1
      TimeSizeBestMeanTimeSizeBestMeanTimeSizeBestMean
      M-CVLPSO4.630.994.0089.564.143.766.6758.007.333.280.4275.56
      VLPSO7.552.891.3386.516.239.958.3353.3310.826.677.0870.74
      ECLPSO47.32500.384.8381.6939.02621.445.0042.8367.42721.480.0074.17
      CLPSO37.22487.996.5093.9832.12604.458.3353.8353.72679.577.5075.12
      PSO52.72682.586.3383.5444.12787.945.0041.6771.52921.077.0873.33
      Full/5469.084.12//5726.037.23//5920.071.67/
      AlgorithmBrain2LungGLIOMA
      TimeSizeBestMeanTimeSizeBestMeanTimeSizeBestMean
      M-CVLPSO8.961.080.0069.549.6154.593.4091.032.564.8978.7573.29
      VLPSO13.481.879.5868.2927.6369.493.2091.284.3148.277.5069.91
      ECLPSO76.04703.769.5864.2478.11517.793.0791.0119.52033.980.0073.95
      CLPSO58.24706.582.0879.9562.41506.594.2592.0215.31991.182.0876.16
      PSO84.75089.067.0862.1384.71613.793.1890.4323.42207.873.5668.28
      Full/10367.062.50//3312.086.83//4434.074.50/

      表 3  平均测试结果

      Table 3.  Average test results

      AlgorithmTimeSizeBestMeanComprehensive
      M-CVLPSO1.001.451.451.545.44
      VLPSO2.001.552.632.919.09
      ECLPSO4.093.823.913.9115.73
      CLPSO3.003.362.092.0010.45
      PSO4.904.823.914.5418.17

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

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

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

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

      从特征子集的维度(Size)来看,PSO、CLPSO和ECLPSO均高于M-CVLPSO若干倍。在维度较低的数据集上,如LSVT、SRBCT等,通常在20倍以内,而在超大规模数据集上,如Leukemia1、Leukemia2、Brain1、Brain2、DLBCL、9Tumor等,最高可以达到170倍。与VLPSO相比,M-CVLPSO在7个数据集上的平均维度低于VLPSO,其中在GLIOMA、Lung、DLBCL、Brain2上的缩减相当明显,最高减少了一半以上的维度。而在剩余的5个数据集上,M-CVLPSO与VLPSO表现相当,VLPSO的平均维度略低于M-CVLPSO。

      从寻优的时间复杂度(Time)来看,M-CVLPSO模型在11个数据集上的表现最好。PSO、ECLPSO和CLPSO均高于M-CVLPSO至少5倍以上的时间。而与VLPSO相比,这个倍数在1.3~2.8。分析原因,一是采用了变长维度的表示方法,而低维度粒子相对于高维度粒子拥有更高的更新计算效率;二是相对于VLPSO,多行为交互的更新方式,能够更快的缩减种群的平均维度,减少了在高维空间探索的代数,从而降低了计算时间。图5示出了各个算法寻优过程中种群平均维度的变化情况。

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

      Figure 5.  The average particle dimension varies with iteration

      从寻优精度来看,在最佳寻优精度(Best)上,M-CVLPSO在7个数据集上取得了最好的结果,获得了最高8%的提升。在3个数据集上取得了第二,与第一最高相差2.5%。在GLIOMA数据集上表现较差,排名第三,与CLPSO相差3.33%。 CLPSO在GLIOMA、Brain2、Lung、DLBCL上的最优精度略高于M-CVLPSO,但是特征子集的维度和寻优的时间复杂度远远高于M-CVLPSO。

      平均寻优精度(Mean)方面,M-CVLPSO依旧在7个数据集上取得了第一,最高提升4.67%,同时在Brain2、DLBCL上取得了第二名。而在GLIOMA、Brain2、DLBCL数据集上,CLPSO表现强势,取得了第一。各算法在寻优过程中的最优粒子适应度曲线变化情况如图6所示。

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

      Figure 6.  Curves of optimal particle fitness

    • 从3.3节的实验结果可以看出,在DLBCL、Lung、Brain2以及GLIOMA数据集上,M-CVLPSO的精度没有达到最好。从粒子的维度来分析,发现在这4个数据集上M-CVLPSO模型的平均粒子维度远小于包括VLPSO在内的其他算法,可能是模型在后期仍在探索新的维度空间而在有限代数内未能及时收敛。因此,在适应度函数的计算中加入了维度缩减率,期望在前期更快地降低种群维度,从而使模型有更充分的代数进行低维空间上的探索。同样,在M-CVLPSO中使用新的适应度函数在上述4个数据集上进行10个10交叉验证,表5示出了100次实验的平均值。其中,I是未加入维度缩减因子的模型,II是加入了维度缩减因子的模型,ALL-Best则代表表3中所有模型在该数据集上能够取得的最好结果。可以看出,在这4个数据集中,其在DLBCL、Lung和Brain2上的结果均优于M-CVLPSO,且在最优精度上高于原来所有模型的最优值。不过,在平均精度上其相较于M-CVLPSO有所提升,仍然低于原来的最优平均精度,而在粒子维度与运算时间上则基本相当。从实验结果来看,维度缩减率能够影响模型分类精度,且对于大规模数据集上的提升较为明显。

      ModelDLBCLBrain2
      TimeSizeBestMeanTimeSizeBestMean
      ALL-Best4.630.996.5093.988.961.082.0879.95
      I4.6 30.994.0089.568.961.080.0069.54
      II5.131.197.591.03 9.365.982.5073.63
      ModelLungGLIOMA
      TimeSizeBestMeanTimeSizeBestMean
      ALL-Best9.6154.594.2592.02 2.564.982.0876.16
      I9.6154.593.4091.032.564.978.7576.67
      II10.1149.094.2790.962.671.076.6770.04

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

      Table 5.  Mean test results with new fitness function

    • 为了验证层次初始化策略的有效性,使用未加入该策略的M-CVLPSO-Without算法进行10交叉验证,每次实验只进行一轮迭代,对10次实验结果的最优粒子适应度(Gbf)、最优粒子维度(Gbs)以及平均粒子适应度(Avf)求平均值,结果如表6所示。可以看出,在绝大部分数据集上,加入了层次初始化策略后,在一轮迭代后最优粒子适应度与平均粒子适应度取得了较大幅度的提高,提升幅度通常在0.03~0.04。而在最优粒子的维度上表现与随机初始化相当。这表明层次初始化策略能有效提高初始化粒子的适应度,但对粒子的维度缩减无明显提高。

      DatasetStrategyGbfGbsAvf
      SRBCTWith0.90149.20.82
      Without0.87200.70.78
      Leukemia1With0.87221.10.78
      Without0.83209.10.74
      Leukemia2With0.83448.80.76
      Without0.83365.50.76
      DLBCLWith0.85218.40.76
      Without0.81195.40.72
      9TumorWith0.52218.90.38
      Without0.51224.50.38
      Brain1With0.71265.80.62
      Without0.67257.40.59
      Brain2With0.73689.90.65
      Without0.74892.00.65
      LungWith0.87435.70.83
      Without0.831465.70.79
      GLIOMAWith0.79531.00.72
      Without0.75601.50.68
      LSVTWith0.7544.50.67
      Without0.7143.60.63
      CarcinomWith0.83428.40.77
      Without0.80333.70.73

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

      Table 6.  single-round iteration average test results

      同时,对仅加入层次初始化模块的模型I进行5次10交叉验证,所用的随机数种子和公共参数与VLPSO保持一致。对50次实验结果取平均值,得到的各项数据如表7所示。

      ModelSRBCTLeukemia1
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO1.652.3100.0099.676.653.195.8392.83
      I'1.451.7100.0099.257.645.598.0693.33
      ModelLeukemia2DLBCL
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO16.134.393.8992.33 7.959.690.6788.03
      I'22.432.991.6790.227.652.092.5089.00
      Model9TumorBrain1
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO6.039.058.3352.33 11.7 29.877.0870.08
      I'6.846.058.3354.0011.128.277.9270.59
      ModelBrain2Lung
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO16.177.875.4266.75 27.6381.092.5691.41
      I'14.299.578.7573.3328.6422.094.3291.86
      ModelGLIOMALSVT
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO4.3181.277.5069.41 0.732.379.6078.48
      I'4.5130.475.4270.000.737.879.1177.13
      ModelCarcinom
      TimeSizeBestMean
      VLPSO44.9145.987.7685.08
      I'54.1145.792.2988.29

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

      Table 7.  Ablation experiment results with hierarchical initialization strategy

      可以看出加入了层次初始化后,相较于VLPSO,模型I'在9个数据集上取得了更好的最优精度,最高有4.53%的提升,平均有1.63%的最优精度提升;在8个数据集上取得了更好的平均精度,最高有6.58%的提升。而在LSVT、Leukemia2和SRBCT数据集上则是小幅度低于原算法。从时间和维度来看,与原算法基本一致,表明层次初始化能整体上提升粒子适应度,更容易在有限次迭代内找到更好的特征子集,而在维度缩减性能上并无提升。

    • 对仅加入多行为交互模块的模型II'进行5次10交叉验证,所用的随机数种子和公共参数与VLPSO保持一致。对50次实验结果取平均值,得到的各项数据如表8所示。

      ModelSRBCTLeukemia1
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO1.652.3100.0099.676.653.195.8392.83
      II'0.965.6100.0099.424.247.695.8391.25
      ModelLeukemia2DLBCL
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO16.134.393.8992.33 7.959.690.6788.03
      II'12.329.793.8992.006.831.692.3387.50
      Model9TumorBrain1
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO6.039.058.3352.33 11.7 29.877.0870.08
      II'4.046.356.6755.677.535.475.0071.33
      ModelBrain2Lung
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO16.177.875.4266.75 27.6381.092.5691.41
      II'9.163.677.9271.6710.0197.592.6189.88
      ModelGLIIOMALSVT
      TimeSizeBestMeanTimeSizeBestMean
      VLPSO4.3181.277.5069.41 0.732.379.6078.48
      II'2.358.382.9274.080.435.482.3378.69
      ModelCarcinom
      TimeSizeBestMean
      VLPSO44.9145.987.7685.08
      II'35.9148.691.0288.07

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

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

      可以看出加入了多行为交互策略后,相较于VLPSO,模型II'在9个数据集上取得了最优精度,最高有5.42%的提升,平均有2.60%的最优精度提升,而在9Tumor与Brain1数据集上略低于原模型。从时间上来看,新的更新方式大大减少了运行时间,提高了计算效率。从维度上来看,在DLBCL、Lung和GLIOMA数据集上模型II取得了较大幅度的提升,在其他数据集上则基本相当。

      同时,对5种算法在每个数据集上100次实验的迭代过程进行分析。因为迭代过程取决于所使用的更新方式,因此可以探究多行为交互策略的有效性。将100次实验过程中每轮迭代的种群平均维度、最优粒子适应度横向求平均值,迭代曲线如图5图6所示。取特征数目差异较大的6个数据集进行展示,更好地探究算法在不同规模数据集上的性能。

      可以看出,相对于VLPSO,M-CVLPSO能更快地降低种群的平均维度,有效地提高了计算效率,因此大大缩减了寻优的时间。而在最优粒子的适应度上,M-CVLPSO也在4个数据集上取得了更好的平均结果,仅在DLBCL数据集上弱于VLPSO。而表3的实验数据也表明,M-CVLPSO最优粒子代表的特征子集在多数数据集的分类中取得了更高的精度。与其它模型相比,M-CVLPSO在种群维度缩减性能上大幅度领先于PSO、ECLPSO与CLPSO,而在最优粒子适应度上大幅度领先于PSO、ECLPSO,低于CLPSO。不过由CLPSO最优粒子的曲线和表3的寻优结果可以看出,该算法出现了PSO算法的过早收敛问题,导致过拟合现象的产生,从而影响了在测试集上的泛化能力。

    • 针对大规模数据集上的特征选择问题,提出了一种基于多行为交互的变维协同进化特征选择方法。首先,提出了连续空间上的层次初始化策略,从期望上缩短了初始解与最优解的距离,一定程度上克服了因随机带来的盲目性。在更新阶段,通过适应度将粒子分为领导者、追随者与淘汰者,不同角色的粒子采用不同的更新方式,动态平衡算法各个阶段的多样性与收敛性。领导者的合作行为将群体知识从低维传向高维,有效解决了VLPSO的信息隔离缺陷。最后,将维度缩减率加入适应度函数中,进一步加强了M-CVLPSO在部分数据集上的表现。基于11个大规模特征选择数据集在分类精度、维度缩减和计算时间上进行实验分析,相比于4种对比算法,M-CVLPSO具有更好的综合表现。本文主要探究了该方法在大规模数据集上的综合特征选择性能,针对具有特定特征,如非平衡大规模数据集上的探索将是下一步的研究方向。

(6)  表(8) 参考文献 (22)

目录

    /

    返回文章