特征提取与选择

第七章特征提取与选择特征形成特征提取特征选择目的：(max)1212(,,,)'(,,,)',Jnmxxxxyyyymn7.1概述直接选择法–分支定界法；–用回归建模技术确定相关特征等方法。变换法在使判据J→max的目标下，对n个原始特征进行变换降维，即对原n维特征空间进行坐标变换，然后再取子空间。主要方法有：–基于可分性判据的特征选择–基于误判概率的特征选择–离散K-L变换法(DKLT)–基于决策界的特征选择等方法。7.2类别可分性判据(ClassSeparabilityMeasures)准则—类别可分性判据:刻划特征对分类的贡献。构造的可分性判据Jij应满足下列要求：(1)与误分概率P(e)(或误分概率的上界、下界)有单调关系，Jij最大值时，P(e)最小。(2)当特征相互独立时，判据有可加性，即121(,,,)()dijdijkkJxxxJx式中xk，是对象不同种类特征的测量值，Jij(●)表示使用括号中特征时第i类与第j类的可分性判据函数。(3)判据具有“距离”的某些特性：Jij0，当i≠j时Jij=0，当i=j时Jij=Jji(4)Jij对特征数目单调不减，即加入新的特征后，判据值不减所构造的可分性判据并不一定要求同时具有上述四个性质。12121(,,,)(,,,,)ijdijddJxxxJxxxx7.2.1基于几何距离的可分性判据可以用距离或离差测度(散度)来构造类别可分性判据(一)点与点的距离在n维特征空间中，点与点之间的欧氏距离为(二)点到点集的距离点到点集之间的均方欧氏距离为ab1/221/21(,)[()'()][()]nkkkdabababab2()2()11(,{})(,)iNiikkkidxadxaNx(),1,2,,iikiakN(三)类内及总体的均值矢量设N个模式分属c类,则各类的均值矢量分别为所有各类模式的总体均值矢量为式中Pi为相应类的先验概率。当用统计量代替先验概率时，有(),1,2,,iikixkN1,2,,ic()()11iNiikkimxN(1,2,,)ic()1ciiimPm()()()1111111iNcccNiiiiikliiiklNmPmmxxNNN(四)类内距离类内均方欧氏距离为类内均方距离也可定义为(五)类内离差（散布）矩阵(Scatter)类内离差矩阵定义为类内离差矩阵SWi的迹等于类内的均方欧氏距离，即类内离差矩阵表示各类模式在类的均值矢量周围的散布情况。2()()()()11()()'()iNiiiiikkkidxmxmN22()()111()(,)(1)iiNNiiciklkliiddaaNN()()()()11()()'iiNiiiiwkkkiSxmxmN(),1,2,,iikixkN2()[]iiwdTrS(六)两类之间的距离当式中的距离取欧氏距离时,有(七)各类模式之间的总的均方距离当取欧氏距离时22()()111(,)(,)jiNNijijklklijddxxNN2()()()()111(,)()'()jiNNijijijklklklijdxxxxNN(),1,2,,iikixkN(),1,2,,jjljxlN22()()111111()(,)2jiNNccijijklijklijdxPPdxxNN2()()()()111111()()'()2jiNNccijijijklklijklijdxPPxxxxNN(八)多类情况下总的类内、类间及总体离差（散布）矩阵总的类内离差矩阵定义为总的类间离差矩阵定义为总体离差矩阵为易导出()()()()1111()()'iiNcciiiiWiikkiikiSPSPxmxmN()()1()()'ciiBiiSPmmmm11()()'NTllWBlSxmxmSSN2()WBTdxTrSSTrSiiNPN()()11iNiikkimxN11NllmxN可分性判据（类内紧，类间开）11WBJTrSS2BWSJS3BWTrSJTrS4||||||||WBTWWSSSJSS可以证明J1、J2与J4在任何非奇异线性变换下是不变的，J3与坐标系有关。7.2.2基于类的概率密度函数的可分性判据用两类概密函数的重迭程度来度量可分性，构造基于类概密的可分性判据Jp，它应满足：(1)Jp0；(2)当两类密度函数完全不重迭时，Jp=max；(3)当两类密度函数完全重合时，Jp=0；(4)相对两个概密具有“对称性”。1(|)px2(|)px12(|)(|)pxpx(a)(b)(一)Bhattacharyya判据(JB)在最小误分概率准则下，误分概率1/212ln(|)(|)BJpxpxdx1/2012()()()expBPePPJ(受相关定义与应用的启发，构造B-判据)(二)Chernoff判据(JC)性质：(1)对一切0s1，Jc0；(2)对一切0s1，;(3)当参数s和(1-s)互调时，才有对称性，即（比JB更广义的判据）1121212ln()()(,;)(;,,,)()0s1ssCCCnCJpxpxdxJsJsxxxJs120(|)(|)CJpxpx1221(,,)(,,1)CCJsJs1()2CBJJ(二)Chernoff判据(JC)性质：(4)当各分量x1,x2,…,xn相互独立时，(5)当各分量x1,x2,…,xn相互独立时，(6)最小误分概率1221(,,)(,,1)CCJsJsx121(,,,,)(,)nCnCllJsxxxJsx101212()()()exp(,;)01ssCPePPJss（JC不具有三点距离不等式的性质。）12121(,,,,)(,,,,,),CnCnnJsxxxJsxxxxknx(三)散度JD(Divergence)对1类的平均可分性信息为对2类的平均可分性信息为对于1和2两类总的平均可分性信息称为散度，其定义为两类平均可分性信息之和，即(|)(|)()ln(|)ln(|)(|)iiijiijjpxpxIxEpxdxpxpx1()()(|)[(|)(|)]ln(|)(,)(,,)DijjiiijjDijDnJIxIxpxpxpxdxpxJJxx(|)(|)()ln(|)ln(|)(|)jjjijjiipxpxIxEpxdxpxpx类别可分性判据小结几何可分性判据类概率密度可分性判据(一)Bhattacharyya判据(JB)(二)Chernoff判据(JC)(三)散度JD11WBJTrSS2BWSJS3BWTrSJTrS12ln{(|)(|)}(1/2)BijcJpxpxdxJ11212ln()()(,;),0s1ssCCJpxpxdxJs(|)()()[(|)(|)]ln(|)iDijjiijjpxJIxIxpxpxdxpx4||||||||WBTWWSSSJSS第七章特征提取与选择7.7特征选择中的直接挑选法特征的选择可以在原坐标系中依据某些原则直接选择特征,：从n个特征中挑选出d个使其Jd最大。7.7.1次优搜索法7.7.2最优搜索法7.7.1次优搜索法(一)单独最优的特征选择基本思路：计算各特征单独使用时的判据值J并以递减排序，选取前d个分类效果最好的特征。一般地讲，即使各特征是统计独立的，这种方法选出的个特征也不一定是最优的特征组合；只有可分性判据J是可分的，即这种方法才能选出一组最优特征。1()()()()niiiJxJxJxJx或(二)增添特征法该方法也称为顺序前进法(SFS)。这是最简单的自下而上搜索方法，每次从未选入的特征中选择一个特征，使它与已选入的特征组合在一起时J值最大，直到选入特征数目达到指定的维数d为止。7.7.1次优搜索法SequentialForwardSelection(三)剔减特征法7.7.1次优搜索法12()()()kkknkJXxJXxJXx设已剔除了k个特征，剩下的特征组记为，将中的各特征xj（j=1,2,…,n-k)分别逐个剔除，并同时计算值，若：kXkX()kjJXx则在这轮中x1应该剔除:这里初值，过程直到k=n-d为止。11kkXXx0120,{,,,}nkXxxx7.7.1次优搜索法(四)增l减r法（l-r法）为了克服前面方法(二)、(三)中的一旦某特征选入或剔除就不能再剔除或选入的缺点，可在选择过程中加入局部回溯，例如在第k步可先用方法(二)，对已选入的k个特征再一个个地加入新的特征到kl个特征，然后用方法(三)一个个地剔除r个特征，称这种方法为增l减r法(lr法)。6选2的特征选择问题(a)搜索树(b)搜索回溯示意图7.7.2最优搜索法BAB算法123234443A3454554555456566566656666nXX000i1i2i4i3i0X()a()bs=0s=1s=2s=3s=4树的每个节点表示一种特征组合，树的每一级各节点表示从其父节点的特征组合中去掉一个特征后的特征组合，其标号k表示去掉的特征是xk。7.7.2最优搜索法BAB算法由于每一级只舍弃一个特征，因此整个搜索树除根节点0级外，还需要n-d级，即全树有n-d级。例如，6个特征中选2个，整个搜索树有4级。第n-d级是叶节点，共有Cnd个叶节点。BAB算法7.7.2最优搜索法表示特征数目为l的特征集合。lX表示舍弃s个特征后余下的特征集合。sX表示当前节点的子节点数。sq表示集合s中元素的数目。sr表示第s级当前节点上用来作为下一级可舍弃特征的特征集合。s由于从根节点要经历n-d级才能到达叶节点，s级某节点后继的每一个子节点分别舍弃s中互不相同的一个特征，从而考虑在s+1级可以舍弃的特征方案数（即子节点数）qs时，必须使这一级舍弃了特征后的Xs+1还剩（n-d)-(s+1)个特征。除了从树的纵向上每一级舍弃一个特征，实际上从树的横向上，一个分支也轮换舍弃一个特征。因此后继子节点数qs=rs-（n-d-s-1）BAB算法7.7.2最优搜索法BAB算法7.7.2最优搜索法ss+1n-d(n-d)-(s+1)qsrs()(1)ssrqnds0rn(1)ssqrnds01qdBAB算法7.7.2最优搜索法06r06(401)3q0123456{,,,,,}xxxxxx123456{,,,,}xxxxx13456{,,,}xxxx1456{,,}xxx2456{,,}xxx256{,}xxBAB算法7.7.2最优搜索法06r06(401)3q0123456{,,,,,}xxxxxx123456{,,,,}xxxxx23456{,,,}xxxx2456{,,}xxx256{,}xxBAB算法7.7.2最优搜索法目标：找出叶节点Lk，使其对应的d个特征的判据J的值最大，即：注意到每个节点（包括非叶节点）都可以计算相应的J值。由于判据J值具有单调性，即：12121(,,,)(,,,,)dddJxxxJxxxx该不等式表明，任何节点的J值均不小于其任何后继节点（子节点）的J值。1()max[()]dnCkjjJLJLBAB算法7.7.2最优搜索法搜索顺序：从上至下、从右至左。四个步骤：1、向下搜索2、更新界值3、向