特征选择和特征提取

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,模式识别原理与应用,专 业：模式识别与智能系统,学生姓名：*,任课教师：余老师,一、基本概念,特征的选择与提取,是模式识别中重要而困难的一个环节：,分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步。,降低特征维数在很多情况下是有效设计分类器的重要课题。,引言,特征的形成,特征形成,(acquisition),：,信号获取或测量原始测量,原始特征,实例,：,数字图象中的各像素灰度值,人体的各种生理指标,原始特征分析：,原始测量很大程度上不能反映对象本质,高维原始特征不利于分类器设计：计算量大，冗余，样本分布十分稀疏。,引言,二、特征的选择与提取,两类提取有效信息、压缩特征空间的方法：特征提取和特征选择,特征提取,(extraction),：,用映射（或变换）的方法把原始特征变换为较少的新特征,。,特征选择,(selection),：,从原始特征中挑选出一些最有代表性，分类性能最好的特征。,特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特征选择与提取方法。,特征的选择与提取举例,细胞自动识别：,原始测量,：（正常与异常）细胞的数字图像,原始特征,（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比,压缩特征,：原始特征的维数仍很高，需压缩以便于分类,特征选择,：挑选最有分类信息的特征,特征提取,：数学变换,傅立叶变换或小波变换,用,PCA,方法作特征压缩,三、特征提取与,K-L,变换,特征提取,：用映射（或变换）的方法把原始特征变换为较少的新特征,PCA(Principle Component Analysis),方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。,K-L(Karhunen-Loeve),变换：最优正交线性变换，相应的特征提取方法被称为,PCA,方法,特征值,特征向量,K-L,变换,离散,K-L,变换：对向量,x,用标准正交向量系,u,j,进行线性变换，得到新的向量,Y.,经过,K,L,变换组合，输出,Y,的各分量之间将具有最小的相关性,.,特征提取,离散,K-L,变换,的,均方误差,用有限项估计,x,：,该估计的均方误差：,特征提取,因为,uj,是确定性向量，所以有,求解最小均方误差正交基,用,Lagrange,乘子法，可以求出满足正交条件下的,取极值时的坐标系统,：,结论：,以相关矩阵,R,的,d,个特征向量,u,j,为基向量来展开,x,时，其截断均方误差取得最小值为,：,K-L,变换,：当取矩阵,R,的,d,个最大特征值对应的特征向量,来展开,x,时，其截断均方误差最小。这,d,个特征向量组成的正交坐标系称作,x,所在的,D,维空间的,d,维,K-L,变换坐标系,，,x,在,K-L,坐标系上的展开系数向量,y,称作,x,的,K-L,变换,特征提取,K-L,变换的表示,K-L,变换的,向量展开表示,：,K-L,变换的,矩阵表示,：,特征提取,K-L,变换的性质,y,的相关矩阵是对角矩阵：,特征提取,K-L,变换的性质,K-L,坐标系把矩阵,R,对角化，即,通过,K-L,变换消除原有向量,x,的各分量间的相关性,，从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的,特征提取,主成分分析,(PCA),主分量分析（,Primary Component Analysis,PCA,）就是基于,K-L,变换的提取图像特征的一种最优正交线性变换，可以有效去掉一个随机向量中各元素间的相关性。,PCA,的目的：寻找能够表示采样数据的最好的投影子空间,.,PCA,的求解：特征向量常被叫做“主分量”，每个样本被它在前几个主分量上的投影近似表示，,U,张成的空间称为原空间的子空间，,PCA,实际上就是在子空间上的投影,.,从几何意义来看，变换后的主分量空间坐标系与变换前的空间坐标系相比旋转了一个角度。而且新坐标系的坐标轴一定指向数据信息量较大的方向。以二维空间为例，假定某样本的分布呈椭圆状，那么经过旋转后，新坐标系的坐标轴一定分别指向椭圆的长半轴和短半轴方向,主分量方向，因为长半轴这一方向的信息量最大。,x,1,x,2,u,2,u,1,主成分是,这个椭圆,的,长轴,方向。,短轴,的方向和,长轴,垂直，是,第二个,主成分的方向。,变换后的各分量，它们所包括的信息量不同，呈逐渐减少趋势。事实上，第一主分量集中了最大的信息量，常常占,80,以上。第二、三主分量的信息量依次很快递减，到了第,n,分量，信息几乎为零。,Principal,component,PCA,对于椭球状分布的样本集有很好的效果,学习所得的主方向就是椭球的主轴方向,.,PCA,是一种非监督的算法,能找到很好地代表所有样本的方向,但这个方向对于分类未必是最有利的,人脸识别就是将已检测到的待识别人脸与数据库中的已知人脸进行比较匹配，得出相关信息，来鉴别该人是谁。这一过程的核心是选择恰当的人脸表征方式与匹配策略，即选择合适的人脸模式的特征，根据所提取的特征进行匹配。,人脸图像所包含的模式特征十分丰富,它不仅包括一些能直观感觉到的特征，如肤色、发色等颜色特征，脸的轮廓等轮廓特征，用到的更多的是不能感觉，只能通过变换等处理之后才表现出来的特征，如特征脸、小波特征等变换域特征，均值、方差等模板特征。,人脸特征表述,基于,PCA,构建特征脸空间是对图像进行,K-L,变换，以去除样本间的相关性，然后根据特征值的大小选择特征向量。,这种方法首先将人脸图像映射为高维空间的向量，然后应用基于统计的离散,K-L,变换方法，构造一个各分量互不相关的特征空间，即特征脸空间，再将人脸图像在高维空间中的向量映射到特征脸空间，得到特征系数。,PCA,构建特征脸空间,ORL,标准人脸库由,40,人，每人,10,幅,11292,图像组成。这些图像是拍摄于不同时期的；人的脸部表情和脸部细节有着不同程度的变化，比如，笑或不笑，眼睛或睁或闭，戴或不戴眼镜；人脸姿态也有相当程度的变化，深度旋转和平面旋转可达,20,度；人脸的尺度也有多达,10,的变化。,ORL,人脸库,(,英国剑桥大学,),M,幅人脸图像样本，其图像矩阵,，,将它们转化为向量,形式，得到,M,个维向量,均值,差值,图像集的协方差矩阵,特征值,特征向量,可以从以上求得的,M,个特征向量中取出对构造图像影响最大的,m,个，这样就可以构造了一个原始图像空间的,m,维子空间，这个,m,维子空间称为特征脸空间。,图像集的协方差矩阵,特征值,特征向量,特征值与特征图像,特征值,ORL 20,人,10,幅,特征脸空间,特征提取,LDA,线性判别分析：,LinearDiscriminantAnalysis(LDA)Fisher(1936),在线性判别函数一章，我们讲过,Fisher,线性判别函数。它的思想是，找一个方向作投影，使得投影后的数据类间距尽可能大，类内距尽可能小。这实际上是两类数据的特征提取，提取的特征数是。这一思想可以推广到任意类数据，提取任意多个特征。,LDA,的思想,:,寻找最能把两类样本分开的投影直线,.,LDA,的目标,:,使投影后两类样本的均值之差与投影样本的总类散布的比值最大,.,LDA,的求解,:,经过推导把原问题转化为关于样本集总类内散布矩阵和总类间散布矩阵的广义特征值问题,.,Best projection direction for classification,多重判别分析,(MDA),MDA,把,LDA,推广到多类的情况,.,对于,c-,类问题,MDA,把样本投影到,c-1,维子空间,.,目标和解法与,LDA,相似,只是类内散布矩阵的定义,更为复杂,求解的广义特征值问题也更为复杂,.,线性方法的缺点,线性方法对于很多数据不能进行有效的处理,.,现实中数据的有用特性往往不是特征的,线性,组合,.,几种流形学习算法,局部线性嵌入,(LLE).,S.T.Roweis and L.K.Saul.Nonlinear dimensionality reduction by locally linear embedding.,Science,vol.290,pp.2323-2326,2000.,等距映射,(Isomap),.,J.B.Tenenbaum,V.de Silva,and J.C.Langford.A global geometric framework for nonlinear dimensionality reduction.,Science,vol.290,pp.2319-2323,2000.,拉普拉斯特征映射,(Laplacian Eigenmap),.,M.Belkin,P.Niyogi,Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.,Neural Computation,Vol.15,Issue 6,pp,.,1373,1396,2003.,在这个例子里，用,LLE,进行降维成功的体现了数据内在的局部分布结构，而用,PCA,映射则会将高维空间里的远点映射到低维空间后变成了近邻点。,特征选择,:=,从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类。,从,D,个特征中选取,d,个,共,C,d,D,种组合。典型的,组合优化问题,特征选择的方法大体可分两大类：,Filter,方法,：根据独立于分类器的指标,J,来评价所选择的特征子集,S,，然后在所有可能的特征子集中搜索出使得,J,最大,的特征子集作为,最优特征子集,。不考虑所使用的学习算法。,Wrapper,方法,：将特征选择和分类器结合在一起，即特征子集的好坏标准是由分类器决定的，在学习过程中表现优异的的特征子集会被选中。,四、特征的选择,一种,Filter,算法,:FOCUS,该算法致力于寻找一个能够正确区分所有类别的最小特征集合。,例如，若区分每个人的特征有：姓名、性别、籍贯、工作单位、身份证号,则该算法会选择：身份证号,搜索时先看一个特征能否正确区分样本，若不能，则考察两个特征,以此类推,经典,特征选择算法,许多特征选择算法力求解决搜索问题，经典算法有：,分支定界法,单独最优特征组合法,顺序后退法,顺序前进法,模拟退火法,Tabu,搜索法,遗传算法,特征选择,顺序前进法,自下而上,搜索方法。,每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的,J,值为最大，直至特征数增加到,d,为止。,该方法考虑了所选特征与已入选特征之间的相关性。,特征选择,顺序后退法,该方法根据特征子集的分类表现来选择特征,搜索特征子集,：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率,依次迭代，直至识别率开始下降为止,用,“,leave-one-out,”,方法估计平均识别率：用,N-1,个样本判断余下一个的类别，,N,次取平均,特征选择,遗传算法,从生物进化论得到启迪。遗传，变异，自然选择。,基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个,D,位的,0/1,构成的串表示一种特征组合。,群体：若干个个体的集合，即问题的一些解的集合。,交叉：由当前两个个体的链码交叉产生新一代的个体。,变异：由一个链码随机某基因使其翻转。,特征选择,遗传算法,适应度：每个个体,x,i,的函数值,f,i,，个体,x,i,越好，,f,i,越大。新一代群体对环境的平均适应度比父代高。,遗传算法的基本框架：,Step1:,令进化代数,t,=0,。,Step2:,给出初始化群体,P(t),，令,x,g,为任一个体。,Step3:,对,P(t),中每个个体估值，并将群体中最优解,x,与,x,g,比较，如果,x,的性能优于,x,g,，则,x,g,=x,Step4:,如果终止条