《人工智能大作业21.docx》由会员分享，可在线阅读，更多相关《人工智能大作业21.docx（21页珍藏版）》请在三一办公上搜索。
1、研究报告题 目 支持向量机学习报告 学 号 学 生 支持向量机学习报告支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。支持向量机SVM(Support Vector Machine)是AT&TBell实验室的VVapnik提出的针对分类和回归问题的统计学习理论。由于SVM方法具有许多优点和有前途的实验性能，该技术已成为机器学习研究领域中的热点，并取得很理想的效果，如人脸识别、手写体数字识别和网页分类等。1原理及方法SVM根
2、据问题的复杂性可以分为线性可分SVM和非线性可分SVM，其基本原理如下：在进行文本分类的时候，每一个样本由一个向量（就是那些文本特征所组成的向量）和一个标记（标示出这个样本属于哪个类别）组成。如下： Di=(xi,yi) xi就是文本向量（维数很高），yi就是分类标记。 在二元的线性分类中，这个表示分类的标记只有两个值，1和-1（用来表示属于还是不属于这个类）。有了这种表示法，可以定义一个样本点到某个超平面的间隔： yi(wxi+b)如果某个样本属于该类别的话，那么wxi+b0（因为我们所选的g(x)=wx+b就通过大于0还是小于0来判断分类），而yi也大于0；若不属于该类别的话，那么wxi+
3、b 核函数矩阵K是对称半正定的。这个条件也是充分的，由Mercer定理来表达。Mercer定理：如果函数K是上的映射（也就是从两个n维向量映射到实数域）。那么如果K是一个有效核函数（也称为Mercer核函数），那么当且仅当对于训练样例，其相应的核函数矩阵是对称半正定的。Mercer定理表明为了证明K是有效的核函数，那么不用去寻找，而只需要在训练集上求出各个，然后判断矩阵K是否是半正定（使用左上角主子式大于等于零等方法）即可。把一个本来线性不可分的文本分类问题，通过映射到高维空间而变成了线性可分的。就像下图这样： 圆形和方形的点各有成千上万个。现在想象我们有另一个训练集，只比原先这个训练集多了一
4、篇文章，映射到高维空间以后（当然，也使用了相同的核函数），也就多了一个样本点，但是这个样本的位置是这样的：就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。这样类似的问题（仅有少数点线性不可分）叫做“近似线性可分”的问题。 但这种对噪声的容错性是人的思维带来的。由于原本的优化问题的表达式中，确实要考虑所有的样本点，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个
5、值。 仿照人的思路，允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样，因此用间隔（而不是几何间隔）来衡量有利于我们表达形式的简洁。我们原先对样本点的要求是： 意思是说离分类面最近的样本点函数间隔也要比1大。如果要引入容错性，就给1这个硬性的阈值加一个松弛变量，即允许因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时（这些点也叫离群点），意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔（在低维空间看来，分类
6、边界也更平滑）。显然我们必须权衡这种损失和好处。好处很明显，我们得到的分类间隔越大，好处就越多。回顾我们原始的硬间隔分类对应的优化问题：|w|2就是目标函数（当然系数可有可无），希望它越小越好，因而损失就必然是一个能使之变大的量（能使它变小就不叫损失了，我们本来就希望目标函数值越小越好）。那如何来衡量损失， 其中l都是样本的数目。把损失加入到目标函数里的时候，就需要一个惩罚因子（cost，也就是libSVM的诸多参数中的C），原来的优化问题就变成了下面这样：一是并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有，所有没离群的点松弛变量都等于0（对负类来说，离群点就是在前面图中，
7、跑到H2右侧的那些负样本点，对正类来说，就是跑到H1左侧的那些正样本点）。 二是松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远。 三是惩罚因子C决定了重视离群点带来的损失的程度，显然当所有离群点的松弛变量的和一定时，定的C越大，对目标函数的损失也越大，此时就暗示着不愿意放弃这些离群点，最极端的情况是把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，问题变成无解，这就退化成了硬间隔问题。 四是惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个必须事先指定的值，指定这个值以后，解一下，得到一个分类器，然后用测试数据看看结果怎么样，如果不够好，换一个C的值
8、，再解一次优化问题，得到另一个分类器，再看看效果，如此就是一个参数寻优的过程，但这和优化问题本身决不是一回事，优化问题在解的过程中，C一直是定值。 从大的方面说优化问题解的过程，就是先试着确定一下w，也就是确定了前面图中的三条直线，这时看看间隔有多大，又有多少点离群，把目标函数的值算一算，再换一组三条直线（你可以看到，分类的直线位置如果移动了，有些原来离群的点会变得不再离群，而有的本来不离群的点会变成离群点），再把目标函数的值算一算，如此往复（迭代），直到最终找到目标函数最小时的w。 松弛变量也就是解决线性不可分问题的方法，核函数的引入也是为了解决线性不可分的问题。其实两者还有些不同。以文本分
9、类为例。在原始的低维空间中，样本相当的不可分，无论怎么找分类平面，总会有大量的离群点，此时用核函数向高维空间映射一下，虽然结果仍然是不可分的，但比原始空间里的要更加接近线性可分的状态（就是达到了近似线性可分的状态），此时再用松弛变量处理那些少数“冥顽不化”的离群点，更加简单有效。 对比复杂的推导过程，SVM的思想确实简单。是在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。之后解决目标函数的最优化问题。在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不
10、是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日对偶和SMO算法化解，使SVM趋向于完美。SVM有如下主要几个特点：(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。(4)SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此
11、不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。(5)SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。(6)少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:增、删非支持向量样本对模型没有影响;支持向量样本集具有一定的鲁棒性;有些成功的应用中,SVM 方法对核的选取不敏感两个不足：(1) SVM
12、算法对大规模训练样本难以实施由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法(2) 用SVM解决多分类问题存在困难经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再
13、就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。2试验及分析2.1libsvm自带例子1用heart_scale测试调整c，分类准确率会变化，但是，变为100%，我认为可能是测试数据和训练数据是相同的数据集引起的。2不同的参数tt 核函数类型：核函数设置类型(默认2)0 线性：uv1 多项式：(r*uv + coef0)degree2 RBF函数：exp(-r|u-v|2)3 sigmoid：tanh(r*uv + coef0)不同的核函数对分类准确率的影响。对于hear
14、t_scale不同的核函数对分类准确率的影响不大,rbf 核函数的性能最好。3调整c和g以找到最优的c和g使分类正确率最高调整c和g得到c=1和g=0.03125，分类正确率最高。2.2wine数据集实验1测试wine数据标签有三类，各选取一半作为测试集，一半为训练集。准确率并不好。 2不同的参数tt 核函数类型：核函数设置类型(默认2)0 线性：uv1 多项式：(r*uv + coef0)degree2 RBF函数：exp(-r|u-v|2)3 sigmoid：tanh(r*uv + coef0)不同的核函数对分类准确率的影响。多项式和sigmoid函数的训练结果最差。3调整c和g以找到最优
15、的c和g使分类正确率最高。调整c和g得到c=64和g=0.00097，分类正确率最高。3图形化3结论及改进SVM有如下主要几个特点： (1)非线性映射是SVM方法的理论基础,SVM用内积核函数代替向高维空间的非线性映射；(2)对特征空间划分的最优超平面是SVM的目标,最大化分类间隔是SVM方法的核心； (3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用 (4)SVM 是一种有坚实理论基础的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归
16、等问题； (5)SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。 (6)少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。SVM不足： (1) 训练好SVM分类器后,得到的支持向量被用来构成决策分类面。对于大规模样本集问题,SVM训练得到的支持向量数目很大,则进行分类决策时的计算代价很大。(2) 用SVM解决多分类问题存在困难，经典的支持向量机算法只给出了二类分类的算法，要解决多类的分类问题。可以通过多个二类支持向量机
17、的组合来解决。要针对不同的问题选择不同的核函数。标准的SVM对噪声是不具有鲁棒性的,如何选择合适的目标函数以实现鲁棒性是至关重要的。要根据具体问题选择合适的核函数及惩罚因子，多次实验选择最好的结果。一个好的分类器固然重要,但前期的数据预处理亦很重要。当数据预处理的好的话,特征提取的好的话,分类器的影响不会占很大比重。SVM算法参数选择可能是凭借经验、实验对比、大范围的搜寻或者利用软件包提供的交互检验功能进行寻优。参考文献1Chih-Jen Lin Department of Computer Science National Taiwan UniversityA Practical Guide
18、 to Support Vector Classification2Chih-Chung Chang and Chih-Jen Lin Department of Computer Science National Taiwan University, Taipei, Taiwan libsvm-A_library_for_support_vector_machines3CHRISTOPHER J.C. BURGES Bell Laboratories, Lucent TechnologiesA Tutorial on Support Vector Machines for Pattern 4支持向量机导论
