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

第三章判别域代数界面方程法第三章颜色（绿/红）似圆度判别函数(DiscriminantFunction)3.1判别域代数界面方程法的概念颜色（绿/红）似圆度判别函数3.1判别域代数界面方程法的概判别函数的形式线性非线性判别规则参数确定3.1判别域代数界面方程法的概念判别函数的形式3.1判别域代数界面方程法的概念3.2.1判别函数的形式3.2线性判别函数模式的特征矢量：判别函数：称为权矢量或系数矢量3.2.1判别函数的形式3.2线性判别函数模式的特征矢量：3.2.1判别函数的形式增广特征矢量：增广权矢量：判别函数：3.2线性判别函数3.2.1判别函数的形式增广特征矢量：增广权矢量：判别函数：3.2.2判别规则3.2线性判别函数1、两类问题颜色（绿/黄）似圆度3.2.2判别规则3.2线性判别函数1、两类问题颜色（绿/判别规则:3.2线性判别函数1、两类问题3.2.2判别规则判别规则:3.2线性判别函数1、两类问题3.2.2判别规则3.2.2判别规则

2、多类问题（1）二分法（2）ωi/ωj二分法（3）最大判别准则3.2线性判别函数3.2.2判别规则（1）二分法3.2线性判别函（1）二分法

2、多类问题（1）二分法 2、多类问题具有性质：

M个判别函数：

（1）二分法判别规则：

2、多类问题具有性质：M个判别函数：（1）二分法判别例1：已知三类ω1,ω2,ω3的判别函数分别为：问

属于哪一类？（1）二分法

2、多类问题解：代入结论：属于ω2类。例1：已知三类ω1,ω2,ω3的判别函数分别为：问结论：判别区间增大，不确定区间减小IR（2）ωi/ωj二分法

2、多类问题结论：判别区间增大，不确定区间减小IR（2）ωi/ωj二分法（2）ωi/ωj二分法有M(M_1)/2个判别平面区分ωi/ωj的判别函数：

具有性质：

2、多类问题判别规则：（2）ωi/ωj二分法有M(M_1)/2个判别平面区分例2：已知三类ω1,ω2,ω3，判别函数分别为：问：当时属于哪一类？（2）ωi/ωj二分法

2、多类问题解：代入判别函数可得:下标变换可得:例2：已知三类ω1,ω2,ω3，判别函数分别为：问：当或（3）最大判别准则

2、多类问题M个判别函数：判别规则：如果，则判，则判或如果判别界面：或（3）最大判别准则 2、多类问题M个判别函数：判别规则：如（3）最大判别准则

2、多类问题结论：无不确定区间（3）最大判别准则 2、多类问题结论：无不确定区间例：假设判别函数为：问属于哪一类。（3）最大判别准则

2、多类问题解：所以例：假设判别函数为：问属于哪一类。（3）最大三种方法小结

2、多类问题分类方法判别函数个数不确定区难易ωi/ωi二分法ωi/ωj二分法最大判别准则MM(M-1)/2M最多较少没有较难较易较易三种方法小结 2、多类问题分类方法判别函数个数不确定区难易ω3.1设一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节中的第三种情况。作业3.1设一3类问题有如下判决函数

d1(x)=-x13.3.1判别函数值的大小、正负的数学意义n维特征空间Xn中，两类问题的线性判别界面方程为此方程表示一超平面，记为

是该平面的法矢量。3.3判别函数值的鉴别意义、权空间及解空间3.3.1判别函数值的大小、正负的数学意义3.3判别函数值2x1xo+-0)(=xdrnrprpxrr-3.2判别函数值的鉴别意义、权空间及解空间3.3.1判别函数值的大小、正负的数学意义(1)系数矢量是该平面的法矢量。(2)判别函数的绝对值正比于特征点到超平面的距离。(3)判别函数值的正负表示出特征点位于哪个半空间中。2x1xo+-0)(=xdrnrprpxrr-3.2判别函数例3：利用判别函数的鉴别意义，试分析d(x1,x2)＝x1+x2+1。d(x1,x2)＝0＋－×××××××××××××－－－－－－－－－－－－-1-13.2判别函数值的鉴别意义、权空间及解空间3.3.1判别函数值的大小、正负的数学意义例3：利用判别函数的鉴别意义，试分析d(x1,x2)＝x1+(1)权空间增广特征矢量与增广权矢量是对称的，判别函数可以写成

视为相应的的“权”指向平面的正侧，即该半空间中的任一点都使背向的半子空间中任一点都有。3.2判别函数值的鉴别意义、权空间及解空间3.3.2权空间、解矢量与解空间(1)权空间增广特征矢量与增广权矢量是对称的，判别函数可以写解空间示意图o+-w1w2b余量解空间示意图o+-w1w2b余量w1w2w3wIIIIIIIVw1w2w3wIIIIIIIV（a）解空间（b）训练模式符号化后的解空间图(3-3-2)权空间中的判别界面及解锥w1w2w3wIIIIIIIVw1w2w3wIIIIIIIV(2)解矢量

对于两类问题，在对待分类模式进行分类之前，应根据已知类别的增广训练模式，确定线性判别函数

这时的称为解矢量，记为可以将已知类别的训练模式符号规范化。3.2判别函数值的鉴别意义、权空间及解空间3.3.2权空间、解矢量与解空间(2)解矢量对于两类问题，在对待分类模式进行分类之(3)解空间

以权空间原点为顶点的凸多面锥。锥中每一点都是上面不等式组的解，解矢量不是唯一的，上述的凸多面锥包含了解的全体，称其为解区、解空间或解锥。每一个训练模式都对解区提供一个约束，训练模式越多，解区的限制就越多，解区就越小，就越靠近解区的中心，解矢量就越可靠，由它构造的判别函数错分的可能性就越小。3.2判别函数值的鉴别意义、权空间及解空间3.3.2权空间、解矢量与解空间(3)解空间以权空间原点为顶点的凸多面锥。锥中每(4)余量为使解矢量可靠,使解区更小,可以采取增加训练模式数以及引入余量,使,这样，有效地避免了量测的误差、引入的误差以及某些算法求得的解矢量收敛于解区的边界上，从而提高了解的可靠性。它的边界离开原解区边界的距离为3.3.2权空间、解矢量与解空间3.2判别函数值的鉴别意义、权空间及解空间(4)余量为使解矢量可靠,使解区更小,可以采取增加训练模式

图3.4.1二维模式向一维空间投影示意图3.4Fisher线性判别图3.4.1二维模式向一维空间投影示意图3.思想：多维

Fisher变换

利于分类的一维

方法：求权矢量

求满足上述目标的投影轴的方向和在一维空间中确定判别规则。3.4Fisher线性判别思想：多维Fisher变换利于分类的一维方法：

用表示待求的。

设给定n维训练模式，其中有N1个和N2=N-N1

个模式分属w1类和w2类，分别记为和，各类模式均值矢量为

各类类内离差阵SWi和总的类内离差阵SW分别为（1)求解Fisher准则函数用表示待求的。

（1)求解Fisher准则函数（1)求解Fisher准则函数

取类间离差阵为

作变换，n维矢量在以矢量为方向的轴上进行投影

变换后在一维y空间中各类模式的均值为i=1,2i=1,2取类间离差阵为

i=1,2i=1,2

类内离差度和总的类内离差度为类间离差度为类内离差度和总的类内离差度为

希望经投影后，类内离差度越小越好，类间离差度越大越好，根据这个目标作准则函数

并使其最大,上式称为Fisher准则函数。希望经投影后，类内离差度

利用二次型关于矢量求导的公式可得令

可得（2)求解Fisher最佳鉴别矢量（2)求解Fisher最佳鉴别矢量

当N较大时，SW通常是非奇异的,于是有

上式表明，是矩阵相应于特征值l的特征矢量。因此称为Fisher最佳鉴别矢量，由上式有当N较大时，SW通常是非奇异的,于是有上式右边后两项因子的乘积为一标量，令其为，于是可得式中为一标量因子，其不改变轴的方向，可以取为1,于是有上式右边后两项因子的乘积为一标量，令其为，于是可得此时的可使Fisher准则函数取最大值，即是n

维空间到一维空间投影轴的最佳方向，由JF最大值为和此时的可使Fisher准则函数取最大值，即是n维空间即称为Fisher变换函数JF=即JF=

可以根据训练模式确定一个阈值yt，于是Fisher判别规则为

判别阈值可取两个类心在u方向上轴的投影连线的中点作为阈值，即（3)求解Fisher判别函数可以根据训练模式确定一个阈值yt，于是Fisher方法总结Fisher方法总结最优问题的求解：（1）一个适当的代价函数（准则函数）（2）一个优化算法梯度下降法3.5一次准则函数及梯度下降法

(GradientDescentAlgorithm)感知准则函数（Rosenblatt）最优问题的求解：3.5一次准则函数及梯度下降法

(Grad可微函数在某点的梯度是一个向量

函数在该点的变化率最大的方向函数的梯度向量定义为可微函数在某点的梯度是一个向量

函数在该点的变化率最大的方梯度下降法的迭代公式为：

任给定初始权矢量，第k+1次迭代时的权矢量等于第k次的权矢量加上被w（k）错分的样本之合乘以某个系数。

梯度下降法的迭代公式为：任给定初始权矢量，第k+1次迭把样本集看成不断出现的序列逐一考虑，称为单样本修正法。且令，称为固定增量法。使得把样本集看成不断出现的序列逐一考虑，称为单样本修正法。+-+-+-+-如果训练模式是线性可分的，感知器训练算法在有限次迭代后便可以收敛到正确的解矢量。感知收敛定理如果训练模式是线性可分的，感知器训练算法在有限次迭代后便对两类问题，训练模式的符号规范化：

若则乘以－1（包括增广分量1）校正规则（增量ρ>0，可取为1）对两类问题，训练模式的符号规范化：

若则乘以－3.5.1感知器算法(PerceptronApproach)

算法思想任选一初始增广权矢量用训练样本检验用分类正确否对进行校正对所有训练样本都能正确分类？ENDYesYesNoNo3.5.1感知器算法(PerceptronApproac算法步骤已知类别的增广训练模式集(1)置步数k=1，

令增量

=某正的常数，（各分量置为较小的任意值）；(2)输入训练模式，计算判别函数值；(3)调整增广权矢量，规则是(4)IFk<Nthenk=k+1goto(2);

else(k=N)IF[]thenEnd.

elsek=1;goto(2);算法步骤已知类别的增广训练模式集图2两类模式感知器训练算法例题作业：取初始权矢量重做本例题（p58例3.5.1）图2两类模式感知器训练算法例题例：已知解：(1)训练样本分量增广化及符号规范化：

(2)给增广权矢量赋任意初值，取增量

=1，例：已知解：(1)训练样本分量增广化及符号规范化：3.5.3感知器训练算法在多类问题中的应用判别规则：

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

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

如果x

i，则有wi’x>wj’x(ji)

因此判别规则是

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

i

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

对于(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋任意的初值，

选择正常数

，置步数k=1(2)输入已知类别的增广训练模式xk，xk

{x1,x2,...,xN},

计算c个判别函数

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

if(xk

i)and(di(xk)>dj(xk))(ji)then

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

if(xk

i)and(di(xk)

dm(xk))(mi)then

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

xk

wm(k+1)=wm(k)-

xk

wj(k+1)=wj(k)(ji,m)(4)ifk<N,令k=k+1,返至⑵；

ifk=N，检验是否对所有样本都能正确分类，若是，结束；否则，令k=1，返至⑵。算法步骤：(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋例题:已知训练样本(0,0)T

1,(1,1)T

2,(-1,1)T

3,试求解向量w1、w2和w3。解:（1）训练样本分量增广化。将训练样本变成增广训练模式：

x1=(0,0,1)T,x2=(1,1,1)T,x3=(-1,1,1)T,

注意：各类样本不需符号规范化。（2）运用感知器训练算法。置k=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)Tw2(2)=w2(1)-x1=(0,0,-1)Tw3(2)=w3(1)-x1=(0,0,-1)Tk=2,xk=x2

2,因为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)Tw3(3)=w3(2)-x2=(-1,-1,-2)T例题:已知训练样本(0,0)T1,(1,1)T2,k=3,xk=x3

3,因为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)Tw3(4)=w3(3)+x3=(-2,0,-1)Tk=4,xk=x1

1,因为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)Tw3(5)=w3(4)-x1=(-2,0,-2)Tk=5,xk=x2

2,因为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)Tw3(6)=w3(5)=(-2,0,-2)T判别域代数界面方程法课件k=6,xk=x3

3,因为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)Tw3(7)=w3(6)=(-2,0,-2)Tk=7，xk=x1

3

，因为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-2判别域代数界面方程法课件3.6二次准则函数及其解法

问题：

一次准则函数及其算法（如感知器算法）只适用于线性可分的情况，如果是线性不可分的，分类过程将不收敛?

能否找到一种算法，使之能够测试出模式样本集是否线性可分，并且对线性不可分的情况也能给出“次最优”的解？3.6二次准则函数及其解法问题：能否找到一种

如果训练模式是线性不可分

不等式组是不一致的，不等式组没解。此时，目标最少的训练模式被错分。（一）最小错分模式数目准则

对线性不可分样本集，求一解矢量使得错分的模式数目最少。

对于两类问题，设n+1维增广训练模式已符号规范化。

如果训练模式是线性可分的，则存在权矢量使不等式组成立。如果训练模式是线性不可分不等式组是不一致的，不等式组没解式中是矩阵。

将上面的不等式组写成矩阵方程形式，并引入N

维余量矢量，于是不等式方程组变为式中是矩阵。将上面（二）最小方差准则及W-H算法

针对方程组,构造方差准则函数

对于,此时的,而对于,此时的。如果方程组有唯一解,说明训练模式集是线性可分的,如果方程组无解,极小点值是最小二乘解。一般情况下使极小等价于误分模式数目最少。（二）最小方差准则及W-H算法

⑴伪逆法

求对的梯度并令其为零，有可得(3-6-12)

当(X’X)-1存在时，

X+=(X’X)-1X’称为X的伪逆(也称广义逆或M-P逆)， 称为的伪逆解。

X’X是(n+1)×(n+1)矩阵，一般是非奇异的。 当(X’X)-1不存在时，可用广义逆法解 这里(X’X)+为X’X的广义逆矩阵。求解最佳权矢量的方法：⑴伪逆法求解最佳权矢量的方法：⑵梯度法由前述知，的梯度为梯度下降算法迭代公式为Step1.任取Step2.(3-6-13)可以证明，当为任意正的常数，

则该算法使权矢量序列收敛于;满足，也称为MSE解。⑵梯度法由前述知，的梯度为梯度下降算法迭代公式为S

此算法的两个性质:1.当时,MSE解等价于Fisher解。

2.令,在样本数时,MSE解以最小均方误差逼近贝叶斯判决函数Step1.任取Step2.此算法通常称为W－H(Widrow－Hoff)算法仿前采用单样本修正法，则式(3-6-13)可以修改为为了减少计算量和存储量，由于(3-6-14)此算法的两个性质:Step1.任取仿前采用单样本修正法，二次准则函数及其算法小结

二次准则函数及其算法小结3·12势函数分类法

概念：

1：q+；

2

：q-

定义点处的位势函数，它应满足：⑴；⑵是连续光滑函数；⑶是与间距离的单值单调下降函数;当且仅当时，达其最大值;3·12势函数分类法概念：1：q+；2：q-

第一类位势函数设是定义域中的完备正交函数集，位势函数取为第二类位势函数

取关于和的距离的对称函数作位势函数，例如两类位势函数 第一类位势函数两类位势函数位势函数图例位势函数图例⑴令初始积累位势函数;判错计数m

=0;⑵令j=1，输入训练模式，使积累位势函数⑶令j=j+1，输入，计算积累位势函数(4)如果j<N

，返至⑶；如果j=N

，检查是否有模式判错；若m=0，则结束。

若m≠0，则令j=0，m=0,返至⑶。位势函数分类训练算法⑴令初始积累位势函数;判错计数m=0;位判别规则：

判别规则：积累位势函数图例积累位势函数图例⑴设初始积累位势函数,i=1,2,…,c表示类别。⑵当时，迭代规则是⑶在全部训练模式均满足

算法结束。位势函数训练算法用于多类问题⑴设初始积累位势函数,i=1,2,判别规则：判别规则：例：已知如图(3-12-1)所示两类训练样本：

试用势函数法进行分类器训练。

解：选用第二类势函数，令

=1，在二维情况下，为积累位势函数[])](exp[))0()0((exp

),()(,,1222122211111xxxxxxKxKxj+-=-+--==Î=rrrrw例：已知如图(3-12-1)所示两类训练样本：

试判别域代数界面方程法课件判别域代数界面方程法课件令判别界面令判别界面判别界面x2=x1-1x2=1-x1判别界面x2=x1-1x2=1-x180作业3.2以下列两类模式为样本，用感知器算法求其判决函数。（令

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)’,}3.3用W-H算法求解3.2题。3.4已知

1：{(0,0)’},

2：{(1,1)’},

3：{(-1,1)’}。用感知器算法求该三类问题的判别函数，并画出解区域。上机:编写感知器判别程序80作业3.2以下列两类模式为样本，用感知器算法求其判决函第三章类域界面方程法总结

分类

特征空间的分划

子空间的界面：1、判别函数的形式2、判别规则求解参数

第三章类域界面方程法总结分类特征空间的分划子空间的第三章类域界面方程法总结

3·2线性判别函数

式中称为权矢量或系数矢量。写成矢量形式这里，，，称为增广特征矢量和增广权矢量。增广特征矢量的全体称为增广特征空间。

第三章类域界面方程法总结3·2线性判别函数判别规则：

解多类问题的两分法:

⑴两分法

有不确定区域

⑵两分法

⑶没有不确定区的两分法

令判别规则：解多类问题的两分法:

⑴两分法

3·3判别函数值的鉴别意义、

权空间及解空间

（1）系数矢量是超平面的法矢量；（2）的绝对值正比于到超平面的