特征选择和特征提取

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

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

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

4、ysis)方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。uK-L (Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法 特征值特征值100kkkNNANkNAIN对于一个的矩阵 ，有 个标量 ，满足称为矩阵的一组特征值。如果给定的矩阵是奇异的，那么 个特征值中至少有一个为 。矩阵的秩 定义为矩阵非零特征值的个数。矩阵的条件数 定义为最大特征值与最小特征值的比值的绝对值。病态矩阵 条件数很大。212122112140211 3A 例： 特征向量特征向量1,0kkkkkkNvAvvAvAV满足

5、下式的的向量则称为 的特征向量。求特征向量的方法是解线性方程组11122212212211 0 2212213 0 221Avvvv 例： 求其特征向量。K-L变换 离散K-L变换：对向量x用标准正交向量系uj进行线性变换，得到新的向量Y. 经过KL变换组合，输出Y的各分量之间将具有最小的相关性.1jjjyxuTjjy ux:Lxy特征提取离散K-L变换的均方误差u用有限项估计x ：1djjjyxu()()TExxxx211TTjjjjdjdEyEuxxuE ()Tijijrx xE Rx x11TTTjjjjjdjdEuxxuuR u特征提取因为uj是确定性向量，所以有求解最小均方误差正交基

6、u用Lagrange乘子法，可以求出满足正交条件下的取极值时的坐标系统：1if th en TjjjjjjdR uuuR u 取 得 极 值u结论：以相关矩阵R R的d个特征向量uj为基向量来展开x x时，其截断均方误差取得最小值为：1jjduK-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变换的变换的向量展开表示向量展开表示：Tjjy uxuK-L变换的变换的矩阵表示矩阵表示

7、：12,.,dxuuuyU yTyUx1djjjyxu特征提取K-L变换的性质uy的相关矩阵是对角矩阵：TTTTijijijTTijijjiijEy yEER ux xuux xuuuuuTTTTEEUUUUy yxxR特征提取K-L变换的性质1200duK-L坐标系把矩阵坐标系把矩阵R R对角化，即对角化，即通过通过K-L变变换消除原有向量换消除原有向量x的各分量间的相关性的各分量间的相关性，从而有可能去掉那些带有较少信息的分从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的量以达到降低特征维数的目的特征提取主成分分析主成分分析 ( PCA ) 主分量分析（主分量分析（Primar

8、y Component Analysis, PCA）就）就是基于是基于K-L变换的提取图像特征的一种最优正交线性变变换的提取图像特征的一种最优正交线性变换，可以有效去掉一个随机向量中各元素间的相关性。换，可以有效去掉一个随机向量中各元素间的相关性。PCA的目的：寻找能够表示采样数据的最好的投影子的目的：寻找能够表示采样数据的最好的投影子空间空间. PCA的求解：特征向量常被叫做的求解：特征向量常被叫做“主分量主分量”，每个样，每个样本被它在前几个主分量上的投影近似表示，本被它在前几个主分量上的投影近似表示，U张成的空张成的空间称为原空间的子空间，间称为原空间的子空间，PCA实际上就是在子空间上

9、的实际上就是在子空间上的投影投影. 从几何意义来看，变换后的主分量空间坐标系与变从几何意义来看，变换后的主分量空间坐标系与变换前的空间坐标系相比旋转了一个角度。而且新坐标系的换前的空间坐标系相比旋转了一个角度。而且新坐标系的坐标轴一定指向数据信息量较大的方向。以二维空间为例，坐标轴一定指向数据信息量较大的方向。以二维空间为例，假定某样本的分布呈椭圆状，那么经过旋转后，新坐标系假定某样本的分布呈椭圆状，那么经过旋转后，新坐标系的坐标轴一定分别指向椭圆的长半轴和短半轴方向的坐标轴一定分别指向椭圆的长半轴和短半轴方向主主分量方向，因为长半轴这一方向的信息量最大。分量方向，因为长半轴这一方向的信息量最

10、大。x1x2u2u1主成分是这个椭圆的长轴方向。短轴的方向和长轴垂直，是第二个主成分的方向。变换后的各分量，它们所包括的信息量不同，呈逐渐减少趋势。事实上，第一主分量集中了最大的信息量，常常占80以上。第二、三主分量的信息量依次很快递减，到了第n分量，信息几乎为零。Principalcomponent PCA对于椭球状分布的样本集有很好的效果对于椭球状分布的样本集有很好的效果, 学习所学习所得的主方向就是椭球的主轴方向得的主方向就是椭球的主轴方向. PCA 是一种非监督的算法是一种非监督的算法, 能找到很好地代表所有样能找到很好地代表所有样本的方向本的方向, 但这个方向对于分类未必是最有利的但

11、这个方向对于分类未必是最有利的 人脸识别就是将已检测到的待识别人脸与数据库中的已知人脸进行比较匹配，得出相关信息，来鉴别该人是谁。这一过程的核心是选择恰当的人脸表征方式与匹配策略，即选择合适的人脸模式的特征，根据所提取的特征进行匹配。 人脸图像所包含的模式特征十分丰富,它不仅包括一些能直观感觉到的特征，如肤色、发色等颜色特征，脸的轮廓等轮廓特征，用到的更多的是不能感觉，只能通过变换等处理之后才表现出来的特征，如特征脸、小波特征等变换域特征，均值、方差等模板特征。人脸特征表述人脸特征表述 基于基于PCA构建特征脸空间是对图像进行构建特征脸空间是对图像进行K-L变换，以去除样变换，以去除样本间的相

12、关性，然后根据特征值的大小选择特征向量。本间的相关性，然后根据特征值的大小选择特征向量。 这种方法首先将人脸图像映射为高维空间的向量，然后应这种方法首先将人脸图像映射为高维空间的向量，然后应用基于统计的离散用基于统计的离散K-L变换方法，构造一个各分量互不相变换方法，构造一个各分量互不相关的特征空间，即特征脸空间，再将人脸图像在高维空间关的特征空间，即特征脸空间，再将人脸图像在高维空间中的向量映射到特征脸空间，得到特征系数。中的向量映射到特征脸空间，得到特征系数。PCA构建特征脸空间构建特征脸空间 ORL标准人脸库由40人，每人10幅11292图像组成。这些图像是拍摄于不同时期的；人的脸部表情

13、和脸部细节有着不同程度的变化，比如，笑或不笑，眼睛或睁或闭，戴或不戴眼镜；人脸姿态也有相当程度的变化，深度旋转和平面旋转可达20度；人脸的尺度也有多达10的变化。ORL人脸库人脸库(英国剑桥大学英国剑桥大学) M幅人脸图像样本，其图像矩阵 ，将它们转化为向量 形式，得到M个维向量 MTTT,21M,21MnnM11 均值差值nnn图像集的协方差矩阵 TMnTnnAAMC11), 2 , 1(Mii), 2 , 1(Miui特征值特征向量 可以从以上求得的M个特征向量中取出对构造图像影响最大的m个，这样就可以构造了一个原始图像空间的m维子空间，这个m维子空间称为特征脸空间。 ,图像集的协方差矩阵

14、 TMnTnnAAMC11), 2 , 1(Mii特征值特征向量,特征值与特征图像特征值与特征图像 特征值ORL 20人 10幅 特征脸空间特征提取LDA 线性判别分析：线性判别分析：LinearDiscriminantAnalysis (LDA) Fisher(1936)在线性判别函数一章，我们讲过在线性判别函数一章，我们讲过Fisher线性判线性判别函数。它的思想是，找一个方向作投影，使得别函数。它的思想是，找一个方向作投影，使得投影后的数据类间距尽可能大，类内距尽可能小。投影后的数据类间距尽可能大，类内距尽可能小。这实际上是两类数据的特征提取，提取的特征数这实际上是两类数据的特征提取，提

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

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

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

18、eduction. 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 LLE 进行降维成功的体现了数进行降维成功的体现了数据内在的局部分布结构，

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

20、的特征子集会被选中。四、特征的选择dDC一种Filter算法: FOCUS 该算法致力于寻找一个能够正确区分所有该算法致力于寻找一个能够正确区分所有类别的最小特征集合。类别的最小特征集合。例如，区分每个人的特征有：姓名、例如，区分每个人的特征有：姓名、性别、籍贯、工作单位、身份证号性别、籍贯、工作单位、身份证号 则该算法会选择：身份证号则该算法会选择：身份证号搜索时先看一个特征能能正确区分样搜索时先看一个特征能能正确区分样本，不能，则考察两个特征本，不能，则考察两个特征以此类推以此类推经典特征选择算法u许多特征选择算法力求解决搜索问题，经典算法有：分支定界法单独最优特征组合法顺序后退法顺序前进

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

22、，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1构成的串表示一种特征组合。u群体：，干个个体的集合，即问题的一些解的集合。u交叉：由当前两个个体的链码交叉产生新一代的个体。u变异：由一个链码随机某基因使其翻转。特征选择遗传算法u适应度：每个个体xi的函数值fi，个体xi越好，fi越大。新一代群体对环境的平均适应度比父代高。u遗传算法的基本框架：特征选择Initialsolutionsstart1100101010101110111000110110011100110001encodingchromosome110010101010111011101100101110101110

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