《模式识别原理与应用》课件第4章.ppt

1、第4章线性判别分析第第4章线性判别分析章线性判别分析4.1线性判别函数线性判别函数4.2线性分类器线性分类器4.3分段线性分类器分段线性分类器4.4近邻分类器近邻分类器习题习题第4章线性判别分析4.1线性判别函数线性判别函数利用样本直接设计分类器,可以避开各类的概率密度函数的估计,其基本思想就是设定一组判别函数,并利用样本直接计算判决函数中的有关参数。在满足要求的情况下,应尽量选择简单的函数形式,最简单的是线性形式,这就是线性判别函数,有时也称线性判决函数。由线性判别函数构成的分类器称为线性分类器。本节重点分析线性判别函数的几何意义,并在此基础上介绍线性分类器设计的方法。第4章线性判别分析4.

2、1.1线性判别函数的几何意义线性判别函数的几何意义线性判别函数的形式如下:0(),1,2,Tiiigwimxw x(4-1)其中:wi 称为权向量;wi0 称为阈值权。wi和wi0 的值需根据样本集来确定。线性分类器设计的关键在于确定权向量wi和阈值权wi0。第4章线性判别分析1.两类问题的讨论两类问题的讨论在两类情况下,判决函数具有简单的形式:若，则判决（或）2；若，则判决（或）；若，则不作判决或作任意判决，即可判成、2中的任意一类。两类判决区域的分界面为)()(21xxgg)()(21xxgg)()(21xxgg1x2x第4章线性判别分析)()(21xxgg即0)()(201021wwTx

3、ww(4-2)令21www20100www(4-3)(4-4)则式（4-2）变成了如下形式：00 wTxw(4-5)第4章线性判别分析其中：12(,)Tdw www，12(,)Tdx xxx，为d矢量；w0为常数。进一步，式（4-5）改写为01 1220()0Tddgww xw xw xwxw x(4-6)其几何意义为d维欧几里德空间中的一个超平面。(1)w是超平面的法向量。对于两类分类问题,线性判决函数的几何意义在于利用一个超平面实现对特征空间Rd的划分。若以H表示超平面,则对H上的任意两点x1、x2有第4章线性判别分析110()0Tgwxw x(4-7a)220()0Tgwxw x(4-7

4、b)示意图为图4-1。式（4-7）可化为：0)(21 xxwT(4-8)由x1、x2的任意性可知,w和H上任一向量正交,即w是超平面H的法向量。第4章线性判别分析图4-1 超平面示意图第4章线性判别分析如果取最大判决，即当)()(21xxgg时,判决 ，1x否则判决2x，从而得出w指向R1,称R1中的点在H的正侧,R2中的点在H的负侧。(2)g(x)是x到超平面距离的一种代数距离。设xp为x在H上的投影,r是x到H的垂直距离,w方向上的单位法向量为,其中,w2=wTw,则x可以分解为2Tww w第4章线性判别分析wwxxrp(4-9)如图4-2所示,判别函数为00()()()()TpTTppg

5、rwwrgrrwxwxww ww xwxww第4章线性判别分析图4-2 超平面的法向量第4章线性判别分析由上式可得：wx)(gr(4-10)据此可得结论:g(x)是x到超平面距离的一种代数距离。所谓代数距离,是和绝对距离相对而言的,指的是该距离有符号,当符号为正时,表明x对应的点在超平面的正侧,反之在负侧。第4章线性判别分析当x=0时,g(x)=w0,即原点到超平面的代数距离为 w00wr(4-11)由式(4-11)可知,若w00,则原点在超平面的正侧;若w00;在负侧时,g(x)0,原点在H正侧,故包含原点的H右侧就是R1。2.多类问题的讨论多类问题的讨论所谓多类问题,是指类别数m3的情形。

6、多类情况下可以按下述三种方法进行划分。(1)任意两个模式类之间分别用单个超平面分开。对于m类中的任意两类:i、j,ij,可以确定一个超平面Hij,能把i和j两类分开,两类各占Hij的一侧。显然,对于m类的判决问题,最多需要确定的超平面个数为第4章线性判别分析)1(212mmCmHij的方程为 0()Tijijijgwxw x()()jiijgg xx(4-12a)(4-12b)其中,ij,i,j=1,2,m。gij(x)判决准则为 第4章线性判别分析0()(,1,2,)0iijjgi jmxxx(4-13)事实上,gij(x)的判决结果与gji(x)的判决结果是一致的。因此,只需用gij(x)

7、=wTijx+wij0(i0,g13(x)0的区域;2的判决区域位于g12(x)0的区域;3的判决区域位于g13(x)0,g23(x)0,gj(x)0条件只能区分属于1和不属于1。此时特征空间中还可能存在不确定区域,如图中g1(x)0,g2(x)0,g3(x)0,g2(x)0,g3(x)0的区域;2的判决区域位于g1(x)0,g3(x)0的区域;3的判决区域位于g1(x)0,g2(x)0的区域。图中的IR1、IR2、IR3区域是有两个判决函数大于0的区域,IR4区域是三个判决函数均小于0的区域,这些区域内样本无法分类。第4章线性判别分析图 4-7例4.3示例图第4章线性判别分析对于x=(x1,

8、x2)T=(6,5)T,代入判决函数可得g1(x)=1,g2(x)=6,g3(x)=4,所以x2。(3)每一模式类都有一个判别函数。对于m类的判决问题,可以确定m个超平面,它的判决函数为0()Tiiigwxw x(4-16)判决准则为,则xi。其中拒判区域为gi(x)=gj(x),ij。()max()ijjggxx第4章线性判别分析对于前面两种情况中的不确定区域,由于不确定区域内任何两类的判别函数值不相等,按最大判决思想,可以做出类别判决,因此这种情况下不存在不确定区域。图4-8画出了m=3时的判决区域划分示意图。第4章线性判别分析图 4-8 每一类具有一个判决函数的情况第4章线性判别分析【例

9、例 4.4】一个三类问题,三个判决函数为 23212211)(1)()(xgxxgxxgxxx请画出各类判决区域,并判断x=(x1,x2)T=(1,1)T属于哪一类。解解各类的判决区域如图4-9所示,分别计算得g1(x)=0,g2(x)=1,g3(x)=1,因为g2(x)g3(x),g2(x)g1(x),所以x2。第4章线性判别分析图 4-9 例4.4示例图第4章线性判别分析4.1.2广义线性判别函数广义线性判别函数线性判决函数的优点是简单易行,但在解决实际问题时经常会遇到非线性判决函数的情况,图4-10所示的两类问题(一维)就属于这种情况。对此类问题,一种处理方法是将非线性判决函数转变为线性

10、判决函数。第4章线性判别分析图 4-10 一维特征空间中非线性可分图示第4章线性判别分析由图4-10可知,1的决策区域为(,a)和(b,+),2的决策区域为(a,b),由此可以建立一个二次函数g(x)=(xa)(xb)=c0+c1x+c2x2,对应的决策规则为 210)(0)(xxgxxg若选择下列非线性变换:212,TTy yx xy，1212,TTa ac ca第4章线性判别分析于是二次判决函数就可以化为向量y的线性函数:2001()Tiiig xca yca y(4-17)对于更一般的二次判决函数(Quadratic Discriminant Function),可以表示为 didjji

11、ijdiiixxwxwwg1110)(x(4-18)第4章线性判别分析因为xixj=xjxi,不失一般性,这里假设wij=wji。因此二次判决函数就由另外的个系数来产生更复杂的分界面。取yi=fi(x)为二次式或一次式,可使g(x)变为线性函数,即 2/)1(dd001()dTiiigwa ywxa y(4-19)变换后的特征空间的维数为 ,称上式为广义线性判决函数,向量a称为广义权向量。这样,原来的问题就通过从x到y的映射简化为寻找一个齐次线性分类器问题。d2/)3(dd第4章线性判别分析4.1.3线性判别函数设计的一般步骤线性判别函数设计的一般步骤在分析几何意义时,已经指出了将多类线性判决

12、问题转化为多个两类判决问题的解决方法,这种方法的优点是两类问题的解决比较简单,缺点是存在拒绝域。由于两类问题的解决具有普遍意义,因此,线性分类器的设计重点是两类情况下的设计问题。两类情况下判决函数的形式为0)(wgTxwx第4章线性判别分析设计线性判别函数的任务就是在一定条件下,寻找最好的w和w0。具体地说,需要先给出分类器性能优劣的数学描述,所谓的“最好”是相对于某种特定的判决准则而言的,不同的准则下所得到的最好分类器未必相同。一般来说,设计两类的线性分类器需要以下三步:(1)选择样本集z=x1,x2,xN。样本集中的样本来自两类且类别已知,同一类中的样本是独立抽取的,应具有相同的分布特性。

13、第4章线性判别分析(2)确定一个准则函数J,要求满足以下两个条件:J是样本集、w和w0的函数;J的值反映分类器性能,它的极值对应于“最好”的决策。(3)用最优化技术求解准则函数,得到极值点对应的w*和w*0。当J的求解比较困难,不能得到全局最优解或是求全局最优结果比较困难时,往往通过求局部最优解(次优解)来降低求解难度,或者用计算解代替解析解。第4章线性判别分析4.2线线 性性 分分 类类 器器本节主要讨论几种典型的线性分类器设计,其关键在于最优准则以及相应的求解方法。4.2.1基于错误概率的线性分类器设计基于错误概率的线性分类器设计基于错误概率的线性分类器设计,实质上就是分析在哪些特定条件下

14、,最小错误概率的贝叶斯分类器是一种线性分类器,从而也表明,线性分类器具有很好的分类性能,在特定条件下可以达到最小的错误概率。第4章线性判别分析由第2章可知,最大后验概率判决准则(也称为最小错误概率判决准则)为)()|(max)()|(,2,1iimijjPpPpxx若则jx其判别函数可表示为()(|)()iiigpPxx(4-20)第4章线性判别分析当类概率密度函数为正态分布或接近正态分布时,即 11221(|)(2)exp()()2dTiiiiipxxx(4-21)取自然对数有 111()()()ln(2)lnln()222TiiiiiidgP xxx(4-22)第4章线性判别分析进一步,若

15、各类是等协方差阵的正态分布,即 mii,2,1 则判决函数可以不考虑 的作用,简化判决函数为 idln21)2ln(211()()()ln()2TiiiiigP xxx1012TTiiw xxw x(4-23)第4章线性判别分析其中 1ii w(4-24)101ln()2iTiiiwP(4-25)观察式(4-23),第一项与类别号i无关,可以不考虑,进一步简化判决函数为 112Txx0()Tiiigwxw x(4-26)第4章线性判别分析此时的线性分类器具有最小错误概率,在错误概率作为性能指标的情况下,是最优的结果。若增加各类等概率的条件,即 miPPi,2,1 )(则式(4-23)中的lnP

16、(i)不起作用,判别函数可以写成进一步简化判别函数 101()()()2TiTiiiigw xw xxx第4章线性判别分析gi(x)=wTix+wi0 (4-27)式(4-27)与式(4-26)是一致的,此时,1012iTiiw 以上的判决函数均为取最大值判决,即)(max)(xxjjigg则判决xi(4-28)这里,是马氏(Mahalanobis)距离平方。在各类等概率条件下,可将系数1/2舍去,将马氏距离平方直接作为判决函数,即 1()()Tiixx第4章线性判别分析1()()()Tiiigxxx(4-29)决策准则改为取最小值判决:)(min)(xxjjigg，则xi(4-30)称这种分

17、类器为线性距离分类器。若在上述条件的基础上再增加条件:类内各特征间相互独立,且具有相同方差,即 第4章线性判别分析2 I 则121iii w1021122iTTiiiiw 与该线性分类器等价的线性距离分类器简化为 2()()()Tiiiigxxxx(4-31)第4章线性判别分析此时判决函数是x到i的欧几里德距离平方,称此时的贝叶斯分类器为最小距离分类器。距离分类器的几何意义在于将样本归入与它最相似的类,这里把类均值i看做是每一类的代表点,将点x到代表点i的距离看成是相似度的度量,距离越小,相似度越高。第4章线性判别分析4.2.2Fisher线性判决线性判决Fisher在1936年发表的论文中首

18、次提出了线性判决函数,称为Fisher线性判决函数。Fisher线性判决的基本思想是寻找一个最好的投影方向,当特征向量x从d维空间映射到这个方向上时,两类能最好地分开。这个方法实际上涉及特征维数的压缩问题。特征向量x从d维空间映射到一维空间的方法很多,在数学上也很容易实现,但投影方向选择的不同,投影结果的可分性也不同,如图4-11所示 第4章线性判别分析图 4-11不同方向上的投影具有不同的可分性第4章线性判别分析在图4-11中,二维空间中的两类1、2是可分开的,在x1方向上作投影后,两类仍是可分的,但在x2方向上作投影后,两类产生了重叠,变成了不可分。由此可见,由d维空间到一维空间的映射关键

19、是找出最易于分类的投影方向。第4章线性判别分析设来自两类的样本集为Z=x1,x2,xN,xi(i=1,2,N)为d维矢量,类别数m=2,两类样本数分别为N1、N2,对应样本子集为Z1、Z2。对xi(i=1,2,N)做如下变换可实现d维空间到一维空间的映射:(1,2,)TiiyiNw x(4-32)第4章线性判别分析则由Z1、Z2可以得到两个相应的集合Y1、Y2。在上述变换过程中,w不同,对应的映射结果也不同,相应地,映射结果的可分离程度也不同。所以,寻找最好的投影方向,在数学上就表现为寻找最好的变换方向w*。选择最好的投影方向,首先需确定类间可分性“最好”的数学表示,并将其表达为一个准则函数J

20、,J的极值对应最好的类间可分性。对于Fisher线性判决而言,为了定义准则函数,需先建立几个参量,下面按d维空间和一维空间分别介绍。第4章线性判别分析1.d 维空间维空间(1)各类样本的均值向量i:1 (1,2)iiiiNxx(4-33)(2)样本类内离散度矩阵Si和总类内离散度矩阵Sw:()()(1,2)iTiiiixSxx(4-34)12wSSS(4-35)第4章线性判别分析若考虑先验概率,则总类内离散度矩阵Sw定义为1122()()wPPSSS(4-36)令Tdieee),(21xx(4-37)则2212221212121)(dddddTiieeeeeeeeeeeeeeexx(4-38)

21、第4章线性判别分析x距离i越远,xi2=e21+e22+e2d越大,该距离平方正好是矩阵(xi)(xi)T 的迹。由此可知,第i类的类内离散度矩阵Si的迹是类内各点到类中心i的距离平方的和,从而反映了该类样本集的离散程度。Si的迹越大,样本集分布越分散。第4章线性判别分析(3)样本类间离散度矩阵Sb:1212()()TbS(4-39)若考虑先验概率,则类间离散度矩阵Sb定义为 121212()()()()TbPPS(4-40)类似地,Sb 的迹为 2212121()()dblllTrS(4-41)第4章线性判别分析2.一维空间一维空间(1)各类样本的均值：i1 (1,2)iiyYiyiN(4-

22、42)(2)类内离散度 和总类内离散度：)2,1(iSiwS2()(1,2)iiiy YSyi(4-43)21SSSw(4-44)第4章线性判别分析总类内离散度反映两类的类内离散程度,类内的分散程度越小,越便于分类,也即越小越好。定义Fisher线性判决函数为wS21212()()FJSSw(4-45)在Fisher线性判决函数中,分子反映了映射后两类中心的距离平方,该值越大,类间可分性越好;分母反映了两类的类内离散度,其值越小越好;从总体上来讲,JF(w)的值越大越好,在这种可分性评价标准下,使JF(w)达到最大值的w即为最佳投影方向。第4章线性判别分析为了求出JF(w)的极大值点,需要将J

23、F(w)转化为w的显式函数。iiZTiYyiiNyNxxw)(111 (1,2)iTTiZiiNxwxw(4-46)所以 2212121212TTTTw w wwTb w S w(4-47)第4章线性判别分析2()iiiyYSy2()iTTiZxw xw()()iTTTTiiZxw xw x w wTi w S w(4-48)第4章线性判别分析因此12TTTwwS w S ww S ww S w(4-49)故Fisher线性判决函数化为()TbFTwJw S www S w(4-50)上式中的JF(w)是著名的广义瑞利(Rayleigh)商。由于JF(w)与w的函数关系比较复杂,极值点不易求解

24、,为此,令分母等于非零常数,在此约束条件下求极值,用Lagrange乘数法求解,设 第4章线性判别分析0TwCw S w(4-51)定义目标函数:(,)()TTbwLCww S ww S w(4-52)其中,为Lagrange乘子,对上式求关于w的梯度:(,)2bwLwS wS ww(4-53)极值点满足:*0bwS wS w(4-54)第4章线性判别分析由于Sw是对称的和半正定的,当样本数目Nd时通常是非奇异的,因而有 1*wbS S ww(4-55)即w*是S-1wSb的特征向量,可以利用一般求解特征矢量的方法求解。Fisher利用Sb的性质实现了w*的解析求解,具体方法如下:第4章线性判

25、别分析*1212TbS ww*1212 Tw12R(4-56)其中*21wTR(4-57)为一标量,所以Sbw*总在12方向上,即两中心点的连线方向,如图4-12所示。第4章线性判别分析图 4-12Sbw*方向示意图第4章线性判别分析从而有*1*112()wbwRwS S wS(4-58)求得*112()wRwS(4-59)忽略常量因子,得 R*112()wwS(4-60)第4章线性判别分析利用w*,将样本x往该方向上投影,可得 xwTy)(*(4-61)在投影空间内的决策准则为:若yy0,则x1,否则x2。Fisher线性分类器具有如下性质:(1)当维数d和样本数N都很大时,在两类的先验概率

26、相等及正态等协方差阵情况下,Fisher线性判决与最小错误概率判决准则的结果等价 第4章线性判别分析(2)阈值y0的典型选择有三种:)(21210y(4-62)(12211210NNNNy(4-63)()(ln21)(212121210PPNNy(4-64)第4章线性判别分析4.2.3感知准则函数感知准则函数感知准则函数的基本思想是寻找一个权向量,使规范化增广样本向量集的错分样本数最少。在介绍感知准则函数之前,首先介绍几个相关的基本概念。1.线性可分性线性可分性已知来自1和2两类的样本集x1,x2,xN,两类的线性判决函数为第4章线性判别分析0)(wgTxwx若令，则得到d+1维的样本集y1,

27、y2,yN,称yi为增广样本向量,v为增广权向量。相应的线性判决函数变为iixy1wv0wiTigyvy)(第4章线性判别分析如果存在一个线性分类器能把每个样本正确分类,即若存在一个权向量v,使得对于任何yi1,都有vTyi0,而对于任何yi2,都有vTyi0,这个过程称为样本的规范化,zi称为规范化增广样本向量。经过这样的变换后,我们可以不考虑样本原来的类别标志,只要找到一个对全部样本zi都满足vTzi0(i=1,2,N)的权向量即可。第4章线性判别分析3.解向量和解区解向量和解区对于规范化增广样本向量而言,满足vTzi0(i=1,2,N)的权向量称为解向量。若把v看成是权向量空间中的一点,

28、对于任一zi,vTzi=0在权向量空间确定了一个超平面,这个超平面的法向量为zi,超平面正侧的向量满足vTzi0。相应地,N个样本确定了N个超平面,每个超平面把权空间分为两个半空间。所以,满足vTzi0(i=1,2,N)的权向量必在这N个超平面正侧的交叠区,称这一交叠区为解区,解区中的任意向量都是解向量v*,如图4-13所示。第4章线性判别分析图 4-13解区和解向量示意图第4章线性判别分析为了使解向量更加可靠,应选择位于解区中间的解向量,因此引入余量b0,即使解向量满足vTzib(i=1,2,N)。显然由此确定的新解区在原解区中,而且它的边界离原来解区边界的距离为b/zi,如图4-14所示。

29、第4章线性判别分析图 4-14 解区和解向量示意图第4章线性判别分析下面我们来讨论感知准则函数。感知准则函数是在研究感知器时得到的,适用于两类判决。设Z=z1,z2,zN是经过规范化的一组样本集,定义感知准则函数如下:()()kTpZJzvv z(4-67)其中,Zk是被权向量v错分类的样本集合,当zZk时,有 0zvT(4-68)显然,Jp(v)0。第4章线性判别分析当且仅当错分样本集Zk为空时,Jp(v)=0,即Jp(v*)=minJp(v)=0,这时将不存在错分样本,而v*就是我们要寻找的解向量。可以用梯度下降法求解v*。()()()kppZJJzvvzv(4-69)第4章线性判别分析迭

30、代公式为(1)()kkZkkzvvz(4-70)其中(4-71)0)(zvzTkkZ即Zk为第k步被错分的样本集。可以证明,若有解,则迭代过程在有限步内收敛,收敛速度取决于初始值v(0)和系数k。第4章线性判别分析4.2.4最小平方误差准则函数最小平方误差准则函数设由X=x1,x2,xN得到的规范化增广向量集合为z1,z2,zN,分类器设计的任务就在于寻找一个矢量v,满足:0 (1,2,)TiiNv z(4-72)满足上面的不等式组的矢量可能不止一个,若引入余量bi,用超平面:第4章线性判别分析0 (1,2,)TiibiNz v(4-73)代替zTiv0,则引入余量后的解区在原解区之内。将上式

31、写成矩阵形式即为 Z vb(4-74)其中12TTTNzzZz，Nbbb21b(4-75)第4章线性判别分析定义误差向量:eZ vb(4-76)定义平方误差准则函数:NiiiTsbJ122)()(zvev(4-77)Js(v)是一个非负函数,当式(4-74)有解时,Js(v)达到最小值0,此时的矢量v*满足:第4章线性判别分析*()0 (1,2,)TiibiNvz(4-78)v*能将所有样本正确分类。若v*不能使某个样本zj正确分类,即(v*)Tzjbj,则e2j=(vTzjbj)2。错分样本的结果是使Js(v)增大,因此,Js(v)越小越好,其最小值0为理想分类结果,实现所有样本的正确分类。

32、求解使Js(v)最小的v*有两种方法:梯度下降法和解析法。第4章线性判别分析1.梯度下降法梯度下降法对Js(v)求梯度()2()TsJvZZvb(4-78)相应地,梯度下降算法为(1)()()TkkkkvvZZvb其中:k为学习速率;初值v(0)可任意选取。第4章线性判别分析2.解析法解析法解析法得到的是伪逆解。令Js(v)=0得*TTZ ZvZ b(4-79)其中*1()TTvZ ZZ bZ b(4-80)ZTZ为(d+1)(d+1)方阵,一般是满秩的,因此有唯一解:1()TTZZ ZZ(4-81)是Z的左逆矩阵,Z的右逆矩阵定义为 1()TZZ Z Z(4-82)b的典型值为 T)1,1,

33、1(b第4章线性判别分析4.2.5决策树决策树决策树是模式识别中的一种有效的分类方法,对于解决多类或多峰问题非常方便。它的基本思想是利用多个判决准则将复杂的多类分类问题转化为若干个简单的分类问题。它是自上而下逐级处理的。第4章线性判别分析一般地,一个决策树由一个根节点、一组内节点和一组叶节点组成。决策树在内部节点进行特征比较,特征的不同取值对应于决策树的不同分支,在叶节点得到分类结论。一个决策树对应于特征空间的一种划分,即一种分类结果。除叶节点之外,每个节点仅有两个分支的决策树称为二叉决策树。第4章线性判别分析由它构成的分类器可以把一个复杂的多类别问题转化为多级多个两类问题来解决。图4-15所

34、示的就是一个二叉决策树,其中n1是根节点,n2是内节点,tj(j=1,2,3)是叶节点。这个决策树将特征空间划分为三个区域,分别对应类1、2、3。当n1对应特征取值为a1,n2对应特征取值为b2时,属于第二类2。第4章线性判别分析图4-15 决策数示意图第4章线性判别分析设计一个决策树关键要解决以下问题:合理安排树的节点和分支,构造合理的树结构;确定根节点和内节点使用的特征;在叶节点选择合适的判决准则。决策树有一些等价的网络表示形式,相应地存在不同的实现算法,这里仅介绍CLS学习算法和ID3算法。第4章线性判别分析1.CLS学习算法学习算法CLS学习算法是Hunt等人在1966年提出的,它是早

35、期的决策树学习算法。它的基本思想是从一个空决策树出发,通过添加新的节点来改善决策树的性能,直到该决策树将所有训练样本都正确分类。该算法的基本步骤如下:(1)假设决策树T的初始状态只包含一个根节点(X,Q),其中X为全体训练样本的集合,Q为全体特征的集合;第4章线性判别分析(2)若T的所有叶节点(X,Q)均满足X中的训练样本属于同一类或Q为空,则算法结束;(3)否则,选择一个不具备步骤(2)所述状态的叶节点(X,Q);(4)对于Q,按照一定规则选取特征b,若X被b的不同取值分为m个不相交的子集XI且1im,则得到m个分支,每个分支代表b的一个不同取值,从而得到m个新的叶节点(Xi,Q b),1i

36、m,转步骤(2)。第4章线性判别分析2.ID3算法算法1979年Quinlan提出了以信息熵的下降速度作为特征选取标准的ID3算法。设训练样本集为X,决策树对样本的划分为R=R1,R2,Rm,分别对应类1,2,m。假设属于第i类的训练样本为Ni,X中训练样本数为N,则第i类样本出现的概率为 第4章线性判别分析()iiNPN决策树对划分R的不确定性可以表示为(,)()log()iiH X RPP(4-83)简记为H(X)。在学习过程中,应使决策树对划分的不确定性逐渐减小。若选择特征b,在特征b取值为bj时得到b=bj条件下训练样本属于第i类的个数为Nij,则此时的概率为 第4章线性判别分析(|)

37、ijijNPbbN这时决策树对划分R的不确定性为(|)(|)log(|)jijijiH X bbPbbPbb(4-84)在选择特征b之后,根据b的不同取值得到的叶节点对于分类信息的信息熵为:(|)()(|)jjjH X bP bb H X bb(4-85)特征b对于分类提供的信息量为 第4章线性判别分析(;)()(|)I X bH XH X b(4-86)式(4-85)取值越小,则式(4-86)的值越大,说明选择b用于分类提供的信息越大,分类结果的不确定性越小。ID3算法就是每次选择使I(X;b)最大的特征用于分类。下面通过一个例子来说明该算法。表4-1给出了一组数据集合,它有四个属性:Out

38、look、Temperature、Humidity、Windy。数据集被分为两类N和P,请采用ID3算法构造分类决策树。第4章线性判别分析属性OutlookTemperatureHumidityWindy类1OvercastHotHighNotN2OvercastHotHighVeryN3OvercastHotHighMediumN4SunnyHotHighNotP5SunnyHotHighMediumP6RainMildHighNotN7RainMildHighMediumN8RainHotNormalNotP9RainCoolNormalMediumN10RainHotNormalVery

39、N11SunnyCoolNormalVeryP12SunnyCoolNormalMediumP13OvercastMildHighNotN14OvercastMildHighMediumN15OvercastCoolNormalNotP16OvercastCoolNormalMediumP17RainMildNormalNotN18RainMildNormalMediumN19OvercastMildNormalMediumP20OvercastMildNormalVeryP21SunnyMildHighVeryP22SunnyMildHighMediumP23SunnyHotNormalNo

40、tP24RainMildHighVeryN第4章线性判别分析解解由于初始时刻属于类N和类P的样本数均为12个,因此有 12121212()loglog124242424H X 其中,lb表示以2为底的对数。如果选取Outlook特征进行分类,根据式(4-85)可得9445581177(|)loglogloglog24999924888871166loglog2477770.5528H X Outlook第4章线性判别分析如果选取Temperature特征进行分类,则有 84444114477(|)loglogloglog248888241111 111154411loglog2455550.6

41、739H X Temperature如果选取Humidity特征进行分类,则有 第4章线性判别分析124488124488(|)loglogloglog241212121224121212120.9183H X Humidity如果选取Windy特征进行分类,则有 8444463333(|)loglogloglog248888246666105555loglog24101010101H X Windy第4章线性判别分析可以看出,H(X|Outlook)的值最小,Outlook能够提供最大信息量,所以选择Outlook作为分类特征。这样就将训练样本集分为三个子集,生成三个叶节点,对每个叶节点依次

42、利用上面的过程生成如图4-16所示的决策树。第4章线性判别分析图 4-16例4.5训练所得的决策树第4章线性判别分析4.3分段线性分类器分段线性分类器由上节讨论可知,线性分类器的分界面是一个超平面。当类与类之间不能用任何一个超平面实现划分时,类间的分界面应是一个超曲面。考虑到曲线可以由多个线段近似表达,曲面可以由多个平面逼近,因此,也可以用多个超平面近似表达超曲面,分段线性分类器正是基于这种思路而设计的一种分类器。第4章线性判别分析4.3.1分段线性分类器的定义分段线性分类器的定义线性判决函数只能解决线性可分问题,对于线性不可分问题,必须采用非线性判决函数。在各种非线性判决函数中,分段线性判决

43、函数是一种特殊的、相对简单的判决函数,它确定的决策面是由若干段超平面组成的,如图4-17所示,其中,H1和H2组成的决策面即为分段线性超平面。与一般的超曲面相比,这种决策面比较简单,又可以逼近多种形状的超曲面,具有很强的适应能力。第4章线性判别分析图 4-17两类非线性可分时可用多段超平面分开 第4章线性判别分析把属于类i的样本区域Ri分为li个两两不相交的子区,对每个子类定义一个线性判决函数:0()()(1,2,1,2,)llTliiiigwllimxwx(4-87)定义类i的判别函数:1,2,()max()(1,2,)iliillggimxx(4-88)判决准则为 若()max()jiig

44、gxx则xj(4-89)第4章线性判别分析称gi(x)(i=1,2,m)为分段线性判决函数,相应的分类器称为分段线性分类器。当类由多个子类构成时,其决策面方程是由各子类的判决函数确定的,若第i类的第n个子类和第j类的第k个子类相邻,则该段决策面方程为()()nkijggxx(4-90)其中,n1,2,li,k1,2,lj,li和lj分别表示第i类和第j类的子类数目。第4章线性判别分析4.3.2分段线性距离分类器分段线性距离分类器在4.2.1节中介绍的最小距离分类器,其判决函数为 221122xxx(4-91)即2211220 xxx(4-92)这时类间的决策面为 2221xx(4-93)它是两

45、类均值点连线的垂直平分面。第4章线性判别分析如果将这个概念推广到多个代表点的情形,考虑到当两类不能用一个超平面分开时,每类可以选多个代表点,两类之间的代表点对之间可构造一个垂直平分面,多个超平面的组合即可实现两类的划分。第4章线性判别分析我们来分析一下图4-18中给出的两类的划分问题,由图中可以看出两类都是多峰分布,将各类的均值作为代表点,采用最小距离分类器方法得到的分界面为,显然这种分类方法的错误率很大。如果我们将每类划分为多个子类,每个子类分别取一个代表点,利用最小距离分类器定义的判决函数,则可以得到图中折线所示的分段线性分界面,它是由多段超平面组成的,其中每一段都是最小距离分类器。这个结

46、果的错误率较小,效果较好。依此类推,可以定义分段线性距离分类器。第4章线性判别分析图 4-18分段线性距离分类器示意图第4章线性判别分析将类i的样本区域Ri分为li个子区:12iliiiiRRRR其中,1212,jjiiRRjj。用mli表示Rli中的均值向量,并以此作为该子区的代表点,确定判别函数:1,2,()miniliillgxxm(4-93)第4章线性判别分析则判决准则为 若)(min)(,2,1xximijgg，则xj(4-94)称这种分类器为分段线性距离分类器。应该注意,线性距离分类器使用的是马氏距离,分段线性距离分类器使用的则是欧几里德距离,由最小距离分类器的导出过程可知,仅当所

47、有子区的协方差阵相同且等于2I时,才具有较好的分类效果。第4章线性判别分析4.3.3分段线性分类器设计的一般考虑分段线性分类器设计的一般考虑设计分段线性分类器的前提条件是有一组已知类别的样本集,其关键在于解决以下两个问题:(1)根据样本集确定子类数目及各子类的划分;(2)利用样本集计算各子类判别函数的权向量和阈值权。根据已知条件的不同,可以分别采取不同的方法。已知条件可以分为三种,相应就有三类设计方法。第4章线性判别分析1.子类数目及各子类划分已知子类数目及各子类划分已知在这种条件下,分段线性分类器的设计比较简单,将每一子类看成独立的类,利用多类线性分类器的设计方法,求出每一子类的权向量和阈值

48、权。若第i类的子类数目为li,i=1,2,m,则把子类看成独立的类后,相当于l1+l2+lm类的线性分类器设计问题,判决准则为若,()max()ktijj tggxx，则xi(4-95)第4章线性判别分析2.子类数目已知子类数目已知,各类划分不知各类划分不知由于各类的划分未知,因此,分段线性分类器的设计不能一次成功,需要在确定权向量和阈值权的同时,确定相应的子类划分,错误修正法正是基于这种需求而提出的一种解决方法。设i类有li个子类,错误修正法的具体步骤如下:(1)确定初始权向量。任意给定类i的li个子类的初始增广权向量 第4章线性判别分析12(1),(1),(1)(1,2,)iliiivim

49、vv(4-96)(2)利用训练样本集通过迭代运算修改权向量,权向量的修改规则如下:若在第k次迭代时下式成立:1,2,()max()iTTtjljjjllkkvyvy(4-97)其中:yj为类j(j=1,2,m)中的样本;t、l为子类号;vlj(k)表示第j类的第l子类的增广权向量在第k次迭代时的值,且 第4章线性判别分析()()(1,2,1,2,)TTtjljjiikkij im llvyvy(4-98)则权向量组vli(k)(i=1,2,m;l=1,2,li)将yj正确分类,各权向量的值保持不变。反之,如果存在某个或几个子类,不满足上述条件,即()()()TTtjnjjikkijvyvy(4

50、-99)则yj被误分,按下述修正公式对权向量的值进行修正:第4章线性判别分析如果,()max()TTnjnjiii nkkvyvy则(1)()(1)()ttjjjknnjkiikkkkvvyvvy(4-100)其中,vtj(k)满足式(4-97)。k的选择应该使修正后的权值满足条件:()()()TTtjnjjikkijvyvy(4-101)第4章线性判别分析(3)重复步骤(2)的迭代过程,直至算法收敛或达到规定的时限(或迭代次数)为止。从理论上看,当样本集对于给定的子类数目能用分段线性判别函数完全分开时,算法将在有限步内收敛。收敛速度与初值的选择、k的选择有关,而初值的选择还没有成熟的理论指导