判别域代数界面方程法

《判别域代数界面方程法》由会员分享，可在线阅读，更多相关《判别域代数界面方程法（159页珍藏版）》请在金锄头文库上搜索。

1、1,模式识别,主讲： 蔡宣平 教授 电话： 74483（O）,74485（H） E-mail：(民网） caixuanpinggfkd.mtn(军网) 单位: 电子科学与工程学院信息工程系,2,第三章 判别域代数界面方程法,3.1 判别域界面方程分类的概念,3.2 线性判别函数,3.3 判别函数值的鉴别意义、权空间及解空间,3.4 Fisher线性判别,3.5 线性可分条件下判别函数权矢量算法,3.6 一般情况下的判别函数权矢量算法,3.7 广义线性判别函数,3.8 二次判别函数,3.9 位势函数分类法,3,3.1 用判别域界面方程分类的概念,2.判别函数 表示界面的函数 称为判别函数(Dis

2、criminant Function)。,1. 分类的基本原理 不同模式对应特征点在不同的区域中散布。运用已知类别的训练样本进行学习,产生若干个代数界面 ,将特征空间划分成一些互不重叠的子区域。,两类的分类问题，它们的边界线就是一个判别函数,两类问题中线性不可分的实例,三类的分类问题，它们的边界线也是一个判别函数,7,3.线性可分的定义 对于来自两类的一组模式 ,如果能用一个线性判别函数正确分类,则称他们是线性可分的。,3.1 用判别域界面方程分类的概念,第三章 判别域代数界面方程法,4.本章分类方法的基本技术思路 第一步：利用训练样本求出分类器/判别函数 第二步：利用判别函数对未知类别样本分

3、类,8,3.2 线性判别函数,在n维特征空间中,特征矢量 ,线性判别函数的一般形式是:,第三章 判别域代数界面方程法,其中 称为权矢量或系数矢量。,简化为:,和 分别称为增广特征矢量和增广权矢量。,一、两类问题 对于两类问题,待识别模式增广特征矢量 可通过下面的判别规则进行分类识别:设 为判别函数,两分法（第一种情况）,基本思想:将属于 类和不属于 类的模式分划开。 类问题转化为 个两类问题。可建立 个判别函数。,二、多类问题 处理多类问题主要有以下几种方法:,通过训练,其中每个判别函数都具有下面的性质：,多类问题图例（第一种情况）,?,不确定区域,1、第一种情况（续）,判别规则为：,如果,则

4、判,比如对图的三类问题,如果对于任一模式 如果它的 则该模式属于1类。,1、第一种情况（续）,如果某个X使二个以上的判别函数 di0 。则此模式X就无法作出确切的判决。如图,另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确定区域。,1、第一种情况（续）,求：当 时属于哪一类?,例3.2.1：已知三类1,2,3的判别函数分别为：,解： 三个判别边界分别为：,1、第一种情况（续）,将 代入方程组:,结论： 因为 所以它属于2类。,1、第一种情况（续）,两分法（第二种情况）,对 类中的任意两类 和 都分别建立一个判别函数,这个判别函数将属于 的模式与属于 的模式区分

5、开。此函数对其他模式分类不提供信息,因此总共需要 个这样的判别函数。,通过训练得到区分两类 和 的判别函数为:,它具有性质：,判别规则是:,如果：,此类方法同样存在不确定区。,则判,2、第二种情况（续）,多类问题图例（第二种情况）,例：设有一个二维三类问题，三个判别函数为：,上面三式等效为：,求模式 属于哪一类?,d12(x) = - d21(x) = x1 x2 + 5 = 0,d12(x)为正,两分法例题图示,d21(x)为正,d23(x)= -d32(x)= x1+x2= 0,d32(x)为正,d23(x)为正,d13(x)= -d31(x)= x1+3 = 0,d31(x)为正,d13

6、(x)为正,3类判别区域 d31(x)0 d32(x)0,3.没有不确定区的 两分法（第三种情况）,令方法2中的判别函数为：,则 等价于 ,于是对每一类 均建立一个判别函数 , 类问题有 个判别函数,故判决规则成为： 如果 则判,判决规则的另一种表达形式 如果 则判,3、第三种情况（续）,多类问题图例（第三种情况）,例：设有一个二维三类问题，三个判别函数为：,。,求模式 属于哪一类?,所以,上述三种方法小结:,方法判别函数的数目和方法相同，但没有不确定区，分析简单，是最常用的一种方法。,28,3.3.1.判别函数值的大小、正负的数学意义,3.3 判别函数值的鉴别意义、权空间及解空间,第三章 判

7、别域代数界面方程法,维特征空间 中,两类问题的线性判别界面方程为：,29,此方程表示一超平面 。它有以下三个性质: (1)系数矢量 ，是该平面的法矢量。 (2)判别函数 的绝对值正比于 到超平面 的距离。 (3)判别函数值的正负表示出特征点位于哪个半空间中。,3.3 判别函数值的鉴别意义、权空间及解空间,第三章 判别域代数界面方程法,图3.3.1 点面距离及界面的正负侧示意图,证明：系数矢量 , 是该平面的法 矢量,即 平面 。,设点 、 在判别界面中，故它们满足方程，于是有,上面二式相减，可得：,这就表明：,而差矢量 在判别界面中，由于 、 是 中的任意两点，故 平面 。,证明：判别函数 的

8、绝对值正比于 到超平面 的距离。,平面 的方程可以写成：,设 是平面 中的任一点， 是特征空间 中任一点，点 到平面 的距离为差矢量 在 上的投影的绝对值，即,上式表明， 的值 正比于 到超平面 的距离 。,证明：判别函数值的正负表示出特征点位于哪个半空间中。,两矢量 和 的数积为：,这说明判别函数值的正负表示出特征点位于哪个半空间中，或者换句话说，表示特征点位于界面的哪一侧。,例3.3.1：利用判别函数的鉴别意义，试分析d(x1,x2)x1+x2+1。,37,(1) 权空间,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,增广特征矢量与增广权矢量是对称的，判别

9、函数可以写成,这里 则应视为相应的 的“权”,38,(2) 解矢量,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,对于两类问题，在对待分类模式进行分类之前，应根据已知类别的增广训练模式 确定线性判别函数,当训练模式 时有,当训练模式 时有,这时的 称为解矢量，记为,39,(2) 解矢量,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,当训练模式 时有,当训练模式 时有,为方便求 ，常需要将已知类别的训练模式符号规范化：当 属于 类时，不改变其符号；当属于 类时，改变其符号。,40,3.3.2权空间、解矢量与解空间,3.3 判别函

10、数值的鉴别意义、权空间及解空间,对于一个训练模式 ，界面 过增广权空间原点且将其分成两个子空间，界面 的法矢量 指向正半子空间，所谓正半子空间是指该子空间中任一点 都使 。显然，解矢量 必在正半子空间中。,41,(3) 解空间,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,先看一个简单的情况。设一维数据1，2属于w1, -1，-2属于w2 求将w1和w2区分开的w0 ，w1。,42,(3) 解空间,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,先看一个简单的情况。设一维数据1，2属于w1, -1，-2属于w2 求将w1和w2区

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

12、维数据1，2属于w1, -1，-2属于w2 求将w1和w2区分开的w0 ，w1。,w0,w1,46,(3) 解空间,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,先看一个简单的情况。设一维数据1，2属于w1, -1，-2属于w2 求将w1和w2区分开的w0 ，w1。,w0,w1,47,(3) 解空间,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,个训练模式将确定 个界面，每个界面都把权空间分为两个半空间， 个正的半子空间的交空间是以权空间原点为顶点的凸多面锥。,满足上面各不等式的 必在该锥体中，即锥中每一点都是上面不等式组的解

13、，解矢量不是唯一的，上述的凸多面锥包含了解的全体，称其为解区、解空间或解锥。,48,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,每一个训练模式都对解区提供一个约束，训练模式越多，解区的限制就越多，解区就越小，就越靠近解区的中心，解矢量 就越可靠，由它构造的判别函数错分的可能性就越小。,49,(4) 余量,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,为使解矢量可靠,使解区更小,可以采取增加训练模式数以及引入余量 ,使 ,从而达到更好的效果。,即由 所确定的凸多面锥在 所确定的多面锥的内部，并且它的边界离开原解区边界的距离为

14、。,50,(4) 余量,3.3.2权空间、解矢量与解空间,3.3 判别函数值的鉴别意义、权空间及解空间,引入了余量可有效地避免量测的误差、引入的误差以及某些算法求得的解矢量收敛于解区的边界上，从而提高了解的可靠性。,51,思想：多维 Fisher变换 利于分类的一维,方法：求权矢量 求满足上述目标的投影轴 的方向 和在一维空间中确定判别规则。,3.4 Fisher线性判别,第三章 判别域代数界面方程法,二维模式向一维空间投影示意图,二维模式向一维空间投影示意图,二维模式向一维空间投影示意图,o,x,y,o,x,y,用 表示待求的 。,设给定n维训练模式 ，其中有N1和N2=N-N1 个模式分属w1类和w2类，分别记为 和 ，各类模式均值矢量为,（1)求解Fish准则函数,各类类内离差阵SWi和总的类内离差阵SW分别为：,取类间离差阵为：,类内离差度 和总的类内离差度 为：,类间离差度为：,希望经投影后，类内离差度 越小越好，类间离差度 越大越好，根据这个目标作准则函数,并使其最大,上式称为Fisher准则函数。,利用二次型关于矢量求导的公式可得：,（2) 求解Fisher最佳鉴别矢量,令,可得：,当N较大时，SW通常是非奇异的,于是有：,上式表明， 是矩阵 相应于特征值l的特