模式识别-特征选择

1、提纲n图像的特征提取图像的特征提取n模式类别可分性度量模式类别可分性度量n基于类可分性度量的特征提取与选择基于类可分性度量的特征提取与选择n离散离散K-LK-L变换及其在特征提取与选择中变换及其在特征提取与选择中的应用的应用n特征选择中的直接挑选法特征选择中的直接挑选法一、图像的特征提取一、图像的特征提取特征提取与选择特征提取与选择 模式识别的三大核心问题模式识别的三大核心问题: :特征提取与选择特征提取与选择图像的特征提取图像的特征提取特征数据采集特征数据采集分类识别分类识别特征提取与选择特征提取与选择 分类识别的正确率取决于对象的表示、训练学习和分类识别算法，我们在前面的学习中详细讨论了后

2、两方面的内容。本章介绍的特征提取与选择问题则是对象表示的一个关键问题。 通常在得到实际对象的若干具体特征之后，通常在得到实际对象的若干具体特征之后，再再由由这些这些原始特征产生原始特征产生出对分类识别出对分类识别最有效、数最有效、数目最少的特征目最少的特征，这就是特征提取与选择的任务。，这就是特征提取与选择的任务。从本质上讲，我们的目的是使从本质上讲，我们的目的是使在最小维数特征空在最小维数特征空间间中异类模式点相距较远（中异类模式点相距较远（类间距离较大类间距离较大），而），而同类模式点相距较近（同类模式点相距较近（类内距离较小类内距离较小）。）。 特征提取与选择特征提取与选择图像的特征提取

3、图像的特征提取图像的特征提取图像的特征提取两个基本途径两个基本途径主要方法有：分支定界法、用回归建模技术确定相关特征等方法。（1 1）直接选择法：）直接选择法：当实际用于分类识别的特征数目d 确定后，直接从已获得的n 个原始特征中选出d 个特征 ，使可分性判据J 的值满足下式：dxxx,21J x xxJ xxxdiiid1212,max,式中 是n 个原始特征中的任意d 个特征，上式表示直接寻找n 维特征空间中的d 维子空间。idiixxx,21(max)121212( ,)(,) ,Jndinxx xxyy yydn yx xx（2 2）变换法：）变换法：在使判据J 取最大的目标下，对n

4、个原始特征进行变换降维，即对原n 维特征空间进行坐标变换，然后再取子空间。主要方法有：基于可分性判据的特征选择、基于误判概率的特征选择、离散K-L变换法(DKLT)、基于决策界的特征选择等方法。图像的特征提取图像的特征提取两个基本途径两个基本途径(max)1212( ,)( )(,), Jndxx xxyh xy yydn(c)是具有分类能力的特征，故选(c)，扔掉(a) 、 (b) 。BA解：法1 特征选择：测量三个结构特征 (a) 周长 (b) 面积 (c)两个互相垂直的内径比 特征选择：一般根据物理特征或结构特征进行压缩。 分析：例：特征选择与特征提取的区别：对一个条形和圆进行识别。 当

5、”模式”在空间中发生移动、旋转、缩放时，特征值应保持不变，保证仍可得到同样的识别效果。法2： 特征抽取：测量物体向两个坐标轴的投影值，则A、B各有2个值域区间。可以看出，两个物体的投影有重叠，直接使用投影值无法将两者区分开。 分析：将坐标系按逆时针方向做一旋转变化，或物体按顺时针方向变，并适当平移等。根据物体在 轴上投影的坐标值的正负可区分两个物体。2x特征提取，一般用数学的方法进行压缩。 BA2x1x22Bx22Ax12Bx12Ax11Bx11Ax21Bx21AxA2x1x2x1x二、模式类别可分性度量二、模式类别可分性度量特征提取与选择特征提取与选择模式类别可分性度量模式类别可分性度量 为

6、确立特征提取和选择的准则：引入类别可分性为确立特征提取和选择的准则：引入类别可分性判据，来表征特征对分类的贡献。为此希望所构造判据，来表征特征对分类的贡献。为此希望所构造的可分性判据的可分性判据J满足下列要求：满足下列要求：构造可分性判据构造可分性判据(1)可分性判据J与误判概率P(e) (或误分概率的上界、下界)有单调关系，J最大时，P(e)最小。(2)当特征相互独立时，判据有可加性 Jx xxJxi jdi jkdk(,)()121式中，x xxd12,是对不同种类特征的测量值，Ji j( ) 表示使用括号中特征(组)时第i 类与第j类可分性判据函数。(3) 判据具有“距离”的某些特性Ji

7、 j 0，当，当ij时；时；Ji j 0，当，当ij时；时；JJi jji(4) 对特征数目是单调不减，即加入新的特征后，判据值不减。 Jx xxJx xxxi jdi jdd(,)(,)12121模式类别可分性度量模式类别可分性度量构造可分性判据构造可分性判据值得注意的是：对构造可分性判据J的要求，“单调性”、“叠加性”、“距离性”、“单调不减性”。在实际应用并不一定能同时具备，但并不影响它在实际使用中的价值。 模式类别可分性度量模式类别可分性度量构造可分性判据构造可分性判据基于几何距离的可分性判据基于几何距离的可分性判据基于距离的可分性度量 一般来讲，不同类的模式可以被区分是由于它们所属类

8、别在特征空间中的类域是不同的区域。显然，区域重叠的部分越小或完全没有重叠，类别的可分性就越好。因此可以用距离或离差测度（散度）来构造类别的可分性判据J。 模式类别可分性度量模式类别可分性度量(一) 点与点的距离 d a babababkkkn( , )() ()()/T1 2211 2(二) 点到点集的距离),(1) ,()(12)(2ikNkiikaxdNaxdi用均方欧氏距离表示基于距离的可分性度量i表示点集的序号,一共有Ni个点点X到点集中所有点的距离平方和求平均(三) 类内及总体的均值矢量 ciiimPm1)(各类模式的总体均值矢量 iNkikiixNm1)()(1类的均值矢量： ci

9、, 2 , 1 Pi为相应类的先验概率，当用统计量代替先验概率时，总体均值矢量可表示为：NllciNkikiciiiciixNxNmNNmPmi111)()(1)(111基于距离的可分性度量某一类的样本集的中心(重心)全体样本的中心(重心)(四) 类内距离 )()(1)()()(T)()(12iikiikNkiimxmxNdi类内均方欧氏距离 类内均方距离也可定义为： iiNkNlilikiiicxxdNNd11)()(22),() 1(1)(五) 类内离差矩阵 T)()()()(1)(1iikiikNkimxmxNSii)(2iSTrdi显然显然12121 122.nnnnaaaaaa aa

10、 aa aa11 12112122221212nnnnnnnnaa aa aa aaa aa aa aaaaaa aa aa a其中其中“Tr”表示矩阵的迹（对角线元素的和）表示矩阵的迹（对角线元素的和）基于距离的可分性度量一类样本每一点到类中心的距离的平方和求平均(五) 类内离差矩阵(续) T)()()()(1)(1iikiikNkimxmxNSii( )( )iiE xm( )( )( )( )( )T( )( )( )( )( )( )11121( )( )( )( )( )( )21222( )( )( )( )( )( )12()()(,)(,)(,)(,)(,)(,)(,)(,)(

11、,)iiiiiiiiiiiiniiiiiiniiiiiinnnnSExE xxE xCov xxCov xxCov xxCov xxCov xxCov xxCov xxCov xxCov xx222212()()()()iiinid显然显然类内离差矩阵表类内离差矩阵表示各类模式在类示各类模式在类的均值矢量周围的均值矢量周围的散布情况。的散布情况。 基于距离的可分性度量协方差(六) 两类之间的距离 ( )( )111(,)(,)jiNNijijklklijdd xxN N 基于距离的可分性度量两类样本之间任意连线的平均值两类样本之间任意连线的平均平方和2( )( )T( )( )11()() (

12、)iNiiiiikkkidxmxmN类内均方欧氏距离2( )( )T( )( )111(,)() ()jiNNijijijklklklijdxxxxN N (六) 两类之间的距离 ( )( )111(,)(,)jiNNijijklklijdd xxN N (七) 各类模式之间的总的均方距离 基于距离的可分性度量两类样本之间任意连线的平均值两类样本之间任意连线的平均平方和多类之间,两两求类间距离的加权和2( )( )T( )( )111(,)() ()jiNNijijijklklklijdxxxxN N 22( )( )111111( )(,)2jiNNccijijklijklijdxPPdxx

13、N N (六) 两类之间的距离 ( )( )111(,)(,)jiNNijijklklijdd xxN N 2( )( )T( )( )111(,)() ()jiNNijijijklklklijdxxxxN N (七) 各类模式之间的总的均方距离 22( )( )111111( )(,)2jiNNccijijklijklijdxPPdxxN N 当取欧氏距离时，总的均方距离为)()(121)()()(11T)()(112jlikNkNljlikjicjjciixxxxNNPPxdij基于距离的可分性度量两类样本之间任意连线的平均值两类样本之间任意连线的平均平方和多类之间,两两求类间距离的加权和

14、(八) 多类情况下总的类内、类间及总体离差矩阵 iiNkiikiikiciiciiWmxmxNPSPS1T)()()()(11)(1总的类内离差矩阵总的类内离差矩阵ciiiiBmmmmPS1T)()()(总的类间离差矩阵总的类间离差矩阵T)()()()(1)(1iikiikNkimxmxNSii类内离类内离差矩阵差矩阵 基于距离的可分性度量类协方差协方差加权和(八) 多类情况下总的类内、类间及总体离差矩阵（续） 总体离差矩阵总体离差矩阵 BWNlllTSSmxmxNS1T)(1( )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()(

15、)(基于距离的可分性度量不分类的样本协方差( )( )( )( )T( )( )T111( )( )( )( )T( )( )T111()()()()1()()()()iiNcciiiiiiWBikkiikiiNciiiiiiikkikiSSPxmxmP mm mmNPxmxmmm mmNTTTTTTT()()()()ABABABABAAABBABB( )( )T( )( )T( )( )T( )( )T11( )( )T( )T( )TT11iNciiiiiiiiWBikkkkikiciiiiiiSSPxxxmm xm mNP m mm mmmmm (八) 多类情况下总的类内、类间及总体离差

16、矩阵（续） 总体离差矩阵总体离差矩阵 BWNlllTSSmxmxNS1T)(1基于距离的可分性度量不分类的样本协方差( )( )T( )( )T( )( )T( )( )T11( )( )T( )T( )TT11iNciiiiiiiiWBikkkkikiciiiiiiSSPxxxmm xm mNP m mm mmmmm T( )( )T( )( )T( )( )T( )( )T( )( )( )( )T1111( )( )T( )( )T11111,1iiiiiNNNNiiiiiiiiiiiikkkkkkkkiiiiNiiiikixmxmm mm xmxm mNNNNm mm mN( )( )

17、T( )T( )TT11( )( )T( )T( )TT1111iiNciiiiWBikkikiNciiiiikkkkikiSSPxxm mmmmmNPxxxmmxmmN (八) 多类情况下总的类内、类间及总体离差矩阵（续） 总体离差矩阵总体离差矩阵 BWNlllTSSmxmxNS1T)(1基于距离的可分性度量不分类的样本协方差TTTTTTT()()()()ABABABABAAABBABB( )( )TT11111()()()()iNcNiiWBikkllTikliSSPxm xmxm xmSNN( )( )T( )T( )TT11( )( )T( )T( )TT1111iiNciiiiWBi

18、kkikiNciiiiikkkkikiSSPxxm mmmmmNPxxxmmxmmN (八) 多类情况下总的类内、类间及总体离差矩阵（续） 总体离差矩阵总体离差矩阵 BWNlllTSSmxmxNS1T)(1基于距离的可分性度量222212( )WBTndxTr SSTr ST111212122212( )( )( ,)( ,)( ,)(,)(,)(,)(,)(,)(,)TnnnnnnSExE xxE xCov x xCov x xCov x xCov x xCov x xCov x xCov xxCov xxCov xx不分类的样本协方差JTr SSWB11JSSBW2lnJTr STr SB

19、W3JSSSSSWBWTW4SW、SBST构造不同的可分性判据：可以用、和J1、J2J4J3可以证明在任何非奇异线性变换下与坐标系有关。是不变的，基于距离的可分性度量类间类间类内类内类间类间类内类内类间类间类内类内总体总体类内类内标准差基于类的概率密度函数的可分性判据考虑两类问题。上图是一维的两类概率分布密度。 (a) 表示两类是完全可分的。(b)是完全不可分的。 可用两类概密函数的重叠程度来度量可分性，可用两类概密函数的重叠程度来度量可分性，构造基于类概密的可分性判据。此处的所谓重叠构造基于类概密的可分性判据。此处的所谓重叠程度是指两个概密函数相似的程度。程度是指两个概密函数相似的程度。 由

20、类概密构造的可分性判据由类概密构造的可分性判据Jp应满足应满足: : (1)(1)Jp 0； (2)(2)当两类概密函数完全不重叠时，当两类概密函数完全不重叠时，Jp max； (3)(3)当两类概密函数完全重合时，当两类概密函数完全重合时，Jp 0； (4)(4)相对于两个概密具有相对于两个概密具有 “对称性对称性”。基于类的概率密度函数的可分性判据( (一一) ) BhattacharyyaBhattacharyya 判据判据( (J JB B) )受相关概念与应用的启发，我们可以构造B- -判据，它的计算式为基于类的概率密度函数的可分性判据1/212ln() ()BJp xp xdx 满

21、足Jij=0满足对称性Jij=Jji1/212121() ()()()12p xp xdxp xp xdx( (一一) ) BhattacharyyaBhattacharyya 判据判据( (J JB B) )受相关概念与应用的启发，我们可以构造B- -判据，它的计算式为 式中表示特征空间。在最小误判概率准则下，误判概率有 基于类的概率密度函数的可分性判据1/212ln() ()BJp xp xdx 1/2012( )() ()expBP ePPJ满足对称性Jij=Jji12()()ln10Bp xp xJ 1212+()(), () ()1,ln0Bp xp xp xp xJ 与基本不重叠证

22、明：设P e( )为误分概率，则最小误分概率为：基于类的概率密度函数的可分性判据210112211221/211221/21/212121/212( )min( )min()()()()min() (), () ()() () () ()() ()() ()() ()expBP eP ePp xdxPp xdxPp xPp xdxPp xPp xdxPPp xp xdxPPJ（二）（二） Chernoff 判据判据 ( () )我们可以构造比我们可以构造比更一般的判据，称其为更一般的判据，称其为其定义式为其定义式为判据，判据，1121212ln()()( ;,)(,; )( ) 0s0)因为，

23、当 0 s 1 时 f(s) = -asb1-s(ln(a)-ln(b)2 0)因为，当 0 s 1 时 f(s) = -asb1-s(ln(a)-ln(b)2 0, 0 s 1 )由该不等式有：xdxpxpsJssc12121)|()|(ln),(1212ln ( |)(1) ( |)ln( |)+(1)( |)=ln(1)0sp xs p xdxs p xdxsp xdxss 01,0CSJ对于一切Jc Jc 性质（性质（2 2）证明：）证明：只考虑连续的情况：由前面的证明可知:要Jc=0,必须有实际上也就是前面的 sa+(1-s)b = asb1-s因为f(s)=0 ，使f(s)=0的充

24、要条件是a=b 1201,=0(|)(|)CSJp Xp X对于一切11212( |)( |)=( |)(1) ( |)ssp xp xsp xs p x111( )(1)lnlnssssssf ssas ba babaa babb求f(s)极值点1( )lnln0ssf saba bab111,0lnlnlnlnln0sssssbka kaba babakaa kaaka设11ln01ln11ln1ln1lnsssssakaakkakakkkkkkkkkkkk Jc Jc 性质（性质（2 2）证明：）证明：只考虑连续的情况：由前面的证明可知:要Jc=0,必须有实际上也就是前面的 sa+(1-

25、s)b = asb1-s因为f(s)=0 ，使f(s)=0的充要条件是a=b )|()|(21xpxpJC=0 1201,=0(|)(|)CSJp Xp X对于一切11212( |)( |)=( |)(1) ( |)ssp xp xsp xs p x,1ln,0sbkakkkk k设有1,10,ln0skkkkk如果,1,( )0,( )=0kabf sf s所以 有且只有即时有最小值 absa+(1-s)b = asb1-sJc Jc 性质（性质（6 6）证明：）证明：设P(e)为最小误分概率，则：P eP ePp xdxPp xdxPp xPp xdx01122112221( )min(

26、)min()()()()min() (),() ()利用不等式 ，由上式进一步可得： 1min,0,0,01ssa ba babsP ePPp xp xdxPPJssssssC0121121121( )()()()()()()exp 101212()()exp,;(01)SSCP ePPJss 由JB和JC的定义知：JB=JC(1/2)对两类都是正态分布正态分布情况: p xN mC() (,)( )111p xN mC() (,)( )222112(1)(2) T(1)(2)12112(1)11(1)()(1)()ln22Csss CsCJss mms CsCmmCC112(1)(2)T(1

27、)(2)121/21/2121()1112()()()ln2822BCCCCCJJsmmmmCC基于类的概率密度函数的可分性判据112ln()()ssCJp xp xdx 11/2/211( |)exp()()22Tiiiidip xxmCxmC当12CCC时，)()(81)()(1 (21)2()1(1T)2()1()2()1(1T)2()1(mmCmmJmmCmmssJBC基于类的概率密度函数的可分性判据Jp xp xp xdxCs ln()()()122实际上 这就启发我们运用两个概密的比或差来描述两个概密重迭或相似的程度。 xdxpxpJssC121)()(ln可以写成： 基于类的概率

28、密度函数的可分性判据( (三三) )散度散度J JD D (Divergence) (Divergence)i类对j类的平均可分性信息为： ( |)( |)( )ln( |)ln( |)( |)iiijijjp xp xIxEp xdxp xp x( |)( |)( )ln( |)ln( |)( |)jjjijiip xp xIxEp xdxp xp xj 对i 类的平均可分性信息为：基于类的概率密度函数的可分性判据似然比( (三三) )散度散度J JD D (Divergence) (Divergence)i类对j类的平均可分性信息为： 基于类的概率密度函数的可分性判据11/2/211( |

29、)exp()()22Tiiiidip xxCxC11( |)111ln( |)222TTjiiiijjjjiCp xTr CxxTr Cxxp xC( |)( )( |)ln( |)iijijp xIxp xdxp x1111111( )( |)ln22211ln( |)221( |)2TTjijiiiijjjiTjiiiiiTjjjiCIxp xTr CxxTr CxxdxCCTr Cxxp xdxCTr Cxxp xdx( (三三) )散度散度J JD D (Divergence) (Divergence)i类对j类的平均可分性信息为： 基于类的概率密度函数的可分性判据11/2/211(

30、|)exp()()22Tiiiidip xxCxC( |)( )( |)ln( |)iijijp xIxp xdxp x111111111( )ln( |)221( |)2111ln( |)222111ln222TjijiiiiiTjjjiTjiijiijiijiiTjijijijijiCIxTr Cxxp xdxCTr Cxxp xdxCTr C CTr Cxxp xdxCCTr CCCTr CC1( )( )( |) ( |)( |)ln( |)(,)( ,)Di jjiiijjdefdefDijDnJIxIxp xp xp xd xp xJJxx 对于i和j两类总的平均可分性信息称为散度

31、，其定义为两类平均可分性信息之和，即 ( (三三) )散度散度JD (Divergence)JD (Divergence)基于类的概率密度函数的可分性判据当两类都是正态分布正态分布时： 11T11112() ()()22DijjiijijijJTr C CCCICC当C Ci i=C=Cj j=C=C时T1()()8DijijBJCJ基于类的概率密度函数的可分性判据111111( )ln222TjijijijijijiCIxTr CCCTr CC1111( )( )1122Di jjiTijjiijijijJIxIxTrCCCCTrCC,TTTr BAA B AB皆向量散度具有如下性质： Jx

32、xxJxxxxknDkDkk(,),121121() (1) JD 0；(2) 对称性: JD(1 , 2)= JD(2 , 1); Jp xp xD012()()(3) Jx xxJxknDkDjjk(,)()121 (4) 当x 各分量x1,x2,xn相互独立时，(具有可加性) (5) 当x各分量x1,x2,xn相互独立时，(对特征数目单调不减)基于类的概率密度函数的可分性判据一般情况下，散度与误分概率(或其上下界)之间的直接解析关系很难得到，但实验可以证明它们之间存在着单调关系。例如两类都是正态分布，且有相同的协方差阵时， 是 的单调减函数。P e0( )JDJDP eydyJD0212

33、122( )exp当两类先验概率相等且为具有相同协方差的正态分布时，则最小误分概率与 的关系为：基于类的概率密度函数的可分性判据对于c类问题类问题，可采用平均B-判据、C-判据、D-判据： cicijjiBjiBJPPJ11),()()( cicijjiCjiCJPPJ11),()()( cicijjiDjiDJPPJ11),()()(由JB、JC、JD的定义式结构以及它们与误分概率的关系可以知道，所选取的特征矢量应使所对应的JB、JC 、JD尽量大，这样可分性就较好。基于类的概率密度函数的可分性判据大盖小问题大盖小问题 在特征空间中，若有某两类间的在特征空间中，若有某两类间的JB、JC或或J

34、D很大很大，可使平均判据变大，这样就掩盖了某些类对的判据，可使平均判据变大，这样就掩盖了某些类对的判据值较小的情况存在，从而可能降低总的分类正确率，值较小的情况存在，从而可能降低总的分类正确率，即所谓的即所谓的大盖小问题大盖小问题。为改善这种情况，可对每个类。为改善这种情况，可对每个类对的判据采用变换的方法，使对小的判据较敏感。例对的判据采用变换的方法，使对小的判据较敏感。例如，对如，对JD ，可采用变换，可采用变换8),(exp1),(jiDjiDJJ8),(exp1),(jiDjiDJJ这样，当i和j两类模式相距很远时，JD(i,j)变得很大，但 也只能接近于1。但对于散度JD(i,j)

35、小的情况， 又变得较敏感。于是，总的平均(变换)判据为 ),(jiDJ),(jiDJ),()()(11jicicijDjiDJPPJ 基于类的概率密度函数的可分性判据 cicijjiDjiDJPPJ11),()()(同样对于JB，两类问题与多类问题的平均判据分别为：1 2(,)22exp(,)BijBijJJ 两类：11() ()(,)ccBijBijij iJPPJ C类平均判据：基于类的概率密度函数的可分性判据1/212ln() ()BJp xp xdx 1/21/212(,)22() ()BijJp xp xdx 0(,)2BijJ 基于后验概率的可分性判据在信息论中，熵(Entropy

36、)表示不确定性，熵越大不确定性越大。可以借用熵的概念来描述各类的可分性。pxi()对于c类问题，给定各类的后验概率 可以写成如下形式：12121212()()()defccccpxpxpxppp熵的定义：11( )( )log()log()ccdefiiiiiiH xH ppppxpx 由洛必达法则知：当 时pi 00logiipp熵的主要性质：熵的主要性质：(1) ，即 是有下界的非负数。当且仅当某个i 有pi =1而其余的 时等号成立，即确定场熵最小。H p( ) 0H p( )pjij0()例如：显然这时能完全正确的分类识别 pxi()1pxjij(), 0基于后验概率的可分性判据熵的主

37、要性质：熵的主要性质：(2) (2) ，即，即 有上界。当且仅当有上界。当且仅当 时等号成立，即时等号成立，即等概率场熵最大，等概率场熵最大，识别最困难。识别最困难。12(,)logcH ppcH p( )1(1,2, )ipicC(3) (3) 是是 的连续上凸函数。的连续上凸函数。H p( )p基于后验概率的可分性判据(4)(4)2122112132121,)(),(),(ppppppHppppppHpppHcc121231212121122121212312121212121212123121211(,)(),()loglogloglog()logloglogloglogcciiicii

38、ippH pppppp Hpppppppppppppppppppppppppppppppppppppppp 12221212311212logloglog(,)cciiiiciippppppppppH p pppppp 熵的主要性质：熵的主要性质：(2) (2) ，即，即 有上界。当且仅当有上界。当且仅当 时等号成立，即时等号成立，即等概率场熵最大，等概率场熵最大，识别最困难。识别最困难。12(,)logcH ppcH p( )1(1,2, )ipicC(3) (3) 是是 的连续上凸函数。的连续上凸函数。H p( )p基于后验概率的可分性判据(4)(4)2122112132121,)(),(

39、),(ppppppHppppppHpppHcc其中021 pp说明说明当类别较少时，分类识别的不确定性变小当类别较少时，分类识别的不确定性变小。 从特征选择角度看，我们从特征选择角度看，我们应选择使熵最小的那些特征用于应选择使熵最小的那些特征用于分类分类即选用具有最小不确定性的特征进行分类是有益的。即选用具有最小不确定性的特征进行分类是有益的。 12123(,)(,)ccH p ppH pppp使熵最小的特征利于分类，取熵的期望：使熵最小的特征利于分类，取熵的期望：min)|(log)|(1xPxPEJiciixH广义熵广义熵（具有熵的性质，利于计算）定义为定义为:()11121(,)(21)

40、 (1)cciiHp ppp式中0， 1。不同的值可得不同的可分性度量。ciiipppH1)1(log)(当当1时，由洛必达法则可得时，由洛必达法则可得Shannon熵熵ciippH12)2(1 2)(当当 =2时，可得平方熵时，可得平方熵使用使用 或或 判据进行特征提取与选择时，目标是使判据进行特征提取与选择时，目标是使HJ()minHHJJ或同理，我们亦可用点熵在整个特征空间的概率平均同理，我们亦可用点熵在整个特征空间的概率平均()12(), (), ()HxcJEHpxpxpx作为可分性判据。作为可分性判据。基于后验概率的可分性判据()HJ三、基于类可分性度量的三、基于类可分性度量的特征

41、提取与选择特征提取与选择特征提取与选择特征提取与选择对某类模式：压缩模式向量的维数。 对多类分类：压缩维数；保留类别间的鉴别信息，突出可分性。 特征提取的目的：特征提取操作方法：m1 mn n1 (m n)注意：维数降低后，在新的m维空间里各模式类之间的分布 规律应至少保持不变或更优化。基于类可分性度量的特征提取与选择YW X12(,)mYy yy12( ,)nXx xx原始特征二次特征特征提取矩阵变换矩阵设和分别为原始特征空间中的类内和类间离差矩阵， 和分别为变换特征空间中的类内和类间离差矩阵，可知 基于类可分性度量的特征提取与选择WSBS*WS*BS*TWWTBBSW S WSW S W(

42、 )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()()( )( )( )( )T11( )( )( )( )T11( )( )( )T( )T111()()1()()1()()iiiNcTTiiiiWikkikiNcTiiiiikkikiNcTiTiiiikkikiW S WWPxmxmWNPWxmxmWNPW xW mxWmWN设和分别为原始特征空间中的类内和类间离差矩阵， 和分别为变换特征空间中的类内和类间离差矩阵，可知 基于类可分性度量的特征提取与选择WSBS*WS*BS*TWWTBBSW S WSW S W( )( )(

43、)T( )T111()()iNcTTiTiiiWikkikiW S WPW xW mxWmWNTYW XTTYX WTYXmW m TTYXmmW ( )( )T( )( )T*111()() =iNciiTiiWiWkyyikiW S WPymymSN ( )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()()(设和分别为原始特征空间中的类内和类间离差矩阵， 和分别为变换特征空间中的类内和类间离差矩阵，可知 根据 J1=TrSW-1SBmax或 J4=|SW+SB|/|SB|=|ST|/|SB| max求变换矩阵 W。基于类可分性

44、度量的特征提取与选择WSBS*WS*BS*TWWTBBSW S WSW S W协方差加权和nn对称阵mmnn对称阵( )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()()( 在变换域中J1为 由线性代数可知，对矩阵作相似变换其迹不变，一个方阵的迹等于它的所有特征值之和。设 为正交阵，用 对对称阵 作相似变换使其成为对角阵 12111120(,)0eWBeeWBennWSS WW SS Wdiag niieBWeBWWSSWTrSSTrJ1111矩阵迹形式的判据11*1TTWBWBJWTrSSTrW S WW S WeWeW1WBS

45、 S其中，i (i=1,2,n)为 的特征值， 的列矢量 为相应于i的特征矢量。由上式可得。eW1WBS SiW1WBS SJTr SSWB111eeWW作变换 ，这时对于给定的d所得到的 达最大值。此方法对J3 =TrSB/TrSW也适用。 转换步骤：转换步骤：使使We的列矢量的排列已作适当调整，使的列矢量的排列已作适当调整，使S SW W-1-1S SB B的的特征值特征值 1 1 2 2 n n 。由此可得，在。由此可得，在d d 给定后，取给定后，取前前d d 个较大的特征值所对应的特征矢量个较大的特征值所对应的特征矢量wi( (i=1,2,=1,2,d,d) )构造构造特征提取矩阵特

46、征提取矩阵W，即:)(21dwwwWxWydiiWJ1*1)(矩阵迹形式的判据1 2 dn nd阵以J4为例，由于SW是对称正定矩阵，设有非奇异阵A，使IASAW1AVSAVTIIVVAVSAVW11设有标准正交矩阵V，使这里 为对角阵，从而行列式形式的判据120=0TnUS U令U=AV ，因此存在非奇异矩阵U ，使 IUSUW4TWSJS上面右式两边同时取逆，有IUSUw111) (这里U及 分别是特征矢量组成的矩阵(特征矢量矩阵)及特征值对角阵。 120=0TnUS UIUSUWSS UUWT1再与左式相乘，并左乘U ，有: 行列式形式的判据因为SSSSSISSWTWWBWB111()

47、diagn(,)12设SW-1SB 的特征值矩阵11()()WBWBISSUUSS UUI 所以I 则行列式形式的判据SS UUWT111112101()=01WBnU SS UU UII eUW因为SSSSSISSWTWWBWB111() diagn(,)12设SW-1SB 的特征值矩阵11()()WBWBISSUUSS UUI 所以I 则于是WTSSJ 4USSUTW11TWSS1TWSS1)1 (1iniini1行列式形式的判据SS UUWT1此处的U 就是前述的We。转换步骤：转换步骤：设设U 的各列已作适当调整，的各列已作适当调整，使使S SW W-1-1S SB B 的特征值的特征

48、值 1 2 n ，对于给定的，对于给定的d，取前，取前d个较大的特征值对应的个较大的特征值对应的特征矢量构造变换矩阵可使特征矢量构造变换矩阵可使J4 取最大值，此时取最大值，此时*41()(1)diiJW )1 (1111114iniiniTWTWTWWTUSSUSSSSSSJ行列式形式的判据四、离散四、离散K-LK-L变换及其变换及其在特征提取与选择中的应用在特征提取与选择中的应用特征提取与选择特征提取与选择特征提取与K-L变换u特征提取特征提取：用映射（或变换）的方法把原始特征变换为较少的新特征uPCA (Principle Component Analysis)方法方法：进行特征降维变换

49、，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的变换方法,使损失最小。uK-L (Karhunen-Loeve)变换变换：最优正交线性变换，相应的特征提取方法被称为PCA方法离散K-L变换（DKLT）DKLT的性质： 使变换后产生的新的分量正交或不相关; 以部分新分量表示原矢量均方误差最小;1. 使变换矢量更趋确定、能量更趋集中。有限离散K-L变换（DKLT）,又称霍特林(Hotelling)变换或主分量分解,它是一种基于目标统计特性的最佳正交变换。 变换是一种工具，它的用途归根结底是用来描述事物，特别是描述信号用的。例如我们看到一个复杂的时序信号，希望能够对它进行描述。

50、描述事物的基本方法之一是将复杂的事物化成简单事物的组合, 或对其进行分解，分析其组成的成分。 例如对一波形，我们希望知道它是快速变化的(高频)，还是缓慢变化的(低频)，或是一成不变的(常量)。如果它既有快速变化的成分，又有缓慢变化的成分，又有常量部分，那么我们往往希望将它的成分分析出来。这时我们就要用到上式中要求titi=1，是考虑到ti是作为度量事物的单位应用的，它本身的模应该为1，ti又称为。而被分解后的任何事物(在此指信号)可等成各种成分之和。故任一信号X可表示成： 其中yi是基ti的相应成分。 综合以上分析，我们可以将对这种变换的定义总结为：如果将这种变换中的每一成分，用一个向量ti表

51、示，i是其下标，原理上可以到，则我们要求的正交变换可表示成：10i jijt tij1i iiXy tn基于Karhunen-Loeve变换的特征提取方法是以在特征空间分布的样本特征向量为原始数据，通过实行K-L变换，找到维数较少的组合特征，达到降维的目的样本都是离散的向量的情况下，只需讨论K-L变换的离散情况。离散K-L变换（DKLT）nK-L变换：对给定一个n维训练样本集（原始特征空间），进行特征空间的降维，降到m维，m2 2c c, ,选取前选取前d d个较大的特征个较大的特征值对应的特征矢量构成变换矩阵，可实现特征的选取。值对应的特征矢量构成变换矩阵，可实现特征的选取。BSBSBSSB

52、iui) 1, 2 , 1(ci121cdui12( ,.,)dUu uu 排序：，取前个构成变换矩阵，有yU x3 基于总的类内离差矩阵 的DKLT进行特征提取选择WST(1,2, )WiiiiWiSuinu S u构造准则函数J yu S uu S uu S uiiBiiWiiBii() TTT 适用于各类模式的类域在某些分量轴上的投影不重迭或较少重迭的情况。离散K-L变换在特征提取与选择中的应用排序：J yJ yJ yn()()()12，取前面d个较大的J( ) 值对应的ui(, , )id 1 2 组成变换矩阵 ，有WTYW XJTr STr SBW34. 依据 、 作DKLT以降低特

53、征维数的最优压缩方法WSBS离散K-L变换在特征提取与选择中的应用设和U是对称正定阵WS的特征值对角阵和特征矢量矩阵，作如下的白化变换 I2121TUSUW易知，存在正交阵V可使 2121TTVUSUVB式中是白化变换后的总的类间离差阵的特征值对角阵。2121TUSUSBBTBBSB S B由于BS的秩不大于1c，所以SB最多只有1c个非零特征值，设非零特征值共有d个，用这d个非零特征值所对应的特征矢量), 2, 1(djvj作变换矩阵，所得的d个分量含有原来n维模式的全部信息。12YW XVU X)(21dvvvV离散K-L变换在特征提取与选择中的应用不损失信息而又达到最小维数的变换矩阵为：

54、12WVUSW特征值对角阵SW特征矢量阵SB特征矢量阵例例两类样本的均值矢量分别为m1=(4,2)和m2=(-4,-2),协方差矩阵分别为：31131C42242C两类的先验概率相等，试求一维特征提取矩阵。解解总的类内离差阵可以算得：5 . 35 . 15 . 15 . 3221121CCSw1icWiiSPS(1)依据SW进行DKLT，得到特征值2, 521对应的特征向量分别为：)707. 0,707. 0(, )707. 0 ,707. 0(21因为总的均值矢量为：)0 , 0(221121mmm故类间离差阵SB为：4881622211121mmmmSB计算J(y1)与J(y2)：1)(,

55、 7 . 3)(22221111BBSyJSyJ因为J(y1)J(y2),所以选最佳变换矩阵为)707. 0 ,707. 0(1WciiiiBmmmmPS1T)()()(2)依据SW和SB作DKLT进行最优特征提取。此时447. 02/11707. 02/125 . 0316. 05 . 0316. 0707. 000447. 0707. 0707. 0707. 0707. 02/1UB对SB进行白化变换：1896. 1896. 16 . 3BSBSBB的非零特征值只有一个， 6 . 41BS对应的特征矢量为)466. 0 ,884. 0(1)046. 0 ,512. 0(1BW总的最优变换为

56、：12WVU5. 基于总体离差阵 的DKLT选择特征 适用于各类模式类间距离较大的情况。ST在未知属别信息时，即没有训练样本，从而无法得到 和 ，此时，可依据总体离差阵 作DKLT，设对应该总体离差阵的特征值依下面次序排列：SWSBST12 n对于给定的 ，选择前面较大的本征值对应的本征矢量作变换矩阵以实现特征选择、降低特征空间维数的目的。d离散K-L变换在特征提取与选择中的应用T11()()NTlllSxm xmN五、特征选择中的直接挑选法五、特征选择中的直接挑选法特征提取与选择特征提取与选择 特征的提取与选择除了我们前面学习的变换法外, 也可以在原坐标系中依据某些原则直接选择特征, 即直接

57、挑选法。n次优搜索法n最优搜索法特征提取与选择特征提取与选择次优搜索法( (一一) )单独最优的特征选择单独最优的特征选择 单独选优法的基本思路是：计算各特征单独使用时的判据值并以递减排序，选取前d个分类效果最好的特征。 这种方法才能选出一组最优特征。一般地讲，即使各特征是统计独立的，这种方法选出的d个特征也不一定是最优的特征组合，只有可分性判据J是可分的时候，即10( )( ) ( )( )nniiiiJ xJ xJ xJ x或 ( (二二) )增添特征法增添特征法次优搜索法( (二二) )增添特征法增添特征法设已选入了k个特征，它们记为Xk，把未选入的n-k个特征xj（j=1,2,n-k)

58、逐个与已选入的特征Xk组合计算J 值，若：则x1选入，下一步的特征组合为Xk+1=Xk+x1。开始时，k=0，X0=F， 该过程一直进行到k=d为止。)()()(21knkkkxXJxXJxXJ次优搜索法( (二二) )增添特征法增添特征法该方法比该方法比“单独最优的特征选择法单独最优的特征选择法”要好，但要好，但其缺点也是明显的：即某特征一旦选入，即使后边其缺点也是明显的：即某特征一旦选入，即使后边的的n-k特征中的某个从组合讲比它好，也无法把它特征中的某个从组合讲比它好，也无法把它剔除。剔除。次优搜索法( (三三) )剔减特征法剔减特征法该方法也称为顺序后退法(SBS)。这是一种自上而下的

59、搜索方法，从全部特征开始每次剔除一个特征，所剔除的特征应使尚保留的特征组合的J值最大。次优搜索法( (三三) )剔减特征法剔减特征法)()()(21knkkkxXJxXJxXJ设已剔除了k个特征，剩下的特征组记为 ，将 中的各特征xj（j=1,2,n-k)分别逐个剔除，并同时计算 值，若：kXkX)(jkxXJ则在这轮中x1应该剔除。这里初值 ，过程直到k=n-d为止。11xXXkk, 0210nxxxXk次优搜索法(四四) 增增l 减减r 法（法（l-r 法）法） 为了克服前面方法（二） 、（三）中的一旦某特征选入或剔除就不能再剔除或选入的缺点，可在选择过程中加入局部回溯，例如在第k步可先用

60、方法（二） ，对已选入的k个特征再一个个地加入新的特征到k+l个特征，然后用方法（三）一个个地剔除r个特征，称这种方法为增l减r 法（ l-r法）次优搜索法次优搜索法最优搜索法最优搜索法分支定界法分支定界法(BAB(BAB算法算法) ) 寻求全局最优的特征选择的搜索过程可用一个寻求全局最优的特征选择的搜索过程可用一个树结构来描述，称其为搜索树或解树。树结构来描述，称其为搜索树或解树。总的搜索方案是沿着树总的搜索方案是沿着树自上而下自上而下、从右至左从右至左进进行，由于树的每个节点代表一种特征组合，于是所行，由于树的每个节点代表一种特征组合，于是所有可能的组合都可以被考虑。有可能的组合都可以被考