模式识别第4章课件.ppt

1、第四章 线性判别函数2010.11第四章 线性判别函数4.1引言4.2 Fisher线性判别4.3 感知准则函数4.4 最小错分样本数准则4.5 最小平方误差准则函数4.6 随机最小错误率线性判别准则函数4.7 多类问题引言v设计贝叶斯分类器的方法：即已知先验概率P(i)和类条件概率密度p(x/i)的情况下，按一定的决策规则确定判别函数和决策面。v类条件概率密度的形式常常难以确定，利用非参数估计分布需要大量样本，且所需样本数随维数升高急剧增加。v线性判别函数法线性判别函数v我们现在对两类问题和多类问题分别进行讨论。v(一)两类问题 即:v v1.二维情况：取两个特征向量v 这种情况下 判别函数

2、:2,),(21MTi2,)(2,1nxxXT32211wxwxw)x(g为坐标向量为参数，21,xxwv在两类别情况，判别函数 g(x)具有以下性质：v这是二维情况下判别由判别边界分类.v情况如图：1.二维情况21,0,0)(XXxgi不定Xxg,0)(32211)(wxwxwxg211x2x2.n维情况v现抽取n个特征为：v判别函数：v另外一种表示方法：TnxxxxX),.,(32112211.)(nnnwxwxwxwxg10nTwXW12112(,.,)(,.,1)TnnTnWw ww wXx xx为增值权向量，为增值模式向量。XWxgT)(为模式向量。为权向量，TnTnxxxXwwwW

3、),.,(),.,(21210v模式分类：v当 g1(x)=WTX=0 为判别边界。当n=2时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面，n3时，则判别边界为一超平面。21,0,0)(xxXWxgT2.n维情况(二)多类问题0,()0,1,2,.,iTiiXg xW XiC其它。v对于多类问题，模式有 1,2,c 个类别。可分三种情况：1。第一种情况：第一种情况：每一模式类与其它模式类间可用单每一模式类与其它模式类间可用单个判别平面把一个类分开个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：权向量。个判别函数的为第式中iwwwwWTininiii),.,

4、(121v每一类别可用单个判别边界与其它类别相分开。v如果一模式X属于1，则由图可清楚看出:这时g1(x)0而g2(x)0，g3(x)0，g2(x)0，g3(x)0。则此模式X就无法作出确切的判决。如图中 IR1,IR3，IR4区域。v另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确 定区域。1 1。第一种情况（续）第一种情况（续）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551v问当x=(x1,x2)T=(6,5)T时

5、属于那一类v结论：g1(x)0，g3(x)g2(x)和 g1(x)g3(x)。v假设判别函数为：v则判别边界为：23212211)(1)()(xxgxxxgxxxg012)()(02)()(012)()(21322131121xxxgxgxxxgxgxxgxg2)()(21xgxg)()(32xgxg)()(31xgxg133。第三种情况（续）v结论：不确定区间没有了，所以这种是最好情况。v用上列方程组作图如下：3。第三种情况（续）1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21x

6、gxg0)()(31xgxg0.15.05.0v问假设未知模式x=(x1,x2)T=(1,1)T，则x属于那一类。v把它代入判别函数：v得判别函数为：v因为v所以模式x=(1,1)T属于 类。3。第三种情况（续）2)()(),()(1232xgxgxgxg1)(,1)(,0)(321xgxgxg).(),(),(321xgxgxg1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0广义线性判别函数kixfwwxfwxfwxfwxgkiii

7、kkk,.,2,1,)()(.)()()(1112211v这样一个非线性判别函数通过映射，变换成线性判别函数。1)(,)(1xfxfki是单值函数式中v判别函数的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空间变换空间0YWT判别平面：11121122110,()()()0,()(),(),().()kxyTiiikkxg xw f xW Yg Yxwf xwfxWYwfx空间变换空间其中：广义权向量。增广模式向量广义线性判别函数（续）21,xaxbxbxorax则则v例：如右图。0bax二次判别函数2122321212123211,0,0)()(,0,0)(xx

8、YaaaWxxYgYWxgxxxaxaaxgT映射：广义线性判别函数（续）v要用二次判别函数才可把二类分开：)1,1,1()25.0,5.0,1(),0,0,1(321yyy05.011y3y2yW平面oYWT212x015.012)(1,2112,1,12123212321321YWYxxxxxgyyyxxYaaaWaaaxT空间判别平面：即：空间它的判别边界：设讨论在推出广义线性判别函数（续）v从图可以看出：在阴影上面是1类，在阴影下面是2类，v结论：在X空间的非线性判别函数通过变换到Y空间成为线性的，但X变为高维空间05.011y3y2yW平面oYWT212xFisher线性判别v出发点

9、 应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题。在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。因此，降低维数有时就会成为处理实际问题的关键。Fisher线性判别v问题描述 考虑把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。Fisher线性判别v问题描述 问题：如何根据实际情况找到一条最好的、最易于分类的投影线，这就是Fisher判

10、别方法所要解决的基本问题。Fisher线性判别v从d维空间到一维空间的一般数学变换方法 假设有一集合包含N个d维样本x1,x2,xN，其中N1个属于1类的样本记为子集1，N2个属于2类的样本记为子集2。若对xn的分量做线性组合可得标量：yn=wTxn,n=1,2,N 这样便得到N个一维样本yn组成的集合，并可分为两个子集1和2。Fisher线性判别v从d维空间到一维空间的一般数学变换方法 实际上，w的值是无关紧要的，它仅是yn乘上一个比例因子，重要的是选择w的方向。w的方向不同，将使样本投影后的可分离程度不同，从而直接影响的分类效果。因此，上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换

11、向量w*的问题。Fisher线性判别Fisher线性判别我们希望投影后，在一维我们希望投影后，在一维Y空间中各类样本尽可能分空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即希望类内离散度越小越好。类样本内部尽量密集，即希望类内离散度越小越好。Fisher线性判别Fisher线性判别v基于最佳变换向量w*的投影 w*是使Fisher准则函数JF(w)取极大值时的解，也就是d维X空间到一维Y空间的最佳投影方向。有了w*，就可以把d维样本x投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向w*

12、相对于Fisher准则函数JF(w)是最好的。利用Fisher准则，就可以将d维分类问题转化为一维分类问题，然后，只要确定一个阈值T，将投影点yn与T相比较，即可进行分类判别。感知器算法v出发点 一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。感知器算法v基本思想 采用感知器算法(Perception Approach)能通过对训练模式样本集的“学习”得到判别函数的系数v说明 这里采用的算法不需要

13、对各类别中模式的统计性质做任何假设，因此称为确定性的方法。感知器算法v感知器的训练算法感知器的训练算法v感知器算法实质上是一种赏罚过程 对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。对错误分类的模式则“罚”，使w(k)加上一个正比于Xk的分量。当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。感知器算法v感知器算法的收敛性只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。采用感知器算法的多类模式的分类v采用多类情况3，将感知器算法推广到多类模式。v

14、感知器算法判别函数的推导感知器算法判别函数的推导采用感知器算法的多类模式的分类v讨论 这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。采用感知器算法的多类模式的分类v讨论 要获得一个判别性能好的线性分类器，究竟需要多少训练样本？直观上是越多越好，但实际上能收集到的样本数目会受到客观条件的限制；过多的训练样本在训练阶段会使计算机需要较长的运算时间；一般来说，合适的样本数目可如下估计：若k是模式的维数，令C=2(k+1)，则通常选用的训练样本数目约为C的1020倍。v讨论 若正确地选择了准则函数J(w,x)，则当权向量w是一个解时，J达到极小值（J的梯度为零）。由于权向量是按J的梯度值减小，因此这种方法称为梯度法（最速下降法）。为了使权向量能较快地收敛于一个使函数J极小的解，C值的选择是很重要的。若C值太小，则收敛太慢；若C值太大，则搜索可能过头，引起发散。梯度算法