1、第七章 特征提取与选择121(,)()dijdijkkJx xxJx式中式中xk，是对象不同种类特，是对象不同种类特征的测量值，征的测量值，Jij()表示使表示使用括号中特征时第用括号中特征时第i类与第类与第j类的可分性判据函数。类的可分性判据函数。12121(,)(,)ijdijddJx xxJx xxxab1/22 1/21(,)()()()nkkkd a bababab2()2()11(,)(,)iNiikkkidx adx aN x(),1,2,iikiakN(),1,2,iikixkN1,2,ic()()11iNiikkimxN(1,2,)ic()1ciiimP m()()()111
2、1111iNcccNiiiiikliiiklNmP mmxxNNN2()()()()11()()()iNiiiiikkkidxmxmN22()()111()(,)(1)iiNNiiciklkliiddaaN N()()()()11()()iiNiiiiwkkkiSxmxmN(),1,2,iikixkN2()iiwdTr S22()()111(,)(,)jiNNijijklklijddxxN N 2()()()()111(,)()()jiNNijijijklklklijdxxxxN N(),1,2,iikixkN(),1,2,jjljxlN22()()111111()(,)2jiNNccijij
3、klijklijdxPPdxxN N 2()()()()111111()()()2jiNNccijijijklklijklijdxPPxxxxN N()()()()1111()()iiNcciiiiWiikkiikiSPSPxmxmN()()1()()ciiBiiSP mm mm11()()NTllWBlSxm xmSSN2()WBTdxTr SSTr SiiNPN()()11iNiikkimxN11NllmxN11WBJTr S S2BWSJS3BWTr SJTr S4|WBTWWSSSJSS可以证明可以证明J1、J2与与J4在任何非奇异线性变换下在任何非奇异线性变换下是不变的是不变的，J3
4、与坐标系有关。与坐标系有关。1(|)p x2(|)p x12(|)(|)p xp x(a)(b)1/212ln(|)(|)BJp xp xdx 1/2012()()()expBP ePPJ(受相关定义与应用的启发，构造受相关定义与应用的启发，构造B-判据判据)（比（比JB更广义的判据更广义的判据）1121212ln()()(,;)(;,)()0s1ssCCCnCJp xp xdxJsJs x xxJs 120(|)(|)CJp xp x1221(,)(,1)CCJsJs 1()2CBJJ1221(,)(,1)CCJsJs x121(,)(,)nCnCllJs x xxJs x101212()(
5、)()exp(,;)01ssCP ePPJss（JC不具有不具有三点距三点距离不等式的性质。）离不等式的性质。）12121(,)(,),CnCnnJs x xxJs x xxxknx(|)(|)()ln(|)ln(|)(|)iiijiijjp xp xIxEp xdxp xp x1()()(|)(|)(|)ln(|)(,)(,)Di jjiiijjDijDnJIxIxp xp xp xd xp xJJxx(|)(|)()ln(|)ln(|)(|)jjjijjiip xp xIxEp xdxp xp x11WBJTr S S2BWSJS3BWTr SJTr S12ln(|)(|)(1/2)Bij
6、cJp xp xdxJ 11212ln()()(,;),0s1 1 的那个节点，则转入与当前节点的那个节点，则转入与当前节点左邻的左邻的s s深度的那个节点，使该节点成为当前节点，深度的那个节点，使该节点成为当前节点，按前面的方法沿它最右边的子树继续搜索。按前面的方法沿它最右边的子树继续搜索。在搜索过程中先要判该节点的在搜索过程中先要判该节点的J J值是否比值是否比B B值大。若值大。若不大于不大于B B值，该节点以下的各子节点值，该节点以下的各子节点J J值均不会比值均不会比B B大，大，故无需对该子树继续进行搜索故无需对该子树继续进行搜索。BAB算法算法如果搜索到叶节点，且如果搜索到叶节点
7、，且该叶节点代表的特征的该叶节点代表的特征的可分性判据可分性判据JBJB，则更，则更新界值，即新界值，即B=JB=J；否则；否则不更新界值。不更新界值。到达叶节点后，要向上回溯。重复上述过程，直到到达叶节点后，要向上回溯。重复上述过程，直到J J B B为止。而对应当前（最大）界值为止。而对应当前（最大）界值B B的叶节点对的叶节点对应的应的d d个特征组合就是所求的最优的选择。个特征组合就是所求的最优的选择。BABBAB算法效率高的原因算法效率高的原因：(1)(1)在构造搜索树时，同一父节点的各子树的右边的在构造搜索树时，同一父节点的各子树的右边的边要比左边的少，即树的结构右边比左边简单；边
8、要比左边的少，即树的结构右边比左边简单；(2)(2)在同一级中按最小的在同一级中按最小的J J值从左到右挑选舍弃的特值从左到右挑选舍弃的特征，即节点的征，即节点的J J值是值是左小右大左小右大，而搜索过程是从，而搜索过程是从右至左进行的；右至左进行的；(3)(3)因因J J的的单调性单调性，若树上某节点，若树上某节点A A的可分性判据值的可分性判据值 J JA A B B ，则，则A A子树上各节点的子树上各节点的J J值都不会大于值都不会大于B B，因，因此不需要搜索此不需要搜索A A子树。子树。从上可知，有很多特征组合不需计算仍能求得全局从上可知，有很多特征组合不需计算仍能求得全局最优解。最优解。谢谢聆听！你我同行，共同进步。
