模式识别第四章(4)非线性判别函数

4.7

非线性判别函数

前面讨论的用线性判别函数设计分类器，在多类情况下可以用树分类器进行多级分类。若在树分类器的各节点上采用线性判别规则，就构成了一个分段线性分类器。

当两类样本分布具有多峰性质并互相交错时，简单的线性判别函数往往会带来较大的分类错误。采用分段线性分类器，常常能有效地应用于这种情况。

整理ppt4.7.1分段线性判别函数的基本概念分段线性判别函数是一种特殊的非线性判别函数。它确定的决策面是由若干超平面段组成的。由于它的基本组成仍然是超平面，因此，与一般超曲面(例如贝叶斯决策面)相比，仍然是简单的；又由于它是由多段超平面组成的，所以它能逼近各种形状的超曲面，具有很强的适应能力。

整理ppt图4.7.1中分别给出了采用线性判别函数，分段线性判别函数和二次判别函数所得到的分界面。ω1ω1ω2ⅠⅡⅢⅠ：线性判别Ⅱ：分段线性判别Ⅲ：二次判别图4.7.1整理ppt当类条件概率密度函数为正态分布，各特征统计独立且同方差时，贝叶斯决策规则可得到线性判别函数，特别是当P(ω1)=P(ω2)时，决策规则可以写成这时的决策面是两类期望连线的垂直平分面，如图4.7.2所示。这样的分类器叫做最小距离分类。整理pptμ1μ2x1x2xg(x)=00图4.7.2这一判别函数虽然是在十分特殊的条件下推出来的，但它却给了我们一个相当重要的启示，这就是可以把均值作为各类的代表点，用距离作为判别函数进行分类。

整理pptω11ω12ω21ω22ω32Ⅰ：线性距离判别m1m2Ⅰ现在考虑图4.7.3所示的两类分布情况。ω1类和ω2类都是多峰分布。如果利用上面方法，把各类均值仍作为代表点，设计最小距离分类器，则得到分界面Ⅰ。缺点是错误率较大。整理pptⅡ：分段线性距离判别图4.7.3ω11ω12ω21ω22ω32Ⅱ如果每类不是只取一个代表点，而是取多个代表点，例如，ω1类取两个代表点，ω2类取三个代表点，仍利用上面定义的距离判别函数，它是由多段超平面组成的，其中每一段都是最小距离分类器。这样的结果是令人满意的。

把未知样本x归到离它最近的代表点所属的类别，则可得到如图中折线(即分界面Ⅱ所示的分段线性分界面，整理ppt一般地，如果对于ωi类取li个代表点，或者说，把属于ωi类的样本区域Ri分为li个子区域，即，其中表示第i类的第l个子区域，用表示该子区域中样本的均值向量，并以此作为该子区域的代表点，这样可以定义如下判别函数这样的分类器叫做分段线性距离分类器。若有则把x归到ωj类。整理ppt4.7.2分段线性判别函数

把上述基于距离的分段线性判别函数概念加以推广。在前面，把每一类都分为若干子区域，并选择各子区域的均值向量作为代表点以设计最小距离分类器。但这种方法只在某些特殊情况下才能得到较好的分类结果，在很多情况下往往不适用。整理ppt例如图4.4所示的样本分布情况。图中各类样本服从正态但非等协方差分布，其等概率密度面为超椭球面，用虚线表示。利用贝叶斯决策规则对样本x进行分类，应决策x∈ω2类；但若以μi作为代表点，按到μi的欧氏距离进行分类，则应决策x∈ω1类。这与贝叶斯决策相矛盾。μ1μ2x1x20x图4.7.4整理ppt只考虑作为各类或各子区域代表点所提供的信息是很不够的。如何利用整个样本集所提供的全部信息是需要考虑的问题。把每一类分为若干个子类，即令不是选择各子类的均值作为代表点设计最小距离分类器，而是对于每个子类定义一个线性判别函数整理ppt则对于c类问题可定义c个判别函数gi(x)，i=1，2，…，c，并得到决策规则：l=1，2，…，li，i=1，2，…，c式中和分别为子类的权向量和阈值权。如果定义ωi的线性判别函数为则决策x∈ωj

对于任意样本x，必有某个子类的判别函数值较其它的判别函数值为最大。整理ppt得到的决策面也是分段线性的，其决策面方程是由各子类的判别函数确定的，如果第i类的第n个子类和第j类的第m个子类相邻，则该决策面方程是关键问题是如何利用样本集确定子类数目以及如何求各子类的权向量和阈值权。

假如具有最大值的判别函数是，则把x归到子类所属的类，即类。整理ppt4.7.3分段线性分类器设计的一般考虑

分类器设计的基本问题是，在一定判别函数类内利用训练样本集确定分类器的参数，即确定判别函数中的系数。设计线性分类器，就是确定权向量w和阈值权w0或广义权向量a。而设计分段线性分类器，则是利用样本集确定一组和。整理ppt㈠利用多类线性判别函数算法设计分段线性分类器若已知样本的子类划分情况，可把子类看作独立的类，然后利用多类线性判别函数算法把各个子类分开，自然也就把各类分开了。这种方法必须以已知子类划分为前提。划分子类的一种方法是根据先验知识直观判定，如字符识别中，可把同一字符看作一类，而把其中不同的字体看作它的不同子类。另一种方法则借助于聚类分析方法来解决。整理ppt㈡已知子类数目时的分段线性判别函数

当已知子类数目，但不知子类划分情况时，可利用下面的错误修正算法设计分段线性分类器，它与多类线性判别函数的固定增量算法很相似，其步骤如下：步骤1首先给定各子类的初始权向量。假设ωi类中有li个子类，则任意给定，，……，，i=1，2，…，c后面用表示第k次迭代时，第i类第l个子类的权向量。整理ppt步骤2利用训练样本集进行迭代，并按下列规则修改权向量：若在第k次迭代时，ωj类(j=1,2，…，c)中的样本yi与ωj类的某个权向量的内积值为最大，即而且满足其中i=1，2，…，c，i≠j，l=1，2，…，li，则说明权向量组,,…,不影响yi正确分类，因此各权向量保持不变。整理ppt则说明yj被错误分类，需要对权向量进行修正。设如果存在某个或几个子类不满足上述条件，即存在，使得则修正算法为整理ppt步骤3重复上面的迭代过程，直到算法收敛或达到规定的迭代次数为止。当样本集对于给定的子类数目能用分段线性判别函数完全正确分类时，算法将在有限步内收敛，否则算法将不收敛，这时可以考虑用递减的ρk序列令算法收敛，但不可避免地会增大分类错误率。整理ppt㈢未知子类数目时的分段线性判别函数

最一般的情况是每类应分成的子类数目未知。这时，设计分段线性分类器的方法很多，以树状分段线性分类器为例说明。对于图4.7.5所示的两类情况，可先用两类线性判别函数算法找一个权向量。它所对应的超平面H1把整个样本集分成两部分，称之为样本子集。整理pptω1ω1ω2ω2图4.7.5H1H4H2H3该分类器是分段线性的。“→”表示权向量ai

的方向，它指向超平面Hi的正侧。整理ppt它的识别过程是一个树状结构，如图4.7.6所示。图中用虚线显示了对未知样本y的决策过程，经过三步，判断y∈ω1。ω1ω1ω2ω1ω2图4.7.6YYYYNNNNaT1y≥0aT2y≥0aT3y≥0aT4y≥0整理ppt通常可以选择分属两类的欧氏距离最小的一对样本，取其垂直平分面的法向量ai

作为初始值，然后求得局部最优解ai*作为第一段超平面的法向量。这种方法对初始权向量的选择很敏感，其结果随初始权向量ai

的不同而大不相同。在每个节点上所用的寻找权向量的方法不同，结果也将各异。对包含两类样本的各子类的划分也可以采用同样的方法。整理ppt4.7.4用凹函数的并表示分段线性判别函数分段线性判别函数的表示

设Li是线性函数，i=1，2，…，r，则分段线性函数可以递归地定义如下：⑴L1，L2，…，Lr都是分段线性函数。⑵如果A和B都是分段线性函数，则A∧B和A∨B也是分段线性函数。这里符号“∧”表示求小，符号“∨”表示求大。⑶分段线性函数只能由⑴和⑵的形式给出。整理ppt任何分段线性函数都可以表示为如下两种一般形式：①分段线性函数的析取范式P=(L11∧L12∧…∧L1,m1)∨…∨(Lq1∧Lq2∧…∧Lq,mq)②分段线性函数的合取范式Q=(L11∨L12∨…∨L1,m1)∧…∧(Lq1∨Lq2∨…∨Lq,mq)用析取范式P表示一个分段线性函数，其中每个(L11∧L12∧…∧Li,mi)称为一个凹函数，P是q个凹函数的并，即在q个凹函数中求最大凹函数。整理ppt对于多峰分布的两类问题，可以用分段线性判别函数P把其分开，P中的每个凹函数粗略地规定了某个类的一个峰，假设第一类呈现q个峰的分布，则P由q个凹函数Pi的并构成，记为P=(P1∨P2∨…∨Pq)其中每个凹函数Pi又是mi个线性判别函数Lij的交构成的，记为Pi

=(Li1∧Li2∧…∧Li,mi)整理ppt假定对于每个线性判别函数Lij，都使i=1，2，…，qj=1，2，…，mi则r个权向量，，…，就能对样本集正确分类，这里分段线性判别函数P是样本集X和权向量，，…，的函数，记为P(X;a1，a2，…，ar)整理ppt这样，设计分段线性分类器的问题就转化为求r个权向量a的问题了。而对于任何x∈ω2，都有P(x;a1,a2,…,ar

≤0，如果对于任何x∈ω1，都有P(x;a1,a2,…,ar)＞0，若则分段线性判别函数P就能对两类样本正确分类，即存在决策规则整理ppt例如，对于图4.7所示的分布，q=3，m1=5，m2=4，m3=4。因此分段线性判别函数L11L12L13L14L15L21L22L23L24L31L32L33L34图4.7整理pptP=(L11∧L12∧L13∧L14∧L15)

∨(L21∧L22∧L23∧L24)

∨(L31∧L32∧L33∧L34)P=max{min(L11，L12，L13，L14，L15)min(L21，L22，L23，L24)min(L31，L32，L33，L34)}在这儿，共有r=m1+m2+m3=13个线性判别函数。对于任意x∈ωi1，即x落入第一类的第i个子类中，所有的Lij

>0，j=1，2，…，mi，故Pi>0，因而P>0。整理ppt而对于任意x∈ω2，因为所有的Pi≤0，i=1，2，3,因而P≤0。对于未知的样本x，如果某个Pi>0，则x∈ωi1，因而x∈ω1。如果Pi≤0，i=1，2，3，x∈ω2。例4.1设有两个未知样本x1和x2，其分段线性判别函数的值分别为x1:L11=8L12=4L13=6L14=10L15=17L21=9L22=15L23=17L24=－3L31=－8L32=－7L33=9L34=－25整理pptx2:L11=26L12=－50L13=25L14=80L15=73L21=18L22=－4L23=－96L24=14L31=17L32=－6L33=－1L34=8∵P=max{min(L11，L12，L13，L14，L15)min(L21，L22，L23，L24)min(L31，L32，L33，L34)∴Px1=max{min(8,4,6,10,17),min(9,15,17,－3),min(－8,－7,9,－25)}=max{4,－3,－25}=4>0决策x1∈ω1整理pptPx2=max{min(26,－50,25,80,73),min(18,－4,－9,14),min(17,－6,－1,8)=max{－50,－9,－6}=－6<0决策x2∈ω2有了分段线性判别函数的定义，如何利用样本集，求出r个权向量，，…，使之满足。整理ppt4.2.2算法步骤令X1和X2分别表示来自ω1和ω2类的样本集。要找出若干个分段线性判别函数Pi组成的分段线性分类器，有效地对ω1和ω2进行分类。假设用线性判别函数，i=1，2，…，r找出，，…，的迭代算法如下：

整理ppt⑴检验k是否为0，并选择Ai1(k)和Ai2(k)。若k=0，则令Ai1(0)，Ai2(0)，i=1，2，…，r分别是从X1和X2中任意选出的第一类和第二类样本的非空子集。步骤1任意给定初始权向量a1(0)，a2(0)，…，a1(0)步骤2令a1(k)，a2(k)，…，ar(k)表示第k次迭代时得到的权向量，可按下述方式得到第k+1次迭代时的权向量a1(k+1)，a2(k+1)，…，ar(k+1)整理ppt若k≠0。则令Ai1(k)和Ai2(k)分别是X1和X2中所有满足下式的样本x组成的样本子集，aiT(k)=P(x;a1(k),a2(k),…,ar(k))或写作式中i=1，2，…，r，很明显，这样的x一定最接近由ai(k)所决定的超平面整理ppt⑵以Ai1和Ai2为样本集，求第k+1次最优权向量即找r个线性判别函数将Ai1和Ai2有效地分开。,i=1，2，…，r，这可用前面介绍的各种线性判别函数算法来解决，也可以作为初始权向量，经过反复迭代找出最优的权向量。步骤3检验由构成的分段线性判别函数P是否能正确分类样本集X1和X2，若能，则就是所求的最优权向量；若不能，则令k=k+1，重复上面的过程。直到算法收敛，或令k达到一个预先规定的上界为止。整理ppt用图4.8给出这种算法的框图。其中：INUM表示以作初始权向量，为求最优而限定的迭代次数。IPLS表示求分段线性判别函数中的a1*,a2*,…,a3*)的迭代次数的上限。IREP表示重新选择初始权向量a1(0),a2(0),…,ar(0)以及Ai1(0)和Ai2(0)的次数。在图4.8中，选择IREP=10。整理pptI=1I>IREP?任意选择初始权向量k=0k=0?按(4-19)式选择Ai1(k)和Ai2(k)正确分X1和X2吗？P(·)停机：输出解向量集停机：将10次迭代中样本错误率最小的分段线性判别函数作为最终结果随机选择Ai1(0)和Ai2(0),i=1,2,…,rk=k+1k=IRLS?I=I+1YYYYNNNN图4.8以为初始权向量以Ai1(k)和Ai2(k)为样本集，求线性判别函数权向量限制迭代次数为INUM整理ppt这种算法存在的主要问题是：⑴在算法执行前，要首先判断每类分布有多少个峰，从而决定选择哪一类作设计，并确定设计几个分段线性判别函数才符合要求。这就需要对样本集有一定的先验知识。如果没有足够的先验知识，实验结果表明，只要选择多于峰数的分段线性判别函数，结果也将是令人满意的。整理ppt这种算法存在的主要问题是(续)：⑵在算法执行前，要给出每个分段线性判别函数中分段的数目。⑶理论上没有证明算法的收敛性。但大量实验结果表明，算法一般都能收敛到较好的结果。多设几次权向量初值，并重新选择Ai1(0)和Ai2(0)。整理ppt4.7.2用交遇区的样本设计分段线性分类器算法基本思想

这是一种实现最少分段线性分类器的方法。当两类样本非线性可分时，贝叶斯分界面一般通过两类样本十分靠近或相互交迭的区域，称之为"交遇区"。整理pptacbω1ω2图4.10把这些区域找出来，利用这些区域中的样本作为新的样本集设计线性判别函数，然后把它们连在一起，就构成了一个分段线性判别函数，这种方法称为“局部训练法”，所得的分界面是分段线性分界面，它可以很好地逼近贝叶斯分界面。

如图4.10所示，其中(a)(c)是交迭区，(b)是靠近区。整理ppt综上所述，这种方法大体需要解决以下几个问题：

⑴如何从样本集中找出“交遇区”；⑵如何利用“交遇区”中的样本设计线性分类器；⑶如何进行分类决策。

整理ppt(一)紧互对原型对与交遇区

假设有两类样本集X1和X2。为找出交遇区，可先将每一类样本用聚类分析方法分为若干个聚类。每个聚类在特征空间中占据一定区域，称为“原型区”，每个聚类的重心，或最靠近重心的一个样本，称该聚类的“原型”。这样，每个聚类可简化为用它的原型来表示，每一类则由若干个原型来表示。整理ppt用原型表示交遇区。令Vi表示ωi类的原型集合式中li为ωi类中的原型个数，用表示一个原型对，其中i,j=1,2，m=1,2,…,li,n=1,2…,lj。如果用表示两个互对原型之间的欧氏距离，则当且仅当和之间的欧氏距离满足当i≠j时，原型对称为互对的。整理ppt时，称为"紧互对原型对"，参见图4.11所示的例子，图中ω1ω2v11v21v31v12v22v32图4.11原型对是一个紧互对原型对。不是紧互对原型对。整理ppt用Φ表示两类紧互对原型对集合，寻找Φ的方法可由下列步骤来完成：步骤1对于ω1类的每一个原型，在V2中找出离它最近的原型，并记集合步骤2用同样的方法，对于每个,在V1中找出离它最近的原型，并记集合步骤3找出L12和L21的交集Φ，Φ=L12∩L21

整理ppt显然，Φ中的紧互对原型对部位于两类样本的交遇区，因此，用紧互对原型对表示交遇区是合理的。可将样本的紧互对原型对集合Φ扩展到k——紧互对原型对集合Φ(k)。寻找Φ(k)的方法与寻找Φ的方法相似，所不同的是在第一、二步不是只找一个最近的原型，而是找出k个。k的选择往往借助于经验，有时取k=d=维数。整理ppt4.3.3局部训练法

利用紧互对原型对集设计局部超平面的方法如下：

步骤l首先在k一紧互对原型对集合中找出最近的一对，用表示。

很容易找到一个超平面把这一对原型分开，为简单起见，可以选择和连线的垂直平分面，这个超平面的方程是整理ppt称这一超平面为。设计时可利用前面介绍的各种线性判别函数算法。步骤2以作为初始超平面，找出正确分类的紧互对原型对，用这些原型所代表的聚类中的所有样本作为局部训练样本集，并利用它设计第一个超平面段。假定是用某种方法找到的一个最佳超平面。整理ppt这时，检验所能正确分类的紧互对原型对。如果正确分类的紧互对原型对与正确分类的紧互对原型对相同，则就是所要求的第一段超平面H1；若不完全相同，则以作为初始超平面，重复上面过程，直至两者完全相同为止，并记最后得到的超平面为H1。步骤3将被H1正确分类的紧互对原型对拿走，对剩下的紧互对原型对重复1、2两个步骤，以得到第二个超平面段H2。整理ppt步骤4重复上述步骤，直到所有的紧互对原型对都被处理完毕为止。这样，就可以序贯地得到一组(比如说共有m个)超平面H1，H2，…，Hm，它们构成一个分段线性分类器。整理ppt4.3.4决策规则

假设分段线性分类器是由m个超平面段组成的。其中每段超平面都可以表示为式中是超平面Hi的法向量。对于每段超平面Hi，它可能把样本x分到它的正侧，也可能分到它的负侧。设时，即x在Hi正侧时记为1，而时记为0。整理ppt这样，对于每个样本x，由m个超平面可以产生一个m维、取值为0或1的向量。记这一向量为z(x)，则其元素zi(x)为这样就得到z(x)=[z1(x)，z2(x)，…，zm(x)]整理ppt对于训练集中的全部N个样本，我们可以得到N个向量，记为z(x1)，z(x2)，…，z(xN)，其中每个z(xk)，k=1，2，…，N，都是一个m维由0或l组成的向量。因为对于m维二值向量，最多有2m种可能的选择，因此，每个z(xk)只能是2m种向量之一。对于这2m种可能的向量，统计其在两类样本集X1和X2中出现的次数，并分别记为N1(zj(x))和N2(zj(x))，j=1，2，…，2m。再定义一个开关函数Ω(zj)。如果N1(zj)和N2(zj)都很小，则记Ω(zj)=δ，否则整理ppt这样决策规则可写作：如果N1(zj)和N2(zj)都较大，但二者差别较小，即，则说明可能还缺少超平面段，应对这部分样本重复上面的算法。

若

<整理ppt举例假设最终的分段线性分类器由三个超平面段组成，那么z(x)最多有23=8种可能的取值如下表所示，表中同时给出了决策规则。对于未知样本x，如果z(x)=001或z(x)=111，则x∈ω1；如果z(x)=011或z(x)=100，则x∈ω2；否则拒绝。整理pptz(x)取值及决策规则表z(x)LΩ(z)决策000

δ拒绝001>1/21ω1010

δ拒绝011<1/20ω2100<1/20ω2101

δ拒绝110

δ拒绝111>1/21ω1整理ppt这一决策过程可用4.12所示的框图表示。序贯选择Hi{Hi}Ω(z)ω1ω2拒绝xzj(x)图4.12整理ppt例4.3假设两类样本分布如图4.13(a)所示，其中“×”表示第一类，“。”表示第二类。说明分段线性分类器的设计过程。(