采用改进黑猩猩优化算法的特征选择

张婉莹，冷 欣，贾鹤鸣

（1.东北林业大学机电工程学院 黑龙江省 哈尔滨 150040；2.三明学院信息工程学院 福建 三明 365004）

随着社会逐渐趋于数字化，如何从繁杂庞大的数据中有效提取出有用信息成为了近些年的研究重点，机器学习因其较强的数据处理能力得到了广泛应用。传统机器学习包括随机森林算法、朴素贝叶斯算法和支持向量机(support vector machine,SVM)等[1]。王联英等[2]利用C4.5算法构造决策树，显著提高了分类效果；李鲜[3]基于随机森林的特征选择算法解决了图像处理中灰度对比度低、边界模糊等问题；崔良中[4]通过改进朴素贝叶斯算法解决了近年来机器学习领域数据分类时间过长的问题；张健沛[5]提出了一种利用支持向量机进行主动学习的方法，解决了部分机器学习问题中获取训练样本代价过大的问题。上述文献研究探索了不同的机器学习算法，而目前许多研究者们提出将优化算法与特征选择工作任务相结合来研究如何高效无差错地进行数据预处理工作[6]。特征选择就是从样本中选择特征子集[7]，特征子集的获取有过滤式、封装式和嵌入式三种类型[8-10]。封装式就是将子集的选择看作是一个搜索寻优问题。如Mafarja等[11]提出了一种基于鲸鱼优化的封装式特征选择方法；张霞等[12]提出一种增强蜂群算法优化的封装式特征选择方法。以上研究表明，封装式特征选择能够有效与元启发式优化算法相结合，并取得较好的实际应用效果。

传统黑猩猩优化算法(chimp optimization algorithm,ChOA)将猩猩分为不同等级，使其能很好地解决收敛速度慢的问题。但是该算法仍存在陷入局部最优的风险。黄倩等[13]人提出了一种多策略黑猩猩优化算法以提高种群的局部开发能力和勘探能力，从而提高算法的收敛精度。Mandeep Kaur等[14]提出了一种正弦余弦黑猩猩优化算法来克服黑猩猩优化算法收敛速度慢的缺点。针对黑猩猩优化算法易陷入局部最优的缺点提出了一种改进的黑猩猩优化算法(improved chimp optimization algorithm,IChOA)。通过改进低等级黑猩猩的位置来提高黑猩猩的全局搜索能力。首先引入斯皮尔曼等级相关系数计算低等级和高等级黑猩猩之间的距离，针对距离高等级黑猩猩较远的黑猩猩再引入甲虫天线搜索算法，使其能根据周围环境改变自己的运动方向，从而提高局部搜索能力，进而提高黑猩猩算法的全局搜索寻优能力。

本文的主要研究内容如下，首先在原始黑猩猩算法中引入斯皮尔曼等级相关系数和甲虫天线搜索算法，以增强全局搜索能力；然后，利用改进后的黑猩猩优化算法对支持向量机进行优化，将此模型应用于封装式特征选择中；最后，将该改进算法与四种优化算法在10种数据集中进行比较，证明该算法在提高全局优化精度、减少所需特征数和避免陷入局部最优方面有明显优势，具有较高的工程实用价值。

1 背景知识

1.1 支持向量机

支持向量机是Vapnik在统计学基础上提出的[15]，因其拥有较强的计算能力，所以被广泛应用于模式识别和回归分析中[16]。它通过构造最优的分离超平面对数据进行分类，构造出的分离超平面不仅要尽可能不出错地分离两种数据，而且要使两者之间的分离间隔尽可能达到最大[17]，超平面的数学方程如下：

式中，w为垂直于超平面的权值，x为超平面上的特征向量，b为偏置常数，原点到超平面中间的垂直距离用‖b‖/‖w‖表示。

支持向量机的最优超平面如图1所示。

图1 SVM的最优超平面示意图

1.2 黑猩猩优化算法

黑猩猩优化算法是一个基于群智能多样性的数学模型[18]。该算法由攻击者、障碍者、追逐者和驱动者四种不同类型的黑猩猩配合完成狩猎。狩猎步骤分为两个阶段：第一阶段为勘探阶段，如图2所示；第二阶段为开发阶段，如图3所示。勘探阶段为驱赶、阻挡和追逐猎物。而后进入开发阶段，此阶段由攻击者直接攻击猎物。驱赶和追逐过程可表示为：

图2 黑猩猩优化算法的勘探阶段[18]

图3 黑猩猩优化算法的开发阶段[18]

式中：xprey代表猎物位置矢量；xchimp代表黑猩猩位置矢量；t为当前迭代次数；a、c、m为系数矢量，这三个系数矢量由以下式子求出：

式中：f为从2.5下降到0的非线性矢量；r1和r2是0到1之间的随机数；m是混沌向量。同时黑猩猩可以根据其他黑猩猩的位置来更新自己的位置，更新过程可以用下式表示：

2 改进的黑猩猩优化算法

2.1 斯皮尔曼等级相关系数

斯皮尔曼等级相关系数利用单调方程评价两个统计变量的相关性，单调方程如下：

式中：ρ为斯皮尔曼等级相关系数的值；di为每对样本的等级差；n为序列的维数。如果数据中没有重复值，当两个变量完全单调相关时，斯皮尔曼相关系数的绝对值为1。

2.2 甲虫天线搜索算法

甲虫天线搜索算法是根据长角甲虫寻找食物的过程提出的[19]。甲虫在寻找食物时能通过触角探测食物的气味，从而发现食物的位置。

在寻找食物时，甲虫通过摆动触角来探测附近区域同时感知气味，当甲虫检测到左侧区域的气味浓度高于右侧时，甲虫会像左移动，反之，甲虫向右移动，如图4所示。

图4 甲虫运动示意图

甲虫的运动方向可以由以下数学模型得到：

甲虫在左右侧搜索区域的位置分别由以下两个数学模型得到：

式中：xl和xr分别表示甲虫在左右搜索区域内的位置；xt表示甲虫在t时刻的位置；dt表示甲虫天线所感知到的长度，此长度会随着时间的推移逐渐减小。

甲虫的位置更新可以用如下方程表示：

式中：δ为搜索的步长，步长的初始范围为搜索区域；x处的气味浓度用表示，f(x)也称为适应度函数。

2.3 改进策略

由于种群的位置更新是由四个等级的黑猩猩共同决定的，为了避免种群陷入局部极小值，所以需要对低等级的黑猩猩的位置进行改进。通过计算驱动者和攻击者之间的斯皮尔曼等级相关系数，可以确定它们之间的距离。斯皮尔曼等级相关系数等于0时，这两种黑猩猩不相关，此时可以看作驱动者与攻击者之间的距离很远。对于离攻击者较远的黑猩猩引入甲虫天线搜素算法，使低等级的黑猩猩获得类似甲虫的搜索能力，让其能够判断周围的环境，从而决定移动的方向。通过这种方式改进低等级黑猩猩的位置，以防止此算法陷入局部最优值。

2.4 IChOA优化SVM与特征选择（IChOA-SVM）

IChOA-SVM模型通过惩罚参数c和核参数g生成初级粒子，并计算适应度值来评估黑猩猩的位置。最后输出c、g的最优值和最佳精度，得到最终的分类结果。

IChOA-SVM的实现步骤如下，流程图如图5所示。

图5 IChOA-SVM算法流程图

输入：最大迭代次数Maxiterations，种群规模N，上界ub，下界lb，参数c的最大值cmax和最小值cmin，参数g的最大值gmax和最小值gmin。

输出：最佳参数c和g，对应的分类精度和适应度。

步骤1初始化黑猩猩的数量、位置和适应度值。

步骤2支持向量机随机生成c和g的值，然后计算初始适应度值。

步骤3训练模型由支持向量机中的训练集得到。

步骤4对种群重新进行排序，得到个体的位置和适应度值。

步骤5引入斯皮尔曼等级相关系数和甲虫天线搜索算法来提高低等级黑猩猩更新位置的能力。

步骤6更新惩罚参数c和和核参数g后，在支持向量机上再次进行训练。

步骤7进行迭代优化，得到最优的c和g值以及最佳精度。

3 实验

本文采用UCI数据库中的10个数据集来评价所提出的IChOA-SVM方法，表1分别给出了10个数据集的特征数、样本数和类别数。

表1 数据集列表

为了验证算法的性能，本文将IChOA算法与ChOA、PSO(particle swarm algorithm)、WOA(Whale Optimization Algorithm)、GOA(g'rasshopper optimization algorithm)算法进行比较。同时将每组实验重复30次，以减少随机影响。其中种群大小为30，当迭代次数达到100时停止运行。所有实验均在由美国 Math Works公司出品的 MATLAB软件上进行，所用版本为 R2016a，计算机配置为Intel(R)Core(TM)i5-1035G1 CPU@1.00GHz 1.19GHz，使用 Microsoft Windows 10 系统。

实验中所有算法的参数设置如表2所示。

表2 不同算法的参数设置

表3给出了五种算法在十个数据集上分类精度的平均值和标准差。图6给出了其中4个数据集的精度箱型图。由表3观察到IChOA优化算法在7个数据集上都获得了最佳性能，以Bupa数据集为例，IChOA的精度约比ChOA高出4% ，这表明该数据集IChOA中的SVM参数可以得到更好的优化；同时从精度箱形图中的分布可以看出，IChOA的精度较为稳定，该算法的精度在10个数据集上变化不大。值得注意的是，虽然在包含Glass数据集在内的三个数据集中，WOA优化算法取得了最优精度，但从箱型图上不难发现，其稳定性略有不足。综合分析可知IChOA在保持较高平均精度的同时也保持了较好的稳定性。

图6 基于4个数据集的IChOA等算法的精度箱型图

表3 五种算法在10个数据集上的分类精度比较

表4给出了五种算法在10个数据集上所需特征数的均值和标准差。IChOA在其中9个数据集中所需的特征数量都是最低的，特别是在Iris和Liver数据集中，所需特征数的平均值非常接近1，这表明IChOA可以更有效探寻搜索空间。在Cancer和Sonar数据集中，有几种优化算法所需要的特征数量比其他优化算法高得多（如WOA），但IChOA无该情况发生。值得注意的是，在Iris数据集中，ChOA所需要的特征数量比IChOA高94% ，这也说明了IChOA在所需特征数量方面优于ChOA等算法。

表4 五种算法在10个数据集上所需特征个数的比较

表5给出了五种算法在10个数据集上的适应度值的平均值和标准差。图7为4个实验所用数据集的适应度值折线图。IChOA的适应度值在其中7个数据集中均取得最小值。通过收敛曲线图可以看出大部分数据集中，IChOA收敛时间要短于其他算法。虽然WOA在Glass，QCM和Sonar数据集中适应度值均为最小，但其在Lymphography数据集中的适应度值远大于其他算法。反观IChOA算法，即使适应度值不是最小，但其适应度值也接近适应度值最小的算法。综上可以看出，IChOA比大多数算法更加优异和稳定。

表5 五种算法在10个数据集上的适应度比较

续表5

图7 基于4个数据集的IChOA等算法的适应度值的折线图

4 总结

针对传统黑猩猩优化算法在运行时容易陷入局部极小值的缺陷，本文提出了一种改进的黑猩猩优化算法，并且将改进的黑猩猩优化算法结合支持向量机进行特征优化选择。该方法能够对支持向量机核函数的参数进行调整，同时进行特征选择，并达到最佳的精度。从实验结果来看，IChOA算法在精度、特征数和适应度值上相较于其他4种优化算法都具有一定优势，且其综合性能相对稳定。在今后的工作中，可以进一步尝试提高IChOA算法的精度，使其能够更好地应用于特征选择领域。