模式识别(4-2).ppt

《模式识别(4-2).ppt》由会员分享，可在线阅读，更多相关《模式识别(4-2).ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 模式识别模式识别 第四章线性判别函数（第四章线性判别函数（2）回顾：回顾： Fisher准则的基本原理，就是要找到一个最合适的准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。从而使分类效果为最佳。12( )TbbFTwSw S wJww S wSS*112()wwSmm4.3 4.3 感知准则函数感知准则函数n感知准则函数是五十年代由感知准则函数是五十年代由Rosenblatt提出的一种提出的一种生成方法，由于生成方法，由于Rosenblatt企图将其用于脑模型企图将其用于脑模型感知器，因

2、此被称为感知器，因此被称为。其特点是。其特点是。几个基本概念几个基本概念设样本设样本d维特征空间中描述，则两类别问题中线性判别函数的一维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成：般形式可表示成：其中其中作特殊映射作特殊映射( )T0g x = w x+w12dxxxx111dxyxx 011dwwaww 几个基本概念几个基本概念 反过来说，如果存在一个权向量反过来说，如果存在一个权向量 ，使得对于任何，使得对于任何 都有都有 ，而对任何，而对任何 ，都有，都有 ，则称这，则称这组样本集为组样本集为线性可分的线性可分的；否则称；否则称样本集样本集为为。a1y0yaT2y0ya

3、T( )TT0g xw x+w = a y线性判别函数线性判别函数g(x)可以表示成：可以表示成：在在两类别情况两类别情况下，判别准则是：下，判别准则是：120g00Txxa yx , 则决策( )=0b0，并寻找满足，并寻找满足 的解向量的解向量 ，显然满，显然满足足 ， 位于原解区之中。位于原解区之中。*a0iTya*abyaiT*a0byaiT*a几个基本概念几个基本概念感知准则函数感知准则函数0Tia y 0,1,2,Tia yiN)(aJp方法是一种方法是一种利用错分类对现决策权向量进行利用错分类对现决策权向量进行修正直至收敛的方法修正直至收敛的方法。这种方法只对。这种方法只对线性可

4、分线性可分情况情况适用。适用。 在给定一个规范化增广样本集在给定一个规范化增广样本集 的条件下，对的条件下，对于任何一个增广权向量于任何一个增广权向量 ，可以计算，可以计算 。 如果该向量是一个能将此样本集正确分类的增广权向量，如果该向量是一个能将此样本集正确分类的增广权向量，则应有则应有 而对可导致错分类的增广权向量，则必有若干个而对可导致错分类的增广权向量，则必有若干个yi , ,使使 ，令被错分类的规范化增广样本组成的集合用，令被错分类的规范化增广样本组成的集合用yk k表表示，错分时示，错分时 ，所以定义一，所以定义一 0Tia yNyyy,21ayaT感知准则函数感知准则函数a( )

5、0PJa 感知准则函数：感知准则函数： 能将该样本集正确分类的增广权向量能将该样本集正确分类的增广权向量 ，使，使 即达到即达到 极小值。因此确定向量的问题变为对极小值。因此确定向量的问题变为对 求求极小值的问题，这个准则函数就是极小值的问题，这个准则函数就是。 求求准则函数的极小值准则函数的极小值问题，可以采用问题，可以采用进行。一个常进行。一个常用的方法是用的方法是，即对第，即对第k k次迭代值，求其梯度次迭代值，求其梯度向量，并令迭代向量沿此负梯度向量方向修正，可以以较向量，并令迭代向量沿此负梯度向量方向修正，可以以较快的速度到达准则函数的极小值。快的速度到达准则函数的极小值。)(aJ)

6、(aJ( )()kTPy yJaa y梯度下降算法梯度下降算法( )()( )(1)( )( )(1)( )kkkkkka ka kJaJ aaJ aJ aJaka kJaJ函数在某点 的梯度是一个向量，其方向是增长最快的方向。其反方向是减少最快的方向。极大点：沿梯度方向走极小点：沿负梯度方向走为步长。梯度下降算法求增广权向量梯度下降算法求增广权向量(1)a k (1)ak 感知准则函数利用梯度下降算法求增广权向量的做法，可简感知准则函数利用梯度下降算法求增广权向量的做法，可简单叙述为：单叙述为： 任意给定一向量初始值任意给定一向量初始值 ，第，第k+1次迭代时的次迭代时的权向量权向量 等于第

7、等于第k次的权向量加上被次的权向量加上被 错分类的所错分类的所有样本之和与有样本之和与 的乘积。的乘积。 ( )( )()kPPy yJaJaya梯度下降算法的迭代公式为：梯度下降算法的迭代公式为：( )a k(1)( )(1)( )kkky ya ka kJa ka ky梯度下降算法求增广权向量梯度下降算法求增广权向量yk+-迭代修正过程：迭代修正过程： 由于所有被由于所有被a(k)错分类的样错分类的样本必然都在以本必然都在以a(k)为法线的超为法线的超平面的负侧，因而它们的总和平面的负侧，因而它们的总和也必然处于该侧。也必然处于该侧。a(k+1)修正时，就会使修正时，就会使a(k+1)向错

8、分类向量和趋近，有可能向错分类向量和趋近，有可能使这些错分类向量之和穿过超使这些错分类向量之和穿过超平面，或至少朝有利方向变动。平面，或至少朝有利方向变动。 例：有两类样本 1=（x1,x2）=(1,0,1) T,(0,1,1) T 2=（x3,x4）=(1,1,0) T,(0,1,0) T试用感知准则函数法求判别函数？解：先求四个样本的规范化增广样本向量 y1=(1,0,1,1) T y2=(0,1,1,1) T y3= - (1,1,0,1) T y4= - (0,1,0,1) T假设初始权向量 a1=(1,1,1,1)T k=1第一次迭代： a1Ty1=(1,1,1,1) (1,0,1,

9、1)T=30 所以不修正a1Ty2=(1,1,1,1) (0,1,1,1)T=30 所以不修正a1Ty3= - (1,1,1,1) (1,1,0,1)T=-30 所以修正a1a2=a1+y3=(0,0,1,0)Ta2Ty4= - (0,0,1,0)T (0,1,0,1) =0 所以修正a2a3=a2+y4=(0,-1,1,-1)T第一次迭代后,权向量a3=(0,-1,1,-1),再进行第2,3,次迭代如下表.训练样本训练样本akTy修正式修正式修正后的权值修正后的权值ak1迭代次数迭代次数y1 1 0 1 1y2 0 1 1 1y3 -(1 1 0 1)y4 -(0 1 0 1)+-0a1a1

10、a1+y3a2+y41 1 1 11 1 1 10 0 1 00 1 1 -1 1y1 1 0 1 1y2 0 1 1 1y3(1 1 0 1)y4-(0 1 0 1)0+0+a3+y1a4a4+y3a51 1 2 01 1 2 00 2 2 10 2 2 -1 2y1 1 0 1 1y2 0 1 1 1y3-(1 1 0 1)y4-(0 1 0 1)+-+a5a5+y2a6a60 2 2 10 1 3 00 1 3 00 1 3 0 3y1 1 0 1 1y2 0 1 1 1y3-(1 1 0 1)y4-(0 1 0 1)+a6a6a6a60 1 3 00 1 3 00 1 3 00 1 3

11、 04直到在一个迭代过程中权向量相同，训练结束。 a=a6=(0,1,3,0)T 判别函数g(x)= aTy=-y2+3y3n感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.本节总结本节总结这一节对感知准则函数的讨论，只是很初步的，并且只这一节对感知准则函数的讨论，只是很初步的，并且只讨论了线性可分的情况。讨论了线性可分的情况。但这种利用错误提供的信息，进行自修正的思想意义是但这种利用错误提供的信息，进行自修正的思想意义是十分深远的。这种只解决线性分类的感知器称为单层感十分深远的。这种只解决线性分类的感知器称为单层感知器。知器。由单层感知机基础上发展

12、起来的多层感知器在原理上能由单层感知机基础上发展起来的多层感知器在原理上能解决非线性分类、多类划分，以及非线性拟和非线性映解决非线性分类、多类划分，以及非线性拟和非线性映射等多种功能。射等多种功能。 n例：有两类样本n 1=（x1,x2）=(0,0,0) T,(1,0,0) Tn 2=（x3,x4）=(0,0,1) T,(0,1,1) Tn试用感知准则函数法求判别函数？4.4 4.4 多类问题多类问题 实际问题中常遇到的是多类别问题。在两类别问实际问题中常遇到的是多类别问题。在两类别问题中使用的线性判别函数方法可以推广到多类别题中使用的线性判别函数方法可以推广到多类别问题中，但可有不同做法。一

13、种最简单作法是将问题中，但可有不同做法。一种最简单作法是将C类别问题化为类别问题化为(C-1)个两类问题，即将第个两类问题，即将第i类与所类与所有非有非i类样本，按两类问题确定其判别函数与决策类样本，按两类问题确定其判别函数与决策面方程。面方程。 4.4 4.4 多类问题多类问题n对于对于C类，则总共有类，则总共有(C-1)个两类别问题。这种做法存在两个两类别问题。这种做法存在两个问题：个问题：n一是可能会出现一些不定区域，如图中绿色阴影所示，在一是可能会出现一些不定区域，如图中绿色阴影所示，在这些区域中的样本无法确定其类别。这些区域中的样本无法确定其类别。n另一方面用线性判别函数对另一方面用

14、线性判别函数对i类类及所有非及所有非i类进行划分并不能保类进行划分并不能保证获得性能良好的划分，硬性证获得性能良好的划分，硬性使用线性分类器可能会产生很使用线性分类器可能会产生很不好的效果。不好的效果。4.4 4.4 多类问题多类问题另一种相对麻烦些的做法是将另一种相对麻烦些的做法是将C C类中的每两类别单独设计其类中的每两类别单独设计其线性判别函数，因此总共有线性判别函数，因此总共有C(C-1)/2C(C-1)/2个线性判别函数。个线性判别函数。这种方法由于每个判别函数这种方法由于每个判别函数针对每两类别样本设计，预针对每两类别样本设计，预期可有好效果，但仍有不定期可有好效果，但仍有不定区域

15、，在该区域内样本类别区域，在该区域内样本类别无法确定。无法确定。4.4 4.4 多类问题多类问题( )max( ),1,2,ijijg xgxjcx ,则 因此一个比较合适的作法是将特征空间确实划分为因此一个比较合适的作法是将特征空间确实划分为C C个决策个决策域，共有域，共有C C个判别函数个判别函数 每个决策域每个决策域 R Ri 按以下规则划分按以下规则划分 如果如果 因此落在因此落在R Ri区域内的样本被划分成区域内的样本被划分成i类，如果发生类，如果发生g gi( (x) )g gj( (x) )，即处于决策域的边界上，则作出拒绝决策。这种分，即处于决策域的边界上，则作出拒绝决策。这

16、种分类器被称为类器被称为线性机器线性机器。0( ),1,.,Tiiig xw xwic4.4 4.4 多类问题多类问题)()(xgxgji0)()(00jiTjiwwxww线性机器中决策域的边界由相邻决策域的线性机器中决策域的边界由相邻决策域的判别函数共同决定，此时应有判别函数共同决定，此时应有4.4 4.4 多类问题多类问题 在线性机器中最多有在线性机器中最多有C(C-1)/2个超平面，但实际的超平面数个超平面，但实际的超平面数目往往要少很多。左图是一个二维特征空间三类别线性机器目往往要少很多。左图是一个二维特征空间三类别线性机器的示意图，的示意图，右图右图则是一个五类别情况，但其分界面的数量远则是一个五类别情况，但其分界面的数量远比比C(C-1)/2要小得多。要小得多。 4.5 4.5 本章小结本章小结n线性判别函数的基本概念线性判别函数的基本概念n多类问题多类问题