《09-特征空间》由会员分享，可在线阅读，更多相关《09-特征空间（48页珍藏版）》请在金锄头文库上搜索。
1、第九章 特征空间?9.0 引言?9.1 特征提取?9.2 特征选择9.0 引言?模式识别中把每个对象都量化为一组特 征来描述，构建特征空间是所有模式识 别问题的第一步?通过直接测量得到的特征称为原始特征原始特征。?比如人体的各种生理指标（描述其健康状况）?数字图象中的每点灰度值（以描述图像内容）9.0 引言?原始特征数量可能很大，不利于学习。 比如 1024*768的灰度图像，256灰度级。?直接表示，每幅需要786,432 bytes。进行训 练识别所需空间、时间、计算量都无法承受！?很少的样本分布会在如此高维的特征空间中 显得十分稀疏，因而产生过学习的现象。?特征空间有很大的冗余。完全可以
2、用很小的 空间相当好地近似表示图像，这一点与压缩 的思想类似。9.0 引言?特征的提取与具体问题有很大关系，目前没有 理论能给出对任何问题都有效的特征提取方法。?例：?用傅立叶变换或小波变换的系数作为图象的特征?指纹的特征?用PCA方法作特征压缩?用LDA方法作特征压缩9.0 引言模式识别中压缩特征空间的方法可分为两类：?特征提取特征提取：用映射（或变换）的方法把原始特 征变换变换为较少的新特征，称为特征提取?特征选择特征选择：从原始特征中挑选挑选出一些最有代表 性，分类性能最好的特征来，称为特征选择9.1 特征提取9.1 特征提取PCA?一般来说，进行特征提取后，不能完全地表示 原有的对象，
3、总会有一点损失。在给定容许的 损失后（比如1%的能量），我们总希望用最少 的比特达到这一要求，也就是找一种是能量最 为集中的的变换方法。?在所有正交线性变换中，这种最优的变换是 Karhunen-Loeve (KL)变换，相应的特征提取方 法被称为Principle Component Analysis (PCA)。9.1 特征提取PCA?正交变换?正交变换就是向量在一组正交基上的投影；?给定n维空间中的一组标准正交基 它诱导了一个线性变换：n,21LyxL:),()(21nyyyyxLL=.iT ixy=., 2 , 1niL=.1iniiyx =正交展开9.1 特征提取PCA?反之，任何一
4、个正交变换也确定了一组正交 基。因此我们只需找一组最优的正交基。?我们希望通过变换，用较少的数 近似表示原来的较多的数， 而且误差尽量的小。myyy,21LT nxxxx),(21L=nm 9.1 特征提取PCA?误差?用m个分量表示带来的误差：?希望误差平方的期望最小：.)(11inmiiimiiyyxmx +=.)()(1222 +=nmiiyEmxEme对所有的 求期望。x9.1 特征提取PCA?求解最小均方误差正交基：?首先假定随机矢量为零均值（期望）的，否 则减掉均值即可。?找n个正交基，使得对任意一组 正交基，和所有的. 0=Exn,21L.)()()()(122122 +=+=n
5、miiTnmiiTxEmexEmen,21L, nm 9.1 特征提取PCA?直接求解有一定困难，先看m=n-1的情形， 也就是找：n.minmin) 1(min2 nT nnTT n nnnxxEne =. 1. .2=nts).(TxxE=协方差矩阵。9.1 特征提取PCA?用Lagrange 乘子法：.min2 nnT n n .nn=得到是的特征向量，是特征根。n.) 1(2=nT nne因此， 是的最小的特征根， 是相应的特征向量。n9.1 特征提取PCA?协方差矩阵是对称阵，所有特征根是实数， 特征向量也是实的，并且所有n个特征向量 构成一组标准正交基，记作，分 别对应特征根?如果
6、用贪心算法，看看会得到什么结果：n,21L .21nL,nn=,111iniin=可以写为这种形式因为与正交1nn9.1 特征提取PCA.1112 11=nniiinT n这时候.11=nn. 11122 1=niin因为贪心算法最后的到的一组标准正交基就是的 特征向量，对应着从大到小排序 的特征根。n,21L9.1 特征提取PCA?启示：特征向量构成的标准正交基是不是满 足最小均方误差？?结论：尽管贪心算法本身不能保证这一点， 但可以证明特征向量就是我们所要的。9.1 特征提取PCA?证明： 将要找的一组标准正交基用特征向量表示出来.nnnnnnnnnn+=+=+=LMLL221122221
7、21212121111nnij*)(=是正交矩阵。9.1 特征提取PCA对固定的m,2 , 12 2, 122 1 , 112 , 12 2, 122 1 , 1122 222 1112)(nmnmmnnnnnnnnnnnmiiT ime+=+=LMLL9.1 特征提取PCA把每一列加起来。由于是正交阵，nnij*)(= =niij 121., 2 , 1njL=.)(212 nmmme+Lnmm,21L+张成的线性子空间与nmm,21L+考虑到m的任意性，,ii=., 2 , 1niL=张成的线性子空间相同。证毕9.1 特征提取PCA?总结：?向量在协方差矩阵的特征向量上的展开称为 Karh
8、unen-Loeve(KL)展开，诱导的线性变换 叫做Karhunen-Loeve变换；?实际应用中，协方差矩阵是未知的，用样本 协方差矩阵代替；?特征向量常被叫做“主分量”，每个样本被它 在前几个主分量上的投影近似表示;.)(11imiiT imiixyx =9.1 特征提取PCA?用这种方法选出的d个主分量来展开原数据 时，和其他正交坐标系下的d个分量的展开 相比，均方误差最小，为?特征值标记着相应特征向量上的能量?PCA的问题：由于用样本协方差矩阵代替协 方差矩阵，主分量与训练数据有着很大关系， 用一批训练数据得到的主成分，可能不反映 其另外一批数据的特征。+=1djj9.1 特征提取P
9、CAPCA的例子：1x2x1y2y121b2b219.1 特征提取LDA?线性判别分析：Linear Discriminant Analysis (LDA) Fisher(1936), Rao(1965)?在线性判别函数一章，我们讲过Fisher线性 判别函数。它的思想是，找一个方向作投影， 使得投影后的数据类间距尽可能大，类内距 尽可能小。这实际上是两类数据的特征提取， 提取的特征数是。这一思想可以推广到任 意类数据，提取任意多个特征。9.1 特征提取LDA?准则：?用原来的特征表示的数据记作?提取的特征表示的数据记作 W是的矩阵。?沿用Fisher判别函数中的记号，假设共有 类：,nx,m
10、Wxy= nm=kjiT jijibmmmmkS,)(1).(121kwkS+=Lk类间散度矩阵类内总散度矩阵9.1 特征提取LDA?用提取的 个特征表示的数据的类内、类间散 度矩阵记作：?准则：求W，希望类内距小、类间距大。m.,T wwT bb WWSSWWSS=).()()()(11T bT wbw WWSWWStrSStrWJ=9.1 特征提取LDA?求 ：W. 0)(= WWJ令得到：).()(11 bwTT bwSSWWSS=小技巧：对角化).(1 bwSS存在矩阵 ，使得：)(mmA. 111=ASSAbw对角阵（见习题）9.1 特征提取LDA.)()(111 11=AWAWSS
11、AAWWSSTT bwTT bw于是：是()1 bwSS的 个特征向量！mAWT这说明特征向量的求解就用前面的对角化方法：.21211= nnnnbwnnbwnn BBSSBSSB9.1 特征提取LDA?m维空间中的任何非奇异变换矩阵A都不 改变J(W)的值，因此可以忽略A。(请自 己证明）?设矩阵的特征值为：?则选取前m个特征值对应的特征向量作为 W，则)(1 bwSSnL21 =miiWJ1)(9.1 特征提取LDA?关于LDA的几点说明：?对于k类问题，选出的特征个数最多只有k-1， 这是因为 的秩最多为k-1.因此，对应非 零特征根的特征向量最多有k-1个，那些零 特征根对应的特征向量
12、对判据的值没有任 何影响；?不同于PCA, LDA的特征不一定满足正交性；bSJ9.1 特征提取LDA?LDA可以从另一个角度很容易的推出：假设 每类数据服从不同均值，相同协方差均阵 的正态分布。从最小错误率准则出发就可以 得到相同的结果。wS回忆Bayes决策理论一章的习题，两类问题，正 态分布且相同协方差矩阵的假设下，决策面是 超平面：)(.211mmSwconstxwwT=特征：9.1 特征提取LDA)(211mmSww=就是矩阵 T wbwmmmmSSS)(212111=的特征向量。.)()()(211211 212111wmmSmmSmmmmSwSSwwT wbw= 因为9.1 特征
13、提取LDA?推广：?LDA可以从相同协防差矩阵的正态分布假设 和最小错误率准则推出，是Campbell在1984 年指出的。?可以做两方面的推广：?假设各类服从协方差矩阵不同的正态分布，称为 Heteroscedastic Discriminant Analysis (HDA).?假设各类服从协方差矩阵相同的Gauss混合分布。9.2 特征选择9.2 特征选择?特征选择是从原始特征中挑选挑选出一些最有代表 性，分类性能最好的特征来。?每个特征的状态是离散的 选与不选?从N个特征中选取k个,共种组合.若不限定 个数，则共2N种。NP 问题?这是一个典型的组合优化问题k NC9.2 特征选择?特征
14、选择的方法大体可分两大类：?Filter方法：并不考虑所使用的学习算法。通常给 出一个独立于分类器的指标来评价所选择的特 征子集S，然后在所有可能的特征子集中搜索出使 得最大的特征子集作为最优特征子集。?Wrapper方法：将特征选择和分类器结合在一起， 即特征子集的好坏标准是有分类器决定的，在学 习过程中表现优异的的特征子集会被选中。9.2 特征选择?一种一种Filter算法算法: FOCUS?该算法致力于寻找一个能够正确区分所 有类别的最小最小特征集合。?例如，若区分每个人的特征有：姓名、 性别、籍贯、工作单位、身份证号 则该算法会选择：身份证号?搜索时先看一个特征能否正确区分样本， 若不
15、能，则考察两个特征以此类推9.2 特征选择?一种一种Wrapper算法：算法：OBLIVION?该方法与最近邻法最近邻法结合，根据特征子集的分类 表现来选择特征?用顺序后退法顺序后退法搜索特征子集： 从全体特征开始，每次剔除一个特征，使得所 保留的特征集合有最大的分类识别率（基于最 近邻法).依次迭代，直至识别率开始下降为止?用leave-one-out 方法估计平均识别率： 用N-1个样本判断余下一个的类别，N次取平均9.2 特征选择?许多特征选择算法力求解决搜索问题， 经典算法有 ：?分支定界法?顺序后退法?顺序前进法?模拟退火法?Tabu 搜索法?遗传算法9.2 特征选择遗传算法?该算法受进化论启迪，根据“物竞天择， 适者生存”这一规则演变?几个术语：?基因链码：使用遗传算法时要把问题的每个 解编码成一个基因链码。比如要从D个特征 中挑选d个,就用一个D位的0或1组成的字符 串
