毕业论文毕业论文毕业论文

《毕业论文毕业论文毕业论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1•综述1.1课题背景1丄1支持向量机的概述与本质机器学习是人工智能的一个理论核心，它研究的是如何根据一些已知具有某些特性的经验数据找到一种规律，并利用这种规律判断或预测未知特性的数据的特性。目询，机器学习的方法主要有三种：第一种是基丁传统统计学的经與的参数估计法。其思路是利用训练样本估计已知形式的参数。它的局限性在于：（1）己知样本的分布形式必须是己知的。（2）训练样本的数口应当趋于无穷大。第二种是非线性方法。其思路是利用经验数据建立一个非线性的模型。它在一定程度上克服了第一种方法的局限性。但是，该方法貝有随意性，目而还缺乏统一的数学理论。第三种是基丁统计学习理论的方法。与第一种方法基于的传统统计学相比，统计学习理论的优势在于，它是研究小样本情况下的机器学习理论。它不仅考虑了渐进性能，并且更加强调如何在有限的信息下得到最优的结果。同时，显然，基于统计学习理论的方法要优于前两种方法。而支持向量机就是一种基于统计学习理论的机器学习方法。它本质上就是一种算法，在机器学习领域，常把一些算法看作是机器（又叫学习机器，或预测函数，或学习函数）。“支持向量”则是指训练集屮的某些训练点的输入xi（注意，该xi不是一个数，而是一个N维的特征向量），而这些训练点对这个算法的求解起着关键的作用，这也可以看做支持向量机名字的由来。支持向量机这种方法通常用在模式识别和数据挖掘等领域。因此，可以把支持向量机看做是模式识别或数据挖掘中的一种新方法。1丄2支持向量机起源、现状和发展方向（1）起源由于传统统计学研究的是样本数目趋于无穷大时的渐近理论。而现有的很多学习方法也多是基于此假设。但在实际问题屮，样本数往往是有限的，因此-•些理论上很优秀的学习方法在实际中的表现却可能不尽人意。而与传统统计学相比，统计学习理论（StatisticalLearningTheory或SLT）是一种专门研究小样木情况下机器学习规律的理论。V.Vapnik等人从六、七十年代开始致力于此方面研究[1],到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。在此基础上，V.Vapnik也进而提岀了基于统计学习理论的一种新的机器学习方法支持向量机（SupportVectorMachine或SVM）。近年来支持向量机在理论研究和算法实现方面都取得了突破性进展，其主要优势在于：<1>它的基础是统计学习理论，针对的是有限样本的情况，其目标是得到有限信息下的最优解而不是样本数目趋于无穷大时的最优值，因此更具有实际应用价值。 ＜2＞通过核变换以及最优化方法，支持向量机算法最终转化为一个二次凸函数求极值问题，因此得到的是全局最优点。解决了其他机器学习方法，例如神经网络中无法避免的局部极值问题。＜3＞算法利用核函数将实际问题通过某种非线性变换映射到高维特征空间（FeatureSpace）/中，然后在高维特征空间中构造线性判别函数来替代输入空间中的非线性判别函数。这一点保证了该方法冇较好的泛化性能，同时通过直接计算核矩阵巧妙的解决了“维数灾难”问题。（2）研究现状就目前來说，SVM是统计学习理论中最新的内容，也是最实用的部分，口J用于模式识别、回归估计或函数逼近等方面，不但是当前人工智能和模式识别领域研究的热点，而且也已成为机器学习和数据挖掘领域的标准工具。现在对SVM的研究主要集屮在以下几个方面（在第2部分有详细介绍）：〈1＞核函数的构造、修正以及相应参数的调整。〈2＞提高测试速度。〈3＞改进训练算法。〈4＞利用SVM解决多分类的问题。（3）应用现状SVM方法在理论上具有突出的优势，贝尔实验室率先对美国邮政手写数字库识别研究方面应用了SVM方法，取得了较大的成功。在近几年内，有关SVM的应用研究得到了很多领域的学者的重视，在人脸检测、验证和识别，说话人/语咅识别，手写体文字识别，图像处理及其他应用方而取得了大量的研究成杲，从最初的简单模式输入的直接SVM方法研究，进入到多种方法取长补短的联合应用研究，对SVM方法也有了很多改进（在笫2部分有详细介绍）。（4）发展方向当前，对支持向量机的研究方兴未艾，总的来说，主耍围绕两个方面：一是通过对支持向量机本身性质的研究，提出进一步完善的措施。此外还包括多类识别问题和快速训练算法等。二是不断探索新的应用领域。支持向量机本质上是一种非线性数据处理工具，人们注意到它在数字信号处理、图象处理、智能控制等领域有巨人的应用潜力。这方面已经有了一些结果，如基于核的主成分分析、非线性去噪、非线性模式重建以及数据挖掘等。遗憾的是，虽然支持向量机在理论上有很突出的优势，但与其理论研究相比，应用研究尚相对比较滞后，目前只有比较有限的实验研究报道，且多属仿真和对比实验。支持向量机的应用研究应该是一个大有作为的方向。我们相信支持向量机是一个值得大力研究的领域，对它的研究将对机器学习等学科领域产生重耍影响。一些学者其至认为，SLT和SVM正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发展。1-2课题提出支持向量机在很多方面都有着和其他统计学技术难以比拟的优越性，并在一些领域获得很大的进展。但是，作为一种尚未成熟的新技术，支持向量机目前仍然存在着很多问题。最人的问题就是核函数的选择——核函数对支持向量机的性能起着非常关键的作用， 而对于怎样选择好的核函数，目前还没有很好的理论指导。另一个问题是编程实现支持向量机的思想。同时，由于SVM是一门新兴学科，很多方面还有待完善。例如：许多理论目前还不能在实际问题中得以实现，而某些实际算法在理论上的解释也并非完美。针对核函数不好选择的问题,Amari&Wu在其论文ImprovingSupportVectorMachineClassifiersbyModifyingKernelFunctions”[4]中,提出一种新的思路：既然目前还没有较好的理论指导如何选择较好的核函数，但是对于选定的一种核函数，可以对它加以修正，相当于构造一个新的核函数，使得用这个新的核函数的支持向量机的性能更好。而台湾大学林智仁博士等人用C++和C开发的一个1ibsvm软件包，实现了SVM的思想,并开放源代码。但程序里只冇几个常用的基本核函数供以选择。仍然无法解决核函数的选择问题。上而捉到在SVM这个新兴学科中，许多理论目前还不能在实际问题屮得以实现，而某些实际算法在理论上的解释也并非完美。那么Amari&Wu提岀的修正核函数的思想可行吗？木设计首先就是在1ibsvm软件包的基础上编程实现了Amari&Wu的这种思想，并以标准字库GB2312-80-级字库中的16区、20区、34区和46区的汉字样本作为实验数据，比较了以高斯径向基函数为核函数的SVM和修止径相基函数后的SVM的性能。而实验结杲表明，修正核函数后的SVM的性能确实有显著的捉高。然而，Amari&Wu的修正核函数的思想仅仅考虑了数据依赖。本设计在验证了该思想的正确性后又进-步提出了一种既考虑到数据依赖又考虑到间隔依赖的修正核函数的思想，并同样以标准字库GB2312-80-级字库中的16区、20区、34区和46区的汉字样本作为实验数据，比较了其与未修止核函数的SVM以及根据Amari&Wu的思想修止核函数的SVM的分类性能。 2•统计学习理论和支持向量机核心内容2.1统计学习理论的核心内容2.1.1机器学习问题的数学模型机器学习的口的是根据给定的训练样木求对某系统输入输出之间依赖关系的佔计，使它能够对未知输出作出尽可能准确的预测。可以一般地表示为：变量y与x存在一定的未知依赖关系，即遵循某一未知的联合概率F(x,y),(x和y之间的确定性关系可以看作是其特例)，机器学习问题就是根据n个独立同分布观测样木(X1,Y1),(X2,Y2),.,(Xn,Yn)(2.1)在一组函数｛f(X,w)｝-|i求一个最优的函数f(x,wo)对依赖关系进行估计，使期望风险R(W)二几(y,f(x,w))dF(x,y)(2.2)最小。其屮，｛f(x,w)｝称作预测函数集，w为函数的广义参数，｛f(x,w)｝可以表示任何函数集,L(y,f(x,w))为由于用f(x,w)对y进行预测而造成的损失,不同类型的学习问题有不同形式的损失函数。预测函数也称作学习函数、学习模型或学习机器。有三类基木的机器学习问题，即模式识别、函数逼近和概率密度估计。对模式识别问题，输出y是类别标号，两类情况下y二｛0,1｝或｛1,-1｝,预测函数称作指示函数，损失函数可以定义为r0,ify=f(x,w),L(y,f(x,w))=[(2.3)1,ifyff(x,w),使风险最小就是Bayes决策小使错误率最小。在函数逼近问题小，y是连续变量(这里假设为单值函数)，损失函数可定义为L(y,f(x,w))=(y-f(x,w))2,(2.4)即采用最小平方误差准则。而对概率密度估计问题，学习的口的是根据训练样木确定x的概率密度。记佔计的密度函数为P(x,w),则损失函数可以定义为L(p(x,w))=-logp(x,w).(2.5)2.1.2经验风险最小化在上面的问题表述中，学习的目标在于使期望风险最小化，但是，曲于我们口J以利用的信息只有样本(2.1),(2.2)式的期果风险并无法计算，因此传统的学习方法中采用了所谓经验风险最小化(ERM)准则，即用样本定义经验风险R呵(w)=》L(y汇(xi，w))(2.6) 1=1作为对(2.2)式的估计，设计学习算法使它最小化。对损失函数(2.3),经验风险就是训练样木错误率；对(2.4)式的损失函数，经验风险就是平方训练误差；而采用(2.5)式损失函数的ERM准则就等价于最大似然方法。事实上，用ERM准则代替期望风险最小化并没有经过充分的理论论证，只是肓观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中山据了主耍地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上，而实际上，即使可以假定当n趋向于无穷大时(2.6)式趋近于(2.2)式，在很多问题中的样本数目也离无穷大相去其远。那么在有限样木下ERM准则得到的结果能使真实风险也较小吗？2.1.3复杂性与推广能力ERM准则不成功的一个例子是神经网络的过学习问题。开始，很多注意力都集屮在如何使孔和仙)更小，但很快就发现，训练误差小并不总能导致好的预测效果。某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加，这就是过学习问题。之所以出现过学习现象，一是I大I为样本不充分，二是学习机器设计不合理，这两个问题是互相关联的。设想一个简单的例子，假设有一组实数样本{x,y},y取值在［0,1］之间，那么不论样本是依据什么模型产生的，只要用函数f(x,Q二sin(ax)去拟合它们Q是待定参数)，总能够找到一个4使训练误差为零，但显然得到的“最优”函数并不能正确代表真实的函数模型。究其原因，是试图用一个十分复杂的模型去拟合有限的样本，导致丧失了推广能力。在神经网络中，若对有限的样本来说网络学习能力过强，足以记住每个样本，此时经验风险很快就可以收敛到很小其至零，但却根本无法保证它对未來样本能给出好的预测。学习机器的复杂性与推广性之间的这种矛盾同样可以在其它学习方法中看到。在有噪声条件下用模型y二X?产生10个样本，分别用一个一次函数和一个二次函数根据ERM原则去拟合，结果显示，虽然真实模型是二次，但由于样本数有限且受噪声的影响,用一次函数预测的结果更好。同样的实验进行了100次，71%的结果是一次拟合好于二次拟合。由此可看出，有限样本情况下，(1)经验风险最小并不一定意味着期望风险最小。(2)学习机器的复杂性不但应与所研究的系统有关，而口要和有限数目的样本相适应。我们需要一种能够指导我们在小的样本情况下建立有效的学习和推广方法的理论一-统计学习理论。 2.1.4VC维为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指标，其中最重要的是VC维（Vapnik-ChervonenkisDimension）。为了弄清楚VC维的概念，我们先理解“打散”的概念：假设有一h个输入点，分别用+1和-1来标记这些点，那么将有2〃种不同的标记法，即有2〃种不同的类别情况。如果对于每一种情况，都能从函数集H中选出合适的函数来正确划分这种标记（正确划分是指将标记为+1的点和标记为T的点完全分开）,那么则称这n个输入点可以被函数集H打散。模式识别方法中VC维的直观定义是：如果一个函数集H能打散某个点集（该点集所含的点的数目n^h）的点的最大数量为h,则称函数集H对应这个点集的VC维为h。需要注意的是，如果一个函数集的VC维为h。那么在共n个点的点集中至少存在某一个h个点的子集合能被该函数集打散，但是并不是任意的h个点都能被该函数集打散。下图给出的是一个打散和VC维概念的具体例子。在RxR平面上任意选取不共线的三点,由图可知，平而上的直线集可以将这三点完全打散。与此同时，很容易验证平面内任意四点都不可能被平而上的直线集打散。因此RxR平而上的直线集能打散的最大点数为3,从而该直线集对应平面上点集（不共线）的VC维是就是3o图2.1VC维示意图VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大）。遗憾的是,目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是n+1,对于一些比较复杂的学习机器（如神经网络），其VC维除了与函数集（神经网结构）有关外，还受学习算法等的影响,其确定更加困难。对于给定的学习函数集，如何（用理论或实验的方法）计算其VC维是当前统计学习理论中有待研究的一个问题。2.1.5结构风险最小化在有了VC维的概念之后，接下来的问题自然是如何通过VC维这个指标来对侯选函数集H的大小，也就是容量进行严格的限制。统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险Z间的关系，即推广性的界。关于两分类的问题，有这样的定理：设函数集H的VC维为h,训练样本的个数为n,若hl,i=l,2,…，/(2.9)也就是说，第1类样木点的输入代入这个函数，输出值大于或等于1,而第2类样木点的输入代入这个函数，输出值小于或等于-1。那么，对于未知类别的样本点的输入x,若f(x)Ml，我们就把它判定为第1类(y=l)；若f(x)W-1,我们就把它判定为第2类(y二-1)。那么对于那些-lWf(x)Wl的呢？我们约定这样的判别规则：对于0Wf(x)Wl的样本点，我们把它判定为第1类；对于TWf(x)W0的样本点，我们把它判定为第2类。综合起來表示，也就是：f(x)=sign(w•x+b)(2.10)其中f(a)为符号函数:a>=0时,sign(a)=1；a<0时,sign(a)=T。那么，现在的问题就是求出满足条件的w和b,并且由于通常满足(2)式的f(x)有很多，我们应当找一个最优的。那么根据什么标准寻优呢？这就要从几何的角度來分析这个问题。我们以二维的情况为例进行讨论。如下图所示，在2维的空间里有23个已知类别的样本点，英屮冇12个圆形的点，11个正方形的点，只有两个类别。它们的分布如下。俗话说“物以类聚”，通常来讲，同一类别的样本点(也就是训练集中的(无，兀))通常分布在二维空间的同一个区域，而不同类别的样本点分布在不同的区域。值得注意的是，这里说的“分布”只是指样木点的输入 兀•的位置，比如有一个样本点A{(10,5),-1},也就是x.=(10,5)y.=-l,那么(10,5)就是这个样木点在二维空间里的坐标。而-1是标识这个样木点是第2类，也就是说这个样木点对应的是图中的某个正方形的点。10图2.3两分类问题示意图我们知道,只考虑二维的情况,对于函数f(x)=w・x+b,如果w和b已经求出来了,是已知的，那么，在二维空间里，就能确定一条直线WX+20(也称超平面，这是一个广义的概念，在二维的情况下实际上是一条“线”)，同时也口J以确定无数条和该直线平行的直线，即w・x+b=d,其中d都是不定的常数。如下图所示的三条直线：W-X+b=0,w•x+b=l(d二1),w•x+b=-l(d二T)。所以，构造函数的问题可以传化为几何问题。式(2.9)在儿何上表示就是：对于所有的已知类别的样木点， >=1时,w•x.+bMl兀二一1吋，w•暫•+bW-1（2.11）也就是说，第1类的样本点“分布”在直线W•x+b=l的下方，而第2类的样本点“分布”在直线W•x+b=-l的上方（如卜•图所示）。然而，就像满足式（2.9）的函数有很多，满足（2.11）的超平面（在二维的情况下是直线）也有很多。如下图2.5也同样满足。所以对函数f（x）二f（xl,x2,・・・xN）二w•x+b的寻优问题（寻找最优的w和b）也就转化成了在二维空间中寻找最优的超平面w・x+b=O,这里的超平而相当丁一条将两个类别划分开的直线。图2.5式（2.9）在几何上的表示2由于我们的最终目的是要分类，那么我们希累图中两个类别分得越开越好。于是，我们希望两类样本中离超平面最近的那些样本点到超平面的距离和越短越好。为了更好地说明这个问题，我们先了解最优分类而的概念。设给定训练集为T={（x,.,兀）,i=1,2,-,I}，其中兀.WR”，兀丘{・1,+1},如下图所示，实心点和空心点代表两类样本,H为分类线,H1,H2分别为过各类屮离分类线最近的样本且平行于分类线的直线，它们Z间的距离叫做分类间隔（Margin）。所谓最大间隔分类线就是它不但能将两类正确分开（训练错谋率为0},而且使分类间隔最大。这个最大间隔分类线也就是我们说的最优分类而。在高维的情况下称为最优超平而。 图2.6最优超平而示意图容易计算，H1到H和H2到H的距离都为1/||w||,所以marginal|w||,所以最优超平面对应的w和b,也就是以下二次规划问题：问题1：已知：yf（w•兀•+b）1,i-1,2,…，/.求*加『的最小值。这个问题的解也就是我们最初问题的解。111,112上的训练样本点就称作支持向量（后而冇对支持向量由来的详细分析）。而倘若上而的二次规划问题冇解，那么我们的问题到此已经解决。比如，对于上面图2.3,求得的最优超平面如下：wx^b=O图2.7而分类病最优超平面示意图（2）线性不可分的分类问题在许多实际问题当屮，简单的线性分类器往往达小到预期的效果，那是因为在这些问题当中的样木集常常是线性小不可分的。但我们若能把线性不可分的情形转化成线性可分的情形，问题就可以按上面的步骤解决了。图2.8线性不可分的分类问题示意图 如图2.8,不同颜色的两类样木点是线性不可分的。原因是A、B和C“分布”得不“规范”。在该问题中，找不到一个能把两个类别完全分开的超平面wx+b=O,于是我们自然而然地想到放松对准确率的要求，即允许有不满足约束条件（2.9）的样本点存在。通过引入非负松驰变量歹丿=1,2,A,1,可以得到“放宽的”约束条件：>0,/=1,2,A，/（2.12）实际上，我们图2.8中的情况用式（2.21）“放宽”条件后，图2.8的就等价于求解下图2.9的情况。但要注意的是，A、B和C实际上是错分的点（它们其实就是后面要讲到的边界支持向量），而“放宽条件”相当于允许把A、B和C划分错。图2.9放宽条件后不可分问题的等价情况由该约束条件可以看出，只要点取得足够大，一定能够找到满足约束的W和b,即能够找到符合要求的分类超平而。但是显然不能将g取得过大，那样的话分类的错谋率将急剧增加。因此为了避免取得过人的珞，应该将其加入最优化问题1中使得越小越好，这也就是通常所说的进行惩罚。于是问题1可以转化为一下问题：问题2：已知ySw'xi&>0,i=1,2,A,1。求+C工的最小值。2z=i其中第一项|h2为正则化参数，为的是避免过学习而第二项•吃&体现的是错2/=!误率的限制，为的是使经验风险尽可能的小。其中C被称为惩罚参数，用來在置信范围与 经验风险Z间取得合理的折衷，使得结构风险达到最小，从而满足SRM准则。采用拉格朗H乘子法求解问题2这个具有线性约束的二次规划问题，可将问题2转化为问题3。厶=丄卩2/=is.t0We，0<为其中乞・,0,为拉格朗日乘子，由此得到当=0_>w=工yy丹cwZi緊0—>工附=0,Ob篙——=0—〉C-a-0=0〜（2.16）代入式（3.13）,得到对偶最优化问题问题3：maxmin将式（2.14）问题4：2+cf*i>b(r+b)-1+梟-亍出i=[z=l(2.13)(2.14)(2.15)(2.16)IIIImax{S二工匕-于工工用・勺}，ai=]厶i=j=I/=1Q1-J>05/=1,2,3,...,/类似于线形情况，得到对偶最优化问题问题6：I|iimax{S=》e一牙工工匕⑺必“（x「）©（Xj）a/=1/Z=1>1II//二工e-牙工工匕。屛儿K（x,,xj/=12/=1j=s.to0(2.28)/=1的充要条件是：对于使得"2⑴dZOO并H不为0的任意函数f(X)，条件^K(x,y)f(x)f(y)dxdy>0(2.29)成立。该条件成为Mercer^r件。那么符合上而的条件的函数就是核函数。而目前已知的满足条件的核函数主要冇三类，一是多项式核函数(Polynomialkernel)«(兀宀)=[(无・厂)+1『(2.30)所得到的是q阶多项式分类器；二是径向基函数(RBFkernel)X-—X•|K(兀•，兀丿=exp{}(2.31)a所得分类器与传统RBF方法的重要区别是，这里毎个基函数中心对应一个支持向量，它们及输出权值都是由算法自动确定的。也可以采用Sigmoid函数作为内积，即K(xz,Xj)=tanh(v(xz-xy)+c),(2.32)这时SVM实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络方法的局部极小点问题。另外，SVM1!1的核函数述有线形核函数(Linearkernel)«(兀宀)=(壬")(2.33)事实上，核函数的选取对支持向量机的性能起着非常关键的作用，然而对于怎样选取好的核函数，目前还没有很好的理论指导。2.2.2支持向量机的应用(1)人脸检测、验证和识别Osuna最早将SVM应用于人脸检测，并取得了较好的效果。其方法是直接训练非线性SVM分类器完成人脸与非人脸的分类。出于SVM的训练需要大量的存储空间，并且非线性SVM分类器需耍较多的支持向量，速度很慢。为此，有人提出了一种层次型结构的SVM分类器，它由一个线性SVM组合和一个非线性SVM组成。检测时，由前者快速排除掉图像屮绝大部分背景窗口，而后者只需对少量的候选区域做出确认；训练时，在线性SVM组合的限定下，与“自举(bootstrapping)v方法相结合可收集到训练非线性SVM的更有效的非人脸样本，简化SVM训练的难度，大量实验结果表明这种方法不仅具有较高的检测率和较 低的误检率，而且具有较快的速度。人脸检测研究中更复杂的情况是姿态的变化。叶航军等提岀了利用支持向量机方法进行人脸姿态的判定，将人脸姿态划分成6个类别，从一个多姿态人脸库中手工标定训练样本集和测试样本集，训练基于支持向量机姿态分类器，分类错误率降低到1.67%,明显优丁在传统方法中效呆最好的人工神经元网络方法。在人脸识别中，而部特征的提取和识别可看作是对3D物体的2D投影图像进行匹配的问题。由于许多不确定性因素的影响，特征的选取与识别就成为一个难点。凌旭峰等及张燕昆等分别捉出基丁TCA与SVM相结合的人脸识别算法，充分利用了PCA在特征捉取方而的冇效性以及SVM在处理小样本问题和泛化能力强等方而的优势，通过SVM与最近邻距离分类器相结合，使得所捉出的算法具冇比传统最近邻分类器和BP网络分类器更高的识别率。王宏漫等在PCA基础上进一步做1CA,捉取更加冇利于分类的而部特征的主要独立成分；然后采用分阶段淘汰的支持向量机分类机制进行识别。对两组人脸图像库的测试结果表明，基于SVM的方法在识别率和识别时间等方而都取得了较好的效果。（2）说话人/语音识别说话人识别属于连续输入信号的分类问题，SVM是一个很好的分类器，但不适合处理连续输入样本。为此，忻栋等引入隐式马尔可夫模型HMM,建立了SVM和的混合模型。HMM适合处理连续信号，SVM而适合于分类问题；HMM的结果反映了同类样本的相似度，ifijSVM的输岀结果则体现了异类样本间的差异。为了方便与HMM组成混合模型，首先将SVM的输出形式改为概率输出。实验屮使用YOHO数据库，特征捉取采用12阶的线性预测系数分析及其微分，组成24维的特征向量。实验表明HMM和SVM的结合达到了很好的效果。（3）文字/手写体识别贝尔实验室对美国邮政手写数字库进行的实验，人工识别平均错误率是2.5%,专门针对该特定问题设计的5层神经网络错误率为5・1%（英屮利用了大量先验知识），而用3种SVM方法（釆用3种核函数）得到的错误率分别为4.0%、4.1%和4.2%,K是直接釆用16X16的字符点阵作为输入，表明了SVM的优越性能。手写体数字0〜9的特征可以分为结构特征、统计特征等。柳回春等在UK心理测试自动分析系统屮组合SVM和其他方法成功地进行了手写数字的识别实验。另外，在手写汉字识别方而，高学等捉出了一种基于SVM的手写汉字的识别方法，表明了SVM对手写汉字识别的冇效性。（4）图象处理图像处理方而的应用主要包括三方而：〈1＞图像过滤。一般的互联网色情图像过滤软件主要采用网址库的形式来封锁色情网址或采用人工智能方法对接收到的中、英文信息进行分析甄别。段立娟捉出一种多层次特定类型图像过滤法，即以综合肤色模型检验，支持向量机分类和最近邻方法校验的多层次图像处理框架，达到85%以上的准确率。〈2＞视频字幕捉取。视频字幕蕴含了丰富语义，可用于对相应视频流进行高级语义标注。庄越挺等捉出并实践了基于SVM的视频字幕自动定位和捉取的方法。该方法首先将原始图像帧分割为NXN的子块，捉取每个子块的灰度特征；然后使用预先训练好的SVM分类机进行字幕子块和 非字幕子块的分类；最后结合金字塔模型和后期处理过程，实现视频图像字幕区域的自动定位捉取。实验表明该方法取得了良好的效呆。〈3＞图像分类和检索。由于计算机自动抽取的图像特征和人所理解的语义间存在巨大的差距，图像检索结果难以令人满意。近年来出现了相关反馈方法，张磊等以SVM为分类器，在每次反馈中对用户标记的正例和反例样 本进行学习，并根据学习所得的模型进行检索，使用由9918幅图像组成的图像库进行实验,结果表明，在有限训练样本情况下具有良好的泛化能力。223支持向量机的研究热点(1)核函数的构造、修正以及相应参数的调整前面提到，核函数的选取对支持向量机的性能起着非常关键的作用。而核函数可以人为地选取，只要其满足mercer条件。因此，如何构造-•个新的性能较好的核函数、如何修正已有的核函数使其性能提高便成了一个被广泛研究的热点。木设计研究的就是修正核函数问题，这在后面的部分有详细的论述。SVM的核函数有多项式核函数、径向基函数等。尽管一些实验结果表明核函数的具体形式对分类效果的影响不大，但是核函数的形式以及其参数的确决定了分类器的类型和复杂程度，它显然应该作为控制分类器性能的手段。最常用的模型参数选择方法是最小化“留一法(LOO)”错误率。其步骤是：<1>对于j=1,2,I个训练样本，每次取出其中一个样本i,而对其余的L1个训练样本求解式maxvv/1iI(&)=£ai£i=l乙i=j=aiajyiyJxi-xj(2.38)(2.39)(2.40)<2>对L1个样本的训练结果，采用式/(x)=sgn(w•兀+b)N=sgn((》e)M)・x+b)Z=1N=sgn(工ey(£*)+/?)•/=1对第i个样本进行测试<3>反复重复上述步骤。LOO的错误率是/••有•)+与-升心,”升)二1-£:7=1可以看出，用LOO估计错误率的方法来调整参数需耍的训练量很大，因此冇人提出用估计错误率上限的方法来调整SVM的参数。有人提出了儿种估计错误率上限的方法，其中有逐个确认估计、留一法上限估计、用支持向量数与训练样木数的比值估计上限、Jaakkola-Haussler上限、Opper-Winther上限、Radius-margin上限、Span上限。同时，还实现了根据错误率上限的估计来调整SVM参数的算法，其具体思路是：初始化SVM的核函数参数，求解式(2.38),后利用求得的结果估计错误率上限，再利用对错误率上限的梯度下降法调整核函数参数，反复执行上述步骤，宜到得到最小的错误率上限。Chapelle等人T2000年使用基于矩阵的二项规划方法实现了利用LOO上限来调整SVM参数 的方法。应当指出的是，即使对于只有几千个样本的中型问题，也很难在内存中容下整个核函数矩阵，并进行相应的矩阵操作，这种方法有时会带来问题，因此，应当找到一种合适的迭代策略來解决这个问题。(1)提高测试速度SVM判决函数的计算量和支持向量的数目成正比。对于大训练集合，其支持向量的数目会达到几千个，这就使SVM对实验样本的测试判决速度变慢，因此，捉高SVM的测试速度是另一个研究热点。对所右N,个支持向量求和，计算量很大，如果可以减少求和的数目，使其达到M(M〈〈N$)个，则可以大大提高速度。判决函数d(x)的近似式如下：Md(x)=工兀K(X,XJ+b1=1(2.34)据此，Osuna提出3种方案：<1>对d(x)在特征空间中进行拟合，得到一个近似的判决函数心(x):d(x)=$>jK(X,ZJ+bf=l(2.35)其中，厂〈〈N$,Z,是特征空间中的合成向量，不一定是样本点，是权重。<2>判决函数d(x)在特征空间中近似为1=1(2.36)其中，厂〈〈N$,7i是与支持向量X,・对应的权重。<3>对原问题重新定义，得到新的判决两数为d(x)=工兀”K(X,XJ+bJ=1(2.37)其中，厂〈〈N$,X,是某些训练样本点，但不一定是支持向量，兀是权重，片是样本点的类别标号。其中，第1个方案已经被Burges论证，并实现，其基木思想是：在SVM的高维特征空间中，运用比原來少得多的精简集合(ReducedSet,RS)向量來拟合原來所有SV所构成的分界超平面，可以在损失极少信息的基础上，大大提高测试速度。(2)改进训练算法由丁SVM对偶问题的求解过程相当于解一个线性约束的二项规划问题(QP),需要计算和存储核函数矩阵，其人小与训练样本数的平方相关，因此，随着样本数目的增多，所需要的内存也就增人，例如，当样本数目超过4000时，存储核函数矩阵需耍多达128M内存；其次，SVM在二次型寻优过程中耍进行人量的矩阵运算，多数情况下，寻优算法是占用算 法时间的主耍部分。通常，训练算法改进的思路是把耍求解的问题分成许多子问题，然后通过反复求解子问题来求得最终的解，方法有以下几种：<1>块处理算法(chunkingalgorithm)它的思想是将样本集分成工作样本集和测试样本集，每次对工作样本集利用二项规划求得最优解，剔除英屮的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结果(一般是指违反KKT条件)的样本(或其屮的一部分)与本次结果的支持向量合并，成为一个新的工作样本集，然后重新训练。如此重复下去，直到获得最优结果。其依据是去掉Lagrange乘子等丁•零的训练样本不会影响原问题的解。块算法的一个前捉是：支持向量的数目比较少。然而如果支持向量的数目本身就比较多，那么随着训练迭代次数的增加，工作样本数也越来越大，就会导致算法无法实施。<2>固定工作样本集算法它使样本数目固定在足以包含所有的支持向量，R算法速度在计算机可以容忍的限度内。迭代过程屮只是将剩余样本屮部分“情况最糟的样本”与工作样本集中的样本进行等量交换。即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模。冇一种具体的算法，将样本集分为B和N两个集合，集合E作为子问题的工作样本集进行SVM训练，集合N屮所冇样本的Lagrange乘子均置为零。显然，如果把集合B中,对应Lagrange乘子为零的样本i(即a»=0,iGB)与集合N中的样本j(即勺=0,jWN)交换，不会改变子问题与原问题的可行性(即仍I口满足约束条件)。于是可以按照以下步骤迭代求解：①选择集合B,构造了问题；②求了问题最优解e,iWB及b,并置勺=0,jWN;③计算g(x>)y>,jWN,找出其屮g(x>)yJ<1的样本j,(It屮g(x>)=£Q〃yK(Xj,X〃)+b),与B屮满足①二0的样本i交换，构成新的子问题。需要指出：p=i如果集合B不足以包括所有的支持向量，该算法没冇提出改变B的大小的策略，那么有可能得不到结果。<3>SM0算法SM0是固定工作样本集算法的一个极端情况，其工作样本数目为2。需要两个样本，是因为等式线性约束的存在使得同时至少有两个Lagrange乘子发生变化。由于只有两个变量，而且应用等式约束可以将其中一个用另一个表示出來，所以迭代过程中，每一步子问题的最优解都可以直接用解析的方法求出來，这样，算法就避开了复杂的数值求解优化问题的过程；此外，算法还设计了一个两层嵌套循环，分别选择进入工作样本集的样本，这种启发式策略大大加快了算法的收敛速度。标准样本集的实验结果证明，SM0在速度方面表现出良好性能。(1)利用SVM解决多分类的问题曲于支持向量机是针对两分类问题提岀的，因此，存在一个如何将其推广到多分类问题上，特别是对极大类别分类的问题上。目前有以下几种方案：<1>一对多(OneclassVersusallOthers,OVO)其基本想法是把某一种类别的样本当作一个类别，剩余其他类别的样本当作另一个类别，这样就变成了一个两分类问题。这种分类方案的缺点是训练样本数目大。训练困难。 图2.11-对多示意图<2>一对一(OneclassVersusAnotherclass,OVA)其做法是在多类别屮,任意抽取两类进行两两配对，转化成两类问题进行训练学习。识别时，对所构成的多个SVM进行综合判断，一般可采用投票方式来完成多类识别。这种分类方案存在一个明显的缺点，就是子分类器过多，测试时需要对每两类都进行比较，导致测试速度慢。DAG方案在训练阶段也是采用一对一的配对训练方式，它的优点在于，对训练结果的推广性进行了分析，另外，它的测试速度也比一对一的方案要快。图2.12—对一示意图<3>SVM决策树(DecisionTreeMethod,DTM)它通常和二叉决策树结合起来，构成多类别的识别器。这种方法的缺点是如果在某个节点上发生了分类错误，将会把错误延续下去，该节点后续下一级节点上的分类就失去了意义。 图2.13SVM决策树示意图<4>Multi-ClassSVM它直接在目标函数上进行改进，建立k分类支持向量机。由二分类支持向量机进行推广得到目标函数：™n0(w,£工帆『+c工工厂(2.41)厶m=i=〃详”满足约束：0(呂)+by.>吨0(无)+bm+2-即(2.42)孚">0,i=1,A,1mg{1,A,k}兀(2.43)这样目标决策函数为/(x)=argmaxw：0(x)+bn](2.44)n=lAJ利用Lagrange优化方法同样口J以把上述最优分类面问题转化为其对偶问题，得到的函数变量数为灯。这种方法因为变量数目过多，所以只在小型问题的求解中才能使用。另外，SVM的研究点还冇如何把SVM中的核函数内积思想应用到其他方面。Scholkopf等学者首先把核函数的概念引入到PCA中，用核函数实现非线性主元分析，它是传统主元分析(PrincipalComponentAnalysis,PCA)方法的推广。对经典的SVM算法的改进也是一个研究点。Scholkopf提出了一类新的支持向量算法，它运用参数Y來控制支持向量的数目及误差，使新的丫-SVR回归算法更加实用，并把丫-SVR的思想运用到了SV的分类问题中。他还提出了SVR的一•种新算法，从e-SVR到Y-SVR,具有更好的适应性及鲁棒性。此外，冇人研究如何处理样本集合中的一-些特殊点或远点，尤其是样本集中的-些离散点，进一步提高SVM识别器的泛化能力。3•与实际问题相关的修正核函数的基本思想目前，较为常用的核函数有：线性函数，多项式函数，径向基函数，多层感知器函数等。而乂由于其参数训练方法的不同可以得到一些新的核。如：可修改核，自适应核，复合核等等。 支持向量机在理论上对于两分类问题有良好的表现，而这个表现在很大程度上取决于所选择的核函数。然而，在实际应用问题屮，关于如何选择一个好的核函数目前还没有相关的理论。核函数与支持向量机的性能有密切关系，如何构造与实际问题有关的核函数，一直是支持向量机研究的重要课题。针对核函数不好选择的问题,Amari&Wu在其论文uImprovingSupportVectorMachineClassifiersbyModifyingKernelFunctions⑷”中提出一种新的思路：既然目前还没冇较好的理论指导如何选择较好的核函数，但是对于选定的一种核函数，可以对它加以修正，相当于构造一个新的核函数，使得用这个新的核函数的支持向量机的性能更好，即识别率更高。Amari&Wu通过对核函数的黎曼儿何分析，进而设计了一种算法，提出利用实验数据逐步修止已有的核函数的方法。使Z更好地与实际问题和吻合。其数学理论分析如2设特征映射t/=0(兀)，贝ijc/f/=，T~^(x)d兀(注意0(x)是高维向量:)。iOX：IIdU『=工(忙心,这里giJ(x)=芦0⑴)•($0⑴)，称非负定矩阵(gij.(x))为R"上ij^XiOXj(由0(尢)诱导)的黎曼张量。ds1=^g..{x)dxldxj为R”上的黎曼距离。赋予黎曼距离的R”成为黎曼空间。体积微元dv二Jg(x)〃X|•••dx”其中g(x)=det(g/x))。通俗的说，g(x)反映了特征空间中点0(兀)附近局部区域被放大的程度，因此也称g(x)为放大因了。因为K(x,z)=(0(x)・0(z)),可以验证g/7(x)=-^|,_ro特别地对高斯核dxfiZjK(x,z)=exp{—|兀—汀/2*0勺,爲。在本文第二部分的支持向量机的核心内容里，我们知道，对于非线性的分类问题，采取的的方法是利用一个非线性函数将输入空间的样本点映射到高维的特征空间，进而在这个高维的特征空间里找到一个最优超平面将两类划分开。其实，引入核函数的概念后，从匕兀宀)二0(呂)・0(厂)中我们可以直观的认为(非严格意义上的)，核函数对样本点从低维的输入空间到高维的的特征空间的映射起着关键的作用。在模式识别问题中，为了更好地将两类不同的模式区分开，我们希望样本点从输入空间映射到高维的特征空间后，两个类别之间的距离越大越好。确切地说，两个类别的分离曲面之间的距离越大越好。jfljAmari&Wu修止核函数思想直观理解是，通过对核函数Kg、）进行某种修正，使得修正后的这个核函数Ry将样本从输入空间映射到高维空间时，能将两个类别的距离拉的更大。更确切地说，是两个类别的分离曲面的区域拉得更大，而保持其他区域基木不变。但是，人们事先并不知道分离曲面是什么。考虑到支持向量几乎总是出现在分离曲面附近，Amari&Wu经过理论分析提出，可以先用一个基本核函数Kg）进行训练，然后 利用训练得到的支持向量的信息（支持向量以及其对应的匕值）按式（4.1）构造一个新的核函数RgXj），然后用这个新的核函数再次对训练样本进行训练时，能够将特征空间的支持向量所处区域放人，进而能够达到在特征空间两个类别的分离曲面之间的距离被拉得更大的目的，进而可以提高支持向量机的分类性能。其具体思想和步骤如下：设c（x）是R"上正的可微实函数，选择核函数K（Xj，b）（比如选择常用的高斯径向基函数K（xi,xj）=exp{-xj-xj|2/2*o2}）,定义斤（x,x/）=c（Xj）•c（x,K（Xi，Xj）（4.1）其屮，c（x）=工乙exp（-卜如%2）（4.2）keSV根据Mercer定理，斤（x,,xj同样是一个核函数。c（x）中的「＞0是参数，Amari&Wu分析得到，若是对径向基函数修正，厂在%“附近取得最优值。其屮，。是K（X•，兀））=exp{-|兀一兀/$/2*o2}中的参数。于是，Amari&Wu修正方法的训练过程由两步组成：（1）先用基本核KgxJ（径向基函数）进行训练，得到支持向量的有关信息（支持向量以及其对应的匕.值）。（2）再采用式（4」）和式（4.2）对K（x「Xj）进行修正，得到新的核函数然后用仏宀）再次进行训练。然而，Amari&Wu的修正核函数的方法仅仅是从数拯依赖的角度去修正核函数，而没有直接考虑分类间隔的因素。事实上，尤其是在分类间隔很小的情况下，我们总是希望将其映射到高维空间后间隔尽可能大。因此，本设计综合考虑两方面的因素，提岀了基于数据依赖和间隔依赖的用去来修正核函数。其修正核函数的表达式为：0（Xj,Xj）=c（xJ・c（Xj）K（X/,X/）（4.3）c（x）=工*|w|exp（-（4.4）展SV从式4.4我们口J以看出，间隔2/|w|越小，也就意味着C（x）越人，同时Amari&Wu方法中涉及的因索这里也考虑到了。于是，本设计提出的修正方法的训练过程同样曲两步组成：（1）先用基本核K（X「Xj）（径向基函数）进行训练，得到支持向量的有关信息（支持向量以及其对应的匕值）。（2）再采用式（4.3）和式（4.4）对KgxJ进行修止，得到新的核函数补gXj）,然后用0（Xj,Xj）再次进行训练。 4•实验过程与结果分析4.1LIBSVM简介4.1.1LIBSVM的概况LIBSVM⑹是台湾大学林智仁(ChihJenLin)博士等开发设计的一个操作简单、易于使用、快速有效的通用SVM软件包，可以解决分类问题(包括C-SVC、SVC)、回归问题(包括e-SVR、n-SVR)以及分布估计(one・class・SVM)等问题，提供了线性、多项式、径向基和S形函数四种常用的核函数供选择，可以有效地解决多类问题、交叉验证选择参数、对不平衡样本加权、多类问题的概率估计等。LIBSVM是一个开源的软件包，他不仅提供了LIBSVM的C++语言的算法源代码，述提供了Python、Java、R、MATLAB>PerLRuby、LabVIEW以及C#.net等各种语言的接口，可以方便的在Windows或UNIX平台下使用，也便于科研工作者根据自己的需要进行改进(譬如设计使用符合自己特定问题需要的核函数等)。另外述提供了WINDOWS平台下的可视化操作工具SVM-toy,并且在进行模型参数选择时可以绘制岀交叉验证精度的等高线图。LIBSVM在给岀源代码的同时述提供了Windows操作系统下的可执行文件，包括:进行支持向量机训练的svm-train.exe；根据已获得的支持向量机模型对数据集进行预测的svm-predict.exe；以及对训练数据与测试数据进彳亍简单缩放操作的svm-scale.exeo它们都可以直接在DOS环境中使用。LIBSVM使用的一般步骤是：(1)按照LIBSVM软件包所要求的格式准备数据集；(2)对数据进行简单的缩放操作(可跳过)；(3)选取适当的核函数；(4)釆用交叉验证选择最佳参数C与g；(5)釆用最佳参数C与g对整个训练集进行训练获取支持向量机模型；(6)利用获取的模型进行测试与预测。4.1.2LIBSVM的具体的训练和测试方法介绍(1)数据准备libsvm软件包规定训练和测试样本的格式:[label][index1]:[value1][index2]:[value2]label，或说是class,就是要分类的种类，通常是一些整数。index是冇顺序的索引，通常是放连续的整数。value是用來训练和测试的资料，通常是一些实数。例如冇如下的数据样本： +11:1.1474862:0.9441273:0.5718714:0.1578905:1.122710,+21:1.7495772:1.5304413:0.9829774:0.4992045:1.388416(1)训练和测试流程1.用svm-scale來把特征向量规范成所指定的格式(根据样本情况可省略)。2.用svm-train把训练样本数据进行训练，并保存成.model的文件。3•用svm-predictjE测试样本数据进行测试。svm・scale用法为：svm-scale[options]scalingsetfile[scale_file]o其中，options是——些可选的参数项，如丄・u等规定了数据格式的上下界。scaling_set_file是规范化之前的格式。scale_file是规范化之后的格式。svm・trairi用法为：svm-train[options]trainingsetfile[model_file]o其中，options是一些可选的参数项，如・t规定了SVM的核函数的类型，gd才等则规定核函数中所需的一些参数。ti*aining_set_file是训练之前的样本文件。modelfile是训练之后的样本文件。svm-train实现对训练数据集的训练，获得SVM模型。svm-prcdict用法：svm-prcdict[options]tcst_f订cmodcl_filcoutput_f订e。其屮，options是操作参数，・bprobability_estimates:是否需要进行概率估计预测，可选值为0或者1,默认值为0omodelfile是由svmtrain产生的模型文件；test_file是要进行预测的数据文件；output_flle是svmpredict的输出文件，表示预测的结果值。svmpredict没有其它的选项。svmpredict是根据训练获得的模型，对数据集合进行预测。4.1.3LIBSVM软件包文档介绍(1)svm.h中的主要声明语句enum{C_SVC,NU_SVC,ONE_CLASS,EPSILON_SVR,NU_SVR}；声明SVM的类型。enum{LINEAR,POLY,RBF,SIGMOID,MULTI_QUADRATIC,MODIFIEDRBF}；声明SVM核函数的类型。(2)svm.cpp中的二次规划的优化子模块Solve<1>功能：把支持向量机屮涉及到的二次规划问题进行优化，从而得到SVM分类器的判别函数。<2>接口设计：经过优化后，所计算出來的值一个存放到变量alpha中，一个存放到变量obj中，而该函数本身无返回値。<3>代码见附录k(3)训练特征向量样本子模块svm-train<1>功能：对训练样本进行训练，并将训练得到的结果(包描支持向量和对应的少值 等)保存在model文件中。＜2＞数据设计：变量argc（svm-train执行时的参数个数）和**argv（svm-train执行时的参数）。＜3＞接口设计：输入数据为一个包含许多特征向量的文件:training_set_file,该模块会将训练好的数据及结果保存到另一个mode文件model_file中。＜4＞模块的算法设计：输入程序所需要的各种参数-＞读入包含特征向量的文件-＞对输入的参数进行检查・・＞参数检查・・＞对训练样本进行训练，将训练得到的结果（包括支持向量支持向量和对应的色值等）保存在model文件中。＜5＞代码见附录2。图5.1SVM训练流程图（4）测试特征向量数据子模块svm-predict＜1＞功能：通过支持向量机对测试样本进行测试，显示相关结果（支持向量数、识别率等）。＜2＞数据设计：变量argc（svm-predict执行时的参数个数）和**argv（svm-predict执行时的参数）。 ＜3＞接口设计：输入数据为一个包含测试数据的文件（test_flle）和svm-train训练好 的model文件（model_file），该模块会将测试结呆保存到另一个文件：output_fileQ<4>模块的算法设计：输入程序所需要的各种参数亠读入包含测试样本的文件亠对输入的参数进行检查亠对测试样本进行预测、输出识别率等并将测试结果保存在output_file文件中。<5>代码见附录3。 图5.2SVM测试流程图4.2实验过程4.2.1实验数据本实验是以标准字库GB2312-80一级字库中的16区、20区、34区和46区的汉字样木作为主耍的实验数据。每个区有94个汉字，而每个汉字均有50多个不同的手写体样本。这些样本是采用弹性网格方向分解特征提取法得到的。根据选取的网格不同又分为4*4网格、6*6网格、8*8网格。为了测试更多组数据、也为了节省吋间（修正核的过程需耍迭代很多次，耗费吋间相对长)，本实验将上述各区的数据分为10类20类的情况分别进行实验。对丁•每个汉字的50多个不同的手写样本，前40个样本用作训练，而后而剩余的样本作为测试样本。同时，为了进一步比较修正前后的性能，本设计述对台湾大学林智仁博士个人网站http://www.csie.ntu.edu.tw/~cjlin/libsvm/index・html上白勺论文"ApracticalguidetoSVMclassification”⑸屮的两组比较典型的数据进行了训练和测试，对这两组数据釆用的方法是文章里提到的"Scaledsetswithparameterselection”,即先L1BSVM里的scale,ext对数据进行缩放，然后用grid,py找岀最优参数，再进行训练和测试。4.2.2修正核函数的编程思路和关键木设计实现的是对径向基函数的修正。修正方法是分别按Amari&Wu的思想和木设计提出的思想对径向基函数进行修正。即分别按照斤(兀,xj)=c(xJ•c(xJ)K(X,.,Xj)(4.5) c(x)=工匕exp(-H%2)(4.6)AeSV和K'(x，x))=c(xJ・c(xj)K(x)(4.7)c(x)=工*Wexp(-Z叨2)(4.8)辰SV对径向基函数进行修正。而c(X)中的的参数Xk和也是用KZj)训练一次后得到的支持向量和相应的6^值。由于用KgXj)训练时，会产生一个model文件，model文件里保存了训练的结果(包括支持向量Xk和相应的色)。故可以从model文件屮读入C(x)的参数Xk和务。|w|的值在训练过程中也能计算出来，并可以保存在model文件屮。同时，虽然训练和测试中理论上用的是同样的核函数，但在L1BSVM+,为了英程序的某种方便，训练和测试用的核函数的实现的方式是不一样的。所以，编程时两个核函数的实现方式都应当加以修正。在本设计中，就要而修正的方法冇两种。一种是直接在原来的核函数“里而”修正，即在核函数里而乘以C(XJ和C(XJ,使得核函数的接口不变，但函数里的代码已经变T,修正后的这个核函数已经不是原来的核函数了。另一种方法是在核函数“外而”修正,即不改变核函数的接口和里面的代码，但每次耍调用Kg®)时，都在其外面乘以C(XJ和C(X＞即丘(Xj,Xj)=c(Xi)・c(Xj)K(Xi，Xj)。本设计为了程序的方便，也为了保证原来的LIBSVM程序里的某种一致性，在对训练时用到的径向基函数doublekemel_rbf(inti,intj)const采用了在“里血”修止的思想，而对在测试时用到的径向基函数doubleKernel::k_function(constsvmnode*x_yang,constsvmnode*y_yang,constsvm_parameter¶m)采亦了在“外面”修正的方法。另外，特别值福注意的是，式(4.1)与式(4.3)中的Xk、%和|w|是针对两分类的情况，而LIBSVM考虑了多类的情况，所以为保持程序的“通用性”，修正核函数吋也应当考虑多类的情况。这就要为多类情况的每一个向量机(若有n个类别，贝IJ有n*(n-l)/2个向量机)选择对应的Xk、也和|w|作为C(x)的参数。4.2.3实验过程(1)精读和理解LIBSVM软件包的关键代码，并在其基础上分别按按4.2.2屮的两种修止核函数的思想编程实现Amari&Wu的思想。(2)选择一个核函数(本实验选择的是高斯径向基函数心兀,•内)=exp{—|兀—兀卄々*。?}),并用这个函数对训练样本进行训练。训练后会产生一个model文件，里面保存着训练结果(包括支持向量和对应的匕值以及|w|等)。然后对相应的测试样本进行测试，记录测试结果，以方便比较未修正核函数的SVM(原来的LIBSVM,木文简称之为SVM-1)和修正核函数后的SVM(在LIBSVM基础上编程实现的SVM,本文分别简称之为SVM-alpha.SVM-W)的分类性能。 (1)将(2)产生的model文件拷贝到SVM-alpha的Debug文件夹下,并改名为“old.Models这是因为程序里是按这个名读取Xk、创h和阿的)。再用SVM-alpha.SVM-W对(2)中同样的训练样本和测试样本分别进行训练和测试。(2)比较SVM-l、SVM-alpha和SVM二W的性能,包括识别率、支持向量数、边界支持向量数。4.2.4实验结果及分析(1)向量机说明：下表屮SVM-1表示原来未修正的SVM(LIBSVM),SVM-alpha是在LIBSVM的基础上按Amari&Wu的思想修正核函数后的SVM,也就是按式(4.1)和式(4.2)修正后的SVM。而SVM-W则是按木设计提出的式(4.3)和式(4.4)修正核函数后的SVM。(2)数据说明：以trl6440110.tel6440110为例，trl6440110表示对16区第1个到第10个汉字(共10类)按4*4网格提取特征向量的样本(94维)的各口前40个样木(共400个)组成的txt文件tr16440110.txt进行训练,对各个汉字剩下的样本组成的txt文件tel6440110.txt进行测试。(3)参数说明：因为LIBSVM采用默认参数吋对用弹性网格方向分解特征提取法得到的手写体汉字样本的识别率比较高，所以训练这些数据(表4.1至表4.16)时用的是默认参数。而用默认参数对表4.17中的数据的识别率不是很高，所以采用的是相对“最优参数”(用LIBSVM软件包里的grid,py得到的相对最优的参数)。注意，径向基函数冇两种表示法，除了上面提到的K(xj,xj)=exp{-xi-xj2/2*o2},还可以表示为K(无，©)=exp{-gamma*|xi-xj|2}。所以gamm沪1/2*o*o。LIBSVM中采用的是用gamma的表示法。下表屮的参数g就代表gamma值，采用的是默认值1/k(k为训练样本的 维数）。经大量的实验表明，C（X）里的参数T在附近取得最优值，所以在木设计的实验过程中，T取的就是J17（2冠g）。另外，表格中训练结果中NBSV"多”表示总的边界支持向量（这里对于多类的情况，只要在某个支持向量机中是边界支持向量，就算是边界支持向量）的个数在100以上，“屮”表示边界支持向量的个数在50和100Z间。“少”表示边界支持向量在50以下。（4）结果如下：衣4.116区10类4*4网格SVM-1(默认参数)c=l;g=l/64=0.015625SVM-alphac=l;g=0.015625SVM-Wc=l;g=0.015625数据训练结杲测试结果训练结杲测试结果训练结果测试结果NSVNBSV识别率（％）NSVNBSV识别率（％）NSVNBSV识别率（％）tri6440110tel6440110338多(123/136)90.442770(119/136)87.502780(120/136)88.23trl6441120tel6440110338多(99/103)96.112810(100/103)97.082810(101/103)98.05tri6442130tel6442130287多(105/108)97.222320(104/108)96.292310(104/108)96.29tri6443140tel6443140308多(98/103)95.152420(98/103)95.152410(98/103)95.15tri6444150tc16444150318多(112/120)93.332580(111/120)92.502530(112/120)93.33tri6445160tel6445160280(107/110)97.272070(110/110)100.002100(110/110)100.00tri6446170tel6446170348多(99/110)90.002720(103/110)93.632720(102/110)92.72tri6447180tel6447180317多(102/109)93.582740(105/109)96.332700(104/109)95.41tri6448190tel6448190340多(84/100)84.003020(85/100)85.003020(86/100)86.00表4.216区10类6*6网格SVM-1(默认参数)c=l;g=l/144=0.006944SVM-alphac=l;g=0.006944SVM-Wc=l;g=0.006944数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率（％）NSVNBSV识别率（％）NSVNBSV识别率（％）trl6660110tel6660110323中(130/136)95.583010(130/136)95.582970(131/136)96.32 tri6661120tcl6660110311少(101/103)9&062810(102/103)99.022750(102/103)99.02tri6662130tel6662130302少(105/108)97.222590(106/108)9&142520(106/108)98.14trl6663140tel6663140306少(99/103)96.112710(100/103)97.082730(100/103)97.08tri6664150tel6664150309少(117/120)97.502730(116/120)96.662650(116/120)96.66tri6665160tel6665160298少(110/110)100.002500(110/110)100.002530(110/110)100.00tri6666170tel6666170335少(109/110)99.092940(110/110)100.002950(109/110)99.09tri6667180tel6667180308少(108/109)99.082810(108/109)99.082750(107/109)98.16tri6668190tc16668190340少(90/100)90.003120(89/100)89.003120(89/100)89.00表4.316区10类8*8网格SVM-1(默认参数)c=l;g=l/l/256=0.003906SVM-alphac=l;g=0.003906SVM-Wc=l;g=0.003906数据训练结杲测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率（％）NSVNBSV识别率（％）NSVNBSV识别率（％）trl6880110tcl6880110338少(132/136)97.053120(132/136)97.053030(132/136)97.05trl6881120tel6880110332少(103/103)100.002920(103/103)100.002870(103/103)100.00trl6882130tel6882130332少(104/108)96.292860(106/108)98.142830(106/108)98.14tri6883140tel6883140326少(100/103)97.082840(101/103)9&052770(101/103)98.05trl6884150tel6884150310少(119/120)99.162860(119/120)99.162830(119/120)99.16trl6885160tc16885160319少(109/110)99.092740(109/110)99.092620(109/110)99.09trl6886170tel6886170358少(110/110)100.003270(110/109)100.003180(110/110)100.00trl6887180tel6887180337少(107/109)98.162880(108/109)99.082640(108/109)99.08tri6888190tel6888190356少(96/100)96.003310(95/100)95.003290(94/100)94.00 表4420区10类4*4网格SVM-1(默认参数)c=1;g=1/64=0.015625SVM-alphac=l;g=0.015625SVM-Wc=l;g=0.015625数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率（％）NSVNBSV识别率（％）NSVNBSV识别率（％）tr20440110te20440110310中(158/162)97.532590(157/162)96.912650(156/162)96.29tr20441120te20440110313屮(152/159)95.592700(155/159)97.432660(153/159)96.22tr20442130te20442130325中(146/159)91.822760(145/159)91.192790(144/159)90.56tr20443140tc20443140341中(149/160)93.122950(154/160)96.252950(154/160)96.25tr20444150te20444150309中(157/159)98.742580(157/159)98.742560(157/159)9&74tr20445160te20445160322中(154/162)95.062700(153/162)94.442700(153/162)94.44tr20446170te20446170347屮(149/159)93.713060(149/159)93.713040(149/159)93.71tr20447180te20447180334中(148/158)93.672870(148/158)93.672900(148/158)93.67tr20448190tc20448190306中(157/158)99.362630(157/158)99.362630(157/158)99.36表4.520区10类6*6网格SVM-1(默认参数)c=l;g=1/144=0.006944SVM-alphac=l;g=0.006944SVM-Wc=l;g=0.006944数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率（％）NSVNBSV识别率（％）NSVNBSV识别率（％）tr20660110tc20660110305少(159/162)98.142700(159/162)98.142710(159/162)98.14tr20661120te20660110319少(159/159)100.002870(157/159)98.742820(157/159)98.74tr20662130tc20662130351少(153/159)96.223190(151/159)94.963170(151/159)94.96tr20663140te20663140343少(156/160)97.503050(156/160)97.502990(157/160)98.12tr20664150te20664150331少(159/159)100.002940(159/159)100.002950(159/159)100.00 tr20665160tc20665160335少(159/162)98.142900(158/162)97.532910(158/162)97.53tr20666170te20666170346少(154/159)96.853140(154/159)96.853140(154/159)96.85tr20667180te20667180349少(151/158)95.563150(151/158)95.563180(152/158)96.20tr20668190te20668190314少(156/158)9&732830(156/158)9&732750(154/158)97.46表4.620区10类8*8网格SVM-1(默认参数)c=l;g=l/l/256=0.003906SVM-alphac=l;g=0.003906SVM-Wc=l;g=0.003906数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率（％）NSVNBSV识别率（％）NSVNBSV识别率（％）tr20880110te20880110338少(158/162)97.533050(158/162)97.532940(158/162)97.53tr20881120te20880110345少(159/159)1002980(159/159)100.002870(159/159)100.00tr20882130te20882130354少(156/159)9&113230(156/159)98.313200(156/159)9&11tr20883140te20883140363少(159/160)99.373310(160/160)100.003310(160/160)100.00tr20884150tc20884150353少(159/159)1003250(159/159)100.003150(159/159)100.00tr20885160te20885160344少(158/162)97.533020(159/162)98.143000(158/162)97.53tr20886170te20886170362少(155/159)97.483310(155/159)97.483320(155/159)97.48tr20887180te20887180348少(155/158)98.103290(154/158)97.463220(154/158)97.46tr20888190te20888190348少(157/158)99.362910(157/158)99.362850(157/158)99.36 tr46445160te46445160tr46444150te46444150tr46443140tc46443140tr46442130te46442130tr46441120te46440110tr46440110te4644011013329O2263s2OC7VSVM-1(默认参数)c=l;g=1/64=0.01562579NBsV(147/150)98.00(145/149)97.31(145/150)96.66(140/150)93.33(155/165)93.93(150/150)100.00o2222575悬VSVM-alphac=l;g=0.015625ooOoOoNB2(146/150)97.33(144/149)96.64(145/150)96.66(143/150)95.33(160/165)96.96(150/150)100.0023OC2忌2277252N三SVM-Wc=l;g=0.015625OoOOOoNB(146/150)97.33(144/149)96.64(145/150)96.66(143/150)95.33(160/165)96.96(150/150)100.00爼4・846冈10號4£匡农tr34448190te34448190tr34447180te34447180tr34446170tc34446170tr34445160te34445160U34444150te34444150tr34443140te34443140tr34442130te34442130tr34441120tc34440110tr34440110te344401103bo3339323352£325VV7甘(322/329)97.87(285/330)86.36(317/330)96.06(300/330)90.90(302/330)91.51(324/330)98.18(315/330)95.45(329/330)99.69(303/328)92.372632932873O2229bo2372gNSVM-alphac=l;g=0.015625OOOoOOoOO(322/329)97.87(292/330)88.48(319/330)96.66(312/330)94.54(309/330)93.63(328/330)99.39(313/330)94.84(329/330)99.69(306/328)93.292g2922000038222230025OOSVM-Wc=l;g=0.015625OOooooOOO(322/329)97.87(288/330)87.27(319/330)96.66(312/330)94.54(310/330)93.93(327/330)99.09(313/330)94.84(329/330)99.69(307/328)93.59煤4・734区10泯4£同茨 tr46446170tc46446170316少(146/150)97.332580(146/150)97.332630(146/150)97.33tr46447180te46447180285少(149/149)100.002350(148/149)99.322330(148/149)99.32tr46448190te46448190303少(150/150)100.002360(150/150)100.002350(150/150)100.00表4.916区20类4*4网格SVM-1c=lg=l/64=0.015625SVM-alphac=lg=0.015625SVM-Wc=lg=0.015625数据训练结果测试结呆训练结果测试结果训练结果测试结呆NSVNBSV识别率(%)NSVNBSV识别率(%)NSVNBSV识别率(%)trl6440110tel6440120728中(221/239)92.56380(217/239)90.806200(217/239)90.8tri6442140tel6442140657中(203/211)96.25410(204/211)96.685100(202/211)95.73tri6444160te16444160654少(218/230)94.75290(220/230)95.65240(220/230)95.65tri6446180tel6446180705中(197/219)89.96050(208/219)94.975880(203/219)92.69表4.1016区20类6*6网格SVM-1c=l沪1/128二0.0078125SVM-alphac=lg=0.0078125SVM-Wc=lg二0.0078125数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率(％)NSVNBSV识别率(%)NSVNBSV识别率(%)tri6660120tc16660120685少(231/239)96.656780(231/239)96.656810(230/239)96.26tri6662140tel6662140652少(204/211)96.685640(206/211)97.635560(206/211)97.63tri6664160tel6664160641少(227/230)98.695480(225/230)97.835510(225/230)97.83tri6666180tel6666180688少(216/219)98.606100(217/219)99.096090(216/219)98.63 表4・1116区20类8*8网格SVM-1c=lg=l/256=0.00390625SVM-alphac=lg=0.00390625SVM-Wc=lg=0.00390625数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率偏)NSVNBSV识别率(%)NSVNBSV识别率(%)trl6880120tcl6880120705少(235/239)9&306950(236/239)9&76960(236/239)9&74trl6882140tel6882140697少(203/211)96.206070(206/211)97.636000(206/211)97.63trl6884160tel68841606760(228/230)99.105900(228/230)99.105790(228/230)99.10trl6886180tel6886180722少(217/219)99.006200(218/219)99.546340(218/219)99.54表4.1220区20类4*4网格SVM-1c=lg=l/64=0.015625SVM-alphac=lg=0.015625SVM-Wc=lg=0.015625数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率(%)NSVNBSV识别率(%)NSVNBSV识别率(%)tr20440120te20440120711中(297/321)92.526220(305/321)95.026250(301/321)93.77tr20440120te20440120724中(284/319)89.036450(287/319)89.906430(293/319)91.85tr20440120te20440120677中(306/321)95.336100(308/321)95.956040(308/321)95.95tr20440120tc20440120712中(291/317)91.796480(290/317)91.486500(291/317)91.79表4.1320区20类6*6网格SVM-1c=lg=l/128=0.0078125SVM-alphac=lg=0.0078125SVM-Wc=lg=0.0078125数据训练结果测试结果训练结果测试结果训练结果测试结果NSVNBSV识别率(%)NSVNBSV识别率(%)NSVNBSV识别率(%)tr20660120te20660120691少(313/321)97.516140(313/321)97.516120(313/321)97.51tr20662140tc20662140740少(308/319)96.556770(305/319)96.616770(306/319)95.92tr20664160te20664160703少(313/321)97.516150(313/321)97.516150(313/321)97.51tr20666180te20666180723中(302/317)95.276610(300/317)94.646700(299/317)94.32 tr46442140te46442140tr46440120te46440120a67466OVSVM-1c=l萨1/64二0.015625s(282/300)94.00(302/3⑸95.87585567胡VSVM-alphac=lg=0.015625OONtcsV(284/300)94.67(307/315)97.4659256O胡VSVM-Wc=l萨0.015625OONtcsV(282/300)94.00(307/315)97.46爼4・1646区20滋4诜4巨忝tr34446180te34446180tr34444160tel6444160tr34442140te34442140tr34440120tc34440120569756VSVM-1c=lg=l/64=0.015625三->§(585/660)8&64(599/660)90.76(634/660)96.06%(626/658)95.14636g7562559誘VSVM-alphac=lg=0.015625OOOO§(595/660)90.15(618/660)93.64(630/660)96.52(631/658)95.9635g756005VSVM-Wc=lg=0.015625OOoO§(595/660)90.15(620/660)93.94(634/660)96.21(631/658)95.75煤4・1534区20寒4关4迓改tr20886180te20886180tr20884160tc20884160tr20882140te20882140tr20880120te20880120d567nJ4VSVM-1c=lg=l/256=0.00390625797§(310/317)97.79(315/321)98.13(311/319)97.49(312/321)97.207O665665O誘VSVM-alphac=lg=0.00390625oOOo§(307/317)96.85(315/321)98.13(312/319)97.81(315/321)98.136里6O2635胡VSVM-Wc=lg=0.00390625OOOONBSV(309/317)97.48(317/321)98.75(312/319)97.81(314/321)97.82爼4」420冈20/'oo.os逶承 tr46444160tc46444160692少(290/299)96.995880(289/299)96.655910(289/299)96.65tr46446180te46446180664少(288/299)96.325590(288/299)96.325630(288/299)96.32表4.17林智仁博士论文“Guide”里的两组典型数据SVM-l“最优参数"c=2;g=2SVM-alphac=2;g=2SVM-Wc=2;g=2训练结果测试结呆训练结果测试结果训练结果测试结果NSVNBSV识别率(%)NSVNBSV识别率(%)NSVNBSV识别率(%)train.1.txttest.1..txt368331(3876/4001)96.87621279(3801/4001)95.00120650(3800/4001)94.98train3.txttest3.txt472245(37/42)88.0953680(42/42)100.003690(42/42)100.00(5)结果分析：从上述表格的结果中不难发现如下共同特点：〈1＞并不是对于所有的样木，修正核函数后的识别率都高。但从总体来看，不管是按照Amari&Wu的方法修正核函数还是按照本设计提岀的方法修正核函数，SVM的识别率都有所提高，这种提高在4*4网格的数据中表现比较明显，但在6*6和8*8网格的数据中表现得不是很明显。原因分析:该手写体样本是通过弹性网格方向分解特征捉取法得到的。网格越多，提供的用于“学习”的“知识”就越多。6*6、8*8网格的训练数据提供的“知识”比较多，未修正核函数的SVM(LIBSVM)对其的识别率已经很高，所以修正核函数后识别率提高不是很明显。而修正后的svm对4*4网格的样本的识别率提高相对明显。〈2＞修止核函数后支持向量数和边界支持向量数都明显卜•降，边界支持向量的数目竞然都是Oo这表示修正核函数后，训练过程屮的复杂度降低了，并可以将对训练样本的错分率降为0。同时我们可以发现，采用本设计提出的方法修正核函数比采用Amari&Wu的方法修正核函数后的支持向量更少，因此训练过程屮的复杂度更低。事实上，这和前面讲的修正核函数的思想是很相符的。修正的核函数将样本点从输入空间映射到高维空间时，能将两个类别的分离曲面Z间的距离拉得更大，这样便越不容易错分。〈3＞存在的问题：曲于在程序中让算以及计算判别函数值以预测未来数据时调用核函数的次数很多，而我们修正核函数的思路是对每一次的核函数的计算都要乘以c(xi)和c(xj),而计算c(xi)和c(xj)都要迭代很多次,所以运行时间相对长一些,这也是符合理论的。而意想不到的是，按木设计提出的方法修止核函数的SVM的运行速度要比按Amari&Wu捉岀的方法修正核函数的SVM的速度快。综合以上分析，本设计还是比较成功的，其不仅实现并通过实验验证了Amari&Wu的修正核函数的思想，而且受Amari&Wu思想的启发，木设计又把间隔因素加入了修正核函数中，取得了不错的效果。因此，本设计对修正核两数的研究有着重要的意义。 三口尔！口此刻，在毕业设计即将结束的吋候，冋想起自己这两个多月来的学习、钻研过程，再想想这让自己满意的成果，我觉得，我收获颇多、感触颇深，主要有以下几点体会。（1）搞研究需耍成就感的支撑。支持向量机（SVM）是基于统计学习理论的一种机器学习方法，其理论比较高深。刚开始选这个题全然是因为好奇，因为我真的很想知道“机器”是怎么“学习”的。而选好题后刚开始的时候也碰了不少壁，加上以前从没接触过这类问题，所以方向感很不明确。但逐渐地，随着对SVM的认识的不断加深，我逐渐地对其“巧妙”的理论产生了兴趣。后来常常会因为理解了一些原本以为很高深的理论而欣喜不已。我想，这便是成就感吧，这种感觉太棒了！这也是支撑我这两个多月来一直能保持饱满的激情专心丁毕业设计的很大一个原因。由此我想到，英实对于任何必须做的事情，都应当让自己喜欢去做。或许刚开始你会遇到难题、感觉没有方向，但只要坚持下去，不断地获得一些成就感后，就会很自然地喜欢去做了。（2）不要害怕遇到问题，而是要在不断地解决问题的过程中提高自己的能力。冈IJ开始，我比较害怕遇到问题，特别是新问题。但后来发现，我前面讲的成就感就来源于解决问题。我也发现，自己在不断地遇到问题和解决问题的过程屮执行能力增强了不少。到后来，我觉得我有了一种希望遇到问题、挑战问题的心态。（3）只有像做毕设这样相对大的项口，才能把很多东西“串”起来，更加深刻地理解以前学过的内容。本设计做的是在LTBSVM软件包的基础上修正核函数，首先就要把LIBSVM软件包的关键代码看透。在看LIBSVM软件包的过程中，我重新复习了C++和C语言的一些相关内容，有些以前比较模糊的概念也在看软件包的过程中弄清楚了。（4）讨论和交流是学习的一个重要途径。比如，在理解SVM的思想和读LIBSVM软件包的吋候，我和做相关题口的同学经常讨论。我们经常'有不同的想法，但每次讨论完后都会得到双方都认可的结论。而11,经过这样的讨论，我们对其印象非常深刻。另外，对于有些不理解的问题，我也采取了很多途径进行交流，如关于SVM的QQ学习群、SVM论坛甚至给台湾大学林智仁博士发邮件等方式。这往往不仅让我理解了自己想要知道的问题，冇时甚至会有意外的收获。总之，我觉得我的木次毕业设计还是比较成功的，我在其屮的努力也没有白费，我也感觉真的学到了不少东西。这个过程也可以看做是我踏入研究生阶段学习的一个过渡。在这个过程中，我体会到了搞研究的快乐，这对我的研究生阶段的学习有着非常重要的积极 致谢首先，借此机会真诚地感谢指导老师孙立民老师。木设计的顺利完成，与孙老师的悉心帮助是分不开的。孙老师虽然公务繁忙，但仍非常关注着我的设计，不断地给我提供一些指导和建议，也给了我不少鼓励和信任。也正是在孙老师的殷切关怀下，我毕业设计的进展很快、在其中学到的东四也很多。同时，孙老师严谨的治学态度、不知疲倦的工作精神也很让我震撼，我也应当向孙老师学习。我也要感谢潘妍学姐、公绪成学长、辛英、胡海威等在毕设期间给过帮助的朋友。也借此机会感谢所有在大学期间给我提供过帮助的老师和同学们！ 参考文献[1]V.Vapnik.TheNatureofStatisticalLearningTheory.NewYork：Springer-Verlag.1995[2]V.Vapnik.StatisticalLerningTheory.Wiley.NewYork.1998[3]Chih-ChungChangandChih-JenLin.LIBSVM—ALibraryforSupportVectorMachines.http://www.csie.ntu.edu.tw/~cjlin/libsvm/[4]S.AmariandS.Wu.Improvingsupportvectormachineclassifierbymodifyingkernelfunction.J.NeuralNetworks.1999[5]Chih-WeiHsu,Chih-JenLin.ApracticalGuidetoSupportVectorClassification.http://www.csie.ntu.edu.tw/~cjlin/libsvm/⑹杜树新，吴铁军.模式识别中的支持向量机方法（浙江大学学报）.杭州：浙江大学.2003[7]祁享年.支持向量机及其应用研究综述（计算机工程）.林安：浙江林学院.2004[8]柳冋春，马树元.支持向量机的研究现状（中国图象图形学报）•北京：北京理工大学.2002[9]王国胜，钟义信.支持向量机的若干新进展（电子学报）.北京：北京邮电大学.2001 附录1求解二次规划问题的关键代码voidSolver::Solve(int1,constQMatrix&Q,constdouble*b_,constschar*y_,double*alpha_,doubleCp,doubleCn,doubleeps,Solutionlnfo*si,intshrinking){this->l二1;this->Q二&Q;QD=Q.get_QD();clone(b,b_,1);clone(y,y_,1);clone(alpha,alpha_,1);this->Cp二Cp;this->Cn二Cn;this->eps二eps;unshrinked二false;//initializealpha_status{alpha_status二newchar[1];for(inti二0;i〈l;i++)update_alpha_status(i);}//initializeactiveset(forshrinking){active_set二newint[1];for(inti二0;i〈l;i++)active_set[i]二i;active_size二1;}//initializegradient{G二newdouble[l];G_bar二newdouble[l];inti;for(i二0;i0){if(alphatj]<0){alphatj]=0;alpha[i]=diff;}}else{if(alpha[i]<0){alpha[i]=0;alpha[j]=-diff;}}辻(d辻f>C_i-C_j){if(alpha[i]>C_i){alpha[i]=C_i;alpha[j]=C_i-diff;}}else{if(alphatj]>C_j){alphatj]=C_j;alpha[i]=C_j+diff;}}}else{doublequad_coef=Q_i[i]+Q_j[j]-2*Q_订j];if(quad_coef<=0)quad_coef=TAU;doubledelta=(G[i]-G[j])/quad_coef;doublesum=alpha[i]+alpha[j];alpha[i]-=delta;alpha[j]+二delta;if(sum>C_i){if(alpha[i]>C_i){alpha[i]=C_i;alpha[j]=sum-C_i; }}else{if(alpha[j]<0){alpha[j]=0;alpha[i]=sum;}}if(sum>C_j){if(alpha[j]>C_j){alpha[j]=C_j;alpha[i]=sum-C_j;}}else{if(alpha[i]<0){alpha[i]=0;alpha[j]=sum;}}}//updateGdoubledelta_alpha_i=alpha[i]-old_alpha_i;doubledelta_alpha_j=alpha[j]-old_alpha_j;for(intk=0;krho=calculate_rho();//calculateobjectivevalue{doublev=0;inti;for(i=0;iobj=v/2;}//putbackthesolution{for(inti=0;iupper_bound_p=Cp;si->upper_bound_n=Cn;info(〃 optimizationfinished,#iter=%d /z,iter);delete[]b;delete[]y;delete]]alpha;delete[]alpha_status;delete[]active_set;delete]]G;delete[]G_bar; 附录2支持向量机训练的关键代码intmain(intargc,char**argv){charinput_file_name[1024];charmodel_file_name[1024];constchar*error_msg;first,end;doubledif;parse_command_1ine(argc,argv,input_fi1e_name,model_fi1e_name);time(&first);read_problem(input_fi1e_name);error_msg二svm_check_parameter(&prob，¶m);if(error_msg){fprintf(stderr,/zError:%s 〃，error_msg);exit(1);}if(cross_validation){do_cross_validation();}else{model二svm_train(&prob,¶m);svm_save_model(model_file_name,model);svm_destroy_model(model);}svm_destroy_param(¶m);free(prob,y);free(prob.x);free(x_space);time(&end);dif二difftime(end,first);printf(〃 共耗时:%.2fsec 〃,dif);return0; 附录3支持向量机测试的关键代码intmain(intargc,char**argv){FILE*input,*output;inti;//parseoptionsfor(i=l;i=argc)exit_with_help();input二fopen(argv[i],/zr/z);if(input二二NULL){fprintf(stderr,/zcan'topeninputfile%s /z,argv[i]);exit(1);}output二fopen(argv[i+2],〃w〃)；if(output==NULL){fprintf(stderr,/zcan'topenoutputfile%s /z,argv[i+2]);exit(1);}if((model=svm_load_model(argv[i+l]))==0){fprintf(stderr,/zcan'topenmodelfile%s /z,argv[i+l]);exit(1);}line二(char*)malloc(max_line_len*sizeof(char));x二(structsvm_node*)malloc(max_nr_attr*sizeof(structsvm_node));if(predict_probabi1ity)if(svm_check_probability_model(model)=0){fprintf(stderr,，zmodeldoesnotsupportprobabiliyestimates'll");predict_probability=0;} predict(input,output);svm_destroy_model(model);free(line);free(x);fclose(input);fclose(output);return0; 附录4Amari&Wu方法修正咼斯径向基函数关键代码说明：下面关键代码均在svm.cpp中。(1)训练过程的高斯径向基函数的修正代码doublekcrnel_rbf(inti，intj)const{/*该函数的参数i和j是提供了两个向量x[i]和x[j],而此刻训练的应当是第i_class类和第j_class类*/intsi_old=start_old_train[i_class];intsj_old=steirt_old_trEiin[j_c1qss];intci_old=model_old_train->nSV[i_class];intcj_old=model_old_train->nSV[j_class];double*coefl_old=model_old_train->sv_coef[j_class-l];double*coef2_old=model_oldtrain->sv_coef[i_class];/*每次用多少kvaluct]则算多少;每次只针对两类求相应值，每次只从大问题里“捉取”相应值*/intk;intN_i_j_sv_old=N_yangben;//用来调参数tstructsvmparameterparamiclass_jclass=model_c)ld_train->param;param_iclass_jclass-gamma=param_iclass_jclass-gamma*N_i_j_sv_old;//先求岀C(x[i])doublesum_cxi=0;//c(x[i])for(k=0;kSV[si_old+k],param_iclass_jclass);//kvalue[si+k]:第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj_old+k],param_iclass_jclass);//kvalue[sj+k]：第j类的0号支持向量到ci~l号支持向量//再算岀c(x[j])doublesum_cxj=0;for(k=0;kSV[si_old+k],param_iclass_jclass);//kvalue[si+k];〃第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj_old+k],param_iclass_jclass);//kvalue[sj+k]：第j类的0号支持向量到ci~l号支持向量returnsum_cxi*sum_cxj*exp(-gamma*(x_square[i]+x_square[j]-2*dot(x[i],x[j])));//这里的gamma是“新的”(在dos下输入的)，而上面的gamma是老的}(2)测试过程的高斯径向基函数的修正代码voidsvm_predict_values(constsvmmodel*model,constsvmnode*x,double*dec_values){ if(model->param.svmtype二二ONE_CLASS|model->param.svmtype==EPSILONSVR|model->param.svm_type二二NU_SVR){double*svcoef二model->sv_coef[0];doublesum二0;for(inti=0;il;i++)sum+二sv_coef[i]*Kernel::k_function(x,model->SV[i],model->param);sum-二model->rho[0];*decvalues二sum;}else{//该函数里用到的model是新的model,而计算C(X)和C(Xi)时应该用原来的model!!!structsvmmodel*model_old=svm_load_model(，zold.modeT7);inti;intnr_class二model->nr_cldss;//model_old和新model的nr_class值一样intnr_class_old=model_old->nr_class;int1二model->l;intl_old=model_old->l;double*kvalue二Malloc(double,1);for(U0;i〈l;i++)//这里的1是所有的支持向量数，这里求的是总问题的值{kvalue[i]二Kernel::k_function(x,model->SV[i],model->param);//SV相当于与svmtrain中的x,也就是prob->x}//至此，原来的model->param.gamma已经用完，后面可以修改。//—>也不能改，因为constsvmmodel*modelint^start=Malloc(int,nr_class);start[0]=0;for(i=l;inSV[i-l];//这里的start表示所有支持向量的startint*start_old=Malloc(int,nr_class_old);start_old[0]=0;for(i=l;inSV[i-l];//这里的start表示所有支持向量的startintp=0;for(i=0;inSV[i];intcj=model->nSV[j];intsi_old=start_old[i];intsj_old=start_old[j];intci_old=model_old->nSV[i];intcj_old=model_old->nSV[j];intk;double*coefl=model->sv_coef[j-1];〃第i类样本的支持向量所放的开始位置，这里的j-l是逻辑列数(从0开始)double*coef2=model->sv_coef[i];〃第j类样本的支持向量所放的开始位置，这里的i也是逻辑行数(从0开始)〃先只考虑两类，从样本中选取第i类和第j类double^coefl_old=model_old->sv_coef[j-l];double*coef2_old=model_old->sv_coef[i];〃每次用多少kvalue：]则算多少,每次只针对两类求相应值，〃每次只从大问题里“捉取”相应值//先求出c(x)doublesuml_cx=0;//c(x)//intN_i_j_sv_old=ci_old+cj_old;intN_i_j_sv_old=N_yangben;(model_old->param)•gaima二N_i_j_sv_old*((model_old->param).gamma);//N_i_j_sv待定for(k=0;kSV[si_old+k],model_o1d->param);//kvalue[si+k]://第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj_old+k],model_o1d->param);//kvalue[sj+k]://第j类的0号支持向量到ci-1号支持向量//再求岀c(model->SV[i])用循环 double*sum_ci二newdouble[ci];//和kvalue[si]kvalue[si+ciT]对应double*sum_cj二newdouble[cj];//和kvalue[sj]kvalue[sj+cjT]对应for(inth=0;h〈ci;h++){sum_ci[h]二0;}for(h=0;hSV[si+h]，其“不变”for(intk=0;kSV[si+h],model_old->SV[si_old+k],model_o1d->param);//kvalue[si+k]:第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[si+h],model_old->SV[sj_old+k],model_o1d->param);}//后一部分新的for(h=0;hSV[sj+h]其“不变”for(intk=0;kSV[sj+h],model_old->SV[si_old+k],model_o1d->param);//kvalue[si+k]:第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj+h],model_old->SV[sj_old+k],model_o1d->param);}//到此已求岀Cx与Cxi;//k_(x,xi)=suml_cx*sum_ci[k]^kvalue[si+k]for(k=0;krho[p];dec_values[p]=sum;p++；}free(kvalue);free(start);}} 附录5本设计提出的方法修正高斯径向基函数关键代码说明：下面关键代码均在svm.cpp中。(1)训练过程的高斯径向基函数的修正代码doublekcrnel_rbf(inti，intj)const{/*该函数的参数i和j是提供了两个向量x[i]和x[j],而此刻训练的应当是第i_class类和第j_class类*/intsi_old=start_old_train[i_class];intsj_old=start_old_train[j_c1qss];intci_old=model_old_train->nSV[i_class];intcj_old=model_old_train->nSV[j_class];double*coefl_old=model_old_train->sv_coef[j_class-l];double*coef2_old=model_oldtrain->sv_coef[i_class];/*每次用多少kvaluct]则算多少;每次只针对两类求相应值，每次只从大问题里“捉取”相应值*/intk;intN_i_j_sv_old=N_yangben;//用来调参数tstructsvmparameterparamic1ass_jc1ass=mode1_o1d_train->perram;param_iclass_jclass-gamma=param_iclass_jclass-gamma*N_i_j_sv_old;//先求岀C(x[i])//求|wdoublealpha_suml1=0;for(k=0;kobj[p_class];doublew_mo=sqrt(2*(alpha_sumll+obj_p));doublesum_cxi=0;//c(x[i])for(k=0;kSV[si_old+k],param_iclass_jclass);//kvalue[si+k]:第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj_old+k],param_iclass_jclass);//kvalue[sj+k]:第j类的0号支持向量到ci~l号支持向量//再算出c(x[jj)doublesum_cxj=0;for(k=0;kSV[si_old+k],paramiclassjclass);//kvalue[si+k];〃第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj_old+k],param_iclass_jclass);//kvalue[sj+k]:第j类的0号支持向量到ci-1号支持向量returnsum_cxi*sum_cxj*exp(-gamma*(x_square[i]+x_square[j]-2*dot(x[i],x[j])));//这里的gamma是“新的”(在dos下输入的)，而上面的gamma是老的}(2)测试过程的高斯径向基函数的修正代码voidsvm_prcdict_valucs(constsvm_model*modcl,constsvmnode*x，double*decvalues){if(modcl->param.svmtype==ONECLASS|modcl->param.svmtype==EPSILONSVR|modcl->param.svmtype==NUSVR){double*svcocf=modcl->svcocf[0];doublesum=0;for(inti=0;il;i++)sum+=svcocf[i]*Kernel::kfunction(x,modcl->SV[i]，modcl->parani);sum-=modcl->rho[0];*decvalues=sum;}else{//该函数里用到的model是新的model,而计算C(X)和C(Xi)时应该用原来的model!!!structsvmmodel*modelold=svmloadmodel("old.model");inti;intnrclass=modcl->nrclass;//modclold牙口新model的nrclass值一样intnrclassold=modclold->nrclass;int1=modcl->l;int1old=modclold->l;double*kvaluc=Malloc(double,1);for(i=0;iSV[i],modcl->param);//SV相当于与svmtrain中的x,也就是prob->x//至此，原来的model->param.gamma已经用完，后而可以修改。//-->也不能改,因为constsvmmodel*modelint*start二Malloc(int,nr_class);start[0]=0;for(i=l;inSV[iT];//这里的start表示所有支持向量的startint*start_old=Malloc(int,nr_class_old);start_old[0]=0;for(i=l;inSV[iT];//这里的start表示所有支持向量的startintp=0;for(i=0;inSV[i];intcj=model->nSV[j];intsi_old=start_old[i];intsj_old=start_old[j];intci_old=model_old->nSV[i];intcj_old=model_old->nSV[j];intk;double*coefl=model->sv_coef[j-1];〃第i类样本的支持向量所放的开始位置，这里的j-l是逻辑列数(从0开始)double*coef2=model->sv_coef[i];〃第j类样本的支持向量所放的开始位置，这里的i也是逻辑行数(从0开始)〃先只考虑两类，从样本中选取第i类和第j类double*coefl_old=model_old->sv_coef[j-l];double*coef2_old=model_old->sv_coef[i];〃每次用多少kvalue：]则算多少,每次只针对两类求相应值，〃每次只从大问题里“捉取”相应值//先求出c(X)//求|wdoublealpha_sumll=O;for(k=0;kobj[p];doublew_mo=sqrt(2^(alpha_suml1+obj_p));doublesuml_cx=0;//c(x)//intN_i_j_sv_old=ci_old+cj_old;intN_i_j_sv_old=N_yangben;(model_old->param).gamma=N_i_j_sv_old*((model_old->param).gamma);〃N_i_j_sv待定for(k=0;kSV[si_old+k],model_old->param);//kvalue[si+k]://第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj_old+k],model_old->param);//kvalue[sj+k]://第j类的0号支持向量到ci-1号支持向量//再求出c(model->SV[i])用循环double*sum_ci二newdouble[ci];//和kvalue[si]kvalue[si+ciT]对应double*sum_cj二newdouble[cj];//和kvalue[sj]kvalue[sj+cjT]对应for(inth=0;hSV[si+h]，其“不变”for(intk=0;kSV[si+h],model_old->SV[si_old+k],model_o1d->param);//kvalue[si+k]:第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[si+h],model_old->SV[sj_old+k],model_o1d->param);}//后一部分新的for(h=0;hSV[sj+h]其“不变”for(intk=0;kSV[sj+h],model_old->SV[si_old+k],model_o1d->param);//kvalue[si+k]:第i类的0号支持向量到ci-1号支持向量for(k=0;kSV[sj+h],model_old->SV[sj_old+k],model_o1d->param);}//到此已求岀Cx与Cxi;//k_(x,xi)二suml_cx*sum_ci[k]^kvalue[si+k]for(k=0;krho[p];dec_values[p]=sum;p++；}free(kvalue);free(start);}}