特征选择的任务是从一组数量为N的特征中选择出数量为n（N>n）的一组最优（或次优）特征，未被选中的子集则被丢弃。从特征选择定义的基础出发，我们认为一个典型的特征选择算法应当包含如下四个基本模块：64999

1. 构造特征子集（等价于在原始特征空间进行查找）；

2. 采用适当的评价标准对所构造的子集进行评价；

3. 确定停止查找的条件；

4. 对得到的最优（或次优）子集进行统计评估，以确认被删除的特征所造成的信息损失在允许的范围内。

相应地特征选择算法的一般流程示意如图1.3.1所示。

目前国际上对特征选择算法的研究主要集中在选择优化特征子集所需要的两个主要步骤上，即搜索策略和评价标准。搜索策略用来产生候选特征子集，评估准则是对候选子集进行评估。

根据所选择的搜索策略的不同，可以将特征选择方法划分为穷举法（Exhaustion）、启发式（Heuristic）和随机法（Random）三类。

穷举法指遍历特征空间中所有特征的组合，选择最优特征组合子集的方法。假设特征个数为N时，计算复杂度为O(2N)。典型算法为分支定界算法，这种算法能保证在事先确定优化特征子集中特征数目的情况下, 找到相对于所设计的可分性判据而言的最优子集。穷举法的优点在于一定能得到最优子集，但实际情况下存在问题：很难确定优化特征子集的数目；满足单调性的可分性判据难以设计；处理高维多类问题时, 算法的时间复杂度较高。因此, 虽然全局最优搜索策略能得到最优解, 但因为诸多因素限制,导致实用性不强。论文网

启发式特征选择方式主要有：单独最优特征组合，序列前向选择方法（SFS）,广义序列前向选择方法（GSFS），序列后向选择方法（SBS），广义序列后向选择方法（GSBS），增l去r选择方法，广义增l去r选择方法，浮动搜索方法。这类方法易于实现且快速，它的搜索空间是O(N2)。一般认为采用浮动广义后向选择方法（FGSBS）是较为有利于实际应用的一种特征选择搜索策略，它既考虑到特征之间的统计相关性，又用浮动方法保证算法运行的快速稳定性。虽然启发式搜索策略效率高，但是它以牺牲全局最优为代价。

随机法在计算过程中把特征选择问题和模拟退火算法、禁忌搜索算法、遗传算法、或随机重采样（Bootstrap）过程结合，以概率推理和采样过程作为算法基础。遗传算法在这一领域的应用最为广泛。从解决问题的效果来看，该方法把分类性能引入作为特征的评价准则，在此基础上对所有的特征进行排序，可以得到一个较好的应用结果。但是这类方法同样也存在着一些问题：1)大量的时间消耗。它的运行时间随着数据集变量的增加呈指数增长，对于特征很多的数据集（如生物芯片数据等）时间消耗特别大。2)如果在该算法中采用的是统计得分的方式，那么仅能对所有特征的重要性进行排序，很难确定一个优化的特征子集。

已有的特征选择方法中，只有穷举法能保证最优，但耗时并且计算复杂度很高，而其它方法则以代价换取简单、快速的实现，不能保证最优，一般能够获得近似于最优解的解。每种搜索策略都有各自的优缺点, 在实际应用过程中, 可以根据具体环境和准则函数来寻找一个最佳的平衡点。