《支持向量机性能分析及改进》由会员分享，可在线阅读，更多相关《支持向量机性能分析及改进（56页珍藏版）》请在金锄头文库上搜索。
1、烟台大学毕业论文（设计）11 绪论1.1 课题背景当今随着信息技术和信息网络的飞速发展，信息产生和传播的速度迅速提高，各种各样的机构每天都在产生并积累着大批量的数据。伴随海量数据而来的问题是信息过载和信息污染，这极大地影响了人们对信息的有效利用，因此，从大量数据中发现有用知识的数据挖掘(Data Mining)，就成为一个十分迫切的富有挑战性的研究课题。基于数据的机器学习(Machine Learning)是数据挖掘技术中的重要内容，机器学习研究从观测数据出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。其重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，
2、但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法在实际中的表现却可能不尽人意。令人激动的是，上述困难随着统计学习理论(Statistical Learning Theory，简记 SLT)及在此基础上发展起来的支持向量机(Support Vector Machine，简记 SVM)技术在实际问题中的广泛应用而逐步得到了缓解。统计学习理论(Statistical Learn-ing Theory SLT)，专门研究实际应用中有限样本情况的机器学习规律，并发展了支持向量机(Support Vector Machine SVM)这一新的通用学习方法，由于它基于结构风险最小化(SRM
3、)原理，而不是传统统计学的经验风险最小化(ERM)，表现出很多优于已有方法的性能，迅速引起各领域的注意和研究兴趣，取得了大量的应用研究成果，推动了各领域的发展。支持向量机结构简单，并且具有全局最优性和较好的泛化能力，自 20 世纪 90 年代提出以来得到了广泛的研究。支持向量机方法是求解模式识别和函数估计的有效工具。汉字识别一直是模式识别最重要的研究领域之一。针对汉字的结构特点，许多学者分别从预处理和特征提取的角度提出了许多方法。从预处理的角度，通过对汉字点阵采取某种非线性变换，矫正手写汉字变形，以减少类内方差。从特征提取的角度，利用汉字固有的笔划构成特征提取手写汉字的笔划以及笔段信息。但是，
4、由于汉字的结构复杂性，以及不同人书写变形的不确定性，到目前为止，手写汉字的识别性能仍然不能令人满意。神经网络由于其较强的曲线拟合和模式分类能力，在汉字识别中得到广泛的应用。经过多年的研究，已经取得了大量成果。但对区分手写得非常近似的汉字,仍然缺乏有效的手段。采用汉字笔画及字型信息的特征,即多特征的方法,可以用于相似字的识别,但效果不能令人满意。人工神经网络的方法在小规模分类中是比较有效的,但人工神经网络学习算法有其固有的缺点,如网络结构的确定尚无可靠的规则, 算法的收敛速度较慢，且无法保证收敛到全局最优点。支持向量机则在一定程度上解决了神经网络的问题，它建立在牢固的数学基础之上，其通过核函数及
5、最优化方法，最终将算法转化为一个二次凸函数求极值问题，从理论上说得到必将是全局最优点，用支持向量机解决手写体相似字识别问题的方法,已经取得较好的效果。本文提出了一种通过修正核函数来提高支持向量机分类性能的方法，其思想是尽量放大分离曲面附近的局部区域，而保持其他区域变化不大（因为高斯核的图形是类似于钟形曲线的） 。考虑到支持向量几乎总是出现在分离曲面附近，故设法放大支持向量的局部区域，通过将原来的样本点映射到一个高维空间，以拉大分类间隔的距离，从而达到提高其分类性能的目的。烟台大学毕业论文（设计）21.2 支持向量机的概述1.2.1 支持向量机的研究背景和意义(1)支持向量机的研究背景基于传统的
6、统计学的机器学习方法，理论体系非常完善，但其在解决基于有限样本的实际问题时的性能往往不能令人满意。前苏联学者 Vladimir N.Vapnik 等人研究基于有限样本情况下的机器学习问题，形成了一个较完善的理论体系统计学习理论。同时，神经网络等一些较新型的基于传统的统计学的机器学习方法的研究则遇到了很大的困难，如过学习与欠学习问题、如何确定网络结构的问题、局部极小点问题等等。因此这种能从更深层次上描述、解决有限样本情况下的机器学习问题的统计学习理论逐步受到广大研究者的重视。20 世纪 90 年代中期，Vaphik 和他领导的 AT&T Bell 实验室小组提出了基于统计学习理论和结构风险最小化
7、的 SVM 算法，进一步丰富和发展了统计学习理论，使它不仅是一种理论分析工具，还是一种可以构造具有多维预测功能的预测学习算法的工具，使抽象的学习理论能够转化为通用的容易实现的预测算法。 (2)支持向量机研究的意义支持向量机是在统计学习理论基础上发展起来的一种新型机器学习方法。由于具有以下主要优点而被广泛关注:基础是统计学习理论，针对有限集样本，而不是样本集数目趋于无穷大，更具有实际应用价值；将学习问题归结为一个凸二次规划问题，从理论上说，得到的将是全局最优解，解决了在神经网络方法中无法避免的局部极值问题；通过非线性变换将数据映射到高维特征空间，使数据在高维空间中可以用线性判别函数分类，巧妙地解
8、决了维数问题，算法复杂度与样本维数无关。支持向量机建立在严格的理论基础之上，较好地解决了非线性、高维数、局部极小点等问题，成为继神经网络研究之后机器学习领域新的研究热点。支持向量机从提出、被广泛重视到现在只有很短的时间，其中还有很多尚未解决或尚未充分解决的问题，在应用方面还具有很大的潜力。因此，支持向量机是一个十分值得大力研究的领域。 1.2.2 支持向量机的基本思想从观测数据中学习归纳出系统运动规律，并利用这些规律对未来数据或无法观测到的数据进行预测一直是智能系统研究的重点。传统学习方法中采用的经验风险最小化准则(empirical risk minimization, ERM)虽然可以使训
9、练误差最小化，但并不能最小化学习过程的泛化误差。ERM不成功的例子就是神经网络的过学习问题。为此,Vapnik提出了结构风险最小化准则( structural risk minimization, SRM)，通俗地说就是通过对推广误差(风险)上界的最小化达到最大的泛化能力。Vapnik提出的支持向量机( support vector machine, SVM) 就是这种思想的具体实现。支持向量机的基本思想是在样本空间或特征空间，构造出最优超平面，使得超平面与不同类样本集之间的距离最大，从而达烟台大学毕业论文（设计）3到最大的泛化能力。1.2.3 支持向量机的应用研究现状模式分类是模式识别中的一
10、项重要内容，分类也是人们认识一切事物的基础，许多优秀的学习算法都是以分类为基础发展起来的 8。SVM方法在理论上具有突出的优势，贝尔实验室率先对美国邮政手写数字库识别研究方面应用了SVM方法，取得了较大的成功。在近几年内，有关SVM的应用研究得到了很多领域的学者的重视，在人脸检测、验证和识别、说话人/语音识别、文字手写体识别、图像处理、及其他应用研究等/方面取得了大量的研究成果，从最初的简单模式输入的直接SVM方法研究，进入到多种方法取长补短的联合应用研究，对SVM方法也有了很多改进 。11.2.4 支持向量机的研究热点由于支持向量机坚实的理论基础和它在很多领域表现出的良好的推广性能，目前，国
11、际上正在广泛开展对支持向量机方法的研究。许多关于SVM方法的研究，包括算法本身的改进和算法的实际应用，都陆续提了出来。以下是其中主要的研究热点。（1）改进训练算法由于SVM对偶问题的求解过程相当于解一个线性约束的二项规划问题(QP)，需要计算和存储核函数矩阵，其大小与训练样本数的平方相关，因此，随着样本数目的增多，所需要的内存也就增大，例如，当样本数目超过4000时，存储核函数矩阵需要多达128M内存；其次，SVM 在二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的主要部分。通常，训练算法改进的思路是把要求解的问题分成许多子问题，然后通过反复求解子问题来求得最终的解，
12、方法有以下几种：块处理算法(chunking algorithm) 它的思想是将样本集分成工作样本集和测试样本集，每次对工作样本集利用二项规划求得最优解，剔除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结果(一般是指违反KKT条件)的样本(或其中的一部分)与本次结果的支持向量合并，成为一个新的工作样本集，然后重新训练。如此重复下去，直到获得最优结果。其依据是去掉Lagrange 乘子等于零的训练样本不会影响原问题的解。块算法的一个前提是：支持向量的数目比较少。然而如果支持向量的数目本身就比较多，那么随着训练迭代次数的增加，工作样本数也越来越大，就会导致算法无法实施。固定工作样
13、本集算法 它使样本数目固定在足以包含所有的支持向量，且算法速度在计算机可以容忍的限度内。迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换。即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模。有一种具体的算法，将样本集分为B和N两个集合，集合B作为子问题的工作样本集进行SVM训练，集合N中所有样本的Lagrange乘子均置为零。显然，烟台大学毕业论文（设计）4如果把集合B中，对应Lagrange乘子为零的样本i(即 = 0，i B)与集合N中的样本j(即i=0, j N)交换，不会改变子问题与原问题的可行性(即仍旧满足约束条件)。于是可j以按照以下步
14、骤迭代求解：选择集合B，构造子问题；求子问题最优解 ，i B及b，并置 = 0 ，j N ；计算g( x ) y ，j N，找出其中g (x ) y SMO 算法 SMO 是固定工作样本集算法的一个极端情况，其工作样本数目为 2。需要两个样本，是因为等式线性约束的存在使得同时至少有两个 Lagrange 乘子发生变化。由于只有两个变量，而且应用等式约束可以将其中一个用另一个表示出来，所以迭代过程中，每一步子问题的最优解都可以直接用解析的方法求出来，这样，算法就避开了复杂的数值求解优化问题的过程；此外，算法还设计了一个两层嵌套循环，分别选择进入工作样本集的样本，这种启发式策略大大加快了算法的收敛
15、速度。标准样本集的实验结果证明，SMO 在速度方面表现出良好性能。（2）提高测试速度SVM 判决函数的计算量和支持向量的数目成正比。对于大训练集合，其支持向量的数目会达到几千个，这就使SVM对实验样本的测试判决速度变慢，因此，提高SVM 的测试速度是另一个研究热点。对所有N 个支持向量求和，计算量很大，如果可以减少求和的数目，使其达到M s(M N )个，则可以大大提高速度。判决函数d(x)的近似式如下：sd(x) = (1.1)MiibXK1),(据此，Osuna 提出3 种方案：对d(x)在特征空间中进行拟合，得到一个近似的判决函数d(x) ：d(x) = (1.2)liibZX1),(其
16、中， N ， 是特征空间中的合成向量，不一定是样本点， 是权重。lsiZ i判决函数d(x)在特征空间中近似为d(x)= (1.3)liibXK1),(其中， N ， 是与支持向量 对应的权重。lsii对原问题重新定义，得到新的判决函数为d(x) = (1.4)li iibXy1),(烟台大学毕业论文（设计）5其中， N ， 是某些训练样本点，但不一定是支持向量， 是权重， 是样本点的lsiX iiy类别标号。其中，第 1 个方案已经被 Burges 论证，并实现，其基本思想是：在 SVM 的高维特征空间中，运用比原来少得多的精简集合(Reduced Set ，RS )向量来拟合原来所有 SV 所构成的分界超
