特征选择和特征提取

8.1基本概念特征的选择与提取是模式识别中重要而困难的一个环节：分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步。降低特征维数在很多情况下是有效设计分类器的重要课题。引言特征的形成特征形成(acquisition)：信号获取或测量→原始测量原始特征实例：数字图象中的各像素灰度值人体的各种生理指标原始特征分析：原始测量很大程度上不能反映对象本质高维原始特征不利于分类器设计：计算量大，冗余，样本分布十分稀疏。引言特征的选择与提取两类提取有效信息、压缩特征空间的方法：特征提取和特征选择特征提取(extraction)：用映射（或变换）的方法把原始特征变换为较少的新特征。特征选择(selection)：从原始特征中挑选出一些最有代表性，分类性能最好的特征。特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特征选择与提取方法。引言特征的选择与提取举例细胞自动识别：原始测量：（正常与异常）细胞的数字图像原始特征（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比压缩特征：原始特征的维数仍很高，需压缩以便于分类•特征选择：挑选最有分类信息的特征•特征提取：数学变换–傅立叶变换或小波变换–用PCA方法作特征压缩引言8.3特征提取与K-L变换特征提取：用映射（或变换）的方法把原始特征变换为较少的新特征PCA(PrincipleComponentAnalysis)方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。K-L(Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法–特征值100kkkNNANkNAIN对于一个的矩阵，有个标量，，，满足称为矩阵的一组特征值。如果给定的矩阵是奇异的，那么个特征值中至少有一个为。矩阵的秩定义为矩阵非零特征值的个数。矩阵的条件数定义为最大特征值与最小特征值的比值的绝对值。病态矩阵条件数很大。2121221121402113A例：–特征向量1,,0kkkkkkNvAvvAvAV满足下式的的向量则称为的特征向量。求特征向量的方法是解线性方程组11122212212211022122130221Avvvv例：求其特征向量。K-L变换•离散K-L变换：对向量x用标准正交向量系uj进行线性变换，得到新的向量Y.经过K－L变换组合，输出Y的各分量之间将具有最小的相关性.1jjjyxuTjjyux:Lxy特征提取离散K-L变换的均方误差用有限项估计x：1ˆdjjjyxu该估计的均方误差：ˆˆ()()TExxxx211TTjjjjdjdEyEuxxuE()TijijrxxERxx11TTTjjjjjdjdEuxxuuRu特征提取因为uj是确定性向量，所以有求解最小均方误差正交基用Lagrange乘子法，可以求出满足正交条件下的ε取极值时的坐标系统：1ifthenTjjjjjjdRuuuRu取得极值结论：以相关矩阵R的d个特征向量uj为基向量来展开x时，其截断均方误差取得最小值为：1jjdK-L变换：当取矩阵R的d个最大特征值对应的特征向量来展开x时，其截断均方误差最小。这d个特征向量组成的正交坐标系称作x所在的D维空间的d维K-L变换坐标系，x在K-L坐标系上的展开系数向量y称作x的K-L变换特征提取K-L变换的表示K-L变换的向量展开表示：TjjyuxK-L变换的矩阵表示：12[,,...,]dxuuuyUyTyUx1djjjyxu特征提取K-L变换的性质y的相关矩阵是对角矩阵：TTTTijijijTTijijjiijEyyEERuxxuuxxuuuuuTTTTEEUUUUyyxxRΛ特征提取K-L变换的性质1200dΛK-L坐标系把矩阵R对角化，即通过K-L变换消除原有向量x的各分量间的相关性，从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的特征提取主成分分析(PCA)主分量分析（PrimaryComponentAnalysis,PCA）就是基于K-L变换的提取图像特征的一种最优正交线性变换，可以有效去掉一个随机向量中各元素间的相关性。PCA的目的：寻找能够表示采样数据的最好的投影子空间.PCA的求解：特征向量常被叫做“主分量”，每个样本被它在前几个主分量上的投影近似表示，U张成的空间称为原空间的子空间，PCA实际上就是在子空间上的投影.从几何意义来看，变换后的主分量空间坐标系与变换前的空间坐标系相比旋转了一个角度。而且新坐标系的坐标轴一定指向数据信息量较大的方向。以二维空间为例，假定某样本的分布呈椭圆状，那么经过旋转后，新坐标系的坐标轴一定分别指向椭圆的长半轴和短半轴方向——主分量方向，因为长半轴这一方向的信息量最大。x1x2u2u1主成分是这个椭圆的「长轴」方向。短轴的方向和长轴垂直，是「第二个」主成分的方向。变换后的各分量，它们所包括的信息量不同，呈逐渐减少趋势。事实上，第一主分量集中了最大的信息量，常常占80％以上。第二、三主分量的信息量依次很快递减，到了第n分量，信息几乎为零。特征提取PrincipalcomponentPCA对于椭球状分布的样本集有很好的效果,学习所得的主方向就是椭球的主轴方向.PCA是一种非监督的算法,能找到很好地代表所有样本的方向,但这个方向对于分类未必是最有利的人脸识别就是将已检测到的待识别人脸与数据库中的已知人脸进行比较匹配，得出相关信息，来鉴别该人是谁。这一过程的核心是选择恰当的人脸表征方式与匹配策略，即选择合适的人脸模式的特征，根据所提取的特征进行匹配。人脸图像所包含的模式特征十分丰富,它不仅包括一些能直观感觉到的特征，如肤色、发色等颜色特征，脸的轮廓等轮廓特征，用到的更多的是不能感觉，只能通过变换等处理之后才表现出来的特征，如特征脸、小波特征等变换域特征，均值、方差等模板特征。人脸特征表述人脸特征颜色特征（肤色、发色等）变换域特征（特征脸等）启发示特征（头发等）镶嵌图特征（马赛克规则等）轮廓特征（椭圆轮廓等）模板特征（均值、方差等）直方图特征（分布、距离等）结构特征（对称性等）•基于PCA构建特征脸空间是对图像进行K-L变换，以去除样本间的相关性，然后根据特征值的大小选择特征向量。•这种方法首先将人脸图像映射为高维空间的向量，然后应用基于统计的离散K-L变换方法，构造一个各分量互不相关的特征空间，即特征脸空间，再将人脸图像在高维空间中的向量映射到特征脸空间，得到特征系数。PCA构建特征脸空间ORL标准人脸库由40人，每人10幅112×92图像组成。这些图像是拍摄于不同时期的；人的脸部表情和脸部细节有着不同程度的变化，比如，笑或不笑，眼睛或睁或闭，戴或不戴眼镜；人脸姿态也有相当程度的变化，深度旋转和平面旋转可达20度；人脸的尺度也有多达10％的变化。ORL人脸库(英国剑桥大学)①M幅人脸图像样本，其图像矩阵，将它们转化为向量形式，得到M个维向量MTTT,,21M,,21MnnM11②均值差值nnn③图像集的协方差矩阵TMnTnnAAMC11),,2,1(Mii),,2,1(Miui特征值特征向量④可以从以上求得的M个特征向量中取出对构造图像影响最大的m个，这样就可以构造了一个原始图像空间的m维子空间，这个m维子空间称为特征脸空间。,③图像集的协方差矩阵TMnTnnAAMC11),,2,1(Mii特征值特征向量,特征值与特征图像特征值ORL20人10幅×特征脸空间特征提取－LDA•线性判别分析：LinearDiscriminantAnalysis(LDA)Fisher(1936)•􀂄在线性判别函数一章，我们讲过Fisher线性判别函数。它的思想是，找一个方向作投影，使得投影后的数据类间距尽可能大，类内距尽可能小。这实际上是两类数据的特征提取，提取的特征数是１。这一思想可以推广到任意类数据，提取任意多个特征。•LDA的思想:寻找最能把两类样本分开的投影直线.•LDA的目标:使投影后两类样本的均值之差与投影样本的总类散布的比值最大.•LDA的求解:经过推导把原问题转化为关于样本集总类内散布矩阵和总类间散布矩阵的广义特征值问题.Bestprojectiondirectionforclassification多重判别分析(MDA)MDA把LDA推广到多类的情况.对于c-类问题,MDA把样本投影到c-1维子空间.目标和解法与LDA相似,只是类内散布矩阵的定义更为复杂,求解的广义特征值问题也更为复杂.-1-0.500.51-1-0.500.5105101520线性方法的缺点线性方法对于很多数据不能进行有效的处理.现实中数据的有用特性往往不是特征的线性组合.几种流形学习算法局部线性嵌入(LLE).S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.等距映射(Isomap).J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.拉普拉斯特征映射(LaplacianEigenmap).M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,Vol.15,Issue6,pp.1373–1396,2003.在这个例子里，用LLE进行降维成功的体现了数据内在的局部分布结构，而用PCA映射则会将高维空间里的远点映射到低维空间后变成了近邻点。特征选择:=从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类。从D个特征中选取d个,共CdD种组合。－典型的组合优化问题特征选择的方法大体可分两大类：Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。–Wrapper方法：将特征选择和分类器结合在一起，即特征子集的好坏标准是由分类器决定的，在学习过程中表现优异的的特征子集会被选中。8.4特征的选择dDC一种Filter算法:FOCUS•该算法致力于寻找一个能够正确区分所有类别的最小特征集合。•􀂄例如，若区分每个人的特征有：姓名、性别、籍贯、工作单位、身份证号……•则该算法会选择：身份证号•􀂄搜索时先看一个特征能否正确区分样本，若不能，则考察两个特征……以此类推经典特征选择算法许多特征选择算法力求解决搜索问题，经典算法有：􀂄分支定界法单独最优特征组合法顺序后退法顺序前进法模拟退火法Tabu搜索法遗传算法特征选择顺序前进法自下而上搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的J值为最大，直至特征数增加到d为止。该方法考虑了所选特征与已入选特征之间的相关性。特征选择顺序后退法该方法根据特征子集的分类表现来选择特