《第四章 线性判别函数精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章 线性判别函数精选文档.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 线性判别函数本讲稿第一页，共三十二页1.按贝叶斯决策理论设计分类器的步骤 这种方法跳过了统计分布的参数估计，没有使用统计参数作为依据，因此称为非参数判别分类方法。而以贝叶斯决策方法为基础的方法则称为参数判别方法。2.获取统计分布及其参数统计分布及其参数这部分是很困难的，实际问题中并不一定具备获取准确统计分布的条件，因此将模式识别的设计过程，主要是判别函数、决策面方程的确定过程改成第四章 线性判别函数4.1 4.1 引言引言本讲稿第二页，共三十二页n按照基于统计参数的决策分类方法，判别函数及决策面方程的类别确定是由样本分布规律决定的，例如，符合某种条件就可使用线性分类器。n利用样本集直接
2、设计分类器的基本思想：q给定某个判别函数类，且假定判别函数的参数形式已知q用训练的方法来估计判别函数的参数值q分类决策n在非参数判别方法的设计中，使用什么典型的分类决策方法要预先由设计者确定，然后利用训练样本集提供的信息进行训练与学习，从而确定这些函数中的参数。这是参数与非参数判别方法的一个重要不同点。4.1 引言本讲稿第三页，共三十二页n n问题描述：问题描述：4.1 引言本讲稿第四页，共三十二页n例如下图：三类的分类问题，它们的边界线就是一个判别函数。4.1 引言本讲稿第五页，共三十二页n判别函数包含两类：q一类 是线性判别函数：n线性判别函数n广义线性判别函数q（所谓广义线性判别函数就是
3、把非线性判别函数映射到另外一个空间变成线性判别函数）n分段线性判别函数q另一类是非线性判别函数n线性分类器的三种典型方法q以Fisher准则为代表的传统模式识别方法，q以感知准则函数为代表的机器自学习方法，q以支持向量机代表的小样本学习理论。n分段线性判别函数：近邻法 这种方法主要依据同类物体在特征空间具有聚类特性的原理。同类物体由于其性质相近，它们在特征空间中应具有聚类的现象，因此可以利用这种性质产生分类决策的规则。4.1 引言本讲稿第六页，共三十二页4.1 引言本讲稿第七页，共三十二页4.2 4.2 线性判别函数线性判别函数n n线性判别函数：线性判别函数：x的各个分量的线性函数或以x为自
4、变量的某些函数的线性函数。n对于c类问题：利用样本集估计参数利用样本集估计参数wi和和wi0，并把未知样本，并把未知样本x归到具有最大判别函数值的类别中去。归到具有最大判别函数值的类别中去。第四章 线性判别函数本讲稿第八页，共三十二页线性判别函数的基本概念线性判别函数的基本概念设样本设样本d维特征空间中描述，则维特征空间中描述，则两类别问题两类别问题中线性判别函数的一中线性判别函数的一般形式可表示成般形式可表示成其中其中w0是一个常数，称为阈值权。相应的决策规则可表示成是一个常数，称为阈值权。相应的决策规则可表示成 g(x)0就是相应的决策面方程，在线性判别函数条件下它对应就是相应的决策面方程
5、，在线性判别函数条件下它对应d维空间的一个超平面。维空间的一个超平面。4.2 线性判别函数本讲稿第九页，共三十二页线性判别函数的基本概念线性判别函数的基本概念n 至于至于w w0 0则体现该决策面在特征空间中的位置则体现该决策面在特征空间中的位置则体现该决策面在特征空间中的位置则体现该决策面在特征空间中的位置，当，当w0=0时，该时，该决策面过特征空间坐标系原点，而决策面过特征空间坐标系原点，而 时，则时，则 表示了坐表示了坐标原点到该决策面的距离。标原点到该决策面的距离。为了说明向量为了说明向量w的意义，我们假设在该决策平面上有两个特征向的意义，我们假设在该决策平面上有两个特征向量量x1与与
6、x2，则应有，则应有其中其中(x1-x2)也是一个向量也是一个向量n 而而g(x)也就是也就是d维空间中任一点维空间中任一点x到该决策面距离的代数度量，到该决策面距离的代数度量，该决策平该决策平面将这两类样本按其面将这两类样本按其到该面距离的正负号到该面距离的正负号到该面距离的正负号到该面距离的正负号确定其类别。确定其类别。n 上上式表明向量式表明向量w与该平面上任两点组成的向量与该平面上任两点组成的向量(x1-x2)正交，因此正交，因此w就是就是该超平面的该超平面的法向量法向量法向量法向量。这就是向量。这就是向量w的几何意义。的几何意义。4.2 线性判别函数本讲稿第十页，共三十二页线性判别函
7、数的几何意义线性判别函数的几何意义令令n决策面(decision boundary)H方程：g(x)=0n向量w是决策面H的法向量ng(x)是点x到决策面H的距离的一种代数度量x1x2wxxprH:g=04.2 线性判别函数本讲稿第十一页，共三十二页x1x2wxxprH:g=0本讲稿第十二页，共三十二页线性判别函数的几何意义线性判别函数的几何意义令令4.2 线性判别函数本讲稿第十三页，共三十二页线性分类器的设计步骤：线性分类器的设计步骤：n给定样本集X，确定线性判别函数 的各项系数w和w0。步骤：步骤：q收集一组具有类别标志的样本收集一组具有类别标志的样本X=x1,x2,xNq按需要确定一准则
8、函数按需要确定一准则函数J，其值反映分类器的性能，其极，其值反映分类器的性能，其极值解对应于值解对应于“最好最好”的决策。的决策。q用最优化技术求准则函数用最优化技术求准则函数J的极值解的极值解w*和和w0*，从而确定，从而确定判别函数，完成分类器设计。判别函数，完成分类器设计。n对于未知样本x，计算g(x)，判断其类别。4.2 线性判别函数本讲稿第十四页，共三十二页 换一个方式说：换一个方式说：设计线性分类器，是指所用的判别函数、分界面方程的类设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方型已选定为线性类型，因此主要的设计任务是确定线性方
9、程的两个参数，一个是权向量程的两个参数，一个是权向量w，另一个是阈值，另一个是阈值w0。为了使所设计的线性分类器在性能上要满足一定的要求，这种为了使所设计的线性分类器在性能上要满足一定的要求，这种要求通过一种准则来体现，并且要表示成一种准则函数，以便要求通过一种准则来体现，并且要表示成一种准则函数，以便能通过将准则函数值优化的方法确定能通过将准则函数值优化的方法确定w与与w0。4.2 线性判别函数本讲稿第十五页，共三十二页4.3 4.3 FisherFisher线性判别线性判别nFisher线性判别函数是研究线性判别函数中最线性判别函数是研究线性判别函数中最有影响的方法之一。对线性判别函数的研
10、究就有影响的方法之一。对线性判别函数的研究就是从是从R.A.Fisher在在1936年发表的论文开始的。年发表的论文开始的。第四章 线性判别函数本讲稿第十六页，共三十二页n首先要首先要确定准则函数确定准则函数；n然后再利用训练样本集确定该然后再利用训练样本集确定该分类器的参数分类器的参数，以求使所确定的准则，以求使所确定的准则达到最佳。达到最佳。n在使用线性分类器时，样本的分类由其判别函数值决定，而每个在使用线性分类器时，样本的分类由其判别函数值决定，而每个样本的判别函数值是其各分量的线性加权和再加上一阈值样本的判别函数值是其各分量的线性加权和再加上一阈值w0 0。设计线性分类器：设计线性分类
11、器：n如果我们只考虑各分量的线性加权和，则它是各样本向量与向量如果我们只考虑各分量的线性加权和，则它是各样本向量与向量w的的向量点积。向量点积。4.3 Fisher线性判别本讲稿第十七页，共三十二页w(y)wy1y2x2x112现在讨论通过映射投影来降低维数的方法。把X空间各点投影到Y空间得一直线上，维数由2维降为一维。若适当选择w的方向，可以使二类分开。下面我们从数学上寻找最好的投影方向，即寻找最好的变换向寻找最好的变换向寻找最好的变换向寻找最好的变换向量量量量w w的问题。4.3 Fisher线性判别本讲稿第十八页，共三十二页FisherFisher准则的基本原理准则的基本原理n Fish
12、er Fisher准则的基本原理，就是要准则的基本原理，就是要找到一个最合适的投影轴，找到一个最合适的投影轴，找到一个最合适的投影轴，找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果使两类样本在该轴上投影的交迭部分最少，从而使分类效果使两类样本在该轴上投影的交迭部分最少，从而使分类效果使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。为最佳。为最佳。为最佳。两类样本投影的均值之差尽可能大些，而使类内样本的离两类样本投影的均值之差尽可能大些，而使类内样本的离两类样本投影的均值之差尽可能大些，而使类内样本的离两类样本投影的均值之差尽可能大些，而使类内样本的离散
13、程度尽可能小散程度尽可能小散程度尽可能小散程度尽可能小n 分析分析w1方向之所以比方向之所以比w2方向优越，可以归纳出这样一个准则，方向优越，可以归纳出这样一个准则，即向量即向量w的方向选择应能使的方向选择应能使两类样本投影的均值之差尽可能大些，两类样本投影的均值之差尽可能大些，两类样本投影的均值之差尽可能大些，两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小而使类内样本的离散程度尽可能小而使类内样本的离散程度尽可能小而使类内样本的离散程度尽可能小。这就是。这就是Fisher准则函数的基准则函数的基本思路。本思路。H:g=0符合符合Fisher准准则要求则要求不符合不符合Fis
14、her准准则要求则要求4.3 Fisher线性判别本讲稿第十九页，共三十二页一些基本参量的定义一些基本参量的定义1.1.样本在样本在d维特征空间维特征空间的一些描述量。的一些描述量。(1)(1)各类样本均值向量各类样本均值向量mi(3)样本类间离散度矩阵样本类间离散度矩阵Sb：(2)样本类内离散度矩阵样本类内离散度矩阵Si与总类内离散度矩阵与总类内离散度矩阵Sw 4.3 Fisher线性判别本讲稿第二十页，共三十二页一些基本参量的定义一些基本参量的定义n样本类内离散度、总类内离散度和类间离散度样本类内离散度、总类内离散度和类间离散度n各类样本均值各类样本均值 2.在在一维一维Y空间空间4.3
15、Fisher线性判别本讲稿第二十一页，共三十二页根据根据Fisher选择投影方向选择投影方向w的原则：使原样本向量在该方向上的投的原则：使原样本向量在该方向上的投影能兼顾：影能兼顾：类间分布尽可能分开，类间分布尽可能分开，类间分布尽可能分开，类间分布尽可能分开，类内样本投影尽可能密集。类内样本投影尽可能密集。类内样本投影尽可能密集。类内样本投影尽可能密集。这个函数称为这个函数称为Fisher准则函数。应该寻找使分子尽可能大，分母准则函数。应该寻找使分子尽可能大，分母尽可能小的尽可能小的w作为投影向量。作为投影向量。n用以评价投影方向用以评价投影方向w的函数为：的函数为：4.3 Fisher线性
16、判别本讲稿第二十二页，共三十二页得出最终表达式：得出最终表达式：4.3 Fisher线性判别本讲稿第二十三页，共三十二页最佳最佳W值的确定值的确定对拉格朗日函数分别对对拉格朗日函数分别对w求偏导并置为求偏导并置为0来求来求w的解。的解。n 最佳最佳w值的确定实际上就是对值的确定实际上就是对Fisher准则函数准则函数求取其达极求取其达极大值时的大值时的 。n 对于这个问题可以采用对于这个问题可以采用拉格朗日乘子算法拉格朗日乘子算法解决，保持分母为一非零解决，保持分母为一非零常数常数c c的条件下，求其分子项的极大值。的条件下，求其分子项的极大值。这是一个求矩阵这是一个求矩阵 的特征值问题的特征
17、值问题。4.3 Fisher线性判别本讲稿第二十四页，共三十二页数值数值R 实际上我们关心的只是向量实际上我们关心的只是向量 的方向，其数值大小对分的方向，其数值大小对分类器没有影响。因此在忽略了数值因子类器没有影响。因此在忽略了数值因子 后，可得：后，可得：上式就是使用上式就是使用Fisher准则求最佳法线向量的解准则求最佳法线向量的解。向量向量 就是使就是使Fisher准则函数准则函数 达极大值的解，也就是达极大值的解，也就是按按按按FisherFisher准则将准则将准则将准则将d维维维维X X空间投影到一维空间投影到一维空间投影到一维空间投影到一维Y Y空间的最佳投影方向空间的最佳投影
18、方向空间的最佳投影方向空间的最佳投影方向，该向量该向量 的各分量值是对原的各分量值是对原d维特征向量求加权和的权值。维特征向量求加权和的权值。4.3 Fisher线性判别本讲稿第二十五页，共三十二页最佳投影方向的理解最佳投影方向的理解 n但是如从使类间分得较开，同时又使类内密集程度较高这样但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对方向作相应的调整，这就体现在对 向量按向量按 作一线作一线性变换，从而使性变换，从而使Fisher准则函数达到极值点。准
19、则函数达到极值点。n(m1-m2)是一向量，显然从两类均值在变换后距离最远这一点看，对与是一向量，显然从两类均值在变换后距离最远这一点看，对与(m1-m2)平行的向量投影可使两均值点的距离最远。平行的向量投影可使两均值点的距离最远。4.3 Fisher线性判别本讲稿第二十六页，共三十二页阈值阈值w0的确定的确定(1)(2)当当 已知时可用已知时可用(3)一般可采用以下几种方法一般可采用以下几种方法确定分界阈值点确定分界阈值点确定分界阈值点确定分界阈值点ww0:0:4.3 Fisher线性判别(1)式中只考虑采用均值连线中点作为阈值点，相当于贝叶斯决策中先验概率相等的情况。其中而(2)与(3)则
20、是以不同方式考虑 与 不等的影响，以减小先验概率不等时的错误率。本讲稿第二十七页，共三十二页决策规则决策规则当当w0确定之后，则可按以下规则分类：确定之后，则可按以下规则分类：使用使用Fisher准则方法确定最佳线性分界面的方法是一个著名的准则方法确定最佳线性分界面的方法是一个著名的方法，尽管提出该方法的时间比较早，仍见有人使用，如人脸方法，尽管提出该方法的时间比较早，仍见有人使用，如人脸识别中用于特征提取。识别中用于特征提取。4.3 Fisher线性判别本讲稿第二十八页，共三十二页例例1：设两类样本的类内离散矩阵分别为：设两类样本的类内离散矩阵分别为 试用试用fisher准则求其决策面方程。准则求其决策面方程。解：解：由于两类样本分布形状是相同的（只是方向不同），因此由于两类样本分布形状是相同的（只是方向不同），因此 应为两类均值的中点应为两类均值的中点 4.3 Fisher线性判别本讲稿第二十九页，共三十二页n例24.3 Fisher线性判别试用Fisher准则求取最佳投影方向，并对(1,2,1)T样本进行分类。本讲稿第三十页，共三十二页解：4.3 Fisher线性判别本讲稿第三十一页，共三十二页解：4.3 Fisher线性判别本讲稿第三十二页，共三十二页