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

多类分类器的设计•分段线性判别函数法（分段LDA法）第五章非线性判别函数5.1分段线性判别函数法利用线性判别函数设计多类分类器有多种方法.例如，可以把c类问题化为c-1个两类问题，其中第i个问题是用线性判别函数把属于类的点同不属于类的点分开，见p112图4.14(a)．•问题的提出多类分类器的设计再麻烦一些的方法是用c(c-1)／2个线性判别函数，把样本分为c个类别，每个线性判别函数只对其中的两个类别分类，如p112图4.14(b)所示。这两种方法都会产生如图中的阴影区域，对这个阴影区域中的点，无法确定其类别。第三种方法是这方法不会产生如前的阴影区域（无法确定其类别），如右图所示。•分段线性判别函数的基本概念多类分类器的设计•用分段线性判别函数解决问题的思路多类分类器的设计1201,2,12,,,3()()1,2,,1,2,,4()max()(55)5iiiiiliiiillTliiiliiiillgxwxwllicgxgx）在各类中选若干个代表点；例中选个代表点；（代表点可以是各类的均值，也可是各类的样本））每一类按代表点分为若干子类：（每个子类包含一个该类的代表点））对每个子类定义一个线性判别函数：）定义的线性判别函数：）决策()max()(56)6()()(57)jijijnmnmijijifgxgxthenxgxgx规则：）决策面方程：（和相邻）•解决问题的关键2kixg？、如何求各子类的判别函数1il、如何确定各子类的数目？5.1.1一种简单的基于距离的分段线性判别函数多类分类器的设计多类分类器的设计5.1.3分段线性分类器设计的一般考虑多类分类器的设计设计线性分类器，就是确定权向量ω和阀值权。而设计分段线性分类器，则是利用样本集确定一组和1)已知样本的子类划分情况:把子类看作独立的类，然后利用线性判别函数算法把各个子类分开，自然也就把各类分开了．这种方法必须以已知子类划分为前提．划分子类的一种方法是根据先验知识直观判定.如字符识别中，可把同一字符看作一类，而把其中不同的字体看作它的不同子类．另一种方法则借助于聚类分析方法来解决。lili002)已知子类数目li，但不知子类划分情况时算法步骤：（1）赋初值,分别给个子类的权矢量赋任意的初值，选择正常数，置步数1k(1,2,)iliwllil•（2）输入已知类别的增广训练模式，计算kx1,2,()(1,2,,)()max()iillmlikkikikllgxwxicgxgx且使•（3）修正权矢量，修正规则是：&()()(,1,2,)(1)()()ijiimnkikkjllifxgxgxjinlthenwkwk正确分类1,2,(1)(),(1)()()max()(1,2,,)iijjjjjmmnnkknnkknlelsewkwkxwkwkxgxgxjc其中：(4)ifkN,令k=k+1,返至⑵；ifk=N，检验判别函数是否对都能正确分类，若是，结束；否则，令k=1，返至⑵。3)未知子类数目(这是一般的情况)多类分类器的设计在这种情况下,设计分段线性分类器的方法很多,在这里我们仅举一例:树状分段线性分类器.对于图5.5所示的两类情况,先用两类线性判别函数算法找一个权向量，它所对应的超平面把整个样本集分成两部分,我们称之为样本子集.由于样本集不是线性可分的,因而每一部分仍然包含两类样本.接着,再利用算法找出第二个权向量,第三个权向量超平面分别把相应的样本子集分成两部分.若每一部分仍然包含两类样本,则继续上述过程,直到某一权向量(如图中)把两类样本完全分开为止.这样得到的分类器显然也是分段线性的，其决策面如图中粗线所示.表示权向量方向,它指向超平面的正侧.它的识别过程是一个树状结构,如图5.6所示.图中用虚线显示了对未知样本y的决策过程，经过三步，判断11H2323,HH4iiH1y需要指出,这种方法对初始权向量的选择很敏感，其结果随初始权向量的不同而大不相同.此外，在每个节点上所用的寻找权向量α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)、析取范式(这是经常采用的形式)2)、合取范式每个都称为凹函数。1111121,12,11121,12,()()maxmin(,,,),,min(,,,)qqmqqqmmqqqmPLLLLLLLLLLLL1111121,12,11121,12,()()minmax(,,,),,max(,,,)qqmqqqmmqqqmQLLLLLLLLLLLL12,iiiimLLL每个凹函数粗略地规定了某个类的一个峰。120,,1,2,...,()0,,1,2,...,ijijxiqLxwxxjm子类下标。每个子类的判别函数个数。对于多峰二类问题：设第一类有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((25二次判别函数图例1211111111:()()(),Tgxkxxk定义判别函数的大小，决定超平面的大小。其中：为均值，为协方差121类比较集中121()0,()0,()0gxxgxxgxk判别规则：判别平面：是个超球面由控制大小12(1)若已知样本分布比较集中，形成单峰，分布分散。如下图：12211111122121122111222121122()()()()2()()()00,(),0,TTTTgxgxgxxxxkkxgxkkx判别平面方程：判别规则：可用来调整二类错误率。1x2x12二次分界面122112122()()()1,2Tiiiiiiigxkxxi（）如果，都比较集中，那么定义两个判别函数：，其中：为，均值，为，协方差