《毕业设计论文非线性分类问题的研究.doc》由会员分享，可在线阅读，更多相关《毕业设计论文非线性分类问题的研究.doc（52页珍藏版）》请在三一办公上搜索。
1、摘 要本文论述了支持向量机的基本原理和思想，侧重分析了支持向量机的两种多类分类训练算法（OAA算法、OAO算法）和四种核函数（即线性内核、径向基函数内核、多项式内核，S型内核）。本论文实现了三种算法（还包括BSVM算法），并使用这三种训练算法和这四种核函数实现了非线性模式分析模型。本论文利用matlab程序语言，实现了一个图形界面。该界面能使用户灵活的选择三种训练算法的一种和四个核函数的一个对数据集进行分类，并能手动创建数据和装载已有数据，还能清除已创建或装载的数据。对于分类结果，图形界面还能显示出分类所用的训练算法，核函数，算法训练时间，支持向量个数以及分类错误率。根据算法训练时间，支持向量
2、个数和分类错误率的统计，本文还做成三个表格，简单分析了三种算法的优劣。本论文的创新点在于：原有算法只能使用一种核函数和一种C调整系数来修正算法的分类效果，本论文通过收集核函数的资料，扩展到能使用四种核函数，并修改少量代码使算法能使用两种C调整系数。关键词：支持向量机，多类分类，核函数AbstractThis text has expounded the basic principle and thought of Support Vector Machine, and has laid particular emphasi on analyzing two kinds of Multi-cla
3、ss classification training algorithms (OAA algorithm, OAO algorithm) and four kernel functions(Linear, Polynomial, RBF, sigmoid) of Support Vector Machine. This thesis implement the three training algorithms（include , BSVM algorithm）, and then, implement the non_linear pattern analysis model. This t
4、hesis implement a graphical interfaces using matlab program language. It is convenient to choose one of the three training algorithms and one of the three kernel functions to classify the data by the graphical interfaces. And the graphical interfaces implement the function of creating data sets by u
5、ser and loading the existent data sets. Moreover, the graphical interfaces can clear the data sets which is created and loaded by user. For the result of classification, the graphical interfaces can display the sort of training algorithms and kernel functions, the time algorithm training, the number
6、 of support vector and the error ratio of classification. This text have made three table by the stat of the time algorithm training, the number of support vector and the error ratio of classification, and analyse simply the quality of the three training algorithms. This thesis have some innovation.
7、 The former algorithm can use a sort of kernel function and one kind of C parameter. And now, the algorithm can use four kernel functions by collecting information about kernel function and can use two C parameters by modifying a few codes. Key words: Support Vector Machine, Multi-class classificati
8、on, kernel function目 录摘 要IAbstractI目 录I第一章 绪 论11.1研究背景11.2国内外研究状况及成果41.3研究目的51.4开发工具简介5第二章 支持向量机82.1支持向量机的思想82.2支持向量机的方法82.3支持向量机现有的几种应用132.4支持向量机的特点132.5支持向量机的核函数14第三章 分类及多类分类问题163.1分类问题和分类学习机163.2多类分类问题的描叙183.3多类分类具体算法193.3.1OAA算法193.3.2OAO算法21第四章 非线性模式分析模型的总体设计234.1功能需求分析234.2总体设计234.3软件具体设计264.3
9、.1.软件功能模块的划分264.3.2.系统的构架274.3.3.模型的总流程图28第五章 非线性模式分析模型的实现295.1模型功能描述295.2系统关键代码305.3系统运行结果33第六章 非线性分类模型分析386.1分类图形结果386.2分类结果分析44结 论47致 谢48参考文献49附录 设计系统部分源代码52II正文内容：除了一、二、三、四级标题外，正文文本为宋体小四号字，20磅行距。中文文本中的括号、标点符号为中文半角状态下的括号、标点符号，英文的括号、标点符号为英文半角状态下的括号、标点符号。图、表的题头为黑体五号字、其中的文本为宋体五号字，图、表所在段落为单倍行距。正文页码：阿
10、拉伯数字，宋体小五号字，页面底端居中（默认格式）。ContentsABSTRACT. ISECTION. IINTRODUCTION. ISECTION I INTRODUCTION. 1Chapter Research Project. 11.2 The status and results of four domestic and foreign research. 41.3 The purpose of the research. 51.4 Introduction 5 Development Tools. 5Chapter I I Support Vector Machine. 82.
11、1 Support Vector Machines thought. 82.2 The support vector machine method. 82.3 Support vector machine several existing applications. 132.4 Support vector machine features. 132.5 Support Vector Machine Kernel. 14Chapter III classification and multi-class classification. 163.1 Classification and clas
12、sification learning machine. 163.2 classification problems depicts. 183.3 specific algorithm for classification. 193.3.1 OAA algorithm. 193.3.2 OAO algorithm. 21Chapter IV Nonlinear model of Chapter of the model design. 234.1 Functional Requirements Analysis. 234.2 Design. 234.3 26 specific design s
13、oftware. 264.3.1. Software function modules. 264.3.2. System architecture. 274.3.3. Model of the total flow chart. 28Chapter V Implementation of nonlinear model model. 295.1 model Functional Description. 295.2 key code system. 315.3 running results. 33Chapter VI Nonlinear classification model.396.1
14、Classification results graphics. 386.2 Classification results. 44Conclusions. 55Acknowledgements. 56References. 57Appendix Design System part of the source code. 522第一章 绪 论1.1 研究背景基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据（样本）出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。迄今为止，关于机器学习还没有一种被共同接受的理论框架，关于其实现方法大致可以分为三种：第一种是经典的（参数）统
15、计估计方法。包括模式识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性，首先，它需要已知样本分布形式，这需要花费很大代价，还有，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。第二种方法是经验非线性方法，如人工神经网络（ANN）。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。与传统
16、统计学相比，统计学习理论（Statistical Learning Theory 或SLT）是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。V. Vapnik 等人从六、七十年代开始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。统计学习理论的一个核心概念就是VC 维(VC Dimension)概念，它是描述函数集或学习机器的复杂性或者说是学习能力(Ca
17、pacity of the machine)的一个重要指标，在此概念基础上发展出了一系列关于统计学习的一致性(Consistency) 、收敛速度、推广性能(Generalization Performance)等的重要结论。统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题（比如神经网络结构选择问题、局部极小点问题等）；同时，这一理论基础上发展了一种新的通用学习方法支持向量机（Support Vector Machine 或SVM），已初步表现出很多优于已有方的性能。一些学者认为，SLT
18、和SVM正在成为继神经网络研究之后新的研究热点，并将推动机器学习理论和技术有重大的发展。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Generalizatin Ability)。支持向量机方法的几个主要优点有：1. 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值；2. 算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点，解决了在神经网
19、络方法中无法避免的局部极值问题；3. 算法将实际问题通过非线性变换转换到高维的特征空间(Feature Space)，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关。目前，国际上对这一理论的讨论和进一步研究逐渐广泛，而我国也在此领域开展了研究，但我们需要及时学习掌握有关理论，开展有效的研究工作，使我们在这一有着重要意义的领域中能够尽快赶上国际先进水平。SLT 理论和SVM 方法已经逐渐成熟，但还是有很多方面尚不完善，比如：许多理论目前还只有理论上的意义，尚不能在实际算法中实现；而有关SVM
20、算法某些理论解释也并非完美（J.C.Burges就曾提到结构风险最小原理并不能严格证明SVM 为什么有好的推广能力）；此外，对于一个实际的学习机器的VC 维的分析尚没有通用的方法；SVM方法中如何根据具体问题选择适当的内积函数也没有理论依据。因此，在这方面我们可做的事情是很多的。在SVM 方法中，只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类器、径向基函数(Radial Basic Function 或RBF)方法、多层感知器网络等许多现有学习算法。统计学习理论从七十年代末诞生，到九十年代之前都处在初级研究和理论准备阶段，近几年才逐渐得到重视，其本身也趋向完善，并产生了支持向量机这一
21、将这种理论付诸实现的有效的机器学习方法。目前，SVM算法在模式识别、回归估计、概率密度函数估计等方面都有应用。例如，在模式识别方面，对于手写数字识别、语音识别、人脸图像识别、文章分类等问题，SVM 算法在精度上已经超过传统的学习算法或与之不相上下。1.2 国内外研究状况及成果研究动态：近年来支持向量机已经成为机器学习领域的一个研究热点，其应用领域从最初的二类分类问题，扩展到复杂系统的建摸、优化控制等问题。支持向量机不仅在传统的模式识别和工业过程领域中得到应用，而且在新兴的生物信息、金融证卷、药物分析、辅助医疗等领域受到研究者的青眯。支持向量的理论框架比较成熟，现在的主要研究有两一个方面，一个是
22、完善部分理论的研究，另一个就是将其推广到实际问题的应用中去。Poser，Guv0n等人利用美国邮政标准手写数字库进行的对比实验，使用多项式核函数对1616的手写体阿拉伯数字进行了识别，训练集共300个样本，测试集有2000个样本。实验结果表明采用SVM 方法比采用其他神经网络(具有五层神经网络复杂结构)算法效果要好。针对手写汉字、针对印刷汉字分别利用SVM技术进行了字体识别，识别率非常高人脸识别是近年来研究颇为热门的一个方向，SVM 为这一领域的研究提供了手段。Guodong Gu0L 等人采用两：人脸数据库，一个是含有400幅图象，另一个含有1079幅图象，并将SVM 方法与其他算法进行丫比
23、较，证明SVM 方法的错识率最低。此外SVM还在其他数据分类、线性回归等方面得到应用。美国航空航天局JPL实验室的科学家在Science（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，该领域在今后的若干年内将取得稳定而快速的发展。如今SVM的应用领域十分广泛，成果也很多。在网络安全，天气预报，生物信息学等方面都有很多成果产品的出现。1.3 研究目的研究的目的在于：训练和提高自己综合运用所学专业知识分析、解决实际问题的能力； 掌握文献检索、资料查询的基本方法以及获取新知识的能力；计算机软件、硬件或应用系统设计和开发的基本能力；书面和口头表达的能力；协作配合工作
24、的能力。学习有关支持向量机的理论，利用和改进已有的非线性多类分类的有关算法和核函数，建立一个非线性模式分析模型。该模型能让用户创建多类数据，用多种算法核核函数的组合来对创建数据分类，并计算其支持向量，训练时间，分类错误率，以比较算法之间的优劣。1.4 开发工具简介本论文使用matlab 7.0开发环境编程，MATLAB的核心是一个基于矩阵运算的快速解释程序，它进行数值计算的基本处理单位是复数数组（或称阵列），并且数组维数是自动按照规则确定的。这一方面使MATLAB程序可以被高度“向量化”。它交互式地接收用户输入的各项命令，输出计算结果。MATLAB还提供了一个开放式的集成环境，用户可以运行系统
25、提供的大量命令，包括数值计算，图形绘制和代码编制等。MATLAB语言有如下一些优点：编程效率高：MATLAB是一种面向科学与工程计算的高级语言，允许用数学形式的语言来编写程序，这样就更接近我们书写计算公式的思维方式。MATLAB语言是一种解释执行的语言，与其他语言相比，它把编辑，编译，连接和执行融为一体，从而加快了开发者编写，修改和调试程序的速度。高效方便的矩阵和数组运算：在决策树分类过程中，输入的数据集，运算的变量以及很多参数都是以数组，向量形式出现的，运算这些数据复杂，易出错而且费时，所以方便高效的数组向量运算就显得尤为重要，而MATLAB恰好具有这个优秀的功能。并且MATLAB语言还像其
26、他语言一样规定了矩阵的算术运算符，关系运算符，逻辑运算符，条件运算符及赋值运算符。这给编写程序带来很大方便与保证。而决策树的树状结构和分类算法包含了大量的数学模型和复杂的运算公式，所以用MATLAB语言进行代码编写比较简单，编程效率比较高，这是选择它作为本论文编程工具的原因之一。方便的绘图功能：本论文借助于MATLAB的绘图功能，能较为方便的建立分类过程中的演示图形。MATLA有一系列绘图函数命令，功能强大，使用方便。第二章 支持向量机122.1 支持向量机的思想它是针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本映射到高维属性空间使其线性可
27、分,从而使得在高维属性空间采用线性算法对样本的非线性特性进行分析成为可能。它通过使用结构化风险最小化的理论在属性空间构建最优化分割超平面,使得学习器得到全局最优化,并在整个样本空间的期望风险以某个概率满足一定上界。因此,无论是在理论基础还是应用前景上,SVM在很多方面都具有其它学习方法难于比拟的优越性。但是作为一种新兴的技术,SVM目前还存在着一些局限性,例如随着训练样本数量的增多,SVM的训练速度将会明显变慢,缺乏对增量式学习的支持,容噪性不高,难于整合先验知识等。2.2 支持向量机的方法统计学习理论是在传统统计学基础上发展起来的一种机器学习方法。SVM 的基本思想可由图1.1 说明,在二维
28、两类线性可分情况下,有很多可能的线性分类器可以把这组数据分割开,但是只有一个使两类的分类间隔margin 最大,即图中的H ,这个线性分类器就是最优分类超平面,与其它分类器相比,具有更好的泛化性 。图1.1 最优分类超平面若样本集Q=（xi，yi）|i=1,LRd*-1,+1是线性可分的。则存在分类超平面wTx+b=0,xRd对样本集Q中任一（xi，yi）都满足： 在空间Rd中样本x=（x1，, xd）r到分类超平面的距离d=|wT*x+b|/|w|，其中|w|= .当存在x 使得wTxi+b=1, 则图1中超平面的分类间隔margin = 2/ w 。使分类间隔margin 最大的超平面即为
29、最优分类超平面。寻找最优分类超平面的问题将转化为求如下一个二次规划问题:min( w) =1/2w （2.1） 满足约束条件：yi ( wTxi + b) 1 , i = 1 ,2 , , L （2.2） 采用Lagrange 乘子转换为一个对偶问题,形式如下: （2.3）满足约束条件:0ai，i=1,L （2.4）其中ai 为每一个样本对应的Lagrange 乘子, 根据Kuhn2Tucker 条件,这个优化的解必须满足:ai (yi wTxi +b-1)=0,i=1,L （2.5）因此多数样本对应 ai将为0 ,少部分不为0 的ai 对应的样本就是支持向量。最后得到分类判别函数为:b*是分
30、类的域值,可以通过两类中任意一对支持向量取中值求得。根据上述易知, 对于空间Rd 中任意样本x =( x1,xd)T ,当|f(x)|0时为线性不可分情况，当C=0时为线性可分情况。引入拉格朗日乘子,，根据目标函数及约束条件建立Lagrangian函数：把上面几个公式代入Lagrangian函数得到其对偶问题，归结为一个二维函数极值问题：满足约束条件：caio.这里a=(a1，ai)是拉格朗日乘子，w*为最优超平面的法向量，(xi；xj)为两向量的内积。那些ai=0的样本对分类问题不起什么作用，只有ai 0的样本对w*起作用，从而决定分类结果。这样的样本定义为支持向量。而最终的分类函数为：根据
31、d(x)的符号来确定X的归属。 (2)非线性情况：对非线性的情况，可以把样本x通过非线性映射映射到高维特征空间H，将其映射为线性情况，并在H中使用线性分类器。这样，在高维空间中实际上只需进行内积运算，而这种内积运算是可以用原空间的函数来实现的，我们甚至没有必要知道变换的形式。根据泛函的有关理论，只要一种核函数K(xj，x)满足Mercer条件，它就对应某一空间中的内积。此时分类函数变为：2.3 支持向量机现有的几种应用 在模式识别领域，利用支持向量机对手写英文或者是汉字进行识别，取得了较好的精度，此方法的汉字识别率较距离分类器有很大的提高。利用支持向量机对车牌中的数字英文字符进行识别，克服了一
32、般的算法识别数字位图时缺乏对相邻空间像素相关性考虑的下足在满足实时性的条件下获得高识别率。支持向量机通过对样本点集的适当变换，提出一种将回归问题转化为二分类问题的新思想，一方面这与前馈神经网络的理论体系相一致，另一方面也使得回归问题中支持向量的几何意义更明显，为分类问题的研究成果应用于回归问题奠定了理论基础。此外支持向量机在数据挖掘、非线性系统控制和非线性系统辨识中均有很好的应用。2.4 支持向量机的特点 从统计学习理论和支持向量机算法原理不难看出，支持向量机具有以下特点：（1） 支持向量算法是基于统计学习理论的结构风险最小化原则的，与传统的算法不同，它不仅优化经验风险，而且通过最大化分界面来
33、控制模型的复杂度，从而有效地避免了过学习现象，为模型选择问题提供了很好的思路。（2） 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值。（3） 训练算法最终将转化成为一个二次型寻优间题，从理论上说，得到的将是全局最优解，解决了在神经网络方法中存在的局部极值问题。（4） 算法将输入空间中的训练样本通过非线性变换转换到高维的特征空间中，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，并能保证机器有较好的泛化能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关。2.5 支持向量机的核函数支持向量机的一个引人注目的特点是用满足Merce
34、r条件的核函数代替向量间的内积运算来实现非线性变换，而不需要非线性的具体形式。研究人员根据这一思想改造经典的线性算法并构造出对应的基于核函数的非线性形式。支持向量机模型最重要的一个参数就是核函数。选择什么样的核函数，就意味着将训练样本映射到什么样的空间去进行线性划分。支持向量机算法的技巧在于不直接计算复杂的非线性变换,而是计算非线性变换的点积，即核函数，从而大大简化了计算。通过把核函数引入到一些学习算法，可以方便地把线性算法转换为非线性算法，我们将其与支持向量机一起称为基于核函数的方法。在高维特征空间实际上只需要进行点积运算，可以用原空间中的函数实现的，甚至没有必要知道变换的形式。根据泛函的有
35、关理论，只要一种核函数满足Mercer条件，它就对应某一变换空间中的点积。因此，在最优分类面中采用适当的点积函数就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加。很多学者证明了核函数存在性定理，并提出了寻找核函数的算法。核函数存在性定理表明：给定一个训练样本集，就一定存在一个相应的函数，训练样本通过该函数映射到高维特征空间的相是线性可分的。但是核函数的寻找在目前为止还没有具体的理论，选择核函数还具有极大的不确定性。SVM 由训练样本集和核函数完全描述，因此采用不同的核函数就可以构造实现输入空间中不同类型的非线性决策面的学习机，导致不同的支持向量算法。本论文研究的四种核函数如下：线性
36、内核 多项式内核 径向基函数内核 Sigmoid内核 第三章 分类及多类分类问题33.1 分类问题和分类学习机分类问题也称为模式识别问题，在概率统计中则称为辨别分析问题。根据给定的训练集： T=（x1 , y1)(xi, yi)(x * y)I,其中xax=Rn，yay=1,-1,a=1,.i,寻找x=Rn上的一个实值函数g(x)，以便用决策函数 f(x)=sgn(g(x)推断任一模式x相对应的y值。由此可见，求解分类问题，实质上就是找到一个把Rn上的点分成两部分的规则。确切的说，上述分类问题是分成两类的问题。与分成两类的分类问题类似，还有分成多类的分类问题。他们的不同之处仅在于前者的输出只取
37、两个值，后者则可取多个值。参照机器学习领域中的术语，我们把解决上述分类问题的方法称为分类学习机。当g(x)为线性函数g(x)=(wx)+b,有决策函数确定分类准则时，称为线性分类学习机；当g(x)为非线性函数时，称为非线性分类学习机。不难想象，分类问题大体有三种类型。对于不同类型的问题，可能需要采用不同的分类学习机。我们以输入2维向量的分类问题为例，从直观上予以说名。首先，对于图3.1所示的问题，很容易用一条直线把训练集正确的分开（即两类点分别在直线的两侧，没有错分点），这类问题称为线形可分问题。这时显然可以使用简单的线形学习机。其次对于图3.2所示的问题，用一条直线也能大体上把训练集正确的分开，这类问题称为近似线性可分问题，这时仍然可以考虑使用线性分类学习机。最后，对于图3.3所示的问题，显然这时用直线分划会产生很大的误差，这类问题称为（实质）线性不可分问题。这时就必须采用非线性分类学习机了。图3.1线性分类图3.2 近似线性分类图3.3 线性不可分分类3.2 多类分类问题的描叙 多类分类问题可以形式化地表述为：给定属于k类的m个训练样本(x1，y1)，、。，(xm，y
