SVM基本原理及其发展概述(共4页)

1、精选优质文档-倾情为你奉上SVM基本原理及其发展概述摘要：支持向量机（Support Vector Machine，SVM）是一种基于统计学习理论的新型机器学习方法，它采用了结构风险最小化原则来代替了经验风险最小化能较好地解决小样本学习的问题；还采用核函数思想，把非线性空间的问题转换到线性空间，降低了算法的复杂度。正因为SVM有较完备的理论基础和较好的学习性能，在解决有限样本、非线性及高维模式识别问题中表现出许多特有的优势，成为当前机器学习领域的研究热点问题之一，并在很多领域都得到了成功的应用。关键词：数据挖掘；统计理论；支持向量机中图分类号：TP301 文献标识码：A 文章编号：1统计学习理

2、论统计学习理论是SVM的理论基础。基于数据的机器学习是现代智能技术中的重要方面，研究从观测样本出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。包括模式识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。与传统统计学相比，统计学习理论(Statistical Learning Theory，SLT)是一种专门研究小样本情况下机器学习规律的理论。Vapnik Vapnik V N.The natu

3、re of statistical learning theoryM.New York:Spring,1995.等人从六、七十年代开始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题(比如神经网络结构选择问题、局部极小点问题等)，同时，在这一理论基础上发展了一种新的通用学习方法支持向量机(Support Vector Machine，SVM)。

4、一些学者认为，SLT和SVM正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发展。统计学习理论的一个核心概念就是VC维，它是描述函数集或学习机器的复杂性或者说学习能力的一个重要指标，在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、推广性能等的重要结论。在统计学习理论基础之上发展起来的支持向量机是统计学习理论中最年轻的内容，它已表现出很多优于己有方法的性能。2支持向量机2.1介绍及其特点支持向量机的重要理论基础是统计学习理论的VC维理论和结构风险最小化原理。根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。传统的统计模式识别方法在进行机

5、器学习时，强调经验风险最小化。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，会产生“过学习问题”，其推广能力较差。SVM根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷以期获得最好的推广能力，从而使其学习机获得了更好的推广性能，这恰恰是统计学习理论最重要的目标之一。SVM可以自动寻找对分类有较好区分能力的支持向量，由此构成的分类器可以最大化类与类之间的间隔。支持向量机主要优点包括：（1）它是专门针对有限样本情况的其目标是得到现有信息下的最优解，而不仅仅是样本数目趋于无穷大时的最优值。（2）算法最终转化为一个二次型寻优问题。从理论上说得到的

6、将是全局最优点，解决了在神经网络方法中无法避免的局部极值问题。（3）算法将实际问题通过非线性变换到高维的特征空间，在高维空间中构造线性判别函数以替换原空间中的非线性判别函数，这样能保证机器有较好的推广能力同时它巧妙地解决了维数问题，算法复杂度与样本维数无关。SVM算法有很多成功的应用领域，如人脸识别、手写体识别、指纹识别等。SVM算法在精度上已经超过传统的学习算法或与之不相上下，这些应用都说明了基于VC维理论和结构风险最小化原理而发展起来的结构化学习方法的潜在优势。2.2算法及其发展2.2.1支持向量机算法V.Vapnik等人首先提出来的是chunking算法：从训练样本中任意选择一个小的子集

7、，求此子集的最优解，保留此子集的支持向量，从剩余的样本中启发式地加入新的子集，再求解新子集的最优，反复迭代直至收敛，但chunking算法需求的内存空间受所解决问题的支持向量数目的限制，当问题的支持向量数过大时子问题的求解也很困难。2.2.2支持向量机的几个发展为了进一步提高支持向量机算法的运行效率和收敛速度，研究人员对此做出了巨大的努力，提出了很多改进办法，不断推动支持向量机研究向前发展。（1）模糊支持向量机，引入样本对类别的隶属度函数，这样每个样本对于类别的影响是不同的。这种理论的应用提高了SVM的抗噪声的能力，尤其适合在未能完全揭示输入样本特性的情况下。（2）最小二乘支持向量机。这种方法

8、是在1999年提出，经过这几年的发展，已经应用要很多相关的领域。研究的问题已经推广到：对于大规模数据集的处理，处理数据的鲁棒性，参数调节和选择问题，训练和仿真等。（3）加权支持向量机（有偏样本的加权，有偏风险加权）。（4）主动学习的支持向量机。主动学习在学习过程中可以根据学习进程，选择最有利于分类器性能的样本来进一步训练分类器，特能有效地减少评价样本的数量。（5）粗糙集与支持向量机的结合。首先利用粗糙集理论对数据的属性进行约简,能在某种程度上减少支持向量机求解计算量。（6）基于决策树的支持向量机。对于多类问题,采用二岔树将药分类的样本集构造出一系列的两类问题,每个两类构造一个SVM。（7）分级

9、聚类的支持向量机。基于分级聚类和决策树思想构建多类svm,使用分级聚类的方法,可以先把n-1个距离较近的类别结合起来,暂时看作一类,把剩下的一类作为单独的一类,用svm分类,分类后的下一步不再考虑这单独的一类,而只研究所合并的n-1类,再依次下去。（8）算法上的提高。Vapnik在1995年提出了一种称为chunking的块算法,即如果删除矩阵中对应Lagrange乘数为0的行和列,将不会影响最终结果。Osuna提出了一种分解算法固定工作样本集方法：选择一个固定大小的工作集B求解B上的quadraticproblemQP问题考察所有不满足KKT条件的样本启发式地选择一些样本与集B中对应优化变量

10、的样本交换反复迭代直到所有的样本都满足KKT条件每一个QP子问题仍然使用迭代数值优化算法求解Osuna证明每次迭代使目标函数单调递增因为目标函数有上界所以经过有限次迭代后算法将收敛并得到最优解但最优解在一般情况下并不唯一。Joachims在1998年将Osuna提出的分解策略推广到解决大型SVM学习的算法。Platt于1998年提出了序贯最小优化每次的工作集中只有2个样本。（9）核函数的构造和参数的选择理论研究。基于各个不同的应用领域,可以构造不同的核函数,能够或多或少的引入领域知识。现在核函数广泛应用的类型有：多项式逼近、贝叶斯分类器、径向机函数、多层感知器。参数的选择现在利用交叉验证的方法

11、来确认。（10）支持向量机从两类问题向多类问题的推广。Weston在1998年提出的多类算法为代表。在经典svm理论的基础上,直接在目标函数上进行改进,重新构造多值分类模型,建立k分类支持向量机。通过sv方法对新模型的目标函数进行优化,实现多值分类。一对多(one-against-rest)Vapnik提出的,k类k个分类器,第m个分类器将第m类与其余的类分开,也就是说将第m类重新标号为1,其他类标号为-1。完成这个过程需要计算k个二次规划,根据标号将每个样本分开,最后输出的是两类分类器输出为最大的那一类。不足:容易产生属于多类别的点(多个1)和没有被分类的点(标号均为-1不对,训练样本数据大

12、,训练困难,推广误差无界。层(数分类方法),是对一对一方法的改进,将k个分类合并为两个大类,每个大类里面再分成两个子类,如此下去,直到最基本的k个分类,这样形成不同的层次,每个层次都用svm来进行分类1对r-1法,构建k-1个分类器,不存在拒绝分类区。3基于支持向量机的数据挖掘及其研究现状3.1支持向量机在数据挖掘中的应用现状统计学习理论和支持向量机建立了一套较好的有限样本下机器学习的理论框架和通用方法，有严格的理论基础，其核心思想就是学习机器的复杂性要与有限的训练样本相适应，能较好地解决有限样本、非线性、高维数和局部极小点等实际问题，能建立稳定的预测准确率高的分类器，所以很适合应用于分类规则

13、挖掘。但是任何一种方法要成功应用于分类规则挖掘，都必须解决几个问题。首先数据挖掘的算法必须能处理海量数据，即数十万、上百万甚至更多的数据量。现有训练算法一般都基于 SMO或其改进算法，已经基本解决了这个问题。其次数据挖掘在处理海量数据的同时还要有较快的运算速度，这样才能有较高的实用价值。Jianxiong Dong开发的HeroSVM（单线程版）经过特别的优化，在Pentium41.7Ghz的CPU上对一百多万样本的汉王手写数字数据库作训练，只需45分钟即可完成（Windows 2000 Professional，1.5G SDRAM）。这样训练速度的问题也基本解决。最后是预测的问题。当训练得

14、到的支持向量比较多时（特别是在训练海量数据时），预测的速度会比较慢。C.J.C.Burges提出了一种简化的支持向量机（Simplified Support Vector Machine），可以大大压缩支持向量的数目，而对预测准确率影响很小，从而可以加快预测速度。由此我们可以说，支持向量机完全可以成为一种很好的分类规则挖掘方法。3.2支持向量机在数据挖掘应用中存在的问题由于统计学习理论和支持向量机建立了一套较好的有限样本下机器学习的理论框架和通用方法，既有严格的理论基础，又能较好地解决小样本、非线性、高维数和局部极小点等实际问题，因此成为20世纪90年代末发展最快的研究方向之一。其核心思想就是学习机器要与有限的训练样本相适应。目前SVM研究中仍需要解决的一些难点包括如下的一些方面：（1）核函数和参数的构造和选择缺乏理论指导。核函数的选择影响着分类器的性能，如何根据待解决问题的先验