第三章 线性判别分析_非参数判别分类方法-第二次课

第3章线性判别分析第三章线性判别分析——非参数判别分类方法第3章线性判别分析第3章线性判别分析本章的思路：利用样本直接设计分类器,可以避开各类的概率密度函数的估计,其基本思想就是设定一组判别函数,并利用样本直接计算判决函数中的有关参数。第3章线性判别分析本章内容3.1线性判别函数3.2线性分类器3.3分段线性分类器3.4近邻分类器总结习题第3章线性判别分析3.1.1线性判别函数的形式如下:0(),1,2,,Tiiigwimxwx其中:wi称为权向量;wi0称为阈值权。wi和wi0的值需根据样本集来确定。线性分类器设计的关键在于确定权向量wi和阈值权wi0。3.1线性判别函数第3章线性判别分析1.两类问题的讨论在两类情况下,判决函数具有简单的形式:若,则判决（或）ω2；若,则判决（或）ω１；若,则不作判决或作任意判决,即可判成ω１、ω2中的任意一类。)()(21xxgg)()(21xxgg)()(21xxgg1x2x第3章线性判别分析)()(21xxgg两类判决区域的分界面为011220()0Tddgwwxwxwxwxwx其几何意义为d维欧几里德空间中的一个超平面。第3章线性判别分析(1)w是超平面的法向量。对于两类分类问题,线性判决函数的几何意义在于利用一个超平面实现对特征空间Rd的划分。若以H表示超平面,则对H上的任意两点x1、x2有110()0Tgwxwx220()0Tgwxwx0)(21xxwTw和H上任一向量正交,即w是超平面H的法向量。超平面示意图第3章线性判别分析如果取最大判决,)()(21xxgg1x2xw指向R1,R1中的点在H的正侧。R2中的点在H的负侧。)()(21xxgg第3章线性判别分析wx)(grg(x)是x到超平面距离的一种代数距离。(2)当x=0时,g(x)=w0,w00wr若w00,则原点在超平面的正侧;若w00,则原点在超平面的负侧;若w0=0,则超平面通过原点。第3章线性判别分析结论：对于两类情形,利用线性函数进行分类,实质上就是用一个超平面H把Rd分成两个决策区域；H的方向由权向量w确定,它的位置由阈值权w0确定；判别函数g(x)正比于x点到H的代数距离；当x在H的正侧时,g(x)0;在负侧时,g(x)0。第3章线性判别分析2.所谓多类问题,是指类别数m≥3的情形。多类情况下可以按下述三种方法进行划分。(1)任意两个模式类之间分别用单个超平面分开。对于m类中的任意两类:ωi、ωj,i≠j,可以确定一个超平面Hij,能把ωi和ωj两类分开,两类各占Hij的一侧。显然,对于m类的判决问题,最多需要确定的超)1(212mmCm第3章线性判别分析三类问题的情况Hij的方程为0()Tijijijgwxwx()()jiijggxx其中,ij,i,j=1,2,…,m。gij(x)判决准则为：0()(,1,2,,)0iijjgijmxxx对于3类问题,可用3个超平面:g12(x)=0,g13(x)=0和g23(x)=0把ω1、ω2、ω3第3章线性判别分析【例】一个三类问题,三个判决函数为21231132112)(3)(5)(xxgxgxxgxxx请画出各类判决区域,并判断x=(x1,x2)T=(4,3)T属于哪一类。解各类的判决区域如图所示,在三条分界线相交组成的三角形区域内的样本无法判决所属类别,该区域称为不确定区域(IR)。第3章线性判别分析对于x=(x1,x2)T=(4,3)T,代入判决函数可得1)(,1)(,2)(231312xxxggg所以判断x∈ω3。21231132112)(3)(5)(xxgxgxxgxxx第3章线性判别分析(2)每一模式类与其他模式类之间用单个超平面分开。对于m类的判决问题,可以确定m个超平面,它的判决函数为0()Tiiigwxwxgi(x)判决准则为0()(1,2,,)0iiigimxxx若,使gk(x)0,gj(x)0(j≠k,j∈{1,2,…,m}),则判断x∈ωk。{1,2,,}km第3章线性判别分析此时特征空间中还可能存在不确定区域,如图中g1(x)0,g2(x)0,g3(x)0确定的区域,在这个区域中的样本不属于任何一类。图中每一类都用一个简单的直线将它与其他模式类分开,例如x∈ω1的样本,同时满足下面三个条件0)(1xg0)(2xg0)(3xg,,单个的g1(x)0条件只能区分属于ω1和不属于ω1。第3章线性判别分析【例】一个三类问题,三个判决函数为请画出各类判决区域,并判断x=(x1,x2)T=(6,5)T属于哪一类。解各类的判决区域如图所示,IR1、IR2、IR3、IR4区域内样本无法分类。11221232()()5()5gxxgxxgxxxx1第3章线性判别分析对于x=(x1,x2)T=(6,5)T,代入判决函数可得g1(x)=－1,g2(x)=6,g3(x)=－4,所以x∈ω2。11221232()()5()5gxxgxxgxxxx1第3章线性判别分析每一类具有一个判决函数的情况(3)每一模式类都有一个判别函数。对于m类的判决问题,可以确定m个超平面,它的判决函数0()Tiiigwxwx判决准则为,则x∈ωi。()max(())ijjggxx对于前面两种情况中的不确定区域,由于不确定区域内任何两类的判别函数值不相等,按最大判决思想,可以做出类别判决,因此这种情况下不存在不确定区域。第3章线性判别分析【例】一个三类问题,三个判决函数为23212211)(1)()(xgxxgxxgxxx请画出各类判决区域,并判断x=(x1,x2)T=(1,1)T属于哪一类。解各类的判决区域如图所示,分别计算得g1(x)=0,g2(x)=1,g3(x)=－1,因为g2(x)g3(x),g2(x)g1(x),所以x∈ω2。第3章线性判别分析3.1.2一维特征空间中非线性可分图示第3章线性判别分析决策区域•ω1：(－∞,a)和(b,+∞)•ω2：(a,b)建立一个二次函数g(x)=(x－a)(x－b)=c0+c1x+c2x2对应的决策规则210)(0)(xxgxxg第3章线性判别分析g(x)=(x－a)(x－b)=c0+c1x+c2x2第3章线性判别分析任何形式的高次判别函数都可转化成线性判别函数处理。譬如将非线性函数g(x)用级数展开,并截取其有限项,使之成为高次多项式,然后转化成广义线性判别函数。第3章线性判别分析对于二次判决函数didjjiijdiiixxwxwwg1110)(x有一种特殊的映射方法,将x增广至1211dxyxxx0102wd并将g(x)中的向量w和w0统一表示成T01()diiigxwwxvy则线性判别函数g(x)可以表示成这是广义线性判别函数的一个特例。y=(1,x)T被称为增广样本向量,v称为增广权向量。第3章线性判别分析设计线性分类器,是指所用的判别函数、分界面方程的类型已选定为线性类型,主要的设计任务是确定线性方程的两个参数,一个是权向量w,另一个是阈值w0。使所设计的线性分类器在性能上要满足一定的要求,这种要求通过一种准则来体现,并且要表示成一种准则函数,以便能通过将准则函数值优化的方法确定w和w0。3.1.30)(wgTxwx设计线性判别函数的任务就是在一定条件下,寻找最好的w和w0,其关键在于最优准则以及相应的求解方法。第3章线性判别分析(2)确定一个准则函数J,要求满足以下两个条件:①J是样本集、w和w0的函数;②J的值反映分类器性能,它的极值对应于“最好”的决策。(3)用最优化技术求解准则函数,得到极值点对应的w*和w*0。(1)选择样本集z={x1,x2,…,xN}。样本集中的样本来自两类且类别已知。当准则函数J的求解比较困难,不能得到全局最优解或是求全局最优结果比较困难时,往往通过求局部最优解（次优解）来降低求解难度,或者用计算解代替解析解。第3章线性判别分析习题1.对于线性判决函数:22)(21xxgx(1)将判别函数写成g(x)=wTx+w0的形式,画出H:g(x)=0的几何图形,标出权向量并确定决策区域R1和R2。(2)化成增广权向量和增广向量的形式:g(x)=vTy。