《ch5多类分类器的设计之-第五章-分段线性判别函数ppt课件.ppt》由会员分享，可在线阅读，更多相关《ch5多类分类器的设计之-第五章-分段线性判别函数ppt课件.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、多类分类器的设计多类分类器的设计多类分类器的设计多类分类器的设计分段线性判别函数法（分段LDA法）第五章第五章 非线性判别函数非线性判别函数在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.1 分段线性判别函数法利用线性判别函数设计利用线性判别函数设计多类多类分类器有多种方法分类器有多种方法.例如，可以把例如，可以把c c类问题化类问题化为为c-c-1 1个两类问题，其中个两类问题，其中第第i i个问题是用线性判别个问题是用线性判别函数把属于类的点同不属函数把属于类的点同不属于类的点分开，于类的点分开，见见p112p112图图4.1
2、4(4.14(a)a)问题的提出多类分类器的设计多类分类器的设计在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确再麻烦一些的方法是用再麻烦一些的方法是用c(c-c(c-1)1)2 2个线性判别函个线性判别函数，把样本分为数，把样本分为c c个类别，每个线性判别函数只个类别，每个线性判别函数只对其中的两个类别分类，如对其中的两个类别分类，如p112p112图图4.14(4.14(b)b)所示。所示。这两种方法都会产生这两种方法都会产生这两种方法都会产生这两种方法都会产生如图中的阴影区域，如图中的阴影区域，如图中的阴影区域，如图中的阴影区
3、域，对这个阴影区域中的对这个阴影区域中的对这个阴影区域中的对这个阴影区域中的点，无法确定其类别。点，无法确定其类别。点，无法确定其类别。点，无法确定其类别。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第三种方法是第三种方法是这方法不会产生如前这方法不会产生如前这方法不会产生如前这方法不会产生如前的的的的阴影区域阴影区域阴影区域阴影区域（无法确（无法确（无法确（无法确定其类别），如右图定其类别），如右图定其类别），如右图定其类别），如右图所示。所示。所示。所示。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的
4、梯度，由浅入深，所提出的问题也很明确分段线性判别函数的基本概念分段线性判别函数的基本概念多类分类器的设计多类分类器的设计用分段线性判别函数解决问题的思路用分段线性判别函数解决问题的思路多类分类器的设计多类分类器的设计解决问题的关键解决问题的关键在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.1.1一种简单的基于距离的分段线性判别函数一种简单的基于距离的分段线性判别函数一种简单的基于距离的分段线性判别函数一种简单的基于距离的分段线性判别函数多类分类器的设计多类分类器的设计在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置
5、具有一定的梯度，由浅入深，所提出的问题也很明确在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确多类分类器的设计多类分类器的设计在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.1.3 分段线性分类器设计的一般考虑分段线性分类器设计的一般考虑多类分类器的设计多类分类器的设计设计线性分类器，就是确定权向量设计线性分类器，就是确定权向量和阀值权和阀值权 。而设计而设计分段线性分类器，则是利用样本集确定一组分段线性分类器，则是利用样本集确定一组 和和1)1)已知样本的子类划分情况已
6、知样本的子类划分情况:2)2)把子类看作独立的类，然后利用线性判别函数算法把把子类看作独立的类，然后利用线性判别函数算法把各个子类分开，自然也就把各类分开了这种方法必各个子类分开，自然也就把各类分开了这种方法必须以须以已知子类划分已知子类划分为前提划分子类的一种方法是根为前提划分子类的一种方法是根据先验知识直观判定据先验知识直观判定.如字符识别中，可把同一字符如字符识别中，可把同一字符看作一类，而把其中不同的字体看作它的不同子类看作一类，而把其中不同的字体看作它的不同子类另一种方法则借助于聚类分析方法来解决。另一种方法则借助于聚类分析方法来解决。2)2)已知子类数目已知子类数目已知子类数目已知
7、子类数目l l l li i i i ，但不知子类划分情况时，但不知子类划分情况时，但不知子类划分情况时，但不知子类划分情况时算法步骤：算法步骤：算法步骤：算法步骤：l（1 1）赋初值）赋初值,分别给分别给 个子类的权矢量个子类的权矢量 赋任意的初值，选择正常数赋任意的初值，选择正常数 ，置步数，置步数 （2 2）输入已知类别的增广训练模式）输入已知类别的增广训练模式 ，计算，计算（3 3）修正权矢量，修正规则是：）修正权矢量，修正规则是：(4)if kN,(4)if kN,(4)if kN,(4)if kN,令令令令k=k+1,k=k+1,k=k+1,k=k+1,返至返至返至返至；if k=
8、Nif k=Nif k=Nif k=N，检验判别函数是否对都能正确分类，若是，结束；否，检验判别函数是否对都能正确分类，若是，结束；否，检验判别函数是否对都能正确分类，若是，结束；否，检验判别函数是否对都能正确分类，若是，结束；否则，令则，令则，令则，令k=1k=1k=1k=1，返至，返至，返至，返至。3)未知子类数目未知子类数目(这是一般的情况这是一般的情况)多类分类器的设计多类分类器的设计在这种情况下在这种情况下,设计分段线性分类器的方法很多设计分段线性分类器的方法很多,在这里我们仅在这里我们仅举一例举一例:树状分段线性分类器树状分段线性分类器.对于图对于图5.55.5所示的两类情况所示的
9、两类情况,先用先用两类线性判别函数算法两类线性判别函数算法找一个权向量，它所对应的超找一个权向量，它所对应的超平面把整个样本集分成两部分平面把整个样本集分成两部分,我们称之为样本子集我们称之为样本子集.由于由于样本集不是线性可分的样本集不是线性可分的,因而每一部分仍然包含两类样本因而每一部分仍然包含两类样本.接接着着,再利用算法找出第二个权向量再利用算法找出第二个权向量,第三个权向量第三个权向量 超平面超平面分别把相应的样本子集分成两部分分别把相应的样本子集分成两部分.若每一部分仍然包含两若每一部分仍然包含两类样本类样本,则继续上述过程则继续上述过程,直到某一权向量直到某一权向量(如图中如图中
10、)把两类把两类样本完全分开为止样本完全分开为止.这样得到的分类器显然也是分段线性的，这样得到的分类器显然也是分段线性的，其决策面如图中粗线所示其决策面如图中粗线所示.表示权向量方向表示权向量方向,它指向超它指向超平面的正侧平面的正侧.它的识别过程是一个树状结构它的识别过程是一个树状结构,如图如图5.65.6所示所示.图中用虚线显示了对未知样本图中用虚线显示了对未知样本y y的决策过程，经过三步，判的决策过程，经过三步，判断断在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确需要指出需要指出,这种方法对这种方法对初始权向量的选择很敏初始权
11、向量的选择很敏感，感，其结果随初始权向其结果随初始权向量的不同而大不相同量的不同而大不相同.此外，在每个节点上所此外，在每个节点上所用的寻找权向量用的寻找权向量 i i的方的方法不同法不同.结果也将各异结果也将各异.通常可以选择通常可以选择分属两类分属两类的欧氏距离最小的一对的欧氏距离最小的一对样本样本，取其垂直平分面，取其垂直平分面的法向量作为的法向量作为 1 1的初始的初始值然后求得局部最忧值然后求得局部最忧解解 1 1*作为第一段超平作为第一段超平面的法向量对包含两面的法向量对包含两类样本的各子类的划分类样本的各子类的划分也可以采用同样的方法也可以采用同样的方法在整堂课的教学中，刘教师总
12、是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.2用用凹函数的并凹函数的并表示分段线表示分段线性判别函数（针对多峰情况性判别函数（针对多峰情况）设设L Li i为线性判别函数，为线性判别函数，i i=1,2,.r=1,2,.r则：则：v(a)a)：L L1 1,L L2 2,L Lr r都是分段线性判别函数都是分段线性判别函数v(b)b)：若若A,BA,B都是分段线性判别函数，则：都是分段线性判别函数，则：AB AB，ABAB也是分段线性判别函数。也是分段线性判别函数。ABAB取最小取最小 ，ABAB取最大。取最大。v(c)(c)：对任何分段线性函数都可以
13、表示成如下二对任何分段线性函数都可以表示成如下二种形式：种形式：1)1)、析取范式、析取范式(这是经常采用的形式这是经常采用的形式)2)2)、合取范式合取范式每个都称为凹函数。每个都称为凹函数。|每个凹函数粗略地规定了某个类的一个峰。每个凹函数粗略地规定了某个类的一个峰。v对于多峰二类问题：设第一类有对于多峰二类问题：设第一类有q个峰，则有个峰，则有q个凹函个凹函数。即数。即P=P1P2Pqv每个凹函数每个凹函数Pi由由m 个线性判别函数来构成。个线性判别函数来构成。Pi=Li1Li2Limv假设对于每个子类线性判别函数假设对于每个子类线性判别函数Lij都设计成：都设计成：v例、设如图例、设如
14、图P=(L11L12 L13 L14 L15)(L21L22 L23 L24)(L31L32 L33 L34)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.3 5.3 用交遇区的样本设计分段线性分类器用交遇区的样本设计分段线性分类器-一种实现最少分段线性分类器的方法一种实现最少分段线性分类器的方法一种实现最少分段线性分类器的方法一种实现最少分段线性分类器的方法 交遇区交遇区交遇区交遇区当两类样本当两类样本非线性可分时非线性可分时非线性可分时非线性可分时,贝叶贝叶斯分界面一般通过两类样本十分斯分界面一般通过两类样本十分靠近或相互交
15、迭的区域靠近或相互交迭的区域,我们称我们称之为之为“交遇区交遇区”,”,如图如图5.105.10所示所示.其中其中a,ca,c是交迭区是交迭区,b b是靠近区是靠近区 局部训练法局部训练法局部训练法局部训练法把这些区域找出来，利用这些把这些区域找出来，利用这些区域中的样本作为新的样本集区域中的样本作为新的样本集设计线性判别函数，然后把它设计线性判别函数，然后把它们连在一起，就构成了一个分们连在一起，就构成了一个分段线性判别函数段线性判别函数.这种方法称这种方法称为为“局部训练法局部训练法”多类分类器的设计多类分类器的设计在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯
16、度，由浅入深，所提出的问题也很明确(1)(1)如何从样本集中找出如何从样本集中找出“交遇区交遇区”；(2)(2)如何利用如何利用“交遇区交遇区”中的样本设计线性分类器；中的样本设计线性分类器；(3)(3)如何进行分类决策。如何进行分类决策。多类分类器的设计多类分类器的设计需要解决的问题需要解决的问题:在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确prototype在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.4 二次判别函数二次判别函数v二次判别函数一般可表示成：二次判别函数一般可表示成：在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 二次判别函数图例二次判别函数图例25