第四章 线性判别函数第四章 线性判别函数2Table of Contents第四章 线性判别函数34.1 引言基于样本的Bayes分类器：通过估计类条件概率密度函数，设计相应的判别函数最一般情况下适用的“最优”分类器：错误率最小，对分类器设计在理论上有指导意义。获取统计分布及其参数很困难，实际问题中并不一定具备获取准确统计分布的条件。 训练样本集样本分布的统计特征：概率密度函数决策规则：判别函数决策面方程分类器功能结构ARGMAXg1.g2gc.x1x2xna(x)第四章 线性判别函数4直接确定判别函数u基于样本的直接确定判别函数方法：设定判别函数形式，用样本集确定判别函数的参数。定义准则函数，表达分类器应满足的要求。这些准则的“最优”并不一定与错误率最小相一致：次优分类器。 实例：正态分布最小错误率贝叶斯分类器在特殊情况下，是线性判别函数g(x)=wTx（决策面是超平面）。那么我们能否基于样本直接确定w?引言训练样本集决策规则：判别函数决策面方程选择最佳准则第四章 线性判别函数5线性分类器设计步骤u线性分类器设计任务：给定样本集K，确定线性判别函数g(x)=wTx的各项系数w。u步骤：1.收集一组已知类别的样本K=x1,x2,xN2.按需要确定一准则函数J(K,w)，其值反映分类器的性能，其极值解对应于“最好”分类。3.用最优化技术求准则函数J的极值解w*，从而确定判别函数，完成分类器设计。u对于未知样本x，计算g(x)，判断其类别。引言设计应用第四章 线性判别函数6第四章 线性判别函数7线性判别函数ud维空间中的线性判别函数的一般形式：ux是样本向量，即样本在d维特征空间中的描述， w是权向量，w0是一个常数(阈值权)。引言第四章 线性判别函数8两类问题的分类决策规则引言规则表达1规则表达2第四章 线性判别函数9线性判别函数的几何意义u决策面(decision boundary)方程：g(x)=0u决策面将特征空间分成决策区域。u向量w是决策面H的法向量ug(x)是点x到决策面H的距离的一种代数度量x1x2wxxprH: g=0R1: g0R2: g0引言第四章 线性判别函数10线性分类器的分类界面线性分类器的分类界面分类界面的几何解释分类界面的几何解释1.线性分类界面H是d维空间中的一个超平面；2.分类界面将d维空间分成两部分，R1，R2分别属于两个类别；3.判别函数的权矢量w是一个垂直于分类界面H的矢量，其方向指向区域R1 ；4.偏置w0与原点到分类界面H的距离有关：第四章 线性判别函数124.2 矩阵计算基础矢量X可以看作是N维欧氏空间中的一个点，用一个列矢量表示： 第四章 线性判别函数13 线性判别函数和判别界面线性判别函数和判别界面第四章 线性判别函数14线性不可分情况线性不可分情况第四章 线性判别函数15矩阵矩阵矩阵可以看作是由若干个矢量构成的： 第四章 线性判别函数16矩阵的秩矩阵的秩u矩阵所有行向量的最大无关组个数称为行秩；u矩阵所有列向量的最大无关组个数称为列秩；u一个矩阵的行秩等于列秩，称为矩阵的秩。第四章 线性判别函数17转置转置u列矢量W的转置WT为一个行矢量；uN*M的矩阵A的转置AT为一个M*N的矩阵。第四章 线性判别函数18矢量与矢量的乘法矢量与矢量的乘法(1) u设W和X为N维列矢量结果是一个数。第四章 线性判别函数19矢量与矢量的乘法矢量与矢量的乘法(2) u设W和X为N维列矢量结果是一个N*N维的矩阵。第四章 线性判别函数20矢量与矩阵的乘法u设W为N维列矢量，A为一个N*M的矩阵：结果是一个N维列矢量。第四章 线性判别函数21正交正交u设W和X为N维列矢量，如果W与X的内积等于零：则称W与X正交，也称W垂直于X。 第四章 线性判别函数22逆矩阵逆矩阵uA为一个N*N的方阵，A的逆阵用A-1表示，满足： 其中I为单位阵。 一个矩阵的逆阵存在条件：1)是一个方阵，2)是一个满秩矩阵，矩阵的秩为N第四章 线性判别函数23矩阵的特征值和特征向量矩阵的特征值和特征向量uA为一个N*N的方阵，如果有： 数称为A的特征值，矢量称为A的特征矢量。第四章 线性判别函数24矩阵的迹和行列式值矩阵的迹和行列式值uA为一个N*N的方阵，A的迹为主对角线元素之和：第四章 线性判别函数25矩阵的迹、行列式值与特征值之间的关系矩阵的迹、行列式值与特征值之间的关系u矩阵A有N个特征值1，2， N，则有如下关系：第四章 线性判别函数26矩阵对数值变量微分矩阵对数值变量微分u矩阵A(t)=aij(t)M*N，元素aij(t)是变量t的函数，矩阵A(t)对t的微分：第四章 线性判别函数27矩阵函数对矩阵的微分矩阵函数对矩阵的微分u矩阵X=(xij)M*N，M*N元函数f(X)，定义f(X)对矩阵X的导数：第四章 线性判别函数28常用矢量微分的性质uX和W为N维矢量，A为M*N的矩阵：第四章 线性判别函数294.3 线性（与非线性）判别函数线性（与非线性）判别函数u一、两类问题一、两类问题u二、多类问题二、多类问题4.3 .1线性判别函数线性判别函数第四章 线性判别函数30两类问题的线性判别函数两类问题的线性判别函数uX0=(x1, x2, xN)T为待识模式的特征矢量；uW0=(w1, w2, , wN)T称为权矢量。第四章 线性判别函数31线性判别函数线性判别函数ux=(x1, x2, xd)t: 特征矢量；uw=(w1, w2, , wd)t: 权矢量；uw0：偏置(bias)。第四章 线性判别函数32线性判别函数的增广形式线性判别函数的增广形式uX=(x1, x2, xN, 1) T称为增广的特征矢量；uW=(w1, w2, , wN , 1)T称为增广的权矢量。第四章 线性判别函数33两类问题线性判别准则两类问题线性判别准则第四章 线性判别函数34多类问题（情况一）多类问题（情况一）u每一类模式可以用一个超平面与其它类别分开；u这种情况可以把M个类别的多类问题分解为M个两类问题解决；第四章 线性判别函数35多类问题（情况一）多类问题（情况一）第四章 线性判别函数36多类问题（情况一）判别规则多类问题（情况一）判别规则u当d1(X)0，而d2(X)0且d3(X)0时，判别X属于1；u当d2(X)0，而d1(X)0且d3(X)0时，判别X属于2；u当d3(X)0，而d1(X)0且d2(X)0 对样本y错误分类，则有：aTy0u定义一准则函数JP(a) (感知准则函数)： 被错分类的规范化增广样本集u恒有JP(a)0，且仅当a为解向量，Yk为空集（不存在错分样本）时， JP(a)=0，即达到极小值。确定向量a的问题变为对JP(a)求极小值的问题。感知器第四章 线性判别函数63梯度下降算法u梯度下降算法：对(迭代)向量沿某函数的负梯度方向修正，可较快到达该函数极小值。 感知器第四章 线性判别函数64感知器算法的思想第四章 线性判别函数65感知器算法1.初始化，置W(1)中的元素为一个小的随机数；2.在第k步学习训练样本Xk，按照如下公式修正权值W：3.重复第2步，直到所有训练样本被正确识别。第四章 线性判别函数66 感知器算法感知器算法(Perceptron)u最直观的准则函数定义是最少错分样本数准则： JN(a) = 样本集合中被错误分类的样本数；感知器准则感知器准则以错分样本到判别界面距离之和作为准则：第四章 线性判别函数68算法(step by step)1. 初值: 任意给定一向量初始值a a12. 迭代: 第k+1次迭代时的权向量a ak+1等于第k次的权向量a ak加上被错分类的所有样本之和与rk的乘积3. 终止: 对所有样本正确分类任意给定一向量初始值a1ak+1= ak+ rkSum(被错分类的所有样本)所有样本正确分类得到合理的a完成分类器设计NY感知器第四章 线性判别函数69感知器方法例解 u固定增量法与可变增量法u批量样本修正法与单样本修正法单样本修正法：样本集视为不断重复出现的序列，逐个样本检查，修正权向量批量样本修正法：样本成批或全部检查后，修正权向量感知器感知器算法感知器算法(批量调整版本批量调整版本)1.begin initialize , , k02. do kk+13. 4. until 5.return a6.end第四章 线性判别函数71感知器算法感知器算法(单样本调整版本单样本调整版本)1.begin initialize , k02. do k(k+1)mod n3. if yk is misclassified by a then 4. until all patterns properly classified5.return a6.end第四章 线性判别函数72感知器方法小结u感知准则函数方法的思路是：先随意找一个初始向量a1，然后用训练样本集中的每个样本来计算。若发现一个y出现aTy0。当然，修改后的ak+1还可以使某些y出现ak+1Ty 0, i=1,Nu线性分类器设计求一组N个线性不等式的解a*u样本集增广矩阵Y及一组N个线性不等式的的矩阵表示：u引入余量(目标向量) b=b1, b2, , bNT， bi为任意给定正常数， aTyi = bi 0uN个线性方程的的矩阵表示：矛盾方程组，没有精确解第四章 线性判别函数77平方误差准则函数u定义误差向量 e=Ya-b：u定义平方误差准则函数Js(a):u最小二乘近似解（MSE解）：MSE方法的思想：对每个样本，设定一个“理想”的判别函数输出值，以最小平方误差为准则求最优权向量MSE第四章 线性判别函数78MSE准则函数的伪逆解Y的伪逆矩阵MSE第四章 线性判别函数79MSE方法的迭代解ua*=Y+b, Y+=(YTY)-1YT，计算量大u实际中常用梯度下降法：批量样本修正法单样本修正法MSEWidrow-Hoff第四章 线性判别函数80LMSE算法的思想算法的思想此方法也称为Ho-Kashyap算法(H-K算法)u将线性不等式组XW0的问题，转化为解线性方程组XW=B的问题。u其中：B=(b1, b2, , bN)T，bi0第四章 线性判别函数81优化的准则函数u定义误差矢量e：n定义准则函数J(W,B)：梯度法求解上面两个公式成立的W即为所求。n定义伪逆矩阵X*：第四章 线性判别函数83梯度下降算法计算实例有两类的二维数据，其中第一类的两个样本为有两类的二维数据，其中第一类的两个样本为(1,4) t和和(2,3) t，第二类的两个样本为，第二类的两个样本为(3,2) t和和(4,1) t。假设初始。假设初始的的a=(0,1,0) t，n(k)=1利用批处理感知器算法求解线性判利用批处理感知器算法求解线性判别函数别函数g(y)=aty的权向量的权向量a。首先对每个样本增加一维为增广样本。然后规范化第首先对每个样本增加一维为增广样本。然后规范化第二类的样本为：二类的样本为：(-3,-2,-1) t和和(-4,-1,-1) t。计算错分的样本集：计算错分的样本集： g(y1)=(0,1,0)(1,4,1) t=4（正确）（正确）g(y2)=(0,1,0)(2,3,1) t=3（正确）（正确）g(y3)=(0,1,0)(-3,-2,-1) t=-2（错分）（错分）g(y4)=(0,1,0)(-4,-1,-1) t=-1（错分）（错分）第四章 线性判别函数84对错分的样本集求和：对错分的样本集求和：(-3,-2,-1) t+(-4,-1,-1) t =(-7,-3,-2) t修正权向量修正权向量a：a= (0,1,0) t +(-7,-3,-2) t= (-7,-2,-2) t再计算错分的样本集：再计算错分的样本集：g(y1)=(-7,-2,-2)(1,4,1) t=-17 （错分）（错分）g(y2)=(-7,-2,-2)(2,3,1) t=-22 （错分）（错分）g(y3)=(-7,-2,-2)(-3,-2,-1) t=27 （正确）（正确）g(y4)=(-7,-2,-2)(-4,-1,-1) t=32 （正确）（正确）第四章 线性判别函数85对错分的样本集求和：对错分的样本集求和：(1,4,1) t+(2,3,1) t =(3,7,2) t修正权向量修正权向量a：a= (-7,-2,-2) t +(3,7,2) t= (-4,5,0) t再计算错分的样本集：再计算错分的样本集：g(y1)=(-4,5,0)(1,4,1) t=16 （正确）（正确）g(y2)=(-4,5,0)(2,3,1) t=7 （正确）（正确）g(y3)=(-4,5,0)(-3,-2,-1) t=2 （正确）（正确）g(y4)=(-4,5,0)(-4,-1,-1) t=11 （正确）（正确）全部样本正确分类，算法结束全部样本正确分类，算法结束a=(-4,5,0) t。最小平方误差的准则函数最小平方误差的准则函数定义误差矢量e，用e长度的平方作为准则函数：权值矢量的求解权值矢量的求解(伪逆求解法伪逆求解法)称为伪逆矩阵第四章 线性判别函数88例例4.2 u有两类模式的训练样本：1： (0,0), (0,1) 2： (1,0), (1,1) 用LMSE算法求取判别函数，将两类样本分开。权值矢量的求解权值矢量的求解(迭代求解法迭代求解法)1.begin initialize a(0), b, , (), k0；2. do kk+1；3. 4. 5. until 6.return a7.endLMSE算法的特点算法的特点算法的收敛依靠(k)的衰减，一般取(k)=(1)/k；算法对于线性不可分的训练样本也能够收敛于一个均方误差最小解；取b=1时，当样本数趋于无穷多时，算法的解以最小均方误差逼近贝叶斯判别函数；当训练样本线性可分的情况下，算法未必收敛于一个分类超平面。第四章 线性判别函数914.7 讨论u基于样本的直接确定判别函数方法主要包含两个步骤：1.确定使用的判别函数类型或决策面方程类型，如线性分类器，分段线性分类器等2.在选定函数类型的条件下，确定相应的参数，从而完成整个分类器设计u线性判别函数计算简单，在一定条件下能实现最优分类，经常是一种“有限合理”的选择u分段线性分类器可以实现更复杂的分类面第四章 线性判别函数92习题1.有一个三次判别函数：z=g(x)=x3+2x2+3x+4。试建立一映射xy，使得z转化为y的线性判别函数。2.证明决策面H：wTx+w0=0的系数向量w是决策面H的法向量3.设五维空间的线性方程为55x1+68x2+32x3+16x4+26x5+10 =0，试求出其权向量与样本向量点积的表达式wTx+w0=0中的w，x以及增广权向量与增广样本向量形式aTy中的a与y4.设在三维空间中一个类别分类问题拟采用二次曲面。如欲采用广义线性方程求解，试问其广义样本向量与广义权向量的表达式，其维数是多少？