单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2012-2-26,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2012-2-26,#,模式识别导论,Pattern Recognition,第六章 特征的选择与提取,王文伟,Wang Wenwei,Dr.-Ing.,Tel:687-78652,Email:,Web:http:/ of Contents,6.1,引言,6.2 类别可分离性判据,6.3 特征提取与K-L变换,6.4 特征的选择,6.5 讨论,电子信息学院,6.1,基本概念,特征的选择与提取,是模式识别中重要而困难的一个环节：,分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步。,降低特征维数在很多情况下是有效设计分类器的重要课题。,三大类特征：物理、结构和数学特征,物理和结构特征,：易于为人的直觉感知，但有时难于定量描述，因而不易用于机器判别。,数学特征,：易于用机器定量描述和判别，如基于统计的特征。,引言,特征的形成,特征形成,(acquisition),：,信号获取或测量原始测量,原始特征,实例：,数字图象中的各像素灰度值,人体的各种生理指标,原始特征分析：,原始测量不能反映对象本质,高维原始特征不利于分类器设计：计算量大，冗余，样本分布十分稀疏。,引言,特征的选择与提取,两类提取有效信息、压缩特征空间的方法：特征提取和特征选择,特征提取,(extraction),：用映射（或变换）的方法把原始特征变换为较少的新特征。,特征选择,(selection),：从原始特征中挑选出一些最有代表性，分类性能最好的特征。,特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特征选择与提取方法。,引言,特征的选择与提取举例,细胞自动识别：,原始测量,：（正常与异常）细胞的数字图像,原始特征,（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比,压缩特征,：原始特征的维数仍很高，需压缩以便于分类,特征选择,：挑选最有分类信息的特征,特征提取,：数学变换,傅立叶变换或小波变换,用,PCA,方法作特征压缩,引言,6.2,类别可分离性判据,类别可分离性判据,：衡量不同特征及其组合对分类是否有效的定量准则,理想准则：某组特征使分类器错误概率最小,实际的类别可分离性判据应满足的条件：,度量特性：,与错误率有单调关系,当特征独立时有可加性：,单调性：,常见类别可分离性判据：基于距离、概率分布、熵函数,基于距离的可分性判据,类间可分性,:=,所有样本间的平均距离：,(8-1),squared Euclidian,(8-5),类内平均距离,类间,距离,(8-6),可分性判据,基于距离的可分性判据矩阵形式,基于距离的准则概念直观，计算方便，但与错误率没有直接联系,样本类间离散度矩阵,样本类内离散度矩阵,类间可分离性判据,可分性判据,基于概率的可分性判据,基于概率的可分性判据：用,概率密度函数间的距离,来度量,散度：,正态分布：,Mahalanobis,可分性判据,基于熵函数的可分性判据,熵函数：,Shannon,熵：,平方,熵：,熵函数期望表征类别的分离程度：,可分性判据,类别可分离性判据应用举例,图像分割：,Otsu,灰度图像阈值算法,(,Otsu thresholding,),图像有,L,阶灰度，,n,i,是灰度为,i,的像素数，图像总像素数,N,=,n,1,+,n,2,+,+,n,L,灰度为,i,的像素概率：,p,i,=,n,i,/,N,类间方差：,可分性判据,Otsu thresholding,灰度图像阈值,:,Otsu,灰度图像二值化算法演示及程序分析,:,可分性判据,6,.,3,特征提取与,K-L,变换,特征提取,：,用映射（或变换）的方法把原始特征变换为较少的新特征,PCA(Principle Component Analysis),方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。,K-L(Karhunen-Loeve),变换：最优正交线性变换，相应的特征提取方法被称为,PCA,方法,K-L,变换,离散,K-L,变换：对向量,x,用确定的完备正交归一向量系,u,j,展开,特征提取,离散,K-L,变换,的,均方误差,用有限项估计,x,：,该估计的均方误差：,特征提取,求解最小均方误差正交基,用,Lagrange,乘子法：,结论：,以相关矩阵,R,的,d,个本征向量为基向量来展开,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,的各分量间的相关性,，从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的,特征提取,K-L,变换图解,x,1,x,2,u,2,u,1,二次曲线方程,标准二次曲线方程,特征提取,K-L,变换的数据压缩图解,取,2x1,变换矩阵,U,=,u,1,，则,x,的,K-L,变换,y,为,：,y=,U,T,x=u,1,T,x=,y,1,变换的能量损失为,特征提取,K-L,变换的产生矩阵,数据集,K,N,=,x,i,的,K-L,变换的,产生矩阵,由数据的二阶统计量决定，即,K-L,坐标系的基向量为某种基于数据,x,的二阶统计量的产生矩阵的本征向量,K-L,变换的产生矩阵可以有多种选择：,x,的相关函数矩阵,R=E,xx,T,x,的协方差矩阵,C,=E(,x-,),(,x-,),T,样本总类内离散度矩阵：,特征提取,未知类别样本的,K-L,变换,用总体样本的协方差矩阵,C,=E(,x-,),(,x-,),T,进行,K-L,变换，,K-L,坐标系,U,=,u,1,u,2,.,u,d,按照,C,的本征值的下降次序选择,例：设一样本集的协方差矩阵是：求最优,2x1,特征提取器,U,解答：计算特征值及特征向量,V,D=eig(C);,特征值,D=24.736,2.263,T,特征向量,:,由于,1,2,，故,最优,2x1,特征提取器此时的,K-L,变换式为：,特征提取,特征选择,:=,从原始特征中挑选出一些最有代表性、分类性能最好的特征进行,分类。,从,D,个特征中选取,d,个,共,C,d,D,种组合。若不限定特征选择个数，则共,2,D,种组合 典型的,组合优化问题,特征选择的方法大体可分两大类：,Filter,方法,：根据独立于分类器的指标,J,来评价所选择的特征子集,S,，然后在所有可能的特征子集中搜索出使得,J,最大,的特征子集作为,最优特征子集,。不考虑所使用的学习算法。,Wrapper,方法,：将特征选择和分类器结合在一起，在学习过程中表现优异的的特征子集会被选中。,6,.,4,特征的选择,经典,特征选择算法,许多特征选择算法力求解决搜索问题，经典算法有：,分支定界法,:,最优搜索,，效率比,盲目穷举法,高。,单独最优特征组合法：,次优搜索。,顺序后退法,顺序前进法,模拟退火法,Tabu,搜索法,遗传算法,特征选择,单独最优特征组合,计算各,特征单独使用时的可分性判据,J,并加以排队，取前,d,个作为选择结果,不一定是最优结果,当可分性判据对各特征具有,(,广义,),可加性,，该方法可以选出一组最优的特征来，例：,各类具有正态分布,各特征统计独立,可分性判据基于,Mahalanobis,距离,特征选择,顺序前进法,自下而上,搜索方法。,每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的,J,值为最大，直至特征数增加到,d,为止。,该方法考虑了所选特征与已入选特征之间的相关性。,特征选择,顺序后退法,该方法根据特征子集的分类表现来选择特征,搜索特征子集,：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率,依次迭代，直至识别率开始下降为止,用,“,leave-one-out,”,方法估计平均识别率：用,N-1,个样本判断余下一个的类别，,N,次取平均,特征选择,模拟退火法,来源于统计力学。材料粒子从高温开始，非常缓慢地降温,(,退火,),，粒子就可在每个温度下达到热平衡。,假设材料在状态,i,的能量为,E,(,i,),，那么材料在温度,T,时从状态,i,进入状态,j,遵循如下规律：,如果,E,(,j,),E,(,i,),，接受该状态被转换。,如果,E,(,j,),E,(,i,),，则状态转换以如下概率被接受：,特征选择,模拟退火法,(II),在某一温度下，进行了充分转换后，材料达到热平衡，这时材料处于状态,i,的概率满足：,所有状态在高温下具有相同概率。,特征选择,模拟退火法,(III),当温度降至很低时，材料会以很大概率进入最小能量状态。,模拟退火优化法：,f:xR,+,，其中,xS,，表示优化问题的一个可行解。,N(x)S,表示,x,的一个邻域集合。,特征选择,模拟退火法,(IV),首先给定初始温度,T,0,和初始解,x,(0),，以概率,P,生成下一个新解,x,：,对于温度,T,i,和该优化问题的解,x,(,k,),，可以生成新解,x,。,经过多次转换，降低温度得到,T,i+1,T,i,。在,T,i+1,下重复上述过程，最终的解是对该问题寻优的结果。,特征选择,模拟退火法,(V),经过有限次转换，在温度,T,i,下的平衡态,x,i,的分布为：,当温度,T,降为,0,时，,x,i,的分布为：,特征选择,特征选择的模拟退火法,Step1:,令,i,=0,k,=0,给出初始温度,T,0,和初始,特征组合,x,(0),。,Step2:,在,x,(,k,),的邻域,N,(,x,(,k,),中选择一个状态,x,，即,新特征组合,。计算其可分性判据,J,(,x,),，并按概率,P,接受,x,(,k,+1)=,x,。,Step3:,如果在,T,i,下还未达到平衡，则转到,Step2,。,Step4:,如果,T,i,已经足够低，则结束，当时的特征组合即为算法的结果。否则继续。,Step5:,根据温度下降方法计算新的温度,T,i+1,。转到,Step2,。,特征选择,遗传算法,从生物进化论得到启迪。遗传，变异，自然选择。,基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个,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:,如果终止条件满足，则算法结束，,x,g,为算法的结果。否则继续。,Step5:,从,P(t),中选择个体并进行交叉和变异操作，得到新一代群体,P(t+1),。令,t=t+1,转到,Step3,。,特征选择,6,.,5,讨论,特征的选择与提取是模式识别中重要而困难的一步,模式识别的第一步：分析各种特征的有效性并选出最有代表性的特征,降低特征维数在很多情况下是有效设计