特征选择和特征提取.ppt

《特征选择和特征提取.ppt》由会员分享，可在线阅读，更多相关《特征选择和特征提取.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 模式识别原理与应用模式识别原理与应用 专专 业：业：模式识别与智能系统模式识别与智能系统 学生姓名：学生姓名：*任课教师：任课教师：余老师余老师一、基本概念u特征的选择与提取特征的选择与提取是模式识别中重要而困是模式识别中重要而困难的一个环节：难的一个环节：分析各种特征的有效性并选出最有代表性的特分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步。征是模式识别的关键一步。降低特征维数在很多情况下是有效设计分类器降低特征维数在很多情况下是有效设计分类器的重要课题。的重要课题。引言特征的形成uu特征形成特征形成 (acquisition)(acquisition)：信号获取或测量原始

2、测量原始特征u实例：数字图象中的各像素灰度值人体的各种生理指标u原始特征分析：原始测量很大程度上不能反映对象本质高维原始特征不利于分类器设计：计算量大，冗余，样本分布十分稀疏。引言二、特征的选择与提取u两类提取有效信息、压缩特征空间的方法：两类提取有效信息、压缩特征空间的方法：特征提取和特征选择特征提取和特征选择u特征提取特征提取(extraction)：用映射（或变换）用映射（或变换）的方法把原始特征变换为较少的新特征的方法把原始特征变换为较少的新特征。u特征选择特征选择(selection)：从原始特征中挑选出从原始特征中挑选出一些最有代表性，分类性能最好的特征。一些最有代表性，分类性能最

3、好的特征。u特征的选择与提取与具体问题有很大关系，特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特目前没有理论能给出对任何问题都有效的特征选择与提取方法。征选择与提取方法。特征的选择与提取举例u细胞自动识别：原始测量：（正常与异常）细胞的数字图像原始特征（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比压缩特征：原始特征的维数仍很高，需压缩以便于分类特征选择：挑选最有分类信息的特征特征提取：数学变换傅立叶变换或小波变换用PCA方法作特征压缩三、特征提取与K-L变换u特征提取：用映射（或变换）的方法把原始特征变换为较少的

4、新特征uPCA(PrincipleComponentAnalysis)方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。uK-L(Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法特征值特征值特征向量特征向量K-L变换离散K-L变换：对向量x用标准正交向量系uj进行线性变换，得到新的向量Y.经过KL变换组合，输出Y的各分量之间将具有最小的相关性.特征提取离散K-L变换的均方误差u用有限项估计x：uu该估计的均方误差：该估计的均方误差：特征提取因为uj是确定性向量，所以有求解最小均方误差正交基u

5、用Lagrange乘子法，可以求出满足正交条件下的取极值时的坐标系统：u结论：以相关矩阵R R的d个特征向量uj为基向量来展开x x时，其截断均方误差取得最小值为：uK-L变换：当取矩阵R R的d个最大特征值对应的特征向量来展开x x时，其截断均方误差最小。这d个特征向量组成的正交坐标系称作x x所在的D维空间的d维K-L变换坐标系，x x在K-L坐标系上的展开系数向量y y称作x x的K-L变换特征提取K-L变换的表示uK-L变换的变换的向量展开表示向量展开表示：uK-L变换的变换的矩阵表示矩阵表示：特征提取K-L变换的性质uy的相关矩阵是对角矩阵：特征提取K-L变换的性质uK-L坐标系把矩

6、阵坐标系把矩阵R R对角化，即对角化，即通过通过K-L变换消除原有向量变换消除原有向量x的各分量间的相关的各分量间的相关性性，从而有可能去掉那些带有较少信息，从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的的分量以达到降低特征维数的目的特征提取主成分分析主成分分析(PCA)主分量分析（主分量分析（Primary Component Analysis,PCA）就）就是基于是基于K-L变换的提取图像特征的一种最优正交线性变变换的提取图像特征的一种最优正交线性变换，可以有效去掉一个随机向量中各元素间的相关性。换，可以有效去掉一个随机向量中各元素间的相关性。PCA的目的：寻找能够表示采样数

7、据的最好的投影子的目的：寻找能够表示采样数据的最好的投影子空间空间.PCA的求解：特征向量常被叫做的求解：特征向量常被叫做“主分量主分量”，每个样，每个样本被它在前几个主分量上的投影近似表示，本被它在前几个主分量上的投影近似表示，U张成的空张成的空间称为原空间的子空间，间称为原空间的子空间，PCA实际上就是在子空间上的实际上就是在子空间上的投影投影.从从几几何何意意义义来来看看，变变换换后后的的主主分分量量空空间间坐坐标标系系与与变变换换前前的的空空间间坐坐标标系系相相比比旋旋转转了了一一个个角角度度。而而且且新新坐坐标标系系的的坐坐标标轴轴一一定定指指向向数数据据信信息息量量较较大大的的方方

8、向向。以以二二维维空空间间为为例例，假假定定某某样样本本的的分分布布呈呈椭椭圆圆状状，那那么么经经过过旋旋转转后后，新新坐坐标标系系的的坐坐标标轴轴一一定定分分别别指指向向椭椭圆圆的的长长半半轴轴和和短短半半轴轴方方向向主主分量方向，因为长半轴这一方向的信息量最大。分量方向，因为长半轴这一方向的信息量最大。x1x2u2u1主成分是这个椭圆的长轴方向。短轴的方向和长轴垂直，是第二个主成分的方向。变换后的各分量，它们所包括的信息量不同，呈逐渐减少趋势。事实上，第一主分量集中了最大的信息量，常常占80以上。第二、三主分量的信息量依次很快递减，到了第n分量，信息几乎为零。Principalcompon

9、ent PCA对于椭球状分布的样本集有很好的效果对于椭球状分布的样本集有很好的效果,学习所学习所得的主方向就是椭球的主轴方向得的主方向就是椭球的主轴方向.PCA 是一种非监督的算法是一种非监督的算法,能找到很好地代表所有样能找到很好地代表所有样本的方向本的方向,但这个方向对于分类未必是最有利的但这个方向对于分类未必是最有利的人脸识别就是将已检测到的待识别人脸与数据库中的已知人脸进行比较匹配，得出相关信息，来鉴别该人是谁。这一过程的核心是选择恰当的人脸表征方式与匹配策略，即选择合适的人脸模式的特征，根据所提取的特征进行匹配。人脸图像所包含的模式特征十分丰富,它不仅包括一些能直观感觉到的特征，如肤

10、色、发色等颜色特征，脸的轮廓等轮廓特征，用到的更多的是不能感觉，只能通过变换等处理之后才表现出来的特征，如特征脸、小波特征等变换域特征，均值、方差等模板特征。人脸特征表述人脸特征表述基于基于PCA构建特征脸空间是对图像进行构建特征脸空间是对图像进行K-L变换，以去除样变换，以去除样本间的相关性，然后根据特征值的大小选择特征向量。本间的相关性，然后根据特征值的大小选择特征向量。这种方法首先将人脸图像映射为高维空间的向量，然后应这种方法首先将人脸图像映射为高维空间的向量，然后应用基于统计的离散用基于统计的离散K-L变换方法，构造一个各分量互不相关变换方法，构造一个各分量互不相关的特征空间，即特征脸

11、空间，再将人脸图像在高维空间中的特征空间，即特征脸空间，再将人脸图像在高维空间中的向量映射到特征脸空间，得到特征系数。的向量映射到特征脸空间，得到特征系数。PCA构建特征脸空间构建特征脸空间ORL标准人脸库由40人，每人10幅11292图像组成。这些图像是拍摄于不同时期的；人的脸部表情和脸部细节有着不同程度的变化，比如，笑或不笑，眼睛或睁或闭，戴或不戴眼镜；人脸姿态也有相当程度的变化，深度旋转和平面旋转可达20度；人脸的尺度也有多达10的变化。ORL人脸库人脸库(英国剑桥大学英国剑桥大学)M幅人脸图像样本，其图像矩阵，将它们转化为向量形式，得到M个维向量均值差值图像集的协方差矩阵特征值特征向量

12、可以从以上求得的M个特征向量中取出对构造图像影响最大的m个，这样就可以构造了一个原始图像空间的m维子空间，这个m维子空间称为特征脸空间。,图像集的协方差矩阵特征值特征向量,特征值与特征图像特征值与特征图像特征值ORL20人10幅特征脸空间特征提取LDA线性判别分析：线性判别分析：LinearDiscriminantAnalysis(LDA)Fisher(1936)在线性判别函数一章，我们讲过在线性判别函数一章，我们讲过Fisher线性判线性判别函数。它的思想是，找一个方向作投影，使得别函数。它的思想是，找一个方向作投影，使得投影后的数据类间距尽可能大，类内距尽可能小。投影后的数据类间距尽可能大

13、，类内距尽可能小。这实际上是两类数据的特征提取，提取的特征数这实际上是两类数据的特征提取，提取的特征数是。这一思想可以推广到任意类数据，提取任是。这一思想可以推广到任意类数据，提取任意多个特征。意多个特征。LDA的思想的思想:寻找最能把两类样本分开的投影直线寻找最能把两类样本分开的投影直线.LDA的目标的目标:使投影后两类样本的均值之差与投影使投影后两类样本的均值之差与投影样本的总类散布的比值最大样本的总类散布的比值最大.LDA的求解的求解:经过推导把原问题转化为关于样本集经过推导把原问题转化为关于样本集总类内散布矩阵和总类间散布矩阵的广义特征值总类内散布矩阵和总类间散布矩阵的广义特征值问题问

14、题.Bestprojectiondirectionforclassification多重判别分析多重判别分析(MDA)MDA把把LDA推广到多类的情况推广到多类的情况.对于对于c-类问题类问题,MDA把样本投影到把样本投影到 c-1 维子空间维子空间.目标和解法与目标和解法与LDA相似相似,只是类内散布矩阵的定义只是类内散布矩阵的定义更为复杂更为复杂,求解的广义特征值问题也更为复杂求解的广义特征值问题也更为复杂.线性方法的缺点线性方法的缺点 线性方法对于很多数据不能进行有效的处理线性方法对于很多数据不能进行有效的处理.现实中数据的有用特性往往不是特征的现实中数据的有用特性往往不是特征的线性线性

15、组合组合.几种流形学习算法几种流形学习算法 局部线性嵌入局部线性嵌入(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.

16、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.13731396,2003.在这个例子里，用在这个例子里，用LLE LLE 进行降维成功的体现了数进行降维成功的体现了数据内在的局部分布结构，而用据内在的局部分布结构，而用PCA PCA 映射则会将高维空映射则会将高维空间里的

17、远点映射到低维空间后变成了近邻点。间里的远点映射到低维空间后变成了近邻点。u特征选择:=从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类。u从D个特征中选取d个,共CdD种组合。典型的组合优化问题u特征选择的方法大体可分两大类：Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。Wrapper方法：将特征选择和分类器结合在一起，即特征子集的好坏标准是由分类器决定的，在学习过程中表现优异的的特征子集会被选中。四、特征的选择一种Filter算法:FOCUS该算法致力于寻找一个能

18、够正确区分所有该算法致力于寻找一个能够正确区分所有类别的最小特征集合。类别的最小特征集合。例如，若区分每个人的特征有：姓名、例如，若区分每个人的特征有：姓名、性别、籍贯、工作单位、身份证号性别、籍贯、工作单位、身份证号则该算法会选择：身份证号则该算法会选择：身份证号 搜索时先看一个特征能否正确区分样本，搜索时先看一个特征能否正确区分样本，若不能，则考察两个特征若不能，则考察两个特征以此类推以此类推经典特征选择算法u许多特征选择算法力求解决搜索问题，经典算法有：分支定界法单独最优特征组合法顺序后退法顺序前进法模拟退火法Tabu搜索法遗传算法特征选择顺序前进法u自下而上搜索方法。u每次从未入选的特

19、征中选择一个特征，使得它与已入选的特征组合在一起时所得的J值为最大，直至特征数增加到d为止。u该方法考虑了所选特征与已入选特征之间的相关性。特征选择顺序后退法u该方法根据特征子集的分类表现来选择特征u搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率u依次迭代，直至识别率开始下降为止u用“leave-one-out”方法估计平均识别率：用N-1个样本判断余下一个的类别，N次取平均特征选择遗传算法u从生物进化论得到启迪。遗传，变异，自然选择。u基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1构成的串表示一种特征组合。

20、u群体：若干个个体的集合，即问题的一些解的集合。u交叉：由当前两个个体的链码交叉产生新一代的个体。u变异：由一个链码随机某基因使其翻转。特征选择遗传算法u适应度：每个个体xi的函数值fi，个体xi越好，fi越大。新一代群体对环境的平均适应度比父代高。u遗传算法的基本框架：uuStep1:Step1:令进化代数令进化代数t t=0=0。uuStep2:Step2:给出初始化群体给出初始化群体P(t)P(t)，令，令x xg g为任一个体。为任一个体。uuStep3:Step3:对对P(t)P(t)中每个个体估值，并将群体中最优解中每个个体估值，并将群体中最优解xx与与x xg g比较，如果比较，

21、如果xx的性能优于的性能优于x xg g，则，则x xg g=x=xuuStep4:Step4:如果终止条件满足，则算法结束，如果终止条件满足，则算法结束，x xg g为算法的为算法的结果。否则继续。结果。否则继续。uuStep5:Step5:从从P(t)P(t)中选择个体并进行交叉和变异操作，得中选择个体并进行交叉和变异操作，得到新一代群体到新一代群体P(t+1)P(t+1)。令。令t=t+1,t=t+1,转到转到Step3Step3。特征选择Initialsolutionsstart1100101010101110111000110110011100110001encodingchromo

22、some110010101010111011101100101110101110101000110110010011001001crossovermutation110010111010111010100011001001solutions candidatesdecodingfitness computationevaluationroulette wheelselectiontermination condition?YNbest solutionstop newpopulationoffspringoffspringt 0 P(t)CC(t)CM(t)P(t)+C(t)遗传算法的求解步骤

23、模拟退火法u模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在 每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。u用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到 解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终 止时的当前解即为所得近似最优解。特征选择u假设材料在状态i的能量为E(i)，那么材料在温度T时从状态i进入状态j遵循如下规律：如果E(j)E(i)，接受

24、该状态被转换。如果E(j)E(i)，则状态转换以如下概率被接受：模拟退火法(II)u在某一温度下，进行了充分转换后，材料达到热平衡，这时材料处于状态i的概率满足：u所有状态在高温下具有相同概率。特征选择S：状态空间集合模拟退火法(III)u当温度降至很低时，材料会以很大概率进入最小能量状态。u模拟退火优化法：f:xR+，其中xS，表示优化问题的一个可行解。N(x)S表示x的一个邻域集合。特征选择Smin=i：E（i）=E min模拟退火法(IV)u首先给定初始温度T0和初始解x(0)，以概率P生成下一个新解x：u对于温度Ti和该优化问题的解x(k)，可以生成新解x。u经过多次转换，降低温度得到

25、Ti+1Ti。在Ti+1下重复上述过程，最终的解是对该问题寻优的结果。特征选择模拟退火法(V)u经过有限次转换，在温度Ti下的平衡态xi的分布为：uu当温度T降为0时，xi的分布为：特征选择特征选择的模拟退火法uStep1:令i=0,k=0,给出初始温度T0和初始特征组合x(0)。uStep2:在x(k)的邻域N(x(k)中选择一个状态x，即新特征组合。计算其可分性判据J(x)，并按概率P接受x(k+1)=x。uStep3:如果在Ti下还未达到平衡，则转到Step2。uStep4:如果Ti已经足够低，则结束，当时的特征组合即为算法的结果。否则继续。uStep5:根据温度下降方法计算新的温度Ti+1。转到Step2。特征选择