工学线性二次分类器.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/10/26,四川大学、电气信息学院、余勤,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/10/26,四川大学、电气信息学院、余勤,#,2025/8/19 周二,四川大学、电气信息学院、余勤,1,二次和线性分类器,2025/8/19 周二,四川大学、电气信息学院、余勤,2,前面讲的提供了设计各种特定形式分类器的基础。,这一小节讲述二次和线性分类器。所以叫作二次或线性分类器是因为,分类（决策）面方程的数学形式是二次或线性的,。,这样的分类器又叫,参数分类器,，因为它们由一些参数所规定（如分布的均值和方差）。,2025/8/19 周二,四川大学、电气信息学院、余勤,3,问题的引出：,在一定的分布和条件下（如正态、等协方差矩阵），贝叶斯决策可以导致二次或线性分类器。,虽然贝叶斯决策（似然比检验）在错误率或风险上是最优的，但必须知道类条件密度。在大多数应用场合，类条件密度函数是从有限的样本中估计的。后面我们将讲一些密度函数估计的方法。但密度函数的估计本身是一件复杂工作（其难度不低于分类）并且需要大量样本。,2025/8/19 周二,四川大学、电气信息学院、余勤,4,即使我们得到了密度函数，有时用似然比检验的方法也很难计算，需要大量的时间和空间。,因此我们有时考虑更简便易行的分类器设计方法。用二次、线性、分段线性分类器。,即先规定分类器的数学形式，然后在适当的准则下，来确定这些参数。,这一节先分析在什么条件下贝叶斯分类器变成二次和线性分类器，第四章再讨论当这些条件不满足时，如何设计,“,性能好,”,的参数分类器,(,LDA,判别式分析法,）。,2025/8/19 周二,四川大学、电气信息学院、余勤,5,一,.,两类问题的二次和线性分类器,对于似然比检验的决策规则,:,2025/8/19 周二,四川大学、电气信息学院、余勤,6,当各类的类条件密度是高斯分布时，,i,和,i,为协方差矩阵和均值向量。,这时似然比为,2025/8/19 周二,四川大学、电气信息学院、余勤,7,定义 ，,-2,倍自然对数,则,:,(1),上式是,二次分类器,。计算,x,到各类均值,m,i,的,Mahalanobis,距离，然后和阈值,相比较，决定,x,属于第一类或第二类。,-2ln,2025/8/19 周二,四川大学、电气信息学院、余勤,8,在一维时，马氏距离 ，即比较用方差标准化的一般距离。,展开,(1),式，有,（,2,）,式中,2025/8/19 周二,四川大学、电气信息学院、余勤,9,决策边界,h,(,x,)=,T,是二次曲面（超曲面）：超椭球面、超双曲面、超抛物面、超平面等，或它们组合的形式。,（,为了确定二次曲面的形状，首先要消掉,x,的各分量相乘的项，可采用旋转坐标系的方法，把坐标轴旋转到,A,的特征向量的方向。曲面的几何形状由,A,的特征值决定。如果,A,的特征值全部是正的，则是超椭球面；如果特征值有些正，有些负，则是超双曲面；如果有些特征值是,0,，则是超抛物面。）,2025/8/19 周二,四川大学、电气信息学院、余勤,10,当,x,落到决策边界的某一侧时，就把它分到相应的类。也可以把上述二次分类器用到非高斯分布的密度函数，但这时不能保证错误率最小。（但所确定的边界是和二阶统计矩（均值、方差）最相匹配的。）,任何具有,（,2,）,式的分类器都叫作,二次分类器,。只有,A,、,b,、,c,是由高斯密度函数确定时，才叫,高斯分类器,。,2025/8/19 周二,四川大学、电气信息学院、余勤,11,例,1,：两维时的二次分类器的决策边界,假定两类模式都是高斯分布的，参数为：,求 的分类边界，并画出其曲线。,2025/8/19 周二,四川大学、电气信息学院、余勤,12,解：,2025/8/19 周二,四川大学、电气信息学院、余勤,13,假定,T,=0,，,h,(,x,)=,T,=0,化为：,，是一双曲线。,2025/8/19 周二,四川大学、电气信息学院、余勤,14,当先验概率相等时，最小错误率决策规则选择类条件概率密度函数大的。,由于第二类在,x,2,方向上的方差大于类,1,的，这样密度函数,p,(,x,|,2,),在,x,2,方向上将有较广的延伸。使得在左边,R,2,区域内有,p,(,x,|,2,),p,(,x,|,1,),，尽管这些点比较靠近类,1,的均值点。,2025/8/19 周二,四川大学、电气信息学院、余勤,15,在前面的,h,(,x,)=,x,T,Ax,+,b,T,x,+,c,中，如果两类的协方差矩阵相等，,=,1,=,2,，则矩阵,A,=0,，这时决策规则为：,式中,(3-9),这时的决策边界就退化为线性决策边界（超平面），相应的分类器为,线性分类器,。,2025/8/19 周二,四川大学、电气信息学院、余勤,16,二,.,判别函数和多类分类器,多类的判别函数,当模式有 类，这时的最小错误率的决策规则可以表示为：,若,（,3,）,式中,称为判别函数（,discriminant function,）。它表示决策规则。,2025/8/19 周二,四川大学、电气信息学院、余勤,17,由贝叶斯公式，和 等价。即把 用（,3,）式中时，决策规则是一样的。,当先验概率相等时，也是一组等价的判别函数。,一般地，若 是任意一组判别函数，则下面定义的 也是一组等价的判别函数：,a,0,b,是常数。（也可以是,x,的函数，但不能是,k,的函数。）,2025/8/19 周二,四川大学、电气信息学院、余勤,18,同样，若 ，,f,是单调增函数，它和 也是等价的。,这些性质可以使我们从一组判别函数推导出另外的判别函数，以便计算上更加简单，或者意义更清楚，便于理解。,2025/8/19 周二,四川大学、电气信息学院、余勤,19,当每类都是正态分布，其均值和协方差分别为,k,和,k,时，这时的最小错误率决策规则的判别函数为：,多类的二次和线性分类器,由于,自然对数是单调增,的，所以可以定义下面等价的判别函数：,（,4,）,2025/8/19 周二,四川大学、电气信息学院、余勤,20,这是二次判别函数。当所有类的先验概率相等时，可以省略 。,前面已经证明，当两类的协方差矩阵相等时，二次分类器退化为线性分类器。多类时也是如此。,当 时，,（,4,）式,化为：,上式中，由于第一项和第四项对所有的类都是相同的，所以等价的一组判别函数为：,（,5,）,上式是,x,的线性函数。,2025/8/19 周二,四川大学、电气信息学院、余勤,21,例,2,：,最小距离分类器,。假定各类的先验概率相等，而且各类 。即,x,的各个分量不相关，且各类等方差。,解：这时的判别函数化为：,后两项对所有类是共同的，可以省略。分母中的 也可以去掉，因而有等价的判别函数：,这时的决策规则的含义是：,x,离哪类的均值最近，就把它分到哪类。,2025/8/19 周二,四川大学、电气信息学院、余勤,22,例,3,：,内积分类器,（,相关分类器,）,有,假定 。利用线性判别函数,若进一步,假定每类的均值的模相等,，即,|,k,|,相等，它们分布在半径为,|,k,|,的一个超球面上，且由于假定,先验概率也相等,，因此，等价的判别函数为：,即将观测向量,x,和每类的均值,k,作内积（或称相关），然后选择值最大的,，作为它的类。,2025/8/19 周二,四川大学、电气信息学院、余勤,23,上述经典例子是通信理论中信号检测的一个例子。,假定有,N,c,种已知信号要检测。令,x,(,t,),表示接收到的信号，,m,k,(,t,),是,N,c,种已知的信号，,k,=1,，,2,，,，,N,c,。当,m,k,(,t,),发送时，加入了白噪声,w,(,t,),，,即：,白噪声,w,(,t,),是零均值、等方差、不相关的信号（随机过程）。即在任意时刻,t,i,，,w,(,t,i,),的均值为,0,，方差为 ，且当 时，,如果随机向量,x,和,m,k,是由相应的时间函数取样而成，即,2025/8/19 周二,四川大学、电气信息学院、余勤,24,2025/8/19 周二,四川大学、电气信息学院、余勤,25,这是一个相关分类器（内积分类器）的模式识别问题。,假定,|,m,k,|,2,相等，即,要求,所有的信号具有相等的能量。,2025/8/19 周二,四川大学、电气信息学院、余勤,26,把接收到的信号和已知信号作相关,m,k,T,x,，然后选择相关最大的。作相关时通常通过一个,“,匹配滤波器,”,来实现。,选择最大的输出,匹配滤波器,1,匹配滤波器,2,匹配滤波器,N,c,2025/8/19 周二,四川大学、电气信息学院、余勤,27,在连续时，判别函数：,构造一个函数,g,k,(,t,),，使满足,g,k,(,T,t,)=,m,k,(,t,),，则,另外，,m,k,和,x,间的相关也可以通过一个线性滤波器的输出来实现。即滤波器的输出是相关值，而滤波器的单位冲激响应是 ，滤波器可由专门的仪器来作。,2025/8/19 周二,四川大学、电气信息学院、余勤,28,可以把上面的线性分类器的讨论再进一步。,在线性分类器,中，如果把向量在,的特征向量的坐标系下表示（作变换），并作比例变换使所有分量的方差变为,1,，这时。线性分类器将作,k,T,x,相关运算。在通信问题中，如果噪声信号是相关的，而且方差是变化的，那么最优的信号检测是使噪声变为不相关的，然后作相关或匹配滤波器运算。,2025/8/19 周二,四川大学、电气信息学院、余勤,29,小结,一些简单的决策理论。,最小错误率、风险、,Neyman,Pearson,似然比检验，只是阈值不同。,最小最大决策，当先验概率变化时，使最大的错误率最小。,序贯决策：测量的维数可变时，分析了阈值和错误率间的关系。在独立同分布的假定下分析了维数的期望值。,2025/8/19 周二,四川大学、电气信息学院、余勤,30,线性和二次分类器。,对于多类模式识别问题的判别函数。,讨论了最近距离分类和相关分类。,线性分类器是最容易实现的。然而，只在正态分布和等协方差的情况下，线性判别函数才是贝叶斯意义上最优的。,在通信系统的信号检测中，等协方差矩阵是合理的。但在不少应用场合，并不满足协方差矩阵相等,。,在设计正态分布、不等协方差的线性分类器，在设计非正态分布的线性分类器上有不少研究成果。当然，它们不是最优的。但简单易行，可以补偿性能上的损失。,Linear Discriminant AnalysisLDA,线性判别式分析法,利用线性判别函数设计两类分类器,This method particularly effective when the probability distributions of the feature variables are not known!,第四章,问题的起源,在前面一节中，我们讨论了两种形式的分类器，在,d,维空间内分析了它的判别边界。其中分类的参数如,A,、,b,、,c,和,T,都是确定的，如果模式满足高斯分布，那么分类器可以使错误率、最小风险或者,Neyman,Pearson,准则最小。,但在某些情况下，不知道类条件密度函数，因此不可能找出最佳分类器。,在另些情况下，虽然可以对类条件密度进行估计，但推导最优分类器的计算量太大。,步骤如下：,给定某个线性判别函数类,g(,x,),利用样本集,X,确定判别函数类,g(,x,),中的未知参数(给定一个,cost function,用最优化方法使代价函数取极值),把未知样本,x,归类到具有最大的判别函数值的类别中,因此，实际工作中，,更需要先假定一种分类器的数学形式，,如线性或二次分类器，,然后确定它的参数，使它能最优某种适当的准则函数，如分离性等。,在一般情况下，这种准则函数不一定是错误率，而是更加简单和易于分析的。,用判别函数分类的概念,用判别函数进行模式分类依赖的两个因素,（1）,判别函数的几何性质：线性的和非线性的函数。,线性的是一条直线；,非线性的可以是曲线、折线等；,线性判别函数建立起来比较简单（实际应用较多）；,非线性判别函数建立起来比较复杂。,（2）,判别函数的系数：判别函数的形式确定后，主要就是确定判别函数的系数问题。,只要被研究的模式是可分的，就能用给定的模式样本集来确定判别函数的系数,线性判别函数的给定,一般线性判别函数,:,Example1:,线性判别函数,分类问题,多类情况1,判别函数,图例,例子,线性判别函数,分类问题,多类情况2,判别函数,图例,例子,Example2:,多类情况1和多类情况2的比较,对于,M,类模式的分类，多类情况1需要,M,个判别函数，而多类情况2需要,M*(M-1)/2,个判别函数，当,M,较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。,采用多类情况1时，每一个判别函数都要把一种类别的模式与其余,M-1,种类别的模式分开，而不是将一种类别的模式仅于另一种类别的模式分开。,由于一种模式的分布要比,M-1,种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。,广义线性判别函数,:,结论:,对任意判别函数作级数展开，然后取其截尾部分的逼近,通过适当的变换，都可以化为广义线性判别函数来处理.,解决由样本集设计线性分类器的主要步骤,:,令,任务是要确定 和 。,表示,X,在,V,方向上的投影。投影后的均值 和方差 是衡量类可分性的一个准则。,我们首先讨论从,d,维空间到一维空间的一般数学变换方法。,投影 比 要好。投影后的均值 和方差 是衡量类可分性的一个准则。,令 是任一准则函数（要最大或最小的），要确定使,f,最大（小）的,v,和,v,0,。,由于,代入，有：,由以上两式可以计算出,v,，,但由于错误率只依赖,v,的方向,，而不是它的大小。因而可以消去,v,的常数系数（不是,m,i,和,i,的函数）。,解出：,式中，,注意，上面得出的,v,和,f,无关，,f,只是出现在,s,中。,回想在正态、等协方差的情况下，有,这里是用,s,和(1,s,),对,1,和,2,作加权平均。当,f,的具体形式给出后，,v,0,是,的解。,准则函数的选取,Fisher,线性准则函数：,线性分类器的形式：,寻找分类器的参数，能够使以下的,Fisher,准则函数最大：,式中,希望使投影后两类的均值离得越开越好，而方差尽可能的小。,回想一下，若有,即,这时,g,(,x,)（,分类器的输出）的均值和方差为,Fisher,准则函数,和参数,c,无关（相减），因此,c,可以包括到阈值,T,里去。因此只要找出,b,就可以了。对准则函数求导并令其等于0，有,（,4-32,）,把项 放到阈值里去：,这样分类器的形式就成为：,当,1,=,2,=,时，4-32）式的,b,和（3.9,）,的,成比例。这样，当模式满足高斯分布，且协方差矩阵相等时，使,Fisher,准则最优等价于最小错误率最优。,(3-2)线性、二次分类器第17页,例,1,：,Fisher,线性分类器,。,因此,s,0.5,最佳的,Fisher,准则不依赖于,v,0,。,因为,v,0,从 和 相减中消失了。,例,2,：另种准则是,解出后有,Fisher,准则不能确定,v,0,。,感知准则函数,(,应用于线性可分的样本集,),原理:,一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。,在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。,感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。,采用感知器算法(,Perception Approach),能通过对训练模式样本集的,“,学习,”,得到判别函数的系数,。,这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。,感知器算法的收敛性,只要模式类别是线性可分的，就可以在有限的迭代步数里求出,权向量,（,判别函数的系数,）。,?,设:样本集,Y=y,1,y,2,y,N,为对应于,X=x,1,x,2,x,N,的增广样本集.,感知准则函数,当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。,如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。,对错误分类的模式则“罚”，使 加上一个正比于 的分量。,该算法实质上是一种赏罚过程,对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。,只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。,若模式不是线性可分的，算法的结果就会来回摆动，得不到收敛。,权空间,若将直线方程,x,1,w,1,+x,2,w,2,+w,3,=0,绘在权向量,w=(w,1,w,2,w,3,),T,的三维空间中，则,x=(x,1,x,2,1),T,为方程的系数。,若以,x,向量作为法线向量，则该线性方程所决定的平面为通过原点且与法线向量垂直的平面，它同样将权空间划分为正、负两边。,在系数,x,不变的条件下，若,w,值落在法线向量离开平面的一边，则,w,T,x0，,若,w,值落在法线向量射向平面的一边，则,w,T,x 0,的解区,B,为,T,y,n,b,的解区,则:对任意,B,必有,A,即有:,A,包含,B.,即新解区,B,位于原解区,A,之中.,设:,A,为,A,解区边界上的点,则,A,满足:,A,T,y,n,=0.,B,为,B,解区边界上的点,则,B,满足:,B,T,y,n,=b.,B,解区,边界离开,A,解区,边界的距离,|,B,-,A,|,为:,B,T,y,n,-,A,T,y,n,=b,B,T,-,A,T,=b/y,n,|,B,-,A,|=b,/,|y,n,|,作业,用感知器算法求下列模式分类的解向量,w,:,1,:(0 0 0),T,(1 0 0),T,(1 0 1),T,(1 1 0),T,2,:(0 0 1),T,(0 1 1),T,(0 1 0),T,(1 1 1),T,编写求解上述问题的感知器算法程序。,最小错分样本数准则,引子:,感知准则函数及其梯度下降算法只适用于线性可分情况，对于线性不可分情况，算法不收敛但在实际问题中往往无法事先知道样本集是否线性可分.因此，我们希望找到一种既适用于线性可分情况，又适用于线性不可分情况的算法。这种算法对于线性可分问题，可以得到一个如感知准则函数那样的解向量，使得对两类样本集做到将全部样本正确分类；而对于线性不可分问题，则得到一个,使两类样本集错分数目最少,的权向量.我们把这样的准则称为最小错分样本数准则,。,最小错分样本数准则函数,I:,对于式(4-47)定义准则函数,I:J,q1,=|(Y,-b)-|Y,-b|,2,找满足:,min,J,q1,的,*.(,共轭梯度法),最小错分样本数准则函数,II:,对于式(4-45)定义准则函数,II:J,q2,=,(1+sgn(y,i,),找满足:,max,J,q2,的,*.(,搜索法),式中:,sgn(y,i,)=-1 if y,i,3，,窗口为一超立方体,超立方体体积为：,定义窗函数,(,u,),(,以原点为中心,棱长为1的超立方体,),(,u,)=,1,|,u,j,|,1/2,j=1,2,d,0,其它,当,x,i,落入,以,x,为中心,体积为,V,N,的超立方体内时,我们有：,否则，,(,u,)=0,因此，落入该超立方体内的样本数为：,结论：,Parzen,窗估计过程是一个内插过程，样本,x,i,距离,x,越近，对概率密度估计的贡献越大，越远贡献越小。,窗宽,h,N,对估计影响很大，应让,h,N,随,N,的不断增加而缓慢趋近于0,窗函数必须满足：,(,u,),0,(,u,),du,=1,u,(,u,),-,0,0,u,u,(,u,)=,1,|,u,j,|,1/2,j=1,2,d,0,其它,窗函数的选择,：,方窗函数,正态,窗函数：,指数窗函数：,其中：,N,个以为,x,i,中心的,函数的叠加取平均.,的幅值为,窗宽,h,N,对,的影响,前面推出:,令:,则:,h,N,大,N,(x),的幅值就小,x,i,离,x,就远(因为,x,i,要落入以,x,为中心的窗体内),就是,N,个宽度较大,函数值变化缓慢的,函数的叠加.,h,N,小,N,(x),的幅值就大,x,i,离,x,近,就是以,N,个样本,x,i,为中心的,尖峰函数的叠加.,x,x,1,x,2,x,3,x,x,1,x,2,x,3,例1：对于一个二类（,1,，,2,）,识别问题，随机抽取,1,类的6个样本,X,=(x,1,，x,2,，.x,6,),1,=(x,1,，x,2,，.x,6,),=(x,1,=3.2，x,2,=3.6，x,3,=3，x,4,=6，x,5,=2.5，x,6,=1.1),估计,P(x|,1,),即,P,N,(x),0,1,2,3,4,5,6,x,6,x,5,x,3,x,1,x,2,x,4,x,解：选正态窗函数,x,是一维的,上式用图形表示是6个分别以3.2，3.6，3，6，2.5，1.1为中心的丘形曲线(正态曲线)，而,P,N,(x),则是这些曲线之和。,由图看出，每个样本对估计的贡献与样本间的距离有关，样本越多，,P,N,(x),越准确。,讨论：由图看出,P,N,(x),随,N,h,1,的变化情况,当,N1,时，,P,N,(x),是一个以第一个样本为中心的正态形状的小丘，与窗函数差不多。,当,N16,及,N=256,时,h,1,0.25,曲线起伏很大，噪声大,h,1,1,起伏减小,h,1,4,曲线平坦，平均误差,当,N,时，,P,N,(x),收敛于一平滑的正态曲线，,估计曲线较好。,当,N=1、16、256、,时的,P,N,(x),估计如图所示,当,N1,时，,P,N,(x),实际是窗函数。,当,N16,及,N=256,时,h,1,0.25,曲线起伏大,h,1,1,曲线起伏减小,h,1,4,曲线平坦,当,N,时，,曲线较好。,讨论：,Parzen,窗估计,优点,由前面的例子可以看出，,Parzen,窗估计的优点是应用的普遍性。对,规则分布，非规则分布，单锋或多峰分布,都可用此法进行密度估计。,可以获得较为光滑且分辨率较高的密度估计，实现了光滑性和分辨率之间的一个较好平衡。,缺点,要求样本足够多，才能有较好的估计。因此使计算量，存储量增大。,窗宽在整个样本空间固定不变，难以获得区域自适应的密度估计。,识别方法,保存每个类别所有的训练样本；,选择窗函数的形式，根据训练样本数,n,选择窗函数的,h,宽度；,识别时，利用每个类别的训练样本计算待识别样本,x,的类条件概率密度：,采用,Bayes,判别准则进行分类。,在,Parzen,窗口法中存在一个问题是对,h,N,的选择问题。,若,h,N,选太小，则大部分体积将是空的（即不包含样本），从而使,P,N,(x),估计不稳定。若,h,N,选太大，则,P,N,(x),估计较平坦，反映不出总体分布的变化，而,K,N,近邻法的思想是以,x,为中心建立空胞，使,v，,直到捕捉到,K,N,个样本为止。,称,K,N,-,近邻估计,v,的改进，样本密度大，,V,N,;,样本密度小，,V,N,;,P(x),的估计为：,K,N,nearest-neighbourhood approach,在,x,点周围选择一个体积,V,N,让,V,N,不断增长直至捕获,k,N,个样本为止,(这些样本为,x,的,k,N,个近邻),注意事项:,k,N,不要增长太快,以使随,N,的增加捕获,k,N,个样本的体积,V,N,不致于缩小到0,k,1,的选取要使,k,N,1,k,N,近邻法的基本估计公式:,基本思想,:,让,k,N,为,N,的函数(,例如,:,k,1,为大于0的常数),使,P,N,(x),收敛于,P(x),的充分必要条件：,，,N,与,K,N,同向变化,，,K,N,的变化远小于,N,的变化,V,1,为,N=1,时的,V,N,值,K,N,近邻估计对,K,N,和,V,N,都作了限制,N,个样本中有,K,N,个落入,V,N,内，,K,N,个样本内有,K,i,个样本属于,i,类,K,N,近邻法作后验概率的估计,由,K,N,近邻估计知:“,N,个已知类别样本中有,K,N,个落入,V,N,内”的概率密度估计为：,则联合概率密度：,根据,Bayes,公式可求出后验概率：,类别为,i,的后验概率就是落在,V,N,内属于,i,的样,本,k,i,与,V,N,内总样本数,K,N,的比值,K,近邻分类准则,：对于待分样本,x，,找出它的,k,个近邻，检查它的类别，把,x,归于样本最多的那个类别。,K,近邻分类的错误率随,K，P,k,最低的错误率为,Bayes,分类。,P,*,P,K,最近邻分类准则,：待分样本,x，,找一个离它最近的样本，把,x,归于最近的样本一类。,Bayes,P,P(e),K,近邻,最近邻,最近邻分类法则的错误率,P,比,K,近邻错误率还大,，但最大不会超过贝叶斯分类器错误率的二倍。,M,为类别数,P(e),为,Bayes,估计的错误率,错误率：,References,Yingquan Wu“Improved k-nearest neighbor classification”Pattern Recognition 35(2002)23112318(,Ramoni”Robust Bayes classifiers”Artificial Intelligence 125(2001)209226(,非线性判别函数,5.1 分段线性判别函数法,利用线性判别函数设计,多类分类器有多种方法.,例如，可以把,c,类问题化,为,c-,1个两类问题，其中,第,i,个问题是用线性判别,函数把属于类的点同不属,于类的点分开，,见图4.14(,a),问题的提出,多类分类器的设计,再麻烦一些的方法是用,c(c-,1)2个线性判别函数，把样本分为,c,个类别，每个线性判别函数只对其中的两个类别分类，如图4.14(,b),所示。,这两种方法都会产生如图中的阴影区域，对这个阴影区域中的点，无法确定其类别。,分段线性判别函数的基本概念,多类分类器的设计,用分段线性判别函数解决问题的思路,在各类中取,若干,个代表点（例,w,i,类就取,l,i,个代表点），代表点可以是,w,i,类样本的均值，也可以是属于,w,i,类的样本,将,w,i,类划分为,l,i,个子类,每个,子类包含1个代表点,每个,子类定义一个判别函数,多类分类器的设计,定义,w,i,类判别函数,决策规则：,决策面方程：,多类分类器的设计,解决问题的关键,如何确定各类的子类数目,l,i,?,如何求各子类的判别函数,?,多类分类器的设计,5.1.1,一种简单的基于距离的分段线性判别函数,多类分类器的设计,多类分类器的设计,5.1.3,分段线性分类器设计的一般考虑,设计线性分类器，就是确定权向量,和阀值权 或广义权向量,。,而设计分段线性分类器，则是利用样本集确定一组 和,已知样本的子类划分情况,:,把子类看作独立的类，然后利用线性判别函数算法把各个子类分开，自然也就把各类分开了这种方法必须以,已知子类划分,为前提划分子类的一种方法是根据先验知识直观判定.如字符识别中，可把同一字符看作一类，而把其中不同的字体看作它的不同于类另一种方法则借助于聚类分析方法来解决。,多类分类器的设计,已知子类数目,l,i,，但不知子类划分情况时,未知子类数目(,这是一般的情况),在这种情况下,设计分段线性分类器的方法很多,在这里我们仅举一例:,树状分段线性分类器,.对于图5.5所示的两类情况,先用两类线性判别函数算法找一个权向量,1,，它所对应的超平面,H,1,把整个样本集分成两部分,我们称之为样本子集.由于样本集不是线性可分的,因而每一部分仍然包含两类样本.接着,再利用算法找出第二个权向量,2,第三个权向量,3,超平面,H,2,H,3,分别把相应的样本子集分成两部分.若每一部分仍然包含两类样本,则继续上述过程,直到某一权向量(如图中,4,)把两类样本完全分开为止.这样得到的分类器显然也是分段线性的，其决策面如图中粗线所示.表示权向量,i,方向,它指向超平面,H,i,的正侧.它的识别过程是一个树状结构,如图5.6所示.图中用虚线显示了对未知样本,y,的决策过程，经过三步，判断,y,w,1,。,多类分类器的设计,需要指出,这种方法对初始权向量的选择很敏感，其结果随初始权向量的不同而大不相同.此外，在每个节点上所用的寻找权向量,i,的方法不同.结果也将各异.通常可以选择,分属两类的欧氏距离最小的一对样本,，取其垂直平分面的法向量作为,1,的初始值然后求得局部最忧解,1,*,作为第一段超平面的法向量对包含两类样本的各子类的划分也可以采用同样的方法,5.2,基于,凹函数的并,的分段线性判别函数（针对多峰情况,）,设,L,i,为线性判别函数，,i,=1,2,.r,则：,(,a)：,L,1,L,2,L,r,都是分段线性判别函数,(,b)：,若,A,B,都是分段线性判别函数，则：,AB，AB,也是分段线性判别函数。,AB,取最小，,AB,取最大。,(c)：,对任何分段线性函数都可以表示成如下二种形式：,1)、析取范式(这是经常采用的形式),P=(L,11,L,12,L,1m,)(L,q,1,L,q,2,L,q,m,),2)、,合取范式,Q=(L,11,L,12,L,1m,)(L,q,1,L,q,2,L,q,m,),每个,(L,i1,L,i2,L,im,),都称为凹函数。,对于多峰二类问题：设第一类有,q,个峰，则有,q,个凹函数。,即,P=P,1,P,2,P,q,每个凹函数,P,i,由,m,个线性判别函数来构成。,P,i,=L,i,1,L,i,2,L,i,m,假设对于每个子类线性判别函数,L,ij,都设计成：,例、设如图,P=(L,11,L,12,L,13,L,14,L,15,)(L,21,L,22,L,23,L,24,)(L,31,L,32,L,33,L,34,),5.3 用交遇区的样本设计分段线性分类器,-,一种实现最少分段线性分类器的方法,交遇区,当两类样本非线性可分时,贝叶,斯分界面一般通过两类样本十分,靠近或相互交迭的区域,我们称,之为,“,交遇区,”,如图5.10所示.,其中,a,c,是交迭区,b,是靠近区,局部训练法,把这些区域找出来，利用这些,区域中的样本作为新的样本集,设计线性判别函数，然后把它,们连在一起，就构成了一个分,段线性判别函数.这种方法称,为,“,局部训练法,”,多类分类器的设计,(1)如何从样本集中找出,“,交遇区,”,；,(2)如何利用,“,交遇区,”,中的样本设计线性分类 器；,(3)如何进行分类决策。,多类分类器的设计,需要解决的问题:,prototype,5.4,二次判别函数,二次判别函数一般可表示成：,第六章 近邻法,最近邻法(,The nearest neighbor(NN)rule,),k,近邻法(,The,k,-nearest neighbor(,k,-NN)rule,),利用“代表点”设计分段线性分类器的,近邻法,设,:,样本集,X,N,=,x,1,x,2,x,N,中有,N,i,个样本来自,w,i,类.,代表点,:,将各类的全部样本作为该类的代表点,.即:,w,1,类有,N,1,个代表点,w,2,类有,N,2,个代表点,分子类,:,w,1,类划分,N,1,个子类,w,1,1,w,1,2,w,1,k,w,1,N,1,w,2,类划分,N,2,个子类,w,2,1,w,2,2,w,2,l,w,2,N,2,每个子类包含1个样本点,定义各子类的判别函数,:,w,1,k,g,1,k,(,x,)=|,x,-,x,1,k,|,k,=1,2,N,1,w,2,l,g,2,l,(,x,)=|,x,x,2,l,|,l,=1,2,N,2,定义各类的判别函数,:,g,i,(,x,)=min|,x,x,i,k,|,k,=1,2,N,i,方法一:最近邻法(,nearest-neighbor),x is unknown pattern,设,:,样本集,X,N,=,x,1,x,2,x,N,中有,N,i,个样本来自,w,i,类.,代表点,:,将各类的全部样本作为该类的代表点.即:,w,1,类有,N,1,个代表点,w,2,类有,N,2,个代表点,分子类,:,w,1,类划分,N,1,个子类,w,1,1,w,1,2,w,1,k,w,1,N,1,w,2,类划分,N,2,个子类,w,2,1,w,2,2,w,2,l,w,2,N,2,每个子类包含1个样本点,定义各子类的判别函数,:,定义各类的判别函数,:,6.1 最近邻法,(,nearest-neighbor),x is unknown pattern,第,i,类中各样本与,x,的最短距离,决策规则,:,最近邻法的错误率分析,:,我们定义最近邻法的,渐近平均错误率为,P,决策：,x,与离它最近的样本同类,一般来说最近邻法的错误率落在图中的阴影区域中,Nearest Neighbor classifiers,however,are extremely sensitive to,the features used.,为最近邻法选择最佳距离度量,见,P157158,证明,小结,参考资料:,KAZUO HATTOR“Effective algorithms for the Nearest Neighbor method in the clustering problem”Pattern Recognition,Vol26,No.5.pp.741-746.1993,I.K.Sethi“Hierarchical classifier design using mutual information”IEEE Trans.PA&MI pp441-445 1982,6.2 k,-,近邻法,The,k,-nearest neighbor(,k,-NN)rule,.,代表点,:,x,的,k,个近邻,定义各类的判别函数,:,g,i,(,x,)=k,i,i=1,2,c,k,i,为,x,的,k,个近邻中属于,w,i,类的样本点的个数,.,决策规则,:,if,g,j,(,x,)=max g,i,(,x,)i=1,2,c,then,x,w,j,如何选取合适的,k,值？,6.3,近邻法的快速算法,基本思想：,将样本集分成多个子集（树状结构）；,每个子集（结点）包含少量样本；,将待识别样本与各结点比较排除大量候选样本；,只在最后的结点中逐个样本比较，找出最近邻,基本算法：,分支定界算法（,Branch-Bound Algorithm),6.3.1,分支定界算法（,Branch-Bound Algorithm),prototype,6.3.2,剪辑近邻法,基本思路：,6.3.3 压缩近邻法,参见：,Yingquan Wu,Krassimir Ianakiev,Venu Govindaraju,“,Improved k-nearest neighbor classification,”,Pattern Recognition 35(2002)2311,2318,2025/8/19 周二,173,特征空间的线性降维法,特征空间分解,特征提取,提取分类信息,分类信息压缩等,2025/8/19 周二,174,特征形成：,根据被识别的对象产生出一组基本特征用以描述被识别的对象。,几个术语,它可以是计算出来的(当识别对象是波形或数字图像时)，也可以是用仪表或传感器测量出来的(当识别对象是实物或某种过程时)，这样产生出来的特征叫做原始特征，有些书中用原始测量(或一次测量)这一名词，在很多情况下有些原始测量就可以作为原始特征，而有些情况则不然，例如识别对象 是数字图像时，原始测量就是各点灰度值，但很少有人用各点灰度作为特征，需要经过计算产生一组原始特征。,2025/8/19 周二,175,特征提取,：把处于高维空间中的样本，通过映射(或变换