第四章非线性判别函数精选PPT.ppt

《第四章非线性判别函数精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章非线性判别函数精选PPT.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章非线性判别函数第1页，此课件共70页哦4.7.1 分段线性判别函数的基本概念 n分段线性判别函数是一种特殊的非线性判别函数。它确定的决策面是由若干超平面段组成的。n由于它的基本组成仍然是超平面，因此，与一般超曲面(例如贝叶斯决策面)相比，仍然是简单的；又由于它是由多段超平面组成的，所以它能逼近各种形状的超曲面，具有很强的适应能力。第2页，此课件共70页哦n图4.7.1中分别给出了采用线性判别函数，分段线性判别函数和二次判别函数所得到的分界面。112：线性判别：分段线性判别：二次判别图 4.7.1第3页，此课件共70页哦n当类条件概率密度函数为正态分布，各特征统计独立且同方差时，贝叶斯决策

2、规则可得到线性判别函数，特别是当P(1)=P(2)时，决策规则可以写成n这时的决策面是两类期望连线的垂直平分面，如图4.7.2所示。这样的分类器叫做最小距离分类。第4页，此课件共70页哦12x1x2xg(x)=00图 4.7.2这一判别函数虽然是在十分特殊的条件下推出来的，但它却给了我们一个相当重要的启示，这就是可以把均值作为各类的代表点，用距离作为判别函数进行分类。第5页，此课件共70页哦1112212232：线性距离判别m1m2n现在考虑图4.7.3所示的两类分布情况。n1类和2类都是多峰分布。n如果利用上面方法，把各类均值仍作为代表点，设计最小距离分类器，则得到分界面。n缺点是错误率较大

3、。第6页，此课件共70页哦：分段线性距离判别图 4.7.31112212232如果每类不是只取一个代表点，而是取多个代表点，例如，1类取两个代表点，2类取三个代表点，仍利用上面定义的距离判别函数，它是由多段超平面组成的，其中每一段都是最小距离分类器。这样的结果是令人满意的。把未知样本x归到离它最近的代表点所属的类别，则可得到如图中折线(即分界面所示的分段线性分界面，第7页，此课件共70页哦一般地，如果对于i类取li个代表点，或者说，把属于i类的样本区域Ri分为li个子区域，即 ，n其中 表示第i类的第l个子区域，用 表示该子区域中样本的均值向量，并以此作为该子区域的代表点，这样可以定义如下判别

4、函数n 这样的分类器叫做分段线性距离分类器。n 若有则把x归到j类。第8页，此课件共70页哦4.7.2 分段线性判别函数分段线性判别函数 n把上述基于距离的分段线性判别函数概念加以推广。n在前面，把每一类都分为若干子区域，并选择各子区域的均值向量作为代表点以设计最小距离分类器。n但这种方法只在某些特殊情况下才能得到较好的分类结果，在很多情况下往往不适用。第9页，此课件共70页哦例如图4.4所示的样本分布情况。n图中各类样本服从正态但非等协方差分布，其等概率密度面为超椭球面，用虚线表示。n利用贝叶斯决策规则对样本x进行分类，应决策x2类；n但若以i作为代表点，按到i的欧氏距离进行分类，则应决策x

5、1类。n这与贝叶斯决策相矛盾。12x1x20 x图 4.7.4第10页，此课件共70页哦n只考虑作为各类或各子区域代表点所提供的信息是很不够的。n如何利用整个样本集所提供的全部信息是需要考虑的问题。n把每一类分为若干个子类，即令n 不是选择各子类的均值作为代表点设计最小距离分类器，而是对于每个子类定义一个线性判别函数第11页，此课件共70页哦n则对于c类问题可定义c个判别函数gi(x)，i=1，2，c，并得到决策规则：l=1，2，li，i=1，2，cn式中 和 分别为子类 的权向量和阈值权。如果定义i的线性判别函数为则决策xj n对于任意样本x，必有某个子类的判别函数值较其它的判别函数值为最大

6、。第12页，此课件共70页哦n得到的决策面也是分段线性的，其决策面方程是由各子类的判别函数确定的，n如果第i类的第n个子类和第j类的第m个子类相邻，则该决策面方程是n 关键问题是如何利用样本集确定子类数目以及如何求各子类的权向量和阈值权。假如具有最大值的判别函数是 ，则把x归到子类所属的类 ，即类 。第13页，此课件共70页哦4.7.3分段线性分类器设计的一般考虑分段线性分类器设计的一般考虑 n分类器设计的基本问题是，在一定判别函数类内利用训练样本集确定分类器的参数，即确定判别函数中的系数。n设计线性分类器，就是确定权向量w和阈值权w0或广义权向量 a。n 而设计分段线性分类器，则是利用样本集

7、确定一组 和 。第14页，此课件共70页哦利用多类线性判别函数算法设计分段线利用多类线性判别函数算法设计分段线性分类器性分类器n若已知样本的子类划分情况，可把子类看作独立的类，然后利用多类线性判别函数算法把各个子类分开，自然也就把各类分开了。n这种方法必须以已知子类划分为前提。n划分子类的一种方法是根据先验知识直观判定，如字符识别中，可把同一字符看作一类，而把其中不同的字体看作它的不同子类。n另一种方法则借助于聚类分析方法来解决。第15页，此课件共70页哦已知子类数目时的分段线性判别函数已知子类数目时的分段线性判别函数 n当已知子类数目，但不知子类划分情况时，可利用下面的错误修正算法设计分段线

8、性分类器，它与多类线性判别函数的固定增量算法很相似，其步骤如下：n步骤1首先给定各子类的初始权向量。假设i类中有li个子类，则任意给定，i=1，2，c后面用 表示第k次迭代时，第i类第l个子类的权向量。第16页，此课件共70页哦步骤2 利用训练样本集进行迭代，并按下列规则修改权向量：n若在第k次迭代时，j类(j=1,2，c)中的样本yi与j类的某个权向量 的内积值为最大，即n而且满足n其中i=1，2，c，ij，l=1，2，li，则说明权向量组,n不影响yi正确分类，因此各权向量保持不变。第17页，此课件共70页哦n则说明yj被错误分类，需要对权向量进行修正。设n如果存在某个或几个子类不满足上述

9、条件，即存在 ，使得 n 则修正算法为第18页，此课件共70页哦n步骤3重复上面的迭代过程，直到算法收敛或达到规定的迭代次数为止。n当样本集对于给定的子类数目能用分段线性判别函数完全正确分类时，算法将在有限步内收敛，否则算法将不收敛，这时可以考虑用递减的k序列令算法收敛，但不可避免地会增大分类错误率。第19页，此课件共70页哦未知子类数目时的分段线性判别函数未知子类数目时的分段线性判别函数 n最一般的情况是每类应分成的子类数目未知。这时，设计分段线性分类器的方法很多，以树状分段线性分类器为例说明。n对于图4.7.5所示的两类情况，可先用两类线性判别函数算法找一个权向量。它所对应的超平面H1把整

10、个样本集分成两部分，称之为样本子集。第20页，此课件共70页哦1122图 4.7.5H1H4H2H3n 该分类器是分段线性的。“”表示权向量 ai 的方向，它指向超平面Hi的正侧。第21页，此课件共70页哦n它的识别过程是一个树状结构，如图4.7.6所示。图中用虚线显示了对未知样本y的决策过程，经过三步，判断y1。11212图 4.7.6YYYYNNNNaT1y0aT2y0aT3y0aT4y0第22页，此课件共70页哦n 通常可以选择分属两类的欧氏距离最小的一对样本，取其垂直平分面的法向量 ai 作为初始值，然后求得局部最优解ai*作为第一段超平面的法向量。n 这种方法对初始权向量的选择很敏感

11、，其结果随初始权向量ai 的不同而大不相同。在每个节点上所用的寻找权向量的方法不同，结果也将各异。n 对包含两类样本的各子类的划分也可以采用同样的方法。第23页，此课件共70页哦4.7.4 用凹函数的并表示分段线性判别函数 n分段线性判别函数的表示分段线性判别函数的表示 n设Li是线性函数，i=1，2，r，则分段线性函数可以递归地定义如下：nL1，L2，Lr都是分段线性函数。n如果A和B都是分段线性函数，则AB和AB也是分段线性函数。这里符号“”表示求小，符号“”表示求大。n分段线性函数只能由和的形式给出。第24页，此课件共70页哦任何分段线性函数都可以表示为如下两种一般形式：n分段线性函数的

12、析取范式nP=(L11L12L1,m1)(Lq1Lq2Lq,mq)n分段线性函数的合取范式nQ=(L11L12L1,m1)(Lq1Lq2Lq,mq)n用析取范式P表示一个分段线性函数，其中每个(L11L12Li,mi)称为一个凹函数，P是q个凹函数的并，即在q个凹函数中求最大凹函数。第25页，此课件共70页哦n对于多峰分布的两类问题，可以用分段线性判别函数P把其分开，P中的每个凹函数粗略地规定了某个类的一个峰，假设第一类呈现q个峰的分布，则P由q个凹函数Pi的并构成，记为 P=(P1P2Pq)n其中每个凹函数Pi又是mi个线性判别函数Lij的交构成的，记为Pi=(Li1Li2Li,mi)第26

13、页，此课件共70页哦假定对于每个线性判别函数Lij，都使i=1，2，qj=1，2，min则r个权向量 ，就能对样本集正确分类，这里 n分段线性判别函数P是样本集X和权向量 ，的函数，记为P(X;a1，a2，ar )第27页，此课件共70页哦n 这样，设计分段线性分类器的问题就转化为求r个权向量a的问题了。而对于任何x2，都有P(x;a1,a2,ar 0，n 如果对于任何x1，都有 P(x;a1,a2,ar)0，若n 则分段线性判别函数P就能对两类样本正确分类，即存在决策规则 第28页，此课件共70页哦例如，对于图4.7所示的分布，q=3，m1=5，m2=4，m3=4。因此分段线性判别函数L11

14、L12L13L14L15L21L22L23L24L31L32L33L34图 4.7第29页，此课件共70页哦P=(L11L12L13L14L15)(L21L22L23L24)(L31L32L33L34)nP=maxmin(L11，L12，L13，L14，L15)min(L21，L22，L23，L24)min(L31，L32，L33，L34)n在这儿，共有r=m1+m2+m3=13个线性判别函数。n对于任意xi1，即x落入第一类的第i个子类中，所有的Lij 0，j=1，2，mi，故Pi 0，因而P 0。第30页，此课件共70页哦而对于任意x2，因为所有的Pi0，i=1，2，3,因而P0。n对于未

15、知的样本x，如果某个Pi 0，则xi1，因而x1。如果Pi0，i=1，2，3，x2。n例4.1设有两个未知样本x1和x2，其分段线性判别函数的值分别为 nx1:L11=8 L12=4 L13=6 L14=10 L15=17L21=9 L22=15 L23=17 L24=3L31=8 L32=7 L33=9 L34=25第31页，此课件共70页哦nx2:L11=26 L12=50 L13=25 L14=80 L15=73L21=18 L22=4 L23=96 L24=14L31=17 L32=6 L33=1 L34=8 P=maxmin(L11，L12，L13，L14，L15)min(L21，L

16、22，L23，L24)min(L31，L32，L33，L34)Px1=maxmin(8,4,6,10,17),min(9,15,17,3),min(8,7,9,25)=max4,3,25=4 0决策x11第32页，此课件共70页哦Px2=maxmin(26,50,25,80,73),min(18,4,9,14),min(17,6,1,8)=max50,9,6=6 IREP?任意选择初始权向量k=0k=0?按(4-19)式选择Ai1(k)和Ai2(k)正确分X1和X2吗？P()停机：输出解向量集停机：将10次迭代中样本错误率最小的分段线性判别函数作为最终结果随 机 选 择Ai1(0)和Ai2(0

17、),i=1,2,rk=k+1k=IRLS?I=I+1YYYYNNNN图 4.8以 为初始权向量以Ai1(k)和Ai2(k)为样本集，求线性判别函数权向量限制迭代次数为INUM第39页，此课件共70页哦这种算法存在的主要问题是：n在算法执行前，要首先判断每类分布有多少个峰，从而决定选择哪一类作设计，并确定设计几个分段线性判别函数才符合要求。这就需要对样本集有一定的先验知识。n如果没有足够的先验知识，实验结果表明，只要选择多于峰数的分段线性判别函数，结果也将是令人满意的。第40页，此课件共70页哦这种算法存在的主要问题是(续)：n在算法执行前，要给出每个分段线性判别函数中分段的数目。n理论上没有证

18、明算法的收敛性。但大量实验结果表明，算法一般都能收敛到较好的结果。多设几次权向量初值，并重新选择Ai1(0)和Ai2(0)。第41页，此课件共70页哦4.7.2用交遇区的样本设计分段线性分类器用交遇区的样本设计分段线性分类器 n算法基本思想算法基本思想 n这是一种实现最少分段线性分类器的方法。n当两类样本非线性可分时，贝叶斯分界面一般通过两类样本十分靠近或相互交迭的区域，称之为交遇区。第42页，此课件共70页哦acb12图 4.10把这些区域找出来，利用这些区域中的样本作为新的样本集设计线性判别函数，然后把它们连在一起，就构成了一个分段线性判别函数，这种方法称为“局部训练法”，所得的分界面是分

19、段线性分界面，它可以很好地逼近贝叶斯分界面。如图4.10所示，其中(a)(c)是交迭区，(b)是靠近区。第43页，此课件共70页哦综上所述，这种方法大体需要解决以下几个问题：n如何从样本集中找出“交遇区”；n如何利用“交遇区”中的样本设计线性分类器；n如何进行分类决策。第44页，此课件共70页哦(一一)紧互对原型对与交遇区紧互对原型对与交遇区 n假设有两类样本集X1和X2。n为找出交遇区，可先将每一类样本用聚类分析方法分为若干个聚类。n每个聚类在特征空间中占据一定区域，称为“原型区”，每个聚类的重心，或最靠近重心的一个样本，称该聚类的“原型”。n这样，每个聚类可简化为用它的原型来表示，每一类则

20、由若干个原型来表示。第45页，此课件共70页哦用原型表示交遇区。n令Vi表示i类的原型集合n式中li为i类中的原型个数，用 表示一个原型对，其中i,j=1,2，m=1,2,li,n=1,2,lj。n如果用 表示两个互对原型之间的欧氏距离，则当且仅当 和 之间的欧氏距离满足 当ij时，原型对 称为互对的。第46页，此课件共70页哦n时，称为紧互对原型对，n参见图4.11所示的例子，图中12v11v21v31v12v22v32图 4.11原型对是一个紧互对原型对。不是紧互对原型对。第47页，此课件共70页哦用表示两类紧互对原型对集合，寻找的方法可由下列步骤来完成：n步骤1 对于1类的每一个原型 ，

21、在V2中找出离它最近的原型 ，并记集合n步骤2 用同样的方法，对于每个 ,在V1中找出离它最近的原型 ，并记集合步骤3 找出L12和L21的交集，=L12L21 第48页，此课件共70页哦显然，中的紧互对原型对部位于两类样本的交遇区，因此，用紧互对原型对表示交遇区是合理的。n可将样本的紧互对原型对集合扩展到k紧互对原型对集合(k)。n寻找(k)的方法与寻找的方法相似，所不同的是在第一、二步不是只找一个最近的原型，而是找出k个。nk的选择往往借助于经验，有时取k=d=维数。第49页，此课件共70页哦4.3.3局部训练法局部训练法 n利用紧互对原型对集设计局部超平面的方法如下：n步骤l 首先在k一

22、紧互对原型对集合中找出最近的一对，用 表示。n很容易找到一个超平面把这一对原型分开，为简单起见，可以选择 和 连线的垂直平分面，这个超平面的方程是第50页，此课件共70页哦n称这一超平面为 。n设计时可利用前面介绍的各种线性判别函数算法。n步骤2 以 作为初始超平面，找出 正确分类的紧互对原型对，用这些原型所代表的聚类中的所有样本作为局部训练样本集，并利用它设计第一个超平面段。n假定 是用某种方法找到的一个最佳超平面。第51页，此课件共70页哦n这时，检验所能正确分类的紧互对原型对。n如果 正确分类的紧互对原型对与正确分类的紧互对原型对相同，则 就是所要求的第一段超平面H1；n若不完全相同，则

23、以 作为初始超平面，重复上面过程，直至两者完全相同为止，并记最后得到的超平面为H1。n步骤3 将被H1正确分类的紧互对原型对拿走，对剩下的紧互对原型对重复1、2两个步骤，以得到第二个超平面段H2。第52页，此课件共70页哦n步骤4 重复上述步骤，直到所有的紧互对原型对都被处理完毕为止。n这样，就可以序贯地得到一组(比如说共有m个)超平面H1，H2，Hm，它们构成一个分段线性分类器。第53页，此课件共70页哦4.3.4 决策规则决策规则 n假设分段线性分类器是由m个超平面段组成的。其中每段超平面都可以表示为n式中 是超平面Hi的法向量。n对于每段超平面Hi，它可能把样本x分到它的正侧，也可能分到

24、它的负侧。设 时，即x在Hi正侧时记为1，而 时记为0。第54页，此课件共70页哦n这样，对于每个样本x，由m个超平面可以产生一个m维、取值为0或1的向量。记这一向量为z(x)，则其元素zi(x)为n这样就得到z(x)=z1(x)，z2(x)，zm(x)第55页，此课件共70页哦n对于训练集中的全部N个样本，我们可以得到N个向量，记为z(x1)，z(x2)，z(xN)，其中每个z(xk)，k=1，2，N，都是一个m维由0或l组成的向量。n因为对于m维二值向量，最多有2m种可能的选择，因此，每个z(xk)只能是2m种向量之一。n对于这2m种可能的向量，统计其在两类样本集X1和X2中出现的次数，并

25、分别记为N1(zj(x)和N2(zj(x)，j=1，2，2m。n再定义一个开关函数(zj)。如果N1(zj)和N2(zj)都很小，则记(zj)=，否则第56页，此课件共70页哦n这样决策规则可写作：n如果N1(zj)和N2(zj)都较大，但二者差别较小，即 ，则说明可能还缺少超平面段，应对这部分样本重复上面的算法。若 1/211010拒绝0111/2021001/211第59页，此课件共70页哦n这一决策过程可用4.12所示的框图表示。序贯选择HiHi(z)12拒绝xzj(x)图 4.12第60页，此课件共70页哦n例4.3假设两类样本分布如图4.13(a)所示，其中“”表示第一类，“。”表示

26、第二类。说明分段线性分类器的设计过程。(a)第61页，此课件共70页哦解：n从这些原型中找出2-紧互对原型对集合和，它们的交组成2-紧互对原型对集合(2)。n利用局部训练法得到两个超平面H1和H2，它们将样本空间分为三个区域R1，R2和R3。R1中的样本大部分属于第二类，R3中的样本大部分属于第一类。R2中两类样本都有且数量相差不多，说明还缺少超平面段。n利用聚类分析方法将每类分成5个聚类，每个聚类用一个原型表示。第62页，此课件共70页哦(a)R1R2R3H1H2第63页，此课件共70页哦n对R2中的样本重复上面算法，可得到第三个超平面段H3。n最终的分段线性分类器由三个超平面H1、H2和H

27、3相应的部分组成，如图4.13(b)中实线所示，在两维空间表现为一折线段。(b)H1H2H3第64页，此课件共70页哦4.4 二次判别函数 n二次判别函数也是一种常用的非线性判别函数，其适用范围比简单的线性判别函数广。n但二次判别函数及其确定的分界面比较复杂，故只简单介绍一下它的基本概念。n二次判别函数的一般表达式为 第65页，此课件共70页哦n其中W是dd实对称矩阵，w为d维向量。为确定判别函数g(x)，需要确定n二次判别函数确定的决策面是一个超二次曲面，包括超球面、超椭球面、超双曲面等。n例如对于一类(设1类)样本分布比较成团，而另一类样本均匀地散布在其周围的两类问题，可用下述方法构造一个

28、二次判别函数：个不同的系数。因此，计算起来非常复杂。第66页，此课件共70页哦n定义二次判别函数n计算1类样本均值 和样本协方差n决策规则表示为 第67页，此课件共70页哦ng(x)=0在X空间确定了一个超椭球面。n它的大小由K来控制，K越大，则落入超椭球外面的第一类样本点越少，因此第一类错分为第二类的概率越小，但第二类误为第一类的概率将增大。n如果两类样本分布各自都比较集中，则可以分别定义两类的判别函数为第68页，此课件共70页哦n其中 nNi为i类的样本数，n若定义 g(x)=g1(x)g2(x)n则决策面方程为第69页，此课件共70页哦n选择适当的K1和K2则可调整两类的错误率。n实际上，如果两类样本都来自正态分布，且对样本均值向量和样本协方差矩阵的估计 和 接近真实分布的期望和协方差矩阵mi和i，则上述二次判别函数确定的分类器错误率和贝叶斯分类器错误率很接近。Ki的作用则反映了i和先验概率P(i)对决策面的影响。因此可以推知，这种分类器的效果将是比较好的。n由上式定义的二次判别函数与第二章(2-112)式xT(WiWj)x+(wiwj)Tx+wi0wj0=0十分相似。第70页，此课件共70页哦