《十三、特征选择与变换》由会员分享，可在线阅读，更多相关《十三、特征选择与变换（80页珍藏版）》请在金锄头文库上搜索。
1、第十三章特征选择与变换13.1 引言13.2 特征选择(Feature Selection)13.3 特征变换(Feature Transformation)13.4 小结13.1 引言模式识别中常常把每个对象量化为一组 特征来描述，对特征进行处理是模式识 别问题的重要步骤通过直接测量得到的特征称为原始特征原始特征比如人体的各种生理指标（描述其健康状况）数字图象中的每点灰度值（以描述图像内容）13.1 引言原始特征数量可能很大，不利于学习。比如 1324*768的256级灰度图像：直接表示需要786,432 bytes。进行训练识别 所需空间、时间、计算量都非常大！特征有很大的冗余。用少量特征
2、就可以很好 地近似表示图像。这与压缩的思想类似。很少的样本分布在如此高维的空间中，显得 十分稀疏，容易产生过学习的现象。维数灾 难！13.1 引言如何提取特征与具体问题有很大关系， 特征是对象的表达对象的表达，根据知识来考虑。特征的稳定性特征的可分性好的特征胜过好的学习算法！指纹细节特征13.1 引言模式识别中处理特征的方法可分为两类：特征选择特征选择(Feature Selection)：从原始特征中 挑选挑选出一些最有代表性、可分性能最好的特 征来特征变换特征变换(Feature Transformation)：希望通 过变换变换消除原始特征之间的相关或减少冗余， 得到新的特征13.2 特
3、征选择13.2 特征选择特征选择从统计的观点来看是变量的选 择。特征选择不仅是为了降低特征空间的维 数。在很多应用中特征本身具有非常明 确的意义，比如基因选择。13.2 特征选择特征选择是从原始特征中挑选挑选出分类性能最好 的特征子集来每个特征的状态是离散的 选与不选从d个特征中选取r个,共有种组合。若不限 定个数，则共种。NP 问题这是一个典型的组合优化问题r dC d213.2 特征选择搜索策略分支定界法顺序前进法顺序前进法顺序后退法顺序后退法模拟退火法Tabu 搜索法遗传算法遗传算法13.2 特征选择顺序前进法不考虑特征相关性，由 少到多，不断增加特征顺序后退法不考虑特征相关性，由 多到
4、少，不断减少特征13.2 特征选择遗传算法该算法受进化论启迪，根 据“物竞天择，适者生存”这一规则演 变几个术语：基因链码：使用遗传算法时要把问题的每个 解编码成一个基因链码。比如要从d个特征 中挑选r个,就用一个d位的0或1组成的字符串 表示一种特征组合。1表示该特征被选中 每个基因链码代表一个解，称作一个“个 体”，其中的每一位看作一个“基因”13.2 特征选择群体：若干个体的集合，也就是一些解的集合交叉：选择群体中的两个个体，以这两个个体为双 亲作基因链码的交叉，从而产生两个新的个体，作 为后代。变异：对某个体，随机选取其中一位，将其翻转适应度：对每个解，以给定的优化准则来评价其性 能的
5、优劣，作为其适应度X11000 1100 X1 1000 1010X2 0100 1010 X2 0100 11001000010 100101013.2 特征选择遗传算法的基本框架：1.初始化进化世代数 t=02.给出初始化群体 P(t)，令Xg为任一个体3.对 P(t) 中每个个体估值，并将群体中最优解X与 Xg比较，若优于Xg，则令Xg= X4.如果终止条件满足，则算法结束，Xg为最终结果。 否则，转步骤55.从P(t)选择个体并进行交叉和变异操作，得到新一 代个体P(t+1)，令t=t+1，转步骤3。13.2 特征选择关于遗传算法的说明：由步骤3保证了最终解是所搜索过的最优解常用的终止
6、条件是群体的世代数超过一个给 定值，或连续数个世代都没有得到更优解群体的大小和演化代数是值得重视的参数。 在一定范围内，这两个参数大些能得到更好 的解对交叉的亲本选择可采用如下规则：个体的 性能越好，被选中的可能性也越大13.2 特征选择特征选择的方法大体可分两大类：Filter方法：不考虑所使用的分类算法。通常 给出一个独立于分类器的选择准则来评价所 选择的特征子集S，然后在所有可能的特征 子集中搜索出“最优”特征子集。Wrapper方法：将特征选择和分类器结合在 一起，即特征子集的好坏标准是由分类器决 定的，在学习过程中表现优异的的特征子集 会被选中。13.2 特征选择Filter方法的选
7、择准则Fisher判别准则互信息量准则13.2 特征选择Fisher判别准则可分性度量 () () ()wwbwbbSSSJStrStrJSStrJ w+=321 113.2 特征选择迭代计算tStSttSSttSS SttSS11111111111=+ = =TTTTsddddds13.2 特征选择根据每个特征在两类的距离和方差来评 价它的分类能力。准则函数为其中分别是特征 在训练样本 中第一类和第二类的均值和标准差。jjjj jF2121)( +=jjjj 2211,jx13.2 特征选择互信息量准则考虑变量和的互 信息量。jxy估计密度函数。对于连续情形，则需要对于离散情形，有的联合密度
8、函数。和是的密度函数，和是=jjxyjj jjjjjjxyjj jyYPxXPyYxXPyYxXPjIyxyxpyxypxpdyxdypxpyxpyxpjI)()(),(log),()(),()(),()()(),(log),()(13.2 特征选择Wrapper方法基于最近邻的特征选择基于SVM的特征选择基于Fisher判别的特征选择基于AdaBoost的特征选择13.2 特征选择基于最近邻的特征选择OBLIVION用顺序后退法顺序后退法搜索特征子集：从全体特征开 始，每次剔除一个特征，使得所保留的特征 集合有最大的分类识别率（基于最近邻法)。 依次迭代，直至识别率开始下降为止。用leave
9、-one-out 方法估计平均识别率：用n-1 个样本判断余下一个的类别，n次取平均。13.2 特征选择基于SVM的特征选择SVM-RFE （ Recursive Feature Elimination ) 根据训练得到的SVM线性分类器的系数来判断每个 特征的重要性和分类能力。假设由线性SVM得到的 分类器为。从全体特征开始， 每次剔除一个特征，使得所保留的特征集合有最大 的分类识别率。当较大时，第i个特征对分类器影响较大；当较小时，第i个特征对分类器影响较小；当为0时， 第i个特征对分类器几乎没有影响。 =+=+=dii iTbxwbxf1)(xwiwiwiw13.2 特征选择基于Fish
10、er判别的特征选择FOMFisher判别准则但是当特征数远远大于样本数时，上面的式 子有无穷多个解，我们通过正则化来求解wSwwSwwwTbT J=)(mwS=w22 1)(wmwSw+=wF13.2 特征选择我们的目的是进行特征选择，即希望得 到的最好是由少数非零元素组成。通 过引入，求解使得下式最小：w =dkwk 1021)(ww)()(22 12 2wwmwSw+=wF=+=diw wdiwiieFe122 121)1 ()()1 ()(22wmwSww来逼近，有无法直接求导，我们用13.2 特征选择迭代求解 ()211 21)(mmSwDISS=+T wi iwT w=22 22 1
11、)()()(i diiwwwieeeDTeifwiw i=otherwise 11, if 1)(jjjj jj jppxpxh13.3 特征变换13.3 特征变换特征变换从信号处理的观点来看，是在 变换域中进行处理并提取信号的性质， 通常具有明确的物理意义。傅立叶变换小波变换Gabor变换13.3 特征变换特征变换从统计的观点来看，就是减少 变量之间的相关性，用少数新的变量来 尽可能反映样本的信息。主成分分析PCA （ Principle Component Analysis ）因子分析FA（Factor Analysis）独立成分分析ICA （ Independent Component
12、Analysis ）13.3 特征变换特征变换从几何的观点来看，通过变换 到新的表达空间，使得数据可分性更好。线性判别分析LDA核方法13.3 特征变换主成分分析PCA是 d维随机向量，均值向量和协方差矩阵为Tdxxx),(21=x() =)(),cov(),cov(),cov()(),cov(),cov(),cov()()()()()(,)(),()(212212121121dddddT ddTdxVxxxxxxxVxxxxxxxVEEEVxExExEExxxxxx13.3 特征变换样本可以认为是由观测 到的d个变量来描述的。我们希望减少变 量之间的相关性，并用少数新的变量来 反映样本的信息
13、。Tdxxx),(21=x13.3 特征变换随机向量x的协方差矩阵的对角元素分 别表示x中各分量的方差，x的总 方差可以为。dxx,1 ( )tr13.3 特征变换我们现在要求线性函数使得新的变量 的方差尽可能的大，也就是：xaTaaaa aaaxa aaxaa aaaaTTTTTTVVJ= 0000max)(max)(max)(max()() ()() ()()axaaxxxxaaxaxxaxaxaxaxaxaxaxaxa)()()()()()()()()()(22VEEEEEEEEEEVEETTTTTTTTTTTTTT=13.3 特征变换等价于：1max)(max=aaaaa aaTTJ1
14、3.3 特征变换由Lagrange乘子法：=aaaaaaaaaaaaaaaaTTTTJLL)(022),() 1(),(13.3 特征变换假设协方差矩阵有r个非零的特征值()()ijjT iiidrrT iriiiT ddp= =+=对应的单位特征向量。是0, 0,111111( )rtr+=113.3 特征变换协方差矩阵的最大特征值所对应的单位 特征向量：1111 )(=aaJ13.3 特征变换进一步考虑01max)(max1=aaaaaaa aaTTTJ13.3 特征变换由Lagrange乘子法：=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaTTTTTTTTTTJLL)(02222022),() 1(),(11111111113.3 特征变换协方差矩阵的第二大特征值所对应的单 位特征向量：2222 )(=aaJ13.3 特征变换因此，我们令，则有riii, 2 , 1,= arT rrTriTTTTiTTTTTaaaaaaaaaaaaaaaaaaaaaa=1, 101222011111maxmaxmax113.3 特征变换我们把分别称为随机向量x的 第一主成分、第二主成分第 主成分。 它们是 个互不相关的随机变量。它们组 成新的
