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

第四章线性判别函数1主要内容引言Fisher线性判别感知器准则最小平方误差准则多类问题分段线性判别函数24.1引言基于样本的Bayes分类器：通过估计类条件概率密度函数，设计相应的判别函数MAXg1...g2gc...x1x2xna(x)最一般情况下适用的“最优”分类器：错误率最小，对分类器设计在理论上有指导意义。获取统计分布及其参数很困难，实际问题中并不一定具备获取准确统计分布的条件。训练样本集样本分布的

统计特征：

概率密度函数决策规则：

判别函数

决策面方程分类器

功能结构3直接确定判别函数基于样本的直接确定判别函数方法：针对各种不同的情况，使用不同的准则函数，设计出满足这些不同准则要求的分类器。这些准则的“最优”并不一定与错误率最小相一致：次优分类器。实例：正态分布最小错误率贝叶斯分类器在特殊情况下，是线性判别函数g(x)=wTx（决策面是超平面），能否基于样本直接确定w?训练样本集决策规则：

判别函数

决策面方程选择最佳准则4判别函数假设对一模式X已抽取n个特征，表示为：模式识别问题就是根据模式X的n个特征来判别模式属于ω1,ω2,

…,

ωc类中的那一类。判别函数：表示类分界面的函数。5两类的分类问题，它们的边界线就是一个判别函数判别函数（续）6两类问题中线性不可分的实例判别函数（续）7三类的分类问题，它们的边界线也是一个判别函数判别函数（续）8判别函数包含两类：一类是线性判别函数：线性判别函数广义线性判别函数

（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）分段线性判别函数另一类是非线性判别函数判别函数（续）9线性判别函数d维空间中的线性判别函数的一般形式：x是样本向量，即样本在d维特征空间中的描述，w是权向量，w0是一个常数(阈值权)。两类问题的分类决策规则:10线性判别函数的几何意义决策面(decisionboundary)H方程：g(x)=0向量w是决策面H的法向量g(x)是点x到决策面H的距离的一种代数度量x1x2wxxprH:g=011证明：权向量是决策面的法向量设点、在决策面H中，故它们满足方程，有：上两式相减，可得：这表明向量与向量正交，由于、是H平面中的任意两点，故与决策面H正交，是H平面的法向量。12证明：判别函数g(x)绝对值正比于x到决策面H的距离设平面H的单位法矢量由平面H的方程可得：设P是平面H中的任一点，X是特征空间中任一点，点X到平面H的距离为差矢量（X-P）在n上的投影的绝对值，即：pwx-pnH:g=0x13判别函数g(x)绝对值正比于x到决策面H的距离14证明：判别函数值的正负表示出特征点位于哪个半空间中两矢量n和（x-p）的数积为：当和夹角小于90度时，即在指向的半空间中

当和夹角大于90度时，即在背向的半空间中

由于，故和同号

15广义线性判别函数线性判别函数是形式最为简单的判别函数，但是它不能用于复杂情况。例：设计一个一维分类器，使其功能为：要用二次判别函数才可把二类分开：16广义线性判别函数二次函数的一般形式：g(x)又可表示成：

如果作非线性变换，则原来的一维特征空间映射为三维特征空间。原来一维非线性可分

三维线性可分。17广义线性判别函数(2)按照上述原理，任何非线性函数g(x)用级数展开成高次多项式后，都可转化成线性判别函数来处理。一种特殊映射方法：增广样本向量y与增广权向量a线性判别函数的齐次简化：增广样本向量使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。18下图所示两类模式为线性不可分19经过非线性变换，两类模式为线性可分20线性分类器设计步骤线性分类器设计任务：给定样本集K，确定线性判别函数g(x)=wTx的各项系数w。步骤：收集一组样本K={x1,x2,…,xN}按需要确定一准则函数J(K,w)，其值反映分类器的性能，其极值解对应于“最好”决策。用最优化技术求准则函数J的极值解w*，从而确定判别函数，完成分类器设计。对于未知样本x，计算g(x)，判断其类别214.2Fisher线性判别线性判别函数y=g(x)=wTx:样本向量x各分量的线性加权样本向量x与权向量w的向量点积如果||w||=1，则视作向量x在向量w上的投影Fisher准则的基本原理：找到一个最合适的投影轴，使两类样本在该轴上投影之间的距离尽可能远，而每一类样本的投影尽可能紧凑，从而使分类效果为最佳。22二维模式向一维空间投影示意图oxyoxy23Fisher线性判别图例H:g=0Fisher准则的描述：用投影后数据的统计性质

—均值和离散度的函数作为判别优劣的标准。oxy24d维空间样本分布的描述量各类样本均值向量mi样本类内离散度矩阵Si与总类内离散度矩阵Sw

样本类间离散度矩阵Sb：离散矩阵在形式上与协方差矩阵很相似，但协方差矩阵是一种期望值，而离散矩阵只是表示有限个样本在空间分布的离散程度25一维Y空间样本分布的描述量各类样本均值样本类内离散度和总类内离散度样本类间离散度

以上定义描述d维空间样本点到一向量投影的分散情况，因此也就是对某向量w的投影在w上的分布。样本离散度的定义与随机变量方差相类似26样本与其投影统计量间的关系样本x与其投影y的统计量之间的关系：2728Fisher准则函数评价投影方向w的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求Fisher准则函数的定义：Fisher最佳投影方向的求解29Fisher公式的推导30Fisher最佳投影方向的求解采用拉格朗日乘子算法解决m1-m2是一向量，对与(m1-m2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对m1-m2

向量按Sw-1作一线性变换，从而使Fisher准则函数达到极值点31判别函数的确定前面讨论了使Fisher准则函数极大的d维向量w*的计算方法，投影后的类判别Y0（阈值）可采用以下几种方法确定：分类规则:324.3

感知器准则感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。33基本概念线性可分性：训练样本集中的两类样本在特征空间可以用一个线性分界面正确无误地分开。在线性可分条件下，对合适的(广义)权向量a应有：规范化样本向量

：将第二类样本取其反向向量

34解向量与解区35感知器准则函数对于任何一个增广权向量a

，对样本y正确分类，则有：aTy>0对样本y错误分类，则有：aTy<0定义一准则函数JP(a)(感知准则函数)：被错分类的规范化增广样本集恒有JP(a)≥0，且仅当a为解向量，Yk为空集（不存在错分样本）时，JP(a)=0，即达到极小值。确定向量a的问题变为对JP(a)求极小值的问题。36梯度下降算法梯度下降算法：对(迭代)向量沿某函数的负梯度方向修正，可较快到达该函数极小值。37算法(stepbystep)1.初值:任意给定一向量初始值a(1)2.迭代:第k+1次迭代时的权向量a(k+1)等于第k次的权向量a(k)加上被错分类的所有样本之和与rk的乘积3.终止:对所有样本正确分类任意给定一向量

初始值a(1)a(k+1)=

a(k)+rk×Sum

(被错分类的所有样本)所有样本

正确分类得到合理的a

完成

分类器设计NY38感知器方法例解固定增量法与可变增量法批量样本修正法与单样本修正法单样本修正法：样本集视为不断重复出现的序列，逐个样本检查，修正权向量批量样本修正法：样本成批或全部检查后，修正权向量39感知器方法小结感知准则函数方法的思路是：先随意找一个初始向量a(1)，然后用训练样本集中的每个样本来计算。若发现一个y出现aTy<0，则只要a(k+1)=a(k)+rky，rk为正(步长系数)，则必有a(k+1)Ty=a(k)Ty+rkyTy，就有趋势做到使a(k+1)Ty>0。当然，修改后的a(k+1)还可以使某些y出现a(k+1)Ty<0的情况，理论证明，只要训练样本集线性可分，无论a(1)的初值是什么，经过有限次叠代，都可收敛。404.4最小错分样本数准则感知准则函数及其梯度下降算法只适用于线性可分情况。对于线性不可分情况，迭代过程永远不会终结，即算法不收敛。x1X4(1,1)X2(1,0)X1(0,0)X3(0,1)x2x1X4(1,1)X2(1,0)X1(0,0)X3(0,1)x241在实际问题中往往无法事先知道样本集是否线性可分，因此，希望找到一种既适用于线性可分情况，又适用于线性不可分情况的算法。4.4最小错分样本数准则42算法应具有以下特点：对于线性可分问题，可以得到一个如感知准则函数那样的解向量a*，使得对两类样本集做到将全部样本正确分类；对于线性不可分问题，则得到一个使两类样本集错分数目最少的权向量a，记为a*。这样的算法准则称为最小错分样本数准则。4.4最小错分样本数准则43d维向量样本集{x1，x2，…，xN

},变成增广向量样本集{y1，y2，…，yN

},再通过得到规范化增广样本向量，线性判别函数可写作：4.4最小错分样本数准则44如果存在权向量a，使得下式成立则y’n被正确分类。对单个样本y’n存在线性不等式解。4.4最小错分样本数准则45设计线性分类器可以看成求一组N个线性不等式的解的问题：若不等式组有解，即不等式组存在公共解(相一致的情况)，说明样本集是线性可分的，找到这个解向量a*。若不等式组无解，即不等式组无公共解(不一致的情况)，说明样本集是线性不可分的。4.4最小错分样本数准则46在线性不可分的前提下，对于任何权向量a，必有某些样本被错分类。寻找一个满足最多数目的不等式的权向量a的问题转变成解线性不等式组的问题。4.4最小错分样本数准则474.4最小错分样本数准则48引入余量b,其维数为N,数值大于零，任何实数，使得下列等式成立。4.4最小错分样本数准则49目前已提出不少最优化这种准则的算法，这里仅介绍两种算法。两种算法：共轭梯度法和搜索法前者定义的准则为(1)式，后者定义的准则为(2)式：4.4最小错分样本数准则504.4.1共轭梯度法定义的准则为:准则的理解：如果Ya>b，则(Ya-b)和|Ya-b|同号，其结果Jq1(a)=0。如果存在某些规范化增广样本向量yi，使得yia<b，则(Ya-b)和|Ya-b|异号，其结果Jq1(a)>0。yia<b的样本向量yi个数越多，Jq1(a)越大。

Jq1(a)与

权向量a成函数关系。51

Jq1(a)与权向量a成函数关系，与它的极小值相应的权向量a则为最优解a*。4.4.1共轭梯度法524.4.1共轭梯度法534.4.2搜索法定义的准则为:Jq2(a)所表示是权向量a所满足的不等式的数目54a(0)=H1nH2I1={3,5,7}a(1)=H3nH2I2={1,5}a(2)=H3nH1a(2)=H3nH5a(1)=H5nH2I2={1,4,8}最优解：a(2)=H3nH1或a(2)=H5nH44.4.2搜索法554.5最小平方误差准则函数(MSE)感知准则函数及其梯度下降算法的缺点：只适用于线性可分情况，对于线性不可分情况，选代过程永远不会终结，即算法不收敛。在实际问题，事先无法知道样本是否线性可分，因此需要寻求更适合一般情况的算法。对于两类问题，已知N个训练样本，寻找权向量a，使得aTyi大于零，i=1,2,…,N。564.5最小平方误差准则规范化增广样本向量yi，增广权向量a，正确分类要求：aTyi>0,i=1,…,N线性分类器设计

求一组N个线性不等式的解样本集增广矩阵Y及一组N个线性不等式的的矩阵表示：引入余量(目标向量)b=[b1,b2,…,bN]T，bi任意给定正常数，aTyi=bi>0N个线性方程的的矩阵表示：5758样本数N总是大于维数(d+1)

，因此Y是长方阵。一般为列满秩阵。方程个数多于未知数，它为矛盾方程组，通常没有精确解存在。但可以寻找最小二乘解。定义一个误差向量e59平方误差准则函数定义误差向量

e=Ya-b：定义平方误差准则函数Js(a):最小二乘近似解（MSE解）：MSE方法的思想：对每个样本，设定一个“理想”的判别函数输出值，以最小平方误差为准则求最优权向量60YTY是(d+1)(d+1)方阵。存在逆矩阵。解向量a*是依赖向量b。Y的

伪逆矩阵4.5.1MSE准则函数的伪逆解61MSE方法与Fisher方法的关系与Fisher方法的关系：当N1个训练样本属于1,N2个训练样本属于2则在线性可分的情况下，MSE解与Fisher线性判别函数等价，MSE解等价于Fisher解。62MSE方法与Bayes方法的关系当N→∞，b=uN=[1,1,…,1]T时，则它以最小均方误差逼近Bayes判别函数：63计算上式伪逆存在问题：逆矩阵常常要求是非奇异的。计算量大。采用梯度下降法递归求解：批量样本修正法4.5.2MSE准则函数的梯度下降算法64样本看成无限重复的序列，即单样本修改权向量，Widrow-Hoff算法。随机MSE准则函数及其随机逼近算法---样本看成是随机样本集，权向量求解也看随机最优化问题。单样本修正法65举例利用MSE求解权向量x2x1X4(1,1)X3(1,0)X1(0,0)X2(0,1)已知模式样本为：66674.6多类问题两类别问题可以推