哈工大 模式识别第3章.

第3章非参数判别分类方法非参数判别分类法贝叶斯决策理论：要设法获取样本统计分布的资料,要知道先验概率，类条件概率密度函数等。类条件概率密度函数的确定是通过确定其函数形式p(x|ωi)并对其参数估计来完成的。因此，以贝叶斯决策方法为基础的方法称为参数判别方法问题：1）类条件概率密度函数形式p(x|ωi)很难确定2）在样本数不足条件下获取准确的统计分布是困难的解决办法：根据训练样本集直接进行分类器设计。这种方法绕过统计分布状况的分析，绕过参数估计这一环，而企图对特征空间实行划分，称为非参数判别分类法，即不依赖统计参数的分类法。§3.1引言贝叶斯决策理论设计分类器的步骤非参数判别分类非参数判别分类方法两个过程确定使用什么典型的分类决策方法即决定判别函数类型（如线性判别函数）及优化准则利用训练样本集提供的信息及优化准则（Fisher准则、感知函数准则、最小错分样本数准则等）确定这些函数中的参数。相对最小错误率及最小风险决策（最优分类器）而言，是次优方法，但在所提准则下，是最好的。§3.2线性分类器判别函数是线性判别函数的分类器称为线性分类器主要工作：用训练样本去估计线性判别函数的参数3.2.1线性判别函数的基本概念线性判别函数的一般形式w0是一个常数，称为阈值权两类别线性判别函数的决策规则g(X)＝0就是相应的决策面方程，在线性判别函数条件下它对应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||XXpR1:g0R2:g0正侧负侧H:g=0g(X)、w0的意义r利用线性判别函数决策，就是用一超平面将特征空间分为两个决策域。超平面的方向由W确定，位置由W0决定。g(x)0,X在H的正侧；X→ω1g(x)0,X在H的负侧；X→ω23.2.2广义线性判别函数欲设计这样一个一维样本的分类器，使其性能为：线性判别函数：无能为力若设计判别函数(非线性)g(x)＝(x-a)(x-b)决策规则若：g(x)0,决策：X∈w1g(x)0,决策：X∈w2则可正确分类广义线性判别函数选择一种映射X→Y，将原样本特征向量X映射成另一向量Y，从而可以采用线性判别函数的方法。广义线性判别函数–线性判别函数优点具有形式简单计算方便的优点已被充分研究–希望能将其用适当方式扩展至原本适宜非线性判别函数的领域采用映射x→Y则：判别函数g(x)又可表示成g(x)被称为广义线性判别函数，a称为广义权向量例如，对于二次函数情况，其一般式可表示成：–按照这种原理，任何形式的高次判别函数都可转化成线性判别函数来处理。–这种处理非线性分类器的方法，在支持向量机中得到充分的研究。–产生问题:维数会增加很多推广----线性判别函数的齐次简化将g(x)中的W向量与w0统一表示成称为增广样本向量a:称为增广权向量(广义权向量)它使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。例如：一个一维特征空间的分类器，其决策面方程为：X-c=0在一维空间中为一个点。经齐次简化后得：y1y23.2.3线性分类器设计步骤线性分类器设计任务在给定样本集XX={X1,X2,…,XN}条件下，确定线性判别函数的各项系数,w1,w2,…,wd，以期对待测样本进行分类时，能满足相应的准则函数J为最优的要求。关键问题:确定所需的准则函数，然后用最优化技术确定准则函数的极值解w*及w0*，或增广权向量a*具体过程1、按需要确定一准则函数J。2、确定准则函数J达到极值时w*及w0*的具体数值，从而确定判别函数，完成分类器设计。设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方程的两个参数，一个是权向量W，另一个是阈值w0。3.3Fisher线性判别函数Fisher线性判别函数是研究这类判别函数中最有影响的方法之一。对线性判别函数的研究就是从R.A.Fisher在1936年发表的论文开始的。Fisher线性判别函数基本原理–设计线性分类器首先要确定准则函数，然后再利用训练样本集确定该分类器的参数，以求使所确定的准则达到最佳。–维数问题:降低维数–线性判别函数把d维空间映射到1维空间3.3.1Fisher准则函数Fisher准则基本原理如果在二维空间中一条直线能将两类样本分开，或者错分类很少，则同一类别样本数据在该直线的单位法向量上的投影的绝大多数都应该超过某一值。而另一类数据的投影都应该小于(或绝大多数都小于)该值，则这条直线就有可能将两类分开。–Fisher准则就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。–分析w1方向之所以比w2方向优越，可以归纳出这样一个准则向量W的方向选择应能使两类样本投影的均值之差尽可能大些而使类内样本的离散程度尽可能小样本在d维特征空间的一些描述量(1)各类样本均值向量mi(2)样本类内离散度矩阵Si与总类内离散度矩阵Sw(3)样本类间离散度矩阵Sb若考虑先验概率，则：2在一维Y空间(1)各类样本均值(2)样本类内离散度和总类内离散度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空间的最佳投影方向。是在两类正态分布但具有相同的协方差矩阵Σ时，按最小错误率的贝叶斯决策得到的结果。如果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.4感知准则函数感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，企图将其用于脑模型感知器，因此被称为感知准则函数。特点：随意确定判别函数的初始值，在对样本分类训练过程中逐步修正直至最终确定。感知准则函数：是设计线性分类器的重要方法感知准则函数使用增广样本向量与增广权向量在两类别情况下，判别准则是为简单起见，我们不考虑g(X)＝0的情况。为了讨论原理方便，这一节在线性可分条件下讨论问题，并且只谈两类识别问题。线性可分性设已知样本集{y1,y2,…,yN}，yn是d维增广样本向量,分属于ω1和ω2类。若存在权向量a,使任何y∈ω1,都有：aTy0y∈ω2,都有：aTy0则称这组样本集线性可分。或：若训练样本集是线性可分的，则必存在一个权向量a，可使该训练样本集中的每个样本正确分类。a样本规范化在线性可分条件下，广义权向量a应有：若Y∈ω1,则：aTY0Y∈ω2,则：aTY0为了方便起见，令：Y’称为规范化的增广样本向量。则合适的a能使所有的Y'满足aTY’0.需要解决的问题:找到满足上式的a21YY-YY{Y':若若令解区与解向量满足aTY’0的权向量a称为解向量。解向量存在无穷多个，解向量组成的区域称为解区对解区的限制目的：使解向量更可靠越靠近解区中间的解向量越好解区边界上的解向量不好引入余量b0，解向量应满足：aTY’b.aTY’b.aTY’0.分析：怎样确定准则函数–根据训练样本确定增广权向量a–在给定一个规范化增广样本集Y1,…,YN的条件下，对于任何一个增广权向量a，可计算aTyi–显然如果该向量是一个能将此样本集正确分类的增广权向量，则应有aTyi0,i=1,2,….,N而对可导致错分类的增广权向量，则必有若干个yi,使aTyi0令被错分类的规范化增广样本组成的集用yk表示，并定义一准则函数Jp(a)kTpyyJ(a)(ay)0对线性可分情况:最佳的a应能将该样本集中所有样本正确分类，即yk是空集。因此，确定向量a的问题变为求Jp(a)的极小值的问题。准则函数Jp(a)就是感知准则函数kTpyyJ(a)(ay)0;ky感知准则函数方法的思路1）随意找一个初始向量a(0)2）用训练样本集中的每个样本Y来计算3）若Y’使aTY’0，则a不适合，需修正。若对当前经k次叠代修正的广义权向量为a(k)修正并使其满足：则，aTY’增加，有可能大于0，即新的a(k+1）有可对Y’正确分类。如何求？a(k1)a(k)pJpJTTTa(k1)a(k)a(k)TpyyJyy求感知准则函数的极小值--------梯度下降算法对第k次迭代值，求其梯度向量：可见：感知准则函数的梯度向量是所有被错分类的规范化增广样本向量之和。令迭代向量a沿此负梯度向量方向修正（迭代公式）kkyyyyTpp)y(a])ya([a)a(J)a(Jkkpkkya(k1)a(k)Ja(k)y0，（步长系数）kTTTTkya(k1)a(k)(y)a(k)iiiiyyyy算法1）给定初始权向量a(k)，k=0；（如a(0)=[1,1,….,1]T）2）利用a(k)对对样本集分类，设错分类样本集为yk3）若yk是空集，则a=a(k)，迭代结束；否则，转4）4）计算：ρk,令k=k+15）转2）kpa(k1)a(k)JkpyyJ(a)(y)感知准则函数利用梯度下降算法可简单叙述为：任意给定一向量初始值a(1)，第k+1次迭代时的权向量a(k+1)等于第k次的权向量a(k)加上被错分类的所有样本之和与ρk的乘积。由于每次修正a时都要计算成批样本，因此，该算法也称为“批处理感知算法”可以证明，对于线性可分的样本集，经过有限次修正，一定可以找到一个解向量，即算法能在有限步内收敛。收敛速度取决于初始权向量a(0)和系数ρk。单个样本修正的感知器算法对上述批处理做修正：顺序输入样本，一旦发现分类错误即对权向量修正算法其他部分和成批处理相同收敛性证明：即：新的权向量a(k+1)可能将yi正确分类kika(k1)a(k)y0，TTTT2Tkiikia(k1)a(k)yy=a(k)||y||=a(k)iiiiyyyy步长ρk的计算1、固定增量ρk=1。称为固定增量法。Rosenblatt提出2、可变增量称为绝对增量法此时：T2ki=|a(k)|/||y||iyTTTT2kiikiTT22iiTTa(k1)a(k)yy=a(k)||y||=a(k)|a(k)|/||y||||y||=a(k)|a(k)|0iiiiiiiyyyyyyy例三个样本，x1=1；x2=0；x3=-2；w1={x1,x2};w2={x3}采用感知准则函数及梯度