特征选择和特征提取.ppt

模式识别原理与应用 专 业：模式识别与智能系统 学生姓名：*任课教师：余老师,一、基本概念,特征的选择与提取是模式识别中重要而困难的一个环节：分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步。降低特征维数在很多情况下是有效设计分类器的重要课题。,引言,特征的形成,特征形成(acquisition)：信号获取或测量原始测量原始特征实例：数字图象中的各像素灰度值人体的各种生理指标原始特征分析：原始测量很大程度上不能反映对象本质高维原始特征不利于分类器设计：计算量大，冗余，样本分布十分稀疏。,引言,二、特征的选择与提取,两类提取有效信息、压缩特征空间的方法：特征提取和特征选择特征提取(extraction)：用映射（或变换）的方法把原始特征变换为较少的新特征。特征选择(selection)：从原始特征中挑选出一些最有代表性，分类性能最好的特征。特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特征选择与提取方法。,特征的选择与提取举例,细胞自动识别：原始测量：（正常与异常）细胞的数字图像原始特征（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比压缩特征：原始特征的维数仍很高，需压缩以便于分类特征选择：挑选最有分类信息的特征特征提取：数学变换傅立叶变换或小波变换用PCA方法作特征压缩,三、特征提取与K-L变换,特征提取：用映射（或变换）的方法把原始特征变换为较少的新特征PCA(Principle Component Analysis)方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。K-L(Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法,特征值,特征向量,K-L变换,离散K-L变换：对向量x用标准正交向量系uj进行线性变换，得到新的向量Y.经过KL变换组合，输出Y的各分量之间将具有最小的相关性.,特征提取,离散K-L变换的均方误差,用有限项估计x：,该估计的均方误差：,特征提取,因为uj是确定性向量，所以有,求解最小均方误差正交基,用Lagrange乘子法，可以求出满足正交条件下的取极值时的坐标系统：,结论：以相关矩阵R的d个特征向量uj为基向量来展开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实际上就是在子空间上的投影.,从几何意义来看，变换后的主分量空间坐标系与变换前的空间坐标系相比旋转了一个角度。而且新坐标系的坐标轴一定指向数据信息量较大的方向。以二维空间为例，假定某样本的分布呈椭圆状，那么经过旋转后，新坐标系的坐标轴一定分别指向椭圆的长半轴和短半轴方向主分量方向，因为长半轴这一方向的信息量最大。,主成分是这个椭圆的长轴方向。短轴的方向和长轴垂直，是第二个主成分的方向。变换后的各分量，它们所包括的信息量不同，呈逐渐减少趋势。事实上，第一主分量集中了最大的信息量，常常占80以上。第二、三主分量的信息量依次很快递减，到了第n分量，信息几乎为零。,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个,共CdD种组合。典型的组合优化问题特征选择的方法大体可分两大类：Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。Wrapper方法：将特征选择和分类器结合在一起，即特征子集的好坏标准是由分类器决定的，在学习过程中表现优异的的特征子集会被选中。,四、特征的选择,一种Filter算法:FOCUS,该算法致力于寻找一个能够正确区分所有类别的最小特征集合。例如，若区分每个人的特征有：姓名、性别、籍贯、工作单位、身份证号则该算法会选择：身份证号搜索时先看一个特征能否正确区分样本，若不能，则考察两个特征以此类推,经典特征选择算法,许多特征选择算法力求解决搜索问题，经典算法有：分支定界法单独最优特征组合法顺序后退法顺序前进法模拟退火法Tabu搜索法遗传算法,特征选择,顺序前进法,自下而上搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的J值为最大，直至特征数增加到d为止。该方法考虑了所选特征与已入选特征之间的相关性。,特征选择,顺序后退法,该方法根据特征子集的分类表现来选择特征搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率依次迭代，直至识别率开始下降为止用“leave-one-out”方法估计平均识别率：用N-1个样本判断余下一个的类别，N次取平均,特征选择,遗传算法,从生物进化论得到启迪。遗传，变异，自然选择。基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1构成的串表示一种特征组合。群体：若干个个体的集合，即问题的一些解的集合。交叉：由当前两个个体的链码交叉产生新一代的个体。变异：由一个链码随机某基因使其翻转。,特征选择,遗传算法,适应度：每个个体xi的函数值fi，个体xi越好，fi越大。新一代群体对环境的平均适应度比父代高。遗传算法的基本框架：,Step1:令进化代数t=0。Step2:给出初始化群体P(t)，令xg为任一个体。Step3:对P(t)中每个个体估值，并将群体中最优解x与xg比较，如果x的性能优于xg，则xg=x Step4:如果终止条件满足，则算法结束，xg为算法的结果。否则继续。Step5:从P(t)中选择个体并进行交叉和变异操作，得到新一代群体P(t+1)。令t=t+1,转到Step3。,特征选择,Initialsolutions,start,encoding,chromosome,crossover,mutation,solutions candidates,decoding,fitness computation,evaluation,roulette wheel,selection,termination condition?,Y,N,best solution,stop,newpopulation,offspring,offspring,t 0 P(t),CC(t),CM(t),P(t)+C(t),遗传算法的求解步骤,模拟退火法,模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在 每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到 解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终 止时的当前解即为所得近似最优解。,特征选择,假设材料在状态i的能量为E(i)，那么材料在温度T时从状态i进入状态j遵循如下规律：如果E(j)E(i)，接受该状态被转换。如果E(j)E(i)，则状态转换以如下概率被接受：,模拟退火法(II),在某一温度下，进行了充分转换后，材料达到热平衡，这时材料处于状态i的概率满足：,所有状态在高温下具有相同概率。,特征选择,S：状态空间集合,模拟退火法(III),当温度降至很低时，材料会以很大概率进入最小能量状态。,模拟退火优化法：f:xR+，其中xS，表示优化问题的一个可行解。N(x)S表示x的一个邻域集合。,特征选择,Smin=i：E（i）=E min,模拟退火法(IV),首先给定初始温度T0和初始解x(0)，以概率P生成下一个新解x：,对于温度Ti和该优化问题的解x(k)，可以生成新解x。经过多次转换，降低温度得到Ti+1Ti。在Ti+1下重复上述过程，最终的解是对该问题寻优的结果。,特征选择,模拟退火法(V),经过有限次转换，在温度Ti下的平衡态xi的分布为：,当温度T降为0时，xi的分布为：,特征选择,特征选择的模拟退火法,Step1:令i=0,k=0,给出初始温度T0和初始特征组合x(0)。Step2:在x(k)的邻域N(x(k)中选择一个状态x，即新特征组合。计算其可分性判据J(x)，并按概率P接受x(k+1)=x。Step3:如果在Ti下还未达到平衡，则转到Step2。Step4:如果Ti已经足够低，则结束，当时的特征组合即为算法的结果。否则继续。Step5:根据温度下降方法计算新的温度Ti+1。转到Step2。,特征选择,