《模式识别-2-线性判别函数与线性分类器设计》由会员分享，可在线阅读，更多相关《模式识别-2-线性判别函数与线性分类器设计（66页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性判别函数与线性分类器设计,判别函数 线性判别函数 线性判别函数的性质 线性分类器设计 梯度下降法迭代法 感知器法 最小平方误差准则(MSE法)-非迭代法 Fisher分类准则,假设对一模式X已抽取n个特征，表示为：模式识别问题就是根据模式X的n个特征来判别模式属于1 ,2 , , m类中的那一类。, 2.1 判别函数,例如右上图：三类的分类问题，它们的边界线就是一个判别函数,用判别函数进行模式分类，取决两个因素： 判别函数的几何性质：线性与非线性 判别函数的参数确定：判别函数形式+参数 判别函数包含两类： 一类是线性判别函数： 线性判别函数：线性判别函数是统计模式识别的基本方法之一
2、，简单且容易实现 广义线性判别函数所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间（高维）变成线性判别函数 分段线性判别函数 另一类是非线性判别函数,2.2 线性判别函数,我们现在对两类问题和多类问题分别进行讨论。 一、两类问题：即: 1. 二维情况 ：取两个特征向量这种情况下 判别函数:,在两类别情况，判别函数 g (x) 具有以下性质：这是二维情况下判别由判别边界分类。 情况如图：,2. n维情况：,现抽取n个特征为：判别函数：另外一种表示方法：,模式分类：当 g1(x) =WTX=0 为判别边界。 当n=2时，二维情况的判别边界为一直线。 当n=3时，判别边界为一平面。 当n3
3、时，则判别边界为一超平面。,1.第一种情况：每一模式类与其它模式类间可用单个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：,二、对于多类问题：模式有 1 ,2 , , m 个类别，可分三种情况：,此情况可理解为 两分法。,下图所示，每一类别可用单个判别边界与其它类别相分开 。如果一模式X属于1，则由图可清楚看出：这时g1(x) 0而g2(x) 0 ， g3(x) 0 ，g2(x) 0 ，g3(x) 0 。则此模式X就无法作出确切的判决。如图中 IR1,IR3，IR4区域。 另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确 定区域。,问当
4、x=(x1,x2)T=(6,5)T时属于那一类结论： g1(x) 0 ， g3(x) g2(x) 和 g1(x) g3(x) 。 假设判别函数为：则判别边界为：,结论：不确定区间没有了，所以这种是最好情况。,用上列方程组作图如下：,问假设未知模式x= (x1,x2)T= (1,1)T ，则x属于那一类。 把它代入判别函数： 得判别函数为： 因为 所以模式x= (1,1)T属于 类。,关于线性判别函数的结论：,模式类别若可用任一线性判别函数来划分，这些模式就称为线性可分；一旦线性判别函数的参数确定，这些函数即可作为模式分类的基础。 对于M（M2）类模式分类，第一、三种情况需要M个判别函数，第两种
5、情况需要M(M-1)/2个判别函数。 对于第一种情况，每个判别函数都要把一种类别（比如i类）的模式与其余M-1种类别的模式划分开，而不是仅将一类与另一类划分开。 实际上，一个类的模式分布要比M-1类模式分布更聚集，因此后两种情况实现模式线性可分的可能性要更大一些。,2.3 广义线性判别函数,研究动机 线性判别函数简单，容易实现； 非线性判别函数复杂，不容易实现； 若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。 基本思想设一模式集x，在模式空间x中线性不可分，但在模式空间x*中线性可分，其中x*的各个分量是x的单值实函数，x*的维数k高于x的维数n，即x* = (f1(x),
6、f2(x), ., fk(x), kn则分类界面在x*空间是线性的，在x空间是非线性的，此时只要将模式x进行非线性变换，使之变换后得到维数更高的模式x*，就可用线性判别函数进行分类。,广义线性判别函数若将非线性判别函数表示为：,式中 是模式x的单值函数，若定义成广义形式：,其中， ， 且,于是，有,由此可知，非线性判别函数已变换成线性，称为广义线性判别函数。,广义线性判别函数的意义 线性的判别函数：若fi(x)=ax+b是一次函数，这相当于把x空间进行了尺度放缩和平移，并且在相同的尺度因子和位移因子上做变换，那么变换后仍然具有相似的线性特征。 fi(x)选用二次多项式函数： 对于二维情况：模式
7、空间为 ，原判别函数为：可线性化为：其中,对于n维情况，则有,式中各项的组成包括x各个分量的二次项、一次项和wn+1项，其总项数为,显然， x*的维数比x高，w分量的数目亦与x*的维数相同。 x*的各分量的一般式为,fi(x)为r次多项式函数， x是n维的情况，则,于是，判别函数g(x)可按如下递推：,讨论： (1) g(x)的总项数为：显然，Nw随r和n的增加会迅速增大，即使原来模式x的维数不高，若采用次数r较高的多项式来变换，也会使变换后的模式x*的维数很高，给分类带来很大困难（称为维数灾难）。实际上，一般r只取2。 (2)采用二次多项式函数fi(x)的判别函数也可用矩阵形式表示：式中，A
8、为实对称矩阵。判别界面的几何形状由矩阵A决定：若A=I，则判别函数为超球面；若A为正定，则判别函数为超椭球面，轴方向为A的本征向量方向；A为半正定，判别函数为超椭圆柱面；A为不定，判别函数为超双曲面体。,2.3 线性判别函数的性质,一、模式空间与加权空间： 模式空间：由 构成的n维欧氏空间。 W是此空间的加权向量，它决定模式的分界面H，W与H正交。 加权空间：以 为变量构成的欧氏空间 模式空间与加权空间的几何表示如下图：,该式表示一个通过加权空间原点的平面，比如同样令g (x2) =g (x3) =g (x4)=0，可分别作出通过加权空间原点的其他平面。,加权空间构造为： 设 是加权空间分界面
9、上的一点，代入上式得：,这是一个不等式方程组，它的解 处于由1类所有模式决定的平面的正边和由2类所有模式决定的平面的负边，它的解区即为凸多面锥。 加权空间的性质：加权空间的所有分界面都通过坐标原点。,在三维空间里，令w3 = 0，则为二维权空间。如图： 给定一个模式X，就决定一条直线： 即分界面H，W与H正交，W称为解向量。 解向量的变动范围称为解区。 因x1,x21， x3,x42由图可见x1,x3离的最近，所以分界面H可以是x1,x3之间的任一直线，由垂直于这些直线的W就构成解区，解区为一扇形平面，即阴影区域。 如右图:,二、解向量和解区,把不等式方程正规化：,正规化：,样本的正规化，令：
10、,由此可见，可以不管样本原来的类别标识，只要找到一个对全部样本 都满足 的权向量即可， 叫做正规化增广样本向量。,g(x)=WTX=0决定一个决策界面，当g(x)为线性时，该决策界面便是一个超平面H，并有以下性质： 性质：W与H正交（如图所示） 假设x1,x2是H上的两个向量 所以 W 与(x1-x2) 垂直，即W与H正交。一般说，超平面H把特征空间分成两个半空间。即1,2空间，当x在1空间时g(x)0,W指向1，为H的正侧，反之为H的负侧。,三、超平面的几何性质,矢量到H的正交投影 与 值成正比,其中： x p是x在H 的投影向量， r是x 到H 的垂直距离。是W方向的单位向量。,性质 ：,
11、另一方面:,这是超平面的第二个性质，矢量x到超平面的正交投影 正比与g(x)的函数值。,性质：,性质：,2.4 线性分类器的设计,上面我们讨论了线性判别函数形式为:g(x)=WTX其中 X= (X1, X2Xn) n维特征向量W= (W1, W2 Wn , Wn+1) n维权向量通常通过特征抽取可以获得n维特征向量，因此n维权向量是要按某种准则（准则函数）求解的。 求解权向量的过程就是分类器的训练过程，使用已知类别的有限学习样本来获得分类器的权向量被称为有监督的分类。,设计线性分类器的主要步骤： (1)收集一组具有类别标识的样本 。若把每个样本看成确定的观测值，则这组样本称为确定性样本集；若把
12、每个样本看成随机变量，则这组样本称为随机样本集。 (2)根据实际情况确定一个准则函数J。J必须满足：a) J是样本集X和 、 的函数；b) J的值反映分类器的性能，其极值解对应于“最好”的决策。 (3)用最优化技术求出准则函数的极值解 。,权向量的训练过程：利用已知类别学习样本来获得权向量的训练过程如下：,已知x1 1, 通过检测调整权向量，最终使x1 1 已知x2 2, 通过检测调整权向量，最终使x2 2 这样就可以通过有限的样本去决定权向量。,0 x1,0 x2,利用方程组来求解权向量 对二类判别函数g(x) = W1X1+ W2X2 +W3 已知训练集：Xa, Xb, Xc, Xd且当 (Xa, Xb) W1时 g(x)0当 (Xc, Xd) W2时 g(x)0 设 Xa = (X1a, X2a)T Xb = (X1b, X2b)TXc = (X1c, X2c)T Xd = (X1d, X2d)T 判别函数可联立成：X1aW1+ X2aW2+ W30 X1bW1+ X2bW2+ W30 X1cW1+ X2cW2+ W30 X1dW1+ X2dW2+ W30 求出W1 , W2, W3,
