融合Shapley值和粒子群优化算法的混合特征选择算法

2018-07-25邓秀勤李文洲武继刚刘太亨

计算机应用 2018年5期

邓秀勤，李文洲，武继刚，刘太亨

(1．广东工业大学应用数学学院，广州510006; 2．广东工业大学计算机学院，广州510006)(*通信作者电子邮箱xiuqindeng@163．com)

0 引言

特征选择也叫特征子集选择，是指从已有的特征中选择出一些有效特征以降低数据集维度的过程，是提高学习算法性能的一个重要手段，也是模式识别中关键的数据预处理步骤。在分类过程中，数据集往往包含大量的特征，但是并不是所有的特征对于分类都是有用的，其中很多无关和冗余的特征会导致分类效果不佳，同时导致维数的复杂性［1］，特征选择是解决数据冗余和不相关的一种非常有效的方法。

特征选择的任务是从一组N个特征中按一定的选择标准选择出一组由n(n＜N)个特征组成的特征子集，这个子集具有比特征全集更好的或一样的分类功能。这实际是一个组合优化的问题，且已被证明是非确定性多项式(Non-Deterministic Polynomial，NP)完全问题［2］，所以最优特征子集的选择很重要。特征选择算法从模型上可分为Filter(滤波)模型和Wrapper(封装)模型［3］。一般来说Filter模型的效率高，但效果差;Wrapper模型的效率低，但效果好［4］。为了解决这两种模型存在的问题，文献［5］提出了结合Filter模型和Wrapper模型的混合模型，在性能上有一定的提高。Hualonga等［6］提出一种混合特征选择算法，将ReliefF算法与Shapley值结合，通过Shapley值选择贡献最高的相关特征，然后运用遗传算法进行特征子集选择。由 Sasikala等［7］所提出的SVEGA(Shapley Value Embedded Genetic Algorithm)特征选择算法，将遗传算法与Shapley值结合，同时通过增l减r法进行特征子集搜索以降低维度;对于同样的中小型数据，SVEGA与 Hualonga等［6］、Tan 等［8］、Kannan 等［9］所提出的算法都进行了比较，并且算法表现优异。PSO-LSSU(Particle Swarm Optimization with Local Search using Symmetric Uncertainty)算法［10］是一种使用基于对称不确定性的局部搜索方法改进粒子群优化(Particle Swarm Optimization，PSO)的特征选择算法，对于同样的8个高维数据集，它与 PSO-LS(PSO with Random Local Research)、PSO-LSRG(PSO with Random Local Research and Resetting Gbest)算法［11］进行比较并得到了更好的训练结果。

文献［12］经过对医疗数据集特征选择方法的研究，得出大多数现有方法存在以下问题:1)由于搜索方法的复杂性而导致迭代数过大;2)这些方法没有考虑所选的特征子集中的特征之间的相互作用;3)产生最佳分类精度的方法采用的特征子集的特征较多，导致相应的分类器需要更多的运行时间;相反，输出最少数量特征的方法却存在较差的分类精度。因此在实现最佳分类精度的同时尽可能减少特征数量，依然是个难题。文献［13］提出对于医疗数据集，PSO算法与支持向量机(Support Vector Machine，SVM)分类器的组合在分类精度和性能上更优于其他启发式算法与其他分类器的组合。

为了在减少特征数量的同时尽可能地实现最佳分类精度，本文提出一种融合 Shapley值和粒子群优化(Shapley Value and Particle Swarm Optimization，SVPSO)算法的混合特征选择算法，将PSO算法与博弈论的Shapley值结合，通过计算特征的Shapley值，在特征子集的局部搜索中去除冗余和不相关特征得出表现最为优异的特征子集，再运用SVM分类器进行分类以达到在减少特征数的同时提高分类精度的目的。

1 粒子群优化算法

PSO算法是一种全局随机优化算法。在PSO算法中，每个粒子代表一个解，每一次迭代，粒子通过跟踪两个“极值”更新自己:一个是粒子本身所找到的最优解，称为个体极值pbest;另一个极值是整个种群目前找到的最优解，称为全局极值gbest。每个粒子根据如下公式更新自己的速度和位置［14］:

很多学者提出了基于PSO算法的特征选择方法［10－11］，不少方法致力于减少所选择的特征数量，其中包括使用滤波模型以减少特征数量的方法。比如文献［15］运用互信息评估特征之间的相关性和冗余度，从而过滤掉全局极值gbest中的冗余特征，实验结果表明，相比以往的基于改进后的PSO算法的特征选择方法，所提方法在分类问题中表现更加优异，而文献［10］指出对于一些可能存在数千个不相关或冗余特征的数据集而言，文献［15］方法不好确定全局极值gbest中该过滤掉的特征数量，因此本文提出运用Shapley值对PSO算法进行局部搜索的特征选择方法。

2 特征选择中的Shapley值

Shapley值法是一种解决n个人合作对策问题的数学方法，合作中的每个人所得都与自己的贡献相等，是一种分配方式，普遍用于经济活动中的利益合理分配等问题。因此Shapley值法在特征选择中可用于计算特征子集中的每个特征的贡献值［16－17］。

设集合N={1，2，…，n}，如果对于N的任一子集S(对应n个人集合中的任一组合，即SN)都对应着一个实值函数v(S)，v(S)表示子集S中每个人的贡献值的总和。v(S)若满足以下两个条件:

2)两个不相交的子集的并集的实值函数大于等于这两个子集的实值函数的和:

v(Si∪ Sj) ≥ v(Si)+v(Sj)，Si∩ Sj=，Si、SjN，则称［N，v］为多人合作对策，v为对策的特征函数。

Shapley值定义如下:在特征选择中，将特征集合中的特征视为合作对策中的人，特征子集S的特征函数v(S)由子集S对分类器的性能的贡献度来表示，因此，特征i在特征子集S中对分类精度的边际贡献度为:

那么特征i的Shapley值为:

其中:Π是n!个特征子集的集合，Si(π)是Π中所有包含特征i的特征子集。

3 融合Shapley值和粒子群的特征选择

3．1 适应度函数

特征选择是一个典型的组合优化问题，将二进制PSO算法用于特征选择时，每个粒子代表一个特征子集，如果某一特征位被选中，对应的二进制位为1，否则对应位为0。特征选择的目的是以较少的特征数实现更高的分类准确率，因此适应度函数包含着分类准确率和子集大小两项指标。如果一个粒子既能够使分类器获得的分类精度越高，同时又使选择的特征数目越少，那么它的适应度值必定越高。而且，如果两个粒子取得的准确率相同，则特征数目少的粒子适应度值较高。因此定义适应度函数为:

其中，accuracy(xi)是子集xi在SVM分类器上的预测精度，SVM分类过程的一般步骤为划分训练集和测试集、数据预处理(特征选择)、训练SVM(训练集)、预测(测试集);nfeature(xi)代表特征子集的大小，即子集中1的个数;A为控制分类精度和特征数目对适应度函数的影响的因子，取值范围为［0，1］。T为迭代次数，在实验中T=50;t为当前迭代次数。在封装模式中，适应度函数用于评价特征子集的好坏，数据分类的准确率在适应度函数中应该起到主导作用。因此在实验中，随着迭代次数的增加，A将逐渐增大，当迭代数到达10次以后，A的取值固定为0．8。

3．2 基于Shapley值的局部搜索

局部搜索的目的是通过从当前的特征子集中删除一定数量的冗余特征找到更好的特征子集。在每次迭代中，根据式(5)计算粒子的适应值并根据适应值更新粒子的个体极值pbest。在粒子的局部搜索中，根据式(4)计算粒子中对应二进制位为1的每个特征的Shapley值并根据Shapley值对特征进行排序，去掉对分类问题贡献最低的特征，即将该特征的二进制位由1改为0，得到新的粒子，计算其分类精度，若分类精度高于原粒子的分类精度，则用该粒子取代原粒子后继续去掉Shalpey值最低的特征，以此类推，直到得到的新粒子的分类精度低于原粒子的分类精度为止则停止更新。计算最后得到的粒子的适应度值，若其适应值比个体极值pbest的适应度值高则更新pbest。

基于Shapley值的特征子集局部搜索算法流程如下:

步骤1 输入粒子(特征子集)，计算每个特征的Shapley值并排序;

步骤2 逐个去掉粒子中Shapley值最低的特征，并计算其分类精度;

步骤3 直到分类精度不再提高，更新粒子并输出。

所有粒子经过局部搜索后，得到全局极值gbest，根据式(1)、(2)对所有粒子的速度和位置进行更新，然后进入下一次迭代，直到达到最大迭代次数停止循环并输出最后的全局极值 gbest。

3．3 SVPSO算法描述

输入:粒子数M，迭代次数T;

输出:特征子集。

1)初始化:随机生成M个具有m个特征的粒子，每个粒子的每位

上的值为0或1;

2)while达到最大迭代次数时停止循环do

for i=1 to M do

计算每个粒子的适应值f(xi);

if f(xi)＞f(xpbest)then

更新pbest;

end

3)运用Shapley值对粒子xi进行局部搜索得到xi'，并计算其分类

精度acc(xi')

if acc(xi')＞acc(xi)then

更新xi;

end

if f(xi')＞f(xpbest)then

更新pbest;

end

4)更新gbest;

for i=1 to M do

根据式(1)更新粒子i的速度;

根据式(2)更新粒子i的位置;

end

4 仿真实验与结果分析

本文使用了17个具有不同特征数量的数据集来做实验，这些数据集来源于UCI机器学习数据集［18］和基因表达数据集［19］。这些用于测试的生物医学数据集依据特征数量可分为小型数据集(2～30个特征)、中型数据集(31～1 000个特征)和大型数据集(超过1 000个特征)。数据集的相关信息如表1和表2的第1列所示。

表1 中小型数据集中不同算法得到的特征子集规模和分类准确率Tab．1 Feature subset size and classification accuracy obtained by different algorithms in small and medium-sized datasets

为了测试本文提出的SVPSO算法的性能，本文使用10折交叉验证，对上面的每个数据集运行了50次，数据集随机分为训练集和测试集，在保证分类精度的情况下选择特征数最少的特征子集。对于所有数据集，都将先进行没有经过特征选择的分类实验，所得的分类精度将与经过SVPSO算法进行特征选择后的实验的分类精度比较。除此之外，SVPSO算法还都将与传统的PSO算法进行比较，而对于小型和中型数据集，SVPSO算法将与 SVEGA［7］进行比较。对于大型数据集，SVPSO算法将与PSO-LSSSU算法［10］进行比较。具体实验结果分别列于表1和表2(“无”表示数据集没有经过特征选择，直接用于分类实验)。

对于中小型数据集，表1的实验结果表明，将没有经过特征选择的数据集直接进行分类实验所得到的分类准确率普遍偏低，由此可见数据集中存在着大量不相关特征或冗余特征，而经过SVPSO算法进行特征选择后，所选择的特征数量比原数据集减少了55%以上，并且所减少的特征数量也随着原有的特征数量的增加而增加，尤其是中型数据集，所选择的特征数量更是减少了80%以上。根据所选择的特征进行分类实验所得的分类准确率提高了9～23个百分点。而与传统的PSO算法相比，与Shapley值结合后，在所实验的数据集中，SVPSO算法所选择的特征数都比PSO算法的要少，尤其在数据集 Post operative patient、Lung cancer、Cardiac arrhythmia 中，最高能减少78%。在分类精度方面，在大部分的数据集中，SVPSO算法所选择的特征子集的分类精度都要比PSO算法的高2～13个百分点。虽然在少数数据集中，比如Dermatology和Lung cancer，所得到的分类精度没有PSO算法高，但是依然可以在保持分类精度不会太差的情况下大幅降低特征个数。由此表明，运用Shapley值对PSO算法进行局部搜索可以有效消除冗余特征，从而可以发现具有更好辨别力的更小的特征子集。而在与SVEGA的对比中可以发现，除了第一个数据集Liver disorder的实验结果没有SVEGA的好，在其他数据集中所选出的特征子集不仅数量要比SVEGA的少25%～50%，分类精度也会差不多或者更高，最高能增加10个百分点。由此可见，Shapley值与PSO算法的结合在医疗数据集中要比与遗传算法的结合表现更加优异。

对于大型数据集，表2的实验结果表明，在经过SVPSO算法的特征选择后，大部分数据集的特征数量都能减少2个数量级，在数据集Leukemia1和Leukemia2中甚至能减少3个数量级，由此可见在大型数据集中，SVPSO算法是能够有效减少特征数量的。而在减少大量特征的同时，所选特征的分类准确率仍然能够提高2～22个百分点。与传统的PSO算法相比，融合了Shapley值的SVPSO所选择的特征子集的特征数也能比PSO算法所选的特征数低1或2个数量级，在数据集Leukemia1中更是能减少3个数量级，与此同时在分类精度上也能提高1～9个百分点。而与表现同样更加优异的PSO-LSSU算法相比，可以发现SVPSO算法在数据集9Tumor和Prostate中无论是特征数量还是分类精度都能优于PSOLSSU算法;而在数据集SRBCT、Brain Tumor 1和 Leukemia1中，SVPSO算法选择的特征子集也能在保持分类精度和PSOLSSU算法所选子集的分类精度差不多的情况下大幅减少特征子集的特征个数;在其他数据集中，SVPSO算法所选择的特征子集要么就是在特征数量上少于PSO-LSSU算法，要么就是在分类精度上高于PSO-LSSU算法。因此，从整体上来看SVPSO算法的表现比PSO-LSSU算法更优异。

5 结语

为了在减少特征数量的同时尽可能地实现最佳分类精度，本文融合Shapley值与PSO算法，提出一种新的混合特征选择算法，并对17个具有不同特征数量的医疗数据集进行分类实验，通过计算特征子集中每个特征的Shapley值，从而在特征子集的局部搜索中删除掉冗余特征，使得算法所选择的特征子集的特征数量达到最小的同时保持一定的分类精度。仿真实验结果表明，无论是中小型的数据集还是大型的数据集，本文SVPSO算法所选择的特征子集在特征数量和分类精度上都能表现优异，不仅能删除数据集中55%以上不相关的或冗余的特征，尤其对于中大型数据集更能删减80%以上，还能将分类准确率提高2～23个百分点。