模式识别1-2判别函数

1、信息工程学院* 2-1、判别函数 2-2、线性判别函数 2-3、线性判别函数的性质 2-4、广义线性判别函数 2-5、非线性判别函数第二章 判别函数信息工程学院*v假设对一模式X已抽取n个特征，表示为：v模式识别问题就是根据模式X X的n n个特征来判别模式属于1 ,2 , , m 类中的那一类。 2-1 判别函数 维空间的一个向量是n),.,(321XxxxxXTn信息工程学院*v例如下图：三类的分类问题，它们的边界线就是一个判别函数123边界2x1x2.1 判别函数（续）信息工程学院*v判别函数包含两类：v一类 是线性判别函数：线性判别函数广义线性判别函数 （所谓广义线性判别函数就是把非线

2、性判别函数映射到另外一个空间变成线性判别函数）分段线性判别函数v另一类是非线性判别函数2.1 判别函数（续）信息工程学院* 2-2 线性判别函数v我们现在对两类问题和多类问题分别进行讨论。v(一)两类问题 即: v v1. 二维情况 ：取两个特征向量v 这种情况下 判别函数:2,),(21MTi2,)(2,1nxxXT32211wxwxw)x(g为坐标向量为参数，21, xxw信息工程学院*v在两类别情况，判别函数 g (x) 具有以下性质：v这是二维情况下判别由判别边界分类.v情况如图：1. 二维情况21, 0, 0)(XXxgi不定Xxg,0)(32211)(wxwxwxg211x2x信息

3、工程学院*2. n维情况v现抽取n个特征为：v判别函数： v另外一种表示方法：TnxxxxX),.,(32112211.)(nnnwxwxwxwxg10nwXW为增值模式向量。，为增值权向量，TnnTnnxxxxXwwwwW) 1,.,(),.,(21121XWxgT)(为模式向量。为权向量，TnTnxxxXwwwW),.,(),.,(21210信息工程学院*v模式分类：v当 g1(x) =WTX=0 为判别边界 。当n=2时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面，n3时，则判别边界为一超平面。21,0,0)(xxXWxgT2. n维情况信息工程学院*(二) 多类问题。其它

4、MiXXWxgiTii,.,2 , 1, 0, 0)(v对于多类问题，模式有 1 ,2 , , m 个类别。可分三种情况：1。第一种情况：每一模式类与其它模式类间可用单第一种情况：每一模式类与其它模式类间可用单个判别平面把一个类分开。个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：权向量。个判别函数的为第式中iwwwwWTininiii) ,.,(121信息工程学院*v右图所示，每一类别可用单个判别边界与其它类别相分开 。v如果一模式X属于1，则由图可清楚看出:这时g1(x) 0而g2(x) 0 ， g3(x) 0 ， g2(x) 0 ， g3(x) 0 。则此模式X就

5、无法作出确切的判决。如图中 IR1,IR3，IR4区域。v另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确 定区域。1 1。第一种情况（续）第一种情况（续）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551信息工程学院*v问当x=(x1,x2)T=(6,5)T时属于那一类v结论： g1(x) 0 ， g3(x) g2(x) 和 g1(x) g3(x) 。v假设判别函数为：v则判别边界为：23212211)(1)()(xxg

6、xxxgxxxg012)()(02)()(012)()(21322131121xxxgxgxxxgxgxxgxg2)()(21xgxg)()(32xgxg)()(31xgxg133。第三种情况（续）信息工程学院*v结论：不确定区间没有了，所以这种是最好情况。v用上列方程组作图如下：3。第三种情况（续）1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0信息工程学院*v问假设未知模式x= (x1,x2)T= (1,1)T ，则x属于那一类。

7、v把它代入判别函数：v得判别函数为：v因为v所以模式x= (1,1)T属于 类。3。第三种情况（续）2)()(),()(1232xgxgxgxg1)(, 1)(, 0)(321xgxgxg).(),(),(321xgxgxg1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05 . 0信息工程学院*2-3、线性判别函数的性质v1、模式空间与加权空间v模式空间：由 构成的n维欧氏空间。vW是此空间的加权向量，它决定模式的分界面H，W与H正交。v加

8、权空间：以 为变量构成的欧氏空间v模式空间与加权空间的几何表示如下图：XWxgTi)(TnxxxxX),.,(321121,.,nwww模式空间 2X1X121x3x4x0)(xg边界2xHW信息工程学院*模式空间信息工程学院*加权空间判别界面信息工程学院*1、模式空间与加权空间（续）信息工程学院*v该式表示一个通过加权空间原点的平面，此平面就是加权空间图中的平面,同样令g (x2) =g (x3) =g (x4)=0，分别作出通过加权空间原点的平面图中用阴影表示的部分是各平面的正侧。v加权空间的构造：v设 是加权空间分界面上的一点，代入上式得：这是加权空间的边界, 0)(31221111wx

9、wxwxg1、模式空间与加权空间Txxx),(1211123422411332231100wxwxwwxwxw13222211312211100wxwxwwxwxw243121,xxxx设：最终形成图多面锥210)(xxxg32211)(wxwxwxg信息工程学院*v这是一个不等式方程组，它的解 处于由1类所有模式决定的平面的正边和由2类所有模式决定的平面的负边，它的解区即为凸多面锥。v如图所示：(b)为加权空间，（c）为正规化后的加权空间。v由上可以得到结论：加权空间的所有分界面都通过坐标原点。这是加权空间的性质。v为了更清楚，下面用二维权空间来表示解向量和解区。1、模式空间与加权空间（续）

10、TwwwW),(321信息工程学院*v在三维空间里，令w3 = 0 则为二维权空间。如图：v给定一个模式X，就决定一条直线：v即分界面H，W与H正交，W称为解向量。v解向量的变动范围称为解区。v因x1,x21， x3,x42由图可见x1,x3离的最近，所以分界面H可以是x1,x3之间的任一直线，由垂直于这些直线的W就构成解区，解区为一扇形平面，即阴影区域。v如右图:2、解向量和解区0)(XWxgT1w2w1x4x3x2x解区W解向量分界面H解向量与解区信息工程学院*v把不等式方程正规化：v正规化：00003422411332231132222113122111wxwxwwxwxwwxwxwwx

11、wxw) ,.,(0)(121nnTiwwwwWXWxg2、解向量的解区（续）1w2w1x4x3x2x解区解向量分界面H3x4x正规化信息工程学院*vg(x)=WTX=0决定一个决策界面，当g(x)为线性时，这个决策界面便是一个超平面H，并有以下性质：v性质：W与H正交（如图所示）v假设x1,x2是H上的两个向量v所以 vW 与(x1-x2) 垂直，即W与H正交。v一般说，超平面H把特征空间分成两个半空间。即1,2空间，当x在1空间时g(x)0,W指向1，为H的正侧，反之为H的负侧.上矢量一定在HxxxxWwxWwxWTnTnT)( , 0)(0212112113、超平面的几何性质信息工程学院

12、*1x2X1X2xWH12g(x)0g(x)03、超平面的几何性质信息工程学院*v 矢量到H的正交投影 与 值成正比v其中： x p： x在H 的投影向量，vr是x 到H 的垂直距离。v 是W方向的单位向量。3、超平面的几何性质（续）W)x(grv性质 ：WWrxrxxpp)(xgxrWWq2X1XpxWxHpr信息工程学院*v另一方面:11)()(npTnTwrxWwxWxg1nTpTwrWxW)(,)()()(021WWWrWxgrWrWWWrWWrWrWxgwxWHpTTTTnpT是投影的绝对值上。在因为3、超平面的几何性质（续）v这是超平面的第二个性质，矢量x到超平面的正交投影 正比与

13、g(x)的函数值。r信息工程学院*WWqqrHxxqWWWxgrxwwxWxgnnnnT11110)()0()(的投影为到时因因原点因为成正比的距离与原点到11nnWH,WWqv性质：3、超平面的几何性质（续）q2X1X0H信息工程学院*v性质：通过原点。，说明超平面则若在原点负侧。则在原点正侧，若则若HxWxgWHWHWTnnn)(, 0, 0, 0111否则，反之。的正侧，在代数距离。到正比于来决定。的位置由超平面决定正交，方向由的平面与）超平面（结论：, 0)()()()(1xgHxHxxgcWHbWWHan3、超平面的几何性质（续）信息工程学院*v一组模式样本不一定是线性可分的，所以需

14、要研究线性分类能力的方法，对任何容量为N的样本集，线性可分的概率多大呢？v（如下图（a），线性不可分）v例：4个样本有几种分法。v图（b）直线把x1分开，每条直线可把4个样本分成1 2 类，4个样本分成二类的总的可能的分法为24=16类，其中有二种是不能用线性分类实现的线性可分的是14。即概率为14/16。4。二分法能力（a）x1x2x3x4 （b）信息工程学院*v结论：N个样品线性可分数目(条件：样本分布良好）：4。二分法能力（续）为特征数为样本数其中nNkNkNCkN,)!1( !)!1(1nkkNNnNCnNnND011,21,2),(若若v对N和n各种组合的D(N,n)值，表示在下表中

15、，从表中可看出，当N，n缓慢增加时D(N,n)却增加很快。信息工程学院*12345612222222444444368888848141616161651022303232324。二分法能力（续）n),(nNDNnkkNNNnNCnNnNDnNP0111,21, 12),(),(若若v线性可分概率：信息工程学院*),(nNP0 .15 .00543211n5n15nn1nN强。说明样本少时二分能力范围，即在。时，线性可分概率为时，即值，对于任意。处出现明显的门限效应时，曲线急剧下降，在由当, 1),(),1(22: )(21),() 1(22: )(21: )(nNPnNcnNPnNnbnav

16、把上式用曲线表示成下图：图中横坐标用=N/n+1表示。v由图讨论：4。二分法能力（续）信息工程学院*.2),1(2: )(,),1(22: )(0是最好情况即二分能力）的估计：个样本的线性可分性（对多线性可分能力越差。说明样品越线性可分概率急剧下降范围，即在nNNenNd),(nNP0 . 15 .00543211n5n15nn1nNv结论：在实际工作中，分类的训练非常重要，由已知样本来训练。因为已知样本有限，而未知样本无限。选择已知类别的训练样本数方法如下：4。二分法能力（续）信息工程学院*v：如果训练样本N N0，设计分类器的分类能力太差，因为训练样本太少。v：如果训练样本N太多时，则样本

17、太多，运算量、存储量太大。v：因此实际工作中应该取：n)1)(2010(),2010(nN训练样品4。二分法能力（续）信息工程学院*2-4、广义线性判别函数kixfwwxfwxfwxfwxgkiiikkk,.,2 , 1, )()(.)()()(1112211v这样一个非线性判别函数通过映射，变换成线性判别函数。1)(,)(1xfxfki是单值函数式中v判别函数的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空间变换空间信息工程学院*0YWT判别平面：)( ,)(.)()()( ,., 0, 0)()()(21212111增广模式向量。广义权向量其中：空间变换空间x

18、fxfxfYwwwWxxYgYWxfwxgkkTyxkiii2-4、广义线性判别函数（续）21,xaxbxbxorax则则v例：如右图。0bax二次判别函数212信息工程学院*2321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：2-4、广义线性判别函数（续）v要用二次判别函数才可把二类分开：)1 , 1, 1()25.0 ,5 .0 , 1(),0 ,0 , 1(321yyy05 .011y3y2yW平面oYWT212x信息工程学院*015 . 012)(1,2112, 1, 12123212321321YWYxxxxxgyyyxxYa

19、aaWaaaxT空间判别平面：即：空间它的判别边界：设讨论在推出2-4、广义线性判别函数（续）v从图可以看出：在阴影上面是1类，在阴影下面是2类，v结论：在X空间的非线性判别函数通过变换到Y空间成为线性的，但X变为高维空间05.011y3y2yW平面oYWT212x信息工程学院*v1.分段线性判别函数分段线性判别函数（用线性无法分开,可用分段线性判别函数） 、基于距离的分段线性判别函数基于距离的分段线性判别函数。（用均值代表一类，通过均值连线中点的垂直线分开） 把i类可以分成li个子类: 分成l个子类。现在定义子类判别函数：在同类的子类中找最近的均值。判别规则：这是在M类中找最近均值。则把x归

20、于j类完成分类。),.,(21liiii2-5、非线性判别函数 2 :线性判别 ：分段线性判别 ：二次判别 11lillixxg,.,2,1min)(Mixgxgij,.,2 , 1),(min)(信息工程学院*2-5、非线性判别函数（续）v例：未知x,如图：v先与1类各子类的均值比较，即 ，找一个最近的 与2各子类均值比较取最近的 因g2(x) g1(x) ，所以x2类 。 211)( xxglx1322)( xxg22123221111112322221x信息工程学院*v设 1, 2 ,mv而每一类又可以分为 子类。v对每个子类定义一个线性判别函数为：v则定义i类的线性判别函数为：、基于函

21、数的分段线性判别函数 利用均值代表一类有时有局限性，如图所示。若用 线性判别函数代表一类，就会克服上述情况。121x2xx1、分段线性判别函数),.,(21liiii子类的权向量。为其中lilililiwxwxg,)()(max)(,.,2, 1xgxglilli信息工程学院*v在各子类中找最大的判别函数作为此类的代表，则对于M类，可定义M个判别函数gi(x),i=1,2,.M,因此，决策规则：v对未知模式x，把x先代入每类的各子类的判别函数中，找出一个最大的子类判别函数，M类有M个最大子类判别函数，在M个子类最大判别函数中，再找一个最大的，则x就属于最大的子类判别函数所属的那一类。jiMij

22、xxgxg则),(max)(,.,2, 11、分段线性判别函数（续）信息工程学院*、基于凹函数的并分段线性判别函数（针对多峰情况） 设li子类判别函数，i=1,2,.r则分段线性判别函数有如下特性：1、分段线性判别函数（续）v(a)：l1,l2,lr都是分段线性判别函数v(b)：若A,B都是分段线性判别函数，则： AB ，AB也是分段线性判别函数。 AB取最小 ，AB取最大。v(c)：对任何分段线性函数都可以表示成如下二种形式：v1)、析取范式(这是经常采用的形式)P=(L11L12L1m)(Lq1Lq2Lqm)v2)、合取范式Q= (L11 L12 L1m) (Lq1 Lq2 Lqm)v每个(L11 L12 L1m) 都称为凹函数。信息工程学院*。每个子类的判别函数数子类。mjxqixxwLijij,.,2 , 1, 0,.,2 , 1, 0211、分段线性判别函数（续）v对于多峰二类问题：设第一类有q个峰，则有q个凹函数。v即P=P1P2Pqv每个凹函数Pi由m 个线性判别函数来构成。vPi=Li1Li2Limv假设对于每个子类线性判别函数Lij都设计成：21, 0, 0 xPxP则则判别规则：信息工程学院*v例、设