模式识别课件：a03.ppt

1、1模式识别主讲主讲： 蔡宣平蔡宣平 教授教授 电话电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系2 第三章第三章 判别域代数界面方程法判别域代数界面方程法3.13.1 用判别域界面方程分类的概念用判别域界面方程分类的概念3.2 3.2 线性判别函数线性判别函数3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间3.4 Fisher3.4 Fisher线性判别线性判别3.5 3.5 一次准则函数及梯度下降法一次准则函数及梯度下降法3.6

2、3.6 二次准则函数及其解法二次准则函数及其解法3.9 3.9 广义线性判别函数广义线性判别函数3.10 3.10 二次判别函数二次判别函数3.12 3.12 位势函数分类法位势函数分类法有有监监督督分分类类3 3.1 3.1 用判别域界面方程分类的概念用判别域界面方程分类的概念4 2x1x21o0)(32211wxwxwxd两类的分类问题，它们的边界线就是一个判别函数两类的分类问题，它们的边界线就是一个判别函数5两类问题中线性不可分的实例两类问题中线性不可分的实例6123边界2x1x三类的分类问题，它们的边界线也是一个判别函数三类的分类问题，它们的边界线也是一个判别函数73.1 3.1 用判

3、别域界面方程分类的概念用判别域界面方程分类的概念 第三章第三章 判别域代数界面方程法判别域代数界面方程法8 3.2 线性判别函数线性判别函数 第三章第三章 判别域代数界面方程法判别域代数界面方程法91011多类问题图例多类问题图例（第一种情况）（第一种情况）3( )0d x 21x 2( )0d x 2x1( )0d x 13? ?不确定区域121 1、第一种情况（续）第一种情况（续）判别规则为：判别规则为：如果如果 ijxdxdji0)(0)(则判则判 ix3( ) 0d x 21x 2( ) 0d x 2x1( ) 0d x 13比如对图的三类问题比如对图的三类问题, ,如果对于任一模式如

4、果对于任一模式 如如果它的果它的 则该模式属于则该模式属于1 1类。类。 0)(1xd0)(2xd0)(3xdx131 1、第一种情况（续）第一种情况（续）3123( )0( )0( )0dxdxdx12123( )0( )0( )0d xdxdx123()0()0()0dxdxdx 4IR3IR1IR2IR1x2x1( )0dx 2( )0d x 3( )0d x 551如果某个如果某个X X使二个以上的判别函数使二个以上的判别函数 d di i00 。则。则此模式此模式X X就无法作出确切的判决。如图就无法作出确切的判决。如图另一种情况是另一种情况是IR2IR2区域，区域，判别函数都为负值

5、。判别函数都为负值。IR1IR1，IR2IR2，IR3IR3，IR4IR4。都为不。都为不确定区域。确定区域。141 1、第一种情况（续）第一种情况（续）11221232( )0( )50( )10dxxxdxxxdxx 解：解： 三个判别边界分别为：三个判别边界分别为：151、第一种情况（续）第一种情况（续）123( )0,( )0,( )0d xdxdx结论：结论： 因为因为所以它属于所以它属于2 2类。类。161 1、第一种情况（续）第一种情况（续）3123( )0( )0( )0dxdxdx12123( )0( )0( )0d xdxdx123()0()0()0dxdxdx 1x2x1

6、( )0dx 2( )0d x 3( )0d x 5511718212( )0dx 23( )0dx 13( )0dx 3 12、第二种情况（续）第二种情况（续）多类问题图例多类问题图例（第二种情况）（第二种情况）d12(x) = - d21(x) = x1 x2 + 5 = 0d d1212(x)(x)为正为正两分法例题图示两分法例题图示ji0 1 2 3 4 5 6 7 8 99876543211x2xd d2121(x)(x)为正为正d d1212(x)(x)为正为正两分法例题图示两分法例题图示ji0 1 2 3 4 5 6 7 8 99876543211x2xd d2121(x)(x)

7、为正为正d d2323(x)= -(x)= -d d3232(x)= (x)= x x1 1+ +x x2 2= 0= 0d d3232(x)(x)为正为正d d2323(x)(x)为正为正d d1212(x)(x)为正为正两分法例题图示两分法例题图示ji0 1 2 3 4 5 6 7 8 99876543211x2xd d2121(x)(x)为正为正d d3232(x)(x)为正为正d d2323(x)(x)为正为正d d1313(x)= -(x)= -d d3131(x)= (x)= x x1 1+3 = +3 = 0 0d d3131(x)(x)为正为正d d1313(x)(x)为正为正

8、 1 1类判别区域类判别区域 d d1212(x)0(x)0 d d1313(x)0(x)0 2 2类判别区域类判别区域 d d2121(x)0(x)0 d d2323(x)0(x)0d d1212(x)(x)为正为正两分法例题图示两分法例题图示ji0 1 2 3 4 5 6 7 8 99876543211x2xd d2121(x)(x)为正为正d d3232(x)(x)为正为正d d2323(x)(x)为正为正d d3131(x)(x)为正为正d d1313(x)(x)为正为正 3 3类判别区域类判别区域 d d3131(x)0(x)0 d d3232(x)0(x)0IR24253、第三种情

9、况（续）第三种情况（续）212( )( )d xd x23( )( )d xd x13( )( )dxdx13多类问题图例多类问题图例（第三种情况）（第三种情况）。上述三种方法小结上述三种方法小结: 方法方法判别函数的数目和方法判别函数的数目和方法相同，但没有不相同，但没有不确定区，分析简单，是最常用的一种方法。确定区，分析简单，是最常用的一种方法。3c时，时，ji法比法比ii法需要更多法需要更多当当的判别函数式，这是一个缺点。的判别函数式，这是一个缺点。i类与其余的类与其余的1c开，而开，而ji法是将法是将i类和类和j类分开，显然类分开，显然jiii法是将法是将但是但是类区分类区分法使模式更

10、容易线性可分，这是它的优点。法使模式更容易线性可分，这是它的优点。283.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 第三章第三章 判别域代数界面方程法判别域代数界面方程法29此方程表示一超平面此方程表示一超平面 。它有以下。它有以下三个性质三个性质: :n(1)(1)系数矢量系数矢量 ，是该平面的法矢量。是该平面的法矢量。n(2)(2)判别函数判别函数 的绝对值正比于的绝对值正比于 到超到超平面平面 的距离。的距离。n(3)(3)判别函数值的正负表示出特征点位于哪个判别函数值的正负表示出特征点位于哪个半空间中。半空间中。012(,.)nww ww(

11、)d xx( )0d x 3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 第三章第三章 判别域代数界面方程法判别域代数界面方程法30图图3.3.1 3.3.1 点面距离及界面的正负侧示意图点面距离及界面的正负侧示意图x2x1xo0)(xdnppx0w313233pnxnpxndx)(pwwxww00000100wwxwwn)(10010 xdwwwxwn34证明：判别函数值的正负表示出特征点位于哪个证明：判别函数值的正负表示出特征点位于哪个半空间中。半空间中。35背向的半空间中时，背向的半空间中时，x当当在在n010nwxw这说明判别函数值的正负表示出

12、特征点位于这说明判别函数值的正负表示出特征点位于哪个半空间中，或者换句话说，表示特征点位于哪个半空间中，或者换句话说，表示特征点位于界面的哪一侧。界面的哪一侧。和和00w，故，故)(pxn10nwxw同号。同号。由于由于在在n指向的半空间中时，指向的半空间中时，010nwxwx即即36例例3.3.13.3.1：利用判别函数的鉴别意义，试分析：利用判别函数的鉴别意义，试分析d(xd(x1 1,x,x2 2) )x x1 1+x+x2 2+1+1。d(x1,x2)d(x1,x2)0 0n -1-1373.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间

13、及解空间判别函数值的鉴别意义、权空间及解空间38(2) (2) 解矢量解矢量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间39(2) (2) 解矢量解矢量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间403.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间41(3) (3) 解空间解空间3.3.2权空间、解矢量与解空

14、间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w142(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0

15、 ，w1。w0w143(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w144(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2

16、属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w145(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w146(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权

17、空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w147(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间483.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间w每一个训练模式都对解区提供一个约束，训练每一个训练模式都对解区提供一个约束，训练模式越多，解区的限制

18、就越多，解区就越小，就越模式越多，解区的限制就越多，解区就越小，就越靠近解区的中心，解矢量靠近解区的中心，解矢量 就越可靠，由它构就越可靠，由它构造的判别函数错分的可能性就越小。造的判别函数错分的可能性就越小。49(4) (4) 余量余量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间50(4) (4) 余量余量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间引入了余量可有效地避免量测的误差、引入引入了余量可

19、有效地避免量测的误差、引入的误差以及某些算法求得的解矢量收敛于解区的的误差以及某些算法求得的解矢量收敛于解区的边界上，从而提高了解的可靠性。边界上，从而提高了解的可靠性。设一设一3 3类问题有如下判决函数类问题有如下判决函数d d1 1(x) = - x(x) = - x1 1d d2 2(x) = x(x) = x1 1 + x + x2 2 -1 -1d d3 3(x) = x(x) = x1 1 - x - x2 2 -1 -1试画出下列各种情况的判决边界及各类的区域：试画出下列各种情况的判决边界及各类的区域：（1 1）满足）满足3.4.23.4.2节中的第一种情况；节中的第一种情况；（

20、2 2）满足）满足3.4.23.4.2节中的第二种情况节中的第二种情况, , 且令且令 d d1212(x)=d(x)=d1 1(x)(x)，d d1313(x)=d(x)=d2 2(x)(x)，d d2323(x)=d(x)=d3 3(x)(x)；（3 3）满足）满足3.4.23.4.2节中的第三种情况。节中的第三种情况。作业作业523.4 Fisher3.4 Fisher线性判别线性判别 第三章第三章 判别域代数界面方程法判别域代数界面方程法53二维模式向一维空间投影示意图二维模式向一维空间投影示意图uoxy54二维模式向一维空间投影示意图二维模式向一维空间投影示意图tyuoxy55二维模

21、式向一维空间投影示意图二维模式向一维空间投影示意图tyoxyoxy56（1)1)求解求解FishFish准则函数准则函数5758uSuuSSusssWWWWWW)(2121222uSumumumumummsBB)()(21212212类间离差度为：类间离差度为：59uSuuSussmmuJWBWWF2222121)()(并使其最大并使其最大, ,上式称为上式称为FisherFisher准则函数准则函数。60利用二次型关于矢量求导的公式可得：利用二次型关于矢量求导的公式可得：2)()(2)(2uSuuSuSuuSuSuuSuuSuuuJWWBBWWBF（2) 2) 求解求解FisherFishe

22、r最佳鉴别矢量最佳鉴别矢量uSuuSuWB令令uSuSWB可得：可得：6162n上式右边后两项因子的乘积为一标量，上式右边后两项因子的乘积为一标量，令其为令其为 ，于是可得，于是可得n式中式中 为一标量因子，其不改变轴的方为一标量因子，其不改变轴的方向，可以取为向，可以取为1,于是有于是有)(211mmSuW)(211mmSuWummmmSuSSuWBW)(21211163uSuuSuuJWBF)()()(21121mmSmmW此时的此时的 可使可使Fisher准则函数取最大值，即是准则函数取最大值，即是n 维维空间到一维空间投影轴的最佳方向，由空间到一维空间投影轴的最佳方向，由u)(211m

23、mSuW)(2121mmmmSB和和JF 最大值为最大值为:)()()()()(2111212112121121mmSSSmmmmSmmmmSmmWWWWW64即即称称为为Fisher变换函数变换函数)()(21121mmSmmWxSmmyW121)(J JF F=65 由于变换后的模式是一维的，因此判别界面实际由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点，所以可以根据训练上是各类模式所在轴上的一个点，所以可以根据训练模式确定一个阈值模式确定一个阈值 y yt t，于是，于是FisherFisher判别规则判别规则为为: : 21xyyxut221mmyt（3) 3)

24、 求解求解FisherFisher判别函数判别函数判别阈值可取两个类心在判别阈值可取两个类心在u u方向上轴的投影连线的方向上轴的投影连线的中点作为阈值，即中点作为阈值，即: :6667ijijijijiimuxuNyNm)()(11（7 7） 计算计算 。im221mmyt（8 8） 计算计算yt 。21xyyxut（9 9） 对未知模式对未知模式x判定模式类。判定模式类。68以以100100元元A A面数据和面数据和5050元元A A面数据为例面数据为例100100元元A A面面:(64,76,99,84,98,95,88,83),:(64,76,99,84,98,95,88,83),50

25、50元元A A面面:(65,67,82,80,89,94,86,92),:(65,67,82,80,89,94,86,92),N N1 1=N=N2 2=60=60算得算得: :m m1 1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m m2 2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)69m m1 1=(=(69.3, 61.9, 83.5, 7

26、0.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.5) )70m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59

27、.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )71m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )72m

28、 m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )737475 利用给定的一个样本数据编写利用给定的一个样本数据编写100100元元B B面与面与5050元元A A面的面的FisherFisher判别门限的程序，并用另一个样本数据判别门限的

29、程序，并用另一个样本数据验证之。验证之。上机练习上机练习763.5 一次准则函数及梯度下降法一次准则函数及梯度下降法3.5.1 感知感知器算法器算法(Perceptron Approach)任选一初始增广权矢量任选一初始增广权矢量用训练样本检验分类是否正确用训练样本检验分类是否正确对所有训练样本都正确分类？对所有训练样本都正确分类？YesYesENDENDYesYesNoNo对权值进行校正对权值进行校正NoNo感知器算法流程图感知器算法流程图流程:773.5 一次准则函数及梯度下降法一次准则函数及梯度下降法3.5.1 感知感知器算法器算法(Perceptron Approach)78 (3)调

30、整增广权矢量，规则是调整增广权矢量，规则是 - 如果如果 和和 ，则，则 - 如果如果 和和 ，则，则 - 如果如果 和和 ， 或或 和和 ，则，则1kx0)(kxkwkxkwkw)() 1(2kxkxkwkw)() 1(0)(kxkw1kx0)(kxkw2kx0)(kxkw)() 1(kwkwxwNxxx,21 (4)如果如果k wx wj jx (x ( j j i)i)因此判别规则是因此判别规则是 若若 d di i(x) d(x) dj j(x) (x) j j i i 则判则判x xi i 第三章第三章 判别域代数界面方程法判别域代数界面方程法93(1) (1) 赋初值赋初值, ,分

31、别给分别给c c个权矢量个权矢量w wi i(i=1,2,(i=1,2,c),c)赋任意的赋任意的初值，选择正常数初值，选择正常数 ，置步数，置步数k=1k=1。算法步骤：算法步骤：(2) (2) 输入已知类别的增广训练模式输入已知类别的增广训练模式x xk k，计算，计算c c个判别函个判别函数数 d di i(x(xk k) = w) = wi ix xk k (i=1,2, (i=1,2,c),c)(3) (3) 修正权矢量，修正规则是：修正权矢量，修正规则是：if (xif (xk ki i) and (d) and (di i(x(xk k)d)dj j(x(xk k) () ( j

32、 j i) theni) then w wi i(k+1) = w(k+1) = wi i(k) (i=1,2,(k) (i=1,2,c) (,c) (正确分类正确分类) ) if (xif (xk ki i) and (d) and (di i(x(xk k) ) d dl l(x(xk k) (l) (l i) theni) then w wi i(k+1) = w(k+1) = wi i(k)+ (k)+ x xk k w wl l(k+1) = w(k+1) = wl l(k)- (k)- x xk kw wj j(k+1) = w(k+1) = wj j(k) (k) ( j j i

33、,l) i,l) 94(1) (1) 赋初值赋初值, ,分别给分别给c c个权矢量个权矢量w wi i(i=1,2,(i=1,2,c),c)赋任意的赋任意的初值，选择正常数初值，选择正常数 ，置步数，置步数k=1k=1。算法步骤：算法步骤：(2) (2) 输入已知类别的增广训练模式输入已知类别的增广训练模式x xk k，计算，计算c c个判别函个判别函数数 d di i(x(xk k) = w) = wi ix xk k (i=1,2, (i=1,2,c),c)(4) if kN ,(4) if kN ,令令k=k+1,k=k+1,返至返至；if k=Nif k=N，检验判别函数是否对都能正确

34、分类，若是，检验判别函数是否对都能正确分类，若是，结束；否则，令结束；否则，令k=1k=1，返至，返至。(3) (3) 修正权矢量。修正权矢量。95例题例题:已知训练样本已知训练样本(0,0)T1，(1,1)T2 ，(-1,1)T3, 试求解向量试求解向量w1、w2和和w3。 （2 2）运用感知器训练算法。置）运用感知器训练算法。置k=1k=1，增量，增量 =1=1，赋初，赋初值：值：w1 1=(0,0,0)=(0,0,0)T T, , w2 2=(0,0,0)=(0,0,0)T T, , w3 3=(0,0,0)=(0,0,0)T T, ,进行迭代运算：进行迭代运算：解解:（1 1）训练样本

35、分量增广化。将训练样本变成增广训）训练样本分量增广化。将训练样本变成增广训练模式：练模式：x1 1=(0,0,1)=(0,0,1)T T, , x2 2=(1,1,1)=(1,1,1)T T, , x3 3=(-1,1,1)=(-1,1,1)T T, , 这里的下标恰是所属类别，各类样本不需符号规这里的下标恰是所属类别，各类样本不需符号规范化。范化。96例题例题:已知训练样本已知训练样本(0,0)T1，(1,1)T2 ，(-1,1)T3, 试求解向量试求解向量w1、w2和和w3。 k=1,k=1,xk k= =x1 11 1, ,因为因为d d1 1( (x1 1)=d)=d2 2( (x1

36、1)=0)=0，d d1 1( (x1 1)=d)=d3 3( (x1 1)=0)=0，错错分，所以分，所以: : w1 1(2)=(2)=w1 1(1)+ (1)+ x1 1=(0,0,1)=(0,0,1)T T w2 2(2)=(2)=w2 2(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T T w3 3(2)=(2)=w3 3(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T Tk=2,xk=2,xk k=x=x2 22 2, ,因为因为d d2 2(x(x2 2)=-1d)=-1d1 1(x(x2 2)=1)=1，d d2 2(x(x2 2)=d)=d

37、3 3(x(x2 2)=-1)=-1，错分，错分，所以所以 w w1 1(3)=w(3)=w1 1(2)- x(2)- x2 2=(-1,-1, 0)=(-1,-1, 0)T T w w2 2(3)=w(3)=w2 2(2)+ x(2)+ x2 2=( 1, 1, 0)=( 1, 1, 0)T T w w3 3(3)=w(3)=w3 3(2)- x(2)- x2 2=(-1,-1,-2)=(-1,-1,-2)T T97例题例题:已知训练样本已知训练样本(0,0)T1，(1,1)T2 ，(-1,1)T3, 试求解向量试求解向量w1、w2和和w3。 k=3,xk=3,xk k=x=x3 33 3,

38、 ,因为因为d d3 3(x(x3 3)=-2d)=-2d)=0d1 1(x(x2 2)=-2)=-2，d d2 2(x(x2 2)=0d)=0d3 3(x(x2 2)=-4)=-4，正确，正确，所以所以 w w1 1(6)=w(6)=w1 1(5)=( 0,-2, 0)(5)=( 0,-2, 0)T T w w2 2(6)=w(6)=w2 2(5)=( 2, 0,-2)(5)=( 2, 0,-2)T T w w3 3(6)=w(6)=w3 3(5)=(-2, 0,-2)(5)=(-2, 0,-2)T Tk=6,xk=6,xk k=x=x3 33 3, ,因为因为d d3 3(x(x3 3)=

39、0d)=0d1 1(x(x3 3)=-2)=-2，d d3 3(x(x3 3)=0d)=0d2 2(x(x3 3)=-4)=-4，正确，正确，所以所以 w w1 1(7)=w(7)=w1 1(6)=( 0,-2, 0)(6)=( 0,-2, 0)T T w w2 2(7)=w(7)=w2 2(6)=( 2, 0,-2)(6)=( 2, 0,-2)T T w w3 3(7)=w(7)=w3 3(6)=(-2, 0,-2)(6)=(-2, 0,-2)T T99例题例题:已知训练样本已知训练样本(0,0)T1，(1,1)T2 ，(-1,1)T3, 试求解向量试求解向量w1、w2和和w3。 k=7,x

40、k=7,xk k=x=x1 11 1, ,因为因为d d1 1(x(x1 1)=0d)=0d2 2(x(x1 1)=-2)=-2，d d1 1(x(x1 1)=0d)=0d3 3(x(x1 1)=-2)=-2，正确，正确，三个权矢量不再变化，因此可以确定所有训练样本均已三个权矢量不再变化，因此可以确定所有训练样本均已被正确分类，被正确分类，由此得到三个解矢量：由此得到三个解矢量：w1 1* *= =w1 1(5)(5)，w2 2* *= =w2 2(5)(5)，w3 3* *= =w3 3(5) (5) 同时可得三个判别函数同时可得三个判别函数: :d d1 1( (x) = -2) = -2

41、x x2 2d d2 2( (x) = 2) = 2x x1 1-2-2d d3 3( (x) = -2) = -2x x1 1-2-2100 3.6 二次准则函数及其解法二次准则函数及其解法 问题：问题： 一次准则函数及其算法（如感知器算法）一次准则函数及其算法（如感知器算法）只适用于线性可分的情况，如果是线性不可分只适用于线性可分的情况，如果是线性不可分的，分类过程将不收敛的，分类过程将不收敛! ! 能否找到一种算法，使之能够测试出模能否找到一种算法，使之能够测试出模式样本集是否线性可分，并且对线性不可分式样本集是否线性可分，并且对线性不可分的情况也能给出的情况也能给出“次最优次最优”的解

42、？的解？ 第三章第三章 判别域代数界面方程法判别域代数界面方程法101 如果训练模式是线性不可分如果训练模式是线性不可分不等式组是不等式组是不一致不一致的，不等式组没解。此时，目标的，不等式组没解。此时，目标最少的训练模式被最少的训练模式被错分。错分。（一）最小错分模式数目准则：（一）最小错分模式数目准则： 如果训练模式是线性可分的，则存在权矢量如果训练模式是线性可分的，则存在权矢量 使不等式组使不等式组w0ixw), 2 , 1(Ni成立。成立。对线性不可分样本集，求一解矢量使得错分的对线性不可分样本集，求一解矢量使得错分的模式数目最少。模式数目最少。 102),(2121NNxxxxxxX

43、103J 如果方程组有唯一解如果方程组有唯一解, ,说明训练模式集是线性说明训练模式集是线性可分的可分的, ,如果方程组无解如果方程组无解, ,极小点值是最小二乘解。极小点值是最小二乘解。一般情况下使一般情况下使 极小等价于误分模式数目最少。极小等价于误分模式数目最少。104105 求矩阵的广义逆计算量较大，引入的误差求矩阵的广义逆计算量较大，引入的误差也可能很大，在实际中多采用下面的梯度法。也可能很大，在实际中多采用下面的梯度法。106107为了减少计算量和存储量，可以仿照单样本修正法为了减少计算量和存储量，可以仿照单样本修正法: :NkkkkxbxwbwXX1)()(由于：由于：此算法通常

44、称为此算法通常称为W WH(WidrowH(WidrowHoff)Hoff)算法算法 108W-HW-H算法有两个性质算法有两个性质109110H-KH-K算法算法求解最佳权矢量的方法求解最佳权矢量的方法(1)( )( )( )( )bb kb kJb kk H-KH-K算法的迭代公式为：算法的迭代公式为：)(2)(bwXJb0其中其中111112H-K算法步骤;21, 1, 0) 1 (kbStep2.Step2.置初值置初值)(1XXXXStep1.Step1.将训练样本符号规范化，得将训练样本符号规范化，得X X求伪逆求伪逆)()()()()(kbkwXkekbXkwStep3.Step

45、3.计算计算113H-K算法步骤Step6. Step6. k=k+1; goto Step3; goto Step3;Step5.Step5.);)()()() 1(kekekbkb)()()() 1(kekeXkwkw)()(keXkw114115116作业1 1 以下列两类模式为样本，用以下列两类模式为样本，用LMSELMSE( (梯度法梯度法) )算法求解算法求解判决函数。（令判决函数。（令 w(1) = (-1,-2,-2)w(1) = (-1,-2,-2) ） 1 1：(0,0,0(0,0,0), (1,0,0) (1,0,0), (1,0,1, (1,0,1), (1,1,0),

46、 (1,1,0), 2 2：(0,0,1)(0,0,1), (0,1,1), (0,1,1), (0,1,0), (0,1,0), (1,1,1), (1,1,1),2 2 用用LMSELMSE( (梯度法梯度法) )算法检验下列模式的线性可分性。算法检验下列模式的线性可分性。 1 1：(0,1)(0,1)，(0,-1)(0,-1) ， 2 2：(1,0)(1,0)，(-1,0)(-1,0) 。3 3 已知已知 1 1：(0,0)(0,0), 2 2：(1,1)(1,1), 3 3：(-1,1)(-1,1) 。用感知器算法求该三类问题的判别函数，并画出解区用感知器算法求该三类问题的判别函数，并

47、画出解区域。域。117 设一维两类模式设一维两类模式 x x 在一维空间在一维空间坐标轴上分坐标轴上分布如图布如图3-9-13-9-1所示，两类的类域为所示，两类的类域为 和和 3.9 3.9 广义线性判别函数广义线性判别函数),( :1a,)b (),( :2ba图图3.9.1 3.9.1 一维特征空间中非线性可分的图示一维特征空间中非线性可分的图示118显然，这两类不是线显然，这两类不是线性可分的，因不能用性可分的，因不能用一个分界点将两类分一个分界点将两类分开。但是，对于一条开。但是，对于一条穿过穿过a a、b b两点的二次两点的二次曲线，曲线，abxbaxbxaxxd)()()(2当当

48、1x0)(xd0)(xdax bx 即即或或时时, ,2x当当bxa即即时时, ,119原来的一维非线性可分的模式在所映射的二维特征空原来的一维非线性可分的模式在所映射的二维特征空间中是线性可分的，即间中是线性可分的，即: :1y0)(yd2y0)(yd12012(),(),()jjjdjyf xfxfx使使在特征空间是线性可在特征空间是线性可分的分的, , 称其为称其为广义线性判别函数广义线性判别函数。121下图所示两类模式是线性不可分的。下图所示两类模式是线性不可分的。122经过非线性变换，两类模式是线性可分的。经过非线性变换，两类模式是线性可分的。12312211)()()()(dddw

49、xfwxfwxfwxd)(12211ydywwywywywddd),(121dwwww) 1),(,),(),() 1 ,(2121xfxfxfyyyydd式中式中), 2 , 1)(dixfyiix是是 的单值实函数。的单值实函数。124125上式右边前两项是上式右边前两项是x x各分量的二次项求和式，各分量的二次项求和式，显然它们的项数分别为显然它们的项数分别为n n和和 n(n-1)/2n(n-1)/2。第三项是第三项是x x的各分量一次项求和式，项数为的各分量一次项求和式，项数为n n。所以所以d(x)d(x)的项数为的项数为: : n+n(n-1)/2+n+1=(n+1)(n+2)/

50、2n+n(n-1)/2+n+1=(n+1)(n+2)/2由于有一个常数项，变换后的特征空间维数为由于有一个常数项，变换后的特征空间维数为: : (n+1)(n+2)/2-1=n(n+3)/2(n+1)(n+2)/2-1=n(n+3)/2126)()()0(10 xdwxdniniixwxd11)(211122112)(iininiiiixxwxdrrrriiiniiii ininiirxxxwxd211211121)(rrnC11nC21nC1127(0)1( )ndxw( )(1)( )( )( )rrrdxdxdx)()(xdr的项数为：的项数为： !)!(rnrn111rkkknC128