模式识别导论本三PPT课件

1、例如下图：三类的分类问题，它们的边界线就是一个判别函数。如果该函数为线性函数，则线性可分123边界2x1x第1页/共42页判别函数包含两类：一类 是线性判别函数：线性判别函数广义线性判别函数（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）分段线性判别函数另一类是非线性判别函数第2页/共42页我们现在对两类问题和多类问题分别进行讨论。(一)两类问题 即: 1. 二维情况 ：取两个特征向量 这种情况下 判别函数:2,),(21MTi2,)(2,1nxxXT32211)(wxwxwxg为坐标向量为参数，21, xxw第3页/共42页在两类别情况，判别函数 g (x) 具

2、有以下性质：这是二维情况下判别由判别边界分类.情况如图：1. 二维情况21, 0, 0)(XXxgi不定Xxg,0)(32211)(wxwxwxg211x2x第4页/共42页2. n2. n维情况维情况现抽取n个特征为：判别函数： 另外一种表示方法：TnxxxxX),.,(32112211.)(nnnwxwxwxwxg10nTwXW为增值模式向量。，为增值权向量，TnnTnnxxxxXwwwwW) 1,.,(),.,(21121XWxgT)(为模式向量。为权向量，TnTnxxxXwwwW),.,(),.,(21210第5页/共42页模式分类：当 g1(x) =WTX=0 为判别边界 。当n=2

3、时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面，n3时，则判别边界为一超平面。21,0,0)(xxXWxgT2. n维情况第6页/共42页( (二二) ) 多类问题多类问题iiTiiXXXWxg, 0, 0)(对于多类问题，模式有 1 ,2 , , m 个类别。可分三种情况：1。第一种情况：每一模式类与其它模式类间可用单个判别平面把一个类分开(绝对可分)。这种情况，M类问题转化为M1个两类问题需建立M1个判别函数，且每个具有以下性质：权向量。个判别函数的为第式中iwwwwWTininiii) ,.,(121第7页/共42页判别界面 将特征空间分划成两个子空间，其中一个包含 ，另一

4、个不包含 ，同样， 也将特征空间分成两个子空间，其中一个包含 另一个不包含。由这两个界面分划的分别包含i和j类的子区域可能有部分重叠，落在重叠区的点不能由这两个判别函数决定使用这类判别函数，可能会出现两个或两个以上的判别式都大于零或者所有判别式都小于零的情况。出现在这些区域中的点，不能有判别式判别属于哪一类。gi(x)0只说明x是在包含i类的半空间中，而这个半空间可能还有其他类别存在i)(xgii)(jxgj第8页/共42页如图所示，每一类别可用单个判别边界与其它类别相分开 。如果一模式X属于1，则由图可清楚看出:这时g1(x) 0而g2(x) 0 ， g3(x) 0 。 1 类与其它类之间的

5、边界由 g1(x)=0确定. 21x 0)(2xg0)(3xg2x0)(1xg13判别规则：判别规则：如果如果则则 ijxgxgji, 0)(0)(ix第9页/共42页1)(5)()(23212211xxgxxxgxxxg例：已知三类例：已知三类1 1,2 2,3 3的判别函数分别为：的判别函数分别为：因此三个判别边界为：01)(05)(0)(23212211xxgxxxgxxxg第10页/共42页v作图如下：30)(0)(0)(321xgxgxg120)(0)(0)(321xgxgxg0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg5

6、51第11页/共42页问当x=(x1,x2)T=(6,5)T时属于那一类结论： g1(x) 0 ， g3(x) 0所以它属于2类:代入判别函数方程组1)(5)()(23212211xxgxxxgxxxg.4)(,6)(, 1)(321xgxgxg得：第12页/共42页这样 有 M(M _ 1)/2个判别平面。对于两类问题，M=2，则有一个判别平面。同理，三类问题则有三个判别平面。判别函数： 判别边界：性质：第二种情况：XWxgTijij)(0)(xgij任意两类间可分别用判别平面分开（成对可分）。20)(12xg0)(23xg0)(13xg 3 10,( )0,iTijijjxgxw xx若若

7、第13页/共42页但是判别函数的正负不能做出x属于i类还是j类，只能做出x是位于含有i类的半空间中还是位于j类的半空间中，因在某个半空间中可能还有其他类别的存在。因此这种方法的决策规则是iijxijxg那么如果, 0)(第14页/共42页0)(03)(05)(21231132112xxxgxxgxxxg21231132112)(3)(5)(xxxgxxgxxxg假设判别函数为：判别边界为：用方程式作图：0,023212gg判别区012)x(g 023)x(g013)x(g 5531x0032313gg判别区0031121gg判别区2x第15页/共42页问问: :未知模式未知模式X=(X=(x

8、x1 1, ,x x2 2) )T T=(4,3)=(4,3)T T属于那一属于那一类类代入判别函数可得:把下标对换可得:因为结论：所以X 属于3类结论：判别区间增大，不确定 区间减小，比第一种情况小的多.1)(, 1)(,2)(231312xgxgxg1)(, 1)(, 2)(323121xgxgxg0)(3xgj0023122gg判别区0031121gg判别区0)(12xg 0)(23xg0)(13xg 5530032313gg判别区1x2x第16页/共42页广义线性判别函数广义线性判别函数kixfwwxfwxfwxfwxgkiiikkk,.,2 , 1, )()(.)()()(11122

9、11这样一个非线性判别函数通过映射，变换成线性判别函数。1)(,)(1xfxfki是单值函数式中判别函数的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空间变换空间第17页/共42页0YWT判别平面：)( ,)(.)()()( ,., 0, 0)()()(21212111增广模式向量。广义权向量其中：空间变换空间xfxfxfYwwwWxxYgYWxfwxgkkTyxkiii21,则,则xa orxbxbxax例：如右图。0bax二次判别函数212第18页/共42页2321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT

10、映射：要用二次判别函数才可把二类分开：)1 , 1, 1()25.0 ,5 .0 , 1(),0 ,0 , 1(321yyy05 .011y3y2yW平面oYWT212x第19页/共42页015 . 012)(1,2112, 1, 12123212321321YWYxxxxxgyyyxxYaaaWaaaxT空间判别平面：即：空间它的判别边界：设讨论在推出从图可以看出：在阴影上面是1类，在阴影下面是2类，结论：在X空间的非线性判别函数通过变换到Y空间成为线性的，但X变为高维空间05.011y3y2yW平面oYWT212x第20页/共42页一组模式样本不一定是线性可分的，所以需要研究线性分类能力的

11、方法，对任何容量为N的样本集，线性可分的概率多大呢？（如下图（a），线性不可分）例：4个样本有几种分法。图（b）直线把x1分开，每条直线可把4个样本分成1 2 类，4个样本分成二类的总的可能的分法为24=16类，其中有二种是不能用线性分类实现的线性可分的是14。即概率为14/16。二分法能力（a）x1x2x3x4 （b）第21页/共42页结论：N个样品线性可分数目(条件：样本分布良好）：为特征数为样本数其中nNkNkNCkN,)!1( !)!1(1nkkNNnNCnNnND011,21,2),(若若对N和n各种组合的D(N,n)值，表示在下表中，从表中可看出，当N，n缓慢增加时D(N,n)却增

12、加很快。第22页/共42页1234561222222244444436888884814161616165102230323232二分法能力（续）n),(nNDNnkkNNNnNCnNnNDnNP0111,21, 12),(),(若若线性可分概率：第23页/共42页),(nNP0 . 15 . 00543211n5n15nn1nN强。说明样本少时二分能力范围，即在。时，线性可分概率为时，即值，对于任意。处出现明显的门限效应时，曲线急剧下降，在由当, 1),(),1(22: )(21),() 1(22: )(21: )(nNPnNcnNPnNnbna把上式用曲线表示成下图：图中横坐标用=N/n+

13、1表示。由图讨论：第24页/共42页( ): 在2范围，即2 (1),线性可分概率急剧下降,说明样品越多线性可分能力越差。dNn),(nNP0 . 15 .00543211n5n15nn1nN结论：在实际工作中，分类的训练非常重要，由已知样本来训练。因为已知样本有限，而未知样本无限。选择已知类别的训练样本数方法如下：第25页/共42页：如果训练样本N 0 所以不修正 w1Tx2=(1,1,1,1) (0,1,1,1)T=30 所以不修正 w1Tx3=(1,1,1,1) (1,1,0,1)T=30 所以修正w1 w2=w1-x3=(0,0,1,0) w2Tx4=(0,0,1,0)T (0,1,0

14、,1) =0 所以修正w2 w3=w2-x4=(0,-1,1,-1)第一次迭代后,权向量w3=(0,-1,1,-1),再进行第2,3,次迭代如下表第31页/共42页训练样本修正式修正后的权值wk1迭代次数x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+0w1w1w1-x3w2-x41 1 1 11 1 1 10 0 1 00 1 1 -1 1x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 10+0-w3+x1w4w4-x3w51 1 2 01 1 2 00 2 2 10 2 2 -1 2x1 1 0 1 1x2 0 1 1 1x3

15、 1 1 0 1x4 0 1 0 1+-w5w5+x2w6w60 2 2 10 1 3 00 1 3 00 1 3 0 3x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w6w6w6w60 1 3 00 1 3 00 1 3 00 1 3 0 4 ktxkw 直到在一个迭代过程中权向量相同，训练结束。w6=w=(0,1,3,0) 判别函数g(x)= -x2+3x3感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.第32页/共42页最小平方误差准则(MSE法）前述迭代求解权向量的方法是在模式集线性可分的情况下采用的。但

16、给出一个模式集往往不能预先告知是否线性可分，LMSE算法就是针对这一问题对准则函数引进最小平方误差而建立起来的，它可以在训练过程中判定训练模式集（样本集）是否线性可分，因而可以判断权向量求解的收敛性。2100 xxwxxwtt对于两类问题: 第33页/共42页如果将属于2第二式也可写成与第一式一样的形式，权向量的求解问题就成为不等式xw0的求解问题，其中每一模式样本都写成增广向量。的模式乘以（-1），则tntittxxxxx2121w=(w1,w2,wn,wn+1)t第34页/共42页若把xw0,改写为xw=b 其中b=(b1,b2,bn)t，其所有分量都为正值。这与不等式xw0是同一意义，求

17、解不等式等价于求解方程XW=b。对于W的估计量 定义误差向量：e=XW-b0 把平方误差作为目标函数第35页/共42页 W的优化就是使J(W)最小。求J(W)的梯度并为0。解上方程得 XTXW=XTb这样把求解XW=b的问题，转化为对XTXW=XTb求解，这一有名的方程最大好处是因XTX是方阵且通常是非奇异的，所以可以得到W的唯一解。 |21|)(22bXWeWJMSE准则函数 0)(2J(W)bXWXT详细推导第36页/共42页bXbXXXTWT*1的伪逆（规范矩阵）称为其中XXXXTXT1*（MSE 解）所以求解W有赖于b的确定。若对b迭代求解，则 kbkbkb1由于b的所有分量必须为正，

18、故可以这样定义 0200kbkxwkbkxwckbkxwkb当第37页/共42页上式中C 为某一校正系数。该式也可以写为 kbkxwkbkxwckb引入误差矢量e(k),即 xw(k)-b(k)=e(k) kekeckb kekecxkwkbxkbxkbkbxkbxkw11第38页/共42页于是，当给定初值 w(1)=x*b(1) 和 b(1)0以及校正系数C ，便可根据上面三个式子进行迭代运算每一次迭代时计算出来的误差矢量e(k)是研究样本集线可分性的重要指标。 只有在e(k)0（即其每一分量均为正值或零）时xwb，系统才是线性可分的。如e(k)0，则不能收敛。教材中例子2第39页/共42页势函数法势函数法 势函数分类器,用非线性判别函数区分线性不可分的类别 势函数分类器:每个特征作为一个点电荷,把特征空间作为能量场. 电位分布函数有下面三种形式。 为系数 xk为某一特定点上图是这些函数在一维时的图形，第三条是振荡曲线，只有第一周期才是可用范围。|11 )K( 2.2kkxxXX|sin|)K( 3.22kkkx