04线性判别函数.doc

第四章线性判别函数4.0引言4.1Fisher线性判别4.2最小平方误差准则4.3最小错分样本数准则4.4线性支撑向量机(SVM)64.0引言Bayes决策尽管是最优决策，但实现困难模式识别的任务是分类，可直接设计判别函数一即分类面最简单的判别函数是线性函数，相应的分类面是超平面4.0引言线性判别函数(两类)：0g(x)=wtxbi02g(x)0是分类面方程；w是分类面的法向量；b是分类面的偏移；设计线性分类器的关键是给出估计叱b的准则投影后是一维数据的分类问题4.0引言选择W就是找一个最佳投影方向只与方向有关，和大小无关！4.1Fisher线性判别Fisher判别的基本思想：希望投影后的一维数据满足：两类之间的距离尽可能远；每一类自身尽可能紧凑准则的描述：用投影后数据的统计性质一均值和离散度的函数作为判别优劣的标准8n124.1Fisher线性判别符号含义：mm2——两类（原始）数据的均值向量气,S2分别表示两类（原始）数据的离散度矩阵r2分别表示两类（投影后，一维）数据的均值r2分别表示两类（投影后，一维）数据的离散度4.1Fisher线性判别原始数据与做W方向投影后数据统计量之间的关系：wTm,iii1,2.2（WTX）2iiwt（xm）（xm）twiiwtSw.i4.IFisher线性判别•均值向量和离散度矩阵1m—xiNi1,2(xm)(xim)ti1,2i4.1Fisher线性判别Fisher准则函数：()2J(w)2^F21212类间距总类内离散度WoptargmaxJ(w).4.1Fisher线性判别4.1Fisher线性判别称阵。

SwSS12类内总离散度矩wtSwJ(w)b.FwtSww类间离散度矩阵)2J(w)=^__丄F2212(wTmwTm)212——wtSwwtSw12wt(mm)(mm)twwrT(SS)w12称S(mm)(mm)tb12121314-4.1 Fisher线性判别Fisher准则的合理性：JF(w)只与投影方向有关，与w大小无关一若w是一个最优解，加也是最优解,，是任何不为零的常数4.1 Fisher线性判别Fisher最佳投影方向的求解：要求：SSS正定w12否则，存在投影方向w，使得wTSw0所有数据被投影到一点w上！JF(w)没有极大值4.1Fisher线性判别求出最佳投影方向上任何一个w即可JF(w)有上界，最佳投影方向一定存在！…(S)J(w)-bmax.F(S)wminQh，(Sbh分别是矩阵S”，的最小、最大的特征根"'4.1Fisher线性判别一定存在一个最优的w，满足:wTSww1.因为Sw正定！wtSw无约束最优化：maxi.wtSww等价于带约束的最优化:maxwtSwbs.t.wtSw1.w4.1Fisher线性判别4.1Fisher线性判别24带等式约束的最优化，用Lagrange乘子法:L(w,)wtSw(wtSw1).bwd(w,)oSwSw.wbw最优解满足：SbwtSwz0-boptwopt19根据类间离散度定义:(mm)(mm”w1212(注意(化m2)Twt12optw=cS1(moptw1optSw.wopt是一个数，记作c,m).2204.1Fisher线性判别只关心投影的方向：wS1(mm)optw12(SS)1(mm).12124.1 Fisher线性判别分类阈值b的确定：两类均值的中点：b—4.2投影后数据的均值(n「n2是两类样本的个数)姒[nnbT_12―.nn12I4.2最小平方误差准则线性分类器的齐次表达式：原始表达式：g(.x)wtxbwixib.i1权、样本增广向量：a(b,w1,w1,,wd)t,z(1,x1,x1,,xd)t.4.2最小平方误差准则样本的增广矩阵:1X1Xd111X1Xd221XdXdnn判别函数的齐次表达式:g(x)zTa.|4.2最小平方误差准则*最小平方误差(MSE)方法的思想：对每个样本x，设定一个“理想”的判别函数输出值c,，以最小平方误差为准则求最优投影方向w(增广权向量°)。

令c(c,c,,c)T.12n平方误差：J(a)"(g(x)c)2=Zac||2.i126—#30|4.2最小平方误差准则增广权向量的求解：J(a)2Zt(Zac).sZTZaZtc.一般样本数大于维数,(ZTZ)可逆.a(ZtZ)iZtcZc.Z(ZtZ)1Zt是Z的最小二乘广义逆I4.2最小平方误差准则与Fisher线性判别的关系：两类样本数分别为N,N;NNN.1212令c(c,,c,c,,c)T.第一类第二类同类样本对应相同值，投影方向w与Fisher判别器所得结果相同bc)2i(wtxbc)2.ix.IIwt(mm)cc12类间距给定wtxbc)2ix.II(wt(xm))2i2x.IIw=wt(nn)w21122|4.2最小平方误差准则解释：这时，最小平方误差相当于给定类间距的条件下，使类内距最小Zac||2(wtxii(wtxbc)2ix.IwTmbc0,必1有：wTmbc0.2I4.2最小平方误差准则(wtxbc)2ix./(wt(xm))2i1x.Inwtwnwt112wtSw.w与Fisher准则等价！4.3最小错分样本数准则样本增广向量的规范化表示:样本增广向量规范化：zxzii1.iZXii2要找增广权向量尽可能满足:zTa0.i1,2,,n.iI4.3最小错分样本数准则*线性可分性的判断：线性可分一若存在增广权向量对规范化的样本满足：zTa0,i1,2,,n.i4.3最小错分样本数准则|4.3最小错分样本数准则Fisher判别与最小平方误差判别的准则函数考虑了所有的样本。

断zTa,ii12,n.是线性规划问题：松弛变量-ns.t.zTammiiii皿i10ii1,2,,n.算法：为避免得到a0的解，引入小量，判线性可分，当且仅当解为所有i°最小错分样本数准则只考虑被错分的样本J(a)=(Zac)-Zac|||2.c(,)t只有被错分的样本zTai有贡献364.3最小错分样本数准则iiiai10min"2s.t.zTai1,2,,n.求解算法：无约束最优化的各种算法，如共轭梯度法带约束的二次规划：41I4.4线性支撑向量机支撑向量机(SupportVectorMachine)CortesandVapnik,1995.适用于两类的分类问题最大边界距离分类器I4.4线性支撑向量机线性可分情形下的最大边界距离分类超平面(maximalmarginhyperplane):marginmargin|4.4线性支撑向量机4.4线性支撑向量机1.分类面与边界距离(margin)的数学表示:训练数据的集合：（x，y）,（x,y）,,（x,y）,1122nnXid,y{i1,1}.yi1表示xi,1yi1表示Xi2分类超平面用法向量W表示w方向的边界距离:(w)min(xTw)max(xTw),iiX1xi2最大边界距离分类超平面唯一。

见习题二)|4.4线性支撑向量机4.4线性支撑向量机maxw,bs.t.xTwixTwiMb/2y1i/2y1ib1.求解最大边界距离分类超平面：4.4线性支撑向量机Lagrange对偶：L(w,b,)1MI22L(w,b)~b43[y(xTwb)1].iiinyx.iiii14.4线性支撑向量机最终对偶形式:L()nyylj!iJ1(xTx).JiJs.t.0,i120.二次规划问题.等价形式（只考虑法向量w的方向）：mmw||2w,b2s.t.xTwbixTwbiyiyi1,约束简化为：y（xTwiii1,2,,n.I4.4线性支撑向量机*最大边界距离分类超平面满足：nwyx.iiii1nyiii10.法向量是样本的线性组合！I4.4线性支撑向量机Karush-Kuhn-Tucker(KKT)条件：(y(xTwb)1)0.i1,2,,n.iii只有y(xTwb)1ii对应的,不为0,这样的t称为支撑向量48|4.4线性支撑向量机几何意义：超平面法向量是支撑向量的线性组合支撑向量：y(xTwb0i非支撑向量?：(XTWb)ii|4.4线性支撑向量机决策函数：ng(x)=。