模式识别课件第四章线性判别函数

第四章线性判别函数Bayesian分类器设计方法，已知类条件概率密度p(x|ωi)参数表达式先验概率P(ωi)利用样本估计p(x|ωi)的未知参数用贝叶斯规则将其转换成后验概率P(ωi|x)，并根据后验概率的大小进行分类决策。解决实际问题方法在实际中存在问题样本特征空间的类条件概率密度形式常常很难确定利用Parzen窗等非参数方法恢复分布往往需要大量样本，而且随着特征空间维数的增加所需样本数急剧增加。因此，在解决实际问题时，往往是利用样本集直接设计分类器，而不恢复类条件概率密度。即采用判别函数，首先给定某个判别函数类，然后利用样本集确定出判别函数中的未知参数。线性判别函数线性判别函数法是一类较为简单的判别函数。是统计模式识别的基本方法之一。它首先假定判别函数g(x)是x的线性函数，即g(x)=wTx+w0，对于c类问题，可以定义c个判别函数，gi(x)=wiTx+wi0，i=1,2，…，c。用样本去估计各wi和wi0，并把未知样本x归到具有最大判别函数值的类别中去。关键是如何利用样本集求得wi和wi0。训练和学习“训练”和“学习”在待识别的模式中，挑选一批有代表性的样本，经过人工判读，成为已知分类的样本，把这批样本逐个输入到计算机中的“训练”程序或算法中，通过一次次的迭代，最后得到正确的线性判别函数。这样的迭代过程称之为训练过程，所构成的分类器称为有人监督或有教师的分类器。4.1.1线性判别函数的基本概念在正态分布的Bayesian判别中，已经遇到过在两类情况下判别函数为线性的情况。假设有ω1和ω2两类模式，在二维模式特征空间可用一直线把这两类模式划分开，如图4.1所示。x1x2g(x)=w2x2+w1x1+w0图4.1两类模式的一个简单判别函数+－划分直线的方程参数坐标变量4.1.1线性判别函数的基本概念判别规则若给定一个未知类别的模式x当g(x)0时，则决策x属于ω1；当g(x)0，则决策x属于ω2；若x处于划分边界上即g(x)=0，则x的类别不可确定，则可将x任意分到某一类或拒绝，g(x)=0为不可确定的条件。这一概念可以推广到有限维欧氏空间中的非线性边界的更一般情况。4.1.1线性判别函数的基本概念g(x)=wdxd+wd-1xd-1+…+w1x1+w0=wTx+w0(4-1)dxxx21xd21w一般的线性判别函数形式为：特征向量(样本向量)权向量阈值权(常数)4.1.1线性判别函数的基本概念简单线性分类器：4.1.1线性判别函数的基本概念对于两类问题的线性分类器决策规则：令g(x)=g1(x)－g2(x)如果g(x)＞0，则决策x∈ω1g(x)＜0，则决策x∈ω2(4-2)g(x)＝0，则可将x任意分到某一类或拒绝4.1.1线性判别函数的基本概念对于两类问题的线性分类器决策规则：方程g(x)=0定义了一个决策面，把归类于ω1类的点和归类于ω2的点分割开。假设x1和x2都在决策面H上，则有wTx1+w0=wTx2+w0(4-3)或wT(x1－x2)=0(4-4)表明，w和超平面H上任一向量正交，即w是H的法向量。4.1.1线性判别函数的基本概念一般地，一个超平面H把特征空间分成两个半空间，即对ω1类的决策域R1和对ω2类的决策域R2。因为当x在R1中时，g(x)0，所以决策面的法向量是指向R1的。因此，有时称R1中的任何x在H的正侧，相应地，称R2中的任何x在H的负侧。4.1.1线性判别函数的基本概念判别函数g(x)是特征空间中某点x到超平面距离的一种代数量度。若把x表示成式中xp：是x在H上的投影向量；r：是x到H的垂直距离；wwxxrpww：是w方向上的单位向量。0p0pT)()(g4.1.1线性判别函数的基本概念若x为原点，则g(x)=w0(4-7)将(4-7)代入(4-6)，就得到从原点到超平面H的距离w)x(gr(4-6)w0wr判别函数g(x)是特征空间中某点x到超平面距离的一种代数量度。4.1.1线性判别函数的基本概念w0wr如果w00，则原点在H的正侧；若w00，则原点在H的负侧。若w0=0，则g(x)具有齐次形式wTx，说明超平面H通过原点。判别函数g(x)是特征空间中某点x到超平面距离的一种代数量度。4.1.1线性判别函数的基本概念图4.2对这些结果作了几何解释。4.1.1线性判别函数的基本概念结论利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域。超平面的方向由权向量w确定，它的位置由阈值权w0确定。判别函数g(x)正比于x点到超平面的代数距离（带正负号）当x在H正侧时，g(x)＞0，在负侧时，g(x)＜0。4.1.1线性判别函数的基本概念4.1.2广义线性判别函数如图4.3所示的二类问题。设有一维样本空间X，所希望的划分是：如果xb或xa，则x属于ω1类；如果bxa，则x属于ω2类。xg(x)图4.3baω1ω1ω24.1.2广义线性判别函数显然，没有任何一个线性判别函数能解决上述划分问题。这说明线性判别函数虽然简单，但局限性较大，不适用于非凸决策区域和多连通区域的划分问题。xg(x)baω1ω1ω2图4.3从图4.3中可以看出，如果建立二次判别函数g(x)=(x-a)(x-b)(4-9)则可以很好地解决上述分类问题，决策规则是：g(x)0，则决策x∈ω1g(x)0，则决策x∈ω2二次判别函数可写成如下一般形式g(x)=c0+c1x+c2x2(4-10)如果适当选择x→y的映射，则可把二次判别函数化为y的线性函数31)(iiiTyagyax4.1.2广义线性判别函数式中213211xxyyyy210321cccaaaayaxTg)(称为广义判别函数，a叫做广义权向量。一般地，对于任意高次判别函数g(x)(这时的g(x)可看作对任意判别函数作级数展开，然后取其截尾部分的逼近)，都可以通过适当的变换，化为广义线性判别函数来处理。31)(iiiTyagyax4.1.2广义线性判别函数存在问题经过变换后，维数大大增加了，这将使问题很快陷入所谓“维数灾难”。在统计学习理论中，对广义线性分类器进行研究，克服了“维数灾难”问题，进而发展出了最新的模式识别方法——支持向量机，成为解决有限样本情况下非线性分类问题的有效手段。4.1.2广义线性判别函数把(4-1)式定义的线性判别函数写成下面的形式xy1121dxxxwa02101ˆddyaxTdiiidiiiyaxwwg110)((4-12)增广特征向量Augmentedfeaturevector增广权向量(广义权向量)Augmentedweightvector4.1.2广义线性判别函数结论y与x相比，虽然增加了一维，但保持了样本间的欧氏距离不变，变换后的样本向量仍然全部位于d维子空间，即原X空间中，方程0yaT(4-13)在Y空间确定了一个通过原点的超平面。Hˆ它对d维子空间的划分与原决策面wTx+w0=0对原X空间的划分完全相同。4.1.2广义线性判别函数例子这种方法的优缺点可通过例子来说明。考虑二次判别函数2321)(xaxaaxg得到三维向量y21xxy从x到y的映射如图所示。4.1.2广义线性判别函数例子4.1.2广义线性判别函数数据仍保持固有的一维，因为改变x将导致y沿着一个三维曲线运动。如果x服从某一个概率分布时，得到的密度函数是退化的，即曲线之外是0，在曲线上是无穷大，这是从低维空间到高维空间映射的普遍问题。例子4.1.2广义线性判别函数图中映射y=(1,x,x2)T把一条直线映射为三维空间中的一条抛物线。由于两类问题，在三维空间中，一个平面就是一个分隔面。因此，由图可见，这产生了原始一维x空间的不连通性例子g(x)=－1+x+2x2x－1和x0.5时g(x)0a=(-1,1,2)T4.1.2广义线性判别函数由aTy=0定义的平面将y空间分成两个判别区域，如图给出当a=(-1,1,2)T时的分类平面和x空间对应的判别区域。结论aTy=0在2维空间不穿过原点4.1.2广义线性判别函数一个三维增广特征空间y和增广权向量a(在原点)。满足aTy=0的点集是一个穿过y空间原点的超平面(用红色表示)，这个平面垂直于a。这个平面在其原来的二维空间中不一定穿过原点(即立方体顶部虚线所示的判决边界)。因此存在一个增广权向量a，可以获得x空间中任意的判定线。4.1.3设计线性分类器的主要步骤设计线性分类器，就是建立线性判别函数(4-l)式g(x)=wTx+w0或广义线性判别函数(4-12)式yaxTg)(这样，设计线性分类器就转化为，利用训练样本集寻找准则函数的极值点和或。*a*w*0w设计线性分类器的主要步骤如下：⒈要有一组具有类别标志的样本集X={x1，x2，…，xN}。如果在样本xn抽出后，把它看作一个确定的观察值，则这组样本集称为确定性样本集；若把xn看作一个随机变量，则这组样本集称为随机样本集。有时也将样本集X转换成增广样本集Y来处理。4.1.3设计线性分类器的主要步骤⒉要根据实际情况确定一个准则函数J它必须满足：⑵J的值反映分类器的性能，它的极值解则对应于最好的决策。⑴J是样本集X和w、w0或a的函数；设计线性分类器的主要步骤如下：4.1.3设计线性分类器的主要步骤*0*)(wgTxwx*0w⒊用最优化技术求出准则函数的极值解和w*或a*。这样就可以得到线性判别函数yaxTg*)(或设计线性分类器的主要步骤如下：4.1.3设计线性分类器的主要步骤4.2Fisher线性判别Fisher线性判别函数是经典判别方法之一，应用非常广泛。应用统计方法解决模式识别问题时，困难之一是维数问题。在低维空间里行得通的方法，在高维空间里往往行不通。因此，降低维数有时就成为处理实际问题的关键。在数学上通常可以把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分开得最好。问题是如何根据实际情况找到这条最好的、使最易于分类的投影线。这就是Fisher法所要解决的基本问题(见图4.4)。4.2Fisher线性判别4.2Fisher线性判别从d维空间到一维空间的数学变换方法假设有一集合X包含N个d维样本x1，x2，…，xN，其中N1个属于ω1类的样本记为子集X1，N2个属于ω2类的样本记为X2，若对xn的分量作线性组合可得标量yn=wTxn,n=1，2，…，Ni这样便得到N个一维样本yn组成的集合，并可分为两个子集Y1和Y2。4.2Fisher线性判别w*就是最好的投影方向从几何上看，如果||w||=1，则每个yn就是相对应的xn到方向为w的直线上的投影，实际上，w的绝对值是无关紧要的，它仅使yn乘上一个比例因子，重要的是选择w的方向。w的方向不同，将使样本投影后的可分离程度不同，从而直接影响识别效果。因此，前述所谓寻找最好投影方向的问题，在数学上就是寻找最好的变换向量w*的问题。4.2Fisher线性判别定义几个基本参量⒈在d维X空间⑴各类样本均值向量miiXxiiNxm1，i=1，2⑵样本类内离散度矩阵Si和总类内离散度矩阵SwiXxTiiiS))((mxmx，i=1，2Sw=S1+S24.2Fisher线性判别⑶样本类间离散度矩阵SbSb=(m1－m2)(m1－m2)T其中Sw是对称半正定矩阵，而且当Nd时通常是非奇异的。Sb也是对称半正定矩阵，在两类条件下，它的秩最大