任课教师评语：签名： 年 月 日南京理工大学课程考核课题课程名称： 数据挖掘与处理 课题题目： 支持向量机 组 长： 组 员： 陈志岩（912113850117） 成 绩： 支持向量机一、概述：支持向量机是数据挖掘中的一项新技术，是在统计学习理论基础上发展起来的一种新的数据挖掘方法，借助于最优化方法解决机器学习问题的新工具。统计学习理论是一种专门研究小样本情况下机器学习规律的理论，其主要内容包括以下四个方面：1、经验风险最小化准则下统计学习一致性的条件2、在这些条件下关于统计学习方法推广性的界的结论3、在这些界的基础上建立的小样本归纳推理准则4、实现新的准则的实际方法2、前期知识：SVM 的背景简介支持向量机(Support Vector Machine)是 Cortes 和 Vapnik 于 1995 年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力）。所谓 VC 维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。正是因为 SVM 关注的是 VC 维，我们可以了解到，SVM 解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得 SVM 很适合用来解决文本分类的问题，当然，有这样的能力也因为引入了核函数）。机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的。既然真实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。比如说我们认为宇宙诞生于 150 亿年前的一场大爆炸，这个假设能够描述很多我们观察到的现象，但它与真实的宇宙模型之间还相差多少？谁也说不清，因为我们压根就不知道真实的宇宙模型到底是什么。这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到 100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。此时的情况便是选择了一个足够复杂的分类函数（它的 VC 维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现，此原则适用的大前提是经验风险要确实能够逼近真实风险才行（行话叫一致），但实际上能逼近么？答案是不能，因为样本数相对于现实世界要分类的文本数来说简直九牛一毛，经验风险最小化原则只在这占很小比例的样本上做到没有误差，当然不能保证在更大比例的真实文本上也没有误差。统计学习因此而引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻画，一是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然，第二部分是没有办法精确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值（所以叫做泛化误差界，而不叫泛化误差）。置信风险与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的 VC 维，显然VC 维越大，推广能力越差，置信风险会变大。泛化误差界的公式为：R(w)R emp(w)+(n/h)公式中 R(w)就是真实风险，R emp(w)就是经验风险，(n/h)就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。SVM 正是这样一种努力最小化结构风险的算法。SVM 其他的特点就比较容易理解了。小样本，并不是说样本的绝对数量少（实际上，对任何算法来说，更多的样本几乎总是能带来更好的效果），而是说与问题的复杂度比起来，SVM 算法要求的样本数是相对比较少的。非线性，是指 SVM 擅长应付样本数据线性不可分的情况，主要通过松弛变量（也有人叫惩罚变量）和核函数技术来实现，这一部分是 SVM 的精髓，以后会详细讨论。多说一句，关于文本分类这个问题究竟是不是线性可分的，尚没有定论，因此不能简单的认为它是线性可分的而作简化处理，在水落石出之前，只好先当它是线性不可分的（反正线性可分也不过是线性不可分的一种特例而已，我们向来不怕方法过于通用）。高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过另一系列文章（文本分类入门）中提到过的降维处理，出现几万维的情况很正常，其他算法基本就没有能力应付了，SVM 却可以，主要是因为 SVM 产生的分类器很简洁，用到的样本信息很少（仅仅用到那些称之为“支持向量”的样本，此为后话），使得即使样本维数很高，也不会给存储和计算带来大麻烦。三、支持向量机：1、支持向量机定义：SVM 是一种准确度高的分类器，具有良好的容错和归纳能力，是一种建立在统计学理论的 VC 理论和结构风险最小原理基础上的，支持向量机技术是从线性可分情况下的最优分类面发展而来的。1.1 线性分类器线性分类器(一定意义上,也可以叫做感知机) 是最简单也很有效的分类器形式.在一个线性分类器中,可以看到 SVM 形成的思路, 并接触很多 SVM 的核心概念.用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示C1 和 C2 是要区分的两个类别，在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。什么叫线性函数呢？在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称 超平面（Hyper Plane）！实际上，一个线性函数是一个实值函数（即函数的值是连续的实数），而我们的分类问题（例如这里的二元分类问题 回答一个样本属于还是不属于一个类别的问题）需要离散的输出值，例如用 1 表示某个样本属于类别 C1，而用 0 表示不属于（不属于 C1 也就意味着属于 C2），这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。 例如我们有一个线性函数g(x)=wx+b我们可以取阈值为 0，这样当有一个样本 xi 需要判别的时候，我们就看g(xi)的值。若 g(xi)0，就判别为类别 C1，若 g(xi)0（记得么？这是因为我们所选的 g(x)=wx+b 就通过大于 0 还是小于 0 来判断分类），而 yi 也大于 0；若不属于该类别的话，那么 wxi+b表示向量 x1,x2的内积（也叫点积，注意与向量叉积的区别）。因此 g(x)的表达式严格的形式应该是：g(x)=+b但是上面的式子还不够好，你回头看看图中正样本和负样本的位置，想像一下，我不动所有点的位置，而只是把其中一个正样本点定为负样本点（也就是把一个点的形状从圆形变为方形），结果怎么样？三条直线都必须移动（因为对这三条直线的要求是必须把方形和圆形的点正确分开）！这说明 w 不仅跟样本点的位置有关，还跟样本的类别有关（也就是和样本的“标签”有关）。因此用下面这个式子表示才算完整：w= 1y1x1+ 2y2x2+ nynxn（式 1）其中的 yi就是第 i 个样本的标签，它等于 1 或者-1。其实以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于 0（不等于 0 才对 w 起决定作用），这部分不等于 0 的拉格朗日乘子后面所乘的样本点，其实都落在 H1 和 H2 上，也正是这部分样本（而不需要全部样本）唯一的确定了分类函数，当然，更严格的说，这些样本的一部分就可以确定，因为例如确定一条直线，只需要两个点就可以，即便有三五个都落在上面，我们也不是全都需要。这部分我们真正需要的样本点，就叫做支持（撑）向量！但肯定有人会说，这并没有把原问题简化呀。其实简化了，只不过在你看不见的地方，以这样的形式描述问题以后，我们的优化问题少了很大一部分不等式约束（记得这是我们解不了极值问题的万恶之源）。但是接下来，看看 SVM 在线性分类器上所做的重大改进 核函数。3、核函数：之前一直在讨论的线性分类器,器如其名，只能对线性可分的样本做处理。如果提供的样本线性不可分，结果很简单，线性分类器的求解程序会无限循环，永远也解不出来。这必然使得它的适用范围大大缩小，而它的很多优点我们实在不原意放弃，怎么办呢？是否有某种方法，让线性不可分的数据变得线性可分呢？ 这时候，我们便需要核函数方法来解决问题。核函数方法就是用非线性变换可以利用核来把数据映射到特征空间，并且在这个空间训练线性机器，能够利用的训练样本的唯一信息是它们在特征空间的 Gram 矩阵。这个矩阵也称为核矩阵，用 K 表示。核函数为支持向量机提供了一个重要的构成模块，常用的核函数有多项式函数、径向基函数和 Sigmoid 函数等，在选用不同的核函数时可以构造出不同的支持向量机。多项式核函数：选用下列核函数 ，构造的支持向量机的判2(,)(,)1iiKx别函数为： 2*1()sgn(,)iifxayxb其中， 为支持矢量的个数。s径向量核函数：选用下列核函数 ，构造的支持向量2(,)ep|/i iKxx机的判别函数为： 2*1()sgne|/i ifxaxb其中， 个支持矢量 可确定径向基函数的中心位置， 是中心的数目。径向基si s函数所对应的特征空间可以是无穷维数，因此理论上讲，一切有限的数据样本在该特征空间中肯定是线性可分的。Sigmoid 函数：选用下列核函数 ，构造的支持向量机(,)tanh()i iKxvxa的判别函数为： *1()sgntah()iifxvxab其为三层神经网络的判别函数，其隐节点数目、隐节点对输入节点的权重矢量， 和输出节点对隐节点的权重 都是在模型训练过程中自动确定的。vixi4、支持向量机回归的实现如果将估计指示函数中得到的结论推广到实函数（回归）中，就变成了支持向量机回归。对于线性回归，考虑用线性回归函数 ()fxwb估计数据 12(,),(,)(,),ilixyxyyR 假定存在函数 在 精度能够估计所有的 数据，那么寻找最小 的问fix题可以表示成凸优化问题 ，约束条件如下：21minwiiyxb为了处理函数 在 精度不能估计数据，引入松弛变量 ，因此上式就f *,i可以写为 2*1min()liiwC约束条件变为 *,0iiiiyxb引入拉格朗日函数和对偶变量 2*11* *1 1()()l li iiiil liiiiiiLwCywxbywxb其中， 。再根据 KKT 条件，得到*,0,ii*1 *1*()0,()lii iil lii iii iiiiiiLCilbwxwxC