第五章特征选择与特征提取-Read

第五章特征选择与特征提取5.1问题的提出前面主要介绍的是各种分类器的设计方法， 实际上我们已经完全可以解决模式识别的问题了。然而在实际应用中，在分类器设计之前，往往需要对抽取出的特征进行一下处理，争取尽量减小特征的维数。在实践中我们发现，特征的维数越大，分类器设计的难度也越大，一维特征的识别问题最容易解决，我们只要找到一个阈值t,大于t的为一类，小于t的为一类。冋时特征维数越大，要求的训练样本数量越多，例如在一维的情况下，10个训练样本就可以比较好的代表一个类别了，而在 10维空间中，1o个训练样本则是远远不够的。这一章中我们就来介绍一下减小特征维数的方法。一般来说模式识别系统的输入是传感器对实物或过程进行测量所得到的一些数据，其中有一业数据直接可以作为特征， 有一业数据经过处理之后可以作为特征，这样的一组特征一般称为原始特征。在原始特征中并不一定每个特征都是有用的， 比如在识别苹果和橙子的系统中，我们可以抽取出的特征很多， （体积，重量，颜色，高度，宽度，最宽处高度） ，同样还有可能抽取出其它更多的特征。在这些特征中对分类有用的是（颜色，高度，最宽处高度），其它特征对识别意义不大，应该去除掉。这样的过程称为是特征选择，也可以称为是特征压缩。特征选择可以描述成这样一个过程，原始特征为 N维特征X=（X1,X2AI,XNf，从中T选择出M个特征构成新的特征矢量丫二Xi,Xijl|,XiM，M::N。同时，特征矢量的每一个分量并不一定是独立的， 它们之间可能具有一定的相矢性， 比如说高度和最宽处的高度，高度值越大， 最宽处的高度值也越大，它们之间具有相矢性，我们可以通过一定的变换消除掉这种相矢性，比如取一个比值：最宽处的高度过程称为特征提取。/高度。这样的特征提取可以描述为这样一个过程，对特征矢量 X=X1,X2,HI,XN丁施行变换：%=h（X）,i=1,2,川，M，McN，产生出降维的特征矢量丫二（叙丫2,川皿$。在一个实际系统的设计过程中，特征的选择和提取过程一般都需要进行，首先进行特征选择，去除掉无矢特征，这些特征实践上根本就不需要抽取出来， 这部分传感器根本不需要安装，这样也可以减小系统的的成本。然后进行特征提取，降低特征的维数。然后利用降维之后的样本特征来设计分类器。5.2模式类别的可分性判据在讨论特征选择和特征压缩之前， 我们先要确定一个选择和提取的原则。对一个原始特征来说，特征选择的方案很多，从N维特征种选择出M个特征共有Cm巴中M!(N—M)!选法，其中哪一种方案最佳，则需要有一个原则来进行指导。同样，特征的压缩实际上是要

找到M个N元函数，N元函数的数量是不可数的，这也要有一个原则来指导找出 M个最佳的N元函数。我们进行特征选择和特征提取的最终目的还是要进行识别， 因此应该是以对识别最有利原则，这样的原则我们称为是类别的可分性判据。 用这样的可分性判据可以度量当前特征维数下类别样本的可分性。可分性越大，对识别越有利，可分性越小，对识别越不利。人们对的特征的可分性判据研究很多，然而到目前为止还没有取得一个完全满意的结果，没有哪一个判据能够完全度量出类别的可分性。 下面介绍几种常用的判据，我们需要根据实际问题，从中选择出一种。一般来说，我们希望可分性判据满足以下几个条件：• 与识别的错误率由直接的联系，当判据取最大值时，识别的错误率最小；当特征独立时有可加性，即：NJijXv|，X2,|11，Xn八JijxkJij是第i类和第j类的可分性判据，Jij越大'两类的可分程度越大'Xi,X2,川,Xn为N维特征；应具有某种距离的特点：Jij*0，当ij时;Jj=o,当/=j时；J・・I>••IJ=Jjl,单调性，加入新的特征后，判据不减小：JijX|>X2JXN-JijX1>X2I>XN>XN1«但是遗憾的是现在所经常使用的各种判据很难满足上述全部条件， 只能满足一个或几个条件。一、基于几何距离的可分性判据在介绍这一类判据之前，先来看一下各种几何距离的定义。7・点与点的距离这是我们前面已经介绍过的一种距离，可以有多种形式，如欧氏距离、街市距离、马氏距离等，特征矢量X和Y之间的距离可以表示为：Td(X5Y)=(X-Y)(X-Y)(欧氏距离)点与类别之间的距离这也是我们前面定义过的一种距离度量，常用的有：平均样本法、平均距离法、最这也是我们前面定义过的一种距离度量，常用的有：平均样本法、平均距离法、最近距离法，K•近邻法等。特征矢量X与几类别之间距离的平方可以表示为:1叫d?（XQ）=—一瓦d?（X,X门）（平均距离法）Nik4其中Xi,X2J|I，X/V为ij类中的样本，Ni为类别中的样本数。•类内距离设「了由样本集Xi,X2川|，Xn「，样本的均值矢量为m>，则由样本集定义的类内均方距离为：NiNi、“cbXsX/k=1I4当取欧氏距离时有：叫Td2j）=一二Xj-打LXkm'NikA4.类别之间的距离在第二章中对类别之间的距离也做过定义， 包括最短距离法，最长距离法，类平均距离法等。〔冷类与j类之间的距离可以表示为：1NiNjdJLj=RR：-dXk>Xi （平均距离法）当取欧氏距离时，可定义两类之间的均方距离：[%叫丁NN迟迟（X£）—X卩））（Xk）—X{j））'J k壬I壬有了距离度量之后，我们就可以在此基础上定义可分性测度了。 一般来讲，当各个类别的类内距离越小时可分性越强， 而类间距离越大时，可分性越强。因此可以有以各类样本之间的平均距离作为判据：1M MJdX PJVPJdJQj2i=1 j=1JdX所反映的主要还是类别之间的分离程度，对类内的聚集程度反映不够。通常我们采用跟一般的矩阵形式来构造可分性判据。1・类内散度矩阵设有M个类别，OJII,Om,Oi类样本集{X11X2川l,XN‘‘，Qi类的散度矩阵定义为：Ni TsP=p（X“品驱卩人⑴Nik=i

总的类内散度矩阵为：M M 1NiSw八P『Sw/[PJ—Xk1i4 i=J Mk=1类间散度矩阵第i个类别和第j个类别之间的散度矩阵定义为：sBu)=(mO-m(0)(m°)—m(J))总的类间散度矩阵可以定义为：M MP「Sbj=M MP「Sbj=—、PjPjm-mjm-mjL— j~Sb=—Pi二 i4M令：m为总体均值，m=ZP(OimD，则有:i:4\o"CurrentDocument"M TSbPQiXmO-mXm(")-m)■—*I—k总体散度矩阵总体散度矩阵可以定义为：St-JXimXiNi：-M其中N为总的样本数，N= N\。可以证明：5心氐*Sb。i:—可以看出三个散度矩阵均为实对称矩阵。上面我们所定义的判据： JdX=JdxjutrSri=trSw-sbotr表示取一个矩N阵的迹，也就是主对角线元素之和， N维方阵Z的迹为：trZ二、aw同样我们可以利用三个散度矩阵定义出一系列的可分性判据:J—=trSwSb其中A表示方阵A的行列式的值，比较常用的判据是Ji。基于几何距离的可分性判据计算起来比较简单，只要我们已知各个类别的训练样本集，就可以计算出三个散度矩阵，同时也就可以计算出各种可分性判据。二、基于概率分布的可分性判据基于几何距离的可分性判据计算起来比较简单， 然而它没有考虑各类别的概率分布， 因此与识别错误率之间的联系却不是很紧密。下面介绍一种直接基于概率分布的可分性判据。先以最简单的一维特征、两类问题为例，下图表示了两种极端情况：第一种情况是两类完全可分：对所有p(X|0第一种情况是两类完全可分：对所有p(X|0〃/0的点，有p(X02)=0;第二种情况是两类完全不可分：对所有的X第二种情况是两类完全不可分：对所有的X有p(X|0u)=p(X|02)o下面我们可以定义两个类条件概率密度函数之间的距离 Jp作为交叠程度的度量，Jp应该满足如下条件：非负性，Jp-0;当两类完全重叠时Jp取最大值，即若对所有X有p(XQ2)式0时，pXJ=0，贝uJp二max;当两类密度函数完全相同时， Jp应为零，即若p(X|C2)=P(X|0i)，则JP=0o按照这样的要求，可以定义出多种可分性判据，这里我们只介绍其中一种 一散度。现在考虑ixffi门j两类之间的可分性，取其对数似然比:LiX=ln则Ji类对Jj类的平均可分性信息可以定义为:

lj(X戶EliX「xpxjln同样」类对」类的平均可分性信息：P(X|Ojlji(X)=Ejji(X)]=Lp(X|Cj)ln dXPXJ散度Jp定义为区分门i类和门j类的总平均信息：=fx[p(X|0i)-P(X0j川n从Jp的定义可以看出，当两类分不完全性同 p(XOi)=p(XQ\)时，Jp=o;当两类完全可分时，Jp=•。基于概率的可分性判据优点是直接与识别的错误率相联系， 缺点是需要已知各个类别类概率密度函数，只有当我们预先已知各类别的概率分布时，才可以利用训练样本集合估计出概率密度函数，但是对很多实际问题来说各类别的概率分布情况我们是无法预先知道的。5.3特征选择所谓特征选择，就是从一组数量为 N的特征中选择出一组数量为 M的最优特征，(NM)这里有两个问题要解决，1、选择一种可分性判据作为最优特征选择的标准； 2、找到一个好的算法，来选择出这组最优特征。下面我们就来介绍几种特征选择的算法。一个最简单的思路是：我们假设 N个特征之间相互独立，并且使用的可分性判据满足N可加性：JX=•Jx，这时候我们只要把N个特征每个单独使用时的可分性判据7JXi计算出来，然后从大到小排序： Jx,•JX2 IIIJXn»选择出前M个特征就是一组最优的特征。然而问题往往没有这么简单，这种特征独立性假设多数情况下并不成立，并且可分性判据也不一定满足可加性。另外一个简单的思路是(穷举法)：对从N中选择出M个特征的所有组合情况都计算其可分性判据，然后选择出其中的最大者作为解决方案。当 N的数值比较小时，这种方法一定是可行的，然而当N比较大时，这个组合数会非常大，比如 N=100，M=10时，组合数的数量级是1，当N=20,M=10时，组合数为184756°将所有的组合都计算一遍显然是不现实的。因此我们需要有一个搜索算法来进行特征选择。一、最优搜索算法一分支定界算法到目前为止唯一能够找到最优解的算法是“分支定界”算法。它所利用的是可分性判据

到目前为止唯一能够找到最优解的算法是“分支定界”算法。它所利用的是可分性判据中的单调性质：JjXi3X23|||中的单调性质：JjXi3X23|||3Xn质。mXi,X2,|]|3Xn,Xni 们前面定义的各种判据都满足这个性分支定界的思想分支定界算法实际上是对一彳、特征选择的搜索树进行搜索,情况来说明一下搜索树。F面先以N=6，M=2的45Xi,在搜索树中根节点Xo代表全部特征的集合x2,1H,X6』，每向下一级节点代表从集Xi,合中删除一个特征，节点边上的数字表示在这一级中刪除的特征，代表fxi9比如A节点表示刪除X2特征,Xa,|||,X6?，因为最后要保留2个特征，因此树的级数为N・合中删除一个特征，节点边上的数字表示在这一级中刪除的特征，代表fxi9叶节点代表一种组合‘比如 C节点代表：Xi,xA>o由于可分性判据具有单调性， 因此在搜索树中的节点具有这样的性质： 每个节点代表的特征集合的可分性判据要大于其后继节点代表的特征集合的可分性判据，比如：JA-JB-JC根据这样的性质，我们就可以有如下的搜索算法。分支定界算法（不严格）1） 搜索从右向左进行，首先设置一个界值 B，初始化为B=0;2） 如果当前节点没有分支， 则向下搜索，直到叶节点为止，计算叶节点代表的特征集合的可分性判据，如果大于界值 B，则将B替换为这个判据值，并记录这个特征集合，作为当前的最优选择；向上回溯，直到有节点有未搜索过的分支为止， 按照从右向左的顺序搜索其子节点；3） 如果当前节点有分支，则计算当前节点代表的特征集合的可分性判据，如果小于界值B，则中止该节点向下的搜索，因为其子节点的可分性判据已经不可能大于 B了。否则按照从右向左的顺序搜索其子节点。分支定界算法的计算时间是不确定的，同最优解分支所在位置有矢，如果最优解分支在分支定界算法的计算时间是不确定的，同最优解分支所在位置有矢，如果最优解分支在3组可最右端，并且去掉Xi或X23组可分性判据；如果每个分支的可分性判据都大于其左端分支的可分性判据，则搜索时间最长，需计算可分性判据的次数可能 15次。二、次优搜索算法顺序前进法（SequentialForwardSelection,SFS）每次从未入选的特征中选择一个特征， 使得它与已入选的特征组合到一起所得到的可分性判据最大，直到特征数增加到 M为止。用Xk表示在第k步时的特征集合，搜索算法如下：1） 开始时，X。二以，从N个特征中选择一个JXi最大的特征，加入已选特征集，X;tA2） 在第k步，Xk中包含已经选择的 k个特征，对未入选的 N-k个特征计算，JXku「Xj?,其中j=1,2,HI,N-k，并且按照由大到小排序，将可分性判据最大的特征xi加入Xk，Xk厂XkUX；；3）直到所选的特征数等于M为止。顺序后退法（SequentialBackwardSelection,SBS）同顺序前进法的过程刚好相反， 最开始时取X。・\为，III,XA?，每次从中剔除一个特征，使得剩余的特征可分性判据最大。增1减「法（I-r法）前两种方法可以进一步改进，比如每次不是加入 1个特征，而是加入|彳、特征；或者每次不是剔除一个特征，而是剔除r个特征。这样的效果要比每次加1或减1的效果好，但是计算量要增大。另外一种改进方法是将SFS和SBS结合，先使用SFS算法逐个选入I个最佳特征，然后使用SBS算法逐个剔除r个最差特征，I・r，再使用SFS算法增加I个特征，再使用SBS剔除r个特征，…，直到选出M个特征为止。5.4特征提取特征抽取的方法很多，下面我们以其中的一种一基于离散K丄变换（DKLT）的特征抽取，其它方法与此类似。设原始特征为N为矢量X=（xi,X2,IH,Xn「，均值矢量m=E（X】，相尖矩阵Rx=eXXt）协方差矩阵cx=EL（X-m\X-m）l我们可以对X我们可以对X作如下的标准正交变换，将其变为矢量y=（%,『m八Y=TTY=TTX=T2Y的每个分量：屮二丁・X，其中T为一个NN的标准正交矩阵，Ti为其第i个列矢J。也就是说YJ。也就是说Y的每个分量是X每一个分量的线性组合。6i・j同样X可以表示为：T-1 V2X二TY二TY=「T2川Tn7N我们要进行特征提取，也就是要用Y的M项来代替X，这种代替必然带来误差，下面我们来对这个误差进行估计：M令：乂二yTi，1vM::N，引入的均方误差为：i生TOC\o"1-5"\h\z- T ・N Ne2(M)=Ei(X—X)(X—X)=2E[yA=S丘阳]N N\o"CurrentDocument"=571tEXXT〕T|=ETrRxTii=MI1 ・i1这又变成一个优化问题，我们希望寻找到一个标准正交矩阵 T，使得e2M