(8)多类分类器的设计之-第五章-分段线性判别函数

多类分类器的设计•分段线性判别函数法（分段LDA法）第五章非线性判别函数5.1分段线性判别函数法利用线性判别函数设计多类分类器有多种方法.例如，可以把c类问题化为c-1个两类问题，其中第i个问题是用线性判别函数把属于类的点同不属于类的点分开，见图4.14(a)．•问题的提出多类分类器的设计再麻烦一些的方法是用c(c-1)／2个线性判别函数，把样本分为c个类别，每个线性判别函数只对其中的两个类别分类，如图4.14(b)所示。这两种方法都会产生如图中的阴影区域，对这个阴影区域中的点，无法确定其类别。•分段线性判别函数的基本概念多类分类器的设计•用分段线性判别函数解决问题的思路1)在各类中取若干个代表点（例wi类就取li个代表点），代表点可以是wi类样本的均值，也可以是属于wi类的样本2)将wi类划分为li个子类,每个子类包含1个代表点3)每个子类定义一个判别函数多类分类器的设计4)定义wi类判别函数5)决策规则：6)决策面方程：多类分类器的设计•解决问题的关键1.如何确定各类的子类数目li?2.如何求各子类的判别函数?xgki多类分类器的设计5.1.1一种简单的基于距离的分段线性判别函数多类分类器的设计多类分类器的设计5.1.3分段线性分类器设计的一般考虑设计线性分类器，就是确定权向量ω和阀值权或广义权向量α。而设计分段线性分类器，则是利用样本集确定一组和1)已知样本的子类划分情况:把子类看作独立的类，然后利用线性判别函数算法把各个子类分开，自然也就把各类分开了．这种方法必须以已知子类划分为前提．划分子类的一种方法是根据先验知识直观判定.如字符识别中，可把同一字符看作一类，而把其中不同的字体看作它的不同于类．另一种方法则借助于聚类分析方法来解决。0lili0多类分类器的设计2)已知子类数目li，但不知子类划分情况时3)未知子类数目(这是一般的情况)在这种情况下,设计分段线性分类器的方法很多,在这里我们仅举一例:树状分段线性分类器.对于图5.5所示的两类情况,先用两类线性判别函数算法找一个权向量α1，它所对应的超平面H1把整个样本集分成两部分,我们称之为样本子集.由于样本集不是线性可分的,因而每一部分仍然包含两类样本.接着,再利用算法找出第二个权向量α2,第三个权向量α3超平面H2,H3分别把相应的样本子集分成两部分.若每一部分仍然包含两类样本,则继续上述过程,直到某一权向量(如图中α4)把两类样本完全分开为止.这样得到的分类器显然也是分段线性的，其决策面如图中粗线所示.表示权向量αi方向,它指向超平面Hi的正侧.它的识别过程是一个树状结构,如图5.6所示.图中用虚线显示了对未知样本y的决策过程，经过三步，判断y∈w1。多类分类器的设计需要指出,这种方法对初始权向量的选择很敏感，其结果随初始权向量的不同而大不相同.此外，在每个节点上所用的寻找权向量αi的方法不同.结果也将各异.通常可以选择分属两类的欧氏距离最小的一对样本，取其垂直平分面的法向量作为α1的初始值．然后求得局部最忧解α1*作为第一段超平面的法向量．对包含两类样本的各子类的划分也可以采用同样的方法．5.2基于凹函数的并的分段线性判别函数（针对多峰情况）设Li为线性判别函数，i=1,2,…..r则：(a)：L1,L2,……Lr都是分段线性判别函数(b)：若A,B都是分段线性判别函数，则：A∧B，A∨B也是分段线性判别函数。A∧B取最小，A∨B取最大。(c)：对任何分段线性函数都可以表示成如下二种形式：1)、析取范式(这是经常采用的形式)P=(L11∧L12∧…∧L1m)∨…∨(Lq1∧Lq2∧…∧Lqm)2)、合取范式Q=(L11∨L12∨…∨L1m)∧…∧(Lq1∨Lq2∨…∨Lqm)每个(Li1∧Li2∧…∧Lim)都称为凹函数。。每个子类的判别函数数子类。mjxqixxwLijij,...,2,1,,0,...,2,1,,021对于多峰二类问题：设第一类有q个峰，则有q个凹函数。即P=P1∨P2∨……∨Pq每个凹函数Pi由m个线性判别函数来构成。∴Pi=Li1∧Li2∧…∧Lim假设对于每个子类线性判别函数Lij都设计成：21,0,0xPxP则则判别规则：例、设如图个分段判别函数有判别函数个数：这样它有三个子类。分三个峰，1344533211mmmq。则。若则若2134312421151211,0,0),...,min(),,...,min(),,...,,min(maxxPxPlllllllP15l11l12l13l14l22l24l23l21l34l33l32l31l1121312∴P=(L11∧L12∧L13∧L14∧L15)∨(L21∧L22∧L23∧L24)∨(L31∧L32∧L33∧L34)5.3用交遇区的样本设计分段线性分类器------一种实现最少分段线性分类器的方法•交遇区当两类样本非线性可分时,贝叶斯分界面一般通过两类样本十分靠近或相互交迭的区域,我们称之为“交遇区”,如图5.10所示.其中a,c是交迭区,b是靠近区•局部训练法把这些区域找出来，利用这些区域中的样本作为新的样本集设计线性判别函数，然后把它们连在一起，就构成了一个分段线性判别函数.这种方法称为“局部训练法”多类分类器的设计(1)如何从样本集中找出“交遇区”；(2)如何利用“交遇区”中的样本设计线性分类器；(3)如何进行分类决策。多类分类器的设计需要解决的问题:prototype出来类中各取一个和prototypeji相距最近的一对。互对原型对集合中，5.4二次判别函数二次判别函数一般可表示成：计算量很大）非常复杂的系数一共有维权向量为维的权向量。是其中：,(1)3(21)(n2)(11110120nnlxgWnnWWxwxxwxwWXWXWXxgnjjinjjjijjiniiiiTT分布分散。如下图：峰，分布比较集中，形成单若已知样本超球面，超双曲面等）面。二次决策面为超二次曲21)1((协方差为均值，为其中：大小。的大小，决定超平面的判别函数定义1111111121,)()()(:kxxkxgT12类比较集中1控制大小由是个超球面判别平面：判别规则：k0)(,0)(,0)(121xgxxgxxg协方差，为均值，，为其中：，两个判别函数：都比较集中，那么定义，）如果（212112212,1)()()(2iiiiTiiiixxkxg。可用来调整二类错误率判别规则：判别平面方程：21212221212211111221111211221,,0,0)(0)()()(2)()()()(kkxxxgkkxxxxgxgxgTTTT1x2x12二次分界面