《(49)--特征选择和特征提取.pdf》由会员分享，可在线阅读，更多相关《(49)--特征选择和特征提取.pdf（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基本概念基本概念类别可分离性判据类别可分离性判据特征选择的最优和次优算法特征选择的最优和次优算法特征提取之特征提取之PCAPCA算法算法特征提取之特征提取之K-LK-L变换变换基于基于PCAPCA变换的变换的irisiris数据分类数据分类基本概念基本概念【问题的提出】特征空间特征空间特征特征每一个特征对应特征空间的一个维度特征越多，特征空间的维度越高问题1：如果用颜色、尺寸与重量组成的特征空间来区分苹果与梨，这两类水果在特征空间中会如何分布？问题2：如果用这个特征空间来区分红苹果与樱桃，这两类水果在特征空间中又会如何分布？原则：在保证分类效果的前提下用尽量少的特征来完成分类原则：在保证分类效
2、果的前提下用尽量少的特征来完成分类【基本概念】【特征选择】一是对一是对特征的评价特征的评价，也就是怎样衡量一组特征对分类的有效性，也就是怎样衡量一组特征对分类的有效性二是二是寻优的算法寻优的算法，就是怎样更快地找到性能最优或比较优的特征组合。，就是怎样更快地找到性能最优或比较优的特征组合。定义与错误率有一定关系但又便于计算的类别可分性准则Jij，用来衡量在一组特征下第i类和第j类之间的可分程度。对判据的要求：1）判据应该与错误率有单调关系，这样才能较好的反映 分类目标。2）当特征独立时，判据对特征应该具有可加性。3）判据应该具有以下度量特性：，当ij时，当i=j时4）理想的判据应该对特征具有单
3、调性，加入新的特征不 会使判据减小类别可分离性判据类别可分离性判据 计算各类特征向量之间的平均距离计算各类特征向量之间的平均距离，考虑最简单的两，考虑最简单的两类情况，可以用两类中任意两两样本间的平均来代表两个类情况，可以用两类中任意两两样本间的平均来代表两个类之间的距离。类之间的距离。-基本思想基本思想其中 Pi，Pj：先验概率：xk与xl之间的距离度量判据的表达式类间的平均距离为JD：)()(1111,121jliknlnkjijcjiciDxxnnPPJji)()(),(lkTlklkxxxxxx矩阵形式的类间距离的表达式JD：定义：类均值向量：总均值向量：类间离散度矩阵Sb的估计：Ti
4、iicibmmmmPS)(1类内离散度矩阵Sw的估计：TiikiiknkiiciwmxmxnPSi)()(111：类协方差阵ibDSJStrw得到：其它的基于类内类间距离的判据：判据的特点：判据的特点：1）基于类内类间距离的可分离性判据实际上是各类向量之间的平均距离。2)J（x）越大，可分离性越好。3）不能确切表明各类分布重叠情况，与错误率无直接联系。用两类分布密度函数间的距离（或重叠程度）来度量可分性，构造基于概率分布的可分性判据。重叠程度反应了概密函数间的相似程度。定义：两个密度函数之间的距离xxxdPPppgJp2121,),|(),|()(它必须满足三个条件：1.2.若 ，则 完全不重
5、叠3.若 ，则完全重叠0pJxxpxp,0)|()|(21maxJJpxxpxp),|()|(210pJ距离的多种具体形式：Bhattacharyya距离（巴氏距离）dxxpxpJB2121)|()|(ln两类完全重合时，两类完全不交叠时，Chernoff界（切诺夫界）dxxpxpJssc)|()|(ln211当 时BcJJ dxxpxpxpxpJxD)|()|(ln)|()|(2121散度表示了区分wi类和j 类的总的平均信息。特征选择和特征提取应使散度尽可能的大。借用熵的概念来描述各类的可分性。例子：设有c个类别，对于某个特征值x，若样本属于各类的后验概率相等，即 P（wi|x）=1/c则
6、从该特征无法判断样本属于哪一类，错误概率为（c-1）/c。若对另外一种情况，有 P（wi|x）=1，并且 则此时样本肯定属于wi类，错误概率为0.在特征的某个取值下：如果样本属于各类的后验概率越平均，则该特征越不利于分类；如果后验概率越集中于某一类，则特征越有利于分类。在信息论中，熵(Entropy)表示不确定性，熵越大不确定性越大。常用的熵度量常用的熵度量Shannon熵：)|(log)|(21xPxPHiici平方熵：)|(1221xPHici基于熵的可分性判据：基于熵的可分性判据：dxxpxHJe)()(说明：Je大，则重叠性大，可分性不好，Je小，则可分性好。特征选择的最优和次优算法特
7、征选择的最优和次优算法问题：问题：从D维特征中选取d维（dD），使分类性能最佳（J最大）。典型的搜索问题在D个特征中选择d个，共有 个组合数!)!(!ddDDCdD方法：方法：最基本的方法就是穷举法，就是穷举所有这些可能，从中选择 判据最优的组合另外一种取得最优解的方法是分枝定界法分枝定界法分枝定界法（branch and bound）这是一种自顶向下的方法，即从包含所有候选特征开始，逐步去掉不被选中的特征。这种方法具有回溯的过程，能够考虑到所有可能的组合。其基本思想是：按照一定的顺序将所有可能的组合排成一棵树，沿树进行搜索，避免一些不必要的计算，使找到最优解的机会最早。在d大约为D的一半时，
8、分枝定界法比穷举法节省的计算量最大。分枝定界法分枝定界法（branch and bound）根结点为全体特征（第根结点为全体特征（第0 0 级）级）每个结点上舍弃一个特征，各个叶结点代表选择的各种组合每个结点上舍弃一个特征，各个叶结点代表选择的各种组合避免在整个树中出现相同组合的树枝和叶结点避免在整个树中出现相同组合的树枝和叶结点记录当前搜索到的叶结点的最大准则函数值（界限记录当前搜索到的叶结点的最大准则函数值（界限B B），初值置），初值置0 0每级中将最不可能被舍弃（舍弃后每级中将最不可能被舍弃（舍弃后J J 值最小）的特征放在最左侧值最小）的特征放在最左侧从右侧开始搜索从右侧开始搜索分枝
9、定界法分枝定界法（branch and bound）算法要点：从左侧同级中将舍弃的特征不在本结点以下各级中舍弃从左侧同级中将舍弃的特征不在本结点以下各级中舍弃搜索到叶结点后，更新搜索到叶结点后，更新B B 值，然后回溯到上一分支处值，然后回溯到上一分支处如果结点上如果结点上J B J B，则不向下搜索，向上回溯，则不向下搜索，向上回溯每次回溯将已舍弃的特征放回（放回待舍弃之列）每次回溯将已舍弃的特征放回（放回待舍弃之列）如已回溯到顶（根）而不能再向下搜索，则如已回溯到顶（根）而不能再向下搜索，则J=B J=B 的叶结的叶结点即为解。点即为解。分枝定界法分枝定界法（branch and boun
10、d）算法要点：1、单独最优特征的组合 计算各特征单独使用时的判据值并加以排队，取前d 个作为选择结果。这一结果与所采用的特征选择的准则函数有关，只有当所采用的判据是每个特征上的判据之和或之积时，这种做法选择出的才是最优的特征。2、顺序前进法 最简单的“自下而上”的搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得判据J值为最大，直到特征数增加到d 为止.3.3.顺序后退法顺序后退法 是一种“自上而下”的方法。从全体特征开始每次剔除一个，所剔除的特征应使仍然保留的特征组的判据J值最大，直到特征数减少到d 为止。4、增l减r法（l-r法）在第k步可先用顺序前进法一个个
11、加入特征到 k+l 个，然后再用顺序后退法一个个剔去 r 个特征，我们把这样一种算法叫增 l 减 r 法（lr 法）特征提取之特征提取之PCAPCA算法算法是通过适当的变换把D个特征转换为d个新特征这里的特征提取专指从一组已有的特征通过一定的数学运算得到一组新特征，有时也把这种特征提取称为特征变换采用线性变换 如果xRD是D维原始特征，变换后的d维新特征yRd为 y=WTx 其中W是Dxd维矩阵，称为变换阵。经过主成分分析身长袖长长度指标胸围胖痩指标腰围反映特体的指标肩宽肩厚通过构造原特征的适当的线性组合,以产生一系列互不相关的新特征,从中选出少数几个新特征并使它们含有尽可能多的原特征带有的信
12、息,从而使得用这几个新特征代替原特征分析问题和解决问题成为可能。假设有p个原特征，分别为：新特征为：是这些原始特征的线性组合pxx,1pii,1,xTipjjijix 11iTi要求解的是最优的正交变换A，它使新特征i的方差达到极值。新特征组合写成矩阵的形式：xAT计算第一主成分计算第一主成分xTpjjjx1111第一个新特征1：11111121211)var(TTTTTxExExxEEE其方差为：用求拉格朗日函数的极值的方法来求解新特征的系数。构建拉格朗日函数构建拉格朗日函数11111)(TTf求拉格朗日函数的极值求拉格朗日函数的极值 最优解最优解a1a1满足：满足：1=v1代入方差的表达式
13、得：代入方差的表达式得：11111)var(TT最优的应该是的最大本征值对应的本征向量最优的应该是的最大本征值对应的本征向量1称作第一主成分，它在原始特征的所有线性组合里是方差最大的。计算第二主成分要求：方差最大，模为1，还必须与第一主成分不相关01212EEE012T将写成原特征a的表达，并代入上式，得：考虑到 1=v1、不相关的要求 和模为1的要求012Ta122T问题就变成了在 和 的约束条件下最大化2的方差。012Ta122Ta2是的第二大本征值对应的本征向量，2被称作第二主成分。若协方差矩阵共有p个特征值i，i=1，,p，把它们从大到小排序为12.。p。由对应这些本征值的本征向量构造
14、的p个主成分i，i=1，,p。全部主成分的方差之和为：它等于各个原始特征的方差之和。piipii11)var(计算主成分的贡献率（主成分数量的确定方法）：k个主成分所代表的数据在全部方差的比例是：piikii11可以事先确定希望新特征所能代表的数据总方差的比例，例如，80%或90%，根据上面的式子来试算出合适的k值。总结主成分分析的步骤 设x为类的样本集，x为n维向量1）用样本估算协方差矩阵或自相关矩阵T11()()NiNxx11NiNx2）求解其特征方程，对特征值从大到小进行排队，并选定前m个特征值，解特征方程|I-|=0，可以求出特征值3）计算前m个特征值所对应的特征向量，并归一化处理。将
15、归一化后的特征向量作为矩阵WT的行。muuu,214）利用WT对样本集x进行变换。*TxW x主成分的特点：1）主成分是原变量的线性组合；2）各个主成分之间互不相关；3）主成分按照方差从大到小依次排列，第一主成分对应最大的方差（特征值）；4）每个主成分的均值为0、其方差为协方差阵对应的特征值；5）不同的主成分轴（载荷轴）之间相互正交。特征提取之特征提取之K-LK-L变换变换K-L展开式模式识别中的一个样本可以看作是随机向量的一次实现。每一个x可以用确定的完备归一化正交向量系中的正交向量展开：1jjajuX其中 aj：线性组合系数jijiuujTi01只用有限项来逼近，即 （x为D维，dmax
16、max=h(j);class=j;end end2）计算各判别函数的数值，找出最大值所属的类别if class=1%画图 plot(x,y,+b);hold on else if class=2 plot(x,y,+r);hold on;else plot(x,y,+g);hold on end end3）将测试数据判别为数值最大的类别，并画图 if(i25&i50&class=3)fprintf(对于”判断第%d个数据属于第%d类”的分类是错误的!n,i,class)m=m+1;end endtitle(iris特征降维分类结果);4）设定错分条件，若某个测试数据被错分，则打印出错信息 display(错分样本数量：)m%错分样本的数量display(错误率：)w_r=m/75%错误率9.显示错分样本的数量，并计算错误率。模式识别中的特征选择和特征提取内容包括特征的评价准则、特征选择的最优算法和次优算法，特征提取的主成分分析方法和K-L变换方法。通过特征选择和特征提取都可以达到减少特征数量，降低特征空间的维度的目的，进而减少计算量，利于后续分类器的设计。特征选择是从众多特征中选择利于分类的特征；而特征提取是通过变换的手段，将原始特征进行线性变换得到新的特征，来达到降维的目的。本章结束本章结束