特征选择和特征提取.ppt

经典特征选择算法 许多特征选择算法力求解决搜索问题，经典算法有：?? 分支定界法 单独最优特征组合法 顺序后退法 顺序前进法 模拟退火法 Tabu搜索法 遗传算法 特征选择 模式识别原理与应用 专 业： 模式识别与智能系统 学生姓名： *** 任课教师： 余老师 一、基本概念 特征的选择与提取是模式识别中重要而困难的一个环节： 分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步。 降低特征维数在很多情况下是有效设计分类器的重要课题。 引言 特征的形成 特征形成 (acquisition)： 信号获取或测量→原始测量 原始特征 实例： 数字图象中的各像素灰度值 人体的各种生理指标 原始特征分析： 原始测量很大程度上不能反映对象本质 高维原始特征不利于分类器设计：计算量大，冗余，样本分布十分稀疏。 引言 二、特征的选择与提取 两类提取有效信息、压缩特征空间的方法：特征提取和特征选择 特征提取 (extraction)：用映射（或变换）的方法把原始特征变换为较少的新特征。 特征选择(selection) ：从原始特征中挑选出一些最有代表性，分类性能最好的特征。 特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特征选择与提取方法。 特征的选择与提取举例 细胞自动识别： 原始测量：（正常与异常）细胞的数字图像 原始特征（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比 压缩特征：原始特征的维数仍很高，需压缩以便于分类 特征选择：挑选最有分类信息的特征 特征提取：数学变换 傅立叶变换或小波变换 用PCA方法作特征压缩 三、特征提取与K-L变换 特征提取：用映射（或变换）的方法把原始特征变换为较少的新特征 PCA (Principle Component Analysis)方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。 K-L (Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法 特征值 特征向量 K-L变换 离散K-L变换：对向量x用标准正交向量系uj进行线性变换，得到新的向量Y. 经过K－L变换组合，输出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实际上就是在子空间上的投影. 从几何意义来看，变换后的主分量空间坐标系与变换前的空间坐标系相比旋转了一个角度。而且新坐标系的坐标轴一定指向数据信息量较大的方向。以二维空间为例，假定某样本的分布呈椭圆状，那么经过旋转后，新坐标系的坐标轴一定分别指向椭圆的长半轴和短半轴方向——主分量方向，因为长半轴这一方向的信息量最大。 x1 x2 u2 u1 主成分是这个椭圆的「长轴」方向。短轴的方向和长轴垂直，是「第二个」主成分的方向。变换后的各分量，它们所包括的信息量不同，呈逐渐减少趋势。事实上，第一主分量集中了最大的信息量，常常占80％以上。第二、三主分量的信息量依次很快递减，到了第n分量，信息几乎为零。 Principal comp