非参数判别分类方法(I)

《非参数判别分类方法(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第三章非参数判别分类方法非参数判别分类方法是当前模式识别中主要使用的方法，并且涉及到人工神经元网络与统计学习理论等多方面，是本门课最核心的章节之一。学习指南非参数判别分类方法的核心是由训练样本集提供的信息直接确定决策域的划分方法。本章最重要的概念是分类器设计用一种训练与学习的过程来实现。机器自动识别事物的能力通过训练学习过程来实现，其性能通过学习过程来提高，这是模式识别、人工神经元网络中最核心的内容。7/18/20211中国矿业大学计算机科学与技术学院 学习这一章要进一步体会模式识别中确定准则函数并实现优化的计算框架。由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非线性函数等。因此确定分界面方程包括选择函数类型与确定最佳参数两个部分。一般说来选择函数类型是由设计者确定的，但其参数的确定则是通过一个学习过程来实现的，是一个叠代实现优化的过程。因此本章从最简单的函数类型讲起，再扩展到非线性函数。7/18/20212中国矿业大学计算机科学与技术学院 数学是模式识别中不可缺少的工具，希望大家学习时，遇到的数学方面的内容要通过再学习、复习等进一步掌握，如线性代数、矩阵的特征值分解与特征向量等概念的运用上起到很重要的作用。通过这门课学习，加深对这些数学工具的理解与运用熟练程度是会终身受益的。对于数学推导理解程度的要求，对增强同学分析问题解决问题的能力有好处。7/18/20213中国矿业大学计算机科学与技术学院 通过本章学习掌握模式识别中最重要的非参数判别分类法的原理。学习目的掌握机器自学习的原理，自学习功能已不仅在模式识别中应用，目前经常用的机器学习这个词已涉及更为广泛的内容。学习线性分类器的三种典型算法，这三种算法各自形成体系，分别形成了传统模式识别、人工神经元网络以及统计学习理论。用近邻法进行分类。通过相应数学工具的运用进一步提高运用数学的本领。7/18/20214中国矿业大学计算机科学与技术学院 本章重点1、非参数判别分类器的基本原理，与参数判别分类方法的比较。2、线性分类器的三种典型方法——以Fisher准则为代表的传统模式识别方法，以感知准则函数为代表的机器自学习方法，以及支持向量机代表的统计学习理论。3、近邻法的工作原理及其改进。4、线性分类器扩展到非线性分类器，两类别分类方法与多类别分类方法。7/18/20215中国矿业大学计算机科学与技术学院 1、Fisher准则函数，其中用到向量点积，带约束条件的拉格朗日乘子法以及矩阵的特征值、特征向量等数学工具。要求对这些数学工具较深理解。2、感知器准则函数提出利用错误提供信息实现叠代修正的学习原理。3、支持向量机方法设计约束条件为不等式的极值优化问题。本章难点4、三种不同典型方法的优缺点比较。5、近邻法的改进。7/18/20216中国矿业大学计算机科学与技术学院 1、机器能否像人类一样通过例证教育认知事物，修正观念中的错误的成分?2、机器学习过程中有教师吗？谁是教师？3、什么叫线性分类器？按照基于最小错误率贝叶斯决策，什么条件下才能用线性分类器？课前思考题7/18/20217中国矿业大学计算机科学与技术学院 §3.1引言按贝叶斯决策理论设计分类器的步骤非参数判别分类方法设计分类器的步骤7/18/20218中国矿业大学计算机科学与技术学院 非参数判别分类方法的两个过程设计者确定使用什么典型的分类决策方法利用训练样本集提供的信息确定这些函数中的参数7/18/20219中国矿业大学计算机科学与技术学院 线性判别函数的一般形式3.1.1线性判别函数的基本概念其中w0是个常数，称为阈值权，x是维特征向量，w称为权向量，分别表示为：7/18/202110中国矿业大学计算机科学与技术学院 在线性判别函数条件下它对应d维空间的一个超平面。相应的决策规则决策面方程7/18/202111中国矿业大学计算机科学与技术学院 向量W的意义假设在该决策平面上有两个特征向量X1与X2，则应有上式表明向量W与该平面上任两点组成的向量(X1-X2)正交，因此W就是该超平面的法线向量。w0则体现该决策面在特征空间中的位置，当时，该决策面过特征空间坐标系原点，而时，则表示了坐标原点到该决策面的距离。7/18/202112中国矿业大学计算机科学与技术学院 向量W的意义7/18/202113中国矿业大学计算机科学与技术学院 3.1.2广义线性判别函数线性判别函数是形式最为简单的判别函数，但是它不能用于稍复杂一些的情况，例如，欲设计这样一个一维样本的分类器，使其性能为：相应的决策规则为：设计一判别函数:7/18/202114中国矿业大学计算机科学与技术学院 广义线性判别函数基本思想：g(X)不再是x的线性函数，而是一个二次函数，此时通过选择一种映射X→Y，即将原样本特征向量X映射成另一向量Y，从而把二次函数转换成线性函数。7/18/202115中国矿业大学计算机科学与技术学院 则判别函数g(x)又可表示成：如果采用映射X→Y，使g(x)为广义线性判别函数，a称为广义权向量。7/18/202116中国矿业大学计算机科学与技术学院 其中写成另一种形式Y为增广样本向量，a为增广权向量。7/18/202117中国矿业大学计算机科学与技术学院 例：一个一维特征空间的分类器其决策面方程为：在一维空间中为一个点，经齐次简化后可得：7/18/202118中国矿业大学计算机科学与技术学院 思考如果在两维空间存在一条不过原点的直线采用增广向量形式：问题：在增加一维的三维空间中，aTY=0表示的是什么呢？答：一个过原点的平面，方程为ay1+by2+cy3=07/18/202119中国矿业大学计算机科学与技术学院 3.1.3设计线性分类器的主要步骤线性分类器设计任务是在给定样本集条件下，确定线性判别函数的各项系数，w0,w1,……,wd以期对待测样本进行分类时，能满足相应的准则函数J为最优的要求。可见此技术的关键问题是确定所需的准则函数，然后用最优化技术确定准则函数的极值解W*及W0*,或增广权向量.7/18/202120中国矿业大学计算机科学与技术学院 3.1.3设计线性分类器的主要步骤（1）按需要确定一准则函数J。（2）确定准则函数J达到极值时W*，w0*和a*的具体数值，从而确定判别函数，完成分类器设计。得到线性判别函数：这种方法的具体过程可大致分为：7/18/202121中国矿业大学计算机科学与技术学院 3.2Fisher线性判别Fisher线性判别函数是研究线性判别函数中最有影响的方法之一。对线性判别函数的研究就是从R.A.Fisher在1936年发表的论文开始的。7/18/202122中国矿业大学计算机科学与技术学院 1.Fisher准则函数基本思想设计线性分类器首先要确定准则函数，然后再利用训练样本集确定该分类器的参数，以求使所确定的准则达到最佳。在使用线性分类器时，样本的分类由其判别函数值决定，而每个样本的判别函数值是其各分量的线性加权和再加上一阈值w0。如果向量W的幅度为单位长度，则线性加权和又可看作各样本向量在向量W上的投影。显然样本集中向量投影的分布情况与所选择的W向量有关。7/18/202123中国矿业大学计算机科学与技术学院 对线性方程的理解：二维空间中一条直线的任何一点到空间某一单位向量的投影值相同，换句话说，该直线是到这个向量投影值相同的点的集合。如果在二维空间中一条直线能将两类样本分开，或者错分类很少，则同一类别样本数据在该直线的单位法向量上的投影的绝大多数都应该超过某一值。Fisher准则的基本原理，即向量W的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。7/18/202124中国矿业大学计算机科学与技术学院 样本在d维X空间的一些描述量（1）各类样本均值向量（2）样本类内离散度矩阵与总类内离散度矩阵（3）样本类间离散度矩阵7/18/202125中国矿业大学计算机科学与技术学院 样本在一维Y空间的一些描述量（1）各类样本均值（2）样本类内离散度矩阵与总类内离散度矩阵7/18/202126中国矿业大学计算机科学与技术学院 Fisher准则的函数形式根据Fisher选择投影方向W的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求，因此，用以评价投影方向W的函数为：进一步化为W显函数的形式：7/18/202127中国矿业大学计算机科学与技术学院 同样也可推出与W的关系：Fisher准则函数为：7/18/202128中国矿业大学计算机科学与技术学院 2.最佳W值的确定最佳W值的确定实际上就是对准则函数求取其取极大值时的W*设计一拉格朗日函数：其中λ为拉格朗日乘子，按拉格朗日算法对上式求对W的偏导数，且令其在W=W*时为零，得：7/18/202129中国矿业大学计算机科学与技术学院 实际上我们关心的只是向量W*的方向，其数值大小对分类器没有影响。因此在忽略了数值因子R/λ后，可得:矩阵非奇异即该矩阵可逆，上式是典型的求矩阵特征值问题。其中                    是一个数量，可用数值R表示，则上式可写成：7/18/202130中国矿业大学计算机科学与技术学院 最佳法线向量使Fisher准则函数达极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向，该向量W*的各分量值是对原d维特征向量求加权和的权值。该式与在两类正态分布且具有相同的协方差矩阵Σ时，按最小错误率的贝叶斯决策得到的结果是一致的。表明Fisher准则是合理的。7/18/202131中国矿业大学计算机科学与技术学院 3.判别函数的确定判别函数中的另一项w0尚未确定，一般可采用以下几种方法确定w0如:按以下规则分类7/18/202132中国矿业大学计算机科学与技术学院