《模式识别-3分类器的设计.ppt》由会员分享，可在线阅读，更多相关《模式识别-3分类器的设计.ppt（48页珍藏版）》请在三一办公上搜索。
1、第三章 分类器的设计,线性分类器的设计分段线性分类器的设计非线性分类器的设计 ustbs2009 123456,3-1 线性分类器的设计,上一章我们讨论了线性判别函数形式为:g(x)=WTX 其中 X=(X1,X2Xn)n维特征向量 W=(W1,W2 Wn,Wn+1)n维权向量 通常通过特征抽取可以获得n维特征向量，因此n维权向量是要求解的。求解权向量的过程就是分类器的训练过程，使用已知类别的有限的学习样本来获得分类器的权向量被称为有监督的分类。,利用已知类别学习样本来获得权向量的训练过程如下,已知x1 1,通过检测调整权向量，最终使x1 1已知x2 2,通过检测调整权向量，最终使x2 2这样
2、就可以通过有限的样本去决定权向量,x1,x2,.,xn,1,w1,w2,wn,wn+1,0 x1,检测(已知类别),W1 X1,W2 X2,Wn Xn,Wn+1,0 x2,g(x)=wTx,利用方程组来求解权向量对二类判别函数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)T Xc=(X1c,X2c)T Xd=(X1d,X2d)T判别函数可联立成：X1aW1+X2aW2+W30 X1bW1+X2bW2+W30 X1cW1+X2cW2+W30 X1
3、dW1+X2dW2+W30 求出W1,W2,W3,将 式正规化，得-X1cW1-X2cW2-W3 0-X1dW1-X2dW2-W3 0所以 g(x)=WTX 0 其中W=(W1,W2,W3)T 为各模式增1矩阵 为N*(n+1）矩阵N为样本数，n为特征数,训练过程就是对已知类别的样本集求解权向量w，这是一个线性联立不等式方程组求解的过程。求解时：只有对线性可分的问题，g(x)=WTX才有解联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解的问题 求解W的过程就是训练的过程。训练方法的共同点是，先给出准则函数，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数。算法
4、可以分为迭代法和非迭代法。,一 梯度下降法迭代法,欲对不等式方程组WTX0求解，首先定义准则函数(目标函数)J(W)，再求J(W)的极值使W优化。因此求解权向量的问题就转化为对一标量函数求极值的问题。解决此类问题的方法是梯度下降法。方法就是从起始值W1开始，算出W1处目标函数的梯度矢量J(W1)，则下一步的w值为：W2=W1-1J(W1)W1为起始权向量 1为迭代步长 J(W1)为目标函数J(W1)为W1处的目标函数的梯度矢量,在第K步的时候Wk+1=Wk-kJ(Wk)k为正比例因子这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解矢量，k取值很重要 k太大，迭代太快，引起振荡，甚至发散
5、。k太小，迭代太慢。应该选最佳k。,选最佳k 目标函数J(W)二阶台劳级数展开式为 J(W)J(Wk)+JT(W-Wk)+(W-Wk)TD(W-Wk)T/2 其中D为当W=Wk时 J(W)的二阶偏导数矩阵 将W=Wk+1=Wk-kJ(Wk)代入式得：J(Wk+1)J(Wk)-k|J|2+k2JT DJ 其中J=J(Wk)对k求导数，并令导数为零有 最佳步长为k=|J|2/JTDJ这就是最佳k的计算公式，但因二阶偏导数矩阵D的计算量太大，因此此公式很少用。,若令W=Wk+1上式为J(Wk+1)=J(Wk)+JT(Wk+1-Wk)+(Wk+1-Wk)TD(Wk+1-Wk)T/2 对Wk+1求导，并
6、令导数为零可得：最佳迭代公式：Wk+1=Wk-D-1J 牛顿法的迭代公式 D-1是D的逆阵讨论：牛顿法比梯度法收敛的更快，但是D的计算量大并且要计算D-1。当D为奇异时，无法用牛顿法。,二 感知器法,感知器的原理结构为：,通过对W的调整，可实现判别函数g(x)=WTX RT 其中RT为响应阈值定义感知准则函数：只考虑错分样本定义：其中x0为错分样本当分类发生错误时就有WTX 0,所以J(W)总是正值，错误分类愈少，J(W)就愈小。理想情况为 即求最小值的问题。,求最小值对W求梯度代入迭代公式中Wk+1=Wk-kJ 由J(W)经第K+1次迭代的时候，J(W)趋于0，收敛于所求的W值,+,感知器算
7、法：1.错误分类修正wk 如wkTx0并且x1 wk+1=wk-kx 如wkTx0并且x2 wk+1=wk-kx 2.正确分类，wk不修正 如wkTx0并且x1 如wkTx0并且x2 wk+1=wk,+,-,H,wk+1,kx,wk,权值修正过程,k选择准则 固定增量原则 k固定非负数 绝对修正规则 k 部分修正规则 k=02,例题：有两类样本 1=（x1,x2）=(1,0,1),(0,1,1)2=（x3,x4）=(1,1,0),(0,1,0)解：先求四个样本的增1模式 x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)假设初始权向量 w1=(1,
8、1,1,1)k=1第一次迭代：w1Tx1=(1,1,1,1)(1,0,1,1)T=30 所以不修正 w1Tx2=(1,1,1,1)(0,1,1,1)T=30 所以不修正 w1Tx3=(1,1,1,1)(1,1,0,1)T=30 所以修正w1 w2=w1-x3=(0,0,1,0)w2Tx4=(0,0,1,0)T(0,1,0,1)=0 所以修正w2 w3=w2-x4=(0,-1,1,-1)第一次迭代后,权向量w3=(0,-1,1,-1),再进行第2,3,次迭代如下表,直到在一个迭代过程中权向量相同，训练结束。w6=w=(0,1,3,0)判别函数g(x)=-x2+3x3感知器算法只对线性可分样本有收
9、敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.,线性不可分样本集的分类解(取近似解)对于线性可分的样本集，可以用上述方法解到正确分类的权向量。当样本集线性不可分时，用上述方法求权值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量，或就取其中之一为权向量，一般可以解到较满意的近似结果。例：在样本1:X1=（0,2）X3=（2,0）X5=（-1,-1）2:X2=（1,1）X4=（0,-2）X6=（-2,0）求权向量的近似解,x2,x1,x6,x1,x3,2,x5,2,x4,x2,1,1,H,解：此为线性不可分问题，利用感知器法求权向量权向量产生循环(-1,2,0),(0
10、,2,2),(-1,1,1),(-1,1,1)(-1,1,1),(0,0,0),(-1,2,0)因此算法不收敛，我们可以取循环中任一权值，例如取W=(0,2,2)T则判别函数为：g(x)=2x1+2x2判别面方程为：g(x)=2x1+2x20 所以x1+x20由图看出判别面H把二类分开，但其中x2错分到1类，而x1错分到2类，但大部分分类还是正确的。,作业：已知四个训练样本 w1=(0,0),(0,1)w2=(1,0),(1,1)使用感知器固定增量法求判别函数 设w1=(1,1,1,1)k=1 要求编写程序上机运行，写出判别函数，并打出图表。,三 最小平方误差准则(MSE法)-非迭代法,前面我
11、们研究了线性不等式方程组g(x)=WTX0的解法。它们共同点是企图找一个权向量W，使错分样本最小。现在我们把不等式组变成如下形式：WTXi=bi0 则有联立方程XW=b 这是矛盾方程组，方程数大于未知数，所以没有精确解的存在。,每个样本有n个特征,定义误差向量：e=XW-b0 把平方误差作为目标函数 W的优化就是使J(W)最小。求J(W)的梯度并为0。解上方程得 XTXW=XTb这样把求解XW=b的问题，转化为对XTXW=XTb求解，这一有名的方程最大好处是因XTX是方阵且通常是非奇异的，所以可以得到W的唯一解。,MSE准则函数,只要计算出X+就可以得到W取：最小平方误差法同Fisher法是一
12、致的。,（MSE 解）,其中N/N1有N1个，N/N2有N2个,四 韦霍氏法（LMS法）迭代法,上节得到MSE法的W解为：W=X+b在计算X+时，1 要求XTX矩阵为非奇异 2 由于计算量太大而引入比较大误差 所以要用迭代法来求求J(W)的梯度J(W)=2XT(XW-b)代入迭代公式 W1任意设定 Wk+1=Wk-kXT(XWk-b)此法可收敛于W值。W满足:XT(XW-b)=0,计算量很大,因此下降算法不论XTX是否奇异，总能产生一个解。若训练样本无限的重复出现，则简化为 W1任意 Wk+1=Wk+k(bk-WkTXk)Xk k随迭代次数k而减少，以保证算法收敛于满意的W值,五 何卡氏法（判
13、断迭代过程中是否线性可分）,若训练样本线性可分时，感知器法可求出界面，但对不可分问题不收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出一加权矢量，但不能保证此矢量就是分界矢量，下面介绍一种方法可以检测迭代过程中是否线性可分。因最小平方误差法的J(W)的解为因为XW=b b应为正值c为矫正系数 当（XWk-bk）0 时 当（XWk-bk）0 时,引入误差矢量ek ek=XWk-bk判断是否线性可分所以J(W)的解为 初始条件 W1=X+b1并且b10迭代时检测 如果ek0时，XWb，系统线性可分，迭代收敛 如果ek0时，XWb，系统线性不可分，迭代不收敛我们用下面的例子来说明ek的作用
14、,因此上式可以写成,例题：1=(0,0)T,(0,1)T 2=(1,0)T,(1,1)T解：正规化 对2取负，有,X的规范矩阵为,x2,x1,x1,x2,x3,x4,取b1=(1,1,1,1)T c=1 W1=X+b1=(-2,0,1)T 所以W1为所求解 e1=XW1-b1=0 系统线性可分,因为,若四个样本变成：1=(0,0)T,(1,1)T 2=(0,1)T,(1,0)T解：取b1=(1,1,1,1)T c=1 W1=X+b1=(0,0,0)T e1=XW1-b1=(-1,-1,-1,-1)T0 系统线性不可分 C为校正系数,取0 C 1在算法进行过程中，应在每一次迭代时，检测ek 的值
15、。只要出现ek0，迭代就应立即停止。,x2,x1,1,1,六 Fisher分类准则,现在讨论通过 映射投影来降低 维数的方法。X空间 X=-WTX-W0 0 X1 X=-WTX-W0 0 X 1 Y=WTX-W0 0 X2把X空间各点投影到Y空间得一直线上，维数由2维降为一维。若适当选择W的方向，可以使二类分开。下面我们从数学上寻找最好的投影方向，即寻找最好的变换向量W的问题。,w(y),w,y1,y2,x2,x1,1,2,投影样本之间的分离性用投影样本之差表示 投影样本类内离散度:,i=1,2,i=1,2,类间散布矩阵,上式就是n维x空间向一维y空间的最好投影方向，它实际是多维空间向一维空间
16、的一种映射。,其中Sw为类内散布矩阵,Sb为类间散布矩阵,现在我们已把一个n维的问题转化为一维的问题。现在一维空间设计 Fisher分类器:W0的选择,Yki表示第i类中第k个样本的投影值 N1为1样本数 N2为2样本数当W0选定后，对任一样本X，只要判断Y=WTX0 则X1;Y=WTX0 则X2。分类问题就解决了,3-2 分段线形分类器的设计,先求子类的权向量Wi l，再求总的权向量Wi 1.已知子类划分时的设计方法把每一个子类作为独立类，利用每个子类的训练样本，求每个子类的线性判别函数，总的判别函数就可获得。子类的划分可用以下方法：用先验知识直接划分 用聚类分析，聚成多个子类 2.已知子类
17、的数目的设计方法 设各个子类的初始权向量：Wi 1,Wi 2 Wi li i=1,2,M Wi中有Li个子类 若第K步迭代时j 类样本Xj 同j类某个子类的权向量Wj n(k)的内积值最大，即Wj n(k)l xj=max Wj n(k)l xj n=1,2,lj,并且满足条件Wj n(k)xj Wi n(k)l xj i=1,2,M类 j=1,2,li子类 ij 则权向量Wi 1(k)，Wi 2(k)，,Wi li(k)不影响分类，所以权向量不需要修正。若有某个或某几个子类不满足条件即：存在Wi n(k)使Wj n(k)xj Wi n(k)l xj ij 所以xj 错分类，要修改权向量。设W
18、i n(k)l xj=max Wi n(k)l xj n=1,2,li ij则修改权向量Wjn(k+1)=Wj n(k)kxj 重复以上迭代,直到收敛,此法类似于固定增量法.,3.未知子类数目时的设计方法 当每类应分成的子类数也不知 时，这是最一般情况，方法很 多，举例如下。树状分段线性分类器:设两类情况1，2。如图所示 先用两类线性判别函数求 出W1,超平面H1分成两个区 间,每个区间包含两类。再利用二类分类求出W2(H2),W3(H3)。如果每个部分仍包含两类,继续上面的过程。,关键是初始权向量W1的选择:一般先选两类中距离最近的两个子类的均值连线做垂直线作为H1(w1)初始值再求最优解。
19、,w1Tx0,w4Tx0,w3Tx0,w2Tx0,Y,N,Y,Y,N,N,1,1,2,2,N,Y,1,树状决策框图,3-3 非线性分类器的设计,电位函数分类器,用非线性判别函数区分线性不可分的类别电位函数分类器:每个特征作为一个点电荷,把特征空间作为能量场.电位分布函数有下面三种形式。为系数 xk为某一特定点上图是这些函数在一维时的图形，第三条是振荡曲线，只有第一周期才是可用范围。,x,K(x),x,3,2,1,电位函数算法的训练过程是在逐个样本输入时，逐渐积累电位的过程，对于二类问题，经过若干循环后，如积累电位方程的运算结果能以正、负来区分二类样本，则训练就可结束。算法:设初始电位为K0(x
20、)=01.输入样本x1计算积累电位K1(x)若x1 K1(x)=K0(x)+K(xx1)若x2 K1(x)=K0(x)-K(xx1)设1为正电荷,2为负电荷 在K0(x)=0时 若x11 K1(x)=K(xx1)若x12 K1(x)=-K(xx1),2.输入样本x2计算积累电荷有以下几种情况 a.若x21 并且K1(x2)0 若x22 并且K1(x2)0 K1(x)=K2(x)不修正 b.若x21 并且K1(x2)0 若x22 并且K1(x2)0 K2(x)=K1(x)K(xx2)=K1(xx1)K(xx2)修正 直到第k+1步,已输入x1,x2,.xk个样本,积累电荷Kk+1(x)有三种情况
21、:1.若xk+11并且Kk(xk+1)0或xk+12 并且Kk(xk+1)0时 rk+1=0 xk+11并且Kk(xk+1)0时 rk+1=1 xk+12并且Kk(xk+1)0时 rk+1=0 xk+12并且Kk(xk+1)0时 rk+1=-1,例题.设有两类样本1=(0,0)T,(2,0)T 2=(1,1)T,(1,-1)T如下图线性不可分特征为二维的，所以电位函数为：K(xx2)=exp-(x1-xk1)2+(x2-xk2)2 输入x1=(xk1,xk2)T=(0,0)T x11 K1(x)=K1(xx1)=exp-(x12+x22)输入x2=(2,0)T x21代入 K1(x2)=exp
22、-(02+22)0 不修正 K2(x)=K1(x)=exp-(x12+x22)输入x3=(1,1)T x32代入 K2(x3)=exp-(12+12)0 所以需要修正 K3(x)=K2(x)-K(xx3)=exp-(x12+x22)-exp-(x1-1)2+(x2-1)2,输入x4=(1,-1)T x32代入K3(x4)=e-2-e-40 所以需要修正K4(x)=K3(x)-K(xx4)=exp-(x12+x22)-exp-(x1-1)2+(x2-1)2-exp-(x1-1)2+(x2+1)2第二次迭代 输入x5=x1=(0,-0)T x51代入K4(x5)=1-e-2-e-40 K5(x)=
23、K4(x)输入x6=x2=(2,0)T x61代入 K5(x6)=e-4-e-2-e-2=0 所以需要修正 K6(x)=K5(x)+K(xx6)=exp-(x12+x22)-exp-(x1-1)2+(x2-1)2-exp-(x1-1)2+(x2+1)2+-exp-(x1-2)2+x22,输入x7=x3=(1,1)T x72代入 K6(x7)=e-2-e0-e-4+e-20 所以不需要修正 K9(x)=K8(x),g(x)0,g(x)0,g(x)0,g(x)0,同理得到:K10(x)=K9(x)=K8(x)=K7(x)=K6(x),经一个完整的循环可得判别函数为：g(x)=exp-(x12+x22)-exp-(x1-1)2+(x2-1)2-exp-(x1-1)2+(x2+1)2+exp-(x1-2)2+x22上边的非线性判别函数形成的边界如图所示。虽然它可以把线性不可分的样本分开，但当样本很多时，使方程的项数太多，增大计算量。,
