赵泽渊，代永强

甘肃农业大学 信息科学技术学院，兰州 730070

特征选择（feature selection）是从数据集已有的N个特征中去除冗余、无用的特征，并选出具有M个特征的特征子集的方法（M≤N），该方法能够降低特征数目，提高分类算法的分类性能[1]。

常见的特征选择方法分为过滤式（filter）、封装式（wrapper）、嵌入式（embedded）[2-3]。过滤式方法与特定的学习算法无关，该方法从数据集本身的内在性质（如相关性）获得评价标准，然后根据各子集的优劣进行选择[4]。封装式方法是从数据集中不断产生特征子集并将其用来训练分类器，最后根据分类器的性能来选择最优特征子集[5]。而在嵌入式方法中，特征选择算法本身作为组成部分嵌入到分类算法里[4]。封装式方法直接面向算法优化，易于实现，并且精度与鲁棒性优于过滤式与嵌入式方法，因此本文采用封装式的方法进行特征选择。

假设数据集维度为n，穷举搜索最优特征子集的时间复杂度为O(2n)，对高维度数据进行特征选择时使用穷举搜索需要耗费大量时间以及计算资源[6-7]。启发式搜索最优特征子集是通过对比特征子集增减特征前后的优劣程度来搜索最优特征子集，其时间复杂度为O(n2)。虽然启发式搜索方法在高维度条件下的性能优于穷举搜索方法，但其仍然需要花费大量时间成本。随机搜索是指将特征选择与随机优化算法相结合，使用随机优化算法的优化策略生成子集，并使用特定的评价函数来评价子集的优劣，最后依照自定义的结束条件来完成特征子集的选择。……