模式识别3分类器的设计

1、第三章 分类器的设计n线性分类器的设计n分段线性分类器的设计n非线性分类器的设计 123456 3-1 线性分类器的设计 上一章我们讨论了线性判别函数形式为:g(x)=wtx 其中 x= (x1, x2xn) n维特征向量 w= (w1, w2 wn , wn+1) n维权向量 通常通过特征抽取可以获得n维特征向量，因此n维权向量是要求解的。 求解权向量的过程就是分类器的训练过程，使用已知类别的有限的学习样本来获得分类器的权向量被称为有监督的分类。0)(,0)(,21xgxxgx分类准则利用已知类别学习样本来获得权向量的训练过程如下已知x1 1, 通过检测调整权向量，最终使x1 1已知x2 2

2、, 通过检测调整权向量，最终使x2 2这样就可以通过有限的样本去决定权向量 x1 x2. xn 1 w1 w2 wn wn+1 0 x1 检测(已知类别) w1 x1 w2 x2 wn xn wn+10 -x1dw1- x2dw2- w3 0所以 g(x) =wtx 0 其中w = (w1 , w2, w3)t 为各模式增1矩阵 为n*(n+1）矩阵n为样本数，n为特征数111121212121ddccbbaaxxxxxxxxx训练过程就是对已知类别的样本集求解权向量w，这是一个线性联立不等式方程组求解的过程。求解时： 只有对线性可分的问题，g(x) =wtx才有解 联立方程的解是非单值，在不

3、同条件下，有不同的解，所以就产生了求最优解的问题 求解w的过程就是训练的过程。训练方法的共同点是，先给出准则函数，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数。算法可以分为迭代法和非迭代法。 一 梯度下降法迭代法欲对不等式方程组wtx0求解，首先定义准则函数(目标函数)j(w)，再求j(w)的极值使w优化。因此求解权向量的问题就转化为对一标量函数求极值的问题。解决此类问题的方法是梯度下降法。方法就是从起始值w1开始，算出w1处目标函数的梯度矢量j(w1)，则下一步的w值为：w2 = w1-1j(w1)w1为起始权向量 1为迭代步长 j(w1) 为目标函数j(w1)为w1处的目

4、标函数的梯度矢量在第k步的时候wk+1 = wk-kj(wk) k为正比例因子这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解矢量，k取值很重要 k太大，迭代太快，引起振荡，甚至发散。 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/

5、jtdj这就是最佳k的计算公式，但因二阶偏导数矩阵d的计算量太大，因此此公式很少用。 21若令w=wk+1上式为j(wk+1)=j(wk)+jt(wk+1-wk)+(wk+1-wk)td(wk+1-wk)t/2 对wk+1求导，并令导数为零可得：最佳迭代公式：wk+1= wk- d-1j 牛顿法的迭代公式 d-1是d的逆阵讨论：牛顿法比梯度法收敛的更快，但是d的计算量大并且要计算d-1。当d为奇异时，无法用牛顿法。二 感知器法感知器的原理结构为：通过对w的调整，可实现判别函数g(x) =wtx rt 其中rt为响应阈值定义感知准则函数：只考虑错分样本定义： 其中x0为错分样本当分类发生错误时就

6、有wtx 0, 所以j(w) 总是正值，错误分类愈少， j(w)就愈小。理想情况为 即求最小值的问题。0)(xxxwwjt0)(wj求最小值对w求梯度代入迭代公式中wk+1 = wk-kj 由j(w)经第k+1次迭代的时候，j(w)趋于0，收敛于所求的w值0)(xxxwwjj01xxxwwkkk即感知器迭代公式：+n感知器算法： 1.错误分类修正wk 如wktx0并且x1 wk+1= wk-kx 如wktx0并且x2 wk+1= wk-kx 2.正确分类 ，wk不修正 如wktx0并且x1 如wktx0并且x2 wk+1= wk +-hwk+1kxwk权值修正过程nk选择准则 固定增量原则 k

7、固定非负数 绝对修正规则 k 部分修正规则 k= 02xxxwtt|xxxwtt|例题：有两类样本 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,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 所

8、以修正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+3x3n感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点. 训练样本训练样本wktx修正式修正式修正后的权值修正后的权值wk1迭代次数迭代次数x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1

9、 0 1+0w1w1w1-x3w2-x41 1 1 11 1 1 10 0 1 00 1 1 -1 1x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 10+0-w3+x1w4w4-x3w51 1 2 01 1 2 00 2 2 10 2 2 -1 2x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w5w5+x2w6w60 2 2 10 1 3 00 1 3 00 1 3 0 3x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w6w6w6w60 1 3 00 1 3 00 1 3 00 1 3

10、0 4线性不可分样本集的分类解(取近似解)对于线性可分的样本集，可以用上述方法解到正确分类的权向量。当样本集线性不可分时，用上述方法求权值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量，或就取其中之一为权向量，一般可以解到较满意的近似结果。例：在样本1: x1 =（0,2） x3 =（2,0） x5 =（-1,-1）2: x2 =（1,1） x4 =（0,-2） x6 =（-2,0）求权向量的近似解x2x1x6x1x32x52x4x211h解：此为线性不可分问题，利用感知器法求权向量权向量产生循环(-1, 2, 0), (0, 2, 2), (-1, 1, 1), (-1, 1,

11、 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类，但大部分分类还是正确的。n作业：已知四个训练样本 w1=(0,0),(0,1) w2=(1,0),(1,1) 使用感知器固定增量法求判别函数 设w1=(1,1,1,1) k=1 要求编写程序上机运行，写出判别函数，并打出图表。三 最小平方误差准则(mse法)-非迭代法前面我们研究了线性不

12、等式方程组g(x) =wtx0的解法。它们共同点是企图找一个权向量w，使错分样本最小。现在我们把不等式组变成如下形式：wtxi=bi0 则有联立方程xw=b 这是矛盾方程组，方程数大于未知数，所以没有精确解的存在。nnnnnnxxxxxxxxxxx.21211121121n . 2,1,xxxtx 令给定的任意正常数n . 2,1,bbbtb 每个样本有n个特征定义误差向量：e=xw-b0 把平方误差作为目标函数 w的优化就是使j(w)最小。求j(w)的梯度并为0。解上方程得 xtxw=xtb这样把求解xw=b的问题，转化为对xtxw=xtb求解，这一有名的方程最大好处是因xtx是方阵且通常是

13、非奇异的，所以可以得到w的唯一解。 nibixiwtbxwewj1222|)(mse准则函数 0)(22j(w)1bxwxxbixiwttini只要计算出x+就可以得到w取： 最小平方误差法同fisher法是一致的。 bxbxxxtwt1的伪逆（规范矩阵）称为其中xxxxtxt1221.1/./nnnnnnnnb（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任

14、意设定 wk+1 = wk-kxt(xwk-b) 此法可收敛于w值。w满足: xt(xw-b)=0为任意常数其中令11kkxxxtxt1伪逆计算量很大因此下降算法不论xtx是否奇异，总能产生一个解。若训练样本无限的重复出现，则简化为 w1任意任意 wk+1=wk+k(bk-wktxk) xk k随迭代次数k而减少，以保证算法收敛于满意的w值k1k取五 何卡氏法 （判断迭代过程中是否线性可分） 若训练样本线性可分时，感知器法可求出界面，但对不可分问题不收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出一加权矢量，但不能保证此矢量就是分界矢量，下面介绍一种方法可以检测迭代过程中是否线性可分

15、。n因最小平方误差法的j(w)的解为n因为xw=b b应为正值nc为矫正系数 当（xwk-bk）0 时 当（xwk-bk） 0 时bxbxxxtwt1|kkkkkbxwbxwcbb的增量为kkkbbbb 1前后两次迭代后，对的增量为其中bbk0kb2kkkbxwcbn引入误差矢量ek ek=xwk-bk判断是否线性可分n所以j(w)的解为 初始条件 w1=x+b1并且b10n迭代时检测 如果ek0时，xw b，系统线性可分，迭代收敛 如果ek0时，xw b，系统线性不可分，迭代不收敛n我们用下面的例子来说明ek的作用|kkkeecb|11kkkkkkkkkeexcwbxbxbbxbxw因此上式

16、可以写成n例题： 1=(0,0)t,(0,1)t 2=(1,0)t,(1,1)tn解：正规化 对2取负，有 111101110100x2/12/12/12/311111111211xxxtxtx的规范矩阵为x2x1x1x2x3x4取b1=(1,1,1,1)t c=1 w1=x+b1=(-2,0,1)t 所以w1为所求解 e1=xw1-b1=0 系统线性可分01111102111101110100, , ,1twx因为 若四个样本变成：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=(

17、-1,-1,-1,-1)t0 系统线性不可分 c为校正系数,取0 c 1在算法进行过程中，应在每一次迭代时，检测ek 的值。只要出现ek0 x1 x=-wtx-w0 0 x 1 y=wtx-w0 0 则x1; y=wtxwi 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 错分类，要修改权向量。 设wi n (k)l xj = max wi n (k)l

18、 xj n = 1,2,li ij则修改权向量wjn(k+1)= wj n(k) kxj 重复以上迭代,直到收敛,此法类似于固定增量法. 3.未知子类数目时的设计方法 当每类应分成的子类数也不知 时，这是最一般情况，方法很 多，举例如下。 树状分段线性分类器: 设两类情况1， 2。如图所示 先用两类线性判别函数求 出w1,超平面h1分成两个区 间,每个区间包含两类。 再利用二类分类求出w2(h2), w3(h3)。 如果每个部分仍包含两类, 继续上面的过程。n关键是初始权向量w1的选择:一般先选两类中距离最近的两个子类的均值连线做垂直线作为h1(w1)初始值再求最优解。w1tx0 w4tx0

19、w3tx0 w2tx0 ynyynn1 1 22 ny1 树状决策框图3-3 非线性分类器的设计n电位函数分类器,用非线性判别函数区分线性不可分的类别n电位函数分类器:每个特征作为一个点电荷,把特征空间作为能量场. 电位分布函数有下面三种形式。 为系数 xk为某一特定点上图是这些函数在一维时的图形，第三条是振荡曲线，只有第一周期才是可用范围。|11 )k( 2.2kkxxxx|sin|)k( 3.22kkkxxxxxxxk(x)x321|exp- )k( 1.2kkxxxx电位函数算法的训练过程是在逐个样本输入时，逐渐积累电位的过程，对于二类问题，经过若干循环后，如积累电位方程的运算结果能以正

20、、负来区分二类样本，则训练就可结束。算法: 设初始电位为k0(x)=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或xk+12 并且kk(xk+1)0时 rk+1= 0 xk+11并且kk(xk+1) 0时 rk+1= 1 xk+12并且kk(xk+1)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,