基于模拟退火斑点鬣狗优化算法的特征选择

贾鹤鸣，姜子超，李瑶，孙康健，李金夺，彭晓旭

东北林业大学 机电工程学院，黑龙江 哈尔滨 150040

数据预处理是数据挖掘的一部分，可显著地改善数据挖掘的性能。特征选择是数据预处理的重要步骤，在减少处理时间的同时，处理更多的特征，进而提高机器学习的准确性[1]。特征选择问题是从某些特征中选取部分特征作为特征子集，所选子集具有比原特征集更优秀的分类效果，其中分类精度与选择特征个数是特征选择的基本评价标准。特征选择分为子集生成、子集评估、停止标准、结果验证4个步骤，过滤式和封装式是特征选择的2种基本方法[2]，过滤式可以较快地获取结果，但无关于后续的学习算法；而封装式虽然速度上有劣势，但准确率高、偏差小，更适合结合优化算法提高运行效率和精度，因此近年来多种混合元启发式算法已在特征选择领域进行了相关研究。贾鹤鸣等[3]提出一种基于热交换的混合海鸥优化算法应用于特征选择问题，极大地改善了原算法的信息分类与选择能力；Wu等[4]将遗传算法的交叉算子用于模拟退火算法，对支持向量机回归的输入特征子集选择、核函数类型和核参数设置进行优化，效果显著；Basiri等[5]提出了一种混合蚁群和遗传算法，并将其应用于文本文档的分类中，分类效果良好；Mafarja等[6]提出了一种基于模拟退火的混合鲸鱼优化算法，并将其应用于特征选择中，明显改善了分类精度。上述所提出的混合元启发式算法在特征选择中均体现出明显的优势，但是No-Free-Lunch定理表明没有一种算法可以解决所有优化问题，这促使我们不断探索更优秀的优化算法以解决特征选择问题[3]。

斑点鬣狗优化是印度塔帕尔大学Dhiman等[7]提出的一种新的优化算法，它主要模拟了斑点鬣狗的狩猎行为。斑点鬣狗依靠可信赖的朋友网络和识别猎物的能力来捕食猎物，这种狩猎方法可以在更短的时间内找到更好的解决方案。斑点鬣狗优化极大地增强了算法的自适应性，同时可以扩展到更高的维度，在优化问题中得以广泛应用，但受随机因子影响仍存在局部最优、复杂优化效果不良等缺陷；模拟退火算法是由Kirkpatrick等[8]提出的元启发式算法，算法从一个较高的温度开始，在温度持续下降和概率函数组合的条件下去搜索空间中目标函数的全局最优解。模拟退火算法具有强大的局部搜索功能，将其应用于混合算法中可以改善局部最优解。

针对班点鬣狗算法受随机因子的影响而导致的全局优化效果差、局部易陷入最优等问题，结合模拟退火算法的优点，本文提出一种模拟退火斑点鬣狗优化的混合元启发式算法，采用封装式的方法并将其应用于特征选择。在混合算法中，模拟退火算法作为斑点鬣狗算法中的一部分，2种算法均在每次迭代中运行一次，有效地提高了斑点鬣狗算法的利用率。为检验混合优化算法在特征选择中优越性，通过特征选择的8个数据集进行测试实验，采用平均分类精度、适应度、选择特征个数（平均值，标准差）、运行时间4个指标来评价优化效果，与原始优化算法、其他4种算法 (蚁群优化 (ant colony optimization, ACO)[9]、混合鲸鱼模拟退火优化算法(hybrid whale optimization algorithm with simulated annealing, WOASA)[6]、正余弦算法(sine cosine algorithm, SCA)[10]、混合海鸥优化算法(hybrid seagull optimization algorithm, HSOA)[3])对比。

1 原始优化算法

1.1 模拟退火算法

模拟退火算法以一定的概率接受比当前解更差的解，因此可以跳出局部最优解并且获得全局最优解。模拟退火算法起始于随机生成的解，根据预先定义的邻域结构，在每次迭代中产生最佳的邻域解，利用适应度函数进行评估[11]。当邻域解比当前解更好时，将其认为是最新的解，否则由Boltzmann概率确定最新解的概率，Boltzmann概率表示为

1.2 斑点鬣狗优化算法

斑点鬣狗是非常聪明的群体社交动物，它们通过多种感官来识别亲属和其他个体，并对同一种族的关系进行了排名，群体中具有高地位的个体优先获得信任。由于这种生活习性，斑点鬣狗在群体狩猎方面具有非常高的成功率。斑点鬣狗种群的捕食机制包括搜索、包围、狩猎和攻击猎物四个过程[7]。斑点鬣狗算法的基本原理如下：

1)包围机制：斑点鬣狗具有熟悉并判断猎物的位置，从而包围它们的能力。该行为的数学模型由具体描述为

斑点鬣狗的个体位置更新为

2)狩猎机制：斑点鬣狗通常依靠可信赖的种群网络及识别猎物位置的能力来生活和分组捕杀。该机制的具体描述为

3)攻击猎物（局部搜索）：斑点鬣狗在猎食的最后阶段开始攻击猎物，当收敛因子时，斑点鬣狗个体便会向猎物发动攻击。全局最优解通过求取当前最优解集的平均值来确定斑点鬣狗搜索个体的更新趋势。攻击猎物的数学公式具体描述如下：

4)搜索机制（全局探索）：斑点鬣狗大多根据位于最优解群集中的斑点鬣狗群或群集的位置来搜寻猎物，当收敛因子时，斑点鬣狗将分散，远离当前的猎物，并寻找更合适的猎物位置。这种机制使得算法可在全局搜索。

2 混合优化算法模型

2.1 二进制方案与适应度函数

特征选择的本质是二元优化问题，其解仅限于二进制{0,1}值，因此在使用斑点鬣狗优化算法的特征选择问题中需要制定二进制方案。优化中，一维向量可以表示一个解决方案，其长度是原始数据集中的特征数目。解中的每个值均可由“0”或“1”表示，值“0”表示未选择该特征，值“1”表示选择了该特征[13-14]。

特征选择可以看作是一个多目标优化的问题，其中主要有2个目标相互矛盾：分类精度与选择的特征个数。当分类结果中分类精度较高，选择特征个数较少时表明所得分类效果较好[15]。在整个迭代过程中，一般采用适应度函数来评估每个解的质量。因此，模拟退火和斑点鬣狗优化算法可以平衡分类精度和选择特征个数这2个标准。根据KNN分类器得到的解的分类精度和选择的特征个数，所得适应度函数为

2.2 模拟退火斑点鬣狗混合算法

斑点鬣狗优化是一种在诸多优化问题上取得良好效果的算法，强大的局部搜索能力是模拟退火的优势，把斑点鬣狗优化算法得到的解作为初始状态，然后利用模拟退火对其进行优化，增强整个搜索过程中的局部寻优能力，进而得到整体最优解，形成新的混合模拟退火斑点鬣狗优化算法(simulated annealing spotted hyena optimization,SASHO)，其中模拟退火用作班点鬣狗算法的优化算子。混合算法的流程图如图1所示。

图1 混合算法的流程图

3 实验设计

3.1 数据集

实验基于UCI数据存储库中的8个数据集测试来评价混合算法的性能[17]，每个数据集的特征个数和样本个数如表1所示，可以根据二进制方案进行有效测试。

表1 实验数据集列

3.2 实验参数设置

在实验中，选择原始算法与混合算法作为测试算法，种群大小设置为30，最大迭代次数取100。交叉验证划分每个数据集可评估算法的有效性，基于欧几里得距离矩阵的KNN分类器(K=5)可以产生最佳的化简效果。在K-fold交叉验证中，训练和验证的子集个数为(K-1)，测试子集个数为1，重复M次，则每个优化算法对每个数据集进行KM次评估[18-20]。此外，实验中还选择了一些较新的优化算法在UCI数据集上进行测试，包括ACO、WOASA、SCA和HSOA算法，其参数设置列在表2中。这些优化算法均适用于特征选择，因此与所提算法形成对比。实验运行环境为MATLAB2016a。

表2 4种对比算法的参数

3.3 测试评价标准

为证明优化算法在特征选择过程中的优化效果，本文采用以下标准评估每个优化算法[21]：

平均分类精度：描述了所选特征集的分类精度的平均值。分类精度计算如下：

适应度标准差δstd：表示在执行次优化算法后得到的最优解的变化，可表示为

平均运行时间：表示每次运行算法的平均时间（s）。计算以下内容：

4 实验结果及分析

4.1 原始算法与混合算法的对比

为了验证所提算法的在特征选择则中的有效性与优越性，将原始算法与混合算法在8个数据集上进行测试，测试结果分别从平均分类精度、平均选择特征个数、适应度（平均值/标准差）与平均运行时间上进行评价。基于2种算法在分类精度和选择特征个数上的测试结果如表3所示，数据表明：在分类精度上，所提混合算法可以对数据集更准确地分类，在选择特征个数上，所提混合算法可以对数据集选取更少的特征个数。因此所提混合算法在特征选择中表现良好，表明算法有效；基于2种算法在特征选择中的适应度（平均值、标准偏差）实验结果如表4所示，数据表明：所提混合算法在适应度(Mean、std)值上表现良好。因此，所提混合算法比原始算法具有更好的效果和稳定性；基于2种算法的平均运行时间如表5所示。数据表明：在8个数据集的运行时间上，原始算法略小于所提算法，这是由模拟退火算法中的适应度函数的运行时间略长所造成的。综上所述，实验测试结果表明：在特征选择中，所提混合算法有效且比原始算法有一定的优越性。

表3 2种算法在分类精度和所选特征平均数的测试结果

表4 2种算法的适应度（平均值、标准差）值测试结果

表5 2种算法的平均运行时间s

4.2 混合算法与其他优化算法的对比

在前文中，所提混合算法在特征选择中的分类精度和选择特征个数上优于原始算法，下面将所提算法与其他用于解决特征选择问题的4种优化算法进行对比，评价标准与前文2种对比算法相同。基于所提算法与其他4种优化算法在分类精度和选择特征个数上的测试结果如图2、3所示，结果表明：所提算法使分类精度平均提高了10.3%，平均减少了2.7个特征。因此，所提算法在特征选择中的分类精度与选择特征个数上优于其他优化算法；基于所提算法与其他4种优化算法的适应度（平均值、标准差）值测试结果如图4、5所示，结果表明：所提算法的适应度平均改善了46.1%，在特征选择中表现较好，SCA在适应度的标准差中具有相对稳定的性能。综合来看，在特征选择中，所提算法具有更好、更稳定的适应度；基于所提算法与其他4种优化算法的平均运行时间如图6所示。数据表明：SCA时间最短，其次是HSOA，所提算法时间与其他算法无明显特点，仍需改进。因此综上所述，与其他4种优化算法相比，所提算法在特征选择中整体性良好，具有一定优势。

图2 所提算法与其他算法的分类精度比较

图3 所提算法与其他算法在选择特征数平均值的比较

图4 所提算法与其他算法的适应度平均值比较

图5 所提算法与其他算法的适应度标准差比较

图6 所提算法与其他算法的平均运行时间比较

5 结论

针对封装式方法下的特征选择问题，本文提出了一种基于模拟退火与斑点鬣狗优化的混合算法，通过在UCI存储库中的8个标准数据集上的分类实验来评估所提算法的性能，并与SHO、ACO、WOASA、HSOA、SCA算法进行对比。实验结果表明：

1) 在8个数据集中，从分类精度与选择特征个数上来看，所提出的SASHO算法能够显著提高分类精度，同时减少选择特征的数目，优于其他算法的特征选择能力。

2) 与其他算法在适应度的平均值与标准差上相比，SASHO算法具有有效的搜索空间，避免局部最优，同时表现出良好的稳定性。

3) 在平均运行时间上，SASHO算法虽然无明显改善，但在分类精度与特征选择个数方面仍具有较大优势。

因此，混合算法(SASHO)在空间搜索和特征属性选择方面具有出色表现。