模式识别(4-2).ppt

模式识别  第四章线性判别函数（2） 回顾： Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。 §4.3 感知准则函数 感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。 几个基本概念 几个基本概念 几个基本概念 几个基本概念 几个基本概念 几个基本概念 感知准则函数 感知准则函数 梯度下降算法 梯度下降算法求增广权向量 梯度下降算法求增广权向量 例：有两类样本 ω1=（x1,x2）={(1,0,1) T,(0,1,1) T} ω2=（x3,x4）={(1,1,0) T,(0,1,0) T} 试用感知准则函数法求判别函数？ 本节总结 例：有两类样本 ω1=（x1,x2）={(0,0,0) T,(1,0,0) T} ω2=（x3,x4）={(0,0,1) T,(0,1,1) T} 试用感知准则函数法求判别函数？ §4.4 多类问题 实际问题中常遇到的是多类别问题。在两类别问题中使用的线性判别函数方法可以推广到多类别问题中，但可有不同做法。一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第i类与所有非i类样本，按两类问题确定其判别函数与决策面方程。 §4.4 多类问题 对于C类，则总共有(C-1)个两类别问题。这种做法存在两个问题： 一是可能会出现一些不定区域，如图中绿色阴影所示，在这些区域中的样本无法确定其类别。 另一方面用线性判别函数对i类及所有非i类进行划分并不能保证获得性能良好的划分，硬性使用线性分类器可能会产生很不好的效果。 §4.4 多类问题 §4.4 多类问题 §4.4 多类问题 §4.4 多类问题 §4.5 本章小结 线性判别函数的基本概念 Fisher线性判别 感知准则函数 多类问题 * * * 设样本d维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成： 其中 作特殊映射 1. 线性可分性 反过来说，如果存在一个权向量 ，使得对于任何 都有 ，而对任何 ，都有 ，则称这组样本集为线性可分的；否则称样本集为线性不可分的。 线性判别函数g(x)可以表示成： 在两类别情况下，判别准则是： 2.样本的规范化 根据上面线性可分的定义，如果样本集 是线性可分的，则必存在某个或某些权向量 ，使得 如果将第二类样本都取其反向向量，则有 也就是说不管样本原来的类别标识，只要找到一个对全部样本都满足 的权向量 就行了。 上述过程称为样本的规范化， 叫做规范化增广样本向量。 在后面我们仍用y来表示。 3.解向量和解区 在线性可分的情况下，满足 ， i=1,2,…,N的权向量称为解向量，记为 。 由满足上述条件的解向量组成的区域，就称作解区。 一般来说，对解区要加以限制，目的是使解向量 更可靠，越靠近解区中间的解向量，越能对新的样本正确分类。 引入余量b0，并寻找满足 的解向量 ，显然满足 ， 位于原解区之中。 感知准则函数方法是一种利用错分类对现决策权向量进行修正直至收敛的方法。这种方法只对线性可分情况适用。 在给定一个规范化增广样本集 的条件下，对于任何一个增广权向量 ，可以计算 。 如果该向量是一个能将此样本集正确分类的增广权向量，则应有 而对可导致错分类的增广权向量，则必有若干个yi ,使 ，令被错分类的规范化增广样本组成的集合用yk表示，错分时 ，所以定义一准则函数 感知准则函数： 能将该样本集正确分类的增广权向量 ，使 即达到 极小值。因此确定向量的问题变为对 求极小值的问题，这个准则函数就是感知准则函数。 求准则函数的极小值问题，可以采用迭代法进行。一个常用的方法是梯度下降算法，即对第k次迭代值，求其梯度向量，并令迭代向量沿此负梯度向量方向修正，可以以较快的速度到达准则函数的极小值。 感知准则函数利用梯度下降算法求增广权向量的做法，可简单叙述为： 任意给定一向量初始值 ，第k+1次迭代时的权向量 等于第k次的权向量加上被 错分类的所