1、第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院1 3.1、线性判别函数与广义线性判别函数一、线性判别函数二、广义线性判别函数 3.2、感知器算法 3.3、最小平方误差算法 3.4、多类模式的分类迭代算法 3.5、势函数法第三章第三章 判别函数确定性分类器判别函数确定性分类器 第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院2v假设对一模式X已抽取n个特征，表示为：v模式识别问题就是根据模式X X 的n n个特征来判别模式属于1,2,m 类中的那一类。3-1线性判别函数与广义线性判别函数线性判别函数与广义线性判别函数 维空间的一个向量是n),.,(321
2、XxxxxXTn一、判别函数一、判别函数第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院3v例如下图：三类的分类问题，它们的边界线就是一个判别函数123边界2x1x一、一、判别函数（续）第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院4v判别函数包含两类：v一类 是线性判别函数：线性判别函数广义线性判别函数 （所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）分段线性判别函数*v另一类是非线性判别函数一、一、判别函数（续）第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院5二、二、线性判别函数v我们现在对两类问
3、题和多类问题分别进行讨论。v(一)两类问题 即:v v1.二维情况：取两个特征向量v 这种情况下 判别函数:2,),(21MTi2,)(2,1nxxXT32211wxwxw)x(g为坐标向量为参数，21,xxw第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院6v在两类别情况，判别函数 g(x)具有以下性质：v这是二维情况下判别由判别边界分类.v情况如图：1.二维情况21,0,0)(XXxgi不定Xxg,0)(32211)(wxwxwxg211x2x第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院72.n维情况v现抽取n个特征为：v判别函数：v另外一种表示
4、方法：TnxxxxX),.,(32112211.)(nnnwxwxwxwxg10nwXW为增值模式向量。，为增值权向量，TnnTnnxxxxXwwwwW)1,.,(),.,(21121XWxgT)(为模式向量。为权向量，TnTnxxxXwwwW),.,(),.,(21210第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院8v模式分类：v当 g1(x)=WTX=0 为判别边界。当n=2时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面，n3时，则判别边界为一超平面。21,0,0)(xxXWxgT2.n维情况第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息
5、工程学院9(二)多类问题。其它MiXXWxgiTii,.,2,1,0,0)(v对于多类问题，模式有 1,2,m 个类别。可分三种情况：1。第一种情况第一种情况 ：每一模式类与其它模式类：每一模式类与其它模式类间可用单个判别平面把一个类分开。间可用单个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：权向量。个判别函数的为第式中iwwwwWTininiii),.,(121)(ii第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院10v右图所示，每一类别可用单个判别边界与其它类别相分开。v如果一模式X属于1，则由图可清楚看出:这时g1(x)0而g2(x)0，g
6、3(x)0，g2(x)0，g3(x)0。则此模式X就无法作出确切的判决。如图中 IR1,IR3，IR4区域。v另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确 定区域。1.1.第一种情况（续）第一种情况（续）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院16v问当x=(x1,x2)T=(6,5)T时属于那一类v结论：g1(x)0，g3(x)g2(x)和
7、 g1(x)g3(x)。v假设判别函数为：v则判别边界为：23212211)(1)()(xxgxxxgxxxg012)()(02)()(012)()(21322131121xxxgxgxxxgxgxxgxg2)()(21xgxg)()(32xgxg)()(31xgxg133.第三种情况（续）第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院23v结论：不确定区间没有了，所以这种是最好情况。v用上列方程组作图如下：3.第三种情况（续）1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgx
8、g0)()(21xgxg0)()(31xgxg0.15.05.0第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院24v问假设未知模式x=(x1,x2)T=(1,1)T，则x属于那一类。v把它代入判别函数：v得判别函数为：v因为v所以模式x=(1,1)T属于 类。3.第三种情况（续）2)()(),()(1232xgxgxgxg1)(,1)(,0)(321xgxgxg).(),(),(321xgxgxg1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()
9、(31xgxg0.15.05.0第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院课堂思考（1）n在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多类情况2。问该模式识别问题所需判别函数的最少数目是多少？第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院26作业（1）n一个三类问题，其判别函数如下：g1(x)=-x1,g2(x)=x1+x2-1,g3(x)=x1-x2-11.设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。2.设为多类情况2，并使：g12(x)=g1(x),g13(x)=g2(x),g23(x
10、)=g3(x)。绘出其判别界面和多类情况2的区域。3.设g1(x),g2(x)和g3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院27 对于多类模式来说，如果能够采取上述三种情况中任一种线性判别函数来进行分类，则这些类别的模式就是线性可分的。多类模式在其特征空间的分布情况往往十分复杂，但只要它们的分布不重叠或重叠度不大，总可以确定其判别边界，而这些判别边界往往都是用曲线或曲面来描述，也就是说是非线性界面。那么，可将非线性函数通过映射，变换成线性判别函数。三、三、广义线性判别函数第三章第三章判别函数确定性分类器
11、判别函数确定性分类器遥感信息工程学院28kixfwwxfwxfwxfwxgkiiikkk,.,2,1,)()(.)()()(1112211v这样一个非线性判别函数通过映射，变换成线性判别函数。1)(,)(1xfxfki是单值函数式中v判别函数的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空间变换空间三、三、广义线性判别函数第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院290YWT判别平面：)(,)(.)()()(,.,0,0)()()(21212111增广模式向量。广义权向量其中：空间变换空间xfxfxfYwwwWxxYgYWxfwxgkkT
12、yxkiii21xaxorbxxbxa则则,v例：如右图。0bax二次判别函数212三、三、广义线性判别函数第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院302321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：v要用二次判别函数才可把二类分开：)1,1,1()25.0,5.0,1(),0,0,1(321yyy05.011y3y2yW平面oYWT212x三、三、广义线性判别函数第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院31015.012)(1,2112,1,12123212321321YWY
13、xxxxxgyyyxxYaaaWaaaxT空间判别平面：即：空间它的判别边界：设讨论在推出v从图可以看出：在阴影上面是1类，在阴影下面是2类，v结论：在X空间的非线性判别函数通过变换到Y空间成为线性的，但X变为高维空间05.011y3y2yW平面oYWT212x三、三、广义线性判别函数第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院32v一组模式样本不一定是线性可分的，所以需要研究线性分类能力的方法，对任何容量为N的样本集，线性可分的概率多大呢？v（如下图（a），线性不可分）v例：4个样本有几种分法。v图（b）直线把x1分开，每条直线可把4个样本分成1 2 类，4个样本分成
14、二类的总的可能的分法为24=16类，其中有二种是不能用线性分类实现的线性可分的是14。即概率为14/16。（a）x1x2x3x4 （b）四、二分法能力第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院33v结论：N个样本线性可分数目(条件：样本分布良好）：为特征数为样本数其中nNkNkNCkN,)!1(!)!1(1nkkNNnNCnNnND011,21,2),(若若v对N和n各种组合的D(N,n)值，表示在下表中，从表中可看出，当N，n缓慢增加时D(N,n)却增加很快。四、二分法能力v上例中：2031422,4kkCD第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信
15、息工程学院341234561222222244444436888884814161616165102230323232n),(nNDNnkkNNNnNCnNnNDnNP0111,21,12),(),(若若v线性可分概率：四、二分法能力第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院35强。说明样本少时二分能力范围，即在。时，线性可分概率为时，即值，对于任意。处出现明显的门限效应时，曲线急剧下降，在由当,1),(),1(22:)(21),()1(22:)(21 :)(nNPnNcnNPnNnbnav把上式用曲线表示成下图：图中横坐标用=N/n+1表示。v由图讨论：四、二分法能
16、力第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院36.2),1(2:)(,),1(22:)(0是最好情况即二分能力）的估计：个样本的线性可分性（对多线性可分能力越差。说明样本越线性可分概率急剧下降范围，即在nNNenNdv结论：在实际工作中，分类的训练非常重要，由已知样本来训练。因为已知样本有限，而未知样本无限。选择已知类别的训练样本数方法如下：四、二分法能力第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院37v：如果训练样本N 0 x1 检测(已知类别)W1 X1 W2 X2 Wn Xn Wn+10 -X1dW1-X2dW2-W3 0所以 g(x)=
17、WTX 0 其中W=(W1,W2,W3)T 为各模式增1矩阵111121212121ddccbbaaXXXXXXXXX利用方程组来求解权向量(续）为N*(n+1）矩阵N为样本数，n为特征数第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院45训练过程就是对已知类别的样本集求解权向量w，这是一个线性联立不等式方程组求解的过程。求解时：只有对线性可分的问题，g(x)=WTX才有解；联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解的问题；求解W的过程就是训练的过程。训练方法的共同点是，先给出准则函数，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数
18、。算法可以分为迭代法和非迭代法。利用方程组来求解权向量(续）第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院46二、梯度下降法迭代法求解不等式组WTX0，首先定义一个对错误分类敏感的准则函数J（w,x），再求J（w,x）的极值使w优化。因此求解权向量的问题就转化为对一准则函数求极值的问题。梯度下降法梯度下降法:准则函数J（w,x），梯度 从起始值W1开始，算出W1处准则函数的梯度矢量J(W1)，则下一步的w值为：W2=W1-1J(W1)W1为起始权向量 1为迭代步长 J(W1)为准则函数J(W1)为W1处的准则函数的梯度矢量wxwJwJ,)(第三章第三章判别函数确定性分类器
19、判别函数确定性分类器遥感信息工程学院47在第K步的时候Wk+1=Wk-kJ(Wk)k为正比例因子这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解矢量，k取值很重要：k太大，迭代太快，引起振荡，甚至发散。k太小，迭代太慢。应该选最佳k。迭代法（续）第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院48 目标函数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(W
20、k)21 对k求导数，并令导数为零有 最佳步长为k=|J|2/JTDJ这就是最佳k的计算公式，但因二阶偏导数矩阵D的计算量太大，因此此公式很少用。迭代法（续）-选最佳选最佳k k第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院49若令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为奇异时，无法用牛顿法。迭代法（续）第三章第三章判
21、别函数确定性分类器判别函数确定性分类器遥感信息工程学院50三三、感知器法感知器法感知器的原理结构为：感知器的原理结构为：“感知器感知器”一词借用于二十世纪五十年代中期到六十年一词借用于二十世纪五十年代中期到六十年代初期人们对一种分类学习机模型的称呼，它是针对仿代初期人们对一种分类学习机模型的称呼，它是针对仿生学领域中如何实现机器学习、模仿的问题而发展起来生学领域中如何实现机器学习、模仿的问题而发展起来的，它的一些数学概念后来在模式识别中起了很大的作的，它的一些数学概念后来在模式识别中起了很大的作用。用。第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院51通过对通过对W的调整
22、，可实现判别函数的调整，可实现判别函数g(x)=WTX RT 其中其中RT为响应阈值为响应阈值定义感知准则函数：只考虑错分样本定义感知准则函数：只考虑错分样本定义：定义：其中其中x0为错分样本为错分样本当分类发生错误时就有当分类发生错误时就有WTX 0,所以所以J(W)总是正值，错误分类愈少，总是正值，错误分类愈少，J(W)就愈小。就愈小。理想情况为理想情况为 即求最小值的问题。即求最小值的问题。0)(XXXWWJT0)(WJ三三、感知器法感知器法第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院52求最小值对求最小值对W求梯度求梯度代入迭代公式中代入迭代公式中Wk+1=Wk
23、-kJ 由由J(W)经第经第K+1次迭代的时候，次迭代的时候，J(W)趋于趋于0，收敛于所求的，收敛于所求的W值值0)(XXXWWJJ01XXXWWkkk即感知器迭代公式：三三、感知器法感知器法第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院53n感知器算法感知器算法：1.错误分类修正错误分类修正wk 如如wkTx0并且并且x1 wk+1=wk+kx 如如wkTx0并且并且x2 wk+1=wk-kx 2.正确分类正确分类，wk不修正不修正 如如wkTx0并且并且x1 如如wkTx0并且并且x2 wk+1=wk若对属于若对属于2 2类的模式样本乘以（类的模式样本乘以（-1 1
24、），感知器算法可以），感知器算法可以统一写为统一写为 001ktkkktxkwxkwxkwkwkw若三三、感知器法感知器法第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院54+-Hwk+1kxwk权值修正过程权值修正过程三三、感知器法感知器法第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院55 固定增量原则固定增量原则 k固定非负数固定非负数 绝对修正规则绝对修正规则 k 部分修正规则部分修正规则 k=02xxxwTT|xxxwTT|三三、感知器法感知器法nk选择准则选择准则 例：例：有四个模式样本，有四个模式样本，x，x属于属于1，x,x属于属于2，现
25、用感知器算法求判别函数中权向量的解现用感知器算法求判别函数中权向量的解 1=（x1,x2）=(1,0,1),(0,1,1)2=（x3,x4）=(1,1,0),(0,1,0)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院56解：先求四个样本的增值模式解：先求四个样本的增值模式 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)T k=1第一次迭代：第一次迭代：w1Tx1=(1,1,1,1)(1,0,1,1)T=30 所以不修正所以不修正 w1Tx2=(1,1,1,1)(0,1
26、,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)三三、感知器法感知器法第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院57第一次迭代后第一次迭代后,权向量权向量w3=(0,-1,1,-1),再进行第再进行第2,3,次次迭代，如下表迭代，如下表训练样本训练样本wkTx修正式修正式修正后的权值修正后的权值wk1迭代次数迭代次数x1 1 0 1 1x2 0
27、 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 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
28、 00 1 3 00 1 3 00 1 3 0 4三三、感知器法感知器法第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院58 直到在一个迭代过程中权向量相同，训练结束。直到在一个迭代过程中权向量相同，训练结束。w6=w=(0,-1,3,0)判别函数判别函数g(x)=-x2+3x3n感知器算法只对线性可分样本有收敛的解感知器算法只对线性可分样本有收敛的解,对非线性可对非线性可分样本集会造成训练过程的振荡分样本集会造成训练过程的振荡,这是它的缺点这是它的缺点.三三、感知器法感知器法第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院59n已知四个训练样本 w1=
29、(0,0),(0,1)w2=(1,0),(1,1)使用感知器固定增量法求判别函数 设w1=(1,1,1)k=1 要求编写程序上机运行，写出判别函数，并打出图表。作业（1）第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院60作业及编程（2）n用感知器算法求下列模式分类的解向量w:1:(0 0 0)T,(1 0 0)T,(1 0 1)T,(1 1 0)T2:(0 0 1)T,(0 1 1)T,(0 1 0)T,(1 1 1)Tn编写求解上述问题的感知器算法程序。第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院61作业（3）n采用梯度法和准则函数式中实数b0，
30、试导出两类模式的分类算法。第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院623.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)n 前述迭代求解权向量的方法是在模式前述迭代求解权向量的方法是在模式集线性可分的情况下采用的。但给出一集线性可分的情况下采用的。但给出一个模式集往往不能预先告知是否线性可个模式集往往不能预先告知是否线性可分，分，LMSE算法就是针对这一问题对准算法就是针对这一问题对准则函数引进最小平方误差而建立起来的，则函数引进最小平方误差而建立起来的，它可以在训练过程中判定训练模式集它可以在训练过程中判定训练模式集（样本集）是否线性可分，因而
31、可以判（样本集）是否线性可分，因而可以判断权向量求解的收敛性。断权向量求解的收敛性。第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院63前面我们研究了线性不等式方程组前面我们研究了线性不等式方程组g(x)=WTX0的解法。的解法。它们共同点是企图找一个权向量它们共同点是企图找一个权向量W，使错分样本最小。使错分样本最小。现在我们把不等式组变成如下形式：现在我们把不等式组变成如下形式：WTXi=bi0 则有联立方程则有联立方程XW=b 这是矛盾方程组，方程数大于未知这是矛盾方程组，方程数大于未知数，所以没有精确解的存在。数，所以没有精确解的存在。NnNNnNXXXXXXXXX
32、XX.21211121121N.2,1,XXXTX 令给定的任意正常数N.2,1,bbbTb 每个样本有n个特征3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院64定义误差向量：定义误差向量：e=XW-b0 把平方误差作为准把平方误差作为准则函数则函数 W的优化就是使的优化就是使J(W)最小。最小。求求J(W)的梯度并为的梯度并为0。NibiXiWTbXWeWJ1222|)(3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工
33、程学院65n一一.伪逆法伪逆法 求求J(W)对对W的梯度并令其为的梯度并令其为00)(22J(W)1bXWXXbiXiWTTiNi解上方程得解上方程得 XTXW=XTb这样把求解这样把求解XW=b的问题，转化为对的问题，转化为对XTXW=XTb求解，这一有名的方程最大好处是求解，这一有名的方程最大好处是因因XTX是方阵且通常是非奇异的，所以可以得是方阵且通常是非奇异的，所以可以得到到W的唯一解。的唯一解。3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院66只要计算出只要计算出X+就可以得到就可以得到W取：
34、取：最小平方误差法同最小平方误差法同FisherFisher法是一致的。法是一致的。bXbXXXTWT1的伪逆（规范矩阵）称为其中XXXXTXT1221.1/./NNNNNNNNb（MSE 解）解）其中其中N/N1有有N1个，个，N/N2有有N2个个3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院67n二二.梯度法梯度法(W-H算法算法(Widrow-Hoff)伪逆法得到的伪逆法得到的W解为：解为：W=X+b在计算在计算X+时，时，1 要求要求XTX矩阵为非奇异矩阵为非奇异 2 由于计算量太大而引入比较大
35、误差由于计算量太大而引入比较大误差 所以要用迭代法来求所以要用迭代法来求XXXTXT1伪逆计算量很大计算量很大3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院68求求J(W)的梯度的梯度J(W)=2XT(XW-b)代入迭代公式代入迭代公式 W1任意设定任意设定 Wk+1=Wk-kXT(XWk-b)此法可收敛于此法可收敛于W值。值。W满足满足:XT(XW-b)=0因此梯度算法不论因此梯度算法不论XTX是否奇异，总能产生一个解。是否奇异，总能产生一个解。若训练样本无限的重复出现，则简化为若训练样本无限的重复出
36、现，则简化为 W1任意任意 Wk+1=Wk+k(bk-WkTXk)Xk k随迭代次数随迭代次数k而减少，以保证算法收敛于满意而减少，以保证算法收敛于满意的的W值值k1K取为任意常数其中令11kk3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院69n三三.何何-卡氏法卡氏法(H-K算法算法(Wo-Kashyap)（判断迭代过程中是否线性可分）（判断迭代过程中是否线性可分）若训练样本线性可分时，感知器法可求出若训练样本线性可分时，感知器法可求出界面，但对不可分问题不收敛只能取平均。最界面，但对不可分问题不收敛
37、只能取平均。最小平方误差法不论样本是否线性可分都能给出小平方误差法不论样本是否线性可分都能给出一加权矢量，但不能保证此矢量就是分界矢量，一加权矢量，但不能保证此矢量就是分界矢量，下面介绍一种方法可以检测迭代过程中是否线下面介绍一种方法可以检测迭代过程中是否线性可分。性可分。3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院70n因最小平方误差法的因最小平方误差法的J(W)的解为的解为n因为因为XW=b b应应为正值为正值nc为矫正系数为矫正系数 当（当（XWk-bk）0 时时 当（当（XWk-bk）0 时时
38、bXbXXXTWT1|kkkkkbXWbXWcbb的增量为kkkbbbb 1前后两次迭代后，对的增量为其中bbk0kb2kkkbXWcb3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院71n引入误差矢量引入误差矢量ek ek=XWk-bk判断是否线性可分判断是否线性可分n所以所以J(W)的解为的解为 初始条件初始条件 W1=X+b1并且并且b10n迭代时检测迭代时检测 如果如果ek0时，时，XW b，系统线性可分，迭代收敛系统线性可分，迭代收敛 如果如果ek0时，时，XW b，系统线性不可分，迭代不收敛系
39、统线性不可分，迭代不收敛n我们用下面的例子来说明我们用下面的例子来说明ek的作用的作用|kkkeeCb|11kKkkKkKKkeeXcWbXbXbbXbXW因此上式可以写成因此上式可以写成3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院72n例题：例题：1=(0,0)T,(0,1)T 2=(1,0)T,(1,1)Tn解：正规化解：正规化 对对2取负，有取负，有 111101110100X2/12/12/12/311111111211XXXTXTX的规范矩阵为的规范矩阵为x2x1x1x2x3x43.33.3
40、、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院73取取b1=(1,1,1,1)T c=1 W1=X+b1=(-2,0,1)T 所以所以W1为所求解为所求解 e1=XW1-b1=0 系统线性可分系统线性可分01111102111101110100,1TWX因为因为3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院741-0 1-1-1-01 1 11 0 0X若四个样本变成：若四个样本变成：1=(0,0)T,(1,1)T 2=(0
41、,1)T,(1,0)T3.33.3、最小平方误差算法、最小平方误差算法(LMSE)LMSE)x2x1x1x2x3x4解：解：取取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 的值。的值。只要出现只要出现ek)d dj j(k(k)jiji则权向量不变，即则权向量不变，即 w wj j(k+1)=(k+1)=w wj j(k(k)j=1,2,)j=1,2,m m 如果其
42、中第如果其中第 个权向量使个权向量使d di i(k)d(k)dj j(k(k)，则相应的权向则相应的权向量应作调整，即量应作调整，即w wi i(k+1)=(k+1)=w wi i(k)+cx(k)+cxw wl l(k+1)=(k+1)=w wl l(k)-cx(k)-cx w wj j(k+1)=(k+1)=w wj j(k(k)j=1,2,)j=1,2,m m ji,jji,j这里这里c c为正的常数。为正的常数。算法中权向量的初始值算法中权向量的初始值w wi i(1)(i=1,2,(1)(i=1,2,m)m)一般可任意选取一般可任意选取 3.43.4、多类模式的分类器迭代算法多类模
43、式的分类器迭代算法 第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院79例：有三类模式，其训练样本为例：有三类模式，其训练样本为1 1(0 0)(0 0)t t 2 2(1 1)(1 1)t t 3 3(-1 1)(-1 1)t t 采用感知器算法，将模式样本首先写成增广向量形式，采用感知器算法，将模式样本首先写成增广向量形式，即即x x1 1=(0 0 1)=(0 0 1)t t x x2 2=(1 1 1)=(1 1 1)t t x x3 3=(-1 1 1)=(-1 1 1)t t取权向量初值取权向量初值w w1 1(1)=w(1)=w2 2(1)=w(1)=w3 3
44、(1)=(0 0 0)(1)=(0 0 0)t t，并令并令C=1C=1。第一次迭代（第一次迭代（K=1K=1），），以以x x1 1作为训练样本，有作为训练样本，有 011011011133122111xwdxwdxwdttt由于由于 ,而而d d1 1(1)d(1)d2 2(1),(1),d d1 1(1)d(1)d3 3(1),(1),故修改权向量故修改权向量w w1 1(2)=w(2)=w1 1(1)+x(1)+x1 1=(0 0 1)=(0 0 1)t tw w2 2(2)=w(2)=w2 2(1)-x(1)-x1 1=(0 0-1)=(0 0-1)t tw w3 3(2)=w(2)
45、=w3 3(1)-x(1)-x1 1=(0 0-1)=(0 0-1)t t11x3.43.4、多类模式的分类器迭代算法多类模式的分类器迭代算法 第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院80第二次迭代（第二次迭代（K=2K=2），），以以x x2 2作为训练样本，作为训练样本，因为因为d d2 2(2)d(2)d1 1(2),d(2),d2 2(2)d(2)d3 3(2)(2)，所以所以w w1 1(3)=w(3)=w1 1(2)-x(2)-x2 2=(-1=(-1 1 0)1 0)t tw w2 2(3)=w(3)=w2 2(2)+x(2)+x2 2=(1 1 0)
46、=(1 1 0)t tw w3 3(3)=w(3)=w3 3(2)-x(2)-x2 2=(-1=(-1 1-2)1-2)t t 122122122233222211xwdxwdxwdttt3.43.4、多类模式的分类器迭代算法多类模式的分类器迭代算法 第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院81第三次迭代（第三次迭代（K=3K=3），），以以x x3 3作为训练样本。作为训练样本。由于由于d d3 3(3)d(3)d1 1(3),d(3),d3 3(3)d(3)d2 2(3)(3)故故w w1 1(4)=w(4)=w1 1(3)-x(3)-x3 3=(0=(0 2-
47、1)2-1)t tw w2 2(4)=w(4)=w2 2(3)-x(3)-x3 3=(2 0-1)=(2 0-1)t tw w3 3(4)=w(4)=w3 3(3)+x(3)+x3 3=(-2 0-1)=(-2 0-1)t t 233033033333322311xwdxwdxwdttt3.43.4、多类模式的分类器迭代算法多类模式的分类器迭代算法 第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院82第四次迭代（第四次迭代（K=4K=4），），又轮到又轮到以以x x1 1作样本。作样本。因因d d1 1(4)d(4)d2 2(4),d(4),d1 1(4)d(4)d3 3(
48、4),(4),故故w w1 1(5)=w(5)=w1 1(4)+x(4)+x1 1=(0=(0 2 0)2 0)t tw w2 2(5)=w(5)=w2 2(4)-x(4)-x1 1=(2 0-2)=(2 0-2)t t w w3 3(5)=w(5)=w3 3(4)-x(4)-x1 1=(-2 0-2)=(-2 0-2)t t 144144144233222211xwdxwdxwdttt第五次迭代（第五次迭代（K=5K=5），），以以x x2 2作训作训练样本。练样本。由 于由 于 d d2 2(5)d(5)d1 1(5),(5),d d2 2(5)d(5)d3 3(5),(5),故按式（故按
49、式（3-5-23-5-2），），有有w1(6)=w1(5)w2(6)=w2(5)w3(6)=w3(5)455055255233222211xwdxwdxwdttt3.43.4、多类模式的分类器迭代算法多类模式的分类器迭代算法 第三章第三章判别函数确定性分类器判别函数确定性分类器遥感信息工程学院83第六次迭代（第六次迭代（K=6K=6），），以以x x3 3作作训练样本。训练样本。由于由于d d3 3(6)d(6)d1 1(6),d(6),d3 3(6)d(6)d2 2(6)(6)，故权向量不变：故权向量不变：w1(7)=w1(6)w2(7)=w2(6)w3(7)=w3(6)0664662663
50、33322311xwdxwdxwdttt第七次迭代（第七次迭代（K=7K=7），），以以x x1 1作训练样作训练样本。本。由于由于d1(7)d2(7)，d1(7)d3(7),故权故权向量亦不须改变。向量亦不须改变。277277077133122111xwdxwdxwdttt因为第五、六、七次迭代中已分别对因为第五、六、七次迭代中已分别对x x2 2,x,x3 3,x,x1 1作出正确判别作出正确判别,所以迭所以迭代到此停止，权向量的解为代到此停止，权向量的解为w w1 1=w=w1 1(7)=(0(7)=(0 2 0)2 0)t tw w2 2=w=w2 2(7)=(2 0-2)(7)=(2
