一个阈值，当评价函数值达到这个阈值后就可停止搜索。 D. 子集验证：用来验证最终所选子集的有效性。
评价函数
• 评价函数通常用来评估某个特征或特征子集分类的能力。 • 最优特征子集产生和评价函数是相关的，不同评价函数
可能产生不同的最优特征子集。 • 将评价函数分为两类：filter和wrapper。 • 用符号J ( Y )来表示评价函数，其中Y是一个特征集，J( Y )
分支限界法（B&B）
Xl 表示特征数目为l 的特征集合。 Xs 表示舍弃s 个特征后余下的特征集合。
s 表示第s 级当前节点上用来作为下一级可舍
弃特征的特征集合。
rs 表示集合s中元素的数目。 qs 表示当前节点的子节点数。
分支限界法（B&B）
由于从根节点要经历n-d级才能到达叶节点，s级某 节点后继的每一个子节点分别舍弃s中互不相同的一 个特征，从而考虑在s+1级可以舍弃的特征方案数 （即子节点数）qs时，必须使这一级舍弃了特征后的 Xs+1还剩（n-d)-(s+1)个特征。除了从树的纵向上 每一级舍弃一个特征，实际上从树的横向上，一个分 支也轮换舍弃一个特征。因此后继子节点数
特征选择一般流程
A. 产生过程( Generation Procedure )：按一定的搜索策略产生候选特征
子集。
B. 评价函数( Evaluation Function ) ：通过某个评价函数来评估特征子集
的优劣。 C. 停止准则( Stopping Criterion )：停止准则是与评价函数相关的，一般是
• 相关性度量：用来度量特征和类别之间的相关性。 --相关系数
• 信息论度量： --信息增益、最小描述长度、互信息
Filter-距离度量
• 距离度量，是基于这样的假设：好的特征子集应该使得 属于同一类的样本距离尽可能小，属于不同类的样本之 间的距离尽可能远。 常见的有欧氏距离、马氏距离、巴 氏距离等等。
• 序列算法：这类算法实际上是一种贪心算法，算法时间 复杂度较低，但是可能会陷入局部最优值，不一定能找 到全局最优解。
• 随机算法：随机算法属于一种近似算法，能找出问题的 近似最优解。每个随机算法都需要设置一定的参数，这 些参数的选择很重要。
搜索策略
• 穷举算法：穷举搜索 Exhaustive Search (ES) 分支限界法 Branch and Bound (B&B) 集束搜索 Beam Search (BS)
• 通过计算特征的信息增益来对特征进行评价。 • 信息熵：假设存在离散变量Y，Y中可能的取值包括{y1，
y2，....，ym} ，yi出现的概率为Pi。则Y的信息熵定义为：
• 条件信息熵：附加条件X=Xi后，Y的条件信息熵变为： • 信息增益：加入条件X前后的信息熵之差。
Filter-信息增益（2）
比如在识别苹果和橙子的系统中，我们可以抽取的特征很多 （体积、重量、颜色、高度、宽度、最宽处高度），在这些特 征中有用的是（颜色、高度、最宽处高度），其它特征对识别 意义不大，所以去掉。
为什么进行特征选择？
在机器学习的实际应用中，特征数量往往较多，其中可能 存在不相关的特征，特征之间也可能存在相互依赖，容易 导致如下的后果： • 特征个数越多，分析特征、训练模型所需的时间就越长。 • 特征个数越多，容易引起“维度灾难”，模型也会越复
• 序列算法：前向顺序选择 后向顺序选择 增L去R算法 双向搜索算法 序列浮动选择算法
• 随机算法：随机产生序列选择算法 模拟退火算法 遗传算法
穷举搜索（ES）
• 穷举所有满足条件的特征子集，从中选取最优。如果有N
个特征，不限定选取特征的个数，则有 2N 个候选特
征子集。 • 从D个特征中选择d个，可能组合q
1 {x2 , x3, x4 , x5, x6} 1 {x3, x4 , x5, x6} 1 {x4 , x5 , x6}
2 {x4 , x5, x6} 2 {x5, x6}
分支限界法（B&B）
0 {x1, x2 , x3, x4 , x5, x6} r0 6 q0 6 (4 0 1) 3
1 {x2 , x3, x4 , x5, x6}
2 {x3, x4 , x5 , x6} 2 {x4 , x5 , x6} 2 {x5, x6}
分支限界法（B&B）
目标：找出叶节点Lk，使
其对应的d个特征的判据J的
值最大，即：
Cnd
J
(
Lk
)
max[ j 1
J
(
L
j
)]
注意到每个节点（包括非叶 节点）都可以计算相应的J 值。由于判据J值具有单调 性，即：
Filter和Wrapper优缺点
评价准则
优点
filter
快速执行； 易于推广；
wrapper 准确率高；
缺点
准确率方面通常低于 Wrapper方法；
计算代价大； 不易于推广；
搜索策略
• 穷举算法：对特征空间进行穷举搜索（当然也会采用剪 枝等优化），搜索出来的特征集对于样本集是最优的。 这类算法的时间复杂度是指数级的。
• 算法流程：
• 算法评价： 一旦某特征被选入，就不能删除，即使由于后面加入的 特征使它变得多余。
序列前向选择SFS（2）
顺序后向选择SBS
• 和前向算法类似。但初始特征集合是所有特征，每次从 中剔除一个，使保留的特征组的J值最大。
• 算法流程：
• 和顺序前向算法相比，SBS计算是在高维空间进行，所以 计算量比前向大。
增L去R算法
• 增L去R选择算法 ( LRS , Plus-L Minus-RSelection ) • 算法描述：该算法有两种形式。
• 当L>R ，算法从空集开始，每轮先加入L个特征，然 后从中去除R个特征，使得J(Y)最大。
• 当L<R ，算法从全集开始，每轮先去除R个特征，然 后加入L个特征，使得J(Y)最大。
• 计算所有可能的特征组合的J，选择J最大的那组为最优组 合。这种方法计算量大，只适用于特征个数比较少的情况， 运算量随着特征维数的增加呈指数递增，实际应用中经常 碰到几百甚至成千上万个特征，因此穷举法虽然简单却难 以实际应用。
分支限界法（B&B）
• 分支限界法是一种自上而下的搜索算法，采用剪枝策略 优化搜索过程，得到全局最优解。
分支限界法（B&B）
树的每个节点表示一种特征组合， 树的每一级各节点表示从其父节点的特征组合中 去掉一个特征后的特征组合，其标号k表示去掉的 特征是xk 。
由于每一级只舍弃一个特征，因此整个搜索树除 根节点0级外，还需要n-d级，即全树有n-d级。 例如，6个特征中选2个，整个搜索树有4级。 第n-d级是叶节点，共有Cnd个叶节点。
分支限界法（B&B）
如果搜索到叶节点，且 该叶节点代表的特征的 可分性判据J>B，则更 新界值，即B=J；否则 不更新界值。
到达叶节点后，要向上回溯。重复上述过程，直到 JB为止。而对应当前（最大）界值B的叶节点对 应的d个特征组合就是所求的最优的选择。
序列前向选择SFS（1）
• 从空集合开始搜索，不断选择新特征加入已有特征集合 Yk，使得加入新特征x’之后的目标函数 J(Yk x') 最大。
特征提取 ( Feature extraction ) 是指利用已有的特征计算出一个抽 象程度更高的特征集。对已有特征 集合进行映射变换得到。 PCA、LDA
特征选择也叫特征子集选择 ( FSS , Feature Subset Selection ) 或属 性选择( Attribute Selection )。 特征选择实质是从原始数据集中选 取最优子集的过程。
越大表示特征集Y越好
评价准则
Filter ： 通 过 分 析 特 征子集内部的信息来 衡量特征子集的好坏。
Wrapper：评价函数是一个分 类器，采用特定特征子集对样 本集进行分类，根据分类的结 果来衡量该特征子集的好坏
评价函数-Filter
• 距离或可分性度量：距离度量有时候也称作类别可分离 判据、离散度准则,在统计模式识别中对类别的可分离性 研究的比较深入。 --欧几里得距离、马氏距离、巴氏距离等
杂，其推广能力会下降。 特征选择能剔除不相关(irrelevant)或亢余(redundant )的特 征，从而达到减少特征个数，提高模型精确度，减少运行 时间的目的。另一方面，选取出真正相关的特征简化了模 型，使研究人员易于理解数据产生的过程。
特征选择和特征抽取区别？
模式识别中特征降维方法有两种：特征抽取和特征选择
分支限界法（B&B）
s=i 00 s=i 11
si=22
X0 0 X n
1
23
2
3 4 A3 4 4
s=3 i 3 3 4 5 4 5 5 4 5 5 5
s=4 i 4 4 5 6 5 6 6 5 6 6 6 5 6 6 6 6
(a)
X0 (b)
6选2的特征选择问题 (a)搜索树 (b)搜索回溯示意图
qs=rs-（n-d-s-1）
分支限界法（B&B）
s
rs
qs
s+1
(n-d)-(s+1) n-d
rs qs (n d ) (s 1) qs rs (n d s 1)r0 n q0 d 1
分支限界法（B&B）
0 {x1, x2 , x3, x4 , x5, x6} r0 6 q0 6 (4 0 1) 3
• 使用分支限界进行特征选择需要先引入一个单调性假设 (monotonicity assumption)：J(Y) < J(Y+x)，即任何 特征集的都优于其任何的子集。