Page 68 - 《软件学报》2020年第12期

3734 Journal of Software 软件学报 Vol.31, No.12, December 2020

dimensional reduction, given the new fitness function. In addition, the idea of sub-population cooperative co-evolution is introduced to
solve high-dimensional data. The original problem is decomposed into relatively small sub-problems to reduce the combined effect of the
original problem scale and each sub-question is solved independently, and then all sub-problems are correlated to optimize the solution to
the original problem. Further, applying multiple competing evolutionary populations to enhance the exploration ability of the algorithm
and designing a population restart strategy to prevent the population from falling into the local optimal solution. Finally, the proposed
algorithm is compared with several traditional feature selection algorithms on some UCI public datasets. The experimental results show
that the proposed algorithm can effectively complete the feature selection problem and has excellent performance compared with the
classical feature selection algorithm, especially when dealing with high-dimensional data.
Key words: evolution strategy; feature selection; cooperative co-evolution; competitive evolution; high-dimensional

特征选择在机器学习、数据挖掘和模式识别等领域中有着重要的应用.由于数据收集技术的不断完善,一
些专业领域中数据量不断积累,导致在机器学习和数据挖掘中要处理的数据特征总数变大.在这些特征中,选取
能够描述目标概念的特征子集就尤为重要.特征选择就是从原始特征集合中选取有效的特征子集来减少数据
[1]
[2]
特征维数的过程 .因此,特征选择自然就成为了机器学习和数据挖掘领域中一个重要的数据预处理手段 .
特征选择算法有很多种,总的来讲可以分为 3 类:过滤式方法、包裹式方法以及嵌入式方法 [3,4] .过滤式方法
不依赖于其他学习算法,首先将数据特征按照一定的标准进行排序,然后选择那些表现比较好的特征,由于这种
[1]
方式具有很高的计算效率 ,因此普遍被用来处理一些高维数据;包裹式方法通过引入一个学习算法来评估所
[5]
选的特征子集 ,因为直接对目标进行优化,所以包裹式方法具有更好的性能;嵌入式方法试图将特征选择和分
类器学习整合在同一个过程中,从而综合了包裹式方法和过滤式方法的优点.
特征选择在分类任务中是 NP-hard 的,由于搜索空间会随着特征个数的增加呈指数级增长.对于包含 n 个特
n
征的实例,其搜索空间就会有 2 个可能的结果 [4,6] .关于特征选择的方法已经进行了许多工作,根据产生特征子
集所采用搜索策略的不同,特征选择方法可以分为穷举法、启发法和随机法.
穷举法试图枚举搜索空间中的解来寻找一个能够正确区分所有类别的最小特征集合.当数据特征个数较
多时,评价所有特征子集在计算上是不可行的,因此在包含大量特征的数据集中,穷举法很少用于特征选择.
[7]
启发式特征选择算法主要包括贪婪爬山算法 、分支限界法、定向搜索以及最佳优先算法.SFS(sequential
forward selection)和 SBS(sequential backward selection)是两种经典的爬山算法,但这两种方法容易陷入局部最
[8]
优解.为克服这一缺点,SFFS 算法、SBFS 算法被提出 .另外,基于支持向量机并应用启发式搜索策略的特征选
择方法是近年发展起来的通用方法,它本身是一种有监督学习算法.Moustakidis 等人提出了一种新的基于模糊
[9]
互补准则的支持向量机特征选择方法 SVM-FuzCoC .
随机法的主要优点是具有可接受的时间复杂性,特别是一些自然启发式算法,由于其出色的全局搜索能力
在特征选择问题中引起了大量的关注 [10] .具体的,Zhu 等人将遗传算法和局部搜索方法结合起来,提出了 FS-
NEIR 算法 [11] .同年,Xue 等人提出了基于粒子群优化的特征选择算法 PSO [12] .Tabakhi 等人提出了基于蚁群优化
的无监督特征选择算法 UFSACO [13] .近年来,关于演化算法在特征选择问题中的应用也有很多,例如 Ghaemi 等
人提出的基于森林优化算法的特征选择方法 FSFOA [14] 、Zhang 等人基于萤火虫算法提出的 Rc-BBFA [15] 、
Marwa 等人提出的混合过滤和包裹方法的多目标演化特征选择算法 FW-NSGA-II [16] 、Hancer 等人基于差分进
化提出的特征选择方法 DE-FLS [17] 、Chen 等人基于细菌觅食算法提出 ISEDBFO [18] 及 ACBFO [18] 、Qian 等人
基于进化帕累托优化提出的 POSS 算法 [19] .之后,Qian 等人又提出了基于帕累托优化的无监督特征选择算法
POCSS [20] .POCSS 采用随机迭代过程来最小化重建误差和所选择的特征数量.此外,基于多种群的协同演化算
法也被用于处理特征选择问题,例如 J.Derrac 等人提出的基于协同进化算法的特征选择方法 IFS-CoCo [21] 等.
相比于传统的特征选择方法,基于演化计算方法的明显优势在于其通常不需要领域内的相关知识和对搜
索空间做任何的假设,并且由于它基于种群机制,能够在一次运行中产生多种结果,使其更适合用来进行多目标
特征选择,以确保在特征数量和分类性能中取得平衡.因此,将演化计算引入特征选择取得了不错的效果.尽管
如此,目前演化计算方法仍存在一些不足之处.
• 首先,演化计算过程中随机性较高,算法每次运行产生的结果不能够保证,并且算法在迭代中不能够准