《模式识别导论.ppt》由会员分享,可在线阅读,更多相关《模式识别导论.ppt(49页珍藏版)》请在三一文库上搜索。
1、第三章 分类器的设计,线性分类器的设计 分段线性分类器的设计 非线性分类器的设计,3-1 线性分类器的设计,上一章我们论讨了线性判别函数形式为: g(x)=WTX +Wn+1 其中 X= (X1, X2Xn) n维特征向量 W= (W1, W2 Wn ) 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) 时 g(x)0 当 (Xc, Xd) 时 g(x)0 设 Xa = (X1a, X2a)T Xb = (X1b, X2b)T Xc = (X1c, X2c)T Xd = (X1d, X2d)T 判别函数可联立成: X1aW1+ X2aW2+ W30 X1b
3、W1+ X2bW2+ W30 X1cW1+ X2cW2+ W30 X1dW1+ 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 =
5、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/JTDJ 这就是最佳k的计算公式,但因二阶
6、偏导数矩阵D的计算量太大,因此此公式很少用。,若令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为错分样本 当分类发生错误时就有WTX 0, 所以J(
7、W) 总是正值,错误分类愈少, J(W)就愈小。 理想情况为 即求最小值的问题。,求最小值对W求梯度 代入迭代公式中Wk+1 = Wk-kJ 由J(W)经第K+1次迭代的时候,J(W)趋于0,收敛于所求的W值,W的训练过程: 例如:x1, x2, x31 作 x1, x3的垂直线可得解区(如图) 假设起始权向量w1=0 k = 1 x1, x2, x3三个矢量相加得矢量2,垂直于矢量2的超平面H将x3错分. x3与矢量2相加得矢量3,垂直于矢量3的超平面H1,将x1错分. 依上法得矢量4,垂直于矢量4做超平面, H2将x3错分 x3与矢量4相加得矢量5,矢量5在解区内,垂直于矢量5的超平面可以
8、把 x1, x2, x3分成一类 。,x1,x2,x3,2,H,3,H1,4,H2,5,W区间,感知器算法: 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) 解:先求四个样本的增值模式 x1
9、=(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 所以修正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
10、,次迭代 如下表,x1,x2,x3,x1,x2,x3,x4,1,1,1,直到在一个迭代过程中权向量相同,训练结束。 w6=w=(0,-1,3,0) 判别函数g(x)= -x2+3x3 感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.,线性不可分样本集的分类解(取近似解) 对于线性可分的样本集,可以用上述方法解到正确分 类的权向量。当样本集线性不可分时,用上述方法求权 值时算法不收敛。如果我们把循环的权向量取平均值作 为待求的权向量,或就取其中之一为权向量,一般可以 解到较满意的近似结果。 例:在样本 1: X1 =(0,2) X3 =(2,0) X5
11、 =(-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, 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把二类分
12、开,但其中x2 错分到1类, 而x5错分到2类,但大部分分类还是正确的。,作业:已知四个训练样本 w1=(0,0),(0,1) w2=(1,0),(1,1) 使用感知器固定增量法求判别函数 设w1=(1,1,1) k=1 要求编写程序上机运行,写出判别函数,并打出图表。,三 最小平方误差准则(MSE法)-非迭代法,前面我们研究了线性不等式方程组g(x) =WTX0的解法。 它们共同点是企图找一个权向量W,使错分样本最小。 现在我们把不等式组变成如下形式: WTXi=bi0 则有联立方程XW=b 这是矛盾方程组,方程数大于未知 数,所以没有精确解的存在。,每个样本有n个特征,给定的任意正常数,定
13、义误差向量:e=XW-b0 把平方误差作为目标函数 W的优化就是使J(W)最小。求J(W)的梯度并为0。 解上方程得 XTXW=XTb 这样把求解XW=b的问题,转化为对XTXW=XTb求解,这 一有名的方程,最大好处是因XTX是方阵且通常是非奇的, 所以可以得到W的唯一解。,MSE准则函数,只要计算出 就可以得到W 取: 最小平方误差法同Fisher法是一致的。,(MSE 解),其中N/N1有N1个,N/N2有N2个,四 韦霍氏法(LMS法)迭代法,上节得到MSE法的W解为:W=X+b 在计算X+时, 1 要求XTX矩阵为非奇异 2 由于计算量太大而引入比较大误差 所以要用迭代法来求。 求J
14、(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值,五 何卡氏法 (判断迭代过程中是否线性可分),若训练样本线性可分时,感知器法可求出界面,但对不可分问题不 收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出 一加权矢量,但不能保证此矢量就是分界矢量,下面介绍一种方法 可以
15、检测迭代过程中是否线性可分。 因最小平方误差法的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的作用,因此上式可以写成,例题: 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,
16、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 的值。 只要出现ek0 ,迭代就应立即停止。,x2,x1,1,1,x4,x1,x3,x2,六 Fisher分类准则,现在讨论通过 映射投影来降低 维数的方法。 X空间 X=-WTX-W
17、0 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空间的最好投影方向, 它实际是多维空间向一维空间的一种映射。,其中Sw为类内散布矩阵, Sb为类间散布矩阵,现在我们已把一个n维的问题转化为一维的问题。 现在一维空间设计 Fisher分类器:
18、 W0的选择,Yki表示第i类中第k个样本的投影值 N1为1样本数 N2为2样本数 当W0选定后,对任一样本X,只要判断Y=WTX0 则 X1; Y=WTX0 则X2。分类问题就解决了。,3-2 分段线形分类器的设计,先求子类的权向量Wi l,再求总的权向量Wi 1. 已知子类划分时的设计方法 把每一个子类作为独立类,利用每个子类的训练样本, 求每个子类的线性判别函数,总的判别函数就可获得。 子类的划分可用以下方法: 用先验知识直接划分 用聚类分析,聚成多个子类 2.已知子类的数目的设计方法 设各个子类的初始权向量:Wi 1 , Wi 2 Wi Li i = 1,2,M Wi中有Li个子类 若
19、第K步迭代时j 类样本Xj 同j类某个子类的权向量 Wj n (k)的内积值最大,即Wj n (k)l xj = max Wj n (k). xj n = 1,2,Lj,并且满足条件Wj n (k) xj Wi n (k)lxj 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) xj n =
20、1,2,Li ij 则修改权向量Wjn(k+1)= Wj n(k) kxj 重复以上迭代,直到收敛,此法类似于固定增量法.,3.未知子类数目时的设计方法 当每类应分成的子类数也不知 时,这是最一般情况,方法很 多,举例如下。 树状分段线性分类器: 设两类情况1, 2。如图所示 先用两类线性判别函数求 出W1,超平面H1分成两个区 间,每个区间包含两类。 再利用二类分类求出W2(H2), W3(H3)。 如果每个部分仍包含两类, 继续上面的过程。,关键是初始权向量W1的选择:一般先选两类中距离最近 的两个子类的均值连线做垂直线作为H1(w1)初始值再求最优 解。,3-3 非线性分类器的设计,电位
21、函数分类器,用非线性判别函数区分线性不可分的类别 电位函数分类器:每个特征作为一个点电荷,把特征空间作为能量场. 电位分布函数有下面三种形式。 为系数 xk为某一特定点 上图是这些函数在一维时的图形,第三条是振荡曲线, 只有第一周期才是可用范围。,x,K(x),x,3,2,1,电位函数算法的训练过程是在逐个样本输入时,逐渐积 累电位的过程,对于二类问题,经过若干循环后,如积 累电位方程的运算结果能以正、负来区分二类样本,则 训练就可结束。 算法: 设初始电位为K0(x)=0 1.输入样本x1计算积累电位K1(x) 若x1 K1(x)= K0(x)+K(xx1) 若x2 K1(x)= K0(x)
22、-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)有三种情况: 1.若xk+11并且Kk(xk+1)0或xk+12 并且Kk(xk+1)0时 rk+1
23、= 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-( 02+ 22)0 不修正 K2(x)= K1(x
24、) =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,g(x)0,g(x)0,g(x)0,g(x)0,输入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
25、代入 K4(x5)=1-e-2- e-40 K5(x)= 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),同理得到: 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 上边的非线性判别函数形成的边界如图所示。虽然它 可以把线性不可分的样本分开,但当样本很多时,使方 程的项数太多,增大计算量。,
链接地址:https://www.31doc.com/p-8792020.html