模式识别之特征选择与提取PPT文档.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,特征选择与特征提取,1,5.1,基本概念,5.2,类别可分性测度,5.3,基于类内散布矩阵的单类模式特征提取,5.4,基于,K-L,变换的多类模式特征提取,第,5,章 特征选择与特征提取,2,5.1,基本概念,由于测量上可实现性的限制或经济上的考虑，所获得的测量值为数不多。,能获得的性质测量值很多。如果全部直接作为分类特征，耗费机时，且分类效果不一定好。有人称之为,“,特征维数灾难,”,。,特征选择和提取的目的,：经过选择或变换，组成识别特征，尽可能保留分类信息，在保证一定分类精度的前提下，减少特征维数，使分类器的工作即快又准确。,1,两种数据测量情况,3,(1),具有很大的识别信息量。即应具有很好的可分性。,(2),具有可靠性。模棱两可、似是而非、时是时非等不易判别,的特征应丢掉。,(3),尽可能强的独立性。重复的、相关性强的特征只选一个。,(4),数量尽量少，同时损失的信息尽量小。,2,对特征的要求,3.,特征选择和特征提取的异同,（,1,）特征选择：从,L,个度量值集合 中按一定准,则,选出,供分类用的子集，作为降维（,m,维，,m,L,）的分类,特征。,（,2,）特征提取：使一组度量值 通过某种,变换,产生新的,m,个特征 ，作为降维的分类特征，,其中 。,4,(c),是具有分类能力的特征，故选,(c),，,扔掉,(a),、,(b),。,B,A,解：,法,1,特征抽取：测量三个结构特征,(a),周长,(b),面积,(c),两个互相垂直的内径比,特征选择：一般根据物理特征或结构特征进行压缩。,分析：,例：特征选择与特征提取的区别：对一个条形和圆进行识别。,当模式在空间中发生移动、旋转、缩放时，特征值应保持不变，保证仍可得到同样的识别效果。,5,法,2,：特征抽取：测量,物体向两个坐标轴的投影,值，则,A,、,B,各有,2,个值域区,间。可以看出，两个物体的,投影有重叠，直接使用投影,值无法将两者区分开。,特征选择：,将坐标系按逆时针方向做一旋转变化，或物体按顺时针方向变，并适当平移等。根据物体在,轴上投影的坐标值的正负可区分两个物体。,特征提取，一般用数学的方法进行压缩。,B,A,B,A,6,5.2,类别可分性测度,5.2.1,基于距离的可分性测度,类别可分性测度：衡量类别间可分性的尺度。,相似性测度：衡量模式之间相似性的一种尺度,类内距离和类间距离,类概率密度函数,类别可,分性测度,空间分布：,随机模式向量：,错误率,与错误率有关的距离,1,类内距离和类内散布矩阵,1),类内距离：同一类模式点集内，各样本间的均方距离。,平方形式：,X,i,，,X,j,：,n,维模式点集,X,中的任意两个样本。,7,特征选择和提取的结果应使类内散布矩阵的迹愈？愈好。,特征选择和提取的结果应使类内散布矩阵的迹愈,小,愈好。,若,X,中的样本相互独立，有,式中，,R,：该类模式分布的自相关矩阵；,M,：均值向量；,C,：协方差矩阵；,：,C,主对角线上的元素，表示模式向量第,k,个分量的方差；,tr,：矩阵的迹（方阵主对角线上各元素之和）。,2),类内散布矩阵：表示各样本点围绕均值的散布情况,即该类分布的协方差矩阵。,类,8,类间散布矩阵的迹愈,大,愈有利于分类。,2,类间距离和类间散布矩阵,1),类间距离：模式类之间的距离，记为 。,每类模式均值向量,与模式总体均值向,量之间平方距离的,先验概率加权和。,2),类间散布矩阵：表示,c,类模式在空间的散布情况，记为,S,b,。,类间散布矩阵的迹愈？愈有利于分类。,3),类间距离与类间散布矩阵的关系：,注意：与类间距离的转置位置不同。,9,3,多类模式向量间的距离和总体散布矩阵,1,）两类情况的距离,q,个,p,个,共,p,q,个距离,两个类区之间的距离,=,p,q,个距离的平均距离,多类间任意两个点间距离的平均距离,类似地 多类情况,多类间任意两个点间,平方距离,的平均值,10,（,5-8,）,类的均值向量：,（,5-10,）,c,类模式总体的均值向量：,（,5-11,）,2,）多类情况的距离,(2),J,d,的另一种形式：将以下,3,式代入,(5-8),式,(1),多类模式向量间的平均平方距离,J,d,（,5-9,）,平方距离：,任意类的组合,特定两类间,任意样本的组合,11,得,某类类内平方,距离平均值,某类类间,平方距离,多类模式向量之间的平方距离,=,各类平方距离的先验概率加权和,某类的平方距离,模式类间的距离,模式类内的距离,多类模式向量之间的距离,3,）多类情况的散布矩阵,多类类间散布矩阵：,12,4,）多类模式平均平方距离与总体散布矩阵的关系,多类类内散布矩阵：,各类模式协方差矩阵的,先验概率加权平均值。,多类模式的总体散布矩阵：,得,13,距离与散布矩阵作为可分性测度的特点：,*计算方便，概念直观反映模式的空间分布情况）；,*与分类错误率没有直接的联系。,5.2.2,基于概率分布的可分性测度,1,散度,出发点：对数似然比含有类别的可分性信息。,1,）散度的定义,14,对不同的,X,，似然函数不同，对数似然比体现的可分性,不同，通常采用平均可分性信息,对数似然比的期望值。,类对数似然比的期望值：,类对数似然比的期望值：,散度等于两类的对数似然比期望值之和。,15,散度表示了,区分,i,类和,j,类的总的平均信息。,2,）散度的性质,（,1,）,特征选择和特征提取应,使散度尽可能的？,特征选择和特征提取应,使散度尽可能的大,。,16,（,3,）错误率分析中，两类概率密度曲线交叠越少，错误率越小。,由散度的定义式,可知，散度愈大，两类概率密度函数曲线相差愈大，交叠愈少，,分类错误率愈小。,17,据此可估计每一个特征在分类中的重要性：,散度较大的特征含有较大的可分信息,保留。,（,5,）可加性表明，加入新的特征，不会使散度减小。即,3,）两个正态分布模式类的散度,设,i,类和,j,类的概率密度函数分别为,18,两类模式之间马氏距离的平方,一维正态分布时：,两类均值向量距离越远，散度愈大,每类自身分布愈集中，,两类间的散度愈大,模式识别导论（齐敏）,p135,19,5.3,基于类内散布矩阵的单类模式特征提取,对某类模式：压缩模式向量的维数。,对多类分类：压缩维数；,保留类别间的鉴别信息，突出可分性。,特征提取的目的：,特征提取操作方法：,m,1,m,n n,1,(,m,n,),注意：维数降低后，在新的,m,维空间里各模式类之间的分布规,律应至少保持不变或更优化。,20,讨论内容：,*根据类内散布矩阵如何确定变换矩阵,A,；,*通过,A,如何进行特征提取。,1,根据类内散布矩阵确定变换矩阵,式中，,X,为,n,维向量，,C,为,n,n,的实对称矩阵。,21,n,个特征向量相互正交，且都是单位长度。,若选,n,个归一化特征向量作为,A,的行，则,A,为归一化正交矩阵：,22,(1),(2),A,nn,23,(3),变换后的类内距离,变换后：类内距离保持不变。,24,根据以上特点得到构造变换矩阵的方法：,思路：,目标：构造一变换矩阵，可以将,n,维向量,X,变换成,m,维（,m,n,）。,将变换前的,C,的,n,个特征值从小到大排队,选择前,m,个小的特征值对应的特征向量,作为矩阵,A,的行（,m,n,）,对,X,进行,A,变换,优点：压缩了维数；,类内距离减小，样本更密集,相当去掉了方差大的特征分量。,后 续,25,2,特征提取的方法,其中，,第二步：计算,C,的特征值，对特征值从小到大进行排队，选择,前,m,个。,26,第四步：利用,A,对样本集,X,进行变换。,则,m,维（,m,n,）模式向量,X,*,就是作为分类用的模式向量。,解：,1),求样本均值向量和协方差矩阵。,27,由,得,由归一化特征向量,u,1,构成变换矩阵,A,：,28,变换前,变换后,29,5.4,基于,K-L,变换的多类模式特征提取,对一类模式：维数压缩。,对多类模式：维数压缩，突出类别的可分性。,特征提取的目的：,卡洛南,-,洛伊（,Karhunen-Loeve,）变换（,K-L,变换）：,*,一种常用的特征提取方法；,*,最小均方误差意义下的最优正交变换；,*,适用于任意的概率密度函数；,*,在消除模式特征之间的相关性、突出差异性方面,有最优的效果。,离散,K-L,变换,连续,K-L,变换,分为：,30,1,K-L,展开式,a,j,：随机系数；,用有限项估计,X,时,：,引起的均方误差：,代入,X,、，利用,31,由 两边 左乘 得 。,u,j,为确定性向量,R,：自相关矩阵。,：拉格朗日乘数,32,说明：当用,X,的自相关矩阵,R,的特征值对应的特征向量展开,X,时，截断误差最小。,选前,d,项估计,X,时引起的均方误差为,因此，当用,X,的正交展开式中前,d,项估计,X,时，展开式中,的,u,j,应当是前,d,个较大的特征值对应的特征向量。,33,K-L,变换方法：,对,R,的特征值由大到小进行排队：,均方误差最小的,X,的近似式：,矩阵形式：,式中，。,其中：,（,5-49,）,K-L,展开式,对式,(5-49),两边左乘,U,t,：,K-L,变换,系数向量,a,就是变换后的模式向量。,自相关矩阵,34,2,利用自相关矩阵的,K-L,变换进行特征提取,第一步：求样本集,X,的总体自相关矩阵,R,。,决定压缩,后的维数,35,3,不同散布矩阵的,K-L,变换,根据不同的散布矩阵进行,K-L,变换，对保留分类鉴别信息,的效果不同。,多类类内散布矩阵：,若要突出各类模式的主要特征分量：,选用对应于大特征值的特征向量组成变换矩阵；,若要使同一类模式聚集于最小的特征空间范围：,选用对应于小特征值的特征向量组成变换矩阵。,类间散布矩阵：,36,适用于类间距离比类内距离大得多的多类问题，选择,与大,特征值对应的特征向量,组成变换矩阵。,总体散布矩阵：,把多类模式合并起来看成一个总体分布。,适合于多类模式在总体分布上具有良好的可分性的情况。,采用大特征值对应的特征向量组成变换矩阵，,能够保留模式原有分布的主要结构。,1,）变换在均方误差最小的意义下使新样本集,X,*,逼近原样本集,X,的分布，既压缩了维数又保留了类别鉴别信息。,利用,K-L,变换进行特征提取的优点：,37,2,）变换后的新模式向量各分量相对总体均值的方差等于原样本,集总体自相关矩阵的大特征值，表明变换突出了模式类之间,的差异性。,3,）,C,*,为对角矩阵说明了变换后样本各分量互不相关，亦即消,除了原来特征之间的相关性，便于进一步进行特征的选择。,K-L,变换的不足之处：,1,）对两类问题容易得到较满意的结果。类别愈多，效果愈差。,2,）需要通过足够多的样本估计样本集的协方差矩阵或其它类,型的散布矩阵。当样本数不足时，矩阵的估计会变得十分粗略，变换的优越性也就不能充分的地显示出来。,38,3,）计算矩阵的本征值和本征向量缺乏统一的快速算法，给计算,带来困难。,例,5.3,两个模式类的样本分别为,利用自相关矩阵,R,作,K-L,变换，把原样本集压缩成一维样本集。,解：第一步：计算总体自相关矩阵,R,。,第二步：计算,R,的本征值，并选择较大者。由 得,39,40,多类类内散布矩阵,S,w,5.5,特征选择,从,n,个特征中选择,d,个,(,d,n,),最优特征构成分类用特征向量。,5.5.1,特征选取择的准则,1,散布矩阵准则,类别可分性测度,类间散布矩阵,S,b,多类总体散布矩阵,S,t,特征选择准则,使,tr(,S,w,),最小,使,tr(,S,b,),最大,使,J,1,J,4,最大,41,2,散度准则,用于正态分布的模式类。,两类的散度表达式,*,平均散度,选择使,J,最大的特征子集,*,变换散度,*,平均变换散度,42,5.5.2,特征选择的方法,从,n,个特征中挑选,d,个特征，所有可能的特征子集数为,组合数很大,穷举法：,计算出各种可能特征组合的某个测度值，加以比较，选,择最优特征组。,特点：,计算量大，难实现。采取搜索技术可降低计算量。,可以得到最优特征组；,1,最优搜索算法,分支定界算法：唯一能获得最优结果的搜索方法。,自上而下、具有回溯功能。,43,使用条件：,可分性测度,J,对维数单调。,方法：,待选择的,n,个原特征为根；,*,将可能的特征组构成树结构。,子结点的特征组元素个数逐级下降；,叶结点按照规定的特征数构成特征组合。,*,从最右边的叶结点开始，根据选择的测度回溯搜索。,*,找到最优特征组，结束。,44,例：从,5,个特征中选出,2,个特征作为模式向量。,45,2,次优搜索算法,虽然不能得到最优解，但可减少计算量。,1,）单独最优特征组合,2,）顺序前进法（,Sequential Forward Selection,，,SFS,）,3,）顺序后退法（,Sequential Backward Selection,，,SBS,）,4,）增,l,减,r,法（,l,r,法）：,SFS,和,SBS,的组合。,广义顺序前进法（,Generalized SFS,，,GSFS,）,广义顺序后退法（,Generalized SBS,，,GSBS,）,广义的,l,r,法,其他：模拟退火（,Simulated Annealing,）算法,Tabu,搜索（,Tabu Search,）算法,遗传算法（,Genetic Algorithm,）,46,结束,47,