模式识别原理4-NSV

第四章线性判别函数线性判别函数判别函数值的鉴别意义、权空间及解空间Fisher线性判别→LDA一次准则函数及梯度下降法二次准则函数及其解法线性规划方法/线性二分能力广义线性判别函数二次判别函数分段线性判别函数位势函数分类法L朋解决：不恢复条件概密，直接用样本集设计分类集。给定某判别函数类，用样本集确定出判别函数中未知参数。(有些基于概率分布设计的分布器，等价于线性分类函数， 以线性判别函数为例来说明如何用样本设计分类器。)一、线性判别函数决策超平面1、一般表达式：模式样本特征值的线性加权和 第四章线性判别函数 可写成g(x)=W¹x两类问题线性分类： 判别函数值的数学意 两类问题的线性判别函数为 的法矢量，从系数、权值到平面、向量→从代数到几何 判别域界面方程分类d(x)判别函数，判别域代数界面g(x)>0的区域R,中任一x在H的正侧 x,为x在超平面H上的投影向量O0方向上的单位向量O判别函数正比于到超平面的代数距离带正负号)H正侧,)H负侧,g0特殊判别函如有一些存到贮好的原型,不计算其分类,原计确最个未知各原型的距离,可把距离最作策书:(页)距离分判别函数分类余应一,每类样本点占据特征空间中不区域,每类集,分类准则:输入模式样本x与距离最近,则有x∈O与类别无关，与输入值有关，对各类都为一样值。线性函数最优分界面在每对原型的距离一半之处。 其它线性判别函数分类，例见余书P224-225与类别无关，与输入值有关，对各类都为一样值。线性函数最优分界面在每对原型的距离一半之处。 其它线性判别函数分类，例见余书P224-225线性判别函数-判别规则两类问题多类问题x,为x在超平面H上的投影向量OOOCC将属于o;类不属于o;类的模式划分开◆为了方便，可以建立c个判别函数为了方便，可以建立c个判别函数反之，不成立十十不确定区：两个或两个以上的判别式大车0的区域或所有判别式都小于0的区域。一类类个例1别区与其别区之只有一界面分开三O分界分类结x区∈₃例2:设有一个二维三类问题，判别函数已求得两法O对这c类判中别的函意将两属类于oo别类建的式个判数分开判c别的组数为c2所类有以设分o和o别函数d=i=-d则判x∈C判决判决例3.每个类别由2个以上的面围住，并与其它类别分开给出三条线方程，求得分界面，标出区，即可判断例4:设有一个二维三类问题，三个判别函数为o/O;,令=c;d=) 如果d,(x)>d,(x) 如果d,(x)>d,(x)任意j≠iT T 吕例6:一维样本空间吕显然不能用线性判别F来解决划分所以，线性判别F简单，但局限性大。选择映射x→y,使g(x)为y的线性F,*变换后样本向量仍然全部位于n维子空间，其划分与对原x空间*变换后样本向量仍然全部位于n维子空间，其划分与对原x空间其中其中3权量阈值w。,未知寻找最好的o,往往出现在准则函数极值点上))取据x志x数=x满₂,…,x2一J是本集的数*J值反映分类器性能,其值解对应于最好的决策。w,化术求出准别F③最优技则数极值解,得线。X₄类别未计算8然据决策规则判x所属类分类：针对不同实际情况，按不同设计要求来设计分类器.数学上表现为某个特定函数形式，称准则函数误率或风险最小，称最优分类器。 EQ\*jc3\*hps47\o\al(\s\up28(次),线)EQ\*jc3\*hps47\o\al(\s\up28(优),性)EQ\*jc3\*hps47\o\al(\s\up28(：),判)EQ\*jc3\*hps47\o\al(\s\up28(和风险次优，),计算存贮量小)EQ\*jc3\*hps47\o\al(\s\up28(对所得的准则),是PR基本方法) 称为维数灾难。∴需要压缩维数(降维),用统计方法 方向确定，分界(平面，线)确定→得各系数方向确定，分界(平面，线)确定→得各系数设n式维分训属模w式1和x.,x其中N2=Nw2各类模式分别记为)各类模式均值矢in维,类:均值向,①i=i各类样本在一维y空间投影②的i==W影后各类差样本能投,一维空分开,量密想法找使投影后则函数X据Fu=,W入,求极大W ∵①每类聚合程度(协方差)相等，各类大小相等 (算进行分类,需计x到各均的欧类,然后归于具即最小距离分类)(Z-均2,各协方,形超集中与该类中内。P-PZ-,m与界面正交,但0通常不在线上m与连。不方)为界面与m,m,连线的交点c2m连线的中₀不;点,但在偏o的均值一方。)各类方差不等二次曲面分界,面时,为超随着用准则及本求分界面例A方程分界面与投影方向直,可设其分界方程为:方向即分界面法方向垂直面W于分界.知道面法线向即知W方设此超平面单位法向量为nn₂……n过平面=(P₁)超上一方向数为o法线方程为:其出和P,即出分界面;分界面一求n定平定,可求得W,求得的未知参数重心m₁,m₈设分界线的法线为(n,n,),类别重心m₁,m₈(2)求重心投影点(3)求投影后的各类内偏差可见在第一类类内，各特征方差不同无需再计算第二类，已知不可用连线方向作方向，只能用Fisher准则求解(2)求重心投影点(3)求投影后的各类内偏差可见在第一类类内，各特征方差不同无需再计算第二类，已知不可用连线方向作方向，只能用Fisher准则求解(5)构造F准则函数得方程与N₁.N₂有关。2感知准则函数2感知准则函数50年代末第一次把神经网络研究从纯理论的探讨付诸 ∴称为感知准则函数(只解决线性问题) (1)基本概念 线性样本向量),分别来自0,o₂类。若存在一个权向量W(存在一个W7X定义的超平面),均有W⁷Y>0; 若样本集Y₂Ym线性可分,则必存在权向量,使满足上式的一切权向量W,均可将M个样本正确分类去掉标,;类样本,统一成一本经此变换求就是对所有Yi具0的两类点集写成总点全部样本写成统一解样本O₁O₁规十权空间W=0—线可分条件下满足W',…的权向。①每个y当时,确定个过权空原点的超平面H个,,法线为,若解向量存在,必在H正侧M个个把权②样本,Y,产生超平面,每均间一分二。Q₂为为(对规范化Y,Ym’y被时⁷,WT0一个准则:被权向量错分的样本错分集据上,W≤0→-WTy于正确分类:W在解区边界或解向量,J对0(·训练矢量都被正确分类)为∴:当YE为空集时,仅不存在错分样本,这时的W就是我找的解向量W·感当脑)模型感知器,一般感(3)感知器算法(Perceptron感知器(perceptron):具有单层计算单元的人工神经网。(3)感知器算法(Perceptron感知器训练算法就是由感知神经网络演变来的。 EQ\*jc3\*hps47\o\al(\s\up3(美),如)EQ\*jc3\*hps47\o\al(\s\up3(国),下)EQ\*jc3\*hps47\o\al(\s\up3(学),图) 感知器实质上是一种神经元模型，是一个多输入/单输出 的非线性器件。用一个数学表达式表示，就是： 法—W-梯度下降法、求感知准则函数求解称为)准若则对W度,得:JZ(-wy正确分类代求W公式迭际算法)求类面的方程)广向量(量但样本没经规化))-)每一轮以第类2,3,至第2类,2,4为序反复迭代,对每误差校正样本一本依法计算其Y轮每一∵样本无规范化代修正至某一类分类全部确)迭轮各所样本正为代所得w值入d),即得界面方程。感器的学机,结参数随学习算法更新,学的任基练数以一训据)已知训练样本(0,0)’属于w₁类，(1,1)’属于(-1,1)’属于w₃类，试求解向量w)求号水x₁=(0,0,1)’,x₂=(1,1,1)’,x₃=(-1,1,1)’(2)运用感知器训练算法。置迭代步数k=1,p=1,三个权矢量不再变化，这表明所有样本均已w₁=w₁(5),w₂*=w₂(5),同时可得三个判别函数w₂(5)=(2,0,-2)’oDerivethecompetitivelearningalgorithm分段线性,以简形二线性次基基于与类心于与界面的的判判函运用使用区域交和并模的式方产法生产分分线用局部的训练模式产生局部的判别函数；代表。).类代表类用类类心的“联合”来代表一分解为类的类实:子聚()设一个类由m个子类组成,则特征点到该类的距离定义为距子类类最小距按照最小距离原则聚类Ⅱ:分段线性距离判别.2)基于与界面距离的分段线性判别函数第三种情况：最大的点面距离每个子类的判别函数→按最大点面Aa分段线性分段线性的线性二次)基于距离的分线函数等概下最小距离x/₂fO均值作类别代表点,距离作别函数但错误率较大以,分布可不①k类,第0类,分l个子域,个代表点第i类判别函数类分规则:g).,得不好,会错分考虑整个本集类每类确定子对每个子类定义一个线性判别go/l=,k第i个线性Fg=mg)l=k类决策规则x;④分类线性决策面方程:第i类第类第相第j程决策面方=g”inputxxjX2x;Xdinputlayer;eachinputunitthenemitsitscorrespondingcomponthenetwork,zk=f(net),areusedasdiscrinetworktraining,theseoutputO.Duda,PeterE.Hart,andDavidG.Stork,PatternClassification.CbyJohnWiley&Sons,I3设计网络A.隐单元数上限(一个样本对应一个区域输入空间S,k个样本，设需n,3设计网络A.隐单元数上限(一个样本对应一个区域输入空间S,k个样本，设需n,个超平面划分为d个区从几何上看，是把n维空间用K—1个超平面不相交地(7为闭区域，其余为有21个开区域。)考虑每个样本落于1个独立区域中，每个样本输入时对应除隐单元输出不同，再经与或组合。(即n维空间中求n₁的分割，用隐单元数n₁,求其可划出的最多区域。)(对k个样本要有k个独立区域数)对n=2,n=3,最大独立区域数n₁—1确定结构后，可用训练方法得到输入至隐层的权值，输出与隐层间权值则可用与、或等方法得到。用上限实现的分类感知器网络(XOR)用上限实现的分类感知器网络(XOR)Backpropagationalgorithm:generalizeddeltarule EQ\*jc3\*hps55\o\al(\s\up51(B),d)EQ\*jc3\*hps55\o\al(\s\up48(a),e)EQ\*jc3\*hps49\o\al(\s\up2147483630(a),e)EQ\*jc3\*hps55\o\al(\s\up45(g),r:) EQ\*jc3\*hps48\o\al(\s\up28(s),r)EQ\*jc3\*hps48\o\al(\s\up28(er,G),tVec)EQ\*jc3\*hps48\o\al(\s\up28(uy),tor)EQ\*jc3\*hps48\o\al(\s\up28(n),M)EQ\*jc3\*hps48\o\al(\s\up28(,Vap),achin)EQ\*jc3\*hps48\o\al(\s\up28(n),e)在很大程度上解决了传统方法(如神经网络)中存在的问3)核函数解决非线性、回避具体变换的求解问题66(c)TrainingdataandabetterclassifEQ\*jc3\*hps34\o\al(\s\up1(F),a)2468最优分类平面二维数据最优分类线的基本要求；H设线性可分样本集(x₁,y),i=1,2…n,x∈Rd,y∈{+1,-1}类别标号，原理线性可分之日构造朗数:w=wZ其中>系求极小值就是对w和氏数极小值。求L约b件偏微分,,并其等可转n偶0为对对最在下式大:值:1最w若为优解,则*=x即最优分类面的权系数向量是训练样本向量的线性组若a;*为最优解，求解上述问题后得到的最优分类函数是：给定未知样本x,只需计sgn(w●x+b),即可判定x分类。对非支持向量a;都为0、对性分样本,希望分类点最入松弛0y-+,…)对给定常数C,求出取变约极小过条EQ\*jc3\*hps36\o\al(\s\up11(：),件)的同样换为格子表的对偶换与可分偶问类结也几全相同(aC=1,C反在性和可分本所占例之的折中。4、用内积K最特优类面中点积,相当于原特征空变换到一新征间,函:法的他条件不变→支持向机。值→解个二规划(约束→一个值.75whichpredictsthef(x)foramynewobjectx∈R"Incomputationalbiology,Mamyproblemscanbeconsideredasclassificationproblem.Forexample:Medicaldiagnosisxisasetoffeatures(age,sex,bloodtype,genome,…),yindicatestherisk.基于s个支持向量x₁,输入向量支持向量机示意图tionsa(rk),k=1.…,,associatedninputvariables,andasetoftrainoftheform(6):d2)Findb(detailscanbeOutputs:Asetoffuzzyrulesparame-containsthelocationparametersoftheIP-partmembershipfunctionsofthejthconstantofthejthfuzzyrule,andm+1givenpositive-definitereferencefunc-tionsaccordingto(13).example,[7]).j-1←j-j+1比比、分类法,对非线性的分类采用势函数分段法。法适用于线广义线用电场概念或质点引力概念类与样本为正电借:荷点质点)平力为力函数点到分界超平势能函数于引力平距1设引力方为势即分面势能最远处力衡的各组或电位的等位线分解面平成如为线,性则此法求任意形状的界面分如,曲面看段平2二即Y"YW=Y7eAdhboostAdhboost算法概述 组成一个强分类器H(x)=sign(Zα₁h,(x))分类：拟合训练数据，正确预测未知样本的类重采样技术→提高分类器的准确率A.Arcing(adaptivereweightingandcombining)自适应的权值重置和组合重新使用和选择数据，达到改善分类器性能目的。最简单arcing=bagging算法样本点(不放回),组成样本集D根据D₁3:构造第三个样本集D3:在D中剩余的样本中选取样本点，并且用C1和C2分类，如果C1和C2判决结果不同，样本加入D3]否则就忽略这个样本。用D3训练新分类器4:用这3个分类器对新样本x进行分类，如果C1和C2的判决结果相同，则表为一类