基于樽海鞘群与粒子群混合优化算法的特征选择

吴晓燕，刘笃晋

(四川文理学院 智能制造学院，四川 达州 635000)

0 引 言

特征选择(feature selection，FS)是一种机器学习过程，常用于解决数据集的高维问题。此过程允许提取高容量数据池中最具代表性的信息，从而减少其他分类任务中的计算工作量[1]。特征选择具有减少特征数量、降低学习任务的难度、提高预测模型的泛化能力和计算效率、增强对快速生成数据基础过程的理解等优势，因此已经成为机器学习和数据挖掘领域的研究热点，在互联网文档处理、医学应用、计算机视觉等众多领域应用广泛[2-3]。

一般来说，由于搜索空间极大，特征选择是一项困难的任务。对于具有m个特征的数据集，可能的解决方案数量为2m个。随着数据收集技术进步和数据集高维问题日趋复杂化，m数量还在持续增加，特征选择任务变得越来越艰巨。近年来，研究人员提出了大量的特征选择方法用于解决该问题[4]。Mafarja等[5]提出了一种基于鲸鱼优化算法的包装器特征选择方法，利用鲸鱼优化算法的二进制变体来搜索最佳特征子集以进行分类。Hancer等[6]提出了一种基于多目标人工蜂群算法的特征选择方法，通过采用结合非支配排序和遗传算子策略解决数据不平衡和维数灾难问题。但是，大多数基于单一元启发式技术的特征选择方法存在收敛速度慢和容易陷入局部最优的问题。为了解决上述问题，研究者采取了多个智能优化算法混合的方式。Rao等[7]针对特征选择的效率和信息质量等问题，提出了一种基于蜂群和梯度增强决策树的特征选择方法。该方法利用蜂群算法识别信息特征，实现决策树输入的全局优化。Sayed等[8]提出了一种基于混沌乌鸦搜索算法(chaotic crow search algorithm，CCSA)进行特征选择的方法。该方法将混沌映射引入乌鸦搜索优化算法中，解决了乌鸦算法收敛速度慢和陷入局部最优的缺点。Al-Tashi等[9]提出了一种混合灰狼优化和粒子群优化(hybrid grey wolf optimization with particle swarm optimization，GWOPSO)的二值化方法来解决特征选择问题。尽管现有的基于混合优化算法的特征选择方法具有很强的性能优势，但是也存在计算成本高和效率低等问题。

针对现有特征选择方法中存在的缺点，提出了一种基于樽海鞘群算法(salp swarm algorithm，SSA)与粒子群优化(particle swarm optimization，PSO)的混合优化(hybrid optimization of salp swarm algorithm and particle swarm optimization, HOSSPSO)特征选择方法，该方法提高了SSA的收敛速度以及探索和开发步骤的效率，增加了解空间更多的灵活性和多样性，能够迅速达到最优值。

1 背景知识

1.1 樽海鞘群优化

樽海鞘是生活在深海中的一种浮游生物，该生物的群居方式采取链聚集，即樽海鞘链，樽海鞘链有助于樽海鞘通过快速和谐的变化觅食并做出更好的运动。Mirjalili等[10]在2017年以数学形式对樽海鞘链进行建模用于解决多种优化问题。

在樽海鞘群算法模型中，将樽海鞘链中的种群分为两组：位于链首端的个体定义为领导者，其余位置处的个体为追随者。领导者对环境拥有最优的判断，位于后面的个体会直接受到前一个个体的影响。樽海鞘的位置在n维搜索空间中确定，n表示问题的变量。樽海鞘群以搜寻食物来源位置为种群运动的目标，因此，樽海鞘链中的个体位置会经常更新。据此，SSA采用(1)式更新领导者位置

(1)

c1=2e-(4t/tmax)2

(2)

(2)式中，t和tmax分别表示当前迭代次数和最大迭代次数。更新领导者的位置后，SSA使用(3)式更新追随者的位置

(3)

SSA具有结构简单、控制参数少、搜索能力强、容易实现的优点，其具体步骤如下。

算法1：樽海鞘群算法(SSA)

1:初始化种群X

2:while(t

3:对于每个解xi计算目标函数

4:更新最优解(F=Xb)

5:利用(2)式更新c1

6:fori=1:Ndo

7:ifi==1 then

8:利用(1)式更新领导者的位置

9:else

10:利用(3)式更新追随者的位置

11:end if

12:end for

13:返回最优解F

1.2 粒子群优化

粒子群优化(particle swarm optimization，PSO)[11-13]是由Eberhart和Kennedy在1995年提出的优化算法，该算法源于对鸟群捕食的行为研究，其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。由于PSO具有容易实现及不需太多参数调节的优势，使其在函数优化、神经网络训练以及其他启发式算法领域中得到广泛的应用。

(4)

(5)

算法2：粒子群优化(PSO)

1:初始化种群X，种群数量为N

2:while(t

3: fori=1:Ndo

4:计算目标函数值

6: end if

8:利用(5)式更新粒子速度

9:利用(4)式更新粒子位置

10:end for

11:返回最优解

2 基于HOSSPSO的混合优化算法

为了提高特征选择方法中混合优化算法的效率，本文提出HOSSPSO混合优化算法，将SSA和PSO结合在一起，把PSO的更新机制合并到SSA的主结构中，通过改进种群位置的更新阶段，来修正SSA的基本结构。该方法为SSA在探索种群中增加了灵活性，在确保其多样性的同时，可以迅速达到最优值。图1给出了HOSSPSO的实现步骤。

图1 HOSSPSO的实现步骤图

第一步，该算法初始化参数，生成表示特征选择问题一组解的种群，即在D维解空间中生成N个随机种群X，根据SSA，计算每个解xi(i=1,2,…N)的食物适合度。在计算目标函数之前，根据(6)式，将每个解xi转换成仅包含0和1的二进制向量

(6)

因此，只有对应于1的xi元素被取出来表示所选择的特征，其他元素因为表示不相关的特征而被忽略。

第二步，根据(7)式计算每个解的适合度函数，通过评价解的性能来确定最佳解

(7)

第三步，通过使用SSA或PSO来更新当前种群xi，更新方式的选择取决于适合度函数的质量。如果当前解的适合度函数的概率大于0.5，则采取SSA更新，否则使用PSO。每个适应度函数的概率可以定义为

(8)

为每个更新的解计算适应度函数，并更新最佳解。上述步骤持续迭代，当循环满足停止条件时，返回全局最优解。

3 实验与结果分析

为了验证所提算法HOSSPSO的可行性以及性能，采用2个实验进行测试：实验1使用6个著名的基准函数[14]，并将结果与标准SSA、PSO进行比较；实验2使用特征选择问题中的10个通用数据集[15]对算法进行测试，并且将测试结果与CCSA[8]、GWOPSO[9]和基于反向策略的社会蜘蛛优化(opposition-based social spider optimization，OBSSO)[16]等进行比较。所有实验在一台配置为Intel(R)Core(TM)i7-7820X CPU @3.60GHz和8GB RAM的机器上进行，且均在Matlab2018a环境下实现。

3.1 实验设置及数据集

为了简化计算量，2次实验中均设定种群数量为30。此外，实验1中的参数分别设定为：迭代次数200，迭代阈值10e-5，其他参数如表1。本文选择了6个典型的Benchmark函数作为测试算法的实验函数，表2给出了这些函数的名称、公式和范围，所有函数的维度为D=10，最小目标值为0。

表1 SSA和PSO的初始参数

表2 基准优化函数集

实验2中的参数分别设定为：迭代次数100，下限lb=0，上限ub=1。此外，每个数据集分为训练组和测试组两部分，每次运行中使用5倍交叉验证，以确保每次运行样本的多样性。为了评估算法的准确性，使用了K最近邻分类器。本文采用UCI数据集(加州大学欧文分校提出的用于机器学习的数据库)中的10个数据子集进行测试，表3给出了10个数据集的描述，包括样本的数量、特征和类别。

表3 常用数据集的相关信息

3.2 实验结果分析

3.2.1 基准函数测试

实验1采用最大值(Max)、最小值(Min)、平均值(μF)和标准差(STD)等4个性能指标进行评估，这些指标的定义为

(9)

(10)

(11)

(12)

实验比较了提出的算法与标准SSA算法在6个基准函数上的计算结果。表4—表7给出了这些函数在最大值、最小值、平均值和标准差4个评估指标方面的测试结果，表中列出了每个函数运行30次后计算性能指标的平均值。从表4—表7可以看出，HOSSPSO比标准SSA和PSO具有更好的性能。具体来说，HOSSPSO在6个基准函数上测试的最大值、最小值、均值和标准差均为最低。结果表明，HOSSPSO具有很好的平衡探索和开发阶段的能力，并且提高了标准SSA，PSO的精度。

表4 使用6个基准函数的最大值测试结果

表5 使用6个基准函数的最小值测试结果

表6 使用6个基准函数的平均值结果

表7 使用6个基准函数的标准差结果

3.2.2 特征选择测试

为了进一步验证HOSSPSO在特征选择方面的性能，采取UCI数据集对算法进行测试，其中UCI数据集包含10个数据子集。本次实验采用均方根误差(RMSE)、选择率(SelR)、精确度(P)以及F-度量值(F)等4个性能指标进行评估。这些指标的定义如下

(13)

(13)式中：P表示算法中估计的适合度值；T表示初始适合度值；Ns表示数据集中的样本数量。

(14)

(15)

(16)

(15)—(16)式中：TP表示正类样本被预测为正类；FP表示负类样本被预测为正类；FN表示正类样本被预测为负类。

图2，图3分别给出了HOSSPSO与其他算法在RMSE和选择率指标的比较结果。从图2，图3中可以得出结论，HOSSPSO在所有数据集中获得最低的RMSE和选择率，即HOSSPSO对所有数据集中的特征都做出了最好的简化。

图2 常用数据集中特征选择的根均方误差对比

图3 常用数据集中特征选择的选择率对比

为了进一步研究HOSSPSO的性能，将选择的特征传递给KNN分类器，以检查这些特征是否能够提高分类精度。图4，图5分别给出了各算法在精确度和F-度量值指标方面的比较结果。从图4，图5中可以看出，所有数据集中，HOSSPSO的精确度和F-度量值均达到最高性能。

图4 分类器在数据集上评估选定特征的精确度对比

图5 分类器在数据集上评估选定特征的F-度量值对比

4 结 语

本文提出了一种基于樽海鞘群算法与粒子群优化的混合优化特征选择方法HOSSPSO，用于解决现有特征选择方法中存在的计算效率低、收敛速度慢以及容易陷入局部优化等问题。该算法利用PSO策略的特点，改进了SSA的搜索质量，从而提高了收敛速度以及探索和开发步骤的效率，使得算法能够迅速获得全局最优值。实验结果表明，提出的算法比其他优化算法具有更好的效果，能够以极少量的特征来表征整个数据集，而且能够获得最大的分类精度。