《模式识别（4-2）线性判别函数》由会员分享，可在线阅读，更多相关《模式识别（4-2）线性判别函数（30页珍藏版）》请在金锄头文库上搜索。
1、,模式识别 第四章线性判别函数（2）,回顾：,Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。,4.3 感知准则函数,感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。,几个基本概念,设样本d维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成：,其中,作特殊映射,1. 线性可分性,几个基本概念,反过来说，如果存在一个权向量 ，使得对于任
2、何都有 ，而对任何 ，都有 ，则称这组样本集为线性可分的；否则称样本集为线性不可分的。,线性判别函数g(x)可以表示成：,在两类别情况下，判别准则是：,几个基本概念,2.样本的规范化 根据上面线性可分的定义，如果样本集 是线性可分的，则必存在某个或某些权向量 ，使得 如果将第二类样本都取其反向向量，则有,几个基本概念,也就是说不管样本原来的类别标识，只要找到一个对全部样本都满足 的权向量 就行了。,上述过程称为样本的规范化， 叫做规范化增广样本向量。在后面我们仍用y来表示。,几个基本概念,3.解向量和解区 在线性可分的情况下，满足 ， i=1,2,N的权向量称为解向量，记为 。 由满足上述条件
3、的解向量组成的区域，就称作解区。 一般来说，对解区要加以限制，目的是使解向量 更可靠，越靠近解区中间的解向量，越能对新的样本正确分类。 引入余量b0，并寻找满足 的解向量 ，显然满足 ， 位于原解区之中。,几个基本概念,几个基本概念,感知准则函数,感知准则函数方法是一种利用错分类对现决策权向量进行修正直至收敛的方法。这种方法只对线性可分情况适用。 在给定一个规范化增广样本集 的条件下，对于任何一个增广权向量 ，可以计算 。 如果该向量是一个能将此样本集正确分类的增广权向量，则应有 而对可导致错分类的增广权向量，则必有若干个yi ,使 ，令被错分类的规范化增广样本组成的集合用yk表示，错分时 ，
4、所以定义一准则函数,感知准则函数,感知准则函数： 能将该样本集正确分类的增广权向量 ，使即达到 极小值。因此确定向量的问题变为对 求极小值的问题，这个准则函数就是感知准则函数。求准则函数的极小值问题，可以采用迭代法进行。一个常用的方法是梯度下降算法，即对第k次迭代值，求其梯度向量，并令迭代向量沿此负梯度向量方向修正，可以以较快的速度到达准则函数的极小值。,梯度下降算法,梯度下降算法求增广权向量,感知准则函数利用梯度下降算法求增广权向量的做法，可简单叙述为： 任意给定一向量初始值 ，第k+1次迭代时的权向量 等于第k次的权向量加上被 错分类的所有样本之和与 的乘积。,梯度下降算法的迭代公式为：,
5、梯度下降算法求增广权向量,迭代修正过程：,由于所有被a(k)错分类的样本必然都在以a(k)为法线的超平面的负侧，因而它们的总和也必然处于该侧。a(k+1)修正时，就会使a(k+1)向错分类向量和趋近，有可能使这些错分类向量之和穿过超平面，或至少朝有利方向变动。,梯度下降算法求增广权向量,设a(1)=0，k=1。则a(2)y1 ， 则y3将在a(2)y1时被错分类，故a(3)y1+y3 ；然而紧接着的y3又被 a(3)错分类，故权向量值又一次修正，迭代下去直至该解向量进入解区内。,我们反复地将y1到y3依次送到分类器检验，并在发生错分类时对向量a(k)作出修正。,例：有两类样本1=（x1,x2）
6、=(1,0,1) T,(0,1,1) T2=（x3,x4）=(1,1,0) T,(0,1,0) T 试用感知准则函数法求判别函数？,解：先求四个样本的规范化增广样本向量y1=(1,0,1,1) T y2=(0,1,1,1) Ty3= - (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,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 所以修正a1 a2=a1+
7、y3=(0,0,1,0)Ta2Ty4= - (0,0,1,0)T (0,1,0,1) =0 所以修正a2 a3=a2+y4=(0,-1,1,-1)T第一次迭代后,权向量a3=(0,-1,1,-1),再进行第2,3,次迭代 如下表.,直到在一个迭代过程中权向量相同，训练结束。a=a6=(0,1,3,0)T 判别函数g(x)= aTy=-y2+3y3感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.,本节总结,这一节对感知准则函数的讨论，只是很初步的，并且只讨论了线性可分的情况。但这种利用错误提供的信息，进行自修正的思想意义是十分深远的。这种只解决线性分类
8、的感知器称为单层感知器。由单层感知机基础上发展起来的多层感知器在原理上能解决非线性分类、多类划分，以及非线性拟和非线性映射等多种功能，这些将在人工神经元网络这一章中进一步讨论。,4.4 多类问题,实际问题中常遇到的是多类别问题。在两类别问题中使用的线性判别函数方法可以推广到多类别问题中，但可有不同做法。一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第i类与所有非i类样本，按两类问题确定其判别函数与决策面方程。,4.4 多类问题,对于C类，则总共有(C-1)个两类别问题。这种做法存在两个问题：一是可能会出现一些不定区域，如图中绿色阴影所示，在这些区域中的样本无法确定其类别。另一方面用
9、线性判别函数对i类 及所有非i类进行划分并不能保 证获得性能良好的划分，硬性 使用线性分类器可能会产生很 不好的效果。,4.4 多类问题,另一种相对麻烦些的做法是将C类中的每两类别单独设计其线性判别函数，因此总共有C(C-1)/2个线性判别函数。这种方法由于每个判别函数 针对每两类别样本设计，预 期可有好效果，但仍有不定 区域，在该区域内样本类别 无法确定。,4.4 多类问题,因此一个比较合适的作法是将特征空间确实划分为C个决策域，共有C个判别函数 每个决策域 Ri 按以下规则划分 如果 因此落在Ri区域内的样本被划分成i类，如果发生gi(x)gj(x)，即处于决策域的边界上，则作出拒绝决策。这种分类器被称为线性机器。,4.4 多类问题,线性机器中决策域的边界由相邻决策域的判别函数共同决定，此时应有,4.4 多类问题,在线性机器中最多有C(C-1)/2个超平面，但实际的超平面数目往往要少很多。左图是一个二维特征空间三类别线性机器的示意图，右图则是一个五类别情况，但其分界面的数量远比C(C-1)/2要小得多。,4.5 本章小结,线性判别函数的基本概念 Fisher线性判别 感知准则函数 多类问题,练习：,设有两类样本：,；,试用感知机算法设计分类器。以,为正样本，增广权向量初值取为,按照上述样本顺序给出迭代过程。,类样本,
