模式识别清华-课件第三章.docx

《模式识别清华-课件第三章.docx》由会员分享，可在线阅读，更多相关《模式识别清华-课件第三章.docx（11页珍藏版）》请在三一办公上搜索。

1、第三章非参数判别分类方法学习指南学习这一章最主要的是了解它在模式识别技术中所处的地位。前一章重点学习的贝叶斯决策具有理论指导的意义，同时也指明了根据统计参数分类决策的方向。沿这条路走就要设法获取样本统计分布的资料,要知道先验概率，类分布概率密度函数等。然而在样本数缺乏条件下要获取准确的统计分别也是困难的。这样一来人们考虑走另一条道路，即根据训练样本集提供的信息，直接进行分类器设计。这种方法绕过统计分布状况的分析，绕过参数估计这一环，而企图对特征空间实行划分，称为非参数判别分类法，即不依赖统计参数的分类法。这是当前模式识别中主要使用的方法，并且涉及到人工神经元网络与统计学习理论等多方面，是本门课

2、最核心的章节之一。非参数判别分类方法的核心是由训练样本集提供的信息直接确定决策域的划分方法。这里最重要的概念是分类器设计用种训练与学习的过程来实现。机器自动识别事物的能力通过训练学习过程来实现，其性能通过学习过程来提高，这是模式识别、人工神经元网络中最核心的内容。学习这一章要进一步体会模式识别中以确定准那么函数并实现优化的计算框架。由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非线性函数等。因此确定分界面方程，这包括选择函数类型与确定最正确参数两个局部。i般说来选择函数类型是由设计者确定的，但其参数确实定那么是通过一个学习过程来实现的，是一个叠代实现优化的过程。因此本章从最简单的函

3、数类型讲起，再扩展到非线性函数。同学们学习的重点要放在线性判别函数的根本内容上，然后再注意如何扩展到非线性函数的应用上去。该章的学习最好通过概念的反复推敲与思考，以加深对重要概念的理解，另一方面通过实验，亲自体验设计模式识别系统的完整过程，对学习才会更加真切。数学是模式识别中不可缺少的工具，希望大家学习时，遇到的数学方面的内容要通过再学习、复习等进一步掌握，如线性代数、矩阵的特征值分解与特征向量等概念的运用上起到很重要的作用。通过这门课学习加深对这些数学工具的理解与运用熟练程度是会终身受益的。对于数学推导理解程度的要求，会对增强同学分析问题解决问题的能力有好处。学习目的(1)通过本章学习掌握模

4、式识别中最重要的非参数判别分类法的原理(2)掌握机器自学习的原理，自学习功能已不仅在模式识别中应用，目前经常用机器学习这个词以涉及更为广泛的内容。(3)学习线性分类器的三种典型算法，这三种算法各自形成体系，分别形成了传统模式识别、人工神经元网络以及统计学习理论(4)用近邻法进行分类(5)通过相应数学工具的运用进一步提高运用数学的本领本章重点(1)非参数判别分类器的根本原理，与参数判别分类方法的比拟(2)线性分类器的三种典型方法一一以FiSher准那么为代表的传统模式识别方法，以感知准那么函数为代表的机器自学习方法，以及支持向量机代表的统计学习理论。(3)近邻法的工作原理及其改良(4)线性分类器

5、扩展到非线性分类器，两类别分类方法与多类别分类方法本章难点(DFiSher准那么函数，其中用到向量点积，带约束条件的拉格朗日乘子法以及矩阵的特征值、特征向量等数学工具。要求对这些数学工具较深理解。(2)感知器准那么函数提出利用错误提供信息实现叠代修正的学习原理(3)支持向量机方法设计约束条件为不等式的极值优化问题(4)三种不同典型方法的优缺点比拟(5)近邻法的改良知识点非参数判别分类方法的基本原理一一有监督学习方法近邻法，线性分类器改进的近邻法U非线性分类器的扩展七 分段线性七特征映射方法实现非 *线性分类器t课前思考题：(1)机器能否像人类一样通过例证教育认知事物，修正观念中的错误的成分？(

6、2)机器学习过程中有教师吗？谁是教师？(3)什么叫线性分类器？按照基于最小错误率贝叶斯决策,什么条件下才能用线性分 类器？在上一章中我们讨论了贝叶斯决策理论和统计判别方法。从原理上说贝叶斯决策理论采用了在d维特征空间中样本分布的最一般描述方式，即统计分布来描述，并且采用分类器中最重要的指标一 错误率作为产生判别函数和决策面的依据，因此它给出了最一般情况下适用的“最优”分类器设计方法, 对各种不同的分类器设计技术在理论上都有指导意义。但是直接使用贝叶斯决策理论需要首先得到有关 样本总体分布的知识，具体说来包括各类先验概率P(3 J及类条件概率密度函数，从而可以计算出样 本的后验概率P(3X),并

7、以此作为产生判别函数的必要数据，设计出相应的判别函数与决策面。 3. 2. 1在线性判别函数的根本概念设样本d维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成g(X)=WX+W0(3-1)其中而3。是一个常数，称为阈值权.相应的决策规则可表示成,g(X)o,g(X)V0,或 X)= 0,则决策X1则决策Xe2可将其任意分类或拒绝.g(X)=O就是相应的决策面方程,在线性判别函数条件下它对应d维空间的一个超平面.WTX+Wn=O(3-3)为了说明向量W的意义，我们假设在该决策平面上有两个特征向量X与X2,则应有WX1+w0=WX2+w0Wt(X1-X2)=O(3-4)其中(Xl-X

8、2)也是一个向量.(3-4)式表明向量H与该平面上任两点组成的向量(XI-X2)正交，因此W就是该超平面的法线向量：这就是向量4的几何意义。而晨X)也就是d维空间中任一点X到该决策面距W0 网表示商的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。至于Wo则体现该决策面在特征空间中的位置,当WO=O时，该决策面过特征空间坐标系原点，而W。时，则了坐标原点到该决策面的距离.有的同学可能对(3-1)公式表示线性判别函数不太理解，这可从线性方程的表示法说起，设二维空间Wo。一直线方程表示为：w2+wll+w0x其中Wl和*2分别是Xi和X2的系数，WO是直线方程的参数项，由于Xi和

9、是一个向量的两个分量W=(w1,此)匚则W2X2+w就是这两个向量的点积，表示成(3-3)式。另外我们也知道一个线性方程在3.2.2广义线性判别数线性判别函数是形式最为简单的判别函数,但是它不能用于稍复杂一些的情况，例如,欲设计这样一个一维样本的分类器,使其性能为:(3-5)Xa决策X1bXO如果Y则aYO.讨论完了问题的提法后，下一步要解决如何找到这样一个合适的&,感知准则函数方法的思路是：先随意找一个初始向量M,写作&(CI)，然后用训练样本集中的每个样本来计算。一旦发现有的Y使aTo,则只要a(k+l)=4K)+pkY,Pk为正，(步长系数)则必有a(k+l)TY=(k)TY+pi(YT

10、Ya(k)TY，就有趋势儆到使a(k+)To.当然，修改后的a(k+l)还可以使某些Y出现a(k+l)T0,X1g(X)=a-y03=1,N反之，若发现出现了刀；0的情况，则意味着这些样本尸；被该决策面错误分类.(3-38)式的增广样本向量又称为规范化增广样本向量：图3.5(b)表示用规范化增广样本向量时正确分类的情况，如果对一个样本集1总能找到一个增广权向量,对该样本集所有样本实现正确分类，则这种情况称为具有线性可分性。以下我们只讨论线性可分性的情况,(a)未规范化(b)规范化(3-39)实际上是一组联立不等式，N个样本共有N个不等式，而每个不等式都决定了一个相应的增广权向量所应在的区域，而

11、N个样本所对应的增广权向量Z所在区域之交迭空间被称为解区，在解区内的任一向量Z能使所有样本得到正确划分。图35(a)及(b)表明了由四个样本得到的解区子空间。设计分类器只需在此解区内选择一合适的向量，作为增广权向量为了使权向量不致选在解区的边界上，一般设有一余量b,使Tyj2bO，以确保增广权向量处在解区空间的内部。3.2.6多类问题3.3非线性判别函数3.3.1非线性判别函数与分段线性判别函数对实际的模式识别问题来说，各类在特征空间中的分布往往比较复杂，因此无法用线性分类函数得到好的效果。这就必须使用非线性的分类方法。在对待非线性判别分类问题，提到的三种不同的方法。传统的模式识别技术，则侧重

12、于使用分段线性判别函数，因此基本上是沿用了线性判别函数的方法e这在3.3.1到3.3.4中讨论。3.3.2的错误修正法是对感知准则函数的扩展，但人工神经元网络如多层感知器等网络能够实用非常复杂的非线性分类，以及非线性函数拟和，非线性映射等，这将在人工神经元网络这一章讨论。支持向量机则提出了一种基于特征映射的方法，也就是使用某种映射，使本来在原特征空间必须使用非线性分类技术才能解决的问题,映射到一个新的空间以后，使线性分类技术能维续使用。3.3.1非线性判别函数与分段线性判别函数I：线性判别函数II：分段线性判别函数III：二次判别函数图3.10由于样本在特征空间分布的复杂性，许多情况下采用线性

13、判别函数不能取得满意的分类效果，例如对图3.10所示两类物体在二维特征空间的分布，采用线性判别函数就无法取得满意的分类效果，在这种情况下，可以采用分段线性判别或二次函数判别等方法，效果就会好得多，与一般超曲面相比，分段线性判别函数是最为简单的形式，是非线性判别函数情况下最为常用的形式。除此之外二次判别函数是除线性及分段线性外最简单的形式，以下只讨论有关分段线性判别函数设计中的一些基本问题a与线性判别函数相比，分段线性判别函数设计中首先要解决的问题是分段线性判别函数的分段段数问题，显然这是一个与样本集分布有关的问题。分段段数过少，就如图3.10的例子中用一个线性判别函数(段数为1)的情况，其分类

14、效果必然要差；但段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策的计算量，在有些实际的分类问题中，同一类样本可以用若干个子类来描述，这些子类的数目就可作为确定分段段数的依据，但多数情况下样本分布及合适子类划分并不知道，则往往需要采用一种聚类的方法(在第五章中讨论)，设法将样本划分成相对密集的子类，然后用各种方法设计各段判别函数。由于在后面章节要讨论聚类问题，这一章主要讨论在样本分布及子类划分大体已定的情况下，设计分段线性判别函数的问题,着重讨论几种典型的设计原理。分段线性判别函数的一般形式可定义为：g-(X)=IViirX+wf0,1=1,2,.,加/=1,.,c(3-47)其中g；(

15、X)表示第i类第1段线性判别函数，Ii为i类所具有的判别函数个数，粕与WM分别是第1段的权向量与阈值权。相应的判别规则是：如果g/(X)=maxgj(X)(3-47)其中giW=11axg；(X)则决策XE(0j(3-48)gi(X)=maxg；(X)则称为第i类的判别函数，J三1.4至于分类的决策面方程取决于相邻的决策域，如第i类的第n个子类与第j类的第m个子类相邻，则由它们共同决定的决策面方程为g*X)=gKX)(3-49)当每一类的样本数据在特征空间中的分布呈复杂修正时，使用线性判别函数就会产生很差的效果，如果能将它们分割成子集，而每个子集在空间聚集成团，那么子集与子集的线性划分就可以取

16、得比较好的效果，因此分段线性判别的主要问题是如何对数据划分成子集的问题，这是第五章着重讨论的内容。3.3.2 基于距离的分段线性判别函数3.3.3 错误修正算法3. 3.4局部训练法 3.4 3.4近邻法3.4.2 近邻法错误率分析3.4.3 改良的近邻法 3.5 支持向量机本章小结一、参数判别分类方法与非参数判别分类方法的区别二、非参数分类判别方法的根本做法三、决策面方程的显式表示和隐式表示四、基于相似度的分类判别方法五、Fisher准那么六、感知准那么函数方法七、近邻法八、支持向量机问答第5题答：按近邻法，对任意两个由不同类别的训练样本构成的样本对，如果它们有可能成为测试样本的近邻，那么它们构成一组最小距离分类器，它们之间的中垂面就是分界面，因此由三个A类与四个B类训练样本可能构成的分界面最大数量为3X4=12。实际分界面如下列图所示，由9条线段构成：