现代模式识别

模式识别主讲：蔡宣平教授

电话：73441（O）,73442（H）

E-mail：xpcai@

单位:电子科学与工程学院信息工程系1

第三章判别域代数界面方程法3.1

用判别域界面方程分类的概念3.2线性判别函数3.3判别函数值的鉴别意义、权空间及解空间3.4Fisher线性判别3.5一次准则函数及梯度下降法3.6二次准则函数及其解法3.9广义线性判别函数3.10二次判别函数3.12位势函数分类法有监督分类2

3.1用判别域界面方程分类的概念3两类的分类问题，它们的边界线就是一个判别函数4两类问题中线性不可分的实例5三类的分类问题，它们的边界线也是一个判别函数63.1用判别域界面方程分类的概念

第三章判别域代数界面方程法7

3.2线性判别函数

第三章判别域代数界面方程法8910多类问题图例（第一种情况）?不确定区域111、第一种情况（续）判别规则为：如果

则判

比如对图的三类问题,如果对于任一模式如果它的则该模式属于ω1类。121、第一种情况（续）如果某个X使二个以上的判别函数di>0

。则此模式X就无法作出确切的判决。如图另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确定区域。131、第一种情况（续）解：三个判别边界分别为：141、第一种情况（续）结论：因为所以它属于ω2类。151、第一种情况（续）16172、第二种情况（续）多类问题图例（第二种情况）1819d12(x)=-d21(x)=–x1–x2+5=0d12(x)为正两分法例题图示0123456789987654321d21(x)为正20d12(x)为正两分法例题图示0123456789987654321d21(x)为正d23(x)=-d32(x)=–x1+x2=0d32(x)为正d23(x)为正21d12(x)为正两分法例题图示0123456789987654321d21(x)为正d32(x)为正d23(x)为正d13(x)=-d31(x)=–x1+3=0d31(x)为正d13(x)为正221类判别区域

d12(x)>0d13(x)>02类判别区域

d21(x)>0d23(x)>0d12(x)为正两分法例题图示0123456789987654321d21(x)为正d32(x)为正d23(x)为正d31(x)为正d13(x)为正3类判别区域

d31(x)>0d32(x)>0IR23243、第三种情况（续）多类问题图例（第三种情况）25。26上述三种方法小结:方法⑶判别函数的数目和方法⑴相同，但没有不确定区，分析简单，是最常用的一种方法。时，法比法需要更多当的判别函数式，这是一个缺点。类与其余的开，而法是将类和类分开，显然法是将但是类区分法使模式更容易线性可分，这是它的优点。273.3判别函数值的鉴别意义、权空间及解空间

第三章判别域代数界面方程法28此方程表示一超平面。它有以下三个性质:(1)系数矢量，是该平面的法矢量。(2)判别函数的绝对值正比于到超平面的距离。(3)判别函数值的正负表示出特征点位于哪个半空间中。3.3判别函数值的鉴别意义、权空间及解空间

第三章判别域代数界面方程法29图3.3.1点面距离及界面的正负侧示意图2x1xo+-0)(=xdrnrprpxrr-30313233证明：判别函数值的正负表示出特征点位于哪个半空间中。34背向的半空间中时，当在这说明判别函数值的正负表示出特征点位于哪个半空间中，或者换句话说，表示特征点位于界面的哪一侧。和，故同号。由于在指向的半空间中时，即35例3.3.1：利用判别函数的鉴别意义，试分析d(x1,x2)＝x1+x2+1。d(x1,x2)＝0＋－×××××××××××××－－－－－－－－－－－－-1-1363.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间37(2)解矢量3.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间38(2)解矢量3.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间393.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间40(3)解空间3.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间先看一个简单的情况。设一维数据1，2属于w1,-1，-2属于w2求将w1和w2区分开的w0

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

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

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

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

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

，w1。w0w146(3)解空间3.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间473.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间每一个训练模式都对解区提供一个约束，训练模式越多，解区的限制就越多，解区就越小，就越靠近解区的中心，解矢量就越可靠，由它构造的判别函数错分的可能性就越小。48(4)余量3.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间49(4)余量3.3.2权空间、解矢量与解空间3.3判别函数值的鉴别意义、权空间及解空间引入了余量可有效地避免量测的误差、引入的误差以及某些算法求得的解矢量收敛于解区的边界上，从而提高了解的可靠性。50设一3类问题有如下判决函数

d1(x)=-x1

d2(x)=x1+x2-1

d3(x)=x1-x2-1

试画出下列各种情况的判决边界及各类的区域：

（1）满足3.4.2节中的第一种情况；

（2）满足3.4.2节中的第二种情况,且令

d12(x)=d1(x)，d13(x)=d2(x)，d23(x)=d3(x)；

（3）满足3.4.2节中的第三种情况。作业513.4Fisher线性判别

第三章判别域代数界面方程法52二维模式向一维空间投影示意图uroxy53二维模式向一维空间投影示意图uroxy54二维模式向一维空间投影示意图oxyoxy55（1)求解Fish准则函数5657类间离差度为：58并使其最大,上式称为Fisher准则函数。59利用二次型关于矢量求导的公式可得：（2)求解Fisher最佳鉴别矢量令可得：6061上式右边后两项因子的乘积为一标量，令其为，于是可得式中为一标量因子，其不改变轴的方向，可以取为1,于是有62此时的可使Fisher准则函数取最大值，即是n

维空间到一维空间投影轴的最佳方向，由和JF最大值为:’63即称为Fisher变换函数JF=64

由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点，所以可以根据训练模式确定一个阈值yt，于是Fisher判别规则为:（3)求解Fisher判别函数判别阈值可取两个类心在u方向上轴的投影连线的中点作为阈值，即:6566（7）计算。（8）计算yt。（9）对未知模式x判定模式类。67以100元A面数据和50元A面数据为例100元A面:(64,76,99,84,98,95,88,83),…50元A面:(65,67,82,80,89,94,86,92),…N1=N2=60算得:m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)68m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)69m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91,91.1,86.5)70m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91,91.1,86.5)71m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91,91.1,86.5)727374利用给定的一个样本数据编写100元B面与50元A面的Fisher判别门限的程序，并用另一个样本数据验证之。上机练习753.5一次准则函数及梯度下降法3.5.1感知器算法(PerceptronApproach)任选一初始增广权矢量用训练样本检验分类是否正确对所有训练样本都正确分类？YesENDYesNo对权值进行校正No感知器算法流程图流程:763.5一次准则函数及梯度下降法3.5.1感知器算法(PerceptronApproach)77

(3)调整增广权矢量，规则是

--如果和，则

--如果和，则

--如果和，或和，则

(4)如果k<N，令k=k+1，返至⑵。如果k=N，检验判别函数对是否都能正确分类。若是，结束；若不是,令k=1，返至⑵。78权空间中感知器算法权矢量校正过程示意图)(ikxr+-)(ikxr)(kwr)1(+kwr)(jkxr+-)(jkxr-)(kwr)1(+kwr79二、收敛定理：

如果训练模式是线性可分的，感知器训练算法在有限次迭代后便可以收敛到正确的解矢量。。证明思路：

如果第k+1次迭代生成的权矢量比第k次迭代生成的权矢量更接近解矢量，则收敛，即：80、

、

81

(1)训练样本分量增广化及符号规范化。82

83

84852.用感知器算法求解向量,训练样本为:w1:{(0,0,0)T,(1,0,0)T,(1,0,1)T,(1,1,0)T}w2:{(0,0,1)T,(0,1,1)T,(0,1,0)T,(1,1,1)T}作业设两类样本的类内离差矩阵分别为:试用Fisher准则求其决策面方程。863.5.2一次准则函数及梯度下降法一、梯度下降法采用梯度下降法沿负梯度方向，选择适当的步长进行搜索，求解函数的极小值点。

第三章判别域代数界面方程法8788增广权矢量的修正迭代公式为：令k=1/2，求得准则函数的梯度其中符号函数89增广权矢量修正迭代公式：称为单样本修正，实际也可构造批量修正：式中的是被错分类的模式集。

90913.5.3感知器训练算法在多类问题中的应用判别规则：

对于c类问题，应建立c个判别函数：

di(x)=wi’xi(i=1,2,…,c)

如果xi，则有wi’x>wj’x(ji)

因此判别规则是

若di(x)>dj(x)ji则判xi

第三章判别域代数界面方程法92(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋任意的初值，选择正常数，置步数k=1。算法步骤：(2)输入已知类别的增广训练模式xk，计算c个判别函数

di(xk)=wi’xk(i=1,2,…,c)(3)修正权矢量，修正规则是：

if(xki)and(di(xk)>dj(xk))(ji)then

wi(k+1)=wi(k)(i=1,2,…,c)(正确分类)

if(xki)and(di(xk)dl(xk))(li)then

wi(k+1)=wi(k)+xk

wl(k+1)=wl(k)-xk

wj(k+1)=wj(k)(ji,l)93(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋任意的初值，选择正常数，置步数k=1。算法步骤：(2)输入已知类别的增广训练模式xk，计算c个判别函数di(xk)=wi’xk(i=1,2,…,c)(4)ifk<N,令k=k+1,返至⑵；

ifk=N，检验判别函数是否对都能正确分类，若是，结束；否则，令k=1，返至⑵。(3)修正权矢量。94例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

（2）运用感知器训练算法。置k=1，增量=1，赋初值：w1=(0,0,0)T,w2=(0,0,0)T,w3=(0,0,0)T,进行迭代运算：解:（1）训练样本分量增广化。将训练样本变成增广训练模式：x1=(0,0,1)T,x2=(1,1,1)T,x3=(-1,1,1)T,

这里的下标恰是所属类别，各类样本不需符号规范化。95例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=1,xk=x11,因为d1(x1)=d2(x1)=0，d1(x1)=d3(x1)=0，错分，所以:w1(2)=w1(1)+x1=(0,0,1)Tw2(2)=w2(1)-x1=(0,0,-1)Tw3(2)=w3(1)-x1=(0,0,-1)Tk=2,xk=x22,因为d2(x2)=-1<d1(x2)=1，d2(x2)=d3(x2)=-1，错分，所以w1(3)=w1(2)-x2=(-1,-1,0)Tw2(3)=w2(2)+x2=(1,1,0)T

w3(3)=w3(2)-x2=(-1,-1,-2)T96例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=3,xk=x33,因为d3(x3)=-2<d1(x3)=0，d3(x3)=d2(x3)=0，错分，所以w1(4)=w1(3)-x3=(0,-2,-1)Tw2(4)=w2(3)-x3=(2,0,-1)T

w3(4)=w3(3)+x3=(-2,0,-1)Tk=4,xk=x11,因为d1(x1)=d2(x1)=-1，d1(x1)=d3(x1)=-1，错分，所以w1(5)=w1(4)+x1=(0,-2,0)Tw2(5)=w2(4)-x1=(2,0,-2)T

w3(5)=w3(4)-x1=(-2,0,-2)T97例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=5,xk=x22,因为d2(x2)=0>d1(x2)=-2，d2(x2)=0>d3(x2)=-4，正确，所以w1(6)=w1(5)=(0,-2,0)Tw2(6)=w2(5)=(2,0,-2)T

w3(6)=w3(5)=(-2,0,-2)Tk=6,xk=x33,因为d3(x3)=0>d1(x3)=-2，d3(x3)=0>d2(x3)=-4，正确，所以w1(7)=w1(6)=(0,-2,0)Tw2(7)=w2(6)=(2,0,-2)T

w3(7)=w3(6)=(-2,0,-2)T98例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

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

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

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

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

107W-H算法有两个性质108109⑶H-K算法求解最佳权矢量的方法——H-K算法的迭代公式为：其中110111H-K算法步骤Step2.置初值Step1.将训练样本符号规范化，得X

求伪逆Step3.计算

112H-K算法步骤Step6.k=k+1;gotoStep3;Step5.113114115作业1以下列两类模式为样本，用LMSE(梯度法)算法求解判决函数。（令w(1)=(-1,-2,-2)’

）

1：{(0,0,0)’,(1,0,0)’,(1,0,1)’,(1,1,0)’,}

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

设一维两类模式x在一维空间──坐标轴上分布如图3-9-1所示，两类的类域为和

3.9广义线性判别函数图3.9.1一维特征空间中非线性可分的图示117显然，这两类不是线性可分的，因不能用一个分界点将两类分开。但是，对于一条穿过a、b两点的二次曲线，当即或时,当即时,118原来的一维非线性可分的模式在所映射的二维特征空间中是线性可分的，即:119使在特征空间是线性可分的,称其为广义线性判别函