一种求解数据特征选择问题的改进樽海鞘群算法

2022-06-17王立威童林邹圆

六盘水师范学院学报 2022年2期

王立威童林*邹圆

（1六盘水师范学院物理与电气工程学院，贵州六盘水 553004；2重庆工商大学经济学院，重庆南岸 400067）

近年来，数据分类已经成为机器学习领域最重要的研究问题之一，随着研究人员对数据分类任务的精细化要求不断提高，在机器学习和数据挖掘领域产生了海量的具有不同特征种类的分类数据集，这些高维数据通常包含大量冗余的特征。特征选择是在去除不相关、冗余、有噪声特征的同时，从原始特征中提取重要特征，实现降维的过程。数据特征选择问题被认为是组合优化问题[1]，与解决组合优化问题方法类似，研究人员通过引入各种启发式算法用来寻找数据特征选择问题可接受的解，包括粒子群优化算法（Particle swarm algorithm，PSO）[2]、遗传优化算法（Genetic algorithm，GA）[3]、灰狼优化算法[4]、蜻蜓优化算法[5]、烟花优化算法[6]等，但无论以何种策略建立优化算法，仍存在着搜索精度低及易早熟收敛等共性问题[7]，该类问题极大地影响了优化算法在数据特征选择上的效果和分类精度。樽海鞘群算法（Salp swarm algorithm,SSA）[8]自2017年被提出以来，该算法就以其参数少、结构简单和易实现的优点，被得到广泛应用，如多目标电力负荷分配问题[9]、离散域中的任务分配问题[10]等，但SSA依然存在着陷入局部最优和精度低的问题。在SSA改进研究中，文献[11]提出一种多子群共生非均匀高斯变异的SSA算法，算法寻优效果得到改进，但研究者并未将其用于解决数据特征选择或其他实际工程问题。文献[12]通过在SSA算法中引入正弦余弦因子和干扰算子并用来解决特征选择问题，文献[13]将动态时变策略和优胜劣汰解决方案集成在SSA算法中应用在机器学习中数据集的特征选择中，文献[14]提出了基于混沌映射的SSA算法。虽然上述改进策略提高了SSA算法的优化性能，但仍存在一些问题，包括算法更新方式单一、搜索位置有限、求解高维优化问题性能较差等问题。

针对上述问题，本文通过在SSA算法中引入量子计算，使得SSA算法量子化，有机结合Cauchy变异操作，得到具有量子行为的改进樽海鞘群算法（Quantum Salp swarm algorithm，QSSA），改进后的算法增加了更新方式，扩大了搜索位置，具有量子计算和SSA算法的高性能和高精度优势，增强了算法的高维问题寻优能力。最后，将QSSA算法应用近邻（K-Nearest Neighbor，KNN）分类器进行数据分类，构造基于QSSA的特征选择算法，与其他算法进行对比进一步验证该算法的有效性。

1 问题描述和求解框架

数据特征选择问题要求实现所选特征数量最少、分类精度最高，能够满足这两个条件的数据子集为数据选择的最佳解决方案，在实际过程中，其二者相互矛盾，为取得二者间的平衡，文献[14]定义适应度函数为

式中，NF为选择出的特征子集的大小，acc是输入为NF子集情况下的分类精度，NT是全部特征的数量，是平衡控制分类精度和特征选择数量的常数。通过求解式（1）所示的函数极小值问题可以实现在所选特征子集NF数量最少的情况下实现分类精度acc最高，当数据特征维度较高时，特征子集NF选择难度较大。

为了求解上述非线性、多约束的高维数据特征选取难题，提出了基于QSSA的特征选择算法，具体求解框架如图1所示。

图1 基于QSSA的特征选择算法框架

由图1可知，框架使用QSSA算法进行特征选择包含两个主要模块：特征选择模块和分类模块。首先，以原始数据集的全部特征为输入，然后使用QSSA算法确定有价值的特征，考虑到KNN分类器简单易于实现，仅对样本之间的距离进行分类，将产生的特征用于输入KNN分类器，根据适应度函数平衡特征数量和分类精度，最后评估结果。

2 求解算法

2.1 标准樽海鞘群算法

樽海鞘群中领导者觅食行为的数学模型可由公式（2）表示

2.2 动态对立学习

SSA算法在首次迭代之前，需要选取一组随机的值用来初始化种群个体，由于可行解范围较大，存在初始化位置选择盲目的问题。改善初始种群的位置可以增加算法收敛速度，基于对立的学习(Opposition-based Learning，OBL)已被广泛用于各种智能算法初始学习阶段，增强算法的搜索能力[15]，其核心思想是通过计算当前值及其对应的对立值来寻求更好的候选解决方案[16]。对立学习具体定义为

将对立学习进一步拓展到高维，公式如（6）所示

式中，ubj和lbj为j维可行解的上下界。为了进一步增强OBL策略，在对立学习的基础上添加随机因子改进为动态对立学习（Dynamic Opposition-based Learning，DOBL），然后将动态对立学习引入到算法的种群初始化中，大大增加种群的多样性，动态对立学习定义如下

2.3 量子樽海鞘群算法

通过量子位置的不断更新，实现了QSSA算法中的整个量子樽海鞘群的演进。

搜索过程中，第i只量子樽海鞘搜索到的最好位置(即局部最优位置)表示为Pi=(Pi1,Pi2,…,pij)(i=1,2,…,h)，整个量子樽海鞘群所搜索到的全局最优位置（所有局部最优位置中的最优位置）表示为Pg=(Pg1,Pg2,…,pgl)。在每次循环中，第i只量子樽海鞘的第j维量子位的量子演进表示如下

式中，i=1,2,…,h;j=1,2,…,D,e1和e2是2个影响因子，分别决定局部最优位置和全局最优位置对量子旋转角的影响程度，t为迭代次数。通过以上操作得到了量子樽海鞘群算法。

2.4 Cauchy变异

考虑到跟随者群体会陷入局部最优影响算法精度，在算法搜索后半段，引入Cauchy算子作为变异步长，具体公式如下

式中各项具体含义见式（4），需要说明的是Cauchy是Cauchy算子，其标准分布概率密度函数公式如下

相比高斯分布，Cauchy分布具有较长的“尾巴”，可使跟随者群体具有更高概率跳到更优位置，同时，中心点较小的峰值表明Cauchy算子搜索领域空间的时间花费更少[18]。通过在SSA算法加入变异策略能降低算法陷入局部最优的概率。

2.5 QSSA算法步骤

本文的改进算法是在SSA的基础上，增加了动态对立学习，增强算法的搜索能力，提升算法收敛速度；引入Cauchy算子，解决SSA算法中跟随者群体会陷入局部最优的问题；采用量子遗传算法进一步寻优，使算法寻优值更能接近最优值。QSSA伪代码如算法1所示。

计算樽海鞘对立位置和适应度值。//根据文章中的公式（7）

计算樽海鞘量子位置和计算当前适应度值。//并根据文章公式（9）（10）

2.6 算法复杂度分析和数值试验

2.6.1算法复杂度分析

本文所提的QSSA主要是由对立学习种群初始化、Cauchy变异和量子优化组成。迭代次数为T，当种群数目为N，优化问题的维度为D，二进制位数为M的时候，对立学习种群初始化的计算复杂度为O(ND)；在柯西变异环节，计算复杂度为O(ND)；在量子优化环节，计算复杂度为O(NDM)。对改进的樽海鞘群算法，每一次迭代过程中，算法的计算复杂度为O(2ND+NDM)，因此，算法总计算复杂度为T(n)=O(T(2ND+NDM))

2.6.2 数值试验

为了验证QSSA有效性，选取文献[11]提出的MSNSSA与其它几种常见算法模型如粒子群算法（PSO）[19]，正余弦算法（SCA）[20]、蝴蝶优化算法（BOA）[21]和飞蛾火焰算法（MFO）[22]进行实验对比，为遵循实验公平性，实验对比过程中，列出的测试函数中种群数量、函数维度、迭代次数、独立运行次数等基本实验参数和对比算法中的各项参数均与文献[11]保持一致。针对常见的10个测试函数最优问题，不同算法的寻优结果如表1所示。

表1 算法性能对比

由表1的结果可知，除Quartic函数，QSSA算法在求解函数最优问题时表现出的效果最好。在Quartic测试函数的最优值为6.9674e-4，QSSA与BOA、MSNSSA求解精度差距较小，在其余函数上，QSSA表现出了更高的精度，相比于SSA算法，求解精度提升较大，特别是在Sphere、Schwefel 1.2和Schwefel 2.21函数上，其收敛精度远超于其他算法，具备更优秀的收敛能力。由于多峰函数求解相对困难，所列算法求解精度均相对较低，QSSA算法依然展现出了良好的搜索能力，与MSNSSA和相差较小，说明对立学习和柯西变异操作有利于SSA算法跳出局部最优值，并采用量子遗传作精细调整，找到全局最优值。综上，QSSA算法能够较好地求解函数优化问题，与其他算法相比，具备较好的综合求解能力。

2.7 基于QSSA的特征选择算法步骤

将QSSA算法应用KNN分类器进行数据分类，构造基于QSSA的特征选择算法，步骤如下：

步骤1：设定数据集中的特征向量分别对应QSSA算法种群，加载数据集并随机初始化量子樽海鞘种群；

步骤2：计算QSSA算法种群适应度，初始的最佳适应度函数fitness设置为食物源位置(foodfitness)；

步骤3：利用算法1中的主函数对SSA个体进行更新，并结合KNN分类器和式（1）计算fitness；

步骤4：按如下方法更新fitness；

步骤5：重复第三步和第四步，直到满足迭代次数要求；

步骤6：返回量子樽海鞘种群最佳位置；并将包含全部特征NT中的识别特征子集NF作为选择特征子集再次送入KNN分类器进行模型综合评估。

3 实验对比

3.1 实验参数设置

为了验证算法的有效性，采用加州大学欧文分校（University of CaliforniaIrvine，UCI）机器学习数据库中经典的数据集对模型进行评估。数据集编号（data set ID，DS ID）及其简要说明，所选数据集拥有从6扩展到90的各种特征如表2所示。

表2 UCI机器学习数据集

数据集的类别（从2到15）和实例（从47到5 000）的数量也各不相同。

实验中文献[14]所提算法、PSO和GA对比数据引自文献[14]，为遵循实验公平性，各项设置参数保持一致如表3所示。

表3 实验参数设置

3.2 算法性能对比与分析

该实验的基本目标是评估具有算法的性能。为了将QSSA、文献[14]所提改进的SSA算法、标准SSA算法和遗传算法（Genetic algorithm，GA）及粒子群算法（Particle swarm algorithm，PSO）进行全面比较，分别给出了最佳及平均适应度值，最优值均以粗体显示，如表4、表5所示。

表4 20次运行的中最佳适应度

表5 20次运行的平均适应度

通过表4和表5可以看到，经过20次程序运行后，在大多数情况下，具有QSSA的性能优于标准SSA和其他算法。其中，QSSA算法在7个数据集(D1、D3、D5、D6、D7、D8、D9)表现出最佳适应度，在6个数据集(D1、D3、D5、D6、D7、D8)中平均适应度最佳，效果优于文献[14]提出的算法，文献[14]所提算法分别从三个数据集中取得最佳适应度和最优平均适应度，效果优于其他三种算法。最佳适应度反应算法能够达到的最佳精度，而平均适应度反应算法的稳定性，与其他算法相比，QSSA算法在适应度寻优上具有优势，但适应度仅综合反映了特征选择求解情况，无法具体表现出分类正确率和特征选择数量，因此，还需要对准确率和寻找的特征子集数量进行对比。程序运行20次后的分类正确率和特征选择子集数量如表6和表7所示。

表6 20次运行的分类正确率（%）

表7 运行20次程序的平均特征选择数

注：粗体表示分类正确率，正确率最高。

首先，通过表6可知，QSSA算法在7个数据集（D1、D4、D5、D6、D7、D8、D9）中获得了最佳分类精度，文献[14]所提算法在三个数据集中获得了最佳分类精度；其次，在表7中看到QSSA和文献[14]所提算法分别在4个数据集中寻找的特征子集数量最少，GA算法在2个数据集中特征子集最少。可知QSSA在一定程度牺牲了特征选择数量换取更高的分类精度，如在D5数据集中，QSSA获取了特征子集数量虽然达到了14.2，大大高于GA算法求得的3.4，分类正确率提高了11.67%，这种能力更加适合对分类精度要求较高的场景。如果更加注重特征数量最少，可以通过调节参数来改变该部分在整体适应度函数中的比重。

综上，QSSA算法分类精度和特征选择能力能够得到有效平衡，具有较好的特征选择能力。