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

模式识别第四章线性判别函数（1）1.按贝叶斯决策理论设计分类器的步骤这种方法跳过了统计分布的参数估计，没有使用统计参数作为依据，因此称为非参数判别分类方法。而以贝叶斯决策方法为基础的方法则称为参数判别方法。2.获取统计分布及其参数这部分是很困难的，实际问题中并不一定具备获取准确统计分布的条件，因此将模式识别的设计过程，主要是判别函数、决策面方程的确定过程改成第四章线性判别函数§4.1引言按照基于统计参数的决策分类方法，判别函数及决策面方程的类别确定是由样本分布规律决定的，例如，符合某种条件就可使用线性分类器。利用样本集直接设计分类器的基本思想：给定某个判别函数类，且假定判别函数的参数形式已知用训练的方法来估计判别函数的参数值分类决策在非参数判别方法的设计中，使用什么典型的分类决策方法要预先由设计者确定，然后利用训练样本集提供的信息进行训练与学习，从而确定这些函数中的参数。这是参数与非参数判别方法的一个重要不同点。4.1引言问题描述：4.1引言例如下图：三类的分类问题，它们的边界线就是一个判别函数。123边界2x1x4.1引言判别函数包含两类：一类是线性判别函数：线性判别函数广义线性判别函数（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）分段线性判别函数另一类是非线性判别函数线性分类器的三种典型方法•以Fisher准则为代表的传统模式识别方法，•以感知准则函数为代表的机器自学习方法，•以支持向量机代表的统计学习理论。分段线性判别函数：近邻法这种方法主要依据同类物体在特征空间具有聚类特性的原理。同类物体由于其性质相近，它们在特征空间中应具有聚类的现象，因此可以利用这种性质产生分类决策的规则。4.1引言4.1引言§4.2线性判别函数线性判别函数：x的各个分量的线性函数或以x为自变量的某些函数的线性函数。对于c类问题：0)(wxwxgT0)(iTiiwxwxg利用样本集估计参数wi和wi0，并把未知样本x归到具有最大判别函数值的类别中去。寻找线性判别函数的问题被形式化为极小化准则函数的问题。以分类为目的的准则函数可以是样本风险，也可以是训练误差。目标：能够正确地对新的样本进行分类第四章线性判别函数线性判别函数的基本概念1212,,...,,...TdTdx=xxxw=()Tgxwxw设样本d维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成其中w0是一个常数，称为阈值权。相应的决策规则可表示成g(x)＝0就是相应的决策面方程，在线性判别函数条件下它对应d维空间的一个超平面。12g0g0g0xxxxx(),则决策如果(),则决策()=,可将其任意分类或拒绝4.2线性判别函数线性判别函数的基本概念至于w0则体现该决策面在特征空间中的位置，当w0=0时，该决策面过特征空间坐标系原点，而时，则表示了坐标原点到该决策面的距离。为了说明向量w的意义，我们假设在该决策平面上有两个特征向量x1与x2，则应有其中(x1-x2)也是一个向量而g(x)也就是d维空间中任一点x到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。上式表明向量w与该平面上任两点组成的向量(x1-x2)正交，因此w就是该超平面的法向量。这就是向量w的几何意义。102102()0TTTwxwwxwwxx4.2线性判别函数线性判别函数的几何意义0()Tgxwxw令决策面(decisionboundary)H方程：g(x)=0向量w是决策面H的法向量g(x)是点x到决策面H的距离的一种代数度量ppxrwx=x+r,wxHxwwHw是在上的投影向量是到的垂直距离是方向上的单位向量x1x2wxxprH:g=0g(x)=rw证明：4.2线性判别函数x1x2wxxprH:g=0线性判别函数的几何意义0()Tgxwxww=r000()wwxgxwHr若为原点，则原点到超平面的距离：令000000wHwHwH原点在的正侧原点在的负侧通过原点4.2线性判别函数线性判决函数理论和分类法，简单易行。但实际应用中常遇到非线性判决函数，如果能把非线性判决函数转变为线性判决函数，那么线性判决函数理论和分类法应用会更广泛。事实上，非线性判决函数可以转变为线性判决函数，称广义线性判决函数。只要各类别没有重叠，总能在Rd空间找到一个广义决策函数，把从全体c类中分离。i广义线性判决函数4.2线性判别函数abox()gx121一维x空间中非线性判别函数例2()()()()gxxaxbxabxab1()()0,ifxaorxbthengxx2()()0,ifaxbthengxx作非线性变换：212,yxyx1201,(),wwabwab通过非线性变换，非线性判决函数转变成了线性判决函数；特征空间也由一维x空间映射成二维y空间。执行非线性变换，特征空间维数的增长往往不可避免。11220wywyw12()()gyabyaby()gx31()Tiiigxwywy此时g(x)被称为广义线性判别函数，a称为广义权向量。4.2线性判别函数12()()0gyabyaby二维y空间决策方程：211()()abyyabab120:abyyab210:yyab12()()0gyabyaby12()yabyab1211yababyyababab120:abyyab210:yyab判决函数的正负侧：正侧区o1y2yababab二维y空间中广义性判决函数21()()0,gxxabxabx212{:,}yxyxy121()()0,gyabyabyy12120,()0,gyyy广义线性判决规则变量代换4.2线性判别函数广义线性判别函数的一般式：110()()()Tkkgwfwfwxxxwy12[1,(),(),,()]Tkfffyxxx012[,,,,]Tkw因此，在y特征空间可线性表示一个非常复杂的x空间的决策函数，广义线性函数.按照上述原理，任何非线性函数g(x)用级数展开成高次多项式后，都可转化成广义线性判别函数来处理。wTy=0在Y空间确定了一个通过原点的超平面。这样我们就可以利用线性判别函数的简单性来解决复杂的问题。经过这种变换，维数大大增加了，这将使问题很快陷入所谓的“维数灾难”。怎么解决？支持向量机4.2线性判别函数广义线性判别函数线性判别函数的齐次简化使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。ˆY()ˆHTgxayraay空间任意一点到的距离为：线性判别函数的齐次简化：()TT0gx=wx+w=ay111,,...,Tdxxxy001,,...,Tdwa一种特殊映射方法：增广样本向量y与增广权向量a4.2线性判别函数广义线性判别函数例如一个一维特征空间的分类器，其决策面方程为x-c=0在一维空间中为一个点。经齐次简化后可得：此时在二维空间中决策面为一过原点的直线，如上图所示。直线以为法线向量，它对1维子空间(y2空间)的划分与原决策面完全相同。4.2线性判别函数1xy1caa广义线性判别函数答：一个过原点的平面，方程为ay1+by2+cy3=0(B)。(A)式与(B)式形式上略有不同，但当y3=1时两者就一样了。也就是说(B)式表示的平面与y3=1子空间(一平面)的交线就是(A)式中表示的直线。思考一下，如果在两维空间存在一条不过原点的直线，ax1+bx2+c=0(A)，采用增广向量形式：那么，它在增加一维的三维空间中，aTY=0表示的是什么呢？4.2线性判别函数线性分类器的设计步骤：给定样本集X，确定线性判别函数的各项系数w和w0。步骤：收集一组具有类别标志的样本X={x1,x2,…,xN}按需要确定一准则函数J，其值反映分类器的性能，其极值解对应于“最好”的决策。用最优化技术求准则函数J的极值解w*和w0*，从而确定判别函数，完成分类器设计。*maxwwJ对于未知样本x，计算g(x)，判断其类别。()T0gx=wx+w4.2线性判别函数换一个方式说：设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方程的两个参数，一个是权向量w，另一个是阈值w0。为了使所设计的线性分类器在性能上要满足一定的要求，这种要求通过一种准则来体现，并且要表示成一种准则函数，以便能通过将准则函数值优化的方法确定w与w0。4.2线性判别函数§4.3Fisher线性判别Fisher线性判别函数是研究线性判别函数中最有影响的方法之一。对线性判别函数的研究就是从R.A.Fisher在1936年发表的论文开始的。第四章线性判别函数首先要确定准则函数；然后再利用训练样本集确定该分类器的参数，以求使所确定的准则达到最佳。在使用线性分类器时，样本的分类由其判别函数值决定，而每个样本的判别函数值是其各分量的线性加权和再加上一阈值w0。()T0gxwx+w设计线性分类器：如果我们只考虑各分量的线性加权和，则它是各样本向量与向量w的向量点积。4.3Fisher线性判别w(y)wy1y2x2x1ω1ω2现在讨论通过映射投影来降低维数的方法。把X空间各点投影到Y空间得一直线上，维数由2维降为一维。若适当选择w的方向，可以使二类分开。下面我们从数学上寻找最好的投影方向，即寻找最好的变换向量w的问题。4.3Fisher线性判别Fisher准则的基本原理Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。分析w1方向之所以比w2方向优越，可以归纳出这样一个准则，即向量w的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。这就是Fisher准则函数的基本思路。H:g=0符合Fisher准则要求不符合Fisher准则要求4.3Fisher线性判别一些基本参量的定义1.样本在d维特征空间的一些描述量。(1)各类样本均值向量miiixXi1m=xi=1,2N(3)样本类间离散度矩阵Sb：Tb1212S=(m-m)(m-m)(2)样本类内离散度矩阵Si与总类内离散度矩阵Sw()(),1,2iTiiiXixSxmxm12wSSS4.3Fisher线性判别一些基本参量的定义1,1,2iiyYimyiN样本类内离散度、总类内离散度和类间离散度2(),1,2iiiyYSymi12wSSS212()bSmm各类样本均值2.在一维Y空间4.3Fisher线性判别根据Fisher选择投影方向w的原则：使原样本向量在该方向上的投影能兼顾：类间分布尽可能分开，类内样本投影尽可能密集。这个函数称为Fisher准则函数。应该寻找使分子尽可能大，分母尽可能小的w作为投影向量。用以评价投影方向w的函数为：2121212()()bFSmmJwSSSS4.3Fisher线性判别得出最终表达式：2121212()()bFSmmJwSSSS11,1,2iiTTiiYxXiimyiNNywxwm221212()()TTbSmmwmwm1212()()TTTbSwmmmm()iiiyYSym2()iTTixXwxwm()()iTTiixXwxmxmwTi