基于重复度分析的森林优化特征选择算法

冀若含，董红斌

（哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001）

大数据和物联网技术的发展，使得越来越多 的数据被采集、存储和分析[1]。目前的数据不仅数量巨大，而且维度高，但并不是全部的数据都是有用的。数据的规模在变大的同时也包含了大量的冗余、不相关或者弱相关特征，这些特征与数据的主要基本结构没有关联，或者只有松散的弱关联。如果特征不进行处理就输入机器学习模型，不仅会增大模型的时间开销，而且干扰特征的存在还会降低算法的预测精度。通过对数据原特征空间分析，过滤掉冗余和不相关特征，保留相关特征，这就是特征选择。特征选择以提高模型精度和减少模型运算时间为目标，以保持模型原始精度为底线，选择极小特征子集。此外，大量的特征也会导致模型过拟合，在项目实施时模型性能不佳，特征选择可以预防这种现象的发生，使模型更加适应现实环境[2]。

特征选择是一个复杂的组合优化问题，这是因为随着特征维度的增加特征搜索空间将会呈指数型增加，一个具有n维特征的数据集，特征子集(不包含空集)的总数为2n-1[3]。因此采用完全搜索策略的计算成本巨大。近几年基于演化算法的启发式搜索策略常用于特征选择领域，因为其不需要有关领域专业知识、强大寻优能力和较为理想的时间成本。森林优化算法(forest optimization algorithm，FOA)[4]，是一种基于森林中树木播种的演化算法。Ghaemi 等[5]于2016 年，通过改变局部播种和全局播种两个算子，使FOA 适应于离散向量，并应用于特征选择，验证了 FSFOA (feature selection using forest optimization algorithm)在特征选择领域的可行性。对比粒子群算法(particle swarm optimization,PSO)和蚁群算法(ant colony optimization,ACO)，FSFOA 更容易实现，而且需要更少的时间代价就能得出使学习模型性能更好的特征子集。虽然FSFOA 已经在低、中、高3 个特征维度的数据集中进行了实验取得了较好的效果，但仍然存在以下问题：

1）FSFOA 在初始化森林的阶段采用随机初始化的策略进行盲目特征选择，特征被选中的概率均为1/n，n为总特征数[6]。因此森林树木初始质量较差，森林收敛速度较慢。而且对高维数据集的适应度较差。

2）FSFOA 未对候选种群的数量进行限制。随着演化过程的进行，候选种群的数量将过于庞大，算法空间成本过高。

3）随着演化的进行种群趋于收敛，森林中会出现大量相同的树木(特征选择向量相同的树木)。重复树木的适应度计算增加了时间成本，降低了算法的搜索能力。

4）实验表明，在仅考虑准确率作为适应度的情况下，会出现多个适应度相同的最优树。而且只考虑分类准确率为优化目标过于单一，不利于提高维度缩减率。

因此，为了提升森林整体的收敛速度、增强森林整体的空间搜索寻优能力，本文提出了基于重复度分析的森林优化特征选择算法(feature selection using forest optimization algorithm based on duplication analysis，DAFSFOA) 。

近年来，信息论与演化算法相结合的研究工作越来越多[7-10]，信息增益(information gain，IG) 可用于初步衡量特征的重要性。通过应用IG，可以提高森林树木的初始质量，过滤掉与分类毫无关系的特征，有利于加速森林整体的演化进程。Xu 等[11]于2021 年提出重复度分析的概念，旨在增加种群多样性，调高算法的全局寻优能力和减少重复计算。受以上内容启发，本文设计了基于信息增益和特征维度的自适应森林初始化策略，加快了森林的收敛速度，且适应于不同类型的数据。同时加入了森林树木分析去重机制、森林种群重启机制、候选森林规模限制和候选最优树生成策略，降低了算法的空间和时间成本，并且增强了算法的空间搜索能力。最后改进适应度函数，提升了算法对于高维数据集的寻优能力。在11 个数据集上测试DAFSFOA 的性能，对比经典的和近几年提出的特征选择算法，DAFSFOA 在分类准确率和特征维度缩减率上都具有很强的竞争力，同时对高维小样本数据也有很好的适应力。

1 相关工作

特征选择作为一种数据降维手段，能在不改变原始特征物理信息的情况下选择尽量小的特征子集。特征选择常作为数据处理工具，去除干扰特征和选择核心特征。因此许多学者已经对特征选择进行了系统的研究。通常将特征选择方法分为3 种类型:过滤式 (filter)、包裹式 (wrapper)和嵌入式 (embedding)[1]。对于过滤式特征选择算法，特征子集的选择与机器学习模型之间没有交互，模型的输出结果不会影响特征子集的选择。在包裹式特征选择算法中，模型的结果例如分类准确率，会直接作为特征子集的适应度函数，评价特征子集的优劣。嵌入式特征选择算法将分类算法或者回归算法的学习过程与特征选择过程合并同时进行，算法学习过程结束的同时产生特征选择结果。包裹式方法往往能取得比过滤式方法更好的效果，但同时也需要付出更大的计算代价。而过滤式方法的计算成本较低，而且通用性更好[12]。随着研究的进展，也产生了越来越多的混合式特征选择算法(hybrid method)，混合式特征选择方式结合了过滤式和包裹式方法的优点。

特征子集搜索技术是特征选择的核心，搜索技术的选择往往会直接影响特征选择算法的效果。子集搜索技术一般分为3 种：完全搜索、启发式搜索、基于演化算法的搜索[13]。完全搜索能够保证寻找到最优特征子集，但是特征选择是个 NP难问题，当面对高维数据时，完全搜索需要的时间代价过大，因此特征选择中较少采用完全搜索策略[14]。启发式搜索常用于特征选择，例如贪婪搜索。贪婪搜索的典型例子是：序列正向选择(sequential forward selection,SFS)[15]、序列反向选择(sequential backward selection,SBS)[16]。但是这两种搜索方式都存在明显的局限，都存在“嵌套效应”，缺少搜索的灵活性，之前添加或者去除的特征，在之后步骤中不能从特征子集中去除或者重新加入特征子集。为了克服这个问题，提出了加L减R法[17]、顺序反向浮动选择(sequential backward floating selection,SBFS)[18]和顺序正向浮动选择(sequential forward floating selection,SFFS)[18]等。加L减R法通过运行L次SFS 算法，R次SBS来达到平衡，但是很难确定L和R的值。演化算法的灵感来源于自然演化中的生物智慧、群体智慧和群体行为，其具有强大的搜索能力。近年来，以粒子群算法(PSO)、遗传算法(genetic algorithm,GA)、蚁群算法(ACO)等经典演化算法为基础的变种算法广泛应用于超参数优化[19]、特征选择[20]和路径规划[21]等领域。同时也出现了大量新型演化算法，如模拟座头鲸气泡网狩猎的鲸鱼算法(whale optimization algorithm,WOA)[22]、受森林中树木播种启发的森林优化算法(FOA)[4]。虽然演化算法的应用领域广泛，但要应用于特征选择也必须进行一系列的改进，形成针对特征选择领域的演化算法。Dong 等[23]结合信息论知识和粒子群算法，并舍弃粒子群更新公式中的速度参数，提出了一种混合特征选择方法：基于PSO 的双全局最优的高维特征选择方法。Agrawal 等[24]结合量子计算的概念提出了基于量子的鲸鱼优化算法(quantum based whale optimization algorithm,QWOA)进行特征选择。该方法利用种群个体的量子位表示法和量子旋转门算子，提高了经典WOA 的特征空间探索和利用能力，全局寻优能力更强、种群多样性更高。Li 等[25]提出了一种改进的黏性二进制粒子群算法(improved binary particle swarm optimization,ISBPSO)。ISBPSO 采用了基于互信息(MI)种群初始化策略获得优质初始种群，并将遗传算法作为PSO 的子算子用于交换种群信息避免种群过早收敛，提高了算法跳出局部最优的能力。

本文提出的DAFSFOA 主要目标为增加森林中树木的多样性，扩大森林对特征空间的覆盖，同时降低算法的计算成本。为达到以上目的，DAFSFOA 添加了基于信息增益的自适应森林初始化策略、森林去重和重启机制、候选森林规模限制策略、候选最优树生成策略，并改进了适应度函数。

2 森林优化特征选择算法

FSFOA 是在FOA 的基础上改进而来的，可以看作二进制离散向量的森林优化算法。FOA 的灵感来自于森林中树木种群的演化过程。在森林中，参天大树往往在水源和阳光充足的地方。树木种子寻找最佳栖息地的过程，也正是一个搜索寻优的过程。通过对这一过程的建模，最终Ghaemi[4]等于2014 年提出了FOA。之后，Ghaemi等[5]提出了针对离散空间搜索的FOA，并应于特征选择。FSFOA 主要由初始化森林、局部播种、森林规模限制候选森林生成、全局播种、更新全局最优树五部分组成。FSFOA 采用Xi=(xi0,xi1,xi2,···,xiD)，表示森林中索引值为i的树木。其中xi0≥0，xi,j＞0∈{1,0}，D表示数据集的维度。树木向量的第0 维表示树木的年龄，第1～D维表示特征选择情况，0 代表未选中该特征，1 代表选中。FSFOA 的主要流程如图1 所示。

图1 FSFOA 流程Fig.1 Flowchart of FSFOA

2.1 初始化森林

在FSFOA 中，森林中每一棵树木都被表示为如图2 所示的长度为D+1的离散向量。与常规特征选择算法中选择结果表示方法不同的是，FSFOA 中添加了年龄Aage这一维。树木的年龄这一重要的参数在后续局部播种和森林规模限制阶段有重要的作用。初始化森林就是生成一定数目的初始树木向量，树木年龄全部设置为0，其余位置随机初始化为0 或1。因此，在初始化森林的阶段每个特征被选中和被删除的概率相同。对于中低维数据集，这种随机的初始化策略s 缺点并不明显，但对于高维数据集，完全随机初始化森林将给后续种群寻优带来极大困难。

图2 Nlsc=2 时局部播种实例Fig.2 Example of local seeding at Nlsc=2

2.2 局部播种

局部播种代表了FSFOA 对特征空间的深度搜索，模拟了树木在自身附近播种的行为。局部播种算子只针对Aage=0 的树木。Nlsc参数代表了Aage=0 的父代树木可产生的子树数目。进行局部播种的树木随机选中Nlsc个不同的位置进行单点翻转突变，也即对选中的位置进行取反操作，选中位置为0 的置为1，为1 的置为0。每进行1 次单点取反将产生1 棵子树，并重置父树继续下次单点突变。Nlsc个突变位置将产生Nlsc棵子树，子树Aage=0，森林中其他所有树木的Aage增加1。具体过程如图2 所示。图2 中代表了选中的突变位置。

2.3 森林规模限制

随着演化的进行，森林中树木会越来越多。因此需要对森林中的总容量进行限制，森林的容量为Sarea。Aage＞Tlife(年龄限制)的树木将会老死，被森林淘汰，移除到候选森林。如果森林中树木总数仍大于Sarea，FSFOA 将会根据适应度值对森林中的树木进行降序排序，排名超过Sarea的树木也将移除到候选森林。FSFOA 中的适应度值为分类器的分类准确率，也即树木选择的特征子集的分类能力。

2.4 全局播种

全局播种代表了FSFOA 对特征空间的广度搜索。对比局部播种，全局播种产生的子树与父树的差距更大。全局播种操作可在森林陷入局部最优的时候，使森林跳出局部最优。候选森林中的树木以Ptransfer的概率被选中进行全局播种。1 棵父树只产生1 棵子树，父树随机选择Ngsc个位置进行多点取反，并置Aage=0，加入森林中参与演化，具体如图3 所示。

图3 Ngsc=4 时全局播种实例Fig.3 Example of global seeding at Ngsc=4

2.5 更新最优树

根据适应度值对森林中的树木进行降序排列，适应度最高的树被选为最优树，并将该树的Aage字段置为0，参与后续的森林演化。将最优树的Aage每次都重置为0，也即优秀的树木不会被淘汰，保证了森林中优秀的树木能够一直参与森林的演化。

3 DAFSFOA 算法

针对引言中提出的FSFOA 的缺陷，以提升森林的收敛速度和算法的搜索能力为目标，本文提出了DAFSFOA 算法。为了加快森林收敛速度，DAFSFOA 引入了信息增益对特征进行初筛，提升了初始种群的质量，而且针对不同维度的数据集采用了不同的初始化策略缩小了高维数据集的搜索空间。同时，采用森林树木重复度分析机制和候选森林规模限制策略降低了算法的时间与空间成本。为了提升算法的搜索能力，DAFSFOA设计了森林重启机制，防止森林过早收敛陷入局部最优，同时提出了候选最优解生成策略进一步提升树木多样性，并且改进了适应度函数，大大提高了算法的寻优能力。

3.1 基于信息增益的自适应初始化策略

近年来，特征选择领域常用信息论知识对特征进行初步筛选。信息增益(IG)能够反应特征与分类标签的相关度。信息增益越大，该特征对于分类的帮助越大。信息增益的定义如式(1)～(4)所示：

H(X)为随机变量的熵，H(Y|X)为条件熵，两者之差就是信息增益。但信息增益并不能反应特征与特征之间的关系，因此不能全凭信息增益选择特征。本文提出增1 减1 法来初始化森林树木。在计算数据集中每个特征的IG 后，对森林进行随机初始化，对初始化后的初代森林中前50%的树木，添加信息增益最大的特征,并删除信息增益最小的特征。并且对于高纬度小样本的数据集采用不同的初始化策略。当D(特征维度)≫N(样本数量)时，无法覆盖整个特征空间，因为样本数量太少此时在初始化森林时选择较少的特征更利于后续收敛。当D＞3N时，初始森林中的树木选择的特征数目应小于等于3N。

3.2 候选森林规模的限制策略

FSFOA 中随着森林演化的进行，森林中越来越多的树被转移到候选森林。候选森林的规模将越来越大，但保存巨大的候选森林会带来较大的内存开销，而且劣质树木对于森林的寻优帮助不大。较大的候选森林也会导致在全局播种阶段有过多的新生树木加入到森林中，也间接加大了算法的计算消耗。因此，在DAFSFOA 中的森林规模限制阶段，本文对候选森林同样进行规模限制。因为候选森林均为较劣质的树木，所以无需在计算适应度进行排序筛选。本文将候选森林的规模限制设为森林规模限制的两倍，即2Sarea。当候选森林中树木数量超过限制时，随机删除树木直到树木数量等于2Sarea。

3.3 重复度分析及森林重启机制

随着演化的进行森林逐渐收敛，森林中产生大量Aage不同，但是所选特征相同的树木。大量重复的树木的存在对森林演化寻优并无帮助，反而因此消耗了大量的计算资源。因此，我们需要对森林中的树木进行重复度分析，每种树木只保留一个个体，极大地提高了森林中树木的多样性，有利于算法的全局寻优。如果经过去重操作森林中剩余的树的数量只有森林初始种群数量Sinitial的一半，此时认为森林种群的多样性过低不利于后续搜索寻优，因此采用森林重启机制，采用初始化森林的方法补充森林中的树木，使森林树木的数量重新达到Sinitial。

3.4 候选最优树生成策略

FSFOA 每轮演化只产生1 棵最优树，忽略了森林中树木的统计信息。为了充分利用森林演化过程中的统计信息，在DAFSFOA 中提出候选最优树概念，即统计目前森林中出现过的全部特征，并根据统计结果生成候选最优树，将候选最优树的年龄置为0，并加入森林参与后续的森林演化。候选最优树的加入不仅增加了森林树木多样性，而且充分利用了森林演化过程中的统计信息。

3.5 改进的适应度函数

适应度值表现了算法所选择的特征子集的好坏。FSFOA 中的适应度函数设计考虑较为片面，仅考虑分类准确率(AC)，AC 的定义如式(5)所示：

式中：Nacc为分类正确的实例数；M为实例总数。在只考虑AC 的情况下实验结果中出现了很多适应度值相同的树，不利于最优树的挑选，而且不利于森林朝着增大DR 的方向演化，DR 为维度缩减率，如式(6)所示：

式中：FnotSelected为对应树未选择的特征数；Fall为特征总数。式(7)为DAFSFOA中采用的适应度函数，为AC 和DR 的加权，避免了不同树适应度值相同的情况。α+β=1而 且 α ≫β，因为特征选择算法的主要目的为提高分类准确率。

3.6 DAFSFOA 流程图

图4 为DAFSFOA 的算法流程图。DAFSFOA的演化终止条件为迭代50 次，当演化次数超过限制，则结束算法，输出森林中目前的最优树也即最优特征子集。

图4 DAFSFOA 流程图Fig.4 Flowchart of DAFSFOA

4 实验和结果分析

实验中代码运行环境为python3.8。硬件环境为CPU Ryzen7 5800H,16 GB 内存。

4.1 数据集及对比算法

FSFOA 中使用了10 个UCI 数据集和1 个高维微阵列数据集。数据集的维度和实例数如表1所示。

表1 数据集简介及Nlsc 和 NgscTable 1 Dataset introduction and corresponding Nlsc and Ngsc values

为了对比显示DAFSFOA 算法的性能，本文采用与FSFOA 相同的11 个数据集。除了与FSFOA 进行实验对比，本文也与几种经典的特征选择算法和近年提出的新算法进行了对比。表2 列出了文中对比算法的简介。

表2 文中对比算法Table 2 Comparative algorithms in the paper

4.2 具体参数设置

为了突出DAFSFOA 对于FSFOA 改进的有效性。除了改进部分，其他参数保持与FSFOA 一致。Tlife设为15，Ptransfer设为0.05，Sarea设为50，以上3 个参数与FSFOA 的设置相同，Sinitial在FSFOA 中未提及具体值，本文中设为50[5]。Nlsc和Ngsc也保持和FSFOA 相同。FSFOA 中指出Nlsc和Ngsc与数据集维度有关，同时实验得出当Nlsc=D/5,Ngsc=D/2 时，能达到计算成本和寻优效果的最佳平衡[5]。参数设置具体如表1 所示。

4.3 分类器和验证方式

本文采用KNN、rbf-svm、C4.5 三种分类器计算AC，其中KNN 采用了n=1、n=3 和n=5 这3 种不同的参数。C4.5 采用J48 参数。同时采用70%～30%的数据集划分、10 折交叉验证、2 折交叉验证这3 种不同的数据集划分方式。实验中采用相同的实验条件计算得出森林中每棵树的AC 和DR，得出最优树，AC 和DR 的计算公式如式(5)、(6)所示。

4.4 实验结果分析

DAFSFOA 与其他算法对比的结果如表3 所示。对于最高正确率和最高维度缩减率均加粗处理。在Dermatology、Sonar、Cleveland、Heart-statlog、Hepatitis、SRBCT、Segmentation 这7 个数据集上，采用不同的数据集划分方式和分类器，DAFSFOA 都取得最高的准确率。

表3 DAFSFOA 与对比算法的实验结果Table 3 Experimental results of DAFSFOA and comparison algorithms

续表 3

DAFSFOA 在高维数据集SRBCT 上算法性能有巨大的提升，对比FSFOA，其准确率提升了5.26%，而且维度缩减率的提升更为巨大。FSFOA 在对应数据集上的准确率高达94.73%，但是维度缩减率只有49.06%，而SRBCT 数据集的特征维度有2 308 维，FSFOA 得到的最优树仍然包含了大量特征。而DAFSFOA 得到的最优树维度缩减率高达92.33%。对比FSFOA，DAFSFOA 能够更好地处理高维特征选择问题，这得益于DAFSFOA 特殊设计的高维数据集初始化策略。对于同样是高维数据集的Sonar，DAFSFOA 的表现也要远远好于FSFOA，平均AC 为93.57%，最高AC 为98.33%，而FSFOA 的平均AC 为80.24%，其最高AC 为86.98%，也低于DAFSFOA 的平均值。当采用rbf-svm 分类器并采用2-fold 验证的时候，DAFSFOA 的准确率比FSFOA 高了22%，同时维度缩减率提高了8%。同时，对比2020 年提出的NFSFOA，DAFSFOA 也具有明显的优势，在同样条件下，DAFSFOA 得出的最优特征子集分类准确率最高达98.33%，而相应的NFSFOA 只有74.6%，但NFSFOA 产生的最优树的维度缩减率只高出DAFSFOA 算法0.09%，DAFSFOA 只牺牲了0.09%的DR，就达到了98.33%的准确率，可见DAFSFOA 的性能优势。在维度缩减率方面，DAFSFOA 并不像在分类正确率上表现得如此出众，但对于大部分数据集DAFSFOA 都优于FSFOA。对于一部分数据集，虽然DAFSFOA 没有取得最高的维度缩减率，但在分类准确率上仍有较大优势。例如，NSM 算法在Ionosphere 数据集上，采用10 折交叉验证和KNN(k=1)分类器取得了88.23%的维度缩减率，高于DAFSFOA。但是NSM 算法的分类准确率比DAFSFOA 低了3.2%。

在大部分数据集中，DAFSFOA 的维度缩减率排行第二，并且与第一相差很小，但分类准确率远超其他算法。通过DAFSFOA 在不同数据集的实验，可以得出DAFSFOA 在AC 和DR 上对比原始的FSFOA，均有巨大提升，而且在大部分数据集中的表现也超过了其他经典的算法和近年来提出的新型特征选择算法。

5 结束语

本文通过对FSFOA 的深入分析，提出了FSFOA 的4 处不足。以提高森林中个体的多样性、降低树木重复度和提高算法的全局寻优能力为目的，本文对FSFOA 算法提出了5 点改进意见，即基于信息增益的自适应初始化策略、候选森林规模限制策略、森林重复度分析及重启机制、候选最优树生成策略、结合维度缩减率的适应度函数，最终形成了基于重复度分析的森林优化特征选择算法。并通过实验在不同维度的数据集上验证了DAFSFOA 改进的有效性。DAFSFOA 在AC 和DR 两个方面的表现普遍超过了FSFOA，尤其是对于高维数据集，DAFSFOA 的表现优于FSFOA。