湛 航，何 朗*，黄樟灿，李华峰，张 蔷，谈 庆

（1.武汉理工大学理学院，武汉 430070；2.武汉大学数学与统计学院，武汉 430072）

（*通信作者电子邮箱helang@whut.edu.cn）

0 引言

特征选择（Feature Selection，FS）是数据挖掘中一项特别重要的数据预处理步骤，常用于去除数据中冗余和不相关的特征数据，降低计算复杂度，提升模型的效果［1-2］。特征选择在数字图像处理、文本分类、生物信息学、基因序列分析、金融时间序列分析以及医学数据分析等方面应用较为广泛［3-6］。常见的特征选择方法有：过滤式（filter）、嵌入式（embedding）和包裹式（wrpper）［7］。过滤式独立于学习器，在训练学习器之前完成特征的选择；嵌入式则将特征选择与学习器的训练结合，在一个优化过程中完成；包裹式则依据学习器的性能作为特征选择优劣的评价［7］。

特征选择是一个NP-hard 问题，对于具有n个特征的特征选择问题有2n个可能的特征子集［8］。在分类问题上，通过选取关键的特征，忽略不太重要的数据特征，构建出一个良好的分类器，进而提高分类预测效果［9］。选择的特征优劣对于构建出一个简洁、高效的分类系统有着重要的影响［10］。

国内外许多学者一直致力于研究这个问题。一些简单方法如穷举搜索算法、分支定界算法等［11］，这些方法可以挑选出最优的特征子集，但是这些方法的时间复杂度对于高维数据并不友好，在应用过程中也存在一些局限性。基于该问题，一些传统的机器学习方法被应用到这个方面，如决策树算法［12］给出了一种基于信息增益大小的特征选择分类方法；……