模式识别第4章课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 线性判别函数,2010.11,第四章 线性判别函数2010.11,1,第四章 线性判别函数,4.1,引言,4.2 Fisher,线性判别,4.3,感知准则函数,4.4,最小错分样本数准则,4.5,最小平方误差准则函数,4.6,随机最小错误率线性判别准则函数,4.7,多类问题,第四章 线性判别函数4.1引言,引言,设计贝叶斯分类器的方法：即已知先验概率,P(,i,)和类条件概率密度,p(x/,i,)的情况下，按一定的决策规则确定判别函数和决策面。,类条件概率密度的形式常常难以确定，利用非参数估计分布需要大量样本，且所需样本数随维数升高急剧增加。,线性判别函数法,引言设计贝叶斯分类器的方法：即已知先验概率P(i)和类条件,线性判别函数,我们现在对两类问题和多类问题分别进行讨论。,(,一,),两类问题 即:,1.二维情况：取两个特征向量,这种情况下 判别函数:,线性判别函数,在两类别情况，判别函数,g,(,x,),具有以下性质,：,这是二维情况下判别由判别边界分类.,情况如图：,1.二维情况,在两类别情况，判别函数 g(x)具有以下性质：1.二,2.n,维情况,现抽取,n,个特征为：,判别函数：,另外一种表示方法：,2.n维情况现抽取n个特征为：,模式分类：,当,g,1,(,x,),=,W,T,X,=,0,为判别边界。当,n,=2,时，二维情况的判别边界为一直线。当,n,=3,时，判别边界为一平面，,n,3,时，则判别边界为一超平面。,2.n,维情况,模式分类：2.n维情况,(,二),多类问题,对于多类问题，模式有,1,2,c,个类别。可分三种情况：,1。,第一种情况：,每一模式类与其它模式类间可用单个判别平面把一个类分开,。,这种情况，,M,类可有,M,个判别函数，且具有以下性质：,(二)多类问题对于多类问题，模式有 1,2,每一类别可用单个判别边界与其它类别相分开。,如果一模式,X,属于,1,，,则由图可清楚看出:这时,g,1,(,x,),0,而,g,2,(,x,),0,，,g,3,(,x,),0，,g,2,(,x,),0，,g,3,(,x,),0，g2(x)0,。则此模式,X,就无法作出确切的判决。如图中,IR1,IR3，IR4,区域。,另一种情况是,IR2,区域，判别函数都为负值。,IR1,，,IR2,，,IR3，IR4。,都为不确 定区域。,1。,第一种情况（续）,必须指出，如果某个X使二个以上的判别函数 gi(x)0,问当,x,=(,x,1,x,2,),T,=(6,5),T,时属于那一类,结论：,g,1,(,x,),0，,g,3,(,x,),g,2,(,x,),和,g,1,(,x,),g,3,(,x,),。,假设判别函数为：,则判别边界为：,3。第三种情况（续）,右图所示是M=3 的例子。对于1类模式，3。第三种情况（续,结论：不确定区间没有了，所以这种是最好情况。,用上列方程组作图如下：,3。第三种情况（续）,结论：不确定区间没有了，所以这种是最好情况。用上列方程组作图,问假设未知模式,x,=,(,x,1,x,2,),T=,(1,1),T,，,则,x,属于那一类。,把它代入判别函数：,得判别函数为：,因为,所以模式,x,=(1,1),T,属于 类。,3。第三种情况（续）,问假设未知模式x=(x1,x2)T=(1,1)T，则x,广义线性判别函数,这样一个非线性判别函数通过映射，变换成线性判别函数。,判别函数的一般形式：,广义线性判别函数这样一个非线性判别函数通过映射，变换成线性判,广义线性判别函数（续）,例：如右图。,广义线性判别函数（续）例：如右图。,广义线性判别函数（续）,要用二次判别函数才可把二类分开：,2,1,2,广义线性判别函数（续）要用二次判别函数才可把二类分开：2,广义线性判别函数（续）,从图可以看出：在阴影上面是,1,类，,在阴影下面是,2,类，,结论：在,X,空间的非线性判别函数通过变换到,Y,空间成为线性的，但,X,变为高维空间,2,1,2,广义线性判别函数（续）从图可以看出：在阴影上面是1类，在阴,Fisher,线性判别,出发点,应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题。,在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。,因此，降低维数有时就会成为处理实际问题的关键。,Fisher线性判别出发点,Fisher,线性判别,问题描述,考虑把,d,维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。,然而，即使样本在,d,维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。,但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。,Fisher线性判别问题描述,Fisher,线性判别,问题描述,问题：如何根据实际情况找到一条最好的、最易于分类的投影线，这就是,Fisher,判别方法所要解决的基本问题。,Fisher线性判别问题描述,Fisher,线性判别,从,d,维空间到一维空间的一般数学变换方法,假设有一集合,包含,N,个,d,维样本,x,1,x,2,x,N,，其中,N,1,个属于,1,类的样本记为子集,1,，,N,2,个属于,2,类的样本记为子集,2,。若对,x,n,的分量做线性组合可得标量：,y,n,=,w,T,x,n,n=1,2,N,这样便得到,N,个一维样本,y,n,组成的集合，并可分为两个子集,1,和,2,。,Fisher线性判别从d维空间到一维空间的一般数学变换方法,Fisher,线性判别,从,d,维空间到一维空间的一般数学变换方法,实际上，,w,的值是无关紧要的，它仅是,y,n,乘上一个比例因子，重要的是选择,w,的方向。,w,的方向不同，将使样本投影后的可分离程度不同，从而直接影响的分类效果。,因此，上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换向量,w*,的问题。,Fisher线性判别从d维空间到一维空间的一般数学变换方法,Fisher,线性判别,Fisher线性判别,Fisher,线性判别,我们希望投影后，在一维,Y,空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即希望类内离散度越小越好。,Fisher线性判别我们希望投影后，在一维Y空间中各类样本尽,Fisher,线性判别,Fisher线性判别,模式识别第4章课件,模式识别第4章课件,模式识别第4章课件,Fisher,线性判别,基于最佳变换向量,w*,的投影,w*,是使,Fisher,准则函数,JF(w),取极大值时的解，也就是,d,维,X,空间到一维,Y,空间的最佳投影方向。有了,w*,，就可以把,d,维样本,x,投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向,w*,相对于,Fisher,准则函数,JF(w),是最好的。,利用,Fisher,准则，就可以将,d,维分类问题转化为一维分类问题，然后，只要确定一个阈值,T,，将投影点,y,n,与,T,相比较，即可进行分类判别。,Fisher线性判别基于最佳变换向量w*的投影,感知器算法,出发点,一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。,在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。,感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。,感知器算法出发点,感知器算法,基本思想,采用感知器算法,(Perception Approach),能通过对训练模式样本集的“学习”得到判别函数的系数,说明,这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。,感知器算法基本思想,感知器算法,感知器的训练算法,感知器算法实质上是一种赏罚过程,对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。,对错误分类的模式则“罚”，使,w(k),加上一个正比于,X,k,的分量。,当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。,如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。,感知器算法感知器的训练算法,感知器算法,感知器算法的收敛性,只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。,感知器算法感知器算法的收敛性,采用感知器算法的多类模式的分类,采用多类情况,3,，将感知器算法推广到多类模式。,感知器算法判别函数的推导,采用感知器算法的多类模式的分类采用多类情况3，将感知器算法推,采用感知器算法的多类模式的分类,讨论,这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。,要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。,采用感知器算法的多类模式的分类讨论,采用感知器算法的多类模式的分类,讨论,要获得一个判别性能好的线性分类器，究竟需要多少训练样本？,直观上是越多越好，但实际上能收集到的样本数目会受到客观条件的限制；,过多的训练样本在训练阶段会使计算机需要较长的运算时间；,一般来说，合适的样本数目可如下估计：,若,k,是模式的维数，令,C=2(k+1),，则通常选用的训练样本数目约为,C,的,1020,倍。,采用感知器算法的多类模式的分类讨论,讨论,若正确地选择了准则函数,J(w,x),，则当权向量,w,是一个解时，,J,达到极小值（,J,的梯度为零）。由于权向量是按,J,的梯度值减小，因此这种方法称为梯度法（最速下降法）。,为了使权向量能较快地收敛于一个使函数,J,极小的解，,C,值的选择是很重要的。,若,C,值太小，则收敛太慢；,若,C,值太大，则搜索可能过头，引起发散。,梯度算法,讨论梯度算法,