基于变长PSO的高维特征选择算法（VLPSO）概述

简介

VLPSO是Binh Tran和Bing Xue等人发在人工智能顶尖杂志上IEEE Transactions on Evolutionary Computation 上的一篇解决高维特征选择的PSO算法。

它能够很好地解决高维特征选择问题，尤其是在计算时间上能够大幅度减少。

问题提出

• ①高维特征选择，占内存
• ②高维特征选择，耗时

VLPSO（变长PSO）主要贡献

• ①变长单目标PSO表示方法的提出
• ②改编的粒子维度值交互学习方式，借鉴的CLPSO

粒子的表示

Exemplar：当前个体的每个维度需要学习的粒子的index

Learning Probability：学习率，达到阈值则学习Exemplar值，否则学习自身的pbest

Renew Exemplar Count： 对Exemplar的重置代数

注意这里借鉴的是CLPSO方法：唯一的不同是Pc的计算方法

例如Exemplar那一行的6表示当前粒子的第4个维度更新时需要学习第6个个体的第6个维度。

Exemplar的生成

对每个个体的每个维度的Exemplar采取如下操作

• 计算学习率Pc
• 如果Pc的值小于随机数，则当前维度的Exemplar为自身粒子的index
• 否则
• 随机选择两个粒子，fitness值较大粒子的index作为当前维度的Exemplar

学习率Pc的计算方式

0.05与0.45是CLPSO中提出的经验值

Rank(i)是粒子的排序，它通过信息论的对称不确定性计算

学习率越大，学习自身粒子的可能性就越大

种群长度划分

PopSize=100，NbrDiv是一个预设的值，令其等于5，则种群被分为5组，每组20个个体。

种群维度划分

假设有5000维，NbrDiv=5，则种群每一层的长度如下所示：

注意：从粒子后端除去维度，比如1000维的除去后面4000个维度

进化中种群维度的改变

触发机制：几代过后gBest没有提升

过程：计算每个层次（不同长度）的粒子适应度的均值，寻找最好的Best Division，保持该层次的长度不变，作为最大长度重新划分其它层次的个体

注意：长度变小的层次的粒子是去除的末尾的维度，长度变长的粒子增加相应的维度，这些维度的值随机生成。

流程图

• ①初始化不同长度的种群，初始化Exemplar
• ②对每个粒子判断是否需要重置Exemplar
• ③速度与位置更新，如果pbest在α代后没有更新，则更新学习率Pc下一代需要重置Exemplar
• ④更新gbest
• ⑤如果gbset在β代后没有提升，则种群长度重置
• ⑥停止准则，否进入第三步

适应度函数Fitness，精确度利用KNN计算

注意：使用实例被选择的特征子集来计算曼哈顿距离，其中距离的度量可以判断特征子集划分不同类别实例与聚合相同类别实例的能力。

实验使用的数据集

实验结果请查看原文

论文原文：Tran B, Xue B, Zhang M. Variable-Length Particle Swarm Optimisation for Feature Selection on High-Dimensional Classification[J]. IEEE Transactions on Evolutionary Computation, 2018.

论文Java代码：https://github.com/xyjigsaw/VarLenPSO