软件学报  2020, Vol. 31 Issue (5): 1511-1524   PDF    
森林优化特征选择算法的增强与扩展
刘兆赓1,4 , 李占山1,2,4 , 王丽3 , 王涛3 , 于海鸿2,4     
1. 吉林大学 软件学院, 吉林 长春 130012;
2. 吉林大学 计算机科学与技术学院, 吉林 长春 130012;
3. 长春工业大学 计算机科学与工程学院, 吉林 长春 130012;
4. 符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012
摘要: 特征选择作为一种重要的数据预处理方法,不但能解决维数灾难问题,还能提高算法的泛化能力.各种各样的方法已被应用于解决特征选择问题,其中,基于演化计算的特征选择算法近年来获得了更多的关注并取得了一些成功.近期研究结果表明,森林优化特征选择算法具有更好的分类性能及维度缩减能力.然而,初始化阶段的随机性、全局播种阶段的人为参数设定,影响了该算法的准确率和维度缩减能力;同时,算法本身存在着高维数据处理能力不足的本质缺陷.从信息增益率的角度给出了一种初始化策略,在全局播种阶段,借用模拟退火控温函数的思想自动生成参数,并结合维度缩减率给出了适应度函数;同时,针对形成的优质森林采取贪心算法,形成一种特征选择算法EFSFOA(enhanced feature selection using forest optimization algorithm).此外,在面对高维数据的处理时,采用集成特征选择的方案形成了一个适用于EFSFOA的集成特征选择框架,使其能够有效处理高维数据特征选择问题.通过设计对比实验,验证了EFSFOA与FSFOA相比在分类准确率和维度缩减率上均有明显的提高,高维数据处理能力更是提高到了100 000维.将EFSFOA与近年来提出的比较高效的基于演化计算的特征选择方法进行对比,EFSFOA仍具有很强的竞争力.
关键词: enhanced feature selection using forest optimization algorithm (EFSFOA)    高维    特征选择    演化计算    
Enhancement and Extension of Feature Selection Using Forest Optimization Algorithm
LIU Zhao-Geng1,4 , LI Zhan-Shan1,2,4 , WANG Li3 , WANG Tao3 , YU Hai-Hong2,4     
1. College of Software, Jilin University, Changchun 130012, China;
2. College of Computer Science and Technology, Jilin University, Changchun 130012, China;
3. College of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China;
4. Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012, China
Abstract: As an important data preprocessing method, feature selection can not only solve the dimensionality disaster problem, but also improve the generalization ability of algorithms. A variety of methods have been applied to solve feature selection problems, where evolutionary computation techniques have recently gained much attention and shown some success. Recent study has shown that feature selection using forest optimization algorithm has better classification performance and dimensional reduction ability. However, the randomness of initialization phase and the artificial parameter setting of global seeding phase affect the accuracy and the dimension reduction ability of the algorithm. At the same time, the algorithm itself has the essential defect of insufficient high-dimensional data processing capability. In this study, an initialization strategy is given from the perspective of information gain rate, parameter is automatically generated by using simulated annealing temperature control function during global seeding, a fitness function is given by combining dimension reduction rate, using greedy algorithm to select the best tree from the high-quality forest obtained, and a feature selection algorithm EFSFOA (enhanced feature selection using forest optimization algorithm) is proposed. In addition, in the face of high-dimensional data processing, ensemble feature selection scheme is used to form an ensemble feature selection framework suitable for EFSFOA, so that it can effectively deal with the problem of high-dimensional data feature selection. Through designing some contrast experiments, it is verified that EFSFOA has significantly improved classification accuracy and dimensionality reduction rate compared with FSFOA, and the high-dimensional data processing capability has been increased to 100 000 dimensions. Comparing EFSFOA with other efficient evolutionary computation for feature selection approaches which have been proposed in recent years, EFSFOA still has strong competitiveness.
Key words: enhanced feature selection using forest optimization algorithm (EFSFOA)    high-dimensional    feature selection    evolutionary computation    

特征选择是从原始特征中选择出一些最有效特征以降低数据维度的过程[1], 是模式识别中重要的数据预处理方法, 是数据发掘中频繁使用的数据处理技术, 也是提高机器学习算法性能的一个重要手段.

针对不同的选择策略, 可以将特征选择方法大致分为包裹式、过滤式和嵌入式3种.

● 包裹式方法:依赖于预定义的学习算法来评估所选特征的质量.根据给定的一个具体学习算法, 典型的包裹式方法将执行两个步骤:(1)搜索特征子集; (2)评估选择的特征.重复步骤(1)和步骤(2), 直到满足停止条件或获得了所需的学习表现后结束.由于包裹式方法在评估选择的特征时能够针对不同问题选择不同的评价方法, 因此目前这类方法的研究更多关注于评价方法的使用和改进上面, 如基于K近邻的包裹式方法[2]、基于支持向量机的包裹式方法[3]、基于决策树的包裹式方法[4]等.

● 过滤式方法:不依赖于任何学习算法, 仅依靠对数据的某些特征进行评估, 以评估特征的重要性.典型的过滤式方法由两个步骤组成:第1步, 根据某些特征评估标准, 将特征重要性进行特征评分来排序; 第2步, 过滤重要性低的特征, 保留重要性评价高的特征.一些代表性的标准包括特征相关性标准[5]、互信息标准[6, 7]、特征判别能力标准[8]、保存数据流形结构能力标准[9, 10]以及重建原始数据能力标准[11, 12]等.过滤式方法通常比包裹式方法更高效, 但是由于缺乏具体的学习算法指导特征选择阶段, 所选特征可能并不是最适合目标学习算法的.

● 嵌入式方法:提供了包裹式方法和过滤式方法之间的折衷解决方案.通过将特征选择与学习模型相结合的方法, 从而继承了包裹式方法和过滤式方法的优点:(1)与学习算法的交互; (2)比包裹式方法更高效.一种典型的嵌入式方法就是LARS[13].

特征选择困难的主要原因是搜索空间随特征数呈指数增长[5], 因此, 如何采用高效的搜索策略进行搜索, 往往是特征选择问题能否有效求解的关键.演化计算技术由于具有良好的全局搜索能力, 近年来在特征选择领域获得了越来越多的关注[14].与传统的搜索方法相比, 演化计算方法的明显优势在于其通常不需要领域知识和对搜索空间做任何的假设(例如是线性或非线性可分的), 并且由于它基于种群机制的特点, 能够在一次运行中产生多种结果, 使其更适合用来进行多目标特征选择以确保在特征数量和分类性能中取得平衡.一些较新的基于演化计算的特征选择算法包括Zhu等人将遗传算法和局部搜索方法结合起来提出的FS-NEIR[15]、Xue等人基于粒子群算法提出的PSO(4-2)[16]、Tabakhi等人基于蚁群算法提出的无监督特征选择算法UFSACO[17]、Zhang等人基于萤火虫算法提出的Rc-BBFA[18]等.Ghaemi等人提出了森林优化特征选择算法(feature selection using forest optimization algorithm, 简称FSFOA)[19], FSFOA相对于其他算法而言, 仅需较小的计算代价就能达到较高的分类准确率, 并保证良好的泛化性能[20].但是FSFOA仍有一些需要改进之处表现在了如下几个方面.

● 第一, 初始化森林时FSFOA单纯采用随机的方式从m维的特征中选取特征, 而这种方式具有一定的盲目性[20].对于FSFOA来说, 在局部播种阶段寻找最优的特征子集围绕初始化展开, 全局播种更依赖于局部播种的结果, 因此初始化方案的好坏, 不仅直接影响后续的搜索能否选到分类准确率更高的解, 也间接影响维度缩减率的高低.

● 第二, FSFOA在全局播种阶段的参数GSC(global seeding change)设置上类似该算法局部播种阶段的参数LSC(local seeding change)的设置, 均由实验人员根据经验设定, 这样的固定参数设定限制了全局播种辅助局部播种寻找全局最优解的能力, 并没有发挥出全局播种策略的最大优势.

● 第三, 在最优树选择方面, FSFOA单纯从已知的优质森林中选择其中一棵树作为最优的特征子集树, 极大地浪费了经过若干轮选出的优质森林中的其他次最优树.

● 第四, FSFOA存在着高维数据处理能力不足的本质缺陷.

因此, 森林优化特征选择算法仍存在较多可以完善之处.参考最近的相关研究[21-23]可以看出, 结合信息增益方法对最优特征子集的选取具有良好的指导作用.模拟退火算法思想最早是由Metropolis等人于1953年提出的, 1983年, Kirkpatric等人成功地将退火思想引入组合优化领域[24].模拟退火算法中模拟了冶金行业的操作过程, 通过设计递减的温度控制函数, 使粒子由高温无序状态最终趋于低温时的基态.基于以上思想, 本文采用一种新的初始化策略和GSC参数选择策略, 同时, 在算法选优阶段引入贪心算法来改进FSFOA.最后, 针对FSFOA高维数据处理能力不足的问题, 我们采用集成特征选择处理的思路对高维数据集进行处理, 很好地弥补了算法存在的缺陷.为了便于描述, 我们将改进后的FSFOA记为EFSFOA(enhanced feature selection using forest optimization algorithm).最后, 我们选择了15个UCI[25]中的数据集, 将EFSFOA与FSFOA和近几年提出的其他比较高效的基于演化计算的特征选择算法进行了对比实验, 通过实验得出, EFSFOA在分类性能和泛化能力上均具有不错的表现.

1 FSFOA概述

FSFOA是Ghaemi等人基于森林优化算法(forest optimization algorithm, 简称FOA)[26]提出的一种新型的特征选择算法, 并将此算法在离散型数据集上进行特征选择实验, 实验取得了良好的效果.

FSFOA将每一个解集(即特征子集)表示为一棵树的形式, 树的长度与特征的长度相等, 每个特征在树中用“0”或“1”的形式记录:“0”表示不选择该特征参与后续的学习任务, “1”表示选择该特征用于后续的学习.

FSFOA包含森林初始化、局部播种、形成候选森林、全局播种、更新优质树、挑选最优树等6个阶段, 其中, 局部播种、形成候选森林、全局播种和更新优质树为主要迭代对象.通过不断的迭代, 产生新树更新森林, 最终挑选森林中的最优树作为最优特征子集.

● 初始化森林:产生N棵特征随机的树并形成森林.每棵树通过0/1字符串记录所选择的对应的特征子集; 同时, 通过一个Age属性记录树的“年龄”, 每棵新生成的树Age均设置为0.这里, 初始化过程单纯采用随机的方式来完成, 具有很大的盲目性.对于FSFOA来说, 在局部播种阶段寻找最优的特征子集围绕初始化展开, 全局播种阶段更依赖于局部播种的结果, 因此, 针对每棵树的初始选取是十分关键的.初始化方案的好坏, 不仅直接影响算法能否通过后续的搜索选到分类准确率更高的解, 也间接影响算法维度缩减率的高低.在后文实验结果对比分析中, 我们会结合具体的对比实验结果做进一步说明.

● 局部播种:依据LSC参数对Age为0的树进行局部播种生成新树, 即对Age为0的树随机选择“某一个”特征, 并将该特征对应的变量值从1改为0, 反之亦然.具体过程如图 1所示, 将新生成的树Age设置为0并将其添加到森林中, 将森林中剩余树的Age加1.

Fig. 1 Local seeding with LSC=2 图 1 局部播种(LSC=2)

● 形成候选森林:为限制局部播种后森林的规模, FSFOA中引入两个新的参数life timearea limit来控制森林中树的数量.这一过程中, 先将森林中Age大于年龄上限参数life time的树放入候选森林, 然后如果森林中剩余树的数量仍然超出区域上限参数area limit, 则根据森林中树的适应度值从小到大依次将多余的树放入候选森林, 直到森林中树的数量等于area limit为止.

● 全局播种:依据设定的transfer rate参数从候选森林中随机选择若干棵树, 每棵树按GSC参数随机选取一些特征进行全局播种生成新树, 同时, 这些特征对应的变量值从1改为0;反之亦然.具体过程如图 2所示, 全局播种后, 此时新生成的树Age与生成它的树Age相同, 将它们加入候选森林, 然后在候选森林中选取对应特征子集的分类准确率最高的树, 将其加入到森林中; 同时, Age置为0.全局播种这样通过人为给定参数的播种方式过于盲目, 不同于局部播种的LSC参数, 更多影响的是关于问题求解时间的大小, 并不影响本质策略——无论LSC的数值如何选取, 改变的特征都是1个, 人为给定的方式往往是通过该参数控制算法搜索时间.而GSC的作用更多的是通过该参数辅助局部播种寻求最优解, 寄希望于通过改变数个特征(个数为GSC的取值)来进行一次扩展的全局搜索, 进而搜索到一个局部最优的解.因此, 该参数的好坏对于全局播种阶段来说是至关重要的.

Fig. 2 Global seeding with GSC=3 图 2 全局播种(GSC=3)

● 更新阶段:比较经过全局播种选出的树的准确率, 把准确率最大的树作为优质树, 并将其Age置0, 重新放入森林中.

● 挑选最优树:在迭代结束后的森林中, 依据每棵树的准确率, 选择准确率最大的一棵作为最优树, 即全局最优解.这种择优方式在一定程度上造成了森林中其他树的浪费, 因为相对于所选的最优树来说, 它们虽然不是最优的, 不过却能在森林中存活到最后, 足以表明它们所选择的特征相对来说也是十分良好的.因此, 并不能单纯地认为现有森林中的最优树相比于取森林中全部树的特征交集得来的树更优秀.

2 EFSFOA

前文概述了FSFOA, 并分析了其不足之处.本节针对以上不足提出3点改进方案, 同时考虑文献[19]中指出的FSFOA对高维数据集的处理需要完善, 且其适应度函数需要综合维度缩减率进行优化等方面的内容.我们给出了最新的完善方案:更新、更高效的特征选择选择算法EFSFOA.通过对比实验表明, EFSFOA不仅在低维数据集的处理上比FSFOA有了更好的表现力, 尤其在高维数据集的处理上, 很好地解决了FSFOA的问题.

2.1 初始森林的生成形式

针对FSFOA随机生成的初始化森林可能出现不利于后续搜索的局面, 我们结合信息论中的理论, 提出一种结合了信息增益率的启发式初始化策略.信息增益率IGR(information gain ratio)的计算公式由公式(1)给出.

$\left. {\begin{array}{*{20}{l}} {P(X = {x_i}) = {p_i}, i = 1, 2, ..., m} \\ {H(c) = - \sum\limits_{i = 1}^n {p({c_i}) \cdot {{\log }_2}p({c_i})} } \\ {H(c|X) = - \sum\limits_{i = 1}^m {p(c, X = {x_i}){{\log }_2}p(c|X = {x_i})} } \\ {IG(X) = H(c) - H(c|X)} \\ {IGR(X) = IG(X)/H(X)} \end{array}} \right\}$ (1)

通过采用这种策略, 保证了初始化森林的优良性.如果把每个特征比喻成一个基因, 把森林的局部播种、全局播种看成树的繁衍行为, 那么通过启发后的初始森林将确保具备足够的优秀基因(即最利于进行分类的特征), 为后代的生长带来更大的优势:即后续搜索将依大概率趋于全局最优.但如果全部的树都具有该基因, 可能导致该基因的过于强大而错失了基因多样性(算法过多的依赖某一特征展开搜索).而众所周知, 多样性对于演化算法寻求最优解往往起到关键性的作用.因此, 我们的初始化策略在原有初始化策略的基础上, 对随机生成的N棵树中的N/2棵树启发的赋予依据信息增益率选出的最优特征(如果原来该特征标记已经为1, 则保持不变; 否则置为1).

2.2 采用模拟退火过程的自适应全局播种策略

如前文所述, FSFOA在全局播种阶段, 通过人为给定GSC参数的方式并不能充分利用全局播种辅助寻优.

● 首先, 因为全局播种策略本质上是一种全局搜索策略, 这种随机全局搜索的策略不仅搜索效率高, 而且搜索范围广, 往往很容易找到相对优秀的搜索空间.但由于GSC参数的固定, 使得这样的全局搜索固定了搜索空间的大小, 在算法找到了相对优秀的搜索空间之后, 只能依赖于局部播种策略的单点改变来使该搜索空间逐渐收敛, 使得收敛到区间最优解的难度过大.

● 其次, 由于在算法的迭代过程中, 生成的候选森林中的每棵树存在的形态并不完全一致, 有些树生成时就相对劣质, 因而会导致其在较低年龄时即被淘汰放入候选森林; 而有些树由于自身特征集合相对优秀, 使得它们可以在森林中存活相对长的时间, 直到达到年龄上限后才被放入候选森林.所以对于算法经过多轮迭代后逐步形成的候选森林而言, 在候选森林中存在的年龄较大的树比年龄较小的树更为优秀, 即它所对应的特征集合及搜索空间更趋近于最优解(局部最优或全局最优).

基于上述两点考虑, 我们受到模拟退火算法中曾使用到的固体退火原理的启发, 提出了自适应全局播种策略.在该策略中, 针对候选森林中的树, 通过其年龄生成GSC参数进行全局播种, 其表示形式如公式(2)所示.

$ G S C=T(A g e) $ (2)

类比于退火过程, 构造满足单调递减性质的函数T, 且需保证2≤T(Age)≤0.5×features.满足2≤T(Age)是为了确保全局播种不退化为局部播种, 保留其特色; 满足T(Age)≤0.5×features是为了控制特征改变的范围, 因为形式上改变50%的特征已经达到了上界.满足这类性质的函数T可以找到若干个, 我们从Age变化导致步长范围变化的考虑出发, 经过反复实验, 最终选取了如公式(3)所示的函数T.

$\left. {\begin{array}{*{20}{l}} {{T_0} = \min (2 + 2 \times life{\rm{ }}time, features \times 0.5)} \\ {T(Age) = {T_0}/(Age + 1)} \end{array}} \right\}$ (3)

通过这种自适应全局播种策略, 不仅使得解空间容易收敛到最优解, 而且充分利用了全局播种策略辅助寻优的特性.

2.3 贪心取优策略

在最优树选择上, FSFOA仅从局部的角度考虑最优树存在于不断迭代产生的优质森林中, 这样的寻优策略极大地造成了优质森林中资源的浪费, 忽略了其他若干次最优树(这里的次最优树指最后形成的优质森林中除最优树以外的所有树)所蕴含的特征.为了避免这样的资源浪费, 我们从全局出发, 合理地认为最优树并非存在于最后所生成的优质森林中, 而是应该由优质森林中的每一棵树共同作用所产生.具体取优策略如下.

EFSFOA贪心取优策略:第1步, 在优质森林中选出最优树作为1号待选最优树(选取方式与FSFOA选取最优树一致)并统计其选取的特征个数N; 第2步, 统计所有特征在优质森林中的每一棵树中出现的总频数并按从大到小的顺序排序; 第3步, 选取总频数排在前N个的特征生成2号待选最优树, 选取总频数排在前N-1个的特征生成3号待选最优树; 第4步, 比较1号待选最优树和2号待选最优树(1号和2号的维度缩减能力一致), 选择准确率较高的一棵和3号待选最优树进行比较, 再选择准确率较高的一棵作为最后的最优树, 如果准确率一致, 选择3号待选最优树作为最后的最优树(因为3号的维度缩减能力高于1号和2号).

2.4 高维数据集的处理

鉴于FSFOA需要进一步完善以达到高维数据处理的目的, 我们考虑特征选择森林适用于集成的特性, 因此尝试通过加入集成特征选择的特点来进一步完善我们的算法.综合考虑我们算法的特点和文献[27]中介绍的集成特征选择框架, 我们设计了如图 3所示的适用于EFSFOA进行高维数据处理的集成特征选择框架.

Fig. 3 Ensemble feature selection framework of EFSFOA 图 3 EFSFOA的集成特征选择框架

实际操作中, 我们首先设置一个参数sliding, 并根据sliding的大小将原始的高维数据集按照特征数量进行顺序切分, 然后将切分后的数据集同时使用EFSFOA进行并行化处理, 最后将所有的计算结果进行一次决策处理, 产生最终的计算结果.在决策处理的过程中, 我们首先从局部的角度出发, 考虑到每一部分数据集经过特征选择后的结果亦是原始问题的一个局部最优解, 因此首先对所有求得的解进行一次比较, 选取其中最优的解作为局部的最优解; 然后, 我们从全局角度进行考虑, 考虑将n个特征选择的结果进行合并, 用来产生一个全局的最优解.由于n个解中仍含有大量的特征, 并不适用于盲目的拼接后穷举搜索的策略.不过比较令人欣慰的是, 这n个解中所包含的特征是对原始特征经过sliding提取之后的进一步提取, 它们更加具有代表性.因此, 我们对这n个解中的每个特征采用类似亚线性抽样算法的方式进行特征的筛选, 来达到进一步搜索的效果.每个特征的抽样概率如公式(4)所示.

$ P({IsSelected})=C A \times f \times 100 \% $ (4)

其中, CA为每个EFSFOA结束后计算的分类准确率(具体由公式(6)给出, 关于公式(6), 会在第3.1节中进行详细说明), f为每个EFSFOA结束后计算的最优特征在该森林中出现的频率.

2.5 新的适应度函数

由于FSFOA主要面向低维数据的处理, 因此其仅使用分类准确率作为特征子集选择时的适应度函数是可以接受的.而EFSFOA不仅致力于在处理低维数据时令结果更加优秀, 而且旨在完善FSFOA在高维数据特征选择上的缺陷.鉴于Ghaemi等人已经指出了原有的适应度函数如果用在高维数据的特征选择处理上时会存在维度缩减率考虑不充分的情况, 为此, 我们提出了一个新的适应度函数, 来确保EFSFOA在处理高维数据时能够考虑维度缩减率.新的适应度函数如公式(5)所示.

$ {Fitness}({tree})=\alpha \times C A+\beta \times D R $ (5)

其中, CADR为分类准确率和维度缩减率(DR具体由公式(7)给出, 关于公式(7), 会在第3.1节中进行详细说明), αβ为调节参数.引入两个调节参数的目的是考虑到了算法的实际应用情况, 比如一些应用场景中需要把准确率放在首位, 而另一些则需要把维度缩减率放在优先考虑的位置, 因此增加αβ两个调节参数来提高算法的灵活性(在我们的实验中, 通常将αβ的关系设为α $ \gg $ β > 0的关系, 用来保证在添加维度缩减率作为考量更新机制因素的同时, 分类准确率仍然处于首要位置, 如果β$ \gg $α > 0, 将导致算法过多考虑维度缩减率, 有时会导致准确率过低, 算法失去稳定性.因此, 即使需要优先考虑维度缩减率, 也建议在α > β > 0的条件下进行调节).

从公式(5)可以看出, 新的适应度函数更为综合地考量了分类准确率和维度缩减率, 因此也能够进一步提高在低维数据处理上的性能, 所以我们在EFSFOA对低维数据的处理上也应用了该函数.后面的实验结果验证了我们的观点.

2.6 算法伪代码

为了便于对比, 将FSFOA伪代码[19]在算法1中给出, EFSFOA伪代码在算法2和算法3中给出.算法2是我们在FSFOA的基础上进行增强后得到的应对低维数据处理的方法, 其中粗体标明了改进的地方:第3*步对应我们在第2.1节中提出的新的初始化策略, 其目的是根据给定的数据集返回信息增益率最高的特征, 然后将森林中一半的树中该特征所对应的标志更新为“1”, 该过程中应用的InfoGainRatio(dataSet)函数的作用是依据公式(1)计算出具有最优信息增益率的特征; 迭代过程中的第11步和第16步中分别使用了第2.2节中介绍的GSC更新策略以及第2.5节中提出的新的适应度函数进行最优树的选取; 第4*步、第5*步对应我们在第2.3节中提出的新的取优策略, 其中, GroupSelection(forest)函数通过给定迭代后生成的优质森林, 返回我们在第2.3节中描述的1号~3号待选最优树.算法3是我们为了让EFSFOA能够处理高维数据而在算法2的基础之上所做的进一步扩展, 其主要思路如第2.4节所述.为了便于理解, 我们在此对重要步骤做进一步说明:第1*步将高维数据集按照sliding参数的大小切分成N个算法2中所述算法能够处理的低维数据集; 第2*步使用算法2中所述算法并行计算第1*步中切分后的N个数据集; 第5*步是将第2*步的计算结果合并成一个包含全部重要特征的集合; 循环阶段使用的Sample(important_features)函数是对第5*步中得到的集合模拟多次抽样, 以便找出一个更为优秀的全局最优解, 其中, 每个特征依据公式(4)所计算的特征抽样概率进行抽样; 第7*步从局部最优解和全局最优解中选择一个较为优秀的解作为算法的最终特征选择结果.

算法1. FSFOA(life time, LSC, GSC, transfer rate, area limit).

输入:life time, LSC, GSC, transfer rate, area limit.

输出:适应度最高的特征子集.

1*:初始化森林

2*:将森林中的每棵树的Age置为0

While

1:对森林中Age为0的树进行局部播种

2: for i=1: LSC do

3:   在选定的树中随机选择一个位置

4:   将选定位置为0的值变为1, 反之亦然

5: end for

6:将森林中所有树的Age加1

7:根据life timearea limit进行种群规模限制

8:对候选森林进行全局播种

9:从候选森林中选择transfer rate比例的树

10: for每棵选择的树do

11:   在选定的树中随机选取GSC个位置

12:   将对应位置为0的值变为1, 对应位置为1的值变为0

13: end for

14:更新最优树

15:根据树的适应度值进行排序

16:将适应度值最高的树的Age重置为0

End while

3*:返回适应度值最好的树并表示最终的特征子集

算法2. EFSFOA_LOW(life time, LSC, transfer rate, area limit).

输入:life time, LSC, transfer rate, area limit.

输出:适应度最高的特征子集.

1*:初始化森林

2*:将森林中的每棵树的Age置为0

3*:依据InfoGainRatio(dataSet)更新森林中一半的树

While满足执行条件 do

1:对森林中Age为0的树进行局部播种

2: for i=1: LSC do

3:   在选定的树中随机选择一个位置

4:   将选定位置为0的值变为1, 反之亦然

5: end for

6:将森林中所有树的Age加1

7:根据life timearea limit进行种群规模限制

8:对候选森林进行全局播种

9:从候选森林中选择transfer rate比例的树

10: for每棵选择的树do

11:    GSCT(Age)

12:   在选定的树中随机选取GSC个位置

13:   将对应位置为0的值变为1, 对应位置为1的值变为0

14: end for

15:更新最优树

16:根据Fitness(tree)选出适应度值最高的树

17:将适应度值最高的树的Age重置为0

End while

4*:根据GroupSelection(forest)生成1号、2号、3号待选最优树

5*:从1号、2号、3号待选最优树中找出最好的树作为最优树

6*:返回最优树并表示最终的特征子集

算法3. EFSFOA_HIGH(life time, LSC, transfer rate, area limit, sliding).

输入:life time, LSC, transfer rate, area limit, sliding.

输出:适应度最高的特征子集.

1*:根据sliding大小将高维数据集划分成N个低维数据集

2*:并行执行EFSFOA_LOW(life time, LSC, transfer rate, area limit)处理划分后的N个低维数据集

3*: results并行执行后的N个结果

4*: micro_final_result←从results中选择最好的结果

5*: important_ features←将results中的N个结果组合

6*:初始化变量macro_final_result为None

While 满足执行条件 do

1: macro_temp_final_resultSample(important_features)

2: if macro_temp_final_result优于macro_final_result

then macro_final_resultmacro_temp_final_result

End while

7*: if micro_final_result优于macro_final_result

then final_resultmicro_final_result

else final_resultmacro_final_result

8*:返回final_result作为高维数据集的最终特征选择结果

3 实验结果与分析

在本文实验中, 主要采用python3.6以及工具包scikit-learn实现代码.所有实验均在一台配置为Intel i7-7700K、16GB内存、500GB硬盘的计算机上完成.

3.1 数据集

我们在15个UCI[25]数据集上对我们提出的方法进行了对比实验(见表 1).

Table 1 Experimental dataset 表 1 实验数据集

分类准确率的具体定义如公式(6)所示.

$ C A=N C C / N A S $ (6)

其中, NCC代表正确的分类数, NAS代表数据集的实例总数.维度缩减率的定义如公式(7)所示.

$ D R=1-(N S F / N A F) $ (7)

其中, NSF代表选择的特征数, NAF代表数据集的特征总数.

3.2 参数设置

实验过程中, EFSFOA除了适应度函数中新增的参数αβ、高维数据处理中新增的参数sliding size以及无法列出的改进的自适应参数GSC外, 参数设置与FSFOA完全相同以便确保对比实验公平性.FSFOA和EFSFOA的参数设置分别由表 2表 3给出.

Table 2 Specific information of the parameters of FSFOA 表 2 FSFOA参数的具体信息

Table 3 Specific information of the parameters of EFSFOA 表 3 EFSFOA参数的具体信息

3.3 实验结果对比分析

我们在比较EFSFOA与FSFOA的同时, 也加入了近年来提出的特征选择算法进行对比.其他对比算法的具体信息由表 4给出, 实验结果由表 5给出.为了确保对比实验结果的准确性, 部分数据结果均采用了文献[19]中公开发表的实验结果.表 5中的粗体部分对应了该组实验中最佳分类准确率(CA)和维度缩减率(DR); 10-fold、2-fold、70%~30%、50%~50%分别表示10折, 2折, 70%作训练集、30%作测试集以及50%作训练集、50%作测试集这4种验证方式; 1-NN、3-NN、5-NN、SVM、DT分别表示1近邻、3近邻、5近邻、支持向量机、决策树这5种分类器.

Table 4 Brief description of the methods for comparisons 表 4 对比算法的简要描述

对比分类准确率, 通过表 5不难看出, EFSFOA在Ionosphere、Cleveland、Dermatology、Heart、Glass、LSVT、CNAE-9、SRBCT、Arcene这9个数据集上均达到了最高.EFSFOA在Wine、Sonar、Segmentation、Vehicle这4个数据集中, 在Wine的1-NN分类器上低于Rc-BBFA; 在Sonar的SVM分类器上低于HGAFS; 在Segmentation的1-NN分类器上低于Rc-BBFA; 在Vehicle的5-NN和SVM分类器上分别低于PSO(4-2)和HGAFS.以上数据集中, EFSFOA虽然不能保证分类准确率均为最高, 但是在决策树分类器上(除Segmentation外)均取得了最高的准确率.之所以会产生这种结果, 是因为决策树算法是基于信息论理论提出的, 而EFSFOA在初始化过程中则充分考虑了依据信息增益率进行有针对性的选择, 这也从侧面论证了初始化阶段对于算法的后续工作是十分重要的.

Table 5 Experimental results 表 5 实验结果

对比FSFOA, EFSFOA无论是在分类准确率还是在维度缩减率上的提高都是十分明显的.在Ionosphere的3-NN分类器上, CA值高出7%, DR值高出26%;在Cleveland的1-NN分类器上, CA值高出6%, DR值高出13%;在Sonar的5-NN分类器上, CA值高出4%, DR值高出32%;在Vehicle的SVM分类器上, CA值高出9%, DR值高出24%;在Dermatology的DT分类器上, 10-fold测试时, CA值高出3%, DR值高出52%, 70%~30%测试时, CA值高出8%, DR值高出19%.

对比最近提出的分类准确率较高的算法——Rc-BBFA(该算法最适应于1-NN分类器, 所以只选取了1-NN分类器的实验结果进行对比)可以看出, EFSFOA在大部分数据集的分类准确率上与Rc-BBFA都在伯仲之间, Rc-BBFA在Wine, Segmentation两个数据集上的分类准确率略高于EFSFOA; EFSFOA在Vehicle、LSVT两个数据集上的分类准确率稍高于Rc-BBFA.但是值得一提的是, EFSFOA在Ionosphere和Sonar上的分类准确率和维度缩减率都优于Rc-BBFA, 其中, 准确率平均高出2%以上, 维度缩减率平均高出20%以上.可见, 在这两个数据集上, EFSFOA的表现还是稍占优势的.

从实验结果可以看出, 在高维数据的处理上, EFSFOA的处理能力显然是优于FSFOA甚至是Rc-BBFA的.当Rc-BBFA处理的特征数量超过20 000时, 就无法在短时间内给出计算结果(我们设置的时间上限为24h); 而FSFOA这个数量仅为10 000;但EFSFOA通过采用集成特征选择的方式对高维数据进行处理, 使得特征数量即使达到100 000时仍能给出令人满意的解.

EFSFOA相对于FSFOA的几点改进都是围绕提高分类准确率进行优化的, 因此带来CA值上的提高是符合预先设想的, 令人比较惊喜的是EFSFOA带来的在DR值上的极大改进(可以看出, FSFOA的维度缩减率效果并不是十分优秀, 甚至在很多时候普遍弱于其他分类器).会造成这种结果的原因除了EFSFOA在最后寻优阶段通过进一步贪心获取尽可能高的维度缩减以外, 主要原因在于初始化时将具有最高信息增益率的特征赋给了森林中的大部分树(事实上, 经过最初的几轮迭代所淘汰的树往往没有选择该特征)和我们在新的适应度函数中充分考虑了维度缩减因素.EFSFOA在时间上的总体开销要多于FSFOA, 但是由于改进的几点中, 只有GSC参数的自动生成的改进是在算法框架的主要迭代阶段进行的, 其余的改进分别针对的是算法的预处理和后处理阶段, 因此所增加的额外时间开销主要都应来自于迭代阶段的参数生成过程, 而该过程的时间复杂度是O(1), 所以时间上的多余开销并不明显.这也是本文遵从于一般演化计算方法, 并未采用时间来衡量算法性能的一个主要原因.

4 总结

本文通过对FSFOA的分析, 针对其不足之处和待研究任务分别提出了3点优化方案, 并推广其工作到高维数据处理上去, 形成了一种新算法EFSFOA.EFSFOA结合信息论理论给出了一个全新的初始化策略.通过该策略, 更高效地指导了算法的后续展开, 避免了算法初始化不利所造成的被动局面; 在全局播种阶段, 通过使用控制函数T, 自动地生成了GSC参数, 充分利用了每棵树的年龄特性, 使算法的自适应能力得到增强; 算法寻优阶段, 采用合理的贪心算法, 在保证算法不低于原始结果的同时, 进一步利用了经过若干轮迭代生成的优质森林中的每一棵树; 面向高维数据处理时, 针对其高维数据处理能力不足的问题, 给出了集成化特征选择的算法框架, 同时, 综合维度缩减率进一步优化了原有的适应度函数.最后, 我们通过涵盖低维、中维、高维的15个数据集和近些年提出的11个特征选择算法与EFSFOA一起设置了对比实验, 经过1-NN、3-NN、5-NN、SVM、DT这5个分类器的验证发现, EFSFOA在分类准确率和维度缩减率上均有明显提高, EFSFOA的特征选择处理能力甚至达到了100 000维.在今后的工作中, 我们将尝试将EFSFOA与一些其他非基于演化计算的特征选择算法进行对比, 进一步检验我们的算法的性能, 同时还将尝试将我们的算法运用到一些如生物医疗等方面的真实数据集中来进一步优化我们的算法, 并对比基于演化计算的特征选择算法在实际的生物医疗数据集中与传统的处理生物医疗数据的方法——基于信息理论的特征选择算法的性能差异.

参考文献
[1]
Liu H, Yu L. Toward integrating feature selection algorithms for classification and clustering. IEEE Trans. on Knowledge and Data Engineering, 2005, 17(4): 491-502. [doi:10.1109/TKDE.2005.66]
[2]
Oh IS, Lee JS, Moon BR. Hybrid genetic algorithms for feature selection. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2004, 26(11): 1424-1437. [doi:10.1109/TPAMI.2004.105]
[3]
Maldonado S, Weber R. A wrapper method for feature selection using support vector machines. Information Sciences, 2009, 179(13): 2208-2217. [doi:10.1016/j.ins.2009.02.014]
[4]
Shah SC, Kusiak A. Data mining and genetic algorithm based gene/SNP selection. Artificial Intelligence in Medicine, 2004, 31(3): 183-196. [doi:10.1016/j.artmed.2004.04.002]
[5]
Guyon I, Elisseeff A. An introduction to variable and feature selection. Journal of Machine Learning Research, 2003, 3(6): 1157-1182. http://d.old.wanfangdata.com.cn/NSTLQK/10.1162-153244303322753616/
[6]
Peng H, Long F, Ding C. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min- redundancy. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2005, 27(8): 1226-1238. [doi:10.1109/TPAMI.2005.159]
[7]
Yu L, Liu H. Feature selection for high-dimensional data: A fast correlation-based filter solution. In: Proc. of the 20th Int'l Conf. on Machine Learning (ICML 2003). AAAI, 2003. 856-863.
[8]
Robnik-Šikonja M, Kononenko I. Theoretical and empirical analysis of ReliefF and RReliefF. Machine Learning, 2003, 53(1-2): 23-69. http://d.old.wanfangdata.com.cn/NSTLQK/10.1023-A-1025667309714/
[9]
Gu Q, Han J. Towards feature selection in network. In: Proc. of the 20th ACM Int'l Conf. on Information and Knowledge Management. ACM, 2011. 1175-1184.
[10]
Zhao Z, Liu H. Spectral feature selection for supervised and unsupervised learning. In: Proc. of the 24th Int'l Conf. on Machine Learning. ACM, 2007. 1151-1157.
[11]
Masaeli M, Yan Y, Cui Y, et al. Convex principal feature selection. In: Proc. of the 2010 SIAM Int'l Conf. on Data Mining. SIAM, 2010. 619-628.
[12]
Farahat AK, Ghodsi A, Kamel MS. An efficient greedy method for unsupervised feature selection. In: Proc. of the 2011 IEEE 11th Int'l Conf. on Data Mining (ICDM). IEEE, 2011. 161-170.
[13]
Efron B, Hastie T, Johnstone I, et al. Least angle regression. The Annals of statistics, 2004, 32(2): 407-499. [doi:10.1214/009053604000000067]
[14]
Xue B, Zhang M, Browne WN, et al. A survey on evolutionary computation approaches to feature selection. IEEE Trans. on Evolutionary Computation, 2016, 20(4): 606-626. [doi:10.1109/TEVC.2015.2504420]
[15]
Zhu W, Si G, Zhang Y, et al. Neighborhood effective information ratio for hybrid feature subset evaluation and selection. Neurocomputing, 2013, 99: 25-37. [doi:10.1016/j.neucom.2012.04.024]
[16]
Xue B, Zhang M, Browne WN. Particle swarm optimisation for feature selection in classification: Novel initialisation and updating mechanisms. Applied Soft Computing, 2014, 18: 261-276. [doi:10.1016/j.asoc.2013.09.018]
[17]
Tabakhi S, Moradi P, Akhlaghian F. An unsupervised feature selection algorithm based on ant colony optimization. Engineering Applications of Artificial Intelligence, 2014, 32: 112-123. [doi:10.1016/j.engappai.2014.03.007]
[18]
Zhang Y, Song X, Gong D. A return-cost-based binary firefly algorithm for feature selection. Information Sciences, 2017, 418-419: 561-574. [doi:10.1016/j.ins.2017.08.047]
[19]
Ghaemi M, Feizi-Derakhshi MR. Feature selection using forest optimization algorithm. Pattern Recognition, 2016, 60: 121-129. [doi:10.1016/j.patcog.2016.05.012]
[20]
Chu B, Li ZS, Zhang ML, et al. Research on improvements of feature selection using forest optimization algorithm. Journal of Software, 2018, 29(9): 2547-2558(in Chinese with English abstract). http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=5395&journal_id=jos [doi:10.13328/j.cnki.jos.005395]
[21]
Jadhav S, He H, Jenkins K. Information gain directed genetic algorithm wrapper feature selection for credit rating. Applied Soft Computing, 2018, 69: 541-553. [doi:10.1016/j.asoc.2018.04.033]
[22]
Pereira RB, Plastino A, Zadrozny B, et al. Information gain feature selection for multi-label classification. Journal of Information and Data Management, 2015, 6(1): 48-58.
[23]
Yiğit F, Baykan ÖK. A new feature selection method for text categorization based on information gain and particle swarm optimization. In: Proc. of the 2014 IEEE 3rd Int'l Conf. on Cloud Computing and Intelligence Systems (CCIS). IEEE, 2014. 523-529.
[24]
Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. Science, New Series, 1983, 220(4598): 671-680. http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_e16e87d1fe5b4e0dd92ce7ad553a8c2a
[25]
Dua D, Graff C. UCI machine learning repository. Irvine: School of Information and Computer Science, University of California, 2017. http://archive.ics.uci.edu/ml
[26]
Ghaemi M, Feizi-Derakhshi MR. Forest optimization algorithm. Expert Systems with Applications, 2014, 41(15): 6676-6687. [doi:10.1016/j.eswa.2014.05.009]
[27]
Cai J, Luo J, Wang S, et al. Feature selection in machine learning: A new perspective. Neurocomputing, 2018, 300: 70-79. [doi:10.1016/j.neucom.2017.11.077]
[28]
Moustakidis SP, Theocharis JB. SVM-FuzCoC: A novel SVM-based feature selection method using a fuzzy complementary criterion. Pattern Recognition, 2010, 43(11): 3712-3729. [doi:10.1016/j.patcog.2010.05.007]
[29]
Hu Q, Che X, Zhang L, et al. Feature evaluation and selection based on neighborhood soft margin. Neurocomputing, 2010, 73(10-12): 2114-2124. [doi:10.1016/j.neucom.2010.02.007]
[30]
Huang J, Cai Y, Xu X. A hybrid genetic algorithm for feature selection wrapper based on mutual information. Pattern Recognition Letters, 2007, 28(13): 1825-1844. [doi:10.1016/j.patrec.2007.05.011]
[20]
初蓓, 李占山, 张梦林, 等. 基于森林优化特征选择算法的改进研究. 软件学报, 2018, 29(9): 2547-2558. http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=5395&journal_id=jos [doi:10.13328/j.cnki.jos.005395]