《计算机模式识别之特征提取.pdf》由会员分享，可在线阅读，更多相关《计算机模式识别之特征提取.pdf（36页珍藏版）》请在三一文库上搜索。
1、基本概念 ?特征的选择与提取是模式识别中重要而困难 的一个环节： ?分析各种特征的有效性并选出最有代表性的特 征是模式识别的关键一步。 ?降低特征维数在很多情况下是有效设计分类器 的重要课题。 ?三大类特征：物理、结构和数学特征 ?物理和结构特征：易于为人的直觉感知，但有 时难于定量描述，因而不易用于机器判别。 ?数学特征：易于用机器定量描述和判别，如基 于统计的特征。 引言 特征的形成 ?特征形成 (acquisition)： ?信号获取或测量原始测量 ?原始特征 ?实例： ?数字图象中的各像素灰度值 ?人体的各种生理指标 ?原始特征分析： ?原始测量不能反映对象本质 ?高维原始特征不利于分
2、类器设计：计算量大， 冗余，样本分布十分稀疏。 引言 特征的选择与提取 ?两类提取有效信息、压缩特征空间的方法： 特征提取和特征选择 ?特征提取 (extraction)：用映射（或变换）的 方法把原始特征变换为较少的新特征。 ?特征选择(selection) ：从原始特征中挑选出 一些最有代表性，分类性能最好的特征。 ?特征的选择与提取与具体问题有很大关系， 目前没有理论能给出对任何问题都有效的特 征选择与提取方法。 引言 特征的选择与提取举例 ?细胞自动识别： ?原始测量：（正常与异常）细胞的数字图像 ?原始特征（特征的形成，找到一组代表细胞性质 的特征）：细胞面积，胞核面积，形状系数，光
3、 密度，核内纹理，核浆比 ?压缩特征：原始特征的维数仍很高，需压缩以便 于分类 特征选择：挑选最有分类信息的特征 特征提取：数学变换 傅立叶变换或小波变换 用PCA方法作特征压缩 引言 类别可分离性判据 ?类别可分离性判据：衡量不同特征及其组合对分类 是否有效的定量准则 ?理想准则：某组特征使分类器错误概率最小 ?实际的类别可分离性判据应满足的条件： ?度量特性： ?与错误率有单调关系 ?当特征独立时有可加性： ?单调性： ?常见类别可分离性判据：基于距离、概率分布、熵 函数 0, if ;0, if ; ijijijji Jij Jij JJ= 12 1 (,.,)() d ijdijk k
4、 Jx xxJx = = 12121 (,.,)(,.,) ijdijdd Jx xxJx xxx + 基于距离的可分性判据 ?类间可分性:=所有样本间的平均距离： ( )( ) 1111 11 ( )(,) 2 j i n n cc ij dijkl ijkl ij JPP nn = = xxx (8-1) ( )( )( )( )( )( ) (,)() () ijijTij klklkl xxx=xxx squared Euclidian ( ) 1 1 i n i ik k i n = = mx 1 c ii i P = = mm ( ) 11 1 ( )(,)(,) i n c i
5、dikii ik i JP n = =+ xxmm m(8-5) 类内平 均距离 类间 距离 111 1 (,)(,) 2 ccc iiijij iij PPP = = m mm m (8-6) 可分性 判据 基于距离的可分性判据矩阵形式 1 ()() c T biii i SP = = mm mm ? ( )( ) 11 1 ()() i n c iiT wikiki ik i SP n = = xmxm ? ( )tr() dwb JSS=+x ? 基于距离的准则概念直观，计算 方便，但与错误率没有直接联系 样本类间 离散度矩阵 样本类内 离散度矩阵 类间可分离 性判据 可分性 判据 基于
6、概率的可分性判据 ?基于概率的可分性判据：用概率密度函数间 的距离来度量 1212 ( )( |), ( |), p Jg ppP P d= xxxx ?散度： ( |) ( )( |)( |) ln ( |) i Dijjiij j p JIIppd p =+= x x xxxx x ( |) ( ) ( |) i ij j p l p = x x x ( |) ( )( )( |)ln ( |) i ijiji j p IE lpd p = x x xxxx x ?正态分布：if (,),(,), iiijjjij NN = = 1 ( )()() T Dijij J =xMahalano
7、bis 可分性 判据 基于熵函数的可分性判据 ?熵函数： 1 (| ),., (| ) cc HJPP=xx ?Shannon熵： 1 2 1 (| )log(| ) c cii i JPP = = xx ?平方熵： 22 1 2 1(| ) c ci i JP = = x ?熵函数期望表征类别的分离程度： 1 ( )(|),.,(|) cc JEJPP=xx 可分性 判据 类别可分离性判据应用举例 ?图像分割：Otsu灰度图像阈值算法 (Otsu thresholding) ?图像有L阶灰度，ni是灰度为i的像素数，图 像总像素数 N= n1+n2+ + nL ?灰度为i的像素概率：pi =
8、 ni/N ?类间方差： 222 1122 ()()() B k=+ 12 111 121 11 , ,1 kLL iii iiki ii kL ii iik ipipip pp =+= =+ = = 可分性 判据 Otsu thresholding ?灰度图像阈值: 2 1 argm ax() L B k tk = = ?Otsu灰度图像二值化算法演示及程序分析: 可分性 判据 特征提取与K-L变换 ?特征提取：用映射（或变换）的方法把原始 特征变换为较少的新特征 ?PCA (Principle Component Analysis)方法： 进行特征降维变换，不能完全地表示原有的 对象，能量
9、总会有损失。希望找到一种能量 最为集中的的变换方法使损失最小。 ?K-L (Karhunen-Loeve)变换：最优正交线性 变换，相应的特征提取方法被称为PCA方法 (*)argm ax()JJ= x xx K-L变换 ?离散K-L变换：对向量x用确定的完备正交归一向量 系uj展开 1 jj j y = = xu T ijij =uu T jj y= ux xy 特征 提取 离散K-L变换的均方误差 ?用有限项估计x： 1 d jj j y = = xu ?该估计的均方误差： ()() T E= xxxx 2 11 TT jjj jdjd EyE =+=+ = uxxu E () T iji
10、j rx xE = Rxx 11 TTT jjjj jdjd E =+=+ = uxxuuR u T jj y= ux 特征 提取 求解最小均方误差正交基 ?用Lagrange乘子法： 1 if then T jjjjj jd =+ = R uuuR u 取 得 极 值 ?结论：以相关矩阵R R的d个本征向量为 基向量来展开x x时，其均方误差为： 1 j jd =+ = ?K-L变换：当取矩阵R R的d个最大本征值对应的本征 向量来展开x x时，其截断均方误差最小。这d个本 征向量组成的正交坐标系称作x x所在的D维空间的d 维K-L变换坐标系， x x在K-L坐标系上的展开系数向 量y y
11、称作x x的K-L变换 特征 提取 K-L变换的表示 ?K-L变换的向量展开表示： T jj y= ux ?K-L变换的矩阵表示： 12 ,., d =xuuuyU y T =yUx 1 d jj j y = = xu 特征 提取 K-L变换的性质 ?y的相关矩阵是对角矩阵： TTTT ijijij TT ijijjiij Ey yEE R = = uxxuuxxu uuuu TTT T EEUU UU = = y yxx R 特征 提取 K-L变换的性质 1 2 0 0 d = ? ?K-L坐标系把矩阵R R对角化，即通过K-L 变换消除原有向量x的各分量间的相关 性，从而有可能去掉那些带有
12、较少信息 的分量以达到降低特征维数的目的 特征 提取 K-L变换图解 x1 x2 u2 u1 12 , 1 222 1 12 2 ( , , , ) ( ) n n ij ij i j U n n f x xx rxx yyy = = = = =+ xy x Rxy URUy y y ? ? 二次 曲线方程 标准二次 曲线方程 特征 提取 K-L变换的数据压缩图解 ?取2x1变换矩阵U=u1，则x的K-L变换y为为： y = UTx = u1T x = y1 ?变换的能量损失为 2 2 2222 12 1 5.9 % 41 = + 特征 提取 K-L变换的产生矩阵 ?数据集KN=xi的K-L变
13、换的产生矩阵由数据 的二阶统计量决定，即K-L坐标系的基向量 为某种基于数据x的二阶统计量的产生矩阵 的本征向量 ?K-L变换的产生矩阵可以有多种选择： ?x的相关函数矩阵R=ExxT ?x的协方差矩阵C=E(x-) (x-)T ?样本总类内离散度矩阵： 1 ,E()(), c T wiiiiii i SP = = xxx 特征 提取 未知类别样本的K-L变换 ?用总体样本的协方差矩阵C=E(x-) (x-)T 进行K-L变换，K-L坐标系U=u1,u2,.,ud按照C 的本征值的下降次序选择 ?例：设一样本集的协方差矩阵是： 求最优2x1特征提取器U 解答：计算特征值及特征向量V, D=ei
14、g(C); 特征值D=24.736, 2.263T,特征向量: 由于12，故最优2x1特征提取器 此时的K-L变换式为： 19.59.5 9.57.5 C = 0.8750.482 0.4820.875 V = 1 0.875 0.482 U = u 1 2 0.8750.482 TT x U x = yxux 特征 提取 ?特征选择:=从原始特征中挑选出一些最有代表性、 分类性能最好的特征进行分类。 ?从D个特征中选取d个,共CdD种组合。若不限定特征 选择个数，则共2D种组合 典型的组合优化问题 ?特征选择的方法大体可分两大类： ?Filter方法：根据独立于分类器的指标J来评价所选择的
15、特征子集S，然后在所有可能的特征子集中搜索出使得J 最大的特征子集作为最优特征子集。不考虑所使用的学 习算法。 ?Wrapper方法：将特征选择和分类器结合在一起，在学 习过程中表现优异的的特征子集会被选中。 特征的选择 d D C 经典特征选择算法 ?许多特征选择算法力求解决搜索问题，经典 算法有：? ?分支定界法: 最优搜索，效率比盲目穷举法高。 ?单独最优特征组合法：次优搜索。 ?顺序后退法 ?顺序前进法 ?模拟退火法 ?Tabu搜索法 ?遗传算法 特征 选择 单独最优特征组合 ?计算各特征单独使用时的可分性判据J并加 以排队，取前d个作为选择结果 ?不一定是最优结果 ?当可分性判据对各
16、特征具有(广义)可加性， 该方法可以选出一组最优的特征来，例： ?各类具有正态分布 ?各特征统计独立 ?可分性判据基于Mahalanobis距离 1 ( )()() T Dijij J =x 12 1 (,.,)() d ijdijk k Jx xxJx = = 特征 选择 顺序前进法 ?自下而上搜索方法。 ?每次从未入选的特征中选择一个特征，使得 它与已入选的特征组合在一起时所得的J值 为最大，直至特征数增加到d为止。 ?该方法考虑了所选特征与已入选特征之间的 相关性。 特征 选择 顺序后退法 ?该方法根据特征子集的分类表现来选择特征 ?搜索特征子集：从全体特征开始，每次剔除 一个特征，使得
17、所保留的特征集合有最大的 分类识别率 ?依次迭代，直至识别率开始下降为止 ?用“leave-one-out”方法估计平均识别率：用N- 1个样本判断余下一个的类别，N次取平均 特征 选择 模拟退火法 ?来源于统计力学。材料粒子从高温开始，非 常缓慢地降温(退火)，粒子就可在每个温度 下达到热平衡。 ?假设材料在状态i的能量为E(i)，那么材料在 温度T时从状态i进入状态j遵循如下规律： ?如果E(j) E(i)，接受该状态被转换。 ?如果E(j)E(i)，则状态转换以如下概率被接受： ( )( )E iE j KT e 特征 选择 模拟退火法(II) ?在某一温度下，进行了充分转换后，材料达
18、到热平衡，这时材料处于状态i的概率满足 ： ( ) () () E i KT TEj KT j S e Pxi e = ?所有状态在高温下具有相同概率。 ( ) () 1 lim E i KT Ej T KT j S e S e = 特征 选择 模拟退火法(III) ?当温度降至很低时，材料会以很大概率进入 最小能量状态。 ?模拟退火优化法：f: xR+，其中xS，表 示优化问题的一个可行解。N(x)S表示x的 一个邻域集合。 min min ( ) min min () 0 1 lim 0 E iE KT EjE T KT j S iS e S e otherwise = 特征 选择 模拟退
19、火法(IV) ?首先给定初始温度T0和初始解x(0)，以概率P 生成下一个新解x： ?对于温度Ti和该优化问题的解x(k)，可以生 成新解x。 ?经过多次转换，降低温度得到Ti+1Ti。在 Ti+1下重复上述过程，最终的解是对该问题 寻优的结果。 0 ()(0) 1()( (0) ( (0)fxfx T fxfx P xx eotherwise = 特征 选择 模拟退火法(V) ?经过有限次转换，在温度Ti下的平衡态xi的 分布为： ?当温度T降为0时，xi的分布为： () () () i j fx T iifx T jS e P T e = * min min 1 0 i i xS SP o
20、therwise = * min 1 i i xS P = 特征 选择 特征选择的模拟退火法 ?Step1: 令i=0, k=0, 给出初始温度T0和初始特征组合 x(0)。 ?Step2: 在x(k)的邻域N(x(k)中选择一个状态x，即 新特征组合。计算其可分性判据J(x)，并按概率P 接受x(k+1)=x。 ?Step3: 如果在Ti下还未达到平衡，则转到Step2。 ?Step4: 如果Ti已经足够低，则结束，当时的特征组 合即为算法的结果。否则继续。 ?Step5: 根据温度下降方法计算新的温度Ti+1。转到 Step2。 特征 选择 遗传算法 ?从生物进化论得到启迪。遗传，变异，自
21、然 选择。 ?基因链码：待解问题的解的编码，每个基因 链码也称为一个个体。对于特征选择，可用 一个D位的0/1构成的串表示一种特征组合。 ?群体：若干个个体的集合，即问题的一些解 的集合。 ?交叉：由当前两个个体的链码交叉产生新一 代的个体。 ?变异：由一个链码随机某基因使其翻转。 特征 选择 遗传算法 ?适应度：每个个体xi的函数值fi，个体xi越好，fi越 大。新一代群体对环境的平均适应度比父代高。 ?遗传算法的基本框架： ?Step1: 令进化代数t=0。 ?Step2: 给出初始化群体P(t)，令xg为任一个体。 ?Step3: 对P(t)中每个个体估值，并将群体中最优解x与 xg比较，如果x的性能优于xg，则xg=x ?Step4: 如果终止条件满足，则算法结束，xg为算法的 结果。否则继续。 ?Step5: 从P(t)中选择个体并进行交叉和变异操作，得 到新一代群体P(t+1)。令t=t+1,转到Step3。 特征 选择 讨论 ?特征的选择与提取是模式识别中重要而困 难的一步 ? 模式识别的第一步：分析各种特征的有效性并 选出最有代表性的特征 ? 降低特征维数在很多情况下是有效设计分类器 的重要课题 ?三大类特征：物理、结构和数学特征 ? 物理和结构特征：易于为人的直觉感知，但难 于定量描述，因而不易用机器判别 ? 数学特征：易于用机器定量描述和判别