特征的选择与提取武汉大学,王文伟老师ppt课件

1、第六章 特征的选择与提取王文伟 Wang Wenwei, Dr.-Ing.: 687-78652: wwwangyahooWeb: /sites/ced/pr/电子信息学院第六章 特征的选择与提取2Table of Contents电子信息学院第六章 特征的选择与提取36.1 根本概念u特征的选择与提取是方式识别中重要而困难的一个环节：u分析各种特征的有效性并选出最有代表性的特征是方式识别的关键一步。u降低特征维数在很多情况下是有效设计分类器的重要课题。u三大类特征：物理、构造和数学特征u物理和构造特征：易于为人的直觉感知，但有时难于定量描画，因此不易用于机器判别。u数学

2、特征：易于用机器定量描画和判别，如基于统计的特征。引言第六章 特征的选择与提取4特征的构成u特征构成 (acquisition)：u信号获取或丈量原始丈量u原始特征u实例：u数字图象中的各像素灰度值u人体的各种生理目的u原始特征分析：u原始丈量不能反映对象本质u高维原始特征不利于分类器设计：计算量大，冗余，样本分布非常稀疏。引言第六章 特征的选择与提取5特征的选择与提取引言第六章 特征的选择与提取6特征的选择与提取举例u细胞自动识别：u原始丈量：正常与异常细胞的数字图像u原始特征特征的构成，找到一组代表细胞性质的特征：细胞面积，胞核面积，外形系数，光密度，核内纹理，核浆比u紧缩特征：原始特征的

3、维数仍很高，需紧缩以便于分类u特征选择：挑选最有分类信息的特征u特征提取：数学变换u傅立叶变换或小波变换u用PCA方法作特征紧缩引言第六章 特征的选择与提取76.2 类别可分别性判据u类别可分别性判据：衡量不同特征及其组合对分类能否有效的定量准那么u理想准那么：某组特征使分类器错误概率最小u实践的类别可分别性判据应满足的条件：u度量特性：u与错误率有单调关系u当特征独立时有可加性：u单调性：u常见类别可分别性判据：基于间隔、概率分布、熵函数0, if ;0, if ;ijijijjiJij Jij JJ121(,.,)()dijdijkkJx xxJx12121(,.,)(,.,)ijdijd

4、dJx xxJx xxx第六章 特征的选择与提取8基于间隔的可分性判据u类间可分性:=一切样本间的平均间隔：( )( )111111( )(,)2jinnccijdijklijklijJPPnn xxx(8-1)( )( )( )( )( )( )(,)() ()ijijTijklklklxxxxxxsquared Euclidian( )11iniikkinmx1ciiiPmm( )111( )(,)(,)incidikiiikiJPnxxmm m(8-5)类内平均间隔类间间隔1111(,)(,)2ccciiijijiijPPP m mm m(8-6)可分性判据第六章 特征的选择与提取9基于

5、间隔的可分性判据矩阵方式1()()cTbiiiiSPmm mm( )( )111()()inciiTwikikiikiSPnxmxm( )tr()dwbJSSx基于间隔的准那么概念直观，计算方便，但与错误率没有直接联络样本类间离散度矩阵样本类内离散度矩阵类间可分别性判据可分性判据第六章 特征的选择与提取10基于概率的可分性判据u基于概率的可分性判据：用概率密度函数间的间隔来度量1212( )( |), ( |),pJg ppP P dxxxx( |)( )( |)( |) ln( |)iDijjiijjpJIIppdpxxxxxxx( |)( )( |)iijjplpxxx( |)( )( )

6、( |)ln( |)iijijijpIE lpdpxxxxxxxif (,),(,),iiijjjijNN 1( )()()TDijijJxMahalanobis可分性判据第六章 特征的选择与提取11基于熵函数的可分性判据u熵函数：1(| ),., (| )ccHJPPxx121(| )log(| )cciiiJPP xx2212 1(| )cciiJPx1()(|),.,(|)ccJEJPPxx可分性判据第六章 特征的选择与提取12类别可分别性判据运用举例u图像分割：Otsu灰度图像阈值算法(Otsu thresholding)u图像有L阶灰度，ni是灰度为i的像素数，图像总像素数 N= n

7、1+n2+ + nLu灰度为i的像素概率：pi = ni/Nu类间方差：2221122()()()Bk1211112111,1kLLiiiiikiiikLiiiikipipippp可分性判据第六章 特征的选择与提取13Otsu thresholdingu灰度图像阈值:21argm ax()LBktk可分性判据第六章 特征的选择与提取146.3 特征提取与K-L变换u特征提取：用映射或变换的方法把原始特征提取：用映射或变换的方法把原始特征变换为较少的新特征特征变换为较少的新特征uPCA (Principle Component Analysis)PCA (Principle Component

8、Analysis)方法：方法：进展特征降维变换，不能完全地表示原有的进展特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。最为集中的的变换方法使损失最小。uK-L (Karhunen-Loeve)K-L (Karhunen-Loeve)变换：最优正交线性变换：最优正交线性变换，相应的特征提取方法被称为变换，相应的特征提取方法被称为PCAPCA方法方法(*)argm ax()JJxxx第六章 特征的选择与提取15K-L变换u离散K-L变换：对向量x用确定的完备正交归一向量系uj展开1jjjyxuTijij

9、uuTjjy uxxy特征提取第六章 特征的选择与提取16离散K-L变换的均方误差u用有限项估计x ：1djjjyxu()()TExxxx211TTjjjjdjdEyEuxxuE ()Tijijrx xE Rx x11TTTjjjjjdjdEux xuuR uTjjy ux特征提取第六章 特征的选择与提取17求解最小均方误差正交基u用Lagrange乘子法：1if then TjjjjjjdR uuuR u 取 得 极 值1jjd特征提取第六章 特征的选择与提取18K-L变换的表示uK-L变换的向量展开表示：Tjjy uxuK-L变换的矩阵表示：12,.,dxuuuyU yTyUx1djjjy

10、xu特征提取第六章 特征的选择与提取19K-L变换的性质uy的相关矩阵是对角矩阵：的相关矩阵是对角矩阵：TTTTijijijTTijijjiijEy yEER uxxuuxxuuuuuTTTTEEUUUUy yxxR特征提取第六章 特征的选择与提取20K-L变换的性质1200duK-L坐标系把矩阵R对角化，即经过K-L变换消除原有向量x的各分量间的相关性，从而有能够去掉那些带有较少信息的分量以到达降低特征维数的目的特征提取第六章 特征的选择与提取21K-L变换图解x1x2u2u112, 12221 12 2( , , , )( )nnij iji jUn nf x xxrxxyyyxyxRxy

11、 URUy y y二次曲线方程规范二次曲线方程特征提取第六章 特征的选择与提取22K-L变换的数据紧缩图解u取2x1变换矩阵U=u1，那么x的K-L变换y为： y = UTx = u1T x = y1u变换的能量损失为2222221215.9 %41特征提取第六章 特征的选择与提取23K-L变换的产生矩阵u数据集KN=xi的K-L变换的产生矩阵由数据的二阶统计量决议，即K-L坐标系的基向量为某种基于数据x的二阶统计量的产生矩阵的本征向量uK-L变换的产生矩阵可以有多种选择：ux的相关函数矩阵R=ExxTux的协方差矩阵C=E(x-) (x-)Tu样本总类内离散度矩阵：1,E()(),cTwii

12、iiiiiSPxxx特征提取第六章 特征的选择与提取24未知类别样本的K-L变换u用总体样本的协方差矩阵C=E(x-) (x-)T进展K-L变换，K-L坐标系U=u1,u2,.,ud按照C的本征值的下降次序选择u例：设一样本集的协方差矩阵是：求最优2x1特征提取器U解答：计算特征值及特征向量V, D=eig(C);特征值D=24.736, 2.263T,特征向量:由于12，故最优2x1特征提取器此时的K-L变换式为：7.5C0.8750.4820.4820.875V10.8750.482Uu120.8750.482TTxUxyxux特征提取第六章 特征的选择与提取25u特征

13、选择:=从原始特征中挑选出一些最有代表性、分类性能最好的特征进展分类。u从D个特征中选取d个,共CdD种组合。假设不限定特征选择个数，那么共2D种组合 典型的组合优化问题u特征选择的方法大体可分两大类：uFilter方法：根据独立于分类器的目的J来评价所选择的特征子集S，然后在一切能够的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不思索所运用的学习算法。uWrapper方法：将特征选择和分类器结合在一同，在学习过程中表现优良的的特征子集会被选中。6.4 特征的选择dDC第六章 特征的选择与提取26经典特征选择算法u许多特征选择算法力求处理搜索问题，经典算法有：u分支定界法: 最优搜索

14、，效率比盲目穷举法高。u单独最优特征组合法：次优搜索。u顺序后退法u顺序前进法u模拟退火法uTabu搜索法u遗传算法特征选择第六章 特征的选择与提取27单独最优特征组合u计算各特征单独运用时的可分性判据J并加以排队，取前d个作为选择结果u不一定是最优结果u当可分性判据对各特征具有(广义)可加性，该方法可以选出一组最优的特征来，例：u各类具有正态分布u各特征统计独立u可分性判据基于Mahalanobis间隔1( )()()TDijijJx121(,.,)()dijdijkkJx xxJx特征选择第六章 特征的选择与提取28顺序前进法u自下而上搜索方法。u每次从未入选的特征中选择一个特征，使得它与

15、已入选的特征组合在一同时所得的J值为最大，直至特征数添加到d为止。u该方法思索了所选特征与已入选特征之间的相关性。特征选择第六章 特征的选择与提取29顺序后退法u该方法根据特征子集的分类表现来选择特征u搜索特征子集：从全体特征开场，每次剔除一个特征，使得所保管的特征集合有最大的分类识别率u依次迭代，直至识别率开场下降为止u用“leave-one-out方法估计平均识别率：用N-1个样本判别余下一个的类别，N次取平均特征选择第六章 特征的选择与提取30模拟退火法u来源于统计力学。资料粒子从高温开场，非常缓慢地降温(退火)，粒子就可在每个温度下到达热平衡。u假设资料在形状i的能量为E(i)，那么资

16、料在温度T时从形状i进入形状j遵照如下规律：u假设E(j) E(i)，接受该形状被转换。u假设E(j)E(i)，那么形状转换以如下概率被接受：( )( )E iE jKTe特征选择第六章 特征的选择与提取31模拟退火法(II)u在某一温度下，进展了充分转换后，资料到达热平衡，这时资料处于形状i的概率满足：( )()()E iKTTEjKTj SePxieu一切形状在高温下具有一样概率。( )()1limE iKTEjTKTj SeSe特征选择第六章 特征的选择与提取32模拟退火法(III)u当温度降至很低时，资料会以很大约率进入最小能量形状。u模拟退火优化法：f: xR+，其中xS，表示优化问

17、题的一个可行解。N(x)S表示x的一个邻域集合。minmin( )minmin()01lim0E iEKTEjETKTj SiSeSeotherwise特征选择第六章 特征的选择与提取33模拟退火法(IV)u首先给定初始温度T0和初始解x(0)，以概率P生成下一个新解x：0()(0)1()( (0)( (0)fxfxTfxfxP xxeotherwise特征选择第六章 特征的选择与提取34模拟退火法(V)u经过有限次转换，在温度Ti下的平衡态xi的分布为：()()()ijfxTiifxTjSeP Te*minmin10iixSSPotherwise*min1iixSP特征选择第六章 特征的选择

18、与提取35特征选择的模拟退火法uStep1: 令i=0, k=0, 给出初始温度T0和初始特征组合x(0)。uStep2: 在x(k)的邻域N(x(k)中选择一个形状x，即新特征组合。计算其可分性判据J(x)，并按概率P接受x(k+1)=x。uStep3: 假设在Ti下还未到达平衡，那么转到Step2。uStep4: 假设Ti曾经足够低，那么终了，当时的特征组合即为算法的结果。否那么继续。uStep5: 根据温度下降方法计算新的温度Ti+1。转到Step2。特征选择第六章 特征的选择与提取36遗传算法u从生物进化论得到启迪。遗传，变异，自然选择。u基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1构成的串表示一种特征组合。u群体：假设干个个体的集合，即问题的一些解的集合。u交叉：由当前两个个体的链码交叉产生新一代的个体。u变异：由一个链码随机某基因使其翻转。特征选择第六章 特征的选择与提取37遗传算法u顺应度：每个个体xi的函数值fi，个体xi越好，fi越大。新一代群体对环境的平均顺应度比父代高。u遗传算法的根本框架：特征选择第六章 特征的选择与提取386