第七章特征提取与选择.ppt

《第七章特征提取与选择.ppt》由会员分享，可在线阅读，更多相关《第七章特征提取与选择.ppt（35页珍藏版）》请在第壹文秘上搜索。

1、目的目的：(max)1212(,)(,),Jnmxx xxyy yymn7.1 7.1 概概 述述n准则准则类别可分性判据类别可分性判据:刻划特征对分类的贡献。刻划特征对分类的贡献。n构造的可分性判据构造的可分性判据Jij应满足下列要求：应满足下列要求：(1)与误分概率与误分概率P(e)(或误分概率的上界、下界或误分概率的上界、下界)有有单调关系，单调关系，Jij最大值时，最大值时，P(e)最小。最小。(2)当特征相互独立时，判据有当特征相互独立时，判据有可加性可加性，即，即121(,)()dijdijkkJx xxJx式中式中xk，是对象不同种类特，是对象不同种类特征的测量值，征的测量值，J

2、ij()表示使表示使用括号中特征时第用括号中特征时第i类与第类与第j类的可分性判据函数。类的可分性判据函数。(3)判据具有判据具有“距离距离”的某些特性：的某些特性：Jij0，当当ij 时时 Jij=0，当当i=j 时时 Jij=Jji12121(,)(,)ijdijddJx xxJx xxx7.2.1 基于几何距离的可分性判据基于几何距离的可分性判据 ab1/22 1/21(,)()()()nkkkd a bababab2()2()11(,)(,)iNiikkkidx adx aN x(),1,2,iikiakN(三三)类内及总体的均值矢量类内及总体的均值矢量(),1,2,iikixkN1,

3、2,ic()()11iNiikkimxN(1,2,)ic()1ciiimP m()()()1111111iNcccNiiiiikliiiklNmP mmxxNNN(四四)类内距离类内距离 n类内均方欧氏距离为类内均方欧氏距离为类内均方距离也可定义为类内均方距离也可定义为(五五)类内离差（散布）矩阵类内离差（散布）矩阵(Scatter)类内离差矩阵定义为类内离差矩阵定义为类内离差矩阵类内离差矩阵SWi的迹等于类内的均方欧氏距离，即的迹等于类内的均方欧氏距离，即类内离差矩阵表示各类模式在类的均值矢量周围的散类内离差矩阵表示各类模式在类的均值矢量周围的散布情况。布情况。2()()()()11()()

4、()iNiiiiikkkidxmxmN22()()111()(,)(1)iiNNiiciklkliiddaaN N()()()()11()()iiNiiiiwkkkiSxmxmN(),1,2,iikixkN2()iiwdTr S(六六)两类之间的距离两类之间的距离当式中的距离取欧氏距离时当式中的距离取欧氏距离时,有有(七七)各类模式之间的总的均方距离各类模式之间的总的均方距离当取欧氏距离时当取欧氏距离时22()()111(,)(,)jiNNijijklklijddxxN N 2()()()()111(,)()()jiNNijijijklklklijdxxxxN N(),1,2,iikixkN(

5、),1,2,jjljxlN22()()111111()(,)2jiNNccijijklijklijdxPPdxxN N 2()()()()111111()()()2jiNNccijijijklklijklijdxPPxxxxN N(八八)多类情况下总的类内、类间及总体离差（散布）矩阵多类情况下总的类内、类间及总体离差（散布）矩阵 总的类内离差矩阵定义为总的类内离差矩阵定义为总的类间离差矩阵定义为总的类间离差矩阵定义为总体离差矩阵为总体离差矩阵为 易导出易导出 ()()()()1111()()iiNcciiiiWiikkiikiSPSPxmxmN()()1()()ciiBiiSP mm mm11

6、()()NTllWBlSxm xmSSN2()WBTdxTr SSTr SiiNPN()()11iNiikkimxN11NllmxN可分性判据可分性判据 （类内紧，类间开（类内紧，类间开）11WBJTr S S2BWSJS3BWTr SJTr S4|WBTWWSSSJSS可以证明可以证明J1、J2与与J4在任何非奇异线性变换下在任何非奇异线性变换下是不变的是不变的，J3与坐标系有关。与坐标系有关。7.2.2 基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据 用两类概密函数的用两类概密函数的重迭程度重迭程度来度量可分性，构造基于来度量可分性，构造基于类概密的可分性判据类概密的可分

7、性判据Jp，它，它应满足：应满足：(1)Jp 0；(2)当两类密度函数完全不重迭时，当两类密度函数完全不重迭时，Jp=max；(3)当两类密度函数完全重合时，当两类密度函数完全重合时，Jp=0；(4)相对两个概密具有相对两个概密具有“对称性对称性”。1(|)p x2(|)p x12(|)(|)p xp x(a)(b)(一一)Bhattacharyya判据判据(JB)在最小误分概率准则下，在最小误分概率准则下，误分概率误分概率1/212ln(|)(|)BJp xp xdx 1/2012()()()expBP ePPJ(受相关定义与应用的启发，构造受相关定义与应用的启发，构造B-判据判据)(二二)

8、Chernoff判据判据(JC)(1)(1)对一切对一切0s10s1，JcJc 0 0；(2)(2)对一切对一切0s10s1，;(3)(3)当参数当参数s s和和(1-s)(1-s)互调时互调时，才有对称性，即，才有对称性，即（比（比JB更广义的判据更广义的判据）1121212ln()()(,;)(;,)()0s1ssCCCnCJp xp xdxJsJs x xxJs 120(|)(|)CJp xp x1221(,)(,1)CCJsJs 1()2CBJJ(二二)Chernoff判据判据(JC)(4)(4)当当 各分量各分量x1,x2,xn相互独立时，相互独立时，(5)(5)当当 各分量各分量x

9、1,x2,xn相互独立时，相互独立时，(6)(6)最小误分概率最小误分概率1221(,)(,1)CCJsJs x121(,)(,)nCnCllJs x xxJs x101212()()()exp(,;)01ssCP ePPJss（JC不具有不具有三点距三点距离不等式的性质。）离不等式的性质。）12121(,)(,),CnCnnJs x xxJs x xxxknx(三三)散度散度JD(Divergence)(|)(|)()ln(|)ln(|)(|)iiijiijjp xp xIxEp xdxp xp x1()()(|)(|)(|)ln(|)(,)(,)Di jjiiijjDijDnJIxIxp

10、xp xp xd xp xJJxx(|)(|)()ln(|)ln(|)(|)jjjijjiip xp xIxEp xdxp xp xn几何可分性判据几何可分性判据n类概率密度可分性判据类概率密度可分性判据(一一)Bhattacharyya判据判据(JB)(二二)Chernoff判据判据(JC)(三三)散度散度JD11WBJTr S S2BWSJS3BWTr SJTr S12ln(|)(|)(1/2)BijcJp xp xdxJ 11212ln()()(,;),0s1 1 的那个节点，则转入与当前节点的那个节点，则转入与当前节点左邻的左邻的s s深度的那个节点，使该节点成为当前节点，深度的那个节

11、点，使该节点成为当前节点，按前面的方法沿它最右边的子树继续搜索。按前面的方法沿它最右边的子树继续搜索。在搜索过程中先要判该节点的在搜索过程中先要判该节点的J J值是否比值是否比B B值大。若值大。若不大于不大于B B值，该节点以下的各子节点值，该节点以下的各子节点J J值均不会比值均不会比B B大，大，故无需对该子树继续进行搜索故无需对该子树继续进行搜索。BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法如果搜索到叶节点，且如果搜索到叶节点，且该叶节点代表的特征的该叶节点代表的特征的可分性判据可分性判据JBJB，则更，则更新界值，即新界值，即B=JB=J；否则；否则不更新界值。不更新界

12、值。到达叶节点后，要向上回溯。重复上述过程，直到到达叶节点后，要向上回溯。重复上述过程，直到J J B B为止。而对应当前（最大）界值为止。而对应当前（最大）界值B B的叶节点对的叶节点对应的应的d d个特征组合就是所求的最优的选择。个特征组合就是所求的最优的选择。BABBAB算法效率高的原因算法效率高的原因：(1)(1)在构造搜索树时，同一父节点的各子树的右边的在构造搜索树时，同一父节点的各子树的右边的边要比左边的少，即树的结构右边比左边简单；边要比左边的少，即树的结构右边比左边简单；(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子树。子树。从上可知，有很多特征组合不需计算仍能求得全局从上可知，有很多特征组合不需计算仍能求得全局最优解。最优解。