其核心问题
是通过合理组合搜索过程，可以避免一些 计算而仍能得到最优的结果。
其关键是利用了判据的单调性
最优搜索算法
判据的单调性
如果特征存在包含关系: 则有: 称该判据具有单调性 讨论过的J1-J5,以及基于概率距离的判据 JD,JC,JB都满足上述关系
最优搜索算法
下面我们结合一个从D＝6的六维特征空 间选择d＝2的二维最优子空间的例子， 说明该算法的原理以及如何利用判据的 单调性减少计算量。 设原D维空间有六个特征表示成 {x1,x2,x3,x4,x5,x6}
(2) 确定直接后继结点要删除的特征
删去其中一特征的相应判据值，判据最小
最优搜索算法
回溯过程
要执行的任务是将第i层的ψ加上第i-1层被删 除的特征，并检查其分支路数q 待发现到 qi-1>1,就到达回溯转折点，转入其 相邻左边第i层结点。
最优搜索算法
优点
该算法避免了部分d个特征组合的判据计算，与穷 举相比节约了时间。
当l＜r时，入选特征数逐渐增加，属“自下而上” 型 反之属“自上而下”型。
增l减r法(l-r法)
此法也可推广至用GSFS及GSBS代替SFS及SBS 并可在实现增加l特征时采用分几步实现
增l特征用Zl步减r则用Zr步，该种方法一般称为(Zl, ( Zr)法 这种做法是为了既考虑入选(或剔除)特征之间的相 关性，又不至因此引起计算量过大。 合理地设置Zl和 Zr可以同时对两者，即计算复杂性 及特征选择的合理性兼顾考虑
简单回顾
类别可分离性判据的种类
基于距离度量的可分性判据 基于概率分布的可分性判据等
特征提取
按欧氏距离度量的特征提取方法 按概率距离判据提取特征
8.4 特征选择
特征选择
即对原有特征进行删选优化
概念上十分简单
一般人常想，只要逐个分析每个特征，判断 它对分类的价值，然后根据其优值删去或保 留，这是一个为人们常采用方法 但是这种方法并不能保证特征空间的最优组 合优化
搜索算法
要得最优解，就必需采用穷举法
任何非穷举的算法都不能确保所得结果是最 优的，因此要得最优解，就必需采用穷举法 搜索技术上采用一些技巧，使计算量有可能 降低 最优特征搜索法，次优解的算法
搜索算法
“自上而下”与“自下而上”两类算法
“自上而下”: 从D维特征开始，逐步将其 中某些特征删除，直到剩下所要求的d维特 征为止。
单独最优特征组合
单独最优特征组合
将各特征按单独使用计算其判据值，然后取 其前d个判据值最大的特征作为最优特征组 合。 这种做法的问题在于即使各特征是独立统计 的，也不一定得到最优结果。 但如果可分性判据可写成如下形式
可以选出最 优特征来
顺序前进法(SFS)
顺序前进法
最简单的自下而上搜索方法 首先计算每个特征单独进行分类的判据值， 并选择其中判据值最大的特性，作为入选特 征。 然后每次从未入选的特征中选择一个特征， 使得它与已入选的特征组合在一起时所得的 J值为最大，直到特征数增至d个为止。
可用下面的搜索树形结构图表示搜索过程
最 优 搜 索 算 法
最优搜索算法
搜索树形结构图
根结点为原特征空间，包含全部特征，在这里是六 个特征 除了根结点外，其它结点每删除一个特征，结点上 的号表示被删特征序号 叶结点本身也删除一个特征，而剩下的特征组的特 征数为d，在此为2。 该树的结构特点:即每一层结点的直接后继结点数各 不相同，但是却有规律性。
另一个问题是要找出较好的特征选择方法
以在允许的时间内选择出一组最优的特征。 所谓最优的特征组，就是要找到合适的特征的组 合
搜索算法
计算量问题
如果从逐个特征配组进行性能比较的话，即穷举 的算法，特征配组的数量极大
如果D＝100，d＝10，则q的数量级就是1013， 即使D＝20，d＝10，则q也可达184756种。 如果将所有可能的特征配组列举出来，按某选定 的可分离性判据进行计算，从中择优，其计算量 非常大
搜索算法
如何解决这个问题呢?
如果将每维特征单独计算可分离性判据，并按其 大小排队，如
然后直接选用前d个特征构成新的特征空间 能得到最优的可分离性？ 不能 即使所有特征都互相独立，除了一些特殊情况外， 一般用前d个最有效的特征组合成的特征组并非是 最优的d维特征组 因此采用这种方法并不能保证得到最优的特征组 合
譬如第一层中三个结点各自的直接后继结点数从左到右分 别是3、2与1个，而第一层的最左结点的三个直接后继结 点的后继结点数也是如此
最 优 搜 索 算 法
最优搜索算法
在每个当前计算结点要执行的计算按是 否处于回溯过程而不同。如处在非回溯 过程，则执行以下几个计算:
(1)确定直接后继结点数
一结点的直接后继点数: 在根结点处r＝6，故q＝3，有三个直接后继结点
缺点
但是由于在搜索过程中要计算中间的判据值，因 此在d很小或d很接近D时，还不如使用穷举法 另外该算法必须使用具有单调性的判据
有时在理论上具有单调性的判据，在实际运用样本计算 时，可能不再具备单调性 因此存在不能保证结果为最优的可能性
8.4.2 次优搜索法
上述分支定界算法虽然比盲目穷举法节 省计算量，但计算量仍可能很大而无法 实现，因此人们还是常用次优搜索法
模式识别
徐蔚然 北京邮电大学信息工程学院
简单回顾
本章讨论的问题
对已有的特征空间进行改造,着重于研究对 样本究竟用什么样的度量方法更好 譬如用三种度量来描述苹果与梨
那么是否运用这三种度量是最有效的呢？ 颜色：
这一个指标对区分红苹果与梨很有效 区分黄苹果与梨就会困难得多 即，这个指标就不很有效了
简单回顾
顺序后退法(SBS)
顺序后退法(SBS)
与面一个方法相反，是自上而下的方法 从现有的特征组中每次减去一个不同的特征并计算 其判据，找出这些判据值中之最大值，如此重复下 去直到特征数达到予定数值d为止 与SFS相比，此法计算判据值是在高维特征空间进 行的，因此计算量比较大 此法也可推广至每次剔除r个，称为广义顺序后退法 (GSBS)
增l减r法(l-r法)
前面两种方法的缺点
即一旦特征入选(或剔除)，过程不可逆转
为了克服这种缺点，可采用将这两种方法结 合起来的方法，即增l减r法 原理:对特征组在增加l个特征后，转入一个局 部回溯过程，又用顺序后退法，剔除掉r个特 征 这种方法既可能是“自上而下”方法，也可 能是“自下而上”的，这取决于l与r的数据大 小
顺序前进法(SFS)
优点
顺序前进法与前一小节的单独特征最优化组合相比， 由于考虑了特征之间的相关性，在选择特征时计算 与比较了组合特征的判据值，要比前者好些。
缺点
一旦某一特征被选入，即使由于后加入的特征使它 变为多余，也无法再把它剔除。
该法可推广至每次入选r个特征，而不是一个， 称为广义顺序前进法(GSFS)
增l减r法(l-r法)

筛选剩下的特征组在每一步上都是最优的
“自下而上”: 从零维特征空间开始，逐个 地从D维持征中选择特征，直至达到预定的 维数指标为止。
在每一步都生成最优的特征空间
8.4.1 最优搜索算法
用最少的计算量得到最优的特征组合 “分支定界”算法
能得到最优解的唯一快速算法 属于“自上而下”算法，但是具有回溯功 能，可使所有可能的特征组合都被考虑到。
简单回顾
特征选择和特征提取
两者区别
特征选择: 删掉部分特征 特征提取:通过一种映射，也就是说新的每一个 特征是原有特征的一个函数
简单回顾
类别可分离性判据
特征选择与特征提取的任务是求出一组对 分类最有效的特征 所谓有效是指在特征维数减少到同等水平 时，其分类性能最佳 因此需要有定量分析比较的方法, 判断所得 到的特征维数及所使用特征是否对分类最 有利 这种用以定量检验分类性能的准则称为 类别可分离性判据
降维主要有两种途径
对特征空间的改造、优化、主要的目的是降维，即 把维数高的特征空间改成维数低的特征空间 ，降维 主要有两种途径 特征的选择: 一种是删选掉一些次要的特征
问题在于如何确定特征的重要性，以及如何删选
特征的提取: 另一种方法是使用变换的手段，在 这里主要限定在线性变换的方法上，通过变换来实 现降维
搜索算法
特征选择的含意
由原有D维特征所组成的特征空间中选出若 干个特征，组成描述样本的新特征空间 即从原有的D维空间选取一个d维子空间(d＜ D)，在该子空间中进行模式识别
搜索算法
有两个问题要解决
一个是选择特性的标准
也就是选择前面讨论过的可分离性判据 以这些判据为准则，使所选择的d维子空间具有 最大的可分离性