模式识别-3分类器的设计ppt课件

1、第三章 分类器的设计n线性分类器的设计n分段线性分类器的设计n非线性分类器的设计nmoshishibie126 ustbs2021nmoshishibie2021sohu 123456 3-1 线性分类器的设计 上一章我们讨论了线性判别函数方式为:g(x)=WTX 其中 X= (X1, X2Xn) n维特征向量 W= (W1, W2 Wn , Wn+1) n维权向量 通常经过特征抽取可以获得n维特征向量，因此n维权向量是要求解的。 求解权向量的过程就是分类器的训练过程，运用已知类别的有限的学习样本来获得分类器的权向量被称为有监视的分类。0)(,0)(,21xgxxgx分类准则利用知类别学习样本

2、来获得权向量的训练过程如下知x1 1, 经过检测调整权向量，最终使x1 1知x2 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，这是一个线性联立不等式方程组求解的过程。求解时

3、： 只需对线性可分的问题，g(x) =WTX才有解 联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解的问题 求解W的过程就是训练的过程。训练方法的共同点是，先给出准那么函数，再寻觅使准那么函数趋于极值的优化算法，不同的算法有不同的准那么函数。算法可以分为迭代法和非迭代法。 一 梯度下降法迭代法欲对不等式方程组WTX0求解，首先定义准那么函数(目标函数)J(W)，再求J(W)的极值使W优化。因此求解权向量的问题就转化为对一标量函数求极值的问题。处理此类问题的方法是梯度下降法。方法就是从起始值W1开场，算出W1处目的函数的梯度矢量J(W1)，那么下一步的w值为：W2 = W1-

4、1J(W1)W1为起始权向量 1为迭代步长 J(W1) 为目的函数J(W1)为W1处的目的函数的梯度矢量在第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(W

5、k)代入式得：代入式得： J(Wk+1) J(Wk)- k|J|2+ k2JT DJ 其中其中J=J(Wk) 对对k求导数求导数 ，并令导数为零有，并令导数为零有 最正确步长为最正确步长为k=|J|2/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

6、的逆阵讨论：牛顿法比梯度法收敛的更快，但是D的计算量大并且要计算D-1。当D为奇特时，无法用牛顿法。二 感知器法感知器的原理构造为：经过对W的调整，可实现判别函数g(x) =WTX RT 其中RT为呼应阈值定义感知准那么函数：只思索错分样本定义： 其中x0为错分样本当分类发生错误时就有WTX 0, 所以J(W) 总是正值，错误分类愈少， J(W)就愈小。理想情况为 即求最小值的问题。0)(XXXWWJT0)(WJ求最小值对W求梯度代入迭代公式中Wk+1 = Wk-kJ 由J(W)经第K+1次迭代的时候，J(W)趋于0，收敛于所求的W值0)(XXXWWJJ01XXXWWkkk即感知器迭代公式：+

7、n感知器算法：n 1.错误分类修正wkn 如wkTx0并且x1 wk+1= wk-kx n 如wkTx0并且x2 wk+1= wk-kx n 2.正确分类 ，wk不修正n 如wkTx0并且x1n 如wkTx0并且x2n wk+1= wk +-Hwk+1kxwk权值修正过程nk选择准那么 n 固定增量原那么 k固定非负数n n 绝对修正规那么 k n n n 部分修正规那么 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,

8、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 所以修正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,次迭代如下表 直到在一个迭代过程中权向量一样，

9、训练终了。w6=w=(0,1,3,0) 判别函数g(x)= -x2+3x3感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会呵斥训练过程的振荡,这是它的缺陷. 训练样本wkTx修正式修正后的权值wk1迭代次数x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 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

10、 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 0 4线性不可分样本集的分类解(取近似解)对于线性可分的样本集，可以用上述方法解到正确分类的权向量。当样本集线性不可分时，用上述方法求权值时算法不收敛。假设我们把循环的权向量取平均值作为待求的权向量，或就取其中之一为权向量，普通可以解到较称心的近似结果。例：在样本1: X1 =0,2 X3 =2,0 X5 =-

11、1,-12: X2 =1,1 X4 =0,-2 X6 =-2,0求权向量的近似解x2x1x6x1x32x52x4x211H解：此为线性不可分问题，利用感知器法求权向量权向量产生循环(-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)= 2x1+2x2判别面方程为： g(x)= 2x1+2x20 所以x1+x20由图看出判别面H把二类分开，但其中x2错分到1类，而x1错分到2类，但大部分分类还是正确的

12、。n作业：知四个训练样本n w1=(0,0),(0,1)n w2=(1,0),(1,1)n 运用感知器固定增量法求判别函数n 设w1=(1,1,1,1) k=1n 要求编写程序上机运转，写出判别函数，并打出图表。三 最小平方误差准那么(MSE法)-非迭代法前面我们研讨了线性不等式方程组g(x) =WTX0的解法。它们共同点是企图找一个权向量W，使错分样本最小。如今我们把不等式组变成如下方式：WTXi=bi0 那么有联立方程XW=b 这是矛盾方程组，方程数大于未知数，所以没有准确解的存在。NnNNnNXXXXXXXXXXX.21211121121N . 2,1,XXXTX 令给定的任意正常数N

13、. 2,1,bbbTb 每个样本有n个特征定义误差向量：e=XW-b0 把平方误差作为目的函数 W的优化就是使J(W)最小。求J(W)的梯度并为0。解上方程得 XTXW=XTb这样把求解XW=b的问题，转化为对XTXW=XTb求解，这一有名的方程最大益处是因XTX是方阵且通常是非奇特的，所以可以得到W的独一解。 NibiXiWTbXWeWJ1222|)(MSE准那么函数 0)(22J(W)1bXWXXbiXiWTTiNi只需计算出X+就可以得到W取： 最小平方误差法同Fisher法是一致的。 bXbXXXTWT1的伪逆（规范矩阵）称为其中XXXXTXT1221.1/./NNNNNNNNbMSE

14、 解其中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为任意常数其中令11kkXXXTXT1伪逆计算量很大因此下降算法不论XTX能否奇特，总能产生一个解。假设训练样本无限的反复出现，那么简化为 W1恣意 Wk+1=Wk+k(bk-WkTXk) Xk k随迭代次数k而减少，以保证算法收

15、敛于称心的W值k1K取五 何卡氏法 判别迭代过程中能否线性可分 假设训练样本线性可分时，感知器法可求出界面，但对不可分问题不收敛只能取平均。最小平方误差法不论样天性否线性可分都能给出一加权矢量，但不能保证此矢量就是分界矢量，下面引见一种方法可以检测迭代过程中能否线性可分。因最小平方误差法的J(W)的解为由于XW=b b应为正值c为矫正系数 当XWk-bk0 时 当XWk-bk 0 时bXbXXXTWT1|kkkkkbXWbXWcbb的增量为kkkbbbb 1前后两次迭代后，对的增量为其中bbk0kb2kkkbXWcbn引入误差矢量ekn ek=XWk-bk判别能否线性可分n所以J(W)的解为n

16、 初始条件 W1=X+b1并且b10n迭代时检测n 假设ek0时，XW b，系统线性可分，迭代收敛n 假设ek0时，XW b，系统线性不可分，迭代不收敛n我们用下面的例子来阐明ek的作用|kkkeeCb|11kKkkKkKKkeeXcWbXbXbbXbXW因此上式可以写成n例题：n 1=(0,0)T,(0,1)T 2=(1,0)T,(1,1)Tn解：正规化n 对2取负，有n n 111101110100X2/12/12/12/311111111211XXXTXTX的规范矩阵为x2x1x1x2x3x4取b1=(1,1,1,1)T c=1 W1=X+b1=(-2,0,1)T 所以W1为所求解 e1

17、=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=(-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)

18、，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 xj n = 1,2,li ij那么修正权向量Wjn(k+1)= Wj n(k) kxj 反复以上迭代,直到收敛,此法类似于固定增量法. 3.未知子类数目时的设计方法 当每类应分成的子类数也不知 时，这是最普通情况，方法很 多，举例如下。 树状分段线性分类器: 设两类情况1， 2。如下图 先用两类线性判别函数求 出

19、W1,超平面H1分成两个区 间,每个区间包含两类。 再利用二类分类求出W2(H2), W3(H3)。 假设每个部分仍包含两类, 继续上面的过程。n关键是初始权向量W1的选择:普通先选两类中间隔最近的两个子类的均值连线做垂直线作为H1(w1)初始值再求最优解。w1Tx0 w4Tx0 w3Tx0 w2Tx0 YNYYNN1 1 22 NY1 树状决策框图3-3 非线性分类器的设计n电位函数分类器,用非线性判别函数区分线性不可分的类别n电位函数分类器:每个特征作为一个点电荷,把特征空间作为能量场. 电位分布函数有下面三种方式。n n n n n n 为系数 xk为某一特定点n上图是这些函数在一维时的

20、图形，第三条是振荡曲线，n只需第一周期才是可用范围。|11 )K( 2.2kkxxXX|sin|)K( 3.22kkkxxxxXXxK(x)x321|exp- )K( 1.2kkxxXX电位函数算法的训练过程是在逐个样本输入时，逐渐积累电位的过程，对于二类问题，经过假设干循环后，如积累电位方程的运算结果能以正、负来区分二类样本，那么训练就可终了。算法: 设初始电位为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= 0n xk+11并且Kk(xk+1) 0时 rk+1= 1 n xk+12并且Kk(xk+1)0 不修正n K2(x)= K1(x) =exp-( x12+ x22)n 输入x3=(1,1)T x32代入n K2(x3)=exp-( 12+ 12)0 所以需求修正n K3(x)= K2(x)- K(xx3) =exp-( x12+ x22)n -exp-(x1-1)2