模式识别(4-1).ppt

《模式识别(4-1).ppt》由会员分享，可在线阅读，更多相关《模式识别(4-1).ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 模式识别模式识别 第四章线性判别函数（第四章线性判别函数（1）回顾：回顾：参数估计与非参数估计参数估计与非参数估计需要大量样本？需要大量样本？需要大量样本？需要大量样本？利用样本集直接设计分类器？利用样本集直接设计分类器？4.1 4.1 引言引言n n利用样本集直接设计分类器的基本思想：利用样本集直接设计分类器的基本思想：qq给定某个判别函数类，且假定判别函数的参数形式给定某个判别函数类，且假定判别函数的参数形式给定某个判别函数类，且假定判别函数的参数形式给定某个判别函数类，且假定判别函数的参数形式已知已知已知已知qq用训练的方法来估计判别函数的参数值用训练的方法来估计判别函数的参数值用训练

2、的方法来估计判别函数的参数值用训练的方法来估计判别函数的参数值qq分类决策分类决策分类决策分类决策n n不需要有关的概率密度函数的确切的参数形式不需要有关的概率密度函数的确切的参数形式，属于非参数估计方法。属于非参数估计方法。4.1 4.1 引言引言n n问题描述：问题描述：q假设对一模式X已抽取n个特征，表示为：q根据模式根据模式X的的n个特征来判别模式属于个特征来判别模式属于1,2,m 类中的那一类类中的那一类?4.1 4.1 引言引言n例如下图：三类的分类问题，它们的边界线就是一个判别函数。4.1 4.1 引言引言n判别函数包含两类：判别函数包含两类：q一类一类 是线性判别函数：是线性判

3、别函数：n线性判别函数n广义线性判别函数q（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）n分段线性判别函数q另一类是非线性判别函数另一类是非线性判别函数4.1 4.1 引言引言n n线性判别函数：线性判别函数：x的各个分量的线性函数或以x为自变量的某些函数的线性函数。n对于c类问题：n优点：q最优？次优？q计算简单；容易实现；需要的计算量和存储量小利用样本集估计参数利用样本集估计参数wi和和wi0，并把未知样，并把未知样本本x归到具有最大判别函数值的类别中去。归到具有最大判别函数值的类别中去。4.1 4.1 引言引言n寻找线性判别函数的问题被形式化为极小化准则函

4、数的问题。以分类为目的的准则函数可以是样本风险，也可以是训练误差。n目标：目标：能够正确地对新的样本进行分类能够正确地对新的样本进行分类线性判别函数的基本概念线性判别函数的基本概念设样本设样本d维特征空间中描述，则维特征空间中描述，则两类别问题两类别问题中线性判别函数的中线性判别函数的一般形式可表示成一般形式可表示成其中其中w0是一个常数，称为阈值权。相应的决策规则可表示成是一个常数，称为阈值权。相应的决策规则可表示成 g(x)0就是相应的决策面方程，在线性判别函数条件下它对就是相应的决策面方程，在线性判别函数条件下它对应应d维空间的一个超平面。维空间的一个超平面。线性判别函数的基本概念线性判

5、别函数的基本概念 至于至于w w0 0则体现该决策面在特征空间中的位置则体现该决策面在特征空间中的位置则体现该决策面在特征空间中的位置则体现该决策面在特征空间中的位置，当，当w0=0时，该时，该决策面过特征空间坐标系原点，而决策面过特征空间坐标系原点，而 时，则时，则 表示了坐表示了坐标原点到该决策面的距离。标原点到该决策面的距离。为了说明向量为了说明向量w的意义，我们假设在该决策平面上有两个特征的意义，我们假设在该决策平面上有两个特征向量向量x1与与x2，则应有则应有其中其中(x1-x2)也是一个向量也是一个向量 而而g(x)也就是也就是d维空间中任一点维空间中任一点x到该决策面距离的代数度

6、量，到该决策面距离的代数度量，该该决策平面将这两类样本按其决策平面将这两类样本按其到该面距离的正负号到该面距离的正负号到该面距离的正负号到该面距离的正负号确定其类别。确定其类别。上上式表明向量式表明向量w与该平面上任两点组成的向量与该平面上任两点组成的向量(x1-x2)正交，因正交，因此此w就是该超平面的就是该超平面的法向量法向量法向量法向量。这就是向量。这就是向量w的几何意义。的几何意义。线性判别函数的几何意义线性判别函数的几何意义令令n决策面(decision boundary)H方程：g(x)=0n向量w是决策面H的法向量ng(x)是点x到决策面H的距离的一种代数度量x1x2wxxprH

7、:g=0线性判别函数的几何意义线性判别函数的几何意义令令x1x2wxxprH:g=0广义线性判别函数广义线性判别函数线性判别函数是形式最为简单的判别函数，但是它不能用于线性判别函数是形式最为简单的判别函数，但是它不能用于稍复杂一些的情况。稍复杂一些的情况。欲设计这样一个一维样本的分类器，使其性能为欲设计这样一个一维样本的分类器，使其性能为 针对这种情况，如果设计这针对这种情况，如果设计这样一个判别函数样一个判别函数:g(x)(x-a)(x-b)相应的决策规则相应的决策规则:此时此时,g(x)不再是不再是x的线性函数，而是一个二次函数的线性函数，而是一个二次函数广义线性判别函数广义线性判别函数由

8、于线性判别函数具有形式简单，计算方便由于线性判别函数具有形式简单，计算方便的优点，并且已被充分研究，因此人们希望的优点，并且已被充分研究，因此人们希望能将其能将其用适当方式扩展至原本适宜非线性判用适当方式扩展至原本适宜非线性判别函数的领域别函数的领域。一种方法是一种方法是选择一种映射选择一种映射xy，即将原样本，即将原样本特征向量特征向量x映射成另一向量映射成另一向量y，从而可以采用，从而可以采用线性判别函数的方法。线性判别函数的方法。广义线性判别函数广义线性判别函数选择一种映射选择一种映射x y，即将原样本特征向量，即将原样本特征向量x映射成另一向量映射成另一向量y，从而可以采用线性判别函数

9、的方法。，从而可以采用线性判别函数的方法。如果我们采用映射如果我们采用映射x y，使，使则判别函数则判别函数g(x)又可表示成又可表示成 此时此时g(x)被称为被称为广义线性判别函数广义线性判别函数，a a称为称为广义权向量广义权向量。广义线性判别函数广义线性判别函数n按照上述原理，任何非线性函数按照上述原理，任何非线性函数g(x)用级数展开成高次多用级数展开成高次多项式后，都可转化成项式后，都可转化成广义线性判别函数广义线性判别函数来处理。来处理。n na aT Ty y=0=0在在在在Y Y空间确定了一个通过原点的超平面空间确定了一个通过原点的超平面空间确定了一个通过原点的超平面空间确定了

10、一个通过原点的超平面。这样我们。这样我们就可以利用线性判别函数的简单性来解决复杂的问题。就可以利用线性判别函数的简单性来解决复杂的问题。n经过这种变换，维数大大增加了，这将使问题很快陷入经过这种变换，维数大大增加了，这将使问题很快陷入所谓的所谓的“维数灾难维数灾难”。怎么解决？。怎么解决？广义线性判别函数广义线性判别函数l 线性判别函数的齐次简化使线性判别函数的齐次简化使特征空间增加了一维特征空间增加了一维，但保持，但保持了样本间的了样本间的欧氏距离不变欧氏距离不变，对于分类效果也与原决策面相同，对于分类效果也与原决策面相同，只是在只是在Y空间中决策面是通过坐标原点的，这在分析某些问题空间中决

11、策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。时具有优点，因此经常用到。n线性判别函数的齐次简化线性判别函数的齐次简化：n一种特殊映射方法一种特殊映射方法：增广样本向量：增广样本向量y与增广权向量与增广权向量a广义线性判别函数广义线性判别函数例如例如例如例如一个一维特征空间的分类器，其决策面方程为一个一维特征空间的分类器，其决策面方程为 x-c=0 x-c=0 在一维空间中为一个点。经齐次简化后可得：在一维空间中为一个点。经齐次简化后可得：此时在二维空间中决策面为一过原点的直线，如下页图此时在二维空间中决策面为一过原点的直线，如下页图所示。直线以所示。直线以 为法线向量，它对

12、为法线向量，它对1 1维子空间维子空间(y2(y2空间空间)的划的划分与原决策面完全相同。分与原决策面完全相同。广义线性判别函数广义线性判别函数由于样本向量在增加一维后变成了一个二维向量，因此由于样本向量在增加一维后变成了一个二维向量，因此原一维空间讨论的问题，转变成在二维空间讨论的问题，原一维空间讨论的问题，转变成在二维空间讨论的问题，而原方程也变成了一条直线，它过二维空间的原点。而原方程也变成了一条直线，它过二维空间的原点。广义线性判别函数广义线性判别函数答：一个过原点的平面，方程为答：一个过原点的平面，方程为ay1+by2+cy3=0(B)。(A)式与式与(B)式形式上略有不同，但当式形

13、式上略有不同，但当y3=1时两者就一样了。时两者就一样了。也就是说也就是说(B)式表示的平面与式表示的平面与y3=1子空间子空间(一平面一平面)的交线就是的交线就是(A)式中表示的直线，这样的方法在后面感知准则函数中用到。式中表示的直线，这样的方法在后面感知准则函数中用到。思考一下思考一下思考一下思考一下，如果在两维空间存在一条不过原点的直线，如果在两维空间存在一条不过原点的直线，ax1+bx2+c=0(A)，采用增广向量形式：采用增广向量形式：那么，它在增加一维的三维空间中，那么，它在增加一维的三维空间中，aTY=0表示的是什么呢？表示的是什么呢？线性分类器的设计任务线性分类器的设计任务n在

14、给定样本集在给定样本集 条件下条件下 ，确定线性判别函数的各项系数确定线性判别函数的各项系数 ，以，以期对待测样本进行分类时，能满足相应的准则期对待测样本进行分类时，能满足相应的准则函数函数J为最优的要求。为最优的要求。n权向量权向量 阈值权阈值权 或或 增广权向量增广权向量n此技术的关键问题是确定所需的准则函数，然此技术的关键问题是确定所需的准则函数，然后用最优化技术确定准则函数的极值点后用最优化技术确定准则函数的极值点 及及 ，或增广权向量，或增广权向量 。线性分类器的设计步骤：线性分类器的设计步骤：n给定样本集X，确定线性判别函数 的各项系数w和w0。步骤：步骤：q收集一组具有类别标志的

15、样本收集一组具有类别标志的样本X=x1,x2,xNq按需要确定一准则函数按需要确定一准则函数J，其值反映分类器的性能，其极，其值反映分类器的性能，其极值解对应于值解对应于“最好最好”的决策。的决策。q用最优化技术求准则函数用最优化技术求准则函数J的极值解的极值解w*和和w0*，从而确定，从而确定判别函数，完成分类器设计。判别函数，完成分类器设计。n对于未知样本x，计算g(x)，判断其类别。换一个方式说：换一个方式说：设计线性分类器，是指所用的判别函数、分界面方程设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确的类型已选定为线性类型，因此主要的设计任务

16、是确定线性方程的两个参数，一个是权向量定线性方程的两个参数，一个是权向量w，另一个是，另一个是阈值阈值w0。为了使所设计的线性分类器在性能上要满足一定的要为了使所设计的线性分类器在性能上要满足一定的要求，这种要求通过一种准则来体现，并且要表示成一求，这种要求通过一种准则来体现，并且要表示成一种准则函数，以便能通过将准则函数值优化的方法确种准则函数，以便能通过将准则函数值优化的方法确定定w与与w0。4.2 4.2 FisherFisher线性判别线性判别nFisher线性判别函数是研究线性判别函数中最线性判别函数是研究线性判别函数中最有影响的方法之一。对线性判别函数的研究就有影响的方法之一。对线

17、性判别函数的研究就是从是从R.A.Fisher在在1936年发表的论文开始的。年发表的论文开始的。4.2 4.2 FisherFisher线性判别线性判别首先要首先要确定准则函数确定准则函数；然后再利用训练样本集确定该然后再利用训练样本集确定该分类器的参数分类器的参数，以求使所确，以求使所确定的准则达到最佳。定的准则达到最佳。在使用线性分类器时，样本的分类由其判别函数值决定，在使用线性分类器时，样本的分类由其判别函数值决定，而每个样本的判别函数值是其各分量的线性加权和再加上而每个样本的判别函数值是其各分量的线性加权和再加上一阈值一阈值w0 0。设计线性分类器：设计线性分类器：如果我们只考虑各分

18、量的线性加权和，则它是各样本向量如果我们只考虑各分量的线性加权和，则它是各样本向量与向量与向量w的向量点积。的向量点积。4.2 4.2 FisherFisher线性判别线性判别w(y)wy1y2x2x112现在讨论通过映射投影来降低维数的方法。把X空间各点投影到Y空间得一直线上，维数由2维降为一维。若适当选择w的方向，可以使二类分开。下面我们从数学上寻找最好的投影方向，即寻找最好的变换向量寻找最好的变换向量寻找最好的变换向量寻找最好的变换向量w w的问题。FisherFisher准则的基本原理准则的基本原理 FisherFisher准则的基本原理，就是要准则的基本原理，就是要找到一个最合适的投

19、影找到一个最合适的投影找到一个最合适的投影找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分轴，使两类样本在该轴上投影的交迭部分最少，从而使分轴，使两类样本在该轴上投影的交迭部分最少，从而使分轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。类效果为最佳。类效果为最佳。类效果为最佳。分析分析w1方向之所以比方向之所以比w2方向优越，可以归纳出这样一个方向优越，可以归纳出这样一个准则，即向量准则，即向量w的方向选择应能使的方向选择应能使两类样本投影的均值之差两类样本投影的均值之差两类样本投影的均值之差两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能

20、小尽可能大些，而使类内样本的离散程度尽可能小尽可能大些，而使类内样本的离散程度尽可能小尽可能大些，而使类内样本的离散程度尽可能小。这就是。这就是Fisher准则函数的基本思路。准则函数的基本思路。一些基本参量的定义一些基本参量的定义1.1.样本在样本在d维特征空间维特征空间的一些描述量。的一些描述量。2.2.(1)(1)各类样本均值向量各类样本均值向量mi(2)样本类内离散度矩阵样本类内离散度矩阵Si与总类内离散度矩阵与总类内离散度矩阵Sw(3)样本类间离散度矩阵样本类间离散度矩阵Sb：一些基本参量的定义一些基本参量的定义样本类内离散度、总类内离散度和类间离散度样本类内离散度、总类内离散度和类

21、间离散度各类样本均值各类样本均值 2.在在一维一维Y空间空间4.2 4.2 FisherFisher线性判别线性判别根据根据Fisher选择投影方向选择投影方向w的原则：使原样本向量在该方向上的原则：使原样本向量在该方向上的投影能兼顾：的投影能兼顾：类间分布尽可能分开，类间分布尽可能分开，类间分布尽可能分开，类间分布尽可能分开，类内样本投影尽可能密集。类内样本投影尽可能密集。类内样本投影尽可能密集。类内样本投影尽可能密集。这个函数称为这个函数称为Fisher准则函数。应该寻找使分子尽可能大，准则函数。应该寻找使分子尽可能大，分母尽可能小的分母尽可能小的w作为投影向量。作为投影向量。用以评价投影

22、方向用以评价投影方向w的函数为：的函数为：4.2 4.2 FisherFisher线性判别线性判别4.2 4.2 FisherFisher线性判别线性判别得出最终表达式：得出最终表达式：最佳最佳W值的确定值的确定对拉格朗日函数分别对对拉格朗日函数分别对w求偏导并置为求偏导并置为0来求来求w的解。的解。最佳最佳w值的确定实际上就是对值的确定实际上就是对Fisher准则函数准则函数求取其达极求取其达极大值时的大值时的 。对于这个问题可以采用对于这个问题可以采用拉格朗日乘子算法拉格朗日乘子算法解决，保持分母解决，保持分母为一非零常数为一非零常数c c的条件下，求其分子项的极大值。的条件下，求其分子项

23、的极大值。这是一个求矩阵这是一个求矩阵 的特征值问题的特征值问题。数值数值R 实际上我们关心的只是向量实际上我们关心的只是向量 的方向，其数值大小对分的方向，其数值大小对分类器没有影响。因此在忽略了数值因子类器没有影响。因此在忽略了数值因子 后，可得：后，可得：上式就是使用上式就是使用Fisher准则求最佳法线向量的解准则求最佳法线向量的解。向量向量 就是使就是使Fisher准则函数准则函数 达极大值的解，也就是达极大值的解，也就是按按按按FisherFisher准则将准则将准则将准则将d d维维维维X X空间投影到一维空间投影到一维空间投影到一维空间投影到一维Y Y空间的最佳投影方向空间的最

24、佳投影方向空间的最佳投影方向空间的最佳投影方向，该向量该向量 的各分量值是对原的各分量值是对原d维特征向量求加权和的权值。维特征向量求加权和的权值。最佳投影方向的理解最佳投影方向的理解 但是如从使类间分得较开，同时又使类内密集程度较高这样但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对方向作相应的调整，这就体现在对 向量按向量按 作一线作一线性变换，从而使性变换，从而使Fisher准则函数达到极值点。准则函数达到极值点。(m1-m2)是一向量，显然从两类

25、均值在变换后距离最远这一点是一向量，显然从两类均值在变换后距离最远这一点看，对与看，对与(m1-m2)平行的向量投影可使两均值点的距离最远。平行的向量投影可使两均值点的距离最远。判别函数的确定判别函数的确定(1)(2)当当 与与 已知时可用已知时可用(3)（1）当维数d与样本数N都很大时，可采用贝叶斯决策规则，获得一种在一维空间的“最优”分类器。（2）当上述条件不满足时，一般可采用以下几种方法一般可采用以下几种方法确定确定确定确定分界阈值点分界阈值点分界阈值点分界阈值点w0:分界阈值点分界阈值点 y0=-w0决策规则决策规则当当y0确定之后，则可按以下规则分类：确定之后，则可按以下规则分类：使

26、用使用Fisher准则方法确定最佳线性分界面的方法是一个准则方法确定最佳线性分界面的方法是一个著名的方法，尽管提出该方法的时间比较早，仍见有人著名的方法，尽管提出该方法的时间比较早，仍见有人使用，如人脸识别中用于特征提取。使用，如人脸识别中用于特征提取。其中而(2)与(3)则是以不同方式考虑 与 不等的影响，以减小先验概率不等时的错误率。(1)式中只考虑采用均值连线中点作为阈值点，相当于贝叶斯决策中先验概率相等的情况。例例1：设五维空间的线性方程为：设五维空间的线性方程为 试求出其权向量与样本向量点积的表达式试求出其权向量与样本向量点积的表达式 中的中的W，X以及增广权向量与增广样本向量形式以及增广权向量与增广样本向量形式 中的中的a与与Y。解：解：例例2：设两类样本的类内离散矩阵分别为：设两类样本的类内离散矩阵分别为 试用试用fisher准则求其决策面方程。准则求其决策面方程。解：解：由于两类样本分布形状是相同的（只是方向不同），因此由于两类样本分布形状是相同的（只是方向不同），因此 应为两类均值的中点应为两类均值的中点 例例3.已知两类数据，其先验概率相等，样本分别为：已知两类数据，其先验概率相等，样本分别为：根据Fisher准则求取最佳投影方向W，并对样本进行分类。解：第一类样本均值第二类均值 待分类样本：所以该样本属于第w1类。