基于多目标骨架粒子群优化的特征选择算法

张翠军，陈贝贝，周 冲，尹心歌

(1.河北地质大学 信息工程学院，石家庄 050031； 2.天津工业大学 管理学院，天津 300387)(*通信作者电子邮箱zc0315@foxmail.com)

0 引言

特征选择是数据挖掘以及模式识别中一种重要的数据预处理步骤[1-2]。高维数据特征往往包含大量冗余特征、不相关的和噪声特征。在数据分类问题中，分类性能常常被冗余的、不相关的和噪声特征影响，并增加了计算成本。特征选择的目的是选择出最少的、相关的和有用的特征，以便提高分类性能和降低计算成本。

根据特征子集的选择策略，特征选择方法可以分为两类：过滤式特征选择方法[3]和封装式特征选择方法[4-5]。过滤式特征选择的评价标准从数据集本身的内部特性获得，与学习算法无关，通常选择与类别相关度大的特征或特征子集；封装式特征选择方法是利用分类算法的性能来评价特征子集的优劣，采用搜索策略来寻找最优子集。过滤式特征选择方法由于特征选择的标准与学习算法无关，不需要分类器的训练步骤，因此其通用性比封装式特征选择方法强，复杂度比封装式特征选择方法低，但是过滤式特征子集在分类准确率方面比封装式特征选择方法低。

优化技术，像进化算法(Evolutionary Algorithm, EA)、遗传算法(Genetic Algorithm, GA)、粒子群优化(Particle Swarm Optimization, PSO)算法、蚁群优化(Ant Colony Optimization, ACO)算法、人工蜂群(Artificial Bee Colony, ABC)算法和差分进化 (Differential Evolution, DE)算法等，有很多已经成功应用到各种应用领域的特征选择问题[6-12]中。

大多数特征选择问题都是针对单目标来解决的，仅考虑了算法的分类准确率，没有考虑选择特征子集的大小。虽然在一些单目标特征选择研究[13-16]中，通过聚合函数形成一个目标，达到同时考虑分类性能和选择的特征子集大小的目的，但是这样引入了新的聚合参数，导致算法不灵活、设置参数等问题，因此，本文将特征选择作为多目标优化问题。特征选择有两个主要目标，即最大化分类准确率(最小化分类错误率)和最小化特征选择的个数，由此，特征选择问题可以表示为两个目标的最小化问题。一般来说，这两个目标函数是相互矛盾的，需要在它们之间进行折中来寻找最优策略。Xue等[17]首次将改进的多目标PSO算法应用到特征选择中，提出了一种基于PSO算法的帕累托(Pareto)前沿面特征选择方法，并通过拥挤距离、变异操作以及支配集寻找Pareto前沿面。实验结果表明，该方法分类性能优于其他特征选择方法。Xue等的算法中将融合多种策略的多目标PSO算法应用到特征选择中，提高了算法的性能，但其存在着大量需要调节的参数，导致收敛速度过慢、计算时间长的问题，使算法的性能下降。

为了达到选择的特征子集个数最小，且算法的分类错误率最小的目的，本文设计了一种基于多目标骨架粒子群(Multi-Objective Bare-bones Partivle Swarm Optimization, MOBPSO)算法用于特征选择方法中，并通过约束机制和变异算子来提高BPSO算法的搜索能力，在算法的执行过程中，通过外部集合记录与维护Pareto最优解，并通过K最近邻(KNearest Neighbor,KNN)(K=3)方法来评估粒子的适应度值。

1 骨架粒子群算法

2003年Kennedy[18]提出了一种变异的骨架粒子群(Bare-bones Particle Swarm Optimization,BPSO)算法，它移除了速度更新公式，在搜索过程中仅使用粒子的位置信息。BPSO更新位置信息时，所有的粒子都从粒子个体历史最优值和全局最优值进行学习。BPSO位置信息更新公式如式(1)所示：

(1)

其中，位置信息根据高斯分布随机产生，高斯分布的均值为(Pbest+Gbest)/2，方差为|Pbest-Gbest|。Kennedy还提出了一种BPSO的变异版本BPSOE(Exploiting Bare-bones PSO), 这种方法更倾向于搜索到历史最优位置。位置信息更新公式如式(2)所示:

(2)

其中R是[0,1]区间的随机数。在BPSOE中粒子有50%的机会跳到自己的最优位置。

由于BPSO算法无需调解参数，比PSO算法更简单，而且目前还没有将多目标BPSO算法应用到特征选择问题中，因此，本文提出将多目标BPSO算法应用到特征选择方法中。

2 基于多目标骨架粒子群的特征选择算法

本文提出了一种基于多目标骨架粒子群算法特征选择算法，该算法结合KNN(K=3)分类器在12个数据集上进行测试。

2.1 种群的编码、解码与评价

种群中每个粒子对应特征选择的一个解，粒子采用实数编码，如式(3)所示，每个解X中包含n个实数，n为对应数据集特征的总特征数，其中每一维xi代表是否选择该特征。

X=[x1,x2,…,xn]

(3)

为了形成特征子集，需要在解码前进行解码处理。粒子的位置可以转换成如下的特征子集：

其中，Ad代表从每个解第d维解码出来的特征子集。Ad可以根据粒子第d维特征的值xd选择其值为0或者是1: 如果Ad=1，代表第d维特征被选择；否则，该维特征不被选择。

将每个粒子解码转换为数据集中所有特征的选择方案，然后采用KNN(K=3)分类器对每个粒子对应的选择方案的分类性能进行测试，并按照式(4)计算该种选择方案对应的分类错误率：

(4)

其中:TP表示正样例被分类正确的个数，TN表示负样例被分类正确的个数，FP表示正样例被分类错误的个数，FN表示负样例被分类错误的个数。ER越小，表示当前特征子集的选择方案对应的错误率越小。将分类错误率结合每个粒子的选择的特征数作为衡量每个粒子适应度值的两个指标。

2.2 更新外部存档

外部存档的作用是保存搜索过程中发现的所有Pareto最优解。在每次迭代过程中，都会产生非支配解，这些新产生的非支配解将会与外部存档中的解进行比较：如果外部存档是空的，当前所有的非支配解都会加入到外部存档中；如果外部存档中存在一个个体，能够支配当前新产生的非支配解，则将会丢弃这个新产生的非支配解，否则，将当前新产生的非支配解存储到外部存档中；如果外部存档中存在一个个体，由新产生的非支配解支配，则将该个体从外部存档中删除；如果外部存档中的个体数量超过最大允许的容量，则调用自适应网格搜索，根据粒子的密度信息选择外部存档中的个体。粒子所在网格中包含的粒子数越多，则粒子的密度值越大; 反之越小。为了保证解的多样性，粒子的密度值越小，选择当前粒子的概率就越大；反之概率越小。

2.3 更新Pbest和Gbest

个体最优位置Pbest保存的是到目前为止粒子本身在搜索空间中找到的最优解。本文采用基于支配的策略更新每个粒子Pbest的位置信息：如果一个粒子在迭代过程中的解受历史保存的粒子最优解支配，则保存Pbest的位置信息不变；否则，将Pbest的位置信息修改为当前的解。

全局最优位置Gbest保存的是到目前为止种群在搜索空间中找到的最优位置。在单目标问题中，种群只有一个Gbest；而对于多目标问题，由于各个目标之间是相互矛盾的，Gbest有很多个，但是每个粒子只能选择一个作为Gbest，然后对粒子的位置信息进行更新。为了解决这个问题，本文应用自适应网格法，根据粒子的密度信息从外部存档中随机选择一个作为Gbest，粒子的密度值越小，选择该粒子作为Gbest的概率就越大。

2.4 变异操作

本文采用的变异率计算公式如式(5)所示:

(5)

其中:it为当前的迭代次数，MaxIt为最大迭代次数，mu为给定的[0,1]区间的值。

在执行变异操作时，随机产生一个[0,1]的数，如果小于变异率，则进行变异操作；否则，不进行变异操作。在粒子进行变异时，会根据新产生的粒子与当前粒子的支配关系进行选择：若新产生的粒子受当前粒子支配时，则粒子不变；若当前粒子受新产生的粒子支配时，则修改为新产生的粒子；若两个粒子互相非支配，则随机选择一个粒子。

2.5 MOBPSO算法描述

输入 粒子群大小N，最大迭代次数MaxIt；

输出 非支配的外部存档解集Archive。

1)

t←0，初始化粒子群S0和外部存档Archive；

2)

fori←1 toNdo

3)

初始化S0中粒子pi的位置；

4)

end

5)

评价粒子群S0，计算每个粒子的目标值，分类错误率和选择的特征个数；

6)

计算非支配解，并对外部存档进行更新；

7)

whilet

8)

fori←1 toNdo

9)

更新粒子的历史最优位置Pbest；

10)

更新全局最优位置Gbest；

11)

根据式(1)更新粒子的位置；

12)

end

13)

对每个粒子执行变异操作；

14)

评价粒子群St+1；

15)

计算非支配解，更新外部存档Archive；

16)

t←t+1；

17)

end

18)

输出外部存档Archive中的非支配解。

3 性能仿真和分析

3.1 数据集以及实验参数设置

本文采用的数据集均来自于UCI数据集[19]以及基因表达数据集[20]，包括zoo、wine、musk1、Ionosphere、lungcancer、parkinsons、dermatology、Alizadeh、wdbc、Hillvalley、Prostate以及9_Tumors数据集，这些数据集类别数包括两类或多类，特征数从13到10 509，样本数从32到1 212。这12个数据集具有一定的代表性，不仅能反映算法在特征数较少或较多情况下去除冗余特征的能力，还能够检测算法在样本数不足以及样本数非常大的情况下的优化性能，具体信息如表1所示。实验仿真在主频为3.40 GHz，内存为8.0 GB的PC机上实现，软件环境为 Matlab R2016a。为了验证算法的性能，将本文算法与两种经典的多目标特征选择方法在上述数据集上进行对比，分别是由Coello等[21]在2004年提出来的多目标粒子群优化(Multi-Objective Particle Swarm Optimization, MOPSO)算法和Deb等[22]在2002年提出的快速非支配排序遗传算法(Non-dominated Sort Genetic Algorithm Ⅱ, NSGAⅡ)。算法的实验参数设置如下，种群大小N设置为20，外部存档的最大容量nrep设置为20，最大的迭代次数MaxIt设置为30。MOPSO算法中，粒子的最大速度vmax为1.0，惯性权重w为0.5，加速因子c1为2，c2为1。NSGAⅡ中，变异概率mrate为1/n,n为种群个数，交叉概率crate设置为0.9。由于采用封装式的特征选择方法，在训练过程中需要一个学习算法来评价分类性能，本文采用最简单的KNN(K=3)算法当作学习算法。

表1 数据集描述

本文实验中，设置的训练集为整个数据集的70%，测试集为30%，在训练过程中，根据粒子的位置，确定选择特征子集的个数，通过KNN(K=3)分类器并采用十折交叉验证，计算特征子集的错误率，将得到的特征子集的个数和错误率作为粒子的适应度函数值；在测试过程中，对选出的每个特征子集进行测试，并将测试结果作为算法的最终结果。

3.2 实验结果分析

实验中，分别将MOBPSO算法与MOPSO算法以及NSGAⅡ在12个数据集上进行测试。MOBPSO算法与MOPSO算法以及NSGAⅡ三种多目标特征选择方法运行结果如图1所示。为了比较算法的计算时间，这三个算法分别运行了10次，计算了每一个算法的平均运行时间，比较结果如表2所示。

表2 三种算法在12个数据集上运行时间比较 s

在Ionosphere数据集上，样本数为351，本文算法与NSGAⅡ都能够找到最小的特征个数，但是应用MOBPSO算法得到的分类错误率比NSGAⅡ得到的分类错误率小。在得到的所有解中，应用MOBPSO算法特征数为10时可以得到最小的错误率，比整个数据集特征的个数少24个，去除了较多的冗余特征，并且在特征数为8、9、10、和11时，MOBPSO算法得到的分类错误率比MOPSO算法和NSGAⅡ低。在Hillvalley数据集上，数据集有足够的样本，为1 212，在该数据集上，本文算法在特征数为24时，可以找到最小分类错误率；在parkinsons数据集上，本文算法不能找到使分类错误率比其他两种算法小的特征子集；在wdbc数据集上，MOBPSO可以获得最小的分类错误率，需要的特征子集大小为16，其他两个比较的算法的分类错误率较高；在Prostate数据集上，特征数最多，为10 509，MOBPSO可以获得最小的分类错误率，需要的特征子集大小为1 079，其他两个比较的算法的分类错误率较高。

图1 MOBPSO与对比算法在12个数据集上的对比结果

在wine数据集上，该数据集的特征数较少，仅为13个，虽然NSGAⅡ在特征数为5时，得到的最小分类错误率与本文算法的最小分类错误率相等，但是本文算法选择的特征数为4，且选择特征数的分类错误率均低于MOPSO算法，但是，特征数为5以及更多时，分类错误率比NSGAⅡ的分类错误率高；在musk1数据集上，该数据集特征数为166，特征数较多，本文算法能够找到最小的特征子集，但是分类错误率较高，三个算法均能够找到使错误率最小的特征子集，应用本文算法仅需要32个特征，而另两个算法分别需要51和56个，说明本文算法去除冗余特征能力比另外两种算法强，但是，本文算法在其他特征子集上的分类错误率较高。因此，本文算法还需要进一步改进。

在多分类数据集zoo上，本文算法在特征数为8时，达到最小错误率，且在特征数为1、2、3和4时，得到的分类错误率均小于其他两种算法；在lungcancer 数据集上，本文算法不能找到使分类错误率比其他两种算法小的特征子集；在dermatology 数据集上，本文算法在特征数为8时，可以得到最小分类错误率，与其他两种算法相比，在特征数为17和20时得到相同的最小错误率时，本文算法使用的特征数更少；在9_Tumors数据集上，该数据集由9类，特征数为5 726，MOBPSO可以获得最小的分类错误率，需要的特征子集大小为1 046，其他两个比较的算法的分类错误率较高； 在Alizadeh数据集上，MOBPSO算法在7个特征子集上，获得了最小的分类错误率，相比其他两个算法，该算法有明显的优势。

对上述12个数据集分析可知，本文算法在部分数据集上去除冗余特征的能力比其他两种算法强，但是，还存在一些数据集，本文算法不能够达到很好的分类效果，还需要进一步的改进。表3对应三个算法在12个测试集上的最小错误率，其中加粗的代表在每个数据集上三种算法得到的最小错误率。由表3可知，本文算法在7个数据集上可以找到分类最小错误率，在其余数据集上虽然得到的不是三个算法中的最小错误率，但是与另外一种算法得到的最小错误率相等。从运行时间上来分析，MOBPSO在8个数据集上，计算时间最少，占比67%。因此，本文算法在去除冗余特征，得到最小特征子集，提高分类效果和降低计算时间上，具有显著优势。

表3 三种算法最小错误率比较 %

4 结语

针对单目标解决特征选择问题中存在的缺陷，本文把特征选择问题作为一个多目标优化问题，即选择分类错误率和特征子集大小作为两个目标。针对粒子群算法中调参问题，多目标骨架粒子群算法是一个少参数的算法，并且该算法还没有应用到特征选择中,针对这些问题，本文提出基于多目标骨架粒子群的特征选择算法。在12个UCI数据集上得到的结果显示，本文算法在大多数数据集上可以去除大部分冗余特征，提高算法分类效果和降低计算成本，但是，仍然存在一些数据集，不能够取得最小分类错误率，仍需要进一步作改进。