第4章线性分类器.pptx

软件工程专业第四章第四章 线性分性分类器器计算机与通信工程学院算机与通信工程学院计算机与通信工程学院算机与通信工程学院模式模式识别软件工程专业v假设对一模式X已抽取n个特征，表示为：v模式识别问题就是根据模式X的n个特征来判别模式属于1,2,m类中的那一类。例如右上图：三类的分类问题，它们的边界线就是一个判别函数4.1 判判别函数函数软件工程专业v用判别函数进行模式分类，取决两个因素：v判别函数的几何性质：线性与非线性v判别函数的参数确定：判别函数形式+参数v判别函数包含两类：v一类是线性判别函数：线性判别函数：线性判别函数是统计模式识别的基本方法之一，简单且容易实现广义线性判别函数所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间（高维）变成线性判别函数分段线性判别函数v另一类是非线性判别函数软件工程专业我们现在对两类问题和多类问题分别进行讨论。一、两一、两类问题：即:1.二二维情况情况：取两个特征向量这种情况下判别函数:4.2 线性判性判别函数函数软件工程专业在两类别情况，判别函数g(x)具有以下性质：这是二维情况下判别由判别边界分类。情况如图：软件工程专业2.n维情况：情况：现抽取n个特征为：判别函数：另外一种表示方法：软件工程专业模式分类：当g(x)=WTX=0为判别边界。当n=2时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面。当n3时，则判别边界为一超平面。软件工程专业1.第一种情况：每一模式类与其它模式类间可用单个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：二、对于多类问题：模式有1,2,m个类别，可分三种情况：此情况可理解为两分法。软件工程专业下图所示，每一类别可用单个判别边界与其它类别相分开。如果一模式X属于1，则由图可清楚看出：这时g1(x)0而g2(x)0，g3(x)0，g2(x)0，g3(x)0。则此模式X就无法作出确切的判决。如图中IR1,IR3，IR4区域。另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确定区域。软件工程专业问当x=(x1,x2)T=(6,5)T时属于那一类结论：g1(x)0，g3(x)g2(x)和g1(x)g3(x)。假设判别函数为：则判别边界为：软件工程专业结论：不确定区不确定区间没有了，所以没有了，所以这种是最好情况种是最好情况。用上列方程组作图如下：软件工程专业问假设未知模式x=(x1,x2)T=(1,1)T，则x属于那一类。把它代入判别函数：得判别函数为：因为所以模式x=(1,1)T属于类。软件工程专业关于关于线性判性判别函数的函数的结论v模式类别若可用任一线性判别函数来划分，这些模式就称为线性可分；一旦线性判别函数的参数确定，这些函数即可作为模式分类的基础。v对于M（M2）类模式分类，第一、三种情况需要M个判别函数，第二种情况需要M(M-1)/2个判别函数。v对于第一种情况，每个判别函数都要把一种类别（比如i类）的模式与其余M-1种类别的模式划分开，而不是仅将一类与另一类划分开。v实际上，一个类的模式分布要比M-1类模式分布更聚集，因此后两种情况实现模式线性可分的可能性要更大一些。软件工程专业4.3 线性判性判别函数的性函数的性质一、模式空一、模式空间与加与加权空空间：v模式空间：由构成的n维欧氏空间。vW是此空间的加权向量，它决定模式的分界面H，W与H正交。v加权空间：以为变量构成的欧氏空间v模式空间与加权空间的几何表示如下图：2024/5/8周三软件工程专业v在三维空间里，令w3=0，则为二维权空间。如图：v给定一个模式X，就决定一条直线：v即分界面H，W与H正交，W称为解向量。v解向量的变动范围称为解区。v因x1,x21，x3,x42由图可见x1,x3离的最近，所以分界面H可以是x1,x3之间的任一直线，由垂直于这些直线的W就构成解区，解区为一扇形平面，即阴影区域。v如右图:二、解向量和解区分解面H软件工程专业把不等式方程正规化：正规化：H分界面样本的正规化，令：由此可见，可以不管样本原来的类别标识，只要找到一个对全部样本都满足的权向量即可，叫做正规化增广样本向量。软件工程专业vg(x)=WTX=0决定一个决策界面，当g(x)为线性时，该决策界面便是一个超平面H，并有以下性质：v性质：W与与H正交正交（如图所示）假设x1,x2是H上的两个向量所以 W 与(x1-x2)垂直，即W与H正交。一般说，超平面H把特征空间分成两个半空间。即1,2空间，当x在1空间时g(x)0,W指向1，为H的正侧，反之为H的负侧。三、超平面的几何性质12g(x)0g(x)0 x10-X1dW1-X2dW2-W30所以g(x)=WTX0其中W=(W1,W2,W3)T为各模式增1矩阵为N*(n+1）矩阵N为样本数，n为特征数启迪：认知小样本和高维特征空间的矛盾软件工程专业由由此此可可见：训练过程就是对已知类别的样本集求解权向量，这是一个线性联立不等式方程组求解的过程。求解求解时：只有对线性可分的问题，g(x)=WTX才有解联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解的问题求解W的过程就是训练的过程。训练方法的共同点是，先给出准则函数，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数。同时，算法可以分为迭代法和非迭代法。软件工程专业一、梯度下降法一、梯度下降法迭代法迭代法基基本本思思路路：欲对不等式方程组WTX0求解，首先定义准则函数(目标函数)J(W)，再求J(W)的极值使W优化。因此，求解权向量的问题就转化为对一标量函数求极值的问题。解决此类问题的方法是梯度下降法。基基本本方方法法：就是从起始值W1开始，算出W1处目标函数的梯度矢量J(W1)，则下一步的W2值为：W2=W1-1J(W1)W1为起始权向量，1为迭代步长J(W)为目标函数J(W1)为W1处的目标函数的梯度矢量软件工程专业在第K步的时候：Wk+1=Wk-kJ(Wk)这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解矢量，步长k取值很重要。关于步关于步长k讨论：(1)k太大，迭代太快，引起振荡，甚至发散;(2)k太小，迭代太慢。结论：应该选最佳k。最优化理论软件工程专业二、感知器法二、感知器法感知器的原理结构为：“感知器”是借于上世纪五六十年代人们对一种分类学习机模型的称呼，源于对生物智能的仿生学领域。软件工程专业基本思路：基本思路：通过对W的调整，可实现判别函数：g(x)=WTXRT其中RT为响应阈值定定义感知准感知准则函数准函数准则：只考虑错分样本定定义：，其中X0为错分样本当分类发生错误时就有WTX0,所以J(W)总是正值，错误分类愈少，J(W)就愈小。理想情况为，即求最小最小值的问题。软件工程专业求最小值，对W求梯度代入迭代公式中由J(W)经第K+1次迭代时，J(W)趋于0，收敛于所求的W值。软件工程专业v感知器算法：感知器算法：1.错误分类修正wk如wkTx0并且x1wk+1=wk+kx如wkTx0并且x2wk+1=wk-kx2.正确分类，wk不修正如wkTx0并且x1如wkTx0并且x2wk+1=wk+-Hwk+1kxwk权值修正示意图软件工程专业例题：有两类样本：1=（x1,x2）=(1,0,1),(0,1,1)，2=（x3,x4）=(1,1,0),(0,1,0)解：先求四个样本的增广向量x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)假设初始权向量w1=(1,1,1,1)k=1第一次迭代：w1Tx1=(1,1,1,1)(1,0,1,1)T=30所以不修正w1Tx2=(1,1,1,1)(0,1,1,1)T=30所以不修正w1Tx3=(1,1,1,1)(1,1,0,1)T=30所以修正w1w2=w1-x3=(0,0,1,0)w2Tx4=(0,0,1,0)T(0,1,0,1)=0所以修正w2w3=w2-x4=(0,-1,1,-1)第一次迭代后,权向量w3=(0,-1,1,-1),再进行第2,3,次迭代，如下表：软件工程专业直到在一个迭代过程中权向量相同，训练结束。w6=w=(0,1,3,0)判别函数g(x)=-x2+3x3v感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点训练样本wkTx修正式修正后的权值wk1迭代次数x11011x20111x31101x40101+0w1w1w1-x3w2-x4111111110010011-11x11011x20111x31101x401010+0-w3+x1w4w4-x3w5112011200221022-12x11011x20111x31101x40101+-w5w5+x2w6w602210130013001303x11011x20111x31101x40101+-w6w6w6w601300130013001304软件工程专业三三、最小平方、最小平方误差准差准则前面我们讨论的线性分类器训练方法，其共同点是企图找一个权向量W，使错分样本最小。现在我们把不等式组变成如下形式：WTXi=bi0则有联立方程XW=b这是矛盾方程组，方程数大于未知数，所以没有精确解的存在。每个样本有n个特征软件工程专业定义误差向量：e=XW-b0把平方误差作为目标函数W的优化就是使J(W)最小。于是，求J(W)的梯度并令其为0，即解上方程得XTXW=XTb这样把求解XW=b的问题，转化为对XTXW=XTb求解，这样最大好处是：因XTX是方阵且通常是非奇异的，所以可以得到W的唯一解。MSE准则函数软件工程专业选取合适的b，只要计算出X+就可以得到W。若取b：（MSE解）其中N/N1有N1个，N/N2有N2个软件工程专业四、四、Fisher分分类准准则现在讨论通过映射投影来降低维数的方法。X空间映射Y空间：把X空间各点投影到Y空间的一直线上，维数由2维降为一维。若适当选择W的方向，可以使二类分开。下面我们从数学上寻找最好的投影方向，即寻找最好的变换向量W的问题Fisher法解决的基本法解决的基本问题。w(y)wy1y2x2x112软件工程专业投影样本之间的分离性用投影样本之差表示：投影样本类内离散度:i=1,2i=1,2软件工程专业类间散布矩阵软件工程专业上式称为广义Rayleigh商，其极值可用Lagrange乘子法求解其极值解是n维x空间向一维y空间的最好投影方向，它实际是多维空间向一维空间的一种映射。其中Sw为类内散布矩阵,Sb为类间散布矩阵软件工程专业现在我们已把一个n维的问题转化为一维的问题。在该一维空间设计Fisher分类器:因此，此时只要确定一个合适的阈值W0，将投影点y与W0比较即可进行分类决策。W0的的选择：软件工程专业Q&A Q&A Q&A Q&A