林炜星，王宇嘉，陈万芬，梁海娜

上海工程技术大学 电子电气工程学院，上海201620

现实生活中存在着大量的事件或对象可以用一系列特征表示，对于给定的学习任务，特征选择从原始特征集合中选出相关特征子集，达到降维和简化学习模型的目的，现已成功应用在生物信息学和图像处理等领域[1-4]。然而，随着高维数据集的出现，问题的搜索空间随着维度的增加呈指数倍增，巨大的搜索空间加大了算法在搜索过程中陷入局部最优的概率；同时，高维情形下出现的维数灾难和计算代价高昂都成为了限制特征选择效率的因素。因此，高维数据特征选择问题仍然是机器学习领域的一项挑战。

特征选择的本质是组合优化问题，对于有n个特征的数据集，其求解是从解空间中2n个组合里选出最优的一个。学者们提出了许多特征选择方法解决分类问题，可分为过滤式选择和包裹式选择[5]。

过滤式方法使用数据的内在特性（例如距离、相关性、一致性和信息度量等）对数据集进行特征选择之后再训练分类器，不涉及任何学习算法来搜索子集。Relief算法[6]是一种经典的过滤式特征选择算法，其设计了一个统计量对特征的重要性进行度量。该统计量的每个分量对应一个原始特征，每个特征的重要性通过统计量的数值与选择阈值对比，从而确定特征的重要性。Relief算法的运行效率高，时间开销低，更适应于高维特征选择。但是过滤式算法缺少学习器反馈环节，分类精度往往比包裹式选择低。……