判别域代数界面方程法课件

第三章第三章 判别域代数界面方程法判别域代数界面方程法第三章 颜色（绿颜色（绿/红）红）似圆度判别函数判别函数(Discriminant Function)n3.13.1 判别域代数界面方程法的概念判别域代数界面方程法的概念颜色（绿/红）似圆度判别函数3.1 判别域代数界面方程法的概n判别函数的形式判别函数的形式线性线性非线性非线性n判别规则判别规则n参数确定参数确定n3.13.1判别域代数界面方程法的概念判别域代数界面方程法的概念判别函数的形式3.1判别域代数界面方程法的概念3.2.13.2.1判别函数的形式判别函数的形式n3.23.2 线性判别函数线性判别函数模式的特征矢量：模式的特征矢量：判别函数：判别函数：称为权矢量或系数矢量称为权矢量或系数矢量3.2.1判别函数的形式3.2 线性判别函数模式的特征矢量：3.2.13.2.1判别函数的形式判别函数的形式增广增广特征矢量：特征矢量：增广增广权矢量：权矢量：判别函数：判别函数：n3.23.2 线性判别函数线性判别函数3.2.1判别函数的形式增广特征矢量：增广权矢量：判别函数：3.2.23.2.2判别规则判别规则n3.23.2 线性判别函数线性判别函数1 1、两类问题、两类问题颜色（绿颜色（绿/黄）黄）似圆度似圆度3.2.2判别规则3.2 线性判别函数1、两类问题颜色（绿/判别规则判别规则:n3.23.2 线性判别函数线性判别函数1 1、两类问题、两类问题3.2.23.2.2判别规则判别规则判别规则:3.2 线性判别函数1、两类问题3.2.2判别规则3.2.23.2.2判别规则判别规则2 2、多类问题、多类问题（1 1）二分法二分法（2 2）i i/j j二分法二分法（3 3）最大判别准则）最大判别准则n3.23.2 线性判别函数线性判别函数3.2.2判别规则（1）二分法3.2 线性判别函（1 1）二分法二分法2 2、多类问题、多类问题（1）二分法2、多类问题具有性质：具有性质：M个判别函数：个判别函数：（1 1）二分法二分法判别规则：判别规则：2 2、多类问题、多类问题具有性质：M个判别函数：（1）二分法判别v例例1 1：已知三类：已知三类1 1,2 2,3 3的判别函数分别为：的判别函数分别为：问问 属于哪一类属于哪一类？（1 1）二分法二分法2 2、多类问题、多类问题v解：解：代入代入结论：属于结论：属于2 2类。类。例1：已知三类1,2,3的判别函数分别为：问 结论：判别区间增大，不确定区间减小结论：判别区间增大，不确定区间减小IRIR（2 2）i i/j j二分法二分法2 2、多类问题、多类问题结论：判别区间增大，不确定区间减小IR（2）i/j二分法（2 2）i i/j j二分法二分法有有 M M(M M _ _ 1)/21)/2个判别平面个判别平面区分区分i/j的判别函数：的判别函数：具有性质：具有性质：2 2、多类问题、多类问题判别规则：判别规则：（2）i/j二分法有 M(M _ 1)/2个判别平面区分v例例2 2：已知三类：已知三类1,2,3，判别函数分别为：，判别函数分别为：问：问：当当 时属于时属于哪一类？哪一类？（2 2）i i/j j二分法二分法2 2、多类问题、多类问题解：代入判别函数可得解：代入判别函数可得:下标变换可得下标变换可得:例2：已知三类1,2,3，判别函数分别为：问：当 或或（3 3）最大判别准则）最大判别准则2 2、多类问题、多类问题M个个判别函数：判别函数：判别规则：判别规则：如果如果，则判，则判，则判，则判或或如果如果判别界面：判别界面：或（3）最大判别准则2、多类问题M个判别函数：判别规则：如（3 3）最大判别准则）最大判别准则2 2、多类问题、多类问题结论：无不确定区间结论：无不确定区间（3）最大判别准则2、多类问题结论：无不确定区间v例：假设判别函数为：例：假设判别函数为：问问 属属于哪一类。于哪一类。（3 3）最大判别准则）最大判别准则2 2、多类问题、多类问题解：解：所以所以例：假设判别函数为：问 属于哪一类。（3）最大三种方法小结三种方法小结2 2、多类问题、多类问题分类方分类方法法判别函数个判别函数个数数不确定不确定区区难易难易i i/i i二分法二分法i i/j j二分法二分法最大判最大判别准则别准则M MM(M-1)/2M M最多最多较少较少没有没有较难较难较易较易较易较易三种方法小结2、多类问题分类方法判别函数个数不确定区难易3.1 3.1 设一设一3 3类问题有如下判决函数类问题有如下判决函数d1(x)=-x1d1(x)=-x1d2(x)=x1+x2-1d2(x)=x1+x2-1d3(x)=x1-x2-1d3(x)=x1-x2-1试画出下列各种情况的判决边界及各类的区域：试画出下列各种情况的判决边界及各类的区域：（1 1）满足）满足3.4.23.4.2节中的第一种情况；节中的第一种情况；（2 2）满足）满足3.4.23.4.2节中的第二种情况节中的第二种情况,且令且令 d12(x)=d1(x)d12(x)=d1(x)，d13(x)=d2(x)d13(x)=d2(x)，d23(x)=d23(x)=d3(x)d3(x)；（3 3）满足）满足3.4.23.4.2节中的第三种情况。节中的第三种情况。作业作业3.1 设一3类问题有如下判决函数d1(x)=-x13.3.1 3.3.1 判别函数值的大小、正负的数学意义判别函数值的大小、正负的数学意义n n维特征空间维特征空间X Xn n中，两类问题的线性判别界面方程为中，两类问题的线性判别界面方程为此方程表示一超平面，记为此方程表示一超平面，记为 是该平面的法矢量。是该平面的法矢量。n3.33.3判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间3.3.1 判别函数值的大小、正负的数学意义3.3判别函数值2x1xo+-0)(=xdrnrprpxrr-n3.23.2判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间3.3.1 3.3.1 判别函数值的大小、正负的数学意义判别函数值的大小、正负的数学意义(1)(1)系数矢量是该平面的法矢量。系数矢量是该平面的法矢量。(2)(2)判别函数的绝对值正比于特判别函数的绝对值正比于特征点到超平面的距离。征点到超平面的距离。(3)(3)判别函数值的正负表示出特判别函数值的正负表示出特征点位于哪个半空间中。征点位于哪个半空间中。2x1xo+-0)(=xdrnrprpxrr-3.2判别函数例例3 3：利用判别函数的鉴别意义，试分析：利用判别函数的鉴别意义，试分析d(xd(x1 1,x,x2 2)x x1 1+x+x2 2+1+1。d(x1,x2)0-1-1n3.23.2判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间3.3.1 3.3.1 判别函数值的大小、正负的数学意义判别函数值的大小、正负的数学意义例3：利用判别函数的鉴别意义，试分析d(x1,x2)x1+(1)(1)权空间权空间n增广特征矢量与增广权矢量是对称的，判别函数增广特征矢量与增广权矢量是对称的，判别函数可以写成可以写成 视为相应的视为相应的 的的“权权”n 指向平面指向平面 的正侧，即该半空间中的任一的正侧，即该半空间中的任一点点 都使都使n 背背向向的的半半子子空空间间中中任任一一点点 都都有有 。n3.23.2判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间3.3.23.3.2权空间、解矢量与解空间权空间、解矢量与解空间(1)权空间增广特征矢量与增广权矢量是对称的，判别函数可以写解空间示意图解空间示意图o+-w1w2b余量余量解空间示意图o+-w1w2b余量w1w2w3wIIIIIIIVw1w2w3wIIIIIIIV（a a）解空间）解空间（b b）训练模式符号化后的解空间）训练模式符号化后的解空间图图 (3-3-2)(3-3-2)权空间中的判别界权空间中的判别界面及解锥面及解锥w1w2w3wIIIIIIIVw1w2w3wIIIIIIIV(2)(2)解矢量解矢量 对对于于两两类类问问题题，在在对对待待分分类类模模式式进进行行分分类类之之前前，应应根据已知类别的增广训练模式，根据已知类别的增广训练模式，确定线性判别函数确定线性判别函数 这时的这时的 称为称为解矢量解矢量，记为，记为 可以将已知类别的训练模式符号规范化。可以将已知类别的训练模式符号规范化。n3.23.2判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间3.3.23.3.2权空间、解矢量与解空间权空间、解矢量与解空间(2)解矢量 对于两类问题，在对待分类模式进行分类之(3)(3)解空间解空间 以权空间原点为顶点的凸多面锥。锥中每一以权空间原点为顶点的凸多面锥。锥中每一点都是上面不等式组的解，解矢量不是唯一的，上点都是上面不等式组的解，解矢量不是唯一的，上述的凸多面锥包含了解的全体，称其为述的凸多面锥包含了解的全体，称其为解区、解空解区、解空间间或或解锥。解锥。每一个训练模式都对解区提供一个约束，训练模式每一个训练模式都对解区提供一个约束，训练模式越多，解区的限制就越多，解区就越小，就越靠近越多，解区的限制就越多，解区就越小，就越靠近解区的中心，解矢量就越可靠，由它构造的判别函解区的中心，解矢量就越可靠，由它构造的判别函数错分的可能性就越小。数错分的可能性就越小。n3.23.2判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间3.3.23.3.2权空间、解矢量与解空间权空间、解矢量与解空间(3)解空间 以权空间原点为顶点的凸多面锥。锥中每(4)(4)余量余量为使解矢量可靠为使解矢量可靠,使解区更小使解区更小,可以采取增加训可以采取增加训练模式数以及引入余量练模式数以及引入余量 ,使使 ,这样，有这样，有效地避免了量测的误差、引入的误差以及某些算效地避免了量测的误差、引入的误差以及某些算法求得的解矢量收敛于解区的边界上，从而提高法求得的解矢量收敛于解区的边界上，从而提高了解的可靠性。了解的可靠性。它的边界离开原解区边界的距离为它的边界离开原解区边界的距离为 3.3.23.3.2权空间、解矢量与解空间权空间、解矢量与解空间n3.23.2判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间(4)余量为使解矢量可靠,使解区更小,可以采取增加训练模式 图图3.4.1 二维模式向一维空间投影示意图二维模式向一维空间投影示意图3.4 Fisher3.4 Fisher线性判别线性判别 图3.4.1 二维模式向一维空间投影示意图3.思想：思想：多维多维 FisherFisher变换变换 利于分类的一维利于分类的一维 方法：方法：求权矢量求权矢量 求满足上述目标的投影轴求满足上述目标的投影轴的方向的方向 和在一维空间中确定判别规则。和在一维空间中确定判别规则。3.4 Fisher3.4 Fisher线性判别线性判别思想：多维 Fisher变换 利于分类的一维 方法：用用 表示待求的表示待求的 。设给定设给定n n维训练模式维训练模式 ，其中有，其中有N N1 1个和个和N N2 2=N N-N N1 1 个模式分属个模式分属w w1 1 类和类和w w2 2 类，分别记为类，分别记为 和和 ，各类模式均值矢量为，各类模式均值矢量为 各类类内离差阵各类类内离差阵S SW Wi i和总的类内离差阵和总的类内离差阵S SW W分别为分别为（1)1)求解求解FisherFisher准则函数准则函数 用 表示待求的 。（1)1)求解求解FisherFisher准则函数准则函数（1)求解Fisher准则函数 取类间离差阵为取类间离差阵为 作变换，作变换，n n维矢量维矢量 在以矢量在以矢量 为方向的轴上进行投影为方向的轴上进行投影 变换后在一维变换后在一维 y y 空间中各类模式的均值为空间中各类模式的均值为i=1,2i=1,2 取类间离差阵为i=1,2i=1,2 类内离差度类内离差度 和总的类内离差度和总的类内离差度 为为 类间离差度为类间离差度为 类内离差度 和总的类内离差度 为 希望经投影后，类内离差度希望经投影后，类内离差度 越小越好，类间离越小越好，类间离差度差度 越大越好，根据这个目标作准则函数越大越好，根据这个目标作准则函数 并使其最大并使其最大,上式称为上式称为FisherFisher准则函数准则函数。希望经投影后，类内离差度 利用二次型关于矢量求导的公式可得利用二次型关于矢量求导的公式可得 令令 可得可得（2)2)求解求解FisherFisher最佳鉴别矢量最佳鉴别矢量 （2)求解Fisher最佳鉴别矢量 当当N N较大时，较大时，S SW W通常是非奇异的通常是非奇异的,于是有于是有 上式表明，上式表明，是矩阵是矩阵 相应于特征值相应于特征值l l的特征矢的特征矢量。因此量。因此 称为称为FisherFisher最佳鉴别矢量最佳鉴别矢量，由上式有，由上式有 当N较大时，SW通常是非奇异的,于是有n上式右边后两项因子的乘积为一标量，上式右边后两项因子的乘积为一标量，令其为令其为 ，于是可得，于是可得n式式中中 为为一一标标量量因因子子，其其不不改改变变轴轴的的方方向，可以取为向，可以取为1 1,于是有于是有上式右边后两项因子的乘积为一标量，令其为 ，于是可得此时的此时的 可使可使FisherFisher准则函数取最大值，即是准则函数取最大值，即是n 维空维空间到一维空间投影轴的最佳方向，由间到一维空间投影轴的最佳方向，由JF 最大值为最大值为和和此时的 可使Fisher准则函数取最大值，即是n 维空间即即称称为为FisherFisher变换函数变换函数J JF F=即JF=可以根据训练模式确定一个阈值可以根据训练模式确定一个阈值 y yt t，于是，于是FisherFisher判判别规则别规则为为 判别阈值可取两个类心在判别阈值可取两个类心在u u方向上轴的投影连线的中点方向上轴的投影连线的中点作为阈值，即作为阈值，即（3)3)求解求解FisherFisher判别函数判别函数 可以根据训练模式确定一个阈值 yt，于是FisherFisher方法总结方法总结Fisher方法总结最优问题的求解：最优问题的求解：（1 1）一个适当的代价函数（准则函数）一个适当的代价函数（准则函数）（2 2）一个优化算法）一个优化算法 梯度下降法梯度下降法3.5 3.5 一次准则函数及梯度下降法一次准则函数及梯度下降法(Gradient Descent Algorithm)(Gradient Descent Algorithm)感知准则函数感知准则函数（RosenblattRosenblatt）最优问题的求解：3.5 一次准则函数及梯度下降法(Grad可微函数在某点的梯度是一个向量可微函数在某点的梯度是一个向量函数在该点的变化率最大的方向函数在该点的变化率最大的方向 函数函数 的梯度向量定义为的梯度向量定义为可微函数在某点的梯度是一个向量函数在该点的变化率最大的方梯度下降法的迭代公式为：梯度下降法的迭代公式为：任给定初始权矢量，第任给定初始权矢量，第k+1k+1次迭代时次迭代时的权矢量等于第的权矢量等于第k k次的权矢量加上被次的权矢量加上被w w（k k）错分的样本之合乘以某个系数。）错分的样本之合乘以某个系数。梯度下降法的迭代公式为：任给定初始权矢量，第k+1次迭把样本集看成不断出现的序列逐一考虑，把样本集看成不断出现的序列逐一考虑，称为单样本修正法。称为单样本修正法。且令且令 ，称为固，称为固定增量法。定增量法。使得使得 把样本集看成不断出现的序列逐一考虑，称为单样本修正法。+-+-+-+-如果训练模式是线性可分的，感知器如果训练模式是线性可分的，感知器训练算法在有限次迭代后便可以收敛到正训练算法在有限次迭代后便可以收敛到正确的解矢量确的解矢量 。感知收敛定理感知收敛定理如果训练模式是线性可分的，感知器训练算法在有限次迭代后便对两类问题，训练模式的符号规范化：对两类问题，训练模式的符号规范化：若若 则乘以则乘以1 1（包括增广分量（包括增广分量1 1）校正规则（增量校正规则（增量 0 0，可取为，可取为1 1）对两类问题，训练模式的符号规范化：若 则乘以3.5.1 3.5.1 感知器算法感知器算法(Perceptron Approach)(Perceptron Approach)算法思想算法思想任选一初始增广权矢量任选一初始增广权矢量用训练样本检验用分类正确否用训练样本检验用分类正确否对进行校正对进行校正对所有训练样本都能正确分类对所有训练样本都能正确分类？ENDYesYesYesNoNo3.5.1 感知器算法(Perceptron Approac算法步骤算法步骤已知类别的已知类别的增广增广训练模式集训练模式集(1)(1)置步数置步数k k=1=1，令增量令增量 =某正的常数，某正的常数，（各分量置为较小的任意值）；（各分量置为较小的任意值）；(2)(2)输入训练模式输入训练模式 ，计算判别函数值，计算判别函数值 ；(3)(3)调整增广权矢量，规则是调整增广权矢量，规则是(4)IF 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 3.5.3 感知器训练算法在多类问题中的应用判别规则：对于(1)(1)赋初值赋初值,分别给分别给c c个权矢量个权矢量w wi i(i=1,2,c)(i=1,2,c)赋任意的初值，赋任意的初值，选择正常数选择正常数，置步数，置步数k=1k=1(2)(2)输入已知类别的增广训练模式输入已知类别的增广训练模式x xk k，x xk k x x1 1,x,x2 2,.,x,.,xN N,计算计算c c个判别函数个判别函数 d di i(x(xk k)=w)=wi ixxk k (i=1,2,c)(i=1,2,c)(3)(3)权矢量修正规则权矢量修正规则:if (x if (xk ki i)and()and(d di i(x(xk k)d)dj j(x(xk k)()(j j i i)then)then w wi i(k+1)=w(k+1)=wi i(k)(i=1,2,c)(k)(i=1,2,c)(正确分类正确分类)if(x if(xk ki i)and()and(d di i(x(xk k)d dm m(x(xk k)(m)(m i i)then)then w wi i(k+1)=w(k+1)=wi i(k)+(k)+x xk k w wm m(k+1)=w(k+1)=wm m(k)-(k)-x xk kw wj j(k+1)=w(k+1)=wj j(k)(k)(j j i,mi,m)(4)if kN,(4)if kN,令令k=k+1,k=k+1,返至返至；if k=Nif k=N，检验是否对所有样本都能正确分类，若是，结束；，检验是否对所有样本都能正确分类，若是，结束；否则，令否则，令k=1k=1，返至，返至。算法步骤：算法步骤：(1)赋初值,分别给c个权矢量wi(i=1,2,c)赋例例题题:已已知知训训练练样样本本(0,0)(0,0)T T1 1,(1,1),(1,1)T T2 2,(-1,1),(-1,1)T T3 3,试求解向量试求解向量w w1 1、w w2 2和和w w3 3。解解:（1 1）训练样本分量增广化。将训练样本变成增广训练模式训练样本分量增广化。将训练样本变成增广训练模式：x1=(0,0,1)T,x2=(1,1,1)T,x3=(-1,1,1)T,注意：各类样本注意：各类样本不需符号规范化。不需符号规范化。（2 2）运用感知器训练算法。置）运用感知器训练算法。置k=1k=1，增量，增量=1=1，赋初值：，赋初值：w1=(0,0,0)T,w2=(0,0,0)T,w3=(0,0,0)T,进行迭代：进行迭代：k=1,xk=x1 1,因为因为d1(x1)=d2(x1)=0，d1(x1)=d3(x1)=0，错分，错分，所以所以:w1(2)=w1(1)+x1=(0,0,1)T w2(2)=w2(1)-x1=(0,0,-1)T w3(2)=w3(1)-x1=(0,0,-1)T k=2,xk=x2 2,因为因为d2(x2)=-1d1(x2)=1，d2(x2)=d3(x2)=-1，错分，错分，所以所以:w1(3)=w1(2)-x2=(-1,-1,0)T w2(3)=w2(2)+x2=(1,1,0)T w3(3)=w3(2)-x2=(-1,-1,-2)T例题:已知训练样本(0,0)T1,(1,1)T2,k=3,xk=x3 3,因为因为d3(x3)=-2d1(x3)=0，d3(x3)d1(x2)=-2，d2(x2)=0d3(x2)=-4，分类分类正确正确，所以所以 w1(6)=w1(5)=(0,-2,0)(0,-2,0)T T w2(6)=w2(5)=(2,0,-2)(2,0,-2)T T w3(6)=w3(5)=(-2,0,-2)(-2,0,-2)T T判别域代数界面方程法课件k=6,xk=x3 3,因为因为d3(x3)=0d1(x3)=-2，d3(x3)=0d2(x3)=-4，分类分类正确正确，所以所以 w1(7)=w1(6)=(0,-2,0)(0,-2,0)T T w2(7)=w2(6)=(2,0,-2)(2,0,-2)T T w3(7)=w3(6)=(-2,0,-2)(-2,0,-2)T Tk=7，xk=x1 3，因为因为d1(x1)=0d2(x1)=-2，d1(x1)=0d3(x1)=-2，三个权矢量不再变化，可以确定所有训练样本均已被正确分类，三个权矢量不再变化，可以确定所有训练样本均已被正确分类，由此得到三个解矢量：由此得到三个解矢量：w1*=w1(5)，w2*=w2(5)，w3*=w3(5)同时可得三个判别函数同时可得三个判别函数:d1(x)=-2x2d2(x)=2x1-2d3(x)=-2x1-2判别域代数界面方程法课件3.6 3.6 二次准则函数及其解法二次准则函数及其解法 问题：问题：一次准则函数及其算法（如感知器算法）一次准则函数及其算法（如感知器算法）只适用于线性可分的情况，如果是线性不可分只适用于线性可分的情况，如果是线性不可分的，分类过程将不收敛的，分类过程将不收敛?能否找到一种算法，使之能够测试出模式能否找到一种算法，使之能够测试出模式样本集是否线性可分，并且对线性不可分的样本集是否线性可分，并且对线性不可分的情况也能给出情况也能给出“次最优次最优”的解？的解？3.6 二次准则函数及其解法 问题：能否找到一种 如果训练模式是线性不可分如果训练模式是线性不可分不等式组是不等式组是不一致不一致的，不等的，不等式组没解。此时，式组没解。此时，目标目标最少的训练模式被错分。最少的训练模式被错分。（一）最小错分模式数目准则（一）最小错分模式数目准则 对线性不可分样本集，求一解矢量使得错分的模式数目最少。对线性不可分样本集，求一解矢量使得错分的模式数目最少。对于两类问题，设对于两类问题，设n+1n+1维增广训练模式维增广训练模式已符号规范化已符号规范化。如果训练模式是线性可分的，则存在权矢量如果训练模式是线性可分的，则存在权矢量 使不等式组使不等式组成立。成立。如果训练模式是线性不可分不等式组是不一致的，不等式组没解式中式中 是是 矩阵。矩阵。将上面的不等式组写成矩阵方程形式，并引入将上面的不等式组写成矩阵方程形式，并引入N 维余量矢量维余量矢量 ，于是不等式方程组变为，于是不等式方程组变为式中 是 矩阵。将上面（二）最小方差准则及（二）最小方差准则及W-HW-H算法算法 针对方程组针对方程组 ,构造方差准则函数构造方差准则函数 对于对于 ,此时的此时的 ,而对于而对于 ,此时的此时的 。如果方程组有唯一解。如果方程组有唯一解,说说明训练模式集是线性可分的明训练模式集是线性可分的,如果方程组无解如果方程组无解,极小点值是最极小点值是最小二乘解。一般情况下使小二乘解。一般情况下使 极小等价于误分模式数目最少极小等价于误分模式数目最少。（二）最小方差准则及W-H算法 伪逆法伪逆法 求求 对对 的梯度并令其为零，有的梯度并令其为零，有 可得可得 (3-6-12)(3-6-12)当当(X X X X)-1-1存在时，存在时，X X+=(=(X X X X)-1-1X X 称为称为X X的伪逆的伪逆(也称广义逆或也称广义逆或M-PM-P逆逆)，称为称为 的伪逆解。的伪逆解。X X X X是是(n n+1)(+1)(n n+1)+1)矩阵，一般是非奇异的。矩阵，一般是非奇异的。当当(X X X X)-1-1不存在时，可用广义逆法解不存在时，可用广义逆法解 这里这里(X X X X)+为为X X X X的广义逆矩阵。的广义逆矩阵。求解最佳权矢量的方法：求解最佳权矢量的方法：伪逆法求解最佳权矢量的方法：梯度法梯度法由前述知，由前述知，的梯度为的梯度为梯度下降算法迭代公式为梯度下降算法迭代公式为Step1.Step1.任取任取Step2.Step2.(3-6-13)可以证明，当可以证明，当 为任意正的常数，为任意正的常数，则该算法使权矢量序列则该算法使权矢量序列 收敛于收敛于 ;满足满足 ，也称为也称为MSEMSE解。解。梯度法由前述知，的梯度为梯度下降算法迭代公式为S 此算法的两个性质此算法的两个性质:1.1.当当 时时,MSE,MSE解解 等价于等价于FisherFisher解。解。2.2.令令 ,在样本数在样本数 时时,MSE,MSE解以最小均解以最小均方误差逼近贝叶斯判决函数方误差逼近贝叶斯判决函数Step1.Step1.任取任取Step2.Step2.此算法通常称为此算法通常称为W WH(WidrowH(WidrowHoff)Hoff)算法算法仿前采用单样本修正法，则式仿前采用单样本修正法，则式(3-6-13)(3-6-13)可以修改为可以修改为为了减少计算量和存储量，由于为了减少计算量和存储量，由于(3-6-14)此算法的两个性质:Step1.任取仿前采用单样本修正法，二次准则函数及其算法小结二次准则函数及其算法小结 二次准则函数及其算法小结 312 312 势函数分类法势函数分类法 概念概念：1：q+；2：q-定义点定义点 处的位势函数处的位势函数 ，它应满足：，它应满足：；是连续光滑函数；是连续光滑函数；是是 与与 间距离的单值单调下降间距离的单值单调下降函数函数;当且仅当当且仅当 时，时，达其最大达其最大值值;312 势函数分类法 概念：1：q+；2：q-第一类位势函数第一类位势函数设设 是是 定义域中的完备正交函数集，定义域中的完备正交函数集，位势函数取为位势函数取为第二类位势函数第二类位势函数取关于取关于 和和 的距离的对称函数作位势函数，的距离的对称函数作位势函数，例如例如两类位势函数两类位势函数第一类位势函数两类位势函数位势函数图例位势函数图例位势函数图例令初始积累位势函数令初始积累位势函数 ;判错计数判错计数m =0;=0;令令j j=1=1，输入训练模式，输入训练模式 ，使，使积累位势函数积累位势函数令令 j j=j j+1+1，输入，输入 ，计算积累位势函数，计算积累位势函数(4)(4)如果如果 j j N N ，返至，返至；如果；如果j j=N N ，检查是否有模式判错；，检查是否有模式判错；若若 m m=0=0，则结束。，则结束。若若 m m00，则令，则令 j j=0=0，m m=0,=0,返至返至。位势函数分类训练位势函数分类训练算法算法令初始积累位势函数 ;判错计数m=0;位判别规则判别规则：判别规则：积累位势函数图例积累位势函数图例积累位势函数图例设初始积累位势函数设初始积累位势函数 ,i i=1,2,=1,2,c c表示类别。表示类别。当当 时，迭代规则是时，迭代规则是 在全部训练模式均满足在全部训练模式均满足 算法结束。算法结束。位势函数训练算法用于位势函数训练算法用于多类问题多类问题设初始积累位势函数 ,i=1,2,判别规则判别规则：判别规则：例：已知如图例：已知如图(3-12-1)(3-12-1)所示两类训练样本：所示两类训练样本：试用势函数法进行分类器训练。试用势函数法进行分类器训练。解：选用第二类势函数，令解：选用第二类势函数，令=1=1，在二维情况下，在二维情况下，为积累位势函数为积累位势函数)(exp)0()0(exp ),()(,1222122211111xxxxxxKxKxj+-=-+-=rrrr例：已知如图(3-12-1)所示两类训练样本：试判别域代数界面方程法课件判别域代数界面方程法课件令令判别界面判别界面令判别界面判别界面判别界面x2=x1-1x2=1-x1判别界面x2=x1-1x2=1-x180作业作业3.2 3.2 以下列两类模式为样本，用感知器算法求其判决函数。以下列两类模式为样本，用感知器算法求其判决函数。（令令 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),(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),3.3 3.3 用用W-HW-H算法求解算法求解3.23.2题。题。3.4 3.4 已知已知 1 1：(0,0),(0,0),2 2：(1,1),(1,1),3 3：(-1,1)(-1,1)。用感知器算法求该三类问题的判别函数，并画出解区域。用感知器算法求该三类问题的判别函数，并画出解区域。上机上机:编写感知器判别程序编写感知器判别程序80作业3.2 以下列两类模式为样本，用感知器算法求其判决函第三章第三章 类域界面方程法类域界面方程法 总结总结 分类分类特征空间的分划特征空间的分划子空间的界面：子空间的界面：1 1、判别函数的形式、判别函数的形式2 2、判别规则、判别规则求解参数求解参数 第三章 类域界面方程法 总结 分类特征空间的分划子空间的第三章第三章 类域界面方程法类域界面方程法 总结总结 32 32 线性判别函数线性判别函数 式中式中 称为权矢量或系数矢量。称为权矢量或系数矢量。写成矢量形式写成矢量形式这里，这里，称，称为为增广特征矢量增广特征矢量和和增广权矢量增广权矢量。增广特征矢量的全体。增广特征矢量的全体称为称为增广特征空间增广特征空间。第三章 类域界面方程法 总结 32 线性判别函数 判别规则判别规则：解多类问题的两分法解多类问题的两分法:两分法两分法 有不确定区域有不确定区域 两分法两分法 没有不确定区的没有不确定区的 两分法两分法 令令判别规则：解多类问题的两分法:两分法 33 33 判别函数值的鉴别意义、判别函数值的鉴别意义、权空间及解空间权空间及解空间（1 1）系数矢量）系数矢量 是超平面是超平面 的法矢量；的法矢量；（2 2）的绝对值的绝对值 正比于正比于 到超平面的到超平面的距离；距离；（3 3）的正（负）反映的正（负）反映 在超平面在超平面 的的正（负）侧。正（负）侧。33 判别函数值的鉴别意义、权空间及解空间 34 Fisher34 Fisher线性判别线性判别 多维多维 FisherFisher变换变换 利于分类的一维利于分类的一维 （1 1）FisherFisher准则函数准则函数 对两类问题对两类问题 作变换，作变换，n n维矢量维矢量 在矢量在矢量 方向轴上的投影方向轴上的投影FisherFisher准则函数准则函数 34 Fisher线性判别 多维 Fisher变换（2 2）FisherFisher变换变换 FisherFisher变换函数变换函数：（3 3）FisherFisher判别规则判别规则 （2）Fisher变换 1 1一次准则函数（感知准则函数）一次准则函数（感知准则函数）2 2固定增量法固定增量法 3.5 一次准则函数及梯度下降法 3.5 一次准则函数及梯度下降法 3 3单样本修正法单样本修正法4.4.算法描述算法描述：如果训练模式已经符号规范化，即如果训练模式已经符号规范化，即 已乘以已乘以1 1（包括增广分量（包括增广分量1 1），则），则 收敛定理收敛定理判别域代数界面方程法课件36 36 二次准则函数及其算法二次准则函数及其算法 1 1、最小错分样本准则、最小错分样本准则2 2、最小方差准则、最小方差准则（1 1）伪逆法）伪逆法36 二次准则函数及其算法 1、最小错分样本准则（1）伪3 36 6 二次准则函数及其算法二次准则函数及其算法 （2 2）梯度法）梯度法MSEMSE解：解：W-HW-H算法算法：36 二次准则函数及其算法（2）梯度法312 312 势函数分类法势函数分类法 概念概念：1：q+；2：q-定义点定义点 处的位势函数处的位势函数 ，它应满足：，它应满足：；是连续光滑函数；是连续光滑函数；是是 与与 间距离的单值单调下降间距离的单值单调下降函数函数;当且仅当当且仅当 时，时，达其最大达其最大值值;312 势函数分类法 概念：1：q+；2：q-第一类位势函数第一类位势函数设设 是是 定义域中的完备正交函数集，定义域中的完备正交函数集，位势函数取为位势函数取为第二类位势函数第二类位势函数取关于取关于 和和 的距离的对称函数作位势函数，的距离的对称函数作位势函数，例如例如两类位势函数两类位势函数第一类位势函数两类位势函数判别规则判别规则：判别规则：设初始积累位势函数设初始积累位势函数 ,i i=1,2,=1,2,c c表示类别。表示类别。当当 时，迭代规则是时，迭代规则是 在全部训练模式均满足在全部训练模式均满足 算法结束。算法结束。位势函数训练算法用于位势函数训练算法用于多类问题多类问题设初始积累位势函数 ,i=1,2,判别规则判别规则：判别规则：练习练习1 1、利用两类方法处理多类问题的技术途径有几、利用两类方法处理多类问题的技术途径有几种？种？2 2、判别函数的值和正负在分类中的意义是什么、判别函数的值和正负在分类中的意义是什么？3 3、感知器算法和、感知器算法和W-HW-H算法的适应范围？算法的适应范围？4 4、模式识别系统的基本构成单元包括什么？、模式识别系统的基本构成单元包括什么？5 5、影响层次聚类算法结果的主要因素有哪些？、影响层次聚类算法结果的主要因素有哪些？6 6、欧式距离、马式距离分别具有哪些不变性？、欧式距离、马式距离分别具有哪些不变性？（1 1）平移不变性（）平移不变性（2 2）旋转不变性（）旋转不变性（3 3）尺度缩）尺度缩放不变性（放不变性（4 4）不受量纲影响的特性）不受量纲影响的特性练习1、利用两类方法处理多类问题的技术途径有几种？练习练习7 7、下列函数可以作为聚类分析中的准则函数、下列函数可以作为聚类分析中的准则函数的有的有 （1 1）（2 2）（3 3）（4 4）8 8、影响聚类结果的主要因素有那些？、影响聚类结果的主要因素有那些？练习7、下列函数可以作为聚类分析中的准则函数的有