非线性支持向量机PPT课件

《非线性支持向量机PPT课件》由会员分享，可在线阅读，更多相关《非线性支持向量机PPT课件（56页珍藏版）》请在金锄头文库上搜索。

1、数据挖掘原理与SPSS Clementine应用宝典 元昌安 主编 邓松李文敬刘海涛编著 电子工业出版社2 214.1支持向量机基础机器学习的基本问题经验风险最小化问题14.1.3 VC维与学习一致性理论结构化风险最小化14.2支持向量机的基本原理线性支持向量机广义线性支持向量机非线性支持向量机到高维空间的影射核函数14.3支持向量机的实现技术14.3.1 chunking算法14.3.2 Decomposing算法14.3.3 SMO算法14.3.5 SMO算法的特点和优势14.4支持向量回归机不敏感损失函数支持向量回归机模型14.5支持向量机的改进算法数据挖掘原理与SPSS Clement

2、ine应用宝典 元昌安 主编 邓松李文敬刘海涛编著 电子工业出版社14.1支持向量机基础支持向量机(support vector machines)是由贝尔实验室研究者Vapnik于20世纪90年代最先提出的一种新的机器学习理论，是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力。 支持向量机从诞生至今才10多年，发展史虽短，但其理论研究和算法实现方面却都取得了突破性进展，有力地推动机器学习理论和技术的发展。这一切与支持向量机具有较完备的统计学习理论基础的发展背景是密不可分的。 统计方法是从事物的外在数

3、量上的表现去推断该事物可能的规律性，它主要考虑测试预想的假设和数据模型拟合，依赖于显式的基本概率模型。 统计学习理论是针对小样本情况下的机器学习理论，它依据算法的经验风险以及算法本身的构造推测它的实际风险，获得了较好的算法泛化能力。统计学习理论将算法的训练过程看作算法向训练样本学习的过程。 统计学习理论的4个部分：1.学习过程一致性的理论。一个基于经验风险最小化原则的学习过程满足什么条件，它的经验风险与实际风险趋向一致。2.学习过程收敛速度的理论。如果学习过程的经验风险与实际风险趋向一致，那么它们间的接近速度随着训练样本数的增加是如何变化的。哪些因素控制着它们接近的速度。3.控制学习过程泛化能

4、力的理论。采用前两部分的结论改进学习过程。4.构造学习算法的理论。采用前三部分的结论，在分类和拟合问题中构造现实的学习算法。机器学习的基本问题统计学习理论领域里把学习问题看作是利用有限数量的观测来寻找待求的依赖关系的问题。而基于数据的机器学习问题，则是根据已知样本估计数据之间的依赖关系，从而对未知或无法测量的数据进行预测和判断。样本学习的一般模型xySLMG可见，学习问题就是从给定的函数集 ，选择出能够最好地逼近训练器响应的函数。机器学习的目标可以形式化的表示为：根据n个独立同分布的观测样本，在一组函数中求出一个最优函数，使其对未知样本进行估计时，最小化期望风险泛函。其中联合概率分布是未知的，

5、是用对y进行预测时造成的损失，称为损失函数。简单地说，学习的目标就是求一映射函数，使之与实际系统映射的差异最小。 经验风险最小化问题学习机器产生的映射函数与实际系统的映射之间的差异可以用单个样本点上的损失函数来描述 。损失函数在总体样本集上的数学期望，即为期望风险的泛函： 损失函数描述了映射函数与实际系统在总体集上的差异，将学习的目标变成了最小化期望风险。在实际的问题中，无法直接的计算得到。 在传统的机器学习方法中，通常将经验风险作为期望风险的估计值，学习的目标就是使经验风险Remp最小，强调利用经验风险最小化（ ERM ）原则进行学习。但实际上，用ERM原则代替最小化期望风险泛函，只是直观上

6、合理的想当然做法而已，理论依据并不充分，容易“过学习”(overfitting)。 underfittingoverfittinggood fit14.1.3 VC维与学习一致性理论对于二值分类问题，其目标函数f只有0和1两种取值，称这类函数为指示函数。对于一个指示函数集的VC维是指能够被“打散”(即，被里的函数按照所有可能的形式分开)的样本集合可能具有的最大样本数(或称作样本集合的最大基数)，记作。一般而言，VC维代表了机器的学习能力，其值越大表明其学习机器的学习能力越强，但学习机器就越复杂。然而，目前还没有通用的关于计算任意函数集的VC维的理论，只有对一些特殊函数集的VC维可以准确知道。

7、对于指示函数集和概率分布函数，如果下列两序列概率地收敛到同一极限，则称为经验风险最小一致性。图14-3 经验风险最小一致性在VC维和学习一致理论基础上，Vapnik等人证明了对二值分类问题，指示函数集中所有的函数，经验风险和实际风险之间至少以概率满足如下关系:其中，是函数集的VC维，n是样本数。上式实质上给出了ERM原则的泛化能力的界。在此基础上，Vapnik等人从理论角度解释了机器学习中的过学习问题，并建立起适用于小样本数据的结构风险最小化原则。上式中的界由两部分组成：经验风险（即训练误差）和置信范围 (Confidence Interval)。结构化风险最小化通常，在小样本的情况下，对于复

8、杂的学习机器，其训练误差过小，但反而造成了置信范围的增大，从而导致泛化性能下降。这往往是由于学习机器的结构不合理造成的。因此，ERM原则在样本有限时是不合理的。为此，统计学习理论提出了一种新的策略，在保证ERM原则的基础上，降低学习机器的VC维，能够使得期望风险在整个总体集上得到控制，即在训练误差和置信范围二者之间寻求一个折衷。这种思想就是结构风险最小化(Structural Risk Minimization，SRM)原则。图14-4 结构风险最小化原则最小化算法的经验风险与置信范围之和(而不仅仅是最小化经验风险)被称作结构风险最小化原则。 实现SRM原则可以有两种思路：1.对函数集S的每个

9、子集Si求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集；2.设计函数集的某种结构使每个子集中都能取得最小的经验风险，如使训练误差为0,然后只需选择适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是最优函数。 14.2支持向量机的基本原理基本概念1.一般地，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。 如果不关注函数空间的维数，这种线性函数还有一个统一的名称，叫超平面（Hyper Plane）。2.通常人们称由线性函数作为分类决策函数的分类器叫线性分类器。同样地，称由非线性函数作为分类决策函数的分类器叫非线性分类器。相应地

10、，由线性函数作为分类决策函数的支持向量机称为线性支持向量机，反之，由非线性函数作为分类决策函数的支持向量机称为非线性支持向量机。 线性支持向量机 一个二值分类问题：设线性可分样本集 (x1,y1), (x2,y2),(xm,ym), xRn,y+1,-1是类别标号，X为具有个属性的向量。要求在上找，得到决策函数，这就是分类学习机器。在2维线性空间中线性判别函数的一般形式为： 。其中，最优分类线L的方程的规范化形式为：其几何表示如下图：L1L2L分类直线示意图 由直线间的距离公式可证：L1与L2之间的距离为：，并且使训练集中的点距离分类线尽可能的远，也就是寻找一个分类线使它两侧的空白区域(mar

11、gin)最大 。 进一步推广到n2时，则同样存在超平面，其中xRn,w,bRn。使得样本集中的任意二元组(xi,yi)，满足: 当 时 当 时可以统一起表示为: 其中，满足上式的超平面就是分类超平面（Seperating Hyperplane）。在样本线性可分时，存在无数个这样的超平面。R2的线性可分情况如图14-6所示： 图14-6 分类超平面示意图 图14-7 最优分类超平面图使间隔margin最大实际上等价于使最小。因此，满足上述条件且使最小的分类超平面就是最优分类超平面。两类样本中离分类面最近的点且平行于最优分类超平面的样本点叫做支持向量。 最优分类超平面最后可以表示成一个约束优化问题

12、： 这是一个严格凸规划问题，可以转换成拉格朗日(Lagrange)问题进行求解。为此，可以定义如下的Lagrange函数： 其中为Lagrange乘子。 由Karush-Kuhn-Tucker (KKT)条件，上式所示的函数在其鞍点位置满足：(14-2-8)将上式代入(14-2-6)，消去w和b得到原问题的Wolf对偶（Dual）问题：s.t 这是一个标准的二次规划问题，是在一个不等式约束条件下进行二次函数寻优。该类问题存在唯一解。 计算 ，选择 的一个正分量 , 并据此计算事实上， 的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关

13、。其中 不为零的这些训练点的输入 为支持向量(SV)构造分划超平面 ,决策函数根据最优解对于近似线性可分问题不要求所有训练点都满足约束条件 ，为此对第 个训练点 引入松弛变量(Slack Variable) ,把约束条件放松到 。 体现了训练集被错分的情况，可采用 作为一种度量来描述错划程度。两个目标：1. 间隔 尽可能大 2. 错划程度 尽可能小（即“软化” 约束条件）广义线性支持向量机因此，引入一个惩罚参数 ，新的目标函数变为: 体现了经验风险，而 则体现了表达能力。所以惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。当 时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。

14、 显然，当 充分大时，样本点 总可以满足以上约束条件。然而事实上应避免 太大，所以需在目标函数对 进行惩罚( (广义广义) )线性支持向量分类机算法线性支持向量分类机算法1. 设已知训练集 ，其中 2. 选择适当的惩罚参数 ，构造并求解最优化问题 求得3. 计算 ，选择 的一个分量 ，并据此 计算出 4. 构造分划超平面 ,决策函数非线性支持向量机在实际应用中，一般的分类问题在定义的特征空间中并不一定线性（或近似线性）可分的。例 对于线性不可分的情况或近似不可分的情况，通常的做法是把未知问题转化为已知问题，也就是转化为线性可分的情况。对于这类问题，我们可以考虑通过一个非线性映射，将低维输入空间

15、中的数据特征x映射到高维线性特征空间F中，然后在高维空间中求线性最优分类超平面，将分类问题转换到特征空间中进行， T: RNP xF(x) 然后用前面介绍的广义最优分类面方法加以解决。 设训练集 ，其中假定可以用 平面上的二次曲线来分划： 现考虑把2维空间 映射到6维空间的变换上式可将2维空间上二次曲线映射为6维空间上的一个超平面：可见，只要利用变换，把 所在的2维空间的两类输入点映射到 所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：最后得出原空间中的二次曲线：怎样求6维空间中的分划超平面？(线性支持向量分类机)需要求解的最优化问题其中在求得最优化问题的解 后，得到分划超

16、平面其中最后得到决策函数或 线性分划非线性分划代价：2维空间内积6维空间内积为此，引进函数有比较(2)和(3)，可以发现这是一个重要的等式，提示6维空间中的内积可以通过计算 中2维空间中的内积 得到。实现非线性分类的思想：给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换，如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数 ，一旦选定了函数，就可以求解最优化问题得最优解 ，因而决策函数其中设 是 中的一个子集。称定义在 上的函数 是核函数(正定核或核)，如果存在着从 到某一个空间 的映射使得其中 表示 中的内积核函数非线性SVM的泛化性能和算法的复杂度取决于支持向量的数目，而与特征空间的维数无关。这种非线性SVM的分类函数（SVC）形式上类似于神经网络，其输出层是由若干中间结点组成，每个结点对应于输入样本点与一个SV的内积，因而也被称为支持向量网络(SV Networks)，如下图所示。 支持向量网络示意图 多项式内核径向基函数内核RBFSigmoind内核目前研究最多的核函数主要有三类：得到q 阶多项式分类器每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定包含