本系列博客主要是在学习《模式识别（张学工著 第三版）》时的一些笔记。
本文地址：http://blog.csdn.net/shanglianlm/article/details/49464445

1. 前言

1-1 问题：

从 D 维特征中选择 d<D 个特征。

1-2 特征选择主要回答两个层面的问题：

1. 对特征的评价，即怎样衡量一组特征对分类的有效性；
2. 寻优的算法，即怎样更快地找到性能最优或比较好的特征组合。

2. 特征的评价准则

类别可分性准则：

2-1 基于类内类间距离的可分性判据

投影到另一空间后，类内离散度尽可能小、类间离散度尽可能大的准则来确定最佳的投影方向。

2-2 基于概率分布的可分性判据

常见的概率距离度量

2-3 基于熵的可分性判据

主要从后验概率角度来考虑。

2-4 利用统计检验作为可分性判据

特点
只能针对单个特征对分类性能进行判据，也存在针对多变量的，但是当特征维数较高时，往往较难实现。

3. 特征选择算法

3-1 特征选择的最优算法（穷举法）

分支定界方法的基本思想：

设法将所有可能特征选择组合构建成一个树状结构，按照特定的规律对树进行搜索，使得搜索过程尽可能早地可以达到最优解而不必遍历整棵树。

实例

从 D =6 个特征中选 d = 2 个特征。

• 树的根节点包含全部特征，称为第 0 级，
• 每一级的节点在其父节点基础上去掉一个特征（去掉的特征序号写在节点旁边）。
• 对于第 l 层节点 i ， 假设它包含 Di 个候选特征，我们在同一层中按照去掉单个特征后的准则函数对各个节点排序，如果去掉某个特征后准则函数损失函数最大，则认为这个特征最不可能去掉，放在该层最左侧节点。
• 第 i 层节点下工生长 Di−d+1 个子节点。
• 第 l +1 层的展开沿最右侧节点开始，在同层上已经在左侧节点上的特征在本节点之下不再进行舍弃，因此，第 l+1 层的一个节点上的候选基因就是它上一层的 Di 个候选特征减去本节点上舍弃的特征以及它同层左侧节点上的特征。
• 从每一树枝的最右侧开始向下生长，当到达叶节点时计算当前达到的准则函数值，记作界限 B 。
• 到达叶节点后算法向上回溯，每回溯一步把相应节点上舍弃的特征回收回来。遇到最近的分支节点停止回溯，从这个分支节点向下搜索左侧最近的一个分支。
• 如果在搜索到某一个节点时，准则函数值已经小于界限 B，说明最优解已不可能在本节点之下的叶节点上，所以可以停止搜索，向上回溯。
• 如果搜索到一个新的叶节点，则更新界限 B 值，向上回溯。
• 直到不能向下搜索其他树枝，则算法停止，最后一次更新 B 时取得的特征组合就是特征选择的结果。

3-2 特征选择的次优算法（确定性的启发式搜索）

最优搜索方法的计算量可能仍然最大，因此会考虑一些计算量较小的次优搜索方法。

3-2-1 单独最优特征的组合

对每一个特征单独计算类别可分性依据，选取最大的前 d 个特征。

特点
只有当特征间统计独立和所采用的判据是每个特征上的判据之和或之积时，才最优。

3-2-2 顺序前进法（从底向上）

第一个特征选择单独最优，后面的特征选择与之组合最优的那些特征（一次可以一个也可以多个）。

特点
某个特征一旦被选中则不能再被剔除。

3-2-3 顺序后退法（从顶向下）

逐渐剔除不被选中的特征。与顺序前进法正好相反。

特点
某个特征一旦被剔除则不能再被选中。

3-2-4 增 l 减 r 法

交替使用 顺序前进法 和 顺序后退法。

3-3 特征选择的遗传算法（随机搜索）

特点
遗传算法虽然不能保证收敛到全局最优解，但是在多数情况下可以至少得到很好的次优解。

3-4 以分类性能为准则的特征选择算法（包裹法）

把分类器和特征选择集合起来，利用分类器进行特征选择的方法称作包裹法。

这些分类器要求满足两个条件
1. 分类器应该能够处理高维的特征向量。
2. 分类器能够在特征维数很高但样本数有限时仍能得到较好的效果。

常见的两种方法有 递归支持向量机（R-SVM）和支持向量机递归特征剔除（SVM-RFE）。