模式识别导论(三)ppt - 分类器的设计线性分类器的设计分段线性

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 分类器的设计,线性分类器的设计,分段线性分类器的设计,非线性分类器的设计,3-1 线性分类器的设计,上一章我们讨论了线性判别函数形式为:,g(x)=W,T,X,其中,X=(X,1,X,2,X,n,)n,维特征向量,W=(W,1,W,2,W,n,W,n,+1,)n,维权向量,通常通过特征抽取可以获得,n,维特征向量，因此,n,维,权向量是要求解的。,求解权向量的过程就是分类器的训练过程，使用已,知类别的有限的学习样本来获得分类器的权向量被称为,有监督的分类。,利用已知类别学习样本来获得权向量的训练过程如下,已知,x,1,1,通过检测调整权向量，最终使,x,1,1,已知,x,2,2,通过检测调整权向量，最终使,x,2,2,这样就可以通过有限的样本去决定权向量,x,1,x,2,.,x,n,1,w,1,w,2,w,n,w,n,+1,0,x1,检测,(,已知类别,),W,1,X,1,W,2,X,2,W,n,X,n,W,n,+1,0,-X,1d,W,1,-X,2d,W,2,-W,3,0,所以,g(x)=W,T,X 0,其中,W=(W,1,W,2,W,3,),T,为各模式增1矩阵,为,N*(n+1）,矩阵,N,为样本数，,n,为特征数,训练过程就是对已知类别的样本集求解权向量,w，,这是一个线,性,联立不等式方程组求解的过程。,求解时：,只有对线,性,可分的问题，,g(x)=W,T,X,才有解,联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解的问题,求解,W,的过程就是训练的过程。训练方法的共同点是，先给出准则函数，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数。算法可以分为迭代法和非迭代法。,一 梯度下降法迭代法,欲对不等式方程组,W,T,X0,求解，首先定义准则函数(目,标函数),J(W)，,再求,J(W),的极值,使,W,优化。因此求解权,向量的问题就转化为对一标量函数求极值的问题。解决,此类问题的方法是梯度下降法。,方法就是从起始值,W,1,开始，算出,W,1,处,目标函数的梯度,矢量,J(W,1,)，,则,下一步的,w,值为：,W,2,=W,1,-,1,J(W,1,),W,1,为起始权向量,1,为迭代步长,J(W,1,),为目标函数,J(W,1,),为,W,1,处的目标函数的梯度矢量,在第,K,步的时候,W,k+1,=W,k,-,k,J(W,k,),k,为正比例因子,这就是梯度下降法的迭代公式。这样一步步迭代,就可以收敛于解矢量，,k,取值很重要,k,太大，迭代太快，引起振荡，甚至发散。,k,太小，迭代太慢。,应该选最佳,k,。,选最佳,k,目标函数,J(W),二阶台劳级数展开式为,J(W)J(W,k,)+J,T,(W-W,k,)+(W-W,k,),T,D(W-W,k,),T,/2 ,其中,D,为当,W=W,k,时,J(W),的,二阶偏导数矩阵,将,W=W,k+1,=W,k,-,k,J(W,k,),代入式得：,J(W,k+1,)J(W,k,)-,k,|J|,2,+,k,2,J,T,DJ,其中,J=J(W,k,),对,k,求导数,，并令,导数为零有,最佳步长为,k,=|J|,2,/J,T,DJ,这就是最佳,k,的,计算公式，但因二阶偏导数矩阵,D,的,计算,量太大，因此此公式很少用。,若令,W=W,k+1,上式为,J(W,k+1,)=J(W,k,)+J,T,(W,k+1,-W,k,)+(W,k+1,-W,k,),T,D(W,k+1,-W,k,),T,/2,对,W,k+1,求导，并令导数为零可得,：,最佳迭代公式：,W,k+1,=,W,k,-D,-1,J ,牛顿法的迭代公式,D,-1,是,D,的逆阵,讨论：牛顿法比梯度法收敛的更快，但是,D,的计算量大并且要计算,D,-1,。,当,D,为奇异时，无法用牛顿法。,二 感知器法,感知器的原理结构为：,通过对,W,的调整，可实现判别函数,g(x)=W,T,X R,T,其中,R,T,为响应阈值,定义感知准则函数：只考虑错分样本,定义：其中,x,0,为错分样本,当分类发生错误时就有,W,T,X 0,所以,J(W),总是正值，错误分类愈少，,J(W),就愈小。,理想情况为 即求最小值的问题。,求最小值对,W,求梯度,代入迭代公式中,W,k+1,=W,k,-,k,J,由,J(W),经第,K+1,次,迭代的时候，,J(W),趋于0，收敛于所求的,W,值,W,的训练过程：,例如,:,x,1,x,2,x,3,1,作,x,1,x,3,的垂直线可得解区(如图),假设,起始权向量,w,1,=0,k,=1,1.x,1,x,2,x,3,三个矢量相加得矢量,2,垂直于矢量,2,的超平面,H,将,x,3,错分,.,2.,x,3,与,矢量2相加得矢量,3,垂直于矢量,3,的超平面,H,1,将,x,1,错分,.,3.,依上法得矢量,4,垂直于矢量,4,做超平面,H,2,将,x,3,错分,4.,x,3,与,矢量4相加得矢量,5,矢量,5,在解区内,垂直于矢量5的超平面可以把,x,1,x,2,x,3,分成一类,。,x,1,x,2,x,3,2,H,3,H,1,4,H,2,5,W,区间,+,感知器算法：,1.,错误分类修正,w,k,如,w,k,T,x,0,并且,x,1,w,k+1,=w,k,-,k,x,如,w,k,T,x,0,并且,x,2,w,k+1,=w,k,-,k,x,2.,正确分类,，,w,k,不修正,如,w,k,T,x,0,并且,x,1,如,w,k,T,x,0,并且,x,2,w,k+1,=w,k,+,-,H,w,k+1,k,x,w,k,权值修正过程,k,选择准则,固定增量原则,k,固定非负数,绝对修正规则,k,部分修正规则,k,=,0,2,例题：有两类样本,1,=,（,x,1,x,2,）,=(1,0,1),(0,1,1),2,=,（,x,3,x,4,）,=(1,1,0),(0,1,0),解：先求四个样本的增值模式,x,1,=(1,0,1,1)x,2,=(0,1,1,1),x,3,=(1,1,0,1)x,4,=(0,1,0,1),假设初始权向量,w,1,=(1,1,1,1),k,=1,第一次迭代：,w,1,T,x,1,=(1,1,1,1)(1,0,1,1),T,=30,所以不修正,w,1,T,x,2,=(1,1,1,1)(0,1,1,1),T,=30,所以不修正,w,1,T,x,3,=(1,1,1,1)(1,1,0,1),T,=30,所以修正,w,1,w,2,=w,1,-x,3,=(0,0,1,0),w,2,T,x,4,=(0,0,1,0),T,(0,1,0,1)=0,所以修正,w,2,w,3,=w,2,-x,4,=(0,-1,1,-1),第一次迭代后,权向量,w,3,=(0,-1,1,-1),再进行第2,3,次迭代,如下表,直到在一个迭代过程中权向量相同，训练结束。,w,6,=w=(0,1,3,0),判别函数,g(x)=-x,2,+3x,3,感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.,训练样本,w,k,T,x,修正式,修正后的权值,w,k1,迭代次数,x,1,1 0 1 1,x,2,0 1 1 1,x,3,1 1 0 1,x,4,0 1 0 1,+,+,+,0,w,1,w,1,w,1,-x,3,w,2,-x,4,1 1 1 1,1 1 1 1,0 0 1 0,0 1 1 -1,1,x,1,1 0 1 1,x,2,0 1 1 1,x,3,1 1 0 1,x,4,0 1 0 1,0,+,0,-,w,3,+x,1,w,4,w,4,-x,3,w,5,1 1 2 0,1 1 2 0,0 2 2 1,0 2 2 -1,2,x,1,1 0 1 1,x,2,0 1 1 1,x,3,1 1 0 1,x,4,0 1 0 1,+,-,-,-,w,5,w,5,+x,2,w,6,w,6,0 2 2 1,0 1 3 0,0 1 3 0,0 1 3 0,3,x,1,1 0 1 1,x,2,0 1 1 1,x,3,1 1 0 1,x,4,0 1 0 1,+,+,-,-,w,6,w,6,w,6,w,6,0 1 3 0,0 1 3 0,0 1 3 0,0 1 3 0,4,线性不可分样本集的分类解(取近似解),对于线性可分的样本集，可以用上述方法解到正确分,类的权向量。当样本集线性不可分时，用上述方法求权,值时算法不收敛。如果我们把循环的权向量取平均值作,为待求的权向量，或就取其中之一为权向量，一般可以,解到较满意的近似结果。,例：在样本,1,:,X,1,=,（,0,2,）,X,3,=,（,2,0,）,X,5,=,（,-1,-1,）,2,:,X,2,=,（,1,1,）,X,4,=,（,0,-2,）,X,6,=,（,-2,0,）,求权向量的近似解,x,2,x,1,x,6,x,1,x,3,2,x,5,2,x,4,x,2,1,1,H,解：此为线性不可分问题，利用感知器法求权向量,权向量产生循环(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1),(-1,1,1),(0,0,0),(-1,2,0),因此算法不收敛，我们可以取循环中任一权值，例如取,W=(0,2,2),T,则判别函数为：,g(x)=2x,1,+2x,2,判别面方程为：,g(x)=2x,1,+2x,2,0,所以,x,1,+x,2,0,由图看出判别面,H,把二类分开，但其中,x,2,错分到,1,类，,而,x,1,错分到,2,类，但大部分分类还是正确的。,作业：已知四个训练样本,w,1,=(0,0),(0,1),w,2,=(1,0),(1,1),使用感知器固定增量法求判别函数,设,w,1,=(1,1,1,1),k,=1,要求编写程序上机运行，写出判别函数，并打出图表。,三 最小平方误差准则(,MSE,法)-非迭代法,前面我们研究了线性不等式方程组,g(x)=W,T,X0,的解法。它们共同点是企图找一个权向量,W，,使错分样本最小。,现在我们把不等式组变成如下形式：,W,T,X,i,=b,i,0,则有联立方程,XW=b,这是矛盾方程组，方程数大于未知,数，所以没有精确解的存在。,每个样本有,n,个特征,定义误差向量：,e=XW-b,0,把平方误差作为目标函数,W,的优化就是使,J(W),最小。,求,J(W),的梯度并为,0。,解上方程得,X,T,XW=,X,T,b,这样把求解,XW=b,的问题，转化为对,X,T,XW=,X,T,b,求解，这,一有名的方程最大好处是因,X,T,X,是方阵且通常是非奇异的，,所以可以得到,W,的唯一解。,MSE,准则函数,只要计算,出,X+,就可以得到,W,取：,最小平方误差法同,Fisher,法是一致的。,（,MSE,解）,其中,N/N,1,有,N,1,个，,N/N,2,有,N,2,个,四 韦霍氏,法（,LMS,法）迭代法,上节得到,MSE,法的,W,解为：,W=X,+,b,在计算,X,+,时，,1,要求,X,T,X,矩阵为非奇异,2,由于计算量太大而引入比较大误差,所以要用迭代法来求,求,J(W),的梯度,J(W)=2X,T,(XW-b),代入迭代公式,W,1,任意设定,W,k+1,=W,k,-,k,X,T,(,XW,k,-b),此法可收敛于,W,值。,W,满足:,X,T,(XW-b)=0,计算量很大,因此下降算法不论,X,T,X,是否奇异，总能产生一个解。,若训练样本无限的重复出现，则简化为,W,1,任意,W,k+1,=W,k,+,k,(,b,k,-,W,k,T,X,k,),X,k,k,随迭代次数,k,而减少，以保证算法收敛于满意,的,W,值,五 何卡氏法,（判断迭代过程中是否线性可分）,若训练样本线性可分时，感知器法可求出界面，但对不可分问题不,收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出,一加权矢量，但不能保证此矢量就是分界矢量，下面介绍一种方法