【毕业学位论文】（Word原稿）基于支持向量机的多分类算法改进与应用-软件工程

硕士学位论文 （专业学位） 基于支持向量机的多分类算法 改进 与应用 姓 名： 学 号： 所在院系：软件学院 职业类型： 工程硕士 专业领域：软件工程 指导教师： 副 指导教师 ： 二一 二 年 三 月 A in n 2012 基于支持向量机的多分类算法改进与应用 同济大学 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动 。 学位论 文作者签名： 2012 年 3 月 1 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 2012 年 3 月 1 日同济大学 硕士学位论文 摘要 I 摘要 支持向量机是由 验室的 人提出的一种针对分类和回归问题的新型机器学习方法，是借助于最优化方法解决机器学习问题的新工具支持向量机方法 是 基于统计学习理论与结构风险最小化原理，具有良好的推广性和 比 较高的准确率它集成了最优分类超平面、核技巧、凸二次规划等多项技术，能有效地解决“过学习”、“维数灾难”和局部极小点等问题由于出色的学习性能，支持向量机已经成为当前机器学习界的一个研究热点，并在很多领域得到了广泛的应用，包括 模式识别、回归估计等方面由于支持向量机方法最初是针对二类别的分类问题提出的，如何将二类别分类方法扩展到多类别分类是支持向量机研究的一个重要内容 本文主要做了以下几个方面的工作 1介绍了机器学习、统计学习理论以及支持向量机的发展和研究现状讨论了支持向量机的理论和算法，包括核函数理论、参数选择等热点问题 2总结了目前常用的基于支持向量机的多分类方法，包括一对多方法、一对一方法、决策二叉树方法对比讨论了各种方法的优缺点本文针对构建分类超平面的支持向量的空间分布特点结合模糊隶属度和“一对一”乡分类 方法所存在的弊端，提出了一种改进的多分类方法，并通过仿真试验验证了改进方法的有效性 关键词： 机器学习；支持向量机；多分类 I is a It is a to of on on by of of as in is in as so is to it is a In is as 1. of of of 2. of at of a is to of of is by of 济大学 硕士学位论文 目录 I 目录 第 1 章 绪论 . 1 题研究背景 . 1 持向量机的发展历史与研究现状 . 2 持向量机的发展历史 . 2 持向量机的研究现状 . 2 持向量机的应用 . 3 文的 研究内容和组织结构 . 4 文研究内容 . 4 文的组织结构 . 4 第 2 章 机器学习与统计学习理论概述 . 5 器学习的基本问题 . 5 器学习的发展历史 . 5 器学习问题的表述 . 6 计学习理论的基本内容 . 7 习一致性条件 . 8 C 维 . 8 广性的界理论 . 8 构风险最小化原则 . 9 第 3 章 支持向量机基本方法 . 11 持向量机基本方法 . 11 性支持向量机 . 11 线性支持向量机与核函数 . 15 支持向量 . 17 回归支持向量机 . 17 数选择 . 20 数选择的意义 . 20 数的作用与影响 . 20 于网格搜索的参数选择方法 . 21 支持向量机的训练 算法 . 22 算法 . 23 解算法 . 24 贯最小优化算法 (. 25 第 4 章 基于支持向量机的多分类方法改进 . 26 同济大学 硕士学位论文 目录 常见的多类分类算法 . 26 一对多分类器 . 27 一对一分类器 . 27 叉树分类器 . 28 一种改进的一对一多类分类器 . 29 糊集的基本概念 . 29 种改进的一对一多类分类器 . 30 第五章 支持向量机的多分类算法应用 . 37 用背景简介 . 37 据的获取 . 37 验结果及分析 . 39 第六章 总结与展望 . 41 参考文献 . 42 致 谢 . 45 个人简历、在读期间发表的学术论文与研究成 果 . 46 第 1 章 绪论 1 第 1章 绪论 课题 研究背景 20 世纪 90 年代以来，计算机技术和信息技术的迅猛发展 同时 宣告了信息时代的到来，这个时代的重要特征就是 ： 人们有了更多的机会和手段 能 接触到大量数据海量数据时刻充斥着我们的生活，它们将在生产和生活中发挥巨大作用因此人们投入了大量资源去收集、存储和处理数据而 在 实际问题中由于数据量太大，很难对 数据 进行高效管理，或者由于数据结构太复杂，很难对其进行有效 的 分析，所以这些海量数据只有一小部分在发挥作用，大量潜在的有价 值 的 信息仍没有被挖掘出来，这就出现了 “ 数据爆炸，信息匾乏 ” 等 现象 对大型、复杂、信息丰富的数据集的理解 ， 实际上是政府、企业和科研领域的共同需要在政府机构中，很多政策、法律、法规的制订都要有数据信息作为依据；在商务领域 、 公司和顾客的数据都被认为是一种战略 性 资产；在科研领域，研究者们从数据中寻找规律 的同时 又在用数据检验规律这就要求对 我们对 数据有深刻 的理解，传统的数据库技术和数据分析方法已经 难以满足 人们 的要求如何从海量数据中快速挖掘出有用知识，己成为信息时代一个十分紧迫而富有挑战的研究课题数据挖掘技术 (1就是在这样的背景下应运而生的 基于数据的机器学习 (数据挖掘技术中的重要内容，它研究从观测数据出发寻找规律，并利用这些规律对未来数据或无法观测的数据进行预测现有机器学习方法共同的重要理论基础之一是统计学传统统计学研究的是样本数目趋于无穷大时的渐近理论，即当样本趋于无穷多时的统计性质但在实际问题中，样本数目往往是有限的，通常的方法仍以样本无穷多为假设进行算法推导和建模，因此一些理论上很优秀的学习方法在实际中的表现可能难以令人满 意比如，在普通的神经网络学习中，当样本数有限时，本来很好的学习机器却表现出很差的推广能力，这种现象被称为过学习现象 为了解决这类问题，许多学者进行了坚持不懈的研究工作二十世纪六七十年代，人开始建立一种研究有限样本情形下统计规律及学习方法性质的理论，即统计学习理论 (2它为有限样本的机器学习问题建立了一个良好的理论框架，较好地解决了小样本、非线性、高维数和局部极小点等实际问题随着其理论的不断发展和成熟，也由于神经网络等 学习有法在理论上缺乏实质性进展，统同济大学 硕士学位论文 基于支持向量机的多分类算法改进与应用 2 计学习理论开始受到越来越广泛的重视直到 1995 年， 他的合作者们明确提出一种新的通用学习方法一支持向量机 ( 4后，该理论才受到广泛的重视并应用到不同的领域它基于 理论和结构风险最小化原理(练学习机器，在很大程度上克服了传统机器学习中的维数灾难以及局部极小等问题 2同时，根据有限的样本信息在模型的复杂性 (即对特定训练样本的学习精度 ， 学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力 ( 支持向量机的 发展历史与研究现状 持向量机的发展历史 早在上世纪六十年代， 开始了统计学习理论的研究，于上世纪六十至七十年代建立了统计学习理论的基本理论框架 1971 年， 1提出 理论 1982 年， 出结构风险最小化原理 1992 年， 1提出最优边界分类器 1995 年， 1等人提出支持向量机概念 1997 年， 绍了基于支持向量机方法的回归算法 持向量机的研究现状 由于 实的理论基础及其在很多领域表现出的良好性能，国内外正广泛开展对 研究目前对 研究主要包括： 支持向量机的变形： 为了使支持向量机在解决某些实际问题时具有更优良的特性，学者们对二次规划的目标函数进行适当修改，从而构造出一些具有新的性质的支持向量机，如 :支持向量机 (19，最小二乘支持向量机 (20，加权文持向量机 (21和模糊支持向量机 (22,23 训练算法的改进： 针对 练速度慢和时间空间复杂度大的问题，目前常见的支持向量机训练算法有： 人在 1992 年提出的选块算法 (5= 1997 年提出的分解算法 16,17； 1998 年提出的序贯最小优化 (法 18； 第 1 章 绪论 3 利用 决多类分类问题： 由于 针对两分类问题提出的，因此存在一个如何将其推广到多分类上的问题目前对于多类问题， 算法主要有：“一对多”多分类方法 24 25，“一对一”多分类方法 25二叉树多分类方法 27,28和一次性求解方法 29 持向量机的应用 支持向量机出色的学习性能，使该技术已经成为机器学习界的研究热点，并在很多领域中得到了成功的应 用国内外学者的积极研究极大地推进了支持向量机在各领域应用的快速发展如：手写汉字识别 6， 7、人脍识别和人脸检测 8网络入侵检测 9、文本分类 10、语音识别 11、信号处理 12、图像分类与识别 13、三维地形处理 14、医疗诊断 15等众多研究领域 同济大学 硕士学位 论文 基于支持向量机的多分类算法改进与应用 4 论文的研究内容 和组织结构 文研究内容 法拥有完备的数学理论基础，是一种在高维空间 用于 表示复杂的函数依赖关系的高效通用手段和其他同类方法相比， 有全局优化、适应性强、理论完备、泛化性能好等优点自 20 世纪 90 年代初对 研究取得突破性进展后， 们 研究的热点但是 持向量模式分类方法最初是针对二类别的分类而提出的，如何将 效地推广到多类别分类 ， 仍然是当前支持向量机研究的一个重要 课题 本文将针对此问题，对支持向量机多类分类方法进行探讨，其中包括： 1讨论了现有的支持向量机多分类方法 2针对支持向量机方法构建分类超平面时所用的支持向量的空间分布特点结合模糊隶属度和“一对一”方法的不足，提出了一种改进的多分类方法 3用常用的训练数据集对本文提出的改进的多分类方法进行了测试， 并与其他方法的测试结果进行了对比，最后对结果进行了分析试验表明：本文提出的改进的多分类方法能够明显地提高支持向量机的多分类性能 文的组织结构 第一章绪论主要介绍了机器学习的发展历程、基本问题 及 主要理论成果阐述了基于统计学习理论的支持向量机的产生、主要研究内容和国内外研究现状 第二章机器学习与统计学习理论概述对支持向量机的应用背景 、机器学习 及它的理论基础统计学习理论进行了简要介绍 第三章支持向量机 基本方法 详细地介绍了支持向量机的理论，并对支持向量机算法进行了详细的推导对核函数理论 、参数选择以及支持向量机的训练算法等热点问题进行了讨论 第四章基于支持向量机的多分类方法 改进 对几种常用的支持向量机多分类方法进行了分析与总结，讨论了各种方法的优缺点针对构建分类超平面的支持向量的空间分布特点结合模糊隶属度和“一对一”多分类方法所存在的弊端，提出了一种改进的多分类方法，并通过仿真试验验证了改进方法的有效性 第五章支持向量机的多分类算法应用 对于孤立性肺结节诊断，对比原有诊断方法，采用改进的多分类方法进行分析诊断，能极大的提高工作效率 第 六 章为结论与展望首先对整个论文的研究工作进行系 统总结，对将来的研究方向和内容进行展望第 2 章 机器学习与统计学习理论概述 5 第 2章 机器学习与统计学习理论概述 20 世纪 90 年代中期， 人在统计学习理论、 理论、结构风险最小化理论、核函数理论的基础上研究提出来的一种最新的机器学习算法，它在很多领域都表现出优于现有学习算法的性能从分类的角度来讲， 是在 性感知机 30的基础上，通过引入结构风险最小化原理、核函数理论、最优化理论演变而成的 本章简要地介绍了机器学习和统计学习理论 器学习的基本问题 器学习的发展历史 机器学习问题的研究历史可以分为四个阶段 2 第一阶段：第一个学习机器的创立 感知器 (20 世纪 60 年代 ) F 出了第一个学习机器的模型，称之为感知器 30这标志着人们对学习过程进行数学研究的真正开始这个阶段的研究工作导致了模式识别这个新学科的诞生，同时还形成了机器学习的一种重要方法判别函数法 第二阶段：学习理论基础的创立 (20 世纪 60 年代 70 年代 )在这段时间内理论分析学派完 成了模式识别学习理论和经验风 险最小化归纳 和 推理的分析 第三阶段：神经网 络的创立 (20 世纪 80 年代 ) 1986 年，研究者提出了同时构造感知器 神经元 向量系数的方法，即后向传 播的方法这一方法的思想是很简单的，在修改的模型中，新的神经元 合成是一个连续函数，利用计算神经元的系统梯度，人们可以应用 于 任何基于梯度的方法来构造对期望函数的逼近后向传播技术的提出是感知器的一次飞跃，这时的感知器也被 人们 称为神经网络神经网络在很多实际应用中也取得了 非常 好的效果然而，所得到的理论成果并没有对一般的学习理论带来很 大的贡献在神经网络学习中，并没有发现新的有意义的现象 第四阶段：统计学习理论 (20 世纪 90 年代 )由于神经网络等现有的机器学习方法的共同理论基础之一是传统统计学，传统统计学 所 研究的是样本数目趋于无限大时的渐进理论但在实际问题中，样本数往往是有限的，与传统 的 统计学相比，统计学习理论 ( 一种专门研究小样本情第 2 章 机器学习与统计学习理论概述 6 况下机器学习规律的理论该理论针对小样本统计 的 问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优绪果 V 人从六、七十年代开始致力于统计 学习理论 ( 研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视 器学习问题的表述 机器学习的目的是根据给定的训练样本，估计系统输入与输出之间 的 依赖关系，使 它 能够尽可能准确地预测 出 系统的未来输出系统是研究的对象，它在给定的输入 X 下得到输出 Y在训练过程中，输入与输出组成训练样本（ X， Y），提供给学习机器在测试过程中，训练后的学习机器对于输入 X 给出预测输出 Y。 假定对于 我们 研究的系统，已知在其输出 Y 可与输入 X 之间具有某种未知的依赖关系，即存在一个未知的联合分布 F(X， Y)对该系统的输入输出进行观测，得到如下独立同分布的观测样本 (， (， (其中 m 表示训练样本数， 示 n 维输入的模式向量， 示系统输出对于两类的模式识别问题， 1， 示该模式向量 对应的类别而在回归估计中， R 表示对应于该向量的实际值 假定学习机器具有广义参数 u（ u A，代表所有参数的集合），则对于输入X，学习机器 的预测输出 Y 可以表示为 Y= f(X， u)，则该学习机器的预测输出的期望风险可以表示为， R(u)= ( ( ) ) ( )L Y f X u d F X Y ， ， ， (同济大学 硕士学位论文 基于支持向量机的多分类算法改进与应用 7 其中 f(X， u)称为预测函数集， L(Y， f(X， u)表示在输入 X 下，用学习机器的预测输出 Y 对系统的实际输出可进行估计而造成的损失因此，机器学习问题也可以表示为，从一组独立 的 同分 式 的观测样本出发，通过最小化风险泛函 R(U)，确定学习机器的广义参数 u 的过程 学习问题 的形式化表述涉及面很广，它包括了很多特殊的问题最基本的机器学习问题有三类：模式识别（分类）、函数逼近（回归估计）和概率密度估 计 1模式识别问题 模式识别即分类问题，系统的输出为类别标号在两类情况下，令训练样本中输出 Y 只取两种值 Y=+1， 并令 f(X， u)， u A 为指示函数集，考虑损失函数：当 Y=f(X， u)时， L(Y， f(X， u)=1； 当 Y f(X， u)时， L(Y， f(X， u)=上述损失函数，式 (泛函确定了训练器和指示函数 f(X， u)所给出的值不同的概率通常把指 示函数给出的值与训练器输出不同的情况叫做分类误差因此，对模式识别问题来说，学习问题就是在概率测度 F(X， u)未知，但训练样本集已知的情况下，寻找使分类误差的概率最小的函数 2回归函数估计问题 回归函数估计问题即函数逼近 的 问题，训练器的输出 Y 为实数值，并令 f(X，u)， u A 为实函数集合回归函数就是在损失函数 L(Y， f(X， u)=(Y- f(X， u)2下使风险泛函最小的函数这样，回归估计的问题就是在 概 率 检 测度 F(X， u)未知，但训练样本集已知 的情况下，寻找使得风险泛函最小 密度 的 函数 3概率密 度估计问题 概率密度估计问题 ， 就是从密度函数集 p(X， u)， u A 中估计密度函数的问题考虑损失函数 L(Y， f(X， u)=， u)，待求的密度函数就是在损失函数下使风险泛函最小化因此从训练样 本集估计密度函数的问题就是，在相应的概率测度 F(X)未知，但给出了独立同分布数据的情况下使风险泛函最小化 计学习理论的基本内容 统计学习理论针对小样本统计问题 ， 建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑对渐近性能的要求，而且追求在现有 的 有限信息的条件下得到最优结果统计学习理论主要内容包 括 ： 经验风险最小化准则下统计学习一致性 ( 条件、在这些条件下关于统计学习方法推广性的界的结论、在这些界的基础上建立的小样本归纳推理准则以及实现新的准则的实际方法（算法） 第 2 章 机器学习与统计学习理论概述 8 学习一致性条件 所谓学习一致性是指 ： 当训练样本数趋于无穷大时，经验风险的最优值能收敛到真实风险的最优值对于有界的损失函数，学习过程一致性充分必要条件是经验风险在以下意义上一致收敛于真实风险，经验风险和期望风险都是预测函数的函数，通过求使经验风险最小化的函数来逼近能够使期望风险最小化的函数统计学习理论定义了一 些指标来衡量函数的住能，其中最重要的是 ( (统计学习理论中 一个重要的概念模式识别方法中对 的定义为：对一个指数函数集，如果存在 h 个样本能够被函数集里的函数按照所有可能的 2h 中形式分开，则称函数集能够把 h 个样本打散函数集的 就是它能够打散的最大样本数目 h若对于任意数目的样本都有函数能将它们打散，则函数集的 是无穷大 简而言之， 它描述了 组成学习模型的函数集合的容量，也就是说刻画了此函数集合的学习能力 31 越大，函数集合越大，其相应的学习能力就越强例如对于二类分类问题，对于 每个可能的划分，在此函数集合中均存在一个函数 使得此函数对其中一个类取 +l，而对另外一个类取 推广性的界理论 对于一个学习机器，我们关心的是该学习机器对训练样本之外的样本数据的处理能力，即学习机的推广性统计学习理论系统地研究了对于不同类型的函数同济大学 硕士学位论文 基于支持向量机的多分类算法改进与应用 9 集，其经验风险和实际风险之间的关 系，即推广性的界，它 也 是分析学习机器性能 及 发展新的学习算法的重要基础推广 能力界的结论从理论上说明了学习机器的实际风险是由两部分组成的，即： 实际风险 =经验风险（训练误差） +置信范围， 置信范围和学习机器的 h 及训练样本 n 有关， 随 n/h 变化趋势如图 对于一个特定的问题，其样本数 n 是固定的，此时学习机器（分类器）的越高（即复杂性越高），则置信范围就越大， 从而 导致实际风险与经验风险之间可能的差就越大因此，在设计分类器时，我们不但要 要 使经验风险最小化，还要使 尽量小，从而缩小 了 置信范围，使期望风险最小神经网络等方法之所以会出现 “ 过学习现象 ” ，就是 因为在有限样本的情况下，如果网络或算法设计不合理，就会导致虽然经验风险较小，但置信范围会很大，导致推广能力下降，这 也 就是为什么在一般情况下选用过于复杂的分类器或神经网络往往得不到好的推广效果的原因 结构风 险最小化原则 传统机器学习方法中普遍采用经验风险最小化原则，由上面的结论可知在有限数据样本时只 有 最小化经验风险是不合理的因为经验风险和置信范围需要 我们 同时最小化，才能得到最小的实际风险 R(u)实际上，在传统方法中，选择学习模型和算法的过程就是调整和优化置信范围的过程，如果 选择的模型比较适合现有的训练 样本（相当于 h n 值适当），则 我们 可以取得较好的效果譬如 ： 应用神经网络时，需要根据实际问题和样本的具体情况来选择不同的网络结构（对应有不同的 ），然后 我们 再进行经验风险最小化为解决经验风险和置信第 2 章 机器学习与统计学习理论概述 10 范围这两项最小化风险泛函问题，统计学习理论提出一种新的策略：结构风险最小化原则 (简称 则统计学习理论同时还给出了合理的函数子集结构应满足的条件及在 则下实际风险的收敛性质2 设给定样本数目 n，那么随着 的增加，经验风险 会 逐渐 变小，而置信范围 会 逐渐递增真实风险的界是经验风险和置信范围之和，随着结构元素序号的增加，经验风险将 逐渐 减小，而置信范围将 逐渐 增加最小的真实风险的上界是在结构的某个适当的元素上取得的综合考虑经验风险与置信区的变化， 我们 可以求得最小的风险边界，它所对应的函数集的中间子集 以作为具有最佳泛化能力的函数集合 实现 可以有两种思路， 是在每个子集中求 得 最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集显然这种方法比较费时 费力 ，当子集数目很大甚至是无穷时是 该方法 不可行的第二种思路，即设 计函数集的某 个 结构使每个子集中都能取得最小的经验风险（如使训练误差为 0），然后只需选择适当的子集使置信范围 达到 最小，则这个子集中使经验风险最小的函数就是最优函数支持向量机方法实际上就是这种思想的具体实现 过程 第 3 章 支持向量机基本方法 11 第 3 章 支持向量机 基本方法 支持向量机的理论最初来自于对数据分类问题的处理对于线性可分数据的二值分类，如果采用神经网络来实现，其机理可以简单描述为：系统随机地产生一个超平面并 且 移动它，直到训练集合中属于不同类别的点正好位于该超平面的不同侧面，就完成了对 整个 网络的设计要求但是这种机理决定了 我们不 能保证最终所获得的分割平面位于两个类别的中心，这对于分类问题的容错性是 非常 不利的保证最终所获得的平面位于两个类别的中心对于分类问题的实际应用是很重要的支持向量机方法很巧妙地解决了这一问题 31,33， 34该方法的机理可以简单描述为：寻找一个满足分类要求的最优分类超平面，使得超平面在保证分类精度的同时，能够使超平面两侧的空白区域最大化理论上来说，支持向量机能够实现对线性可分数据的最优分类为了进一步解决非线性问题，人通过引入核映射方法将低维空间中的非线性问题转化为高维空间的线性可分问题来 解决 持向量机基本方法 线性支持向量机 给定训练样本集 ( i=1， 2， N）， +1， 它们从莱一确定但未知分布 p(x， y)中随机独立抽取 一、线性可分情形 我们 假设 +1 类与 可用超平面完全正确分离，当然这样的分离超平面可能有许多 种 ，那么 我们 如何选择一个较好的超平面作为分类判决面，使得它的推广能力即对新样本的正确分类能力高呢？线性支持向量机就是把具有最大分类面间距的分离超平面作为它的解，其中分类面间距的定义如下 定义 1 设分离超平面 T+b=0 把样本集 ( i=1， 2， N）正确分离，即 或统一写成 1 ， i=1， 2， N， 1111第 3 章 支持向量机基本方法 12 则该分离超平面的分类面间距定义为 分类面间距 =d+ + 其中 该定义表明，一个分离超平面的分类面间距实际上就是两类样本点到该平面的最短距离之和当存在点使得 1 ， d+ +=1/ | 即 分类面间距 =2/ | 。 显然，从直观上也可以看出当分离超平面的分类面间距越大，它对新样本的正确分类能力也越高 。 见图 义 1 对于给定的训练样本集，它的具有最大分类面间距的分离超平面称为最优分离超平面 线性 是要求最优分离超平面，即求 0 其中 是以下凸二次规划 (解： |/)(m in d 1: bx i |/)(m in d 1: bx i 同济大学 硕士学位论文 基于支持向量机的多分类算法改进与应用 13 引入拉格朗日函数 以上三式再加上原约束条件就构成式 ( 件，由于式 (凸二次规划，所以它们也是式 (解的充分必要条件把它们代入 L( ， b，a I)中并消去 ，得到式 (对偶规划式 （ 设 a*是式 (解，则 得的最优分离超平面是 ： 其中 0)( * bx 而 b 可由约束条件 第 3 章 支持向量机基本方法 14 确定，若 a* 0，则 求得 二、非线性可分情形 此时两类样本点非线性可分，即一个超平面不能把它们完全分开，但几乎线性可分，即只有少数点被错分，所以仍旧用一个超平面作为分界面引入松弛变量 使超平面 0 满足 样本 能被错分，所以是被错分样本数的一个上界 如图 示，图中两条虚线的方程为 1 ，中间的实线就是分界线 0 虽然每类有两个点落在两虚线 之间，但它们没有越过分界线，即满足 0l因此式 (值大于错分样本数 4，即式 ( 我们 引入以下目标函数 其中 C 是一个正常 数，可以称为惩罚因子，如果 C 很大，说明对于错分的惩罚大此时 过求解以下二次规划式 (实现 非线性支持向量机与核函数 上一节我们讨论了最简单 的线性支持向量机，即在原空间直接建立一个超平面作为分界面，显然这样 只有在给定样本集线性或几乎线性可分时才能得到较好的结果而实际上许多分类问题 要 复杂 很多 ，用简单的超平面无法达到分类的目的， 我们 必须以复杂的超曲面作为分界面我们这一节将要讨论的非线性支持向量机就是通过在另一个更高维的空间用前面的方法建立一个分类超平面，从面在原空间建立一个分类超 曲面 首先引入一个非线性映射， HR d : 把数据从原空间 射到更高维的特征空间 H，使得数据在 H 上是线性或几乎线性可分，如图 3 章 支持向量机基本方法 16 例 原空间 2R 中有两类数据点以圆周 9)2()1( 2221 分界面，引入映射 42: 则在 2R 中的圆周分界面变为 H 中的超平面： 4424321 的样本集 ( i=1， 2， N） 映射到特征空间 H 上的新样本集，对该新样本集利用线性 H 上建立一个超平面，我们不需要重新推导。 所以非线性 H 上建立了如下超平面，亦即在原空间 建立一个超平面 0)( 其中 而 ),2,1( 是以下二次规划的解 分类判决函数 从上面的公式中 看出西 (x) 总是以内积的形式出现，所以在计算时可以把它们作整体处理，这样在整个计算过程中，只需在原空间上计算而根本不用在同济大学 硕士学位论文 基于支持向量机的多分类算法改进与应用 17 特征空间上进行任何计算实际上我们也不必去考虑映射西是如何构造的，而只要找一个核函数 k（ x， y）使得它可以写成同一个函数的内积形式 定理 若对称核函数 k(x， y)满足 其中 z(x)为任意满足 的函数，则 k(x，可 )可以写成内积形式 下面列出几种常用的核函数， (1)p 阶多项式核函数： (2)径向基核函数： (3) 函数： 持向量 对式 (最优化求解得到的拉格朗日乘子 取值可能是：(1) 0i(2) 0i C， (3) i C 当i是后两种取值时，所对应的 为支持向量也即是说，支持向量是那些定义最优 分类超平面的训练样本，也是那些最难被分类的模式由式 (知，只有那些是支持向量的样本才对最优分类超平面和决策函数有贡献 回归支持向量机 支持向量机最初是为 了 分类问题而设计的，而支持向量机用在函数回归问题当中时，也同样具有很好的性能 32 回归支持向量机有线性回归和非线性回归，对于线性回归，考虑用线性回归函数 第 3 章 支持向量机基本方法 18 拟合数据 , , 1, 2 , , , ,di i i ix y i N x y 保证回归函数 (平坦，必须寻找一个最小的 ，为此，采用最小化欧几里德空间的泛数其中， 和 b 分别为性回归函数的法向量及偏移量，并假设所有的训练数据在精度 们可以解下面的优化问题，即 在不能完全满足 (中约束的情况下，我们可以引入松弛变量i和*i ，