模式识别课件05.pdf

《模式识别课件05.pdf》由会员分享，可在线阅读，更多相关《模式识别课件05.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 线性判别函数 Linear Discriminant Functions 4.1 引言 从基于概率密度（估计）的分类器设计 -model-based method 到基于样本的直接分类器设计 思路：首先选定判别函数类和一定的目标（准则），利用样本集确定出函数类中的某些未知参数，使所选的准则最好。形式化：判别函数类),(g，：未定参数 准则函数)(L 求*：)(min)(*LL=本章只考虑线性判别函数 0)(wxwxgT+=多类情况 0)(iTiiwxwxg+=，ci,1L=次优分类器（相对于贝叶斯分类器）当正态分布且各类协方差相同时为最优分类器。4.1.1 一些基本概念 4.1.2 广

2、义线性判别函数 Generalized Linear Discriminant 对非线性判别函数)(xg，通过适当的变换转化为线性判别函数)(yg。比如=21xxx，cBxAxxxgT+=)(二次判别函数。若定义Txxxxxxy21222121,=则总可以找到0,，使 )()(0 xgyygT+=广义线性判别函数 因任何非线性函数都可以通过级数展开转化为多项式函数（逼近），所以任何非线性判别函数都可以转化为广义线性判别函数。问题：1.实现这种转化的非线性变换可能非常复杂 2.变换空间的维数可能非常高。维数灾难 特例：线性判别函数的齐次简化 ywxwxgTT=+=0)(=xy1，=ww0 增广样

3、本向量 增广权向量 4.2 Fisher 线性判别 Fisher Discriminant Analysis(FDA)出发点：把所有样本都投影到一维，使在投影线上最易于分类。-寻找投影方向 样本集Nxx,1L=X X 1类11111,Nxx L=X X 2类22122,Nxx L=X X 投影 iTixwy=，Ni,1L=离散度矩阵(Scatter Matrix)：在X空间：类均值向量 jxiixNmij=X X1，2,1=i within-class scatter 类内离散度矩阵 TijijximxmxSij)(=X X，2,1=i 总类内离散度矩阵 21SSSw+=或 2211)()(S

4、PSPSw+=between-class scatter 类间离散度矩阵 TbmmmmS)(2121=或 TbmmmmPPS)()()(212121=在Y空间（一维投影）类均值 jxiiyNmij=Y Y1，2,1=i 类内离散度 2)(ijximySij=Y Y，2,1=i 总类内离散度 21SSSw+=类间离散度 2212)(mmSb=Fisher 准则函数(Fishers Criterion)：max 2221221)()(SSmmwJF+=即：使两类之间尽可能分开，各类内部尽可能聚集。代入xwyT=，可得 wSwwSwwJwTbTF=)(:*w)(maxwJFw 求解：令分母0=cwS

5、wwT，最大化分子。定义 Lagrange 函数 )(),(cwSwwSwwLwTbT=0/=wL，得 0*=wSwSwb 即 *wSwSwb=。*w为极值解。（当dN 时wS通常是非奇异的），两边左乘1wS，得 *1wwSSbw=即*w为bwSS1矩阵的本征向量。将bS代入，有 *21211*)(wmmmmSwTw=RmmSw)(211=（*21)(wmmRT=为标量）只考虑*w的方向，得 )(211*mmSww=选阈值0w：（1）d和N很大时，y近似正态分布，可在Y空间内用 Bayes 分类器。（2）经验，如：)(21210mmw+=mw0=)()(ln21)(212121210PPNNm

6、mw+=4.3 感知准则函数 Perceptron Criterion Function 考虑齐次线性判别函数yygT=)(，两类1、2 Nyyy,21L=Y Y。d维增广样本向量 决策规则)(yg 0，则21y类 线性可分性：存在一个权向量，使所有样本被正确分类。即：0 then ,if 0 then ,if ,21iTiiTiyyyy Ni,1L=若定义=,if,if ,21iiiiiyyyyy Ni,1L=则有 0iTy,Ni,1L=iy叫做规范化增广样本向量，仍记为iy 本节只考虑线性可分情况，例 解向量*：满足0iTy，Ni,1L=的权向量。解区：权值空间中所有解向量组成的区域。对每

7、个样本iy，0=iTy为权空间中的一个超平面iH 解区只可能在iH的正侧。所有样本对应的超平面iH的正侧的交集就是解区。余量：解区中所有权向量都是解，但越靠近解区中间的解向量，所得的分类面离各类样本越远（最近距离越远），对将来的样本错分的可能性越小。引入余量0b，要求解向量满足byiT，Ni.,1L=（若要求b最大则为“最优分类面”，见 ch13）目的：1.解更可靠，（推广性更强）2.防止算法收敛到解区边界 求解：如果样本ky被错分，则有0kTy，因此可定义如下的 感知准则函数(Perceptron Criterion Function)()(jTyPyJkj=Y Y 其中kY Y是被错分样本

8、的集合。当且仅当0)(min)(*=PPJJ时，无错分样本。-Rosenblatt 用梯度下降法求解：Jkkk=+)()1()(/)(jyPyJJkj=Y Y jykykkkj+=+Y Y)()1(收敛：对线性可分样本集，经过有限次修正后一定可以找到一个解*单样本修正：固定增量法：（1）初值)0(任意 （2）对样本jy，若0)(jTyk，则 jykk+=+)()1(（1=k）（3）对所有样本重复（2），直至0=PJ 显然，如果错分条件改为bykjT)(，则考虑了余量b 变增量，如绝对修正法：2)(jjTkyyk=关于收敛性：4.4 最小错分样本数准则 考虑线性不可分情况，希望*使错分样本数最少

9、 考查不等式组0iTy，Ni,1L=，其中不成立的不等式数目就是错分样本数。0Y，=TNTyyYM1 求*，使其中不成立的不等式最少 考虑余量b，则不等式组变为 0 bY 4.5 最小平方误差（MSE）准则函数 Minimum Squared-Error Criterion Function 把不等式0iTy变为0=iiTby，Ni,1L=于是不等式组变为方程组 bY=TNbbbb,21L=通常dN，方程个数多于未知数个数，为矛盾方程组，误差bYe=，可求最小二乘近似解。MSE 准则函数 ()212)(iiTNiSbybYJ=*：)(minSJ 4.5.1 MSE 准则函数的伪逆解 0)(2)

10、(令=bYYJTS 得 bYbYYYTT+=1*)(TTYYYY1)(+=：伪逆 （YYT是dd方阵，一般非奇异）1.若b取为 =2211 if ,/if ,/iiiyNNyNNb，则 MSE 解*等价于 Fisher 解，且其中*0wmwT=)(12211mNmNNm+=.相当于 Fisher 中my0=2.若b取为T 1,1,1 L，则当N时，MSE 解yygT=)(以最小均方误差 逼近 Bayes 判别函数 )|()|()(210 xPxPxg=即*使dxxpxgyeT)()(202=极小。4.5.2 MSE 准则函数的梯度下降算法 )(2)(bYYJTs=算法：（1）初值)0(任意 （

11、2）)()()1(bYYkkTk=+until)(SJ或+)()1(kk 可选 kk/0=，00 单样本修正：kkTkkyykbkk)()()1(+=+ky是使kkTbyk)(的样本 Widrow-Hoff 算法 4.5.3 随机 MSE 准则函数及其随机逼近算法 4.6 随机最小错误率线性判别准则函数 小结 线性判别函数0)(wxWxgT+=，决策面0)(=xg 规则)(xg210 x 准则函数)(J，=0wwT 求*利用各种最优化方法 4.7 多类问题 Multicategory Problems 4.7.1 基本考虑 思路一：转化为多个两类问题 A.c类转化为1c个两类问题。i与非i O

12、ne-vs-rest,one-vs-all B.每类转化为1c个两类问题，i与j，ij c类则)1(cc个两类问题，但其中半数相同，故 c类转化为2)1(cc个两类问题 pairwise 思路二：线性机器(Linear Machine)c个线性判别函数 0)(iTiiwxwxg+=，ci,1L=if)()(xgxgji，ij，则ix if)()(xgxgji=，ij，则拒绝 增广权向量=0iiiww，线性机器可表示为),(21cLL 4.7.2 逐步修正法求线性机器 Incremental Correction 回顾感知器准则的单样本修正法 kkky+=+1，0kTky 若对ikyY Y，但kTjkTiykyk)()(，ij 则 =+=+=+jilkkykkykkllkkjjkkii,)()1()()1()()1(若样本集线性可分，则可在有限步内收敛于解机器 4.7.3 决策树简介 将多类问题转化为两类问题的一种方法。把类别分级分组 在每个结点上只解决一个两类问题(二叉树)通常还考虑在每个结点上用不同的特征 用优化方法设计决策树 启发式方法(根据对问题的认识设计决策树)