《哈工大模式识别第3章ppt课件》由会员分享，可在线阅读，更多相关《哈工大模式识别第3章ppt课件（108页珍藏版）》请在金锄头文库上搜索。
1、第3章 非参数判别分类方法,非参数判别分类法,贝叶斯决策理论： 要设法获取样本统计分布的资料,要知道先验概率，类条件概率密度函数等。类条件概率密度函数的确定是通过确定其函数形式p(x|i)并对其参数估计来完成的。因此，以贝叶斯决策方法为基础的方法称为参数判别方法 问题：1）类条件概率密度函数形式p(x|i)很难确定 2）在样本数不足条件下获取准确的统计分布是困难的 解决办法：根据训练样本集直接进行分类器设计。 这种方法绕过统计分布状况的分析，绕过参数估计这一环，而企图对特征空间实行划分，称为非参数判别分类法，即不依赖统计参数的分类法。,3.1引言,贝叶斯决策理论设计分类器的步骤 非参数判别分类
2、,非参数判别分类方法两个过程,确定使用什么典型的分类决策方法 即决定判别函数类型（如线性判别函数）及优化准则 利用训练样本集提供的信息及优化准则（Fisher准则、感知函数准则、最小错分样本数准则等）确定这些函数中的参数。 相对最小错误率及最小风险决策（最优分类器）而言，是次优方法，但在所提准则下，是最好的。,3.2 线性分类器,判别函数是线性判别函数的分类器称为线性分类器 主要工作：用训练样本去估计线性判别函数的参数 3.2.1 线性判别函数的基本概念 线性判别函数的一般形式,w0是一个常数，称为阈值权,两类别线性判别函数的决策规则,g(X)0就是相应的决策面方程，在线性判别函数条件下它对应
3、d维空间的一个超平面,向量W的意义,设在该决策平面上有两个特征向量X1与X2，则 W与该平面上任两点组成的向量(X1-X2)正交 W是该超平面的法线向量,g(X)是d维空间任一点X到决策面H的距离的代数度量 w0体现该决策面在特征空间中的位置 1) w0=0时，该决策面过特征空间坐标系原点 2)否则，R0=w0/|W|表示坐标原点到决策面的距离,g(X) / |W|,R0=w0 / |W|,X,Xp,R1: g0,R2: g0,正侧,负侧,H: g=0,g(X)、 w0的意义,r,g(X)的意义,设Xp是X在H上的投影向量，r是x到H的垂直距离 W/|W|是W方向的单位向量，则 g(X) =W
4、Tx+w0=WT(Xp+rW/|W|)+w0 =( WTXp+w0)+rWTW/|W| =r|W| r=g(X)/|W| 若X=0(原点)，则g(X)=WTx+w0=w0 否则：r0=g(0)/|W|=w0 /|W|,利用线性判别函数决策，就是用一超平面将特征空间分为两个决策域。超平面的方向由W确定，位置由W0决定。 g(x)0,X在H的正侧；X 1 g(x)0,X在H的负侧；X 2,3.2.2广义线性判别函数,欲设计这样一个一维样本的分类器，使其性能为： 线性判别函数：无能为力 若设计判别函数(非线性)g(x)(x-a)(x-b) 决策规则 若：g(x)0, 决策：Xw1 g(x)0, 决策
5、：Xw2 则可正确分类,广义线性判别函数,选择一种映射XY，将原样本特征向量X映射成另一向量Y，从而可以采用线性判别函数的方法。 广义线性判别函数 线性判别函数优点 具有形式简单 计算方便的优点 已被充分研究 希望能将其用适当方式扩展至原本适宜非线性判别函数的领域,采用映射xY 则：判别函数g(x)又可表示成,g(x)被称为广义线性判别函数， a称为广义权向量,例如，对于二次函数情况，其一般式可表示成：,按照这种原理，任何形式的高次判别函数都可转化成线性判别函数来处理。 这种处理非线性分类器的方法，在支持向量机中得到充分的研究。 产生问题: 维数会增加很多,推广-线性判别函数的齐次简化,将g(
6、x)中的W向量与w0统一表示成,称为增广样本向量,a:称为增广权向量 (广义权向量),它使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。,例如：一个一维特征空间的分类器，其决策面方程为： X-c=0 在一维空间中为一个点。经齐次简化后得：,3.2.3线性分类器设计步骤,线性分类器设计任务 在给定样本集XX=X1,X2,XN条件下， 确定线性判别函数的各项系数,w1,w2,wd ，以期对待测样本进行分类时，能满足相应的准则函数J为最优的要求。 关键问题: 确定所需的准则函数，然后用最
7、优化技术确定准则函数的极值解w*及w0*，或增广权向量 a*,具体过程,1 、按需要确定一准则函数J。2 、确定准则函数J达到极值时w*及w0*的具体数值，从而确定判别函数，完成分类器设计。 设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方程的两个参数，一个是权向量W，另一个是阈值w0。,3.3Fisher线性判别函数,Fisher线性判别函数是研究这类判别函数中最有影响的方法之一。 对线性判别函数的研究就是从R.A.Fisher在1936年发表的论文开始的。,Fisher线性判别函数基本原理 设计线性分类器首先要确定准则函数，然后再利用训练
8、样本集确定该分类器的参数，以求使所确定的准则达到最佳。 维数问题: 降低维数 线性判别函数把d维空间映射到1维空间,Fisher线性判别函数基本原理 如果我们只考虑各分量的线性加权和，则它是各样本向量与向量W的向量点积。 如果向量W的幅度为单位长度，则线性加权和又可看作各样本向量在向量W上的投影。 Fisher的基本问题 在1维直线上不一定能够分开样本 希望在1维直线上不同类别的样本分得越开越好 如何找到这条最好的、最易于分类的投影线,3.3.1 Fisher准则函数,Fisher准则基本原理,如果在二维空间中一条直线能将两类样本分开，或者错分类很少，则同一类别样本数据在该直线的单位法向量上的
9、投影的绝大多数都应该超过某一值。而另一类数据的投影都应该小于(或绝大多数都小于)该值，则这条直线就有可能将两类分开。 Fisher准则就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。 分析w1方向之所以比w2方向优越，可以归纳出这样一个准则 向量W的方向选择应能使两类样本投影的均值之差尽可能大些 而使类内样本的离散程度尽可能小,样本在d维特征空间的一些描述量,(1) 各类样本均值向量mi (2) 样本类内离散度矩阵Si与总类内离散度矩阵Sw (3) 样本类间离散度矩阵Sb 若考虑 先验概率，则：,2 在一维Y空间,(1) 各类样本均值 (2) 样本类内
10、离散度 和总类内离散度,Fisher准则的函数形式,Fisher选择投影方向W的原则： y=WTX 类间分布尽可能分开， 类内样本投影尽可能密集的要求 评价投影方向W的函数 上式并不是W的显函数，需化为W的显函数,进一步化为W的显函数,分子,分母,分母：,因此,3.3.2最佳W值的确定,最佳W值的确定: 求取使JF达极大值时的 w* 可以采用拉格朗日乘子算法解决 设计一拉格朗日函数,对向量的求导(或偏导)的定义是,由于Sw非奇异，两边乘以Sw-1得,最佳法线向量W*,使Fisher准则函数JF达极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向。,是在两类正态分布但
11、具有相同的协方差矩阵时，按最小错误率的贝叶斯决策得到的结果。 如果P(i)=P(j)，则最佳分界线就是两类概率密度函数值相等的点的集合。 按Fisher准则，Sw=1+ 2=2 ， Sb=(u1-u2)， 即：若两类样本的离散矩阵相近，也就是说两类分布的形式很相近，按Fisher准则，错分率就应比较小（接近最小错误率），Fisher准则的合理性可以在这里体现,3.3.3W0的确定,若维数d足够大，样本数足够多，可估计各类样本在1维上的方差和均值、先验概率等，然后，按最小错误率Bayes决策确定阈值W0。 否则，按如下方法确定： 1、 2、 3、,（P(W1)、P(W2)已知时）,分类规则,3.
12、4感知准则函数,感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，企图将其用于脑模型感知器，因此被称为感知准则函数。 特点：随意确定判别函数的初始值，在对样本分类训练过程中逐步修正直至最终确定。 感知准则函数：是设计线性分类器的重要方法 感知准则函数使用增广样本向量与增广权向量,在两类别情况下，判别准则是,为简单起见，我们不考虑g(X)0的情况。,为了讨论原理方便，这一节在线性可分条件下讨论问题，并且只谈两类识别问题。,线性可分性,设已知样本集y1,y2,yN， yn是d维增广样本向量,分属于1 和2类。 若存在权向量a,使任何y1 ,都有：aTy0 y2 ,都有：
13、aTy0 则称这组样本集线性可分。 或：若训练样本集是线性可分的，则必存在一个权向量a，可使该训练样本集中的每个样本正确分类。,样本规范化,在线性可分条件下，广义权向量a应有：若 Y1 ,则：aTY0 Y2 ,则：aTY0. 需要解决的问题: 找到满足上式的a,解区与解向量,满足aTY0的权向量a称为解向量。 解向量存在无穷多个，解向量组成的区域称为解区,对解区的限制,目的：使解向量更可靠 越靠近解区中间的解向量越好 解区边界上的解向量不好 引入余量b0，解向量应满足： aTYb.,aTYb.,aTY0.,分析：怎样确定准则函数,根据训练样本确定增广权向量 a 在给定一个规范化增广样本集Y1,
14、YN的条件下，对于任何一个增广权向量a ，可计算 aTyi 显然如果该向量是一个能将此样本集正确分类的增广权向量，则应有 aTyi0, i=1,2,.,N,而对可导致错分类的增广权向量，则必有若干个yi ,使 aTyi0 令被错分类的规范化增广样本组成的集用yk表示，并定义一准则函数Jp(a),对线性可分情况: 最佳的a应能将该样本集中所有样本正确分类，即yk是空集。因此， 确定向量a的问题变为求Jp(a)的极小值的问题。 准则函数 Jp(a) 就是感知准则函数,感知准则函数方法的思路,1）随意找一个初始向量 a(0) 2）用训练样本集中的每个样本Y来计算 3）若Y使aTY0，则a不适合，需修
15、正。 若对当前经k次叠代修正的广义权向量为a(k)修正 并使其满足： 则， aTY增加，有可能大于0，即新的a(k+1）有可对Y正确分类。 如何求 ？,求感知准则函数的极小值 -梯度下降算法,对第k次迭代值，求其梯度向量： 可见：感知准则函数的梯度向量是所有被错分类的规范化增广样本向量之和。 令迭代向量a沿此负梯度向量方向修正（迭代公式）,（步长系数 ）,算法,1）给定初始权向量a(k) ，k=0； （ 如a(0)=1,1,.,1T） 2）利用a(k)对对样本集分类，设错分类样本集为yk 3）若yk是空集，则a=a(k)，迭代结束； 否则，转4） 4）计算：k, 令k=k+1 5）转2）,感知
16、准则函数利用梯度下降算法,可简单叙述为： 任意给定一向量初始值a(1)，第k+1次迭代时的权向量a(k+1)等于第k次的权向量a(k)加上被错分类的所有样本之和与k 的乘积。 由于每次修正a时都要计算成批样本，因此，该算法也称为“批处理感知算法” 可以证明，对于线性可分的样本集，经过有限次修正，一定可以找到一个解向量 ，即算法能在有限步内收敛。 收敛速度取决于初始权向量a(0) 和系数k 。,单个样本修正的感知器算法,对上述批处理做修正： 顺序输入样本，一旦发现分类错误即对权向量修正 算法其他部分和成批处理相同 收敛性证明： 即：新的权向量a(k+1)可能将yi正确分类,步长k 的计算,1、固定增量 k =1。 称为固定增量法。Rosenblatt提出 2、可变增量 称为绝对增量法 此时：,例,
