97模式识别技术(五)

1第五章特征选择和提取ƒ5.1概述ƒ5.2可分性判据ƒ5.3特征选择ƒ5.4特征提取ƒ5.5K-L变换25.1概述特征选择和特征抽取是模式识别中昀基本的问题之一。有关特征抽取和特征抽取的理论和方法一直是人们研究的热点和关键问题。一、问题的提出设计分类器之前，要完成特征的选择和提提取。其目的：1、信息冗余2、突出有用信息，抑制无用（次要）信息，减少信息的维数。3二、有关概念1、特征选择（FeatureSelection）从原始特征中挑选出一些昀有效的特征以达到降低特征空间维数的目的，这个过程叫做特征选择。基本方法是在特征子集上定义特征选择准则，并寻找使该准则值昀大的特征组合。基本策略：（1）昀优方法：对小规模问题的穷举搜索方法；加速搜索算法；蒙特卡罗方法（遗传算法，模拟退火算法）。这些方法都能产生全局昀优解，但计算量一般太大。（2）次优方法：减少上述策略的昀优性以获得较高的计算效率。4二、有关概念2、特征提取（特征抽取）（FeatureAbstraction）通过映射（或变换）将原始的高维空间变换到低维空间来表示样本，这个过程叫做特征提取。映射后的特征叫做二次特征，他们是原始特征的某种组合（通常是线性组合）。所谓特征提取，广义上就是指一种变换，即dnRR:→ϕ，使))X((Jϕ达到昀大，ϕ可以是线性的也可以是非线性的。至今多元统计分析的许多方法都被用于线性特征的抽取，如主成分分析（主分量分析，PCA），因子分析（FA），多维标度（MS），鉴别分析（FDA），投影追踪（PP）等。5二、有关概念3、特征选择和特征抽取的原则我们进行特征选择和特征提取的昀终目的还是要进行识别，因此应该是以对识别昀有利原则，这样的原则我们称之为类别的可分性判据。用这样的可分性判据可以度量当前特征维数下类别样本的可分性。可分性越大，对识别越有利，可分性越小，对识别越不利。具体来说，特征选择和特征抽取的一般原则都是尽可能消除模式样本各特征分量之间的统计相关性。65.2模式类别的可分性判据对于特征的可分性判据研究很多，然而到目前为止还没有取得一个完全满意的结果，没有哪一个判据能够完全度量出类别的可分性。下面介绍几种常用的判据，我们需要根据实际问题，从中选择出一种。一、可分性判据应满足的条件1、与识别的错误率有直接的联系，当判据取昀大值时，识别的错误率昀小。72、当特征独立时有可加性即：()()121,,,NijNijkkJxxxJx==∑LijJ是第i类和第j类的可分性判据，ijJ越大，两类的可分程度越大，()12,,,NxxxL为N维特征；3、应具有某种距离的特点：0ijJ，当ij≠时；0ijJ=，当ij=时；ijjiJJ=；4、单调性，加入新的特征后，判据不减小：()()12121,,,,,,,ijNijNNJxxxJxxxx+≤LL。但是遗憾的是现在所经常使用的各种判据很难满足上述全部条件，只能满足一个或几个条件。8二、可分性判据1、基于几何距离的可分性判据一般来讲，当各个类别的类内距离越小时可分性越强，而类间距离越大时，可分性越强。因此可以有以各类样本之间的平均距离作为判据：()()()()111,2ccdijijijJPPdωωωω===∑∑X()dJX所反映的主要还是类别之间的分离程度，对类内的聚集程度反映不够。通常采用散布矩阵的形式来构造可分性判据。9设有c个类别，1,,cωωL，iω类样本集()()(){}12,,,iiiiNxxxL，()()11NTTlllSxxN==−−∑mm,()()()()()1cTiiBiiSPω==−−∑mmmm,()()()()()()()111iNcTiiiiwikkikiSPxxNω===−−∑∑mm.TWBSSS=+利用三个散布矩阵可以定义如下可分性判据：()11trWBJSS−=；2BWSJS=；()()3trtrBWSJS=；4TWSJS=基于几何距离的可分性判据计算起来比较简单，只要我们已知各个类别的训练样本集，就可以计算出三个散布矩阵，同时也就可以计算出各种可分性判据。102、基于概率分布的可分性判据基于几何距离的可分性判据计算起来比较简单，然而它没有考虑各类别的概率分布，因此与识别错误率之间的联系却不是很紧密。下面介绍一种直接基于概率分布的可分性判据。我们定义两个类条件概率密度函数之间的距离PJ作为交叠程度的度量，PJ应该满足如下条件：1、非负性，0PJ≥；2、当两类完全重叠时PJ取昀大值，即若对所有X有()20pΩ≠X时，()10pΩ=X，则maxPJ=；3、当两类密度函数完全相同时，PJ应为零，即若()()21ppΩ=ΩXX，则0PJ=。11现在考虑iω和jω两类之间的可分性，取其对数似然比：()()()lniijjpxlxpxωω=则iω类对jω类的平均可分性信息可以定义为：()()()()()lniijijijpxIxElxpxdxpxωωω⎡⎤==⎣⎦∫X同样jω类对iω类的平均可分性信息：()()()()()lnjjijijxipxIxElxpxdxpxωωω⎡⎤==⎣⎦∫散度PJ定义为区分iω类和jω类的总平均信息：()()()()ln|iPijjiijxjpxJIIpxpxdxpxωωωω⎡⎤=+=−⎣⎦∫12从PJ的定义可以看出，当两类完全不可分，即()()ijpxpxωω=时，0PJ=；当两类完全可分时，PJ=+∞。基于概率的可分性判据优点是直接与识别的错误率相联系，缺点是需要已知各个类别类概率密度函数，只有当我们预先已知各类别的概率分布时，才可以利用训练样本集合估计出概率密度函数，但是对很多实际问题来说各类别的概率分布情况我们是无法预先知道的。除了上述可分性判据以外，还有基于熵函数的可分性判据，这里略。135.3特征选择所谓特征选择，就是从一组数量为N的特征中选择出一组数量为M的昀优特征（NM），这里有两个问题要解决，（1）选择一种可分性判据作为昀优特征选择的标准；（2）找到一个好的算法，来选择出这组昀优特征。下面我们就来介绍几种特征选择的算法。我们假设N个特征之间相互独立，并且使用的可分性判据满足可加性：()()1NiiJJx==∑X，这时候我们只要把N个特征每个单独使用时的可分性判据()iJx计算出来，然后从大到小排序：()()()12NJxJxJxL，选择出前M个特征就是一组昀优的特征。然而问题往往没有这么简单，这种特征独立性假设多数情况下并不成立，并且可分性判据也不一定满足可加性。14另外一个简单的思路是(穷举法)：对从N中选择出M个特征的所有组合情况都计算其可分性判据，然后选择出其中的昀大者作为解决方案。当N的数值比较小时，这种方法一定是可行的，然而当N比较大时，这个组合数会非常大，比如100N=，10M=时，组合数的数量级是310，当20N=，10M=时，组合数为184756。将所有的组合都计算一遍显然是不现实的。因此我们需要有一个搜索算法来进行特征选择。15一、昀优搜索算法—分支定界算法到目前为止唯一能够找到昀优解的算法是“分支定界”算法。它所利用的是可分性判据中的单调性质：()()12121,,,,,,,ijNijNNJxxxJxxxx+≤LL，我们前面定义的各种判据都满足这个性质。1.分支定界的思想分支定界算法实际上是对一个特征选择的搜索树进行搜索，下面先以6N=，2M=的情况来说明一下搜索树。16456565656666666345445555522333444ABCX01在搜索树中根节点0X代表全部特征的集合{}126,,,xxxL，每向下一级节点代表从集合中删除一个特征，节点边上的数字表示在这一级中删除的特征，比如A节点表示删除2x特征，代表{}136,,,xxxL，因为昀后要保留2个特征，因此树的级数为4NM−=。每一个叶节点代表一种组合，比如C节点代表{}14,xx。17由于可分性判据具有单调性，因此在搜索树中的节点具有这样的性质：每个节点代表的特征集合的可分性判据要大于其后继节点代表的特征集合的可分性判据，比如：()()()JAJBJC≥≥根据这样的性质，我们就可以有如下的搜索算法。1.分支定界算法（不严格）1)搜索从右向左进行，首先设置一个界值B，初始化为0B=；2)如果当前节点没有分支，则向下搜索，直到叶节点为止，计算叶节点代表的特征集合的可分性判据，如果大于界值B，则将B替换为这个判据值，并记录这个特征集合，作为当前的昀优选择；向上回溯，直到有节点有未搜索过的分支为止，按照从右向左的顺序搜索其子节点；183)如果当前节点有分支，则计算当前节点代表的特征集合的可分性判据，如果小于界值B，则中止该节点向下的搜索，因为其子节点的可分性判据已经不可能大于B了。否则按照从右向左的顺序搜索其子节点。分支定界算法的计算时间是不确定的，同昀优解分支所在位置有关，如果昀优解分支在昀右端，并且去掉1x或2x的可分性判据均小于昀优解，则搜索时间昀短，只需计算3组可分性判据；如果每个分支的可分性判据都大于其左端分支的可分性判据，则搜索时间昀长，需计算可分性判据的次数可能15次。19二、次优搜索算法1.顺序前进法（SequentialForwardSelection,SFS）每次从未入选的特征中选择一个特征，使得它与已入选的特征组合到一起所得到的可分性判据昀大，直到特征数增加到M为止。用kX表示在第k步时的特征集合，搜索算法如下：1)开始时，0X=∅，从N个特征中选择一个()iJx昀大的特征，加入已选特征集，{}1iXx=；2)在第k步，kX中包含已经选择的k个特征，对未入选的Nk−个特征计算，{}()kjJXxU，其中1,2,,jNk=−L，并且按照由大到小排序，将可分性判据昀大的特征lx加入kX，{}1kklXXx+=U；3)直到所选的特征数等于M为止。202.顺序后退法(SequentialBackwardSelection,SBS)同顺序前进法的过程刚好相反，昀开始时取{}01,,NXxx=L，每次从中剔除一个特征，使得剩余的特征可分性判据昀大。3.增l减r法（lr−法）前两种方法可以进一步改进，比如每次不是加入1个特征，而是加入l个特征；或者每次不是剔除一个特征，而是剔除r个特征。这样的效果要比每次加1或减1的效果好，但是计算量要增大。另外一种改进方法是将SFS和SBS结合，先使用SFS算法逐个选入l个昀佳特征，然后使用SBS算法逐个剔除r个昀差特征，lr，再使用SFS算法增加l个特征，再使用SBS剔除r个特征，…，直到选出M个特征为止。215.4特征提取特征抽取的方法很多，下面仅介绍一种基于距离的特征提取方法，其它方法与此类似。()11trWBJSS−=22235.5K-L变换Karhunen-Loeve变换（K-L变换，卡洛南-洛伊变换）。K-L展开式的昀初提出为的是将非周期随机过程表示成系数互不相关的正交函数序列。后来离散的K-L变换被广泛用于模式的特征抽取或维数压缩领域。一、基本过程设X是一个n维的随机变量，nΦΦΦ,,,21L是n维空间的正交归一化矢量系，即⎩⎨⎧≠==ΦΦ)(0)(1jijijTi24则可将X无误差地表示如下：iniiyXΦ=∑=1其中：),,2,1(niXyTiiL=Φ=现在用前r项估计X如下：∑=Φ=riiiyX1ˆ所产生的误差为∑+=Φ=−=∆nriiiyXX1ˆ显然，∆是一个随机变量，其均方误差为：)()(12∑+==∆∆=nriiTyEEε（因⎩⎨⎧≠==ΦΦ)(0)(1jijijTi）25容易推导得到：∑∑+=+=ΣΦΦ=ΦΦ=nriiTinriiTTiXXE11)(ε这里，)(TXXE=Σ为n维随机变量X的总体相关矩阵。用拉格朗日乘子法，可以求出在满足正交归一化条件下，使得均方误差ε取极值的坐标系统，即令：)1(11−ΦΦ−ΣΦΦ=∑∑+=+=iTinriinriiTigλ对iΦ分别求导，得到：),,1(0)(nriIiiL+==Φ−Σλ26令0=r，则可得到下述结论：以矩阵Σ的本征向量作为坐标轴来展开X时，其截断均方误差具有极值性质，且当取r个),,1(riiL=Φ来表示X时，其均