非参数判别分类方法3.1-3.2.ppt

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