改进二进制沙丘猫群优化特征选择算法

Improved Binary Sand Cat Swarm Optimization Feature Selection Algorithm

摘要: 特征选择在机器学习的分类任务中被广泛应用，选择出的特征子集会直接影响后续学习算法的性能。针对沙丘猫群优化算法(SCSO)全局搜索能力弱、收敛速度慢问题，本文提出一种改进的二进制沙丘猫群优化特征选择算法。首先改进控制沙丘猫在搜索阶段和攻击阶段转换参数的调整方法，使用两阶段的改进收敛因子策略代替线性递减策略，以提升算法的全局搜索能力。其次受PSO算法位置更新公式的启发，引入社会学习因子和认知学习因子策略，提高算法的收敛速度。为了验证新提出算法在求解特征选择问题上的性能，本文选择了4种经典算法在8个UCI数据集上进行了对比测试，实验结果表明新提出算法的性能优于对比算法。

Abstract: Feature selection is widely used in classification tasks of machine learning, and the selected feature sets directly affect the performance of subsequent learning algorithms. Aiming at the issues of weak global search ability and slow convergence speed of Sand Cat Swarm Optimization (SCSO), an improved binary sand cat swarm optimization feature selection algorithm is proposed in this paper. Firstly, the adjustment method of controlling the transition parameters of sand cat in the search phase and attack phase is improved.This method employs a two-stage improved convergence factor strategy, replacingthe linear decrement strategy, aiming to enhance the algorithm’s global search capability. Secondly, inspired by the position update formula of the PSO algorithm, social learning factor and cognitive learning factor strategies are introduced to improve the convergence speed of the algorithm. In order to verify the performance of the newly proposed algorithm in solving the feature selection problem, this study conducted comparative tests on eight UCI datasets using four classical algorithms. The experimental results demonstrate that the performance of the newly proposed algorithm outperforms the compared algorithms.

1. 引言

特征选择是一种数据的预处理方式，用于从初始的特征空间中选择出与研究问题相关、有代表性的特征，剔除那些和研究问题无关、冗余的特征 [1] 。选择出来的特征子集具有更低的维度，能够提高分类算法的性能。

依据特征子集的搜索策略是否和后续的学习器相结合，可以将特征选择的方法分为过滤式特征选择、包装式特征选择和嵌入式特征选择 [2] 。过滤式特征选择首先对已知的数据集进行特征选择，然后将选好之后的特征子集用于模型训练，这两个过程是相互独立的 [3] 。过滤式特征选择的核心是选用某种准则对特征子集进行度量，如Zheng K等人 [4] 提出了一种结合最大信息熵(MIE)和最大信息系数(MIC)的过滤式特征子集选择方法。包装式特征选择中特征子集的选择标准会依赖于后续的学习器，所以首先需要确定后续的学习器，如K近邻(K-Nearest Neighbor, KNN)、支持向量机(Support Vector Machine, SVM)、随机森林(Random Forest)等 [5] 。Wei J等人 [6] 提出了一种新的变异增强BPSO-SVM算法，增加粒子的变异概率，从而使算法跳出局部最优，获得高质量的特征。徐明等人 [7] 对正余弦算法进行改进，首先设计出一种新的非线性递减函数替代原有线性递减函数，其次引入个体最优位置引领个体位置的更新，最后引入翻筋斗觅食机制以增加群体多样性，在解决高维特征选择问题上取得较好的效果。嵌入式特征选择就是将前面的特征选择算法嵌入后续的学习器中，即在学习器训练的过程中，同时完成特征选择。由于包装式特征选择算法具有可直接对算法本身进行优化、易于实现、精度与其它两种算法相比较高等优点，所以本文采用的是包装式的特征选择方法。

特征子集的搜索策略包括穷举法、分支定界法、前向搜索法、后向搜索法、随机搜索法等 [8] 。穷举法随着特征数量的增加，特征子集的数量会呈现指数级的增长趋势，算法的复杂度很高，只适用于维数低的情况。分支定界法较穷举法复杂度相对较低，但是随着特征数量的增大，复杂度也会呈现出指数级的增长趋势。前向搜索法：每次选择一个表现最好的特征加入到已选好的特征子集中。后向搜索法：每次从已选好的特征子集中剔除一个表现最差的特征。随机搜索法：使用一定的随机优化算法如遗传算法 [9] (Genetic Algorithm, GA)、蚁狮算法 [10] (Ant Lion Optimizer, ALO)、粒子群优化算法 [11] (Particle Swarm Optimization, PSO)、灰狼算法(Grey Wolf Optimizer, GWO)等生成特征子集，再利用特定的评价函数去评定所选出的特征子集的优劣，通过不断地迭代使得选出来的特征子集的变化趋于稳定，最终得到最优特征子集。徐明等人 [12] 对灰狼算法进行改进并将其用于求解特征选择问题中，设计一种基于正弦函数的非线性过渡参数策略代替原来的线性递减策略，且在最优灰狼个体的选取上，引入小孔成像学习策略产生新的候选个体。改进算法能有效地提高分类精度，选择最优特征。随机搜索可以防止算法陷入局部最优，找到近似最优解。随机搜索算法被广泛的用于求解优化问题，路雪刚等人 [13] 对鲸鱼优化算法进行改进，并将其用于求解畜禽废弃物运输路径优化问题。MPanda等人 [14] 将灰狼算法用于求解路径规划问题。和其它的搜索方法相比，随机搜索的搜索效率远高于其它搜索方法。

受沙丘猫搜索和捕食猎物行为的启发，Amir Seyyedabbasi等人 [15] 于2022年提出了沙丘猫群优化算法(Sand Cat Swarm Optimization, SCSO)。该算法通过一种自适应机制，控制算法在搜索阶段和攻击阶段之间的过渡，具有较好的全局寻优能力，在求解高维和多目标问题中表现良好，可以将其用于求解特征选择问题。YIMING LI等人 [16] 提出了一种基于随机变异和精英协作的沙丘猫群优化算法，该算法首先引入了一种非线性周期调整机制，以平衡算法的全局探索能力和局部开发能力，加快算法的收敛速度。其次引入随机变异的精英协作策略，使算法能够跳出局部极值，进一步提高了算法的寻优精度和收敛速度。并与文献中其它群智能优化方法进行了对比实验，验证了改进策略的有效性。Dijana Jovanovic等人 [17] 提出了一种基于改进的沙丘猫群优化算法的入侵检测特征选择，在SCSO算法的基础上嵌入了著名的人工蜂群算法(Artificial Bee Colony, ABC)的搜索机制。通过在两个著名数据集(UNSW-NB15和CICIDS-2017)上验证所提出的方法，并将结果与处理相同问题并在类似配置下工作的其他前沿算法的报告结果进行比较，证明了性能改进。综合来说，SCSO算法具有较强的优化问题求解能力，但是其解存在精度低、容易陷入局部最优、迭代后期收敛速度慢等缺点，算法性能具有较大的提升空间。

2. 基本的沙丘猫群优化算法

沙丘猫群优化算法是受沙丘猫的觅食行为启发而提出的一种新的随机优化算法。沙丘猫利用它们奇妙的听觉特性，可以探测到地下活动的猎物。沙丘猫的觅食行为分为搜索猎物和攻击猎物两个阶段，并通过一种机制去控制两种行为之间的平衡。算法的数学模型如式(1)所示：

$\stackrel{\to }{Pos}\left(t+1\right)=\{\begin{array}{l}\stackrel{\to }{Po{s}_b}\left(t\right)-\stackrel{\to }{r}\cdot \stackrel{\to }{Po{s}_{rnd}}\cdot \cos \left(\theta \right),\text{if}\left|R\right|\le 1;\\ \stackrel{\to }{r}\cdot \left(\stackrel{\to }{Po{s}_{bc}}\left(t\right)-rand\left(0,1\right)\cdot \stackrel{\to }{Po{s}_c}\left(t\right)\right),\text{otherwise}.\end{array}$ (1)

其中 $\stackrel{\to }{Pos}\left(t+1\right)$ 表示第t + 1次迭代后沙丘猫的位置，其中 $\stackrel{\to }{Po{s}_b}\left(t\right)$ 为第t代时种群的最优解的位置， $\stackrel{\to }{Po{s}_c}\left(t\right)$ 表示第t代时个体当前位置， $\stackrel{\to }{Po{s}_{bc}}\left(t\right)$ 表示第t代时种群一个候选解的位置， $\stackrel{\to }{Po{s}_{rnd}}$ 为当前位置和最优位置之间的一个随机位置，计算公式如式(6)所示， $\stackrel{\to }{r}$ 表示每只猫的灵敏度范围，计算公式如式(4)所示，θ为通过轮盘赌算法选择出的随机角度。参数R用来控制沙丘猫在搜索阶段和攻击阶段之间的过渡。R的计算公式如式(2)所示：

$\stackrel{\to }{R}=2\times \stackrel{\to }{r_G}\times rand\left(0,1\right)-\stackrel{\to }{r_G}$ (2)

其中 $\stackrel{\to }{r_G}$ 为沙丘猫的常规的灵敏度范围， $\stackrel{\to }{r_G}$ 的计算公式如式(3)所示：

$\stackrel{\to }{r_G}=S_M-\frac{S_M\times ite{r}_c}{ite{r}_{max}}$ (3)

$\stackrel{\to }{r_G}$ 随着迭代次数的增加线性下降。其中iter_c为当前迭代次数，iter_max为最大迭代次数，S_M是由沙丘猫的听觉特征激发的，初始时设置其值为2。 $\stackrel{\to }{r}$ 表示每只猫的灵敏度范围，计算公式如式(4)所示：

$\stackrel{\to }{r}=\stackrel{\to }{r_G}\times rand\left(0,1\right)$ (4)

当参数R的绝对值小于等于1的时候，处于攻击阶段，使用式(5)进行位置更新。

$\stackrel{\to }{Pos}\left(t+1\right)=\stackrel{\to }{Po{s}_b}\left(t\right)-\stackrel{\to }{r}\cdot \stackrel{\to }{Po{s}_{rnd}}\cdot \cos \left(\theta \right)$ (5)

其中 $\stackrel{\to }{Po{s}_b}\left(t\right)$ 为第t代时种群的最优解的位置，θ为利用轮盘选择算法为每只沙丘猫选择出的一个随机角度， $\stackrel{\to }{Po{s}_{rnd}}$ 为当前位置和最优位置之间的一个随机位置，以确保沙丘猫可以靠近猎物，计算公式如式(6)所示：

$\stackrel{\to }{Po{s}_{rnd}}=\left|rand\left(0,1\right)\cdot \stackrel{\to }{Po{s}_b}\left(t\right)-\stackrel{\to }{Po{s}_c}\left(t\right)\right|$ (6)

当参数R的绝对值大于1的时候，处于搜索阶段，使用公式(7)进行位置更新。

$\stackrel{\to }{Pos}\left(t+1\right)=\stackrel{\to }{r}\cdot \left(\stackrel{\to }{Po{s}_{bc}}\left(t\right)-rand\left(0,1\right)\cdot \stackrel{\to }{Po{s}_c}\left(t\right)\right)$ (7)

其中 $\stackrel{\to }{Po{s}_{bc}}\left(t\right)$ 表示第t代时种群一个候选解的位置， $\stackrel{\to }{Po{s}_c}\left(t\right)$ 表示第t代时个体当前位置。

综上所述，沙丘猫的位置更新分为搜索和攻击两个阶段。在攻击阶段时，使用轮盘赌算法可以避免算法陷入局部最优陷阱，引入随机位置可以保证沙丘猫在不断地向猎物位置靠近。在搜索阶段时，选择一个随机候选解来引导沙丘猫的位置更新，沙丘猫能够找到其它的可能的猎物位置，防止算法陷入局部最优。

3. 改进的二进制沙丘猫群优化算法

本文通过引入两阶段的改进收敛因子策略和改进学习因子策略，提高了算法的全局搜索能力，加快了算法的收敛速度，并在特征子集的评价函数中加入了特征和类别之间的关联性作为评价函数的一部分。从标准UCI数据集值选取8个样本数和特征数量均不同的数据集来测试算法的性能，实验结果表明，改进后的算法具有更好的分类效果。

3.1. 基本二进制沙丘猫群优化特征选择算法

3.1.1. 基本二进制沙丘猫群优化算法

基本的沙丘猫群优化算法只能用于处理连续的问题，为了将沙丘猫群优化算法用于求解离散型问题，需要将沙丘猫的位置离散化。在初始化及位置更新时，将每只沙丘猫的位置离散化，经过离散化处理后可得到二进制沙丘猫群优化算法(Binary Sand Cat Swarm Optimization, BSCSO)，算法的具体实现如下所示。

在种群初始化时，随机生成每只沙丘猫的初始位置，每只沙丘猫每一维的位置都为0或1。初始时的位置生成公式如式(8)所示：

$P_{ij}=randint\left(0,1\right)$ (8)

其中 $P_{ij}$ 表示第i个个体在第j维中的取值。 $randint\left(0,1\right)$ 表示0或1。

在位置更新时，根据公式(1)计算出每只沙丘猫的位置，然后通过文献18中8种不同的Sigmoid函数(如式(9)~(16)所示)将每只沙丘猫的位置离散化 [18] 。具体的计算公式如式(17)所示。

$S_1:S\left(x\right)=\frac{1}{1+{\text{e}}^{-2x}}$ (9)

$S_2:S\left(x\right)=\frac{1}{1+{\text{e}}^{-x}}$ (10)

$S_3:S\left(x\right)=\frac{1}{1+{\text{e}}^{-x/2}}$ (11)

$S_4:S\left(x\right)=\frac{1}{1+{\text{e}}^{-x/3}}$ (12)

$V_1:V\left(x\right)=\left|\frac{\sqrt{\pi }}{2}{\displaystyle {\int }_0^{\left(\sqrt{\pi }/2\right)x}{\text{e}}^{-t^2}\text{d}t}\right|$ (13)

$V_2:V\left(x\right)=\left|\tanh \left(x\right)\right|$ (14)

$V_3:V\left(x\right)=\left|x/\sqrt{1+x^2}\right|$ (15)

$V_4:V\left(x\right)=\left|\frac{2}{\pi }\arctan \left(\frac{\pi }{2}x\right)\right|$ (16)

$P{N}_{ij}^t=\{\begin{array}{l}0,\text{if}Sig\left(P_{ij}^t\right)\le rand\left(0,1\right);\\ 1,\text{otherwise}\text{.}\end{array}$ (17)

其中 $P_{ij}^t$ 代表离散化前沙丘猫群第i个个体在第j维的取值，Sig表示不同的激活函数， $P{N}_{ij}^t$ 代表离散化后沙丘猫群第i个个体在第j维的取值， $rand\left(0,1\right)$ 表示0到1之间的随机数。

3.1.2. 基本二进制沙丘猫群优化算法求解特征选择问题

基本二进制沙丘猫群优化算法求解特征选择问题的伪代码如下所示：

首先对种群进行初始化，根据特征子集的评价函数计算出每个个体的适应度值，挑选出适应度值最好的个体并记录其所在的位置，根据位置更新公式更新每个个体的位置及全局最优位置，不断地重复上述过程直至达到最大迭代次数。

3.2. 改进的二进制沙猫群优化算法特征选择算法

3.2.1. 改进策略

沙丘猫独特的觅食方式使得沙丘猫群优化算法具有良好的局部寻优能力，但同时算法也存在容易陷入局部最优的问题。为了提高算法的全局搜索能力，本文提出了一种两阶段的改进收敛因子的策略，增加了处于搜索阶段的迭代次数，提高了算法的全局搜索能力。

在搜索阶段和攻击阶段时的位置更新公式中，SCSO算法通过随机解引领个体位置的更新，这样虽然可以防止算法陷入局部最优，但同时也会导致算法出现收敛速度慢、精度低等问题。受PSO算法中粒子的位置更新公式的启发，我们引入社会学习因子和认知学习因子策略，通过全局最优位置和局部最优位置共同引领个体位置的更新，加快了算法的收敛速度。

(1) 两阶段的改进收敛因子策略

沙丘猫的觅食行为分为搜索和攻击两个阶段，搜索阶段类似全局搜索，即对整个可行域进行搜索。攻击阶段类似局部搜索，即对某一部分区域进行密切搜索。如何协调算法在搜索和攻击阶段之间的过渡是至关重要的。

由公式(1)可知，R控制算法在两个阶段之间的过渡，在|R| > 1时，算法的搜索范围广，算法具有较好的全局搜索能力，当|R| < 1时，算法具有较好的局部开发能力。由公式(2)可知，R的取值由 $\stackrel{\to }{r_G}$ 决定，由公式(3)可知， $\stackrel{\to }{r_G}$ 在算法的迭代过程中由2线性递减到0。而在实际的沙丘猫捕食猎物的过程中，收敛因子 $\stackrel{\to }{r_G}$ 的线性变化并不能满足实际的要求。本文提出了一种两阶段的改进收敛因子的策略，在第一阶段，采用线性递减的策略，在第二阶段，采用对数函数非线性调整收敛因子，与原有的线性递减的策略相比，增加了处于搜索阶段的迭代次数，提高了算法的全局搜索能力，加快了算法的收敛速度。收敛因子 $\stackrel{\to }{r_G}$ 的更新公式如式(18)所示：

$r_G=\{\begin{array}{l}{S}_M-S_M\ast t/ite{r}_{Max}\text{,if}{r}_G>\text{1}\text{.2;}\\ 1.2/\lg 1.2\ast \lg \left(1.2-{\left(t/ite{r}_{max}\right)}^k\right),\text{otherwise}.\end{array}$ (18)

其中S_M值设为2，k的值设为3，t表示当前迭代次数，iter_max表示算法的最大迭代次数。

(2) 引入社会学习因子和认知学习因子策略

由公式(7)可知，在搜索阶段，通过一个随机候选解引领沙丘猫个体位置的更新，这样虽然可以保证算法的随机性较强，不易陷入局部最优，但同时会使得算法的收敛速度较慢。为了解决这一问题，我们引入了全局最优位置，使用随机候选解和全局最优解共同引领位置的更新。改进后的位置更新公式如式(19)所示：

$\stackrel{\to }{Pos}\left(t+1\right)=\stackrel{\to }{r}\cdot \left(a\ast \stackrel{\to }{Po{s}_{bc}}\left(t\right)+\left(1-a\right)\ast \stackrel{\to }{Po{s}_b}\left(t\right)-rand\left(0,1\right)\cdot \stackrel{\to }{Po{s}_c}\left(t\right)\right)$ (19)

权重系数a值设置为0.9。由式(1)可知，沙丘猫的位置更新方式具有过大的随机性，在维度较高的条件下，算法的性能会很差。为了加快算法的收敛速度，受粒子群算法影响，让搜索方向保持一定的惯性，不易轻易改变，我们引入了惯性权重w。为了加快算法的寻优速度，能够更快的找到最优解，我们引入了学习因子c₁、c₂。通过随机位置、局部最优位置和全局最优位置共同引领沙丘猫位置的更新，使沙丘猫能够更快的向最优位置靠近。改进后的位置更新公式如式(20)~(21)所示。公式(20)用于搜索阶段的位置更新，公式(21)用于攻击阶段的位置更新。

$\begin{array}{c}\stackrel{\to }{Pos}\left(t+1\right)=w\cdot \stackrel{\to }{r}\cdot \left(a\ast \stackrel{\to }{Po{s}_{bc}}\left(t\right)+\left(1-a\right)\ast \stackrel{\to }{Po{s}_b}\left(t\right)-rand\left(0,1\right)\cdot \stackrel{\to }{Po{s}_c}\left(t\right)\right)\\ +c_1\cdot rand\left(0,1\right)\cdot \left(\stackrel{\to }{Po{s}_b}\left(t\right)-\stackrel{\to }{Po{s}_c}\left(t\right)\right)+c_2\cdot rand\left(0,1\right)\cdot \left(\stackrel{\to }{Po{s}_p}\left(t\right)-\stackrel{\to }{Po{s}_c}\left(t\right)\right)\end{array}$ (20)

$\begin{array}{c}\stackrel{\to }{Pos}\left(t+1\right)=w\cdot \left(\stackrel{\to }{Po{s}_b}\left(t\right)-\stackrel{\to }{r}\cdot \stackrel{\to }{Po{s}_{rnd}}\cdot \cos \left(\theta \right)\right)+c_1\cdot rand\left(0,1\right)\cdot \left(\stackrel{\to }{Po{s}_b}\left(t\right)-\stackrel{\to }{Po{s}_c}\left(t\right)\right)\\ +c_2\cdot rand\left(0,1\right)\cdot \left(\stackrel{\to }{Po{s}_p}\left(t\right)-\stackrel{\to }{Po{s}_c}\left(t\right)\right)\end{array}$ (21)

其中惯性权重w的值设置为0.9，学习因子c₁、c₂的值设置为0.5， $\stackrel{\to }{Po{s}_b}\left(t\right)$ 表示第t代时的局部最优位置。

将上述两种策略融入到算法中，在增强算法的全局搜索能力的同时加快算法的收敛速度。

3.2.2. 改进二进制沙丘猫群优化算法求解特征选择问题

改进的二进制沙丘猫群优化算法(Improved Binary Sand Cat Swarm Optimization, PBSCSO)求解特征选择问题的伪代码如下所示：

3.2.3. 改进策略的验证

从标准UCI数据集中选取8个数据集测试算法的性能，数据集详情见表3所示。使用S₃型函数作为沙丘猫位置离散化的转换函数，用2.3节中的特征子集评价函数计算个体的适应度值。设置算法的执行次数为30次，种群规模为10，最大迭代次数为100，使用K-NN分类器以及holdout验证的方式对筛选出来的特征子集的性能进行评估，K的值设置为5。

表1是在BSCSO算法的基础上引入两阶段的改进收敛因子策略(Convergence Binary Sand Cat Swarm Optimization, CBSCSO)与BSCSO算法的比较。使用3.3节中的特征子集的评价指标作为评估标准，其中AVG表示运行30次所得的最优适应度值的平均值，AVGALL表示在8个数据集上最优适应度值的平均值。从结果可以看出CBSCSO在7个数据集上表现较优，且在所有数据集上的平均性能较好。说明本文提出的两阶段的改进收敛因子策略是有效的，能够加强算法的全局搜索能力，找到更优的特征子集。

Table 1. The average of the optimal fitness values of the two algorithms

表1. 两种算法的最优适应度值的平均值

表2是在BSCSO算法的基础上引入社会学习因子和认知学习因子策略(Study Binary Sand Cat Swarm Optimization, SBSCSO)与BSCSO算法的比较。其中AVG表示运行30次所得的适应度值收敛时的迭代次数的平均值。从结果可以看出SBSCSO在8个数据集上表现都较优，说明本文提出的引入改进学习因子的策略能够提高算法的收敛速度，更快找到最优特征子集。

Table 2. The number of iterations when the fitness values of the two algorithms converge

表2. 两种算法适应度值收敛时的迭代次数

3.3. 特征子集评价函数

分类问题的特征选择中，为了提高算法的性能，在特征子集的评价函数设计时，不仅需要考虑分类的准确率，还需将特征子集的维度、特征和类别的相关性考虑在内。其中特征和类别的相关性通过特征和类别之间的互信息来计算。本文利用改进的二进制沙丘猫群优化算法搜索特征子集，用特征值为1或0代表特征是否被选中，引入K-NN分类器验证分类的准确率，构造了一种新的特征子集的评价函数如式(22)所示。

$feature\text{\_}val=0.98\ast ERate+0.01\ast \frac{SelNum}{Sum}+0.01\ast \frac{{\displaystyle \sum \left(1-I\left(X;Y\right)\right)}}{SelNum}$ (22)

其中ERate表示分类的错误率，SelNum表示被选中的特征子集(即离散化后特征值为1)中特征的数目，Sum表示数据集中特征的数目，I(X;Y)表示每个被选中的特征和类别之间互信息。在分类问题中，分类准确率是最重要的评价标准，因此将分类错误率的权重设置为0.98，特征子集的维度和特征和类别之间的相关性的权重设置为0.01。

4. 实验及结果分析

4.1. 测试文本

使用python编写程序，从标准UCI数据集值选取8个样本数和特征数量均不同的数据集来测试算法的性能。表3给出了数据集的名称、特征值的数量、样本的数量、类别数量。

Table 3. Data set introduction

表3. 数据集介绍

4.2. 测试算法及相关参数

将PBSCSO与GA、BPSO [19] 、BGWO [20] 、BSCSO对比，使用KNN分类器以及holdout验证的方式对筛选出来的特征子集的性能进行评估，K的值设置为5。五种群智能算法的初始种群数为10，最大迭代次数为100，算法运行次数为30。GA算法中交叉概率为0.9，变异概率为0.1。PSO算法中设置惯性权重w为1.0，学习因子c₁ = c₂ = 1.8。BSCSO中角度范围设置为[0, 360]。

除此之外，在BSCSO算法中沙丘猫的位置离散化时，我们采用式(9)~(16)中8中不同的转换函数，并将结果最好的转换函数用于PBSCSO中。

4.3. 评价指标

使用分类准确率、适应度值、最优特征子集的维度作为评价指标与其他的4种群智能优化算法进行比较，证明PBSCSO算法的有效性。

(1) 分类准确率

分类准确率是分类正确的样本数占样本总数的比例，是度量分类问题最主要的评价指标。分类准确率计算公式如式(23)所示：

$avgAcc=\frac{1}{K}{\displaystyle {\sum }_{i=1}^K\frac{1}{N}{\displaystyle {\sum }_{j=1}^{N}compare\left(O_j,R_j\right)}}$ (23)

其中K表示算法的执行次数，N表示用于验证的样本的总数量，O_j表示输出得到的类标签，R_j表示真实的类标签。compare将算法输出得到的类标签与数据的真实标签进行对比，如果相同为1，不同为0。

(2) 适应度值

适应度值由三部分组成，分别是分类的准确率、特征子集的维度、特征和类别之间的相关性。算法执行K次，求每次执行完后所求得的最佳位置的适应度值的平均值，计算公式如式(24)所示：

$avgFit=\frac{1}{K}{\displaystyle {\sum }_{i=1}^K{w}_1\ast ERate}+w_2\ast \frac{SelNum}{Sum}+w_3\ast \frac{{\displaystyle \sum \left(1-I\left(X;Y\right)\right)}}{SelNum}$ (24)

其中K表示算法的执行次数，w₁表示分类准确率所占的权重，取值为0.98，w₂表示特征子集的维度所占的权重，取值为0.01，w₃表示被选中的特征和类别之间的相关性的权重，取值为0.01。ERate表示分类的错误率，SelNum表示被选中的特征子集的维度，Sum为特征的总数目，I(X;Y)表示每个被选中特征和类别之间的相关性。

(3) 最优特征子集的维度

最优特征子集的维度就是每次迭代结束后所挑选出来的特征子集中值为1的特征的个数。算法执行K次，求特征子集维度的平均值，计算公式如式(25)所示：

$avgSize=\frac{1}{K}{\displaystyle {\sum }_{i=1}^{K}size\left(f_i\right)}$ (25)

其中K表示算法的执行次数，f_i表示第i次执行所选出的特征子集，size(f_i)表示所选出的特征子集的维度。

4.4. 实验分析

本文采用五种不同的算法在表3中8种不同的UCI数据集上进行了30次独立重复实验。表4是BSCSO算法在8种测试数据集上利用八种不同的转换函数最终得到的分类准确率的情况。其中AVG表示运行30次所得的分类准确率的平均值，STD表示其对应的标准差，AVGALL表示在8个数据集上分类准确率的平均值，STDALL表示在8个数据集上的分类准确率标准差的平均值。从结果可以看出，虽然使用S₃型转换函数进行离散化在个别数据集上表现并不突出，但其所得到的准确率的平均值最高，对于不同数据集上进行特征子集选择的平均性能较好。因此，选取S₃型转换函数进行离散化，并将该转换函数用于以下PBSCSO中沙丘猫位置的离散化。

表5是PBSCSO与其它的四种算法分类准确率的比较，其中AVG表示运行30次所得的分类准确率的平均值，STD表示其对应的标准差，AVGALL表示在8个数据集上的分类准确率的平均值，STDALL表示在8个数据集上的分类准确率标准差的平均值。从结果可以看出，BGWO在Breastcancer数据集上表现最好，BSCSO在BreastEW和IonosphereEW数据集上表现最好，PBSCSO在Breastcancer、HeartEW、Lymphopgraphy、SpectEW、WineEW和Zoo数据集上表现都是最好的，在BreastEW和IonosphereEW数据集上的表现仅次于最优值。相比较于GA、BPSO和BGWO，本文提出的PBSCSO算法的特征选择机制在大多数数据集上都可以进一步的提升分类的效果，说明在进行特征选择时，PBSCSO能够有效的提取出和类别相关信息，找到最优特征子集。

Table 4. Classification accuracy of BCSCSO algorithm under eight conversion functions

表4. BSCSO算法在8种转换函数下的分类准确率及其标准差

Table 5. The mean value and standard deviation of classification accuracy of the five algorithms

表5. 5种算法的分类准确率的平均值及其标准差

分类准确率是衡量分类问题的性能的最重要的指标，从表5可以看出，PBSCSO在不同数据集上进行特征子集选择的平均准确率最高、平均标准差最小，这表明使用PBSCSO算法的特征选择机制的分类效果最好且比较稳定。

表6是PBSCSO与其他的四种算法适应度值的比较，其中AVG表示运行30次所得的最优适应度值的平均值，STD表示其对应的标准差，AVGALL表示在8个数据集上的适应度值的平均值，STDALL表示在8个数据集上的适应度值标准差的平均值。从结果可以看出，BPSO在WineEW数据集上表现最好，BSCSO在HeartEW数据集上表现最好，PBSCSO在Breastcancer、BreastEW、Lymphopgraphy、SpectEW、IonosphereEW和Zoo数据集上表现都是最好的，在WineEW和HeartEW数据集上表现仅次于最优值。相比较于GA、BPSO和BGWO，本文提出的PBSCSO算法的特征选择机制在大多数数据集上都可以进一步的提高算法的寻优能力，说明在进行特征选择时，PBSCSO能够选出最优特征子集。相比于BSCSO，本文提出的PBSCSO算法在大部分数据集上适应度值都较小，说明本文提出的两阶段的改进收敛因子策略是有效的，能够提升算法的寻优能力。

Table 6. The mean value and standard deviation of the optimal fitness values of the five algorithms

表6. 5种算法的最优适应度值的平均值及其标准差

适应度值综合考虑分类的准确率和所选出来的最优特征子集的维度，从表6可以看出，PBSCSO在不同数据集上进行特征子集选择的平均适应度值最小、平均标准差最小，这表明使用PBSCSO算法的寻优能力最好且比较稳定。

图1是在8种不同的数据集上利用5种不同的算法得到的最优特征子集的数量平均值情况。和BPSO、BGWO和BSCSO相比，PBSCSO在大多数数据集上的特征子集的维度都是最小的，和GA相比，两种算法在8个数据集上的特征子集的维度基本一致。从结果可以看出，本文提出的PBSCSO算法能够在保证分类准确率的前提下，有效的降低所选出的最优特征子集的维度。

综上所述，PBSCSO算法能够在保证特征子集维度较小的情况下提高分类的准确率，寻到更优的特征子集。将PBSCSO算法用于求解特征选择问题能取得较好的效果。

(a) Breastcancer (b) BreastEW

(c) HeartEW(d) Lymphopgraphy

(e) SpectEW (f) IonosphereEW(g) WineEW(h) Zoo

Figure 1. Number of feature subsets

图1. 特征子集数量

5. 结论

PBSCSO特征选择算法通过引入两阶段的改进收敛因子策略，增加了处于搜索阶段的迭代次数，提高了算法的全局搜索能力。通过引入社会学习因子和认知学习因子策略，有效地降低了个体位置更新时的随机性，加快了算法的收敛速度。实验结果表明，引入两阶段的改进收敛因子策略能够增强算法的寻优能力，引入社会学习因子和认知学习因子策略能够加快算法的收敛速度。与GA、BPSO、BGWO和BSCSO相比，PBSCSO特征选择算法在提高分类准确率、降低最优特征子集的维度、鲁棒性和收敛性等方面均表现较好。

NOTES

^*第一作者。