一、特征提取与选择任务定义：得到实际对象的若干具体特征之后，再由这些原始特征产生对分类识别最有效、数目最少的特征。使在最小维数特征空间中异类模式点相距较远，同类模式点相距较近。

二、特征提取与选择任务的提出背景：①获得的特征测量值不多，导致提供的信息较少②获得的测量值太多，导致维度灾难(特征数目达限后，性能反而不好)③特征存在很多无用信息，或者有的有用信息不能反映本质，要通过变换才能得到更有意义的量。

二、特征选择与提取的两个基本途径

（一）直接选择法(特征选择)：直接从已获得的n个原始特征中选出d个特征。主要方法有：统计检验法、分支定界法、遗传算法等。

1、最优搜索算法——分支定界法(BAB算法)：利用可分性判据的单调性采用分支定界策略，和值左小右大的树结构，使得在实际不计算某些特征组合而又不影响全局寻优。这种具有上述特点的快速搜索方法称为分支定界。

（1）分支定界法高效的原因：①构造搜索树时，同一父节点的各子节点为根的各子树右边的边比左边少，树的结构右边简单。②同一级中，节点的J值左小右大，而搜索过程从右至左。③由J的单调性知，搜索树的上某个节点的J值大于以该节点为根节点的子树的各节点的J值。由①②③知，有很多特征组合不需要计算仍能求得全局最优解。

2、次优搜索算法

（1）单独最优的特征选择法：计算各特征单独使用时的判据值并以递减排序，选取前d个分类效果最好的特征。

（2）增添特征法(顺序前进法SFS)：每次从未选入的特征中选择一个特征，使它与已选入的特征组合在一起时可分性判据值J最大。

（3）剔减特征法(顺序后退法SBS)：从全部特征开始每次剔除一个特征，所剔除的特征应使尚保留的特征组合的值最大。

（4）增l减r法：结合(2)、(3)，加入局部回溯。

3、遗传算法：是一种基于自然选择和群体遗传机理的搜索算法，模拟了自然选择和自然遗传过程中的繁殖杂交和突变现象。在利用遗传算法求解问题时：①问题的每个可能解都被编码为一个“染色体”，即个体。若干个个体构成了群体(所有可能解)②在遗传算法开始时，随机产生一些个体(即初始解)③根据预定的目标函数对每个个体进行评估，给出适应度，基于该适应度选择一些个体用来产生下一代，“坏”的个体则被淘汰，适应度越高的越容易被选中④选出来的个体经过交叉变异算子进行再组合生成新的一代，这一代的个体由于继承了上一代的一些优良性状，因而在性能上优于上一代，这样逐步朝着最优解的方向进化。

（1）算法步骤：编码——初始解——适应度评估——适应度评估越高越容易被选中——交叉变异——生成下一代——进行适应度评估，以此重复循环。当进化代数超过阈值或连续数个世代都没有得到更优解时，则停止算法。【群体大小和进化代数是两个重要参数】

（2）遗传操作：模拟生物基因的操作，其任务是根据个体适应度对其施加一定的操作，从而实现优胜劣汰的进化过程，可以使问题的解逐代优化，逼近最优解。遗传操作包括三个基本遗传算子：选择、交叉、变异：

①选择、交叉基本上完成了遗传算法的大部分搜索功能，选择是基于适应度进行选择，交叉是获取优良个体的重要手段；

②变异增加了遗传算法找到最优解的能力，能避免由于选择、交叉算子而引起的某些信息永久性丢失，保证了遗传算法的有效性，使遗传算法具有局部随机搜索的能力。

（3）遗传算法设计的五个基本要素：参数编码、初始群体设计、适应度函数设计、遗传操作设计、控制参数设定

（二）变换法(特征提取)：对n个原始特征进行变换降维，坐标变换再取子空间。主要方法有基于可分性判据的特征选择、基于误判概率的特征选择、离散K-L变换法(DKLT)、基于决策界的特征选择。

1、主成分分析PCA：使数据集由较少的“有效”特征来表示。其思想是找出“主要”元素和结构，去除噪声和冗余，将原有的复杂数据降维，揭示隐藏在复杂数据背后的简单结构。【找到一个从原d维输入空间到新K维空间的具有最小信息损失的映射。】基于最大化方差。

2、基于K-L变换的特征提取：PCA是K-L变换的一种最基本形式。实质是坐标的旋转。

（三）特征选择与特征变换的比较：

1、特征选择是从D个原始特征中选择其中的d个，保持了原有物理含义；

2、特征变换是通过适当的数学变换把D个原始特征转换成d个新特征，得到的特征不具有原始物理含义，但一般来说消除了特征之间的相关性，减少特征中与分类无关的信息。