判别函数及几何分类法课件

1、第第3章章 判别函数及几何分类法判别函数及几何分类法3.1 判别函数判别函数3.2 线性判别函数线性判别函数3.3 广义线性判别函数广义线性判别函数3.4 线性判别函数的几何性质线性判别函数的几何性质3.5 感知器算法感知器算法3.6 梯度法梯度法3.7 最小平方误差算法最小平方误差算法3.8 非线性判别函数非线性判别函数聚类分析法（第七章）判决函数法几何分类法确定性事件分类（第三章）概率分类法随机事件分类（第二章）线性判决函数法统 计 决 策 方 法非线性判决函数法复习与引申：复习与引申：模式识别统计若分属于1，2的两类模式可用一方程d(X) =0来划分，那么称d(X) 为判别函数，或称判决

2、函数、决策函数。3.1 判别函数判别函数(discriminant function) 直接用来对模式进行分类的准则函数。例：一个二维的两类判别问题，模式分布如图示，这些分属于1，2两类的模式可用一直线方程 d(X)=0来划分。0)(32211wxwxwd X21,xx为坐标变量，321,www为方程参数。式中：图3.2 两类二维模式的分布1判别函数的定义判别函数的定义若 ，则若 ，则 类；若 ，则 类；0)(Xd1X0)(Xd2X0)(Xd21XX或 或拒绝将某一未知模式 X 代入：维数=3时：判别边界为一平面。维数3时：判别边界为一超平面。32211)(wxwxwdX d(X) 表示的是一

3、种分类的标准，它可以是1、2、3维的，也可以是更高维的。 判别界面的正负侧，是在训练判别函数的权值时确定的。2判别函数正负值的确定判别函数正负值的确定图3.3 判别函数正负的确定1）判决函数d(X)的几何性质。它可以是线性的或非线性的函 数，维数在特征提取时已经确定。如：已知三维线性分类 判决函数的性质就确定了判决函数 的形式：4332211)(wxwxwxwdX3. 确定判别函数的两个因素确定判别函数的两个因素例：非线性判决函数2）判决函数d(X)的系数。用所给的模式样本确定。3.2 线性判别函数线性判别函数3.2.1 线性判别函数的一般形式线性判别函数的一般形式将二维模式推广到n维，线性判

4、别函数的一般形式为：T1 122nn00 dw xw xw xwwXW X (3-2)T21,.,nxxxX式中：1 122nn012T120 11nndw xw xw xwxxwwwwxL LMXW XT120,.,nwwwwWT211 ,.,nxxxX增广向量的形式：式中：为增广权向量，为增广模式向量。T12,.,nw wwW权向量3.2.2 线性判别函数的性质线性判别函数的性质21T, 0, 0)(XXXWX若若d1. 两类情况d(X) = 0：不可判别情况，可以或拒绝或21XX） 对M个线性可分模式类，1， 2， M，有三种划分方式：2. 多类情况 ii两分法ji两分法ji两分法特例i

5、i两分法(1)多类情况1： 用线性判别函数将属于i类的模式与其余不属于i类的模式分开。将某个待分类模式 X 分别代入 M 个类的d (X)中，若只有di(X)0，其他d(X)均0的条件超过一个，或全部的di(X)dj(X)就相当于多类情况2中的dij(X) 0。ji两分法特例(3)多类情况3： 因此对具有判别函数 Midii, 1,)(TXWX的M类情况，判别函数性质为： ijiMjiijddXXX若, 2 , 1,;,)(或： ikiMkddXXX若, 1,max)( 识别分类时： 判别界面需要做差值。对i类，应满足： di其他所有dj2313dddd0122x1x 0)(21-XdXd-

6、0)(31-XdXd 0)(32-XdXd3212dddd3121dddd3 除边界区外，没有不确定区域。特点： 是第二种情况的特例。由于dij(X)= di (X) dj(X) ，若在第三种情况下可分，则在第二种情况下也可分，但反过来不一定。2313dddd0122x1x 0)(21-XdXd- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd3 把 M 类情况分成了(M -1)个两类问题。并且 类的判别界面全部与 类的判别界面相邻（向无穷远处延伸的区域除外）。iijj特别的定义23212211)(1)()(xdxxdxxd-XXX例例3.5 一个三类模式（M=3）

7、分类器，其判决函数为： 试判断X0=1,1T属于哪一类，且分别给出三类的判决界面。解： 2003020102030201)()()()(1)(1111)(011)(-XXXXXXXXddddddd012)()(121-xddXX02)()(2131-xxddXX012)()(112-xddXX012)()(2132-xxddXX)()(1331XXdd-)()(2332XXdd-类的判决函数：1判决界面如图所示。类的判决函数：2类的判决函数：3- 0)(21-XdXd2313dddd0.5x2- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd110.5123x1-O

8、2x1x 0)(21-XXdd- 0)(31-XXdd 0)(32-XXdd例例3.6 已知判决界面的位置和正负侧，分析三类模式的分布 区域 。132(1) 明确概念：线性可分。 一旦线性判别函数的系数Wk被确定以后，这些函数就可以作为模式分类的基础。3. 小结小结(2) 分法的比较：jiii与 对于M类模式的分类， 两分法共需要M个判别函数，但 两分法需要M(M-1)/2个。当时M3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。 jiii原因： 一种类别模式的分布要比M-1类模式的分布更为聚集， 分法受到的限制条件少，故线性可分的可能性大。jiii两分法 全

9、部不属任何类 IR，可能 属于1或3 1230)(2Xd0)(3XdIR，可能 属于3或2 -0)(1Xd0, 0312ddd0, 0321ddd0, 0,321dddIR，可能属于1或2 0, 0213ddd2x1x若只有di(X)0，其他d(X)均 0时，原点在超平面的正侧；wn+1 Tik XW()=1+kW( )ickXW+( )kW( )0Tik XW若( )0Tik XW若（3）分析分类结果：只要有一个错误分类，回到（2），直至 对所有样本正确分类。 分类正确时，对权向量“赏”这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”对其修改，向正确的方向转换。感知器算法是一种赏罚过

10、程：感知器算法是一种赏罚过程：3. 收敛性收敛性收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。可以证明感知器算法是收敛的。收敛条件：模式类别线性可分。 例例3.8 已知两类训练样本解：所有样本写成增广向量形式； 进行规范化处理，属于2的样本乘以(1)。T11 , 0 , 0XT21 , 1 , 0XT31, 0 , 1 -XT41, 1, 1-X用感知器算法求出将模式分为两类的权向量解和判别函数。 :1T10,0X:2T21 ,0XT30, 1XT41 , 1X任取W(1)=0，取c=1，迭代过程为：第一轮： 0,1000 , 0 , 0) 1 (

11、1TXWT11 , 0 , 0) 1 () 2(, 0XWW故1,1101 , 0 , 0)2(2TXWT1 , 0 , 0) 2() 3 (, 0WW故-1,1-01-1 , 0 , 0)3(3TXWT30 , 0 , 1-) 3 () 4(, 0XWW故1,1-1-1-0 , 0 , 1-)4(4TXWT0 , 0 , 1-) 4() 5 (, 0WW故有两个WT(k)Xi 0的情况（错判），进行第二轮迭代。T11T1 , 0 , 1-)5()6(,00)5(XWWXW故T2T1 , 0 , 1-(6)7(,01)6(WWXW故T33T0 , 0 , 2-)7()8(,00)7(XWWXW

12、故T4T0 , 0 , 2-)8()9(,02)8(WWXW故第二轮：T11T1 , 0 , 2-)9()10(,00)9(XWWXW故(10)11(,01)10(2TWWXW故)11()12(,01)11(3TWWXW故)12()13(,01)12(4TWWXW故第三轮：)13()14(,01)13(1TWWXW故(14)15(,01)14(2TWWXW故)15()16(,01)15(3TWWXW故)16()17(,01)16(4TWWXW故第四轮：T1 , 0 , 2-W该轮迭代的分类结果全部正确，故解向量1+2=)(1xd X相应的判别函数为： 当c、W(1)取其他值时，结果可能不一样，

13、所以感知器算法的解不是单值的。判别界面d(X)=0如图示。采用多类情况3的方法时，应有：4. 感知器算法用于多类情况感知器算法用于多类情况Mj, 1= iX ,)(ijddjiXX若，则 Midi, 1,对于M类模式应存在M个判决函数：算法主要内容：M,21设有 M 种模式类别： Mjj, 1,1W设其权向量初值为： 第k次迭代时，一个属于i类的模式样本 X 被送入分类器，计算所有判别函数训练样本为增广向量形式，但不需要规范化处理不需要规范化处理。 分二种情况修改权向量： Mjkkdjj, 1,TXW 若第l个权向量使 ，则相应的权向量作调整，即： -lijkkckkckkjjllii,111

14、WWXWWXWW 可以证明：只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法收敛。， c为正的校正增量例例3.9 设有三个线性可分的模式类，三类的训练样本分别为 若 则权向量不变； Mjijkdkdji, 2 , 1;, Mjkkjj, 2 , 1,1WW( )( )kdkdli T33T22T111 , 11 , 10 , 0-XXX：；：；：现采用多类情况3的方式分类，试用感知器算法求出判别函数。 解：增广向量形式：T3T2T11,1, 1,1,1, 1,1 , 0 , 0-XXX注意，这里任一类的样本都不能乘以（1）。任取初始权向量T3210 , 0 , 0) 1 () 1

15、() 1 (WWW；c=1 第一次迭代： 0111T11XWd 0111T22XWd 0111T33XWd三个权向量都需要修改：11X 1121dd 1131dd，但且不成立，T1111 , 0 , 0) 1 ()2(XWWT1221, 0 , 0) 1 ()2(-XWWT1331, 0 , 0) 1 ()2(-XWW第二次迭代： 1222T11XWd 1222T22-XWd 1222T33-XWd22X 2212dd 2232dd，但且不成立，修改权向量：T2110 , 1, 1)2()3(-XWWT2220 , 1 , 1)2() 3(XWWT2332, 1, 1)2()3(-XWW第三次

16、迭代： 修改为权向量。33X 3313dd 3323dd，但且不成立， 以上进行的一轮迭代运算中，三个样本都未正确分类，进行下一轮迭代。第四次迭代： 在第五、六、七迭代中，对所有三个样本都已正确分类。权向量的解：T11110 , 2, 0)5()6()7(-WWWWT22222, 0 , 2)5()6()7(-WWWWT33332, 0 , 2)5()6()7(-WWWW判别函数：212)(xd-X22)(12-xdX22)(13-xdX 设函数f (Y)是向量 的函数，则f (Y)的梯度定义为：3.6 梯度法梯度法T21,nyyyY T21,ddnyfyfyfffYYY梯度的方向方向是函数

17、f (Y) 在Y点增长最快的方向，梯度的模模是f (Y)在增长最快的方向上的增长率 (增长率最大值)。1. 梯度概念梯度概念 梯度向量的最重要性质之一：指出函数梯度向量的最重要性质之一：指出函数 f 在其自变量增加在其自变量增加时，增长最快的方向。时，增长最快的方向。3.6.1 梯度法基本原理梯度法基本原理显然：负梯度指出了最陡下降方向。梯度算法的依据。即：2. 梯度算法梯度算法 设两个线性可分的模式类1和2的样本共N个，2类样本乘(-1)。将两类样本分开的判决函数d(X)应满足： 梯度算法的目的仍然是求一个满足上述条件的权向量，主导思想是将联立不等式求解W的问题，转换成求准则函数极小值的问题

18、。Nidii, 2 , 10)(TXWXN个不等式 准则函数的选取原则： 具有唯一的最小值，并且这个最小值发生在W TXi0时。 用负梯度向量的值对权向量W进行修正，实现使准则函数达到极小值的目的。 基本思路： 定义一个对错误分类敏感的准则函数J(W, X)，在J的梯度方向上对权向量进行修改。一般关系表示成从W(k)导出W(k+1)：其中c是正的比例因子。 梯度法求解步骤： JckJckk-WWW)(1 kJckkWWWXWWW-,1（1）将样本写成规范化增广向量形式，选择准则函数，设置初始权向量W(1)，括号内为迭代次数k=1。 权向量修正为：)(,)(kiJkJWWWXW )(1kJckk

19、-WW迭代次数k加1，输入下一个训练样本，计算新的权向量，直至对全部训练样本完成一轮迭代。 （3）在一轮迭代中，如果有一个样本使 ，回到(2)进行下 一轮迭代。否则， W不再变化，算法收敛。0J（2）依次输入训练样本X。设第k次迭代时输入样本为Xi，此时 已有权向量W(k)，求 ：)(kJ例例3.10 选择准则函数 ， ，简单地考虑X为一维增广模式的情况X=1，此时W=w，两者均为标量，XWXWXWTT),(-JwwJ-),(XW错误分类时： 22,1-wwwwwJJXXWW0010TwwXW ckckk221-WWW， 对权向量校正。 Jckk-WW1正确分类时：0010TwwXW0-www

20、J kckkWWW-01， 对权向量不做修正。说明： 随着权向量W向理想值接近，准则函数关于W的导数 ( )越来越趋近于零，这意味着准则函数J 越来越接近最小值。当 最终 时，J达到最小值，此时W不再改变，算法收敛。J0J 将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题。 kJckJckkWWWXWWWW-,1 c) 梯度算法是求解权向量的一般解法，算法的具体计算形式取决于准则函数J(W, X)的选择，J(W, X)的形式不同，得到的具体算法不同。a) b) c值的选择很重要，如c值太小，收敛太慢；但若太大，搜索又可能过头，甚至引起发散。3.6.2 固定增量法固定增量法准则函

21、数：求W(k)的递推公式：1. 求J的梯度?,WXWJJ方法：函数对向量求导=函数对向量的分量求导，即T1,nxfxffX该准则函数有唯一最小值“0”，且发生在 的时候。 0TXW设 ，T211 ,nxxxXT121,nnwwwwWXWXWXWTT21),(-J部分：niniiwxw11TWWXWT111111,iniininiikniniiwxwwwxwwwxwwXT11 ,nkxxxnnddddIXXXXTT 111111TnnnnXXIWXWXWT首先求另：矩阵论中有XWXWXWTT21),(-JXXWXWXW-Tsgn21,JJ其中 -0, 10, 1sgnTTTXWXWXW若若 由的

22、结论 有： XWXWTXWXWWXWXWTTT0时，XWXWWXWXW-TTT0时，XXWWXWTTsgnXWXWXWTT21),(-J kJckJckkWWWXWWWW-,12. 求W(k+1)将 代入得： XXWXWW-)(sgn211Tkckk 0)(,0)(, 0TTXWXXWWkckk若若 XWXXW)(sgn2Tkck-XXWXWXW-Tsgn21,JJ 由此可以看出，感知器算法是梯度法的特例。即：梯度法是将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题，将原来有多个解的情况，变成求最优解的情况。上式即为固定增量算法，与感知器算法形式完全相同 。 0)(,0)(,

23、01TTXWXXWWWkckkk若若即： 0, 0,1TTiiikckkkkXWXWXWWW若若只要模式类是线性可分的，算法就会给出解。*argmax (,)J KwwwFisher判别x1x2w1H: g=0w2Fisher准则的描述：用投影后数据的统计性质均值和离散度的函数作为判别优劣的标准。Fisher判别1 1,2iix KiiNmx()() , 1,2iTiiii-xSxmxm12wSSS1212()()Tb-Smmmm离散度矩阵在形式上与协方差矩阵很相似，但协方差矩阵是一种期望值，而离散矩阵只是表示有限个样本在空间分布的离散程度1, 1,2iiyimyiN2() , 1,2iiiy

24、Symi-12wSSS212()bSmm-以上定义描述d维空间样本点到一向量投影的分投影的分散情况散情况，因此也就是对某向量w的投影在w上的分布。样本离散度的定义与随机变量方差相类似 12wSSS2121212()( )bFSmmJwSSSS-22()()()()iiiiiyTTix KTTiiix KTSSym-w xw mwwxmxwwm1212()TTwSSSSSwwww2212121212()()()()TTTbTbTSSmm-w mw mwwmmmmww12( )TbbFTwSSJwSSSwwww*argmax( )FJwww*112()wS-wmmm1-m2是一向量，对与(m1-m

25、2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对m1-m2 向量按Sw-1作一线性变换，从而使Fisher准则函数达到极值点1202mmw1122012N mN mwmNN1212012ln()/()22PPmmwNN-0102TTywyww xxw xx12( )TbbFTwSSJwSSSwwwwc0TwSww令 Lagrange:( , )()TTbwLSSc-wwwww定义函数 ( , ):0bwLSS-wwww令 1wbSS-ww111212112()()(

26、)TwbwwSSSSR-wwmmmmwmm*111212()()wwRSS-wmmmm*112()wS-wmm3.7 最小平方误差算法最小平方误差算法（least mean square error, LMSE；亦称Ho-Kashyap算法） 上述的感知器算法、梯度算法、固定增量算法或其他类似方法，只有当模式类可分离时才收敛，在不可分的情况下，算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛时，造成不收敛现象的原因分不清，有两种可能：a) 迭代过程本身收敛缓慢b) 模式本身不可分对可分模式收敛。对于类别不可分的情况也能指出来。LMSE算法特点：1. 分类器的不等式方程分类器的不等式方程-N

27、nNnnNNnnnnnnwxwxwxwwxwxwxwwxwxwxwXXX对对对00012211212222211111122111类1类20TiXW 两类分类问题的解相当于求一组线性不等式的解。如果给出分属于 ， 两个模式类的训练样本集 ，应满足：12, 2 , 1,NiiX其中，Xi是规范化增广样本向量， 。T21 1,iniiixxxX上式分开写为：写成矩阵形式为 ： 令N (n+1) 的长方矩阵为X，则 , 变为：0TiXW0XW0-11112112122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx-NnNnnNNnnnnnnwxwxwxwwxwxwx

28、wwxwxwxwXXX对对对00012211212222211111122111类1类21,.iNL式中：T121,nnwwwwW121TT1TT2T1-nNNNiXXXXXX0XW0-11112112122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx0为零向量 感知器算法是通过解不等式组 ，求出W。0XW2. LMSE算法算法1) 原理原理的求解。式中： 两式等价。T21,NibbbbB为各分量均为较小正值的矢量。LMSE算法把对满足 XW 0 的求解，改为满足BXW 在方程组系数矩阵中当行数列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通

29、常训练样本数N总是大于模式的维数n，因此方程的个数(行数)模式向量的维数(列数)，是矛盾方程组，只能求近似解W*，即说明：极小-BXW * LMSE算法的出发点：选择一个准则函数，使得当J达到最小值时，XW=B 可得到近似解（最小二乘近似解）。 LMSE算法的思路：BWBXWXW、通过求准则函数极小找求解对求解对 0转化为转化为准则函数定义为： 221,BXWBXW-J“最小二乘”： 最小：使方程组两边误差最小， 也即使J最小。 二乘：次数为2，乘了两次最小平方（误差算法）1111121111221111111111-NNinnnnNNnNininnbbbwwwwxxxxxxxxBXW-NNi

30、iNNnnNnNinnininnnbbbbwwxwxbwwxwxbwwxwxXWXWXWTT11T1111111111111向量各分量的平方和向量各分量的平方和-22BXW-NiiiNNbbb12T2T211T2XWXWXWBXW考察向量(XWB) 有：可以看出： 当函数J达到最小值，等式XW=B有最优解。即又将问题转化为求准则函数极小值的问题。 因为J有两个变量W和B，有更多的自由度供选择求解，故可望改善算法的收敛速率。21T22121,-NiiibJXWBXWBXWXW=B 的近似解也称“最优近似解”： 使方程组两边所有误差之和最小（即最优）的解。准则函数：BXBXXXWBXXWXBXWX

31、#T1TTTT0-使J 对W求最小，令 ，得：2) 推导推导LMSE算法递推公式算法递推公式与问题相关的两个梯度： BXWXW-TJBXWBXWB-21J (3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求递推公式：(1) 求W 的递推关系X为N(n+1)长方阵，X#为(n+1) N 长方阵。T1T#XXXX-称为X的伪逆，式中： (3-45)0WJ(2) 求B(k+1)的迭代式 kJckkBBBBB-1 kkkkckkBXWBXWBB-21(3-46)代入，得cc 2 kkkeBXW- 令，定义(3-49) kkckkeeBB1(3-50)(3-46)BXWBXWB-2

32、1J利用梯度算法公式有： kJckkWWWXWWW-,1 kkBBXXXXX-#T1T kckckeXeXBX#(3) 求W(k+1)的迭代式将(3-50)代入(3-47)式W=X#B 有： kkckkkeeBXBXW#11 kkkBXWXXXeX-T1T#=0 kckeXW#0 kkkeBXW-(3-49) kkckkeeBB1(3-50) 11#BXW kkkBXWe- kckkeXWW#1 kkckkeeBB111#kkBXW总结：设初值B(1)，各分量均为正值，括号中数字代表迭代次数 。W(k+1)、B(k+1)互相独立，先后次序无关。求出B，W后，再迭代出下一个e，从而计算出新的B，

33、 W。 11#BXW kkkBXWe- kkckkeeBB1或另一算法：先算B(k+1)，再算W(k+1)。3）模式类别可分性判别）模式类别可分性判别 如果e(k)0 ，表明XW(k)B(k) 0， 隐含有解。继续迭代， 可使e(k) 0 。 如果e(k)0，有解。分以下几种情况：111-kkkBXWe kkWW1 kkee1 kkBB111#kkBXW情况分析： kkckkeeBB1e(k)0，线性可分，若进入(5)可使e(k) 0 ，得最优解。如果e(k)0，线性不可分，停止迭代，无解，算法结束。如果e(k)=0，线性可分，解为W(k)，算法结束。否则，说明e(k)的各分量值有正有负，进入

34、(5)。 kckkeXWW#1 kkckkeeBB1 kkckkeeBB111#kkBXW(5) 计算W(k+1)和B(k+1)。方法1：分别计算方法2：先计算再计算迭代次数k加1，返回(4)。3. 算法特点算法特点(1) 算法尽管略为复杂一些，但提供了线性可分的测试特征。(2) 同时利用N个训练样本，同时修改W和B，故收敛速度快。(3) 计算矩阵 复杂，但可用迭代算法计算。1T-XX例3.11 已知两类模式训练样本： TT11 ,0,0,0:TT21 ,1,0,1:试用LMSE算法求解权向量。-111101110100X解：(1) 写出规范化增广样本矩阵： Aij是aij的代数余子式，注意两

35、者的行和列的标号互换。 T1T#XXXX- (2) 求伪逆矩阵-422221212111101110100111110101100TXX*11AAA-求逆矩阵：333231232221131211aaaaaaaaaA332313232212312111*AAAAAAAAAA若，则 |A|A的行列式A*A的伴随矩阵422221212TXX 划去aij所在的行和列的元素，余下元素构成的行列式做aij的余子式，记作Mij ，将 叫做元素aij的代数余子式。例：代数余子式定义： ijijAM ji1- 323112113231121132231-aaaaaaaaA-322240204413222402

36、041T1TXXXX44884416422221212T-XX行列式: 333231232221131211aaaaaaaaaA*11AAA-1113222222224111111010110032224020441#X -1024084111111113222222224111#BXW(3) 取 和 c=1 开始迭代： T1 , 1 , 1 , 11 B -0000111111111111102111101110100111BXWe 121-xd X解为 W(1) ，判断函数为：T1T#XXXX-图示如下：例3.12 已知模式训练样本： ，TT11 , 1,0,0:TT20, 1,1 ,0:

37、-101110111100X( 2) 求 ：T1T#XXXX-11132222222241#X解：(1) 规范化增广样本矩阵：(3) 取 和c=1，迭代： T1 , 1 , 1 , 11 B用LMSE算法求解权向量。 T#00011BXW TTT111111110000111-BXWe e(1)全部分量为负，无解，停止迭代。为线性不可分模式。 小结：小结：(1) 感知器法、梯度法、最小平方误差算法讨论的分类算法都是通过模式样本来确定判别函数的系数，所以要使一个分类器设计完善，必须采用有代表性的数据，训练判别函数的权系数。它们能合理反映模式数据的总体。(2) 要获得一个有较好判别性能的线性分类器

38、，所需要的训练样本的数目的确定。用指标二分法能力N0来确定训练样本的数目：通常训练样本的数目不能低于N0 ，选为 N0的510倍左右。二维：不能低于6个样本，最好选在3060个样本之间。三维：不能低于8个样本，最好选在4080个样本之间。120nNn为模式维数如3.8 非线性判别函数非线性判别函数3.8.1 分段线性判别函数分段线性判别函数线性判别函数的特点：形式简单，容易学习； 用于线性可分的模式类。非线性判别函数：用于线性不可分情况。分段线性、超曲面。 特点基本组成为超平面。* 相对简单；* 能逼近各种形状的超曲面。1一般分段线性判别函数一般分段线性判别函数设有M类模式，将i类（i=1,2

39、, ,M）划分为li个子类：Miiliiii, 2 , 1,:21其中第n个子类的判别函数： Milndinini, 2 , 1;, 2 , 1)()(TXWXi类的判别函数定义为：, 2 , 1),(max)(iniilnddXXM类的判决规则： , 2 , 1),(max)(MiddijXXjX若，则用各类判别函数进行分类判决实际是用各类选出的子类判别函数进行判决判别面由各子类的判别函数决定若i类的第n个子类和j类的第m个子类相邻，判别界面方程为：)()(XXmjnidd子类之间的判别界面组成各类之间的判别界面类间判别界面分段线性2基于距离的分段线性判别函数基于距离的分段线性判别函数设 1

40、类均值向量：11111NiiNXM21221NiiNXM2类均值向量：N1，N2：两类样本数。 任一模式X到M1和M2的欧氏距离平方：211|)(MXX-d222|)(MXX-d判决规则：)()(21XXdd1X若， 则)()(12XXdd2X若， 则判别界面方程：2221|MXMX-1）最小距离分类器化简得：0)()(21T12T2T21-MMMMXMM X的线性方程，确定一个超平面。 最小距离分类器 2）分段线性距离分类器 设：M类模式，其中i类划分为li个子类，第n个子类的均值向量为 。每个子类的判别函数：niMMilndinini, 2 , 1;, 2 , 1,|)(2-MXX每类的判

41、别函数： , 2 , 1),(min)(iniilnddXX判决规则：, 2 , 1),(min)(MiddijXX若jX则Mi, 2 , 13.8.2 分段线性判别函数的学习方法分段线性判别函数的学习方法1已知子类划分时的学习方法已知子类划分时的学习方法* 每个子类看成独立的类；* 在一类范围内根据多类情况3，学习各子类判别函数；* 继而得到各类判别函数。 2已知子类数目时的学习方法已知子类数目时的学习方法 用类似于固定增量算法的错误修正算法学习分段线性判别函数 3未知子类数目时的学习方法未知子类数目时的学习方法树状分段线性分类器 树状分段线性分类器判别函数的学习及分类过程 暂停点暂停点：，

42、； ：，3.8.3 势函数法势函数法1. 势函数概念势函数概念划分属于1和2类模式样本： 样本是模式空间中的点， 将每个点比拟为点能源，在点上势能达到峰值，随着与该点距离的增大，势能分布迅速减小。 1类样本势能为正势能积累形成 “高地”； 2类样本势能(-1)势能积累形成 “凹地”； 在两类电势分布之间，选择合适的等势面（如零等势面），即可认为是判别界面了。借用点能源的势能概念解决模式分类问题。 kx),(kxxKxO一个样本xk的势能分布用势函数K( x , xk )表示)(xKxO12积累势函数一维情况示例2. 势函数法判别函数的产生势函数法判别函数的产生依次输入样本，利用势函数逐步积累势

43、能的过程。 判别函数由模式空间中样本向量 的势函数K(X, Xk)累加产生，分类器计算积累势K(X)，最后取d(X)=K(X)。21,2, 1,kkkXX且设初始积累势函函数 ，下标为迭代次数。0)(0XK势函数法：势函数法：第一步：加入训练样本 X1 ，K1(X) 描述了加入第一个样本后的边界划分。-211011101),()(),()()(XXXXXXXXX若若KKKKK第二步：加第二个训练样本X2，分三种情况：)()(12XXKK分类正确，势函数不变：0)(2112XXK且若0)(2122XXK且或21212,),()()(XXXXXXXXKKKKK，错误分类，修改势函数：0)(2112

44、XXK但若，错误分类，修改势函数：0)(2122XXK但若21212,),()()(XXXXXXXXKKKKK- 第k步：设Kk(X) 为加入训练样本X1 ，X2 ，Xk后的积累势函数， 则加入第k+1个样本，有：)(1XkK正确分类， 0)(111kkkKXX且若0)(121kkkKXX且或)(1XkK，错误分类：0)(111kkkK XX但若0)(121kkkK XX但若 ，错误分类：)(1XkK以上决定积累位势的迭代算法可写为：其中rk+1 为校正项系数，定义为：)(XkK),()(1kkKKXXX),()(1-kkKKXXX),()()(111kkkkKrKKXXXX(3-57)-0,

45、 10, 10,00,01211111211111kkkkkkkkkkkkkKKKKrXXXXXXXX且对于且对于且对于且对于(3-58)从所给的训练样本集 中略去不使积累势发生变化的那些样本，可得一简化样本序列 （校正错误的样本），算法可规纳为：,21kXXX,21jXXX),()(1jjXjkKKXXX即：由(k+1)个训练样本产生的积累势，等于两类中校正错误 的样本的总势能之差。 -21,1,1jjjXX对于对于式中， ),()()(111kkkkKrKKXXXX-0, 10, 10, 00, 01211111211111kkkkkkkkkkkkkKKKKrXXXXXXXX且对于且对于且

46、对于且对于(3-59)(3-60) 从势函数算法可看出，积累势函数起着判别函数的作用，因此可直接用作判别函数，故取 d(X)=K(X) 。由(3-57)式得：式中rk+1按(3-58)式取值：1111sgn121-kkkkkdrX也可简写成：-0, 10, 10,00,01211111211111kkkkkkkkkkkkkddddrXXXXXXXX且对于且对于且对于且对于式中 取值同(3-60) ：1k-211,1,1jjkXX对于对于),()()(111kkkkKrKKXXXX(3-57),()()(111kkkkKrddXXXX(3-61) 两个n维向量 X 和 Xk 的函数K(X, Xk) ，如同时满足下列三个条件，都可做为势函数：3. 势函数的选择势函数的选择，当且仅当 X = Xk 时达到最大值。),(),(XXXXkkKK 当向量 X 与 Xk 的距离趋于无穷时，K(X, Xk) 趋于零。 K(X, Xk) 是光滑函数，且是X与Xk之间距离的单调下降函数。1）势函数应