非参数判别分类方法.ppt

《非参数判别分类方法.ppt》由会员分享，可在线阅读，更多相关《非参数判别分类方法.ppt（31页珍藏版）》请在三一办公上搜索。

1、2023/9/16,中国矿业大学 计算机科学与技术学院,(31)1,3.7 支持向量机,Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(Support Vector Machine,简称SVM)。,在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况。,支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，要用到以不等式作为必须满足的条件

2、，此时我们只要了解拉格朗日理论的有关结论就行。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)2,3.7.1 线性可分条件下的 支持向量机最优分界面,SVM的思路,隔离带,支持向量,最大间隔准则,最优分类面示意图,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)3,训练样本集表示成 xi,yi,i=1,N,其中xi为d维向量，也即特征向量，而yi-1，+1，即用yi是+1或-1表示其类别。,最大间隔准则,并且令,对在H1与H2平面上的点，上两式取等号。上两式也可合并成,对于分界面H表示成：,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)4,H

3、1平面到坐标原点的距离为：,H1到H2的间隔为：,最大间隔准则,H2平面到坐标原点的距离为：,因此欲达到Vapnik提出的使间隔最大的准则，则应使 最小。,其约束条件为：,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)5,按这个理论构造拉格朗日函数的原则为：目标函数减去用拉格朗日乘子(乘子值必须不小于0)与约束条件函数的乘积。,最大间隔准则的问题可写成：,KKT条件：目标函数是二次函数，而约束条件为线性函数，按拉格朗日理论该问题存在唯一解。,扩展的拉格朗日乘子理论,目标函数：,(3.7-1),2023/9/16,中国矿业大学 计算机科学与技术学院,(31)6,只有满足yi(W

4、TXi+W0)-1=0 条件的点，其拉格朗日乘子才可能不为零；而对满足yi(WTXi+W0)-10的样本数据来说，其拉格朗日乘子必须为零。,唯一解的充分必要条件,显然只有部分(经常是少量)的样本数据的ai不为零，而线性分界面的权向量W则是这些ai不为零的样本数据的线性组合，ai不为零的样本数据也因而被称为支持向量。,(3.7-2),(3.7-3),(3.7-4),(3.7-5),(3.7-6),2023/9/16,中国矿业大学 计算机科学与技术学院,(31)7,最佳的权向量,最佳的权向量W就是这些支持向量数据的线性求和。,(3.7-7),2023/9/16,中国矿业大学 计算机科学与技术学院,

5、(31)8,求解,为了求出最佳的ai，拉格朗日理论中引入一种对偶函数，与L(W,a)式相对偶的函数的构造方法是：对L(W,a)分别求它对W及w0的偏微分，并置为零，然后再代回到L(W,a)式中，从而得到：,通过求L(W,a)式的极大值来求解。,(3.7-8),拉格朗日理论证明：满足上述条件(3.7-2)到(3.7-6)时，找(3.7-8)式极大值的解就是(3.7-1)式的条件极小值，因此由(3.7-8)可求得各个最佳值，代入(3.7-7)即可得到，在W确定之后w0值也可利用(3.7-5)对某个 的数据求出。,对(3.7-8)式的来源不要求弄懂，只需知道，它的极大值解与(3.7-1)式的极小值解

6、是一致的就行了。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)9,3.7.2 线性不可分条件下的 广义最优线性分界面,对于线性不可分的情况下，如果仍要使用线性分界面，则必然有部分训练样本向量被错分。,保留求最宽隔离带的框架，但允许有些数据能进入隔离带，甚至到对方的决策域中。但是对这部分数据的数量要严加控制。,为了实行控制，增加一种起缓冲作用的量，i(i 0)称为缓冲量，此时,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)10,线性不可分条件下的广义最优线性分界面,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)11,线性不可分条件下的广义最

7、优线性分界面,目标函数可写为,拉格朗日函数,(3.7-11),比较线性可分条件下的拉格朗日函数,(3.7-1),2023/9/16,中国矿业大学 计算机科学与技术学院,(31)12,由于(3.7-11)仍满足KKT条件，因此唯一解的充要条件是,线性不可分条件下的广义最优线性分界面,(3.7-12),(3.7-13),(3.7-14),(3.7-15),(3.7-16),(3.7-17),(3.7-18),(3.7-19),问题：思考一下，这一堆式子与线性可分条件下的解相比，哪些式子是增加的？哪些式子略有改变？,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)13,(3.7-2)

8、,(3.7-3),(3.7-4),(3.7-5),(3.7-6),线性不可分,线性可分,(3.7-12),(3.7-13),(3.7-14),(3.7-15),(3.7-16),(3.7-17),(3.7-18),(3.7-19),答：(3.7-14)是增加的，它对ai的值有了限制。(3.7-17)是增加的，(3.7-19)是增加的，它们都与i有关。(3.7-12)，(3.7-18)及(3.7-13)没有明显变化。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)14,很有意思的是(3.7-11)式的对偶形式按拉格朗日理论构造出来与(3.7-1)式完全一样:,(3.7-20),

9、因此可以看到在线性不可分条件下，硬要用线性分类器，因此必然有的样本会被错分类，表现出来就是走到线性分界面另一类样本的区域。这样一来，对这些错误的总量要加以控制，目标函数就从 变成增加缓冲项。,目标函数变了，但使用拉各朗日乘子方法的框架不变，因此原理上两者没有什么不同，只是要控制的量增加了。一些细节不要求，只要弄清楚在线性不可分条件下的处理方法就行了。,(3.7-8),唯一的不同是由(3.7-14)式与(3.7-19)式联合的结果，应有,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)15,3.7.3 特征映射法、解决非线性判别分类问题,支持向量机采用的方法与前面提到的方法很不相

10、同，支持向量机提出的方法是利用特征映射方法，使非线性分类的问题可以利用线性分类的计算框架来实现。,原理示意图,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)16,广义线性判别函数,例：假设对一个二维空间的分类问题，想用一个二次函数作为判别函数，则二次曲线函数的一般式可写成,如果希望采用广义线性方程的方法，则可以定义,作为映射后的特征向量，而相应的广义权向量为,则生成一个新的线性方程为：,其中w0=f,这样一来，线性分类方法就可以直接采用。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)17,支持向量机利用特征映射的思想,(3.7-8),(3.7-7),回顾一

11、下支持向量机中的以下两个式子:,其中 是以下式子求极大值的解,计算上式的极大值只用到训练样本数据间的点积，而使用的分类器判别函数中权向量的作用也是通过权向量与样本的点积体现出来的，而从(3.7-7)式中看出来，权向量是训练样本中的支持向量的线性组合，因此WTX值的计算可写成,(3.7-21),2023/9/16,中国矿业大学 计算机科学与技术学院,(31)18,支持向量机利用特征映射的思想,式(3.7-21)表明在计算判别函数值时，仍然只需通过计算相应数据的点积即可。,(3.7-21),由此可以设想，如果我们将原特征向量用映射的方式转换成xif(xi)，则相应的式子只需改变成,(3.7-22)

12、,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)19,特征映射,由于特征进行了映射，从x变成了f(x)，因此问题是在另一个映射后的空间讨论的。,设原空间维数为d，即XRd，而新空间为m维，即f(X)Rm，则一般m维要比d维大得多。,权向量的维数也是m维，它是在映射后空间中的支持向量的线性求和:,但是支持向量机的提出者进一步发现，并不一定要求出这个权向量，因为分类判别函数中只关心权向量与样本向量之间的点积。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)20,(3.7-22),分类界面方程,(3.7-23),其中w0*为相应的常数项。,特征映射,选择了一种函数

13、k(a,b),其中a和b是原特征空间的两个数据点，那么只要这种函数是反映了特征映射后数据的内积，线性分类器的框架就都可以用了。,因此选择合适的函数k(,)就成为设计中的重要问题。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)21,与内积函数值等价的函数k(,)称为核函数。,核函数,理论上对核函数的充分必要条件进行了研究，并已得出一些主要结论(如Mercer条件)，但由于这些成果还不能具体地确定哪些函数具备这种条件，因此目前常用的核函数还局限于以下三种函数形式。,多项式类型的函数,高斯型式的函数,S形函数,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)22,

14、支持向量机计算示意图,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)23,一、参数判别分类方法与非参数判别分类方法的区别,本章小结,参数判别方法：它的前提是对特征空间中的各类样本的分布清楚，因此一旦要测试分类样本的特征向量值X已知，就可以确定X对各类的后验概率，也就可按相应的准则计算与分类。所以判别函数等的确定取决于样本统计分布的有关知识。,非参数判别方法：着眼于直接利用训练样本集，省去参数估计这一环节，这样一来，从保证最小错误率的原则出发计算确定判别函数的方法就不适用了。因此非参数分类判别方法只能根据一些其它准则来设计分类器。分类器的效果好坏，所选择的判别函数型式，所使用的

15、训练样本集，以及所用的算法对结果都会有影响。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)24,二、非参数分类判别方法的基本做法,非参数分类判别方法进行分类器设计主要包含两个步骤：,(1)确定要使用的判别函数类型或决策面方程类型，如线性分类器，分段线性分类器，非线性分类器等或近邻法等。如果使用人工神经元网络，则怎样的网络结构也隐含了所使用的函数形式。,(2)在选定的函数类型网络结构等条件下，确定相应的参数，从而完成整个分类器设计。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)25,三、决策面方程的显式表示和隐式表示,用函数直接表示分界面方程，如线性方程式

16、表示的边界等。,用隐含形式，例如用最小距离分类器就代表了这种类型，其实这两种形式是等价的。,本章学习的Fisher准则、支持向量机与局部训练法等用的是显式表示，而错误修正法和近邻法则可以说是隐式表示。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)26,四、基于相似度的分类判别方法,判别函数的隐式表示与使用基于相似度判别的原则有关。如近邻法是用距离远近表示相似程度，错误修正法用样本向量与增广权向量的点积运算，也可在一定程度上看作相似度。在多类问题上，往往用计算相似度较方便。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)27,五、Fisher准则,Fishe

17、r准则是传统模式识别方法中的典型方法，它强调将线性方程中的法向量与样本的乘积看作样本向量在单位法向量上的投影，如能做到不同类的样本在法向量上的投影呈现类内聚集，类间分开的效果，则对减少错分类有利。所得最佳法向量计算式为。这个结果与正态分布协方差矩阵等的贝叶斯决策结果相似，这说明如果两类分布围绕各自均值的确相近，Fisher准则可使错误率较小。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)28,六、感知准则函数方法,这种方法提倡用错分类提供的信息修正错误，这种思想对机器学习的发展以及人工神经元网络的发生发展产生深远影响。,七、近邻法,近邻法训练样本数量较多时，从渐近错误率角度

18、看，其错误率比较小，是经常使用的模式识别分类方法，比较适合在多类别情况下使用。当每类的样本数很多时，存储量与计算量要求都偏高，使用剪辑近邻法与压缩近邻法，特别是压缩近邻法可大量减少训练样本的数量。,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)29,八、支持向量机,支持向量机是新近提出的影响较大的方法。在理论上有很深的背景，这里指的理论是统计学习理论。,它主要关注的问题是：当训练样本数量有限时。在训练过程中做到使训练样本错误率为最小，是否就意味着系统在实际运用中，也能自然而然做到错误率小呢？,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)30,泛化能力,2023/9/16,中国矿业大学 计算机科学与技术学院,(31)31,统计学习理论,从我们所讨论的一些方法中,分类器设计的性能，都以对训练样本集有好的性能为目标，而没有办法保证在实际使用时仍能保持好的性能。支持向量机在线性可分时要求隔离带尽可能宽，正是从期望实际的错误率也较低这一点出发的。关于这一点需要很深的理论，我们只做一种浅显的解释。,对我们的实际应用来说，支持向量机可以通过特征映射方法,将原特征空间需要用非线性函数分类的问题，转换成在一个新的空间中仍然采用线性分类器的方法，使实际使用非线性分类器(而不是分段线性分类器)的可能性大大增加。这是一个很大的突破。,