支持向量机算法研究及应用毕业论文.doc

支持向量机算法研究及应用毕业论文.doc

《支持向量机算法研究及应用毕业论文.doc》由会员分享，可在线阅读，更多相关《支持向量机算法研究及应用毕业论文.doc（64页珍藏版）》请在冰点文库上搜索。

支持向量机算法研究及应用毕业论文

目录

1.绪论 4

1.1课题背景 4

1.2国外研究综述 4

1.3本课题研究的意义和目的 5

2.最优化基础 5

2.1欧式空间上的凸规划 5

2.2Hilbert空间上的凸规划 5

3.线性分类机 5

3.1线性可分问题的支持向量分类机 5

3.2线性支持向量分类机 5

4.线性回归机 5

4.1硬-带超平面 5

4.2线性硬-带支持向量回归机 5

5.核与支持向量机 5

5.1核函数 5

5.2支持向量机及其性质 5

6.支持向量机的应用 5

6.1准备工作 5

6.2问题描述 5

6.3步骤 5

6.4实现图 5

7.结束语 5

参考文献 5

致谢辞 5

附录1英文原文 5

附录2中文译文 5

附录3代码 5

.专业.专注.

1绪论

1.1课题背景

支持向量机是借助于最优化方法解决数据挖掘中若干问题的有力工具，它在一定程度上克服了“维数灾难”和“过学习”等传统困难，并在文本分类、生物信息、语音识别、遥感图像分析、故障识别和预测、时间序列预测、信息安全等诸多领域有了成功的应用。

国外数学专家仔细研究了支持向量机理论,并针对目前一些支持向量机算法存在的缺陷,分析了产生的原因,提出了两种新的支持向量机算法,针对支持向量机算法难以处理大规模数据的问题,提出了两种新的支持向量机分类方法。

随着对支持向量机研究的深入，涌现了许多支持向量机的变形算法，其主要思想是通过增加函数项、变量或系数等方法使公式变形，从而产生各种具有某一方面优势的或者具有一定应用围的新算法。

1.2国外研究综述

支持向量机是借助于最优化方法解决数据挖掘中若干问题的有力工具，支持向量机不仅有着统计学习理论的监视理论，而且具有直观的几何解释和完美的数学形式。

虽然自20世纪90年代有Vapnik提出以来一直处于飞速发展的阶段，但是支持向量机的理论基础和各种算法实现的基本框架已经形成，自2000年开始，国外已陆续有专著出版。

2004年，邓乃扬等人在科学出版了学术专著《数据挖掘中的新方法——支持向量机》，该书是国第一本专门对支持向量机进行全面完整介绍和论述的著作。

国外数学专家仔细研究了支持向量机理论，并针对目前一些支持向量机算法存在的缺陷，分析了产生的原因，提出了两种新的支持向量机算法,针对支持向量机算法难以处理大规模数据的问题，提出了两种新的支持向量机分类方法。

并就多类别分类问题等方面开展了初步的理论研究。

该文主要工作包括：

（1）讨论了支持向量机理论中各种变形的支持向量机算法，对常规支持向量机公式进行变形的算法主要有C-SVM系列、v-SVM系列、One-classSVM、RSVM、WSVM和LS-SVM等算法，通过增加函数项、变量或系数等方法使公式变形，产生出各种有某一方面优势或者一定应用围的算法。

通过比较它们各自的优缺点等情况，为提出新的支持向量机算法做了理论准备。

（2）介绍了超球面支持向量机算法的思想,以及超球面和超平面的区别。

（3）针对某些支持向量机算法不能解决样本类别之间差异造成的不良影响的缺陷，提出了一种新的加权支持向量机算法，该算法具有补偿类别差异的优点，可应用于解决多类别分类问题。

（4）提出了基于粗糙集理论和支持向量机理论的粗SVM分类方法。

（5）提出了基于主成分分析方法和支持向量机理论的去噪声加权SVM分类方法。

（6）把支持向量机理论应用到污水处理过程运行状态监控中去。

由于支持向量机具有坚实的理论基础并在很多领域表现出良好的推广性能，因为国际上正在广泛开展对支持向量机的研究。

90年代之后取得了许多突破性进展，许多改进的和新型的SVM算法相继出现。

目前对支持向量机的研究主要包括：

SVM训练算法；大规模问题的求解；模型选择；应用研究等反方面。

支持向量机是在统计学习理论基础上发展起来的一种新的通用学习方法，其主要思想可概括为两点：

首先，它通过使用非线性映射将低维输入空间的样本映射到高维特征空间，从而使得在特征空间采用线性方程对样本进行分类成为可能；其次，他遇到过使用结构风险最小化原则在特征空间构建最优化分类超平面，使得学习机会有较好的泛化能力。

最优化分类超平面可以通过解决一个二次规划问题获得，包括线性可分、非线性可分两种情况。

随着对支持向量机研究的深入，涌现了许多支持向量机的变形算法，其主要思想是通过增加函数项、变量或系数等方法使公式变形，从而产生各种具有某一方面优势的或者具有一定应用围的新算法。

1.3本课题研究的意义和目的

支持向量机是借助于最优化方法解决数据挖掘中若干问题的有力工具，它在一定程度上克服了“维数灾难”和“过学习”等传统困难，并在文本分类、生物信息、语音识别、遥感图像分析、故障识别和预测、时间序列预测、信息安全等诸多领域有了成功的应用。

在论文写作中学习运用相关软件绘制图行,熟练掌握文本中的公式编辑以及插入,学会运用vs2010软件求解相关问题。

学习支持向量机的相关理论知识，掌握支持向量机的理论、算法与拓展的方法。

了解支持向量机所研究的最终的目的。

学习支持向量机中用最优化方法解决问题。

支持向量机是基于统计学习理论，借助最优化方法来解决分类问题的新工具。

2最优化基础

2.1欧式空间上的凸规划

2.1.1凸规划问题

与最优化问题相比，凸规划是一类特殊的最优化问题，即对其中的函数附带若干限定条件的最优化问题，为简单起见，这里不讨论最一般的形式是凸规划，而讨论如下所示的凸规划问题。

定理2.1.1（凸规划问题）凸规划问题是指最优化问题

其中和，都是定义在上的连续可微的凸函数，而，是线性函数。

定理2.1.2考虑二次规划问题

其中为矩阵，，，，，。

若为半正定矩阵，则该二次规划问题为凸规划问题，即它是凸二次规划问题。

凸规划问题的基本性质

先考察凸规划的可行域的性质，为此给出以下引理：

引理2.1.3若是上的凸函数，则对于任意的，水平集

的凸集。

定理2.1.4凸规划问题的可行域是闭的凸集。

该问题的解集也是闭的凸集。

可见，凸规划的问题就是要寻找一个凸集上的一个凸函数的最小值点。

定理2.1.5设凸规划问题中的变量具有式

所示的分化，记若分别是变量和的严格凸函数和凸函数，则该问题对的解唯一。

2.1.2凸规划对偶问题

考虑凸规划问题，即

其中是上的连续可微的凸函数，分别记该问题的可行域和最优值为和：

现在研究如何估计，即找出的下界。

引进函数

其中和是乘子向量。

显然，当，时，有

，

因而

所以，若令

则有

这表明对任意是的一个下界，若要寻找这些下界中最好的下界，则导致下列最优化问题

其中是由式给出的函数。

弱对偶定理　　从前段对偶问题的导出可以得知，若记该对偶问题的最优值为：

，

则对偶问题的最优值是原始问题

最优值的一个下界。

这个事实常用下面定义的“对偶间隙”来描述：

定义2.1.6（对偶间隙）称原始问题的最优值与对偶问题的最优值之差为原始问题的对偶间隙。

定理2.1.7（弱对偶问题）原始问题的对偶问题间隙永远取非负值，即原始问题的最优值和对偶问题的最优值有如下关系：

注意，不论原始问题和对偶问题是否有解，上述定理中的式总是成立的，即允许该式中的和取无穷大值。

例如，当原始问题的目标函数值无下界时，。

此时必有，即对偶问题无可行解。

反之，当对偶问题的目标函数值无上界时，。

此时必有，即原始问题无可行解。

推论2.1.8设和分别为原始问题和对偶问题的可行点。

若，则和分别为原始问题和对偶问题的整体解。

强对偶定理强对偶定理主要研究对偶间隙为零的情况。

要保证对偶间隙为零是有条件的。

这样的条件称为约束规格。

对凸规划来说，最简单的约束规格是如下的Slater条件：

定义2.1.9（Slater条件）称凸规划满足Slater条件，如果存在着可行点，使得

当该凸规划中的前个不等式约束为线性约束时，则只需存在着可行点，使得

定理2.1.10（强对偶理论）考察凸规划。

若满足Slater条件，则它的对偶间隙为零。

进一步，若还知原始问题的最优值可以达到，即存在着最优解，则对偶问题的最优值也可以达到，即必存在着对偶问题的整体解，使得

凸函数的最优性条件

首先引进著名的Karush-Kuhn-Tucker（KKT）条件：

定义2.1.11（KKT）条件考虑凸规划。

称满足KKT条件，如果存在分别与约束和约束对应的乘子向量和，使得函数

满足

利用强对偶定理，不难证明KKT条件是凸规划解的必要条件：

定理2.1.12考虑凸规划，并设它满足Slater条件。

若是该问题的解，则满足KKT条件。

KKT条件不仅是凸规划解得必要条件，而且也是其充分条件。

定理2.1.13考虑凸规划

若满足KKT条件则是该问题的解。

定理2.1.14对于满足Slater条件的凸规划来说，点是解得充分必要条件是它满足KKT条件。

2.2Hilbert空间上的凸规划

现在把定义在欧式空间上的凸规划推广到Hilbert空间上。

与从欧式空间到实数的函数相对应，需要考虑从Hilbert空间到实数或欧式空间的映射。

2.2.1凸函数及Frechet导数

Hilbert空间中的凸集和凸映射的定义与空间中的凸集和凸函数定义类似，即只需要把定义和定义中的空间直接推广到Hilbert空间即可。

对此我们不在阐述。

这里先推广空间上的函数的可微性。

定义2.2.1（Frechet导数）设是从Hilbert空间到实数的映射，。

如果存在从到的线性连续映射其中使得

则称映射在点处是Frechet可微的，并称上式的积中的元素为在点处的Frechet导数，记为

和通常定义函数的连续可微一样，称从到的映射在上是连续可微的，如果它在的任一点处都是Frechet可微的，且其Frechet导数是连续的。

2.2.2凸规划问题

定义2.2.2（Hilbert空间上的凸规划问题）Hilbert空间上的凸规划问题是指最优化问题

其中和，都是从Hilbert空间到实数上的连续可微的凸映射，而，是式所示的线性连续映射。

关于上式问题的性质，我们几乎可以逐字逐句抄写欧式空间上的定理，仅仅是它们所考虑的空间哟所不同而已。

事实上，与从到的二次函数相对应，我们可以考虑Hilbert空间到的二次映射，其中：

是线性连续映射。

若对任意的都有则称是半正定的。

这样便有如下定理：

定理2.2.3考虑二次规划问题

其中，和分别从Hilbert空间到，和上的线性连续映射，。

若为半正定的，则该二次规划问题为凸规划问题，即凸二次规划问题。

定理2.2.4考虑Hilbert空间H上的凸规划问题。

若是它的局部解，则也是它的整体解。

推论2.2.5考虑当H为半正定时的凸二次规划问题，则它的任一局部解都是它的整体解。

凸规划的对偶理论

与式引进的对欧式空间凸规划的Lagrange函数相对应，这里可以引进Lagrange隐射

，

其中和是Lagrange乘子向量。

与导出由定义给出的空间上凸规划问题的对偶问题的过程完全一样，可以得到Hilbert空间上的凸规划问题的对偶问题：

定义2.2.6（对偶问题）称问题

为问题

关于Lagranger映射的对偶问题，或简称为问题的对偶问题。

定义2.2.7（Slater条件）称Hilbert空间上的凸规划满足Slater条件，如果存在着可行点，使得

凸规划的最优性条件

定理2.2.8考虑问题

并设它满足定义的Slater条件，若是该问题的解，则满足KKT条件：

定理2.2.9考虑凸规划，若满足上述条件，则是该问题的解。

上述两个定理意味着下列定理成立：

定理2.2.10对于满足由定义2.2.7定义的Slater条件的问题来说，点是其解的充分必要条件是它满足KKT条件。

3.线性分类机

3.1线性可分问题的支持向量分类机

为建立线性分类机，先考虑线性可分问题。

粗略的说，线性可分问题就是其训练集能用一个超平面完全正确分开的问题，线性可分问题的确切定义如下：

定义3.1.1（线性可分问题）考虑式所示训练集，其中。

若存在和正数，使得对所有使得下标，有而对所有使得下标，有，则称训练集T线性可分。

同时我们也称相应的分类问题是线性可分的。

3.1.1最大间隔法

算法3.1.2（线性可分问题的最大间隔法）

设已知训练集，其中；

构造并求解凸二次规划

得解；

构造分划超平面，由此求得决策函数

最大间隔法的性质

定理3.1.3对线性可分问题来说，最大间隔法中的凸二次规划问题的解存在，而且满足：

（i）0

（ii）存在使得

（iii）存在使得

。

上述定理阐明了3.1.2的下了性质：

（i）表明该算法总可以构造出一个分划超平面，显然此分化超平面能将训练集中对应两类点的输入完全正确的分开；结论（ii）和（iii）表明该算法得到的超平面是两个支持超平面。

下面定理表明这样构造的分划超平面是唯一的。

定理3.1.4对线性可分的问题来说，最大间隔法中的凸二次规划问题的解唯一。

3.1.2线性可分问题的支持向量分类机

现在考虑实现最大间隔法原则的另一途径，即不直接求解最优化问题，而是通过寻求它的对偶问题的解得到它的解。

原始问题与对偶问题解得关系

为导出原始问题的对偶问题，引入函数

其中为乘子向量。

这样便有下列定理

定理3.1.5最优化问题

，

是原始问题的对偶问题。

定理3.1.6最优化问题是凸二次规划

证明令

则问题可表示为

令，则易见。

所以H是半正定矩阵。

因此根据定理可知上式是凸规划。

线性可分支持向量分类机

算法3.1.6（线性可分支持向量分类机）

给定训练集，其中

；

构造并求解凸二次规划问题

得解；

计算选取的一个正分量据此计算

构造分划超平面，由此求得决策函数

其中

。

3.2线性支持向量分类机

本节讨论一般分类问题的线性分划。

设训练集为

其中，这里与前节不同，不在限定它是线性可分的。

3.2.1最大间隔法

算法3.2.1（最大间隔法）求解与训练集对应的原始最优化问题，得解，构造分划超平面，并由此求得决策函数其中。

（原始问题关于b的解不唯一的例子）考虑一维空间R上的分类问题。

设训练集为

设选取惩罚参数，其原始最优化问题为

试求该问题的函数

下面求出满足定义所给出的KKT条件的和。

首先写出KKT条件：

显然这些条件蕴含着

这样只需要三种情况寻求满足条件的全部解

（i）设此时有这些条件可得最后一式与条件矛盾，因此此事无解。

（ii）设此时有这些条件可得显然最后两式时矛盾的，因此此事无解。

（iii）设此时这些条件等价于

，

其中因此根据定理知，问题对b的解集是闭区间。

定理3.2.3原始问题关于b的解得集合是一个有界闭区间，其中

3.2.2线性支持向量分类

线性支持向量分类机的基本思想是通过求解对偶问题得到原始问题的解。

定理3.2.4最优化问题

是原始问题的对偶问题。

定理3.2.5对偶问题必有解

为简化对偶问题，我们利用等式约束消去变量，从而变成只含有变量的问题。

此外，与讨论线性可分问题是类似，我们再把这个大化问题写成小化问题，即下列凸二次规划问题

。

4.线性回归机

4.1硬-带超平面

4.1.1从线性回归问题到硬-带超平面

为求解线性回归问题，首先引入-带和硬-带超平面的概念。

定义4.1.1（超平面的-带）设，一个超平面的-带是指该超平面沿轴依次上下平移所扫过的区域

请注意，上面定义的超平面的-带是开区域，即它不包含满足

和的点

定义4.1.2（硬-带超平面）设给定训练集，其中并给定。

称一个超平面为对于训练集T的硬-带包含了训练集T中所有训练点，即超平面满足

现在考察任意训练集的硬-带超平面，由于训练集中只有有限个训练点，所以当充分大时，硬-带超平面总是存在的，而这里能够使硬-带超平面存在的值不会太小，它应大于下列最优化问提的最优值：

显然，对给定的有两种可能：

当时，硬-带超平面存在，而且不唯一；当时，硬-带超平面不存在。

4.1.2硬-带超平面与线性分划

我们设法把构造硬-带超平面转化为线性分划的问题，以便用分类的方法构造硬-带超平面。

从该式所示的训练集T出发构造出两类点：

将训练集T中每个训练点的y值分别增加和减少，得到正类点和负类点两个集合，分别记他们为和，即

由此得到分类问题的训练集

其中和表示输入，最后一个分量1和-1表示输出，可以想象，构造对于原训练集T的硬-带超平面就等价于对上述训练集进行一次完全正确的线性分划。

事实上，下列定理论述了硬-带超平面和线性分划之间的确切关系：

定理4.1.3对给定的训练集和，考虑

定义的集合和集合。

则一个超平面是硬-带超平面的充要条件是和分别位于该超平面的两侧，且和中所有的点都不在该超平面上。

4.1.3.构造硬-带超平面的最优化问题

应用解决分类问题的方法来构造硬-带超平面，具体说时，与线性可分的最大间隔法相对应，我们也可以建立构造硬-带超平面的最优值问题。

注意，与n维空间上的回归问题的训练集相对应，这里的分类问题是维空间上的，其超平面的一般形式是，即超平面的法向量的形式应为，其中是与x对应的n维向量，是与y对应的实数。

可以得到凸二次规划问题

求出其解后，便得到分划超平面

由此可得线性回归函数

其中

定理4.1.4设凸二次规划问题有解，则有而且，若令

则（i）满足

其中是问题的最优值；

（ii）是凸二次规划问题

的解。

4.2线性硬-带支持向量回归机

本节对训练集建立线性硬-带支持向量回归机

4.2.1原始问题

在前文中已引入了构造线性回归函数的凸二次规划问题，这就是我们的原始最优化问题

对于寻求回归直线的一维空间上的回归问题来说，上述最优化问题有着清晰的几何意义。

对上述公式有以下定理

定理4.2.1若满足，其中是问题

的最优值，则原始问题的解存在，而且它关于的解唯一，即若和都是解，则。

4.2.2对偶问题及其与原始问题解得关系

为导出原始问题的对偶问题，引入函数

其中为乘子向量。

定理4.2.2最优化问题

是原始问题的对偶问题。

定理4.2.3若满足，其中是问题

的最优值，则对偶问题必有解

证明一方面，当时，有定理知原始问题有解；另一方面，注意到原始问题是凸规划，而且它还满足Slatert条件，由定理知它的对偶问题一定有解显然

定理4.2.4最优化问题

是凸二次规划问题。

4.2.3线性硬-带支持向量回归机

算法4.2.5（线性硬-带支持向量回归机）

（1）给定训练集，其中

;

（2）选择适当的参数

（3）构造并求解凸二次规划问题

得解；

（4）计算。

选取的分量，据此计算

或者选取的分量，据此计算

（5）构造决策函数

定义4.2.6（支持向量）设为算法所得到的问题的解。

称训练点为支持向量，如果的分量或者否则称为非支持向量。

5.核与支持向量机

5.1核函数

5.1.1核函数及其特征

首先给出核函数的定义：

定义5.1.1（核函数）称定义在上的函数是的核函数或简称它是核函数，若果存在着从到Hilbert空间H的变换

使得

其中表示空间H中的积。

定义5.1.2（Gram矩阵）给定函数：

和称第i行第j列元素为的阶矩阵K为函数的关于的Gram矩阵。

定理5.1.3（核函数的特征）定义在上的对称函数式核函数的充要条件是对任意的关于的Gram矩阵。

是半正定的。

5.1.2函数的判定和常用的核函数

定理5.1.4定义在上的函数是核函数。

证明令，则可表示为

于是有定义知，是核函数。

保持核函数的运算

定理5.1.6设和都是上的核函数，则它们的核

与积

也都是核函数。

常用的核函数

现在从上面给出的最基本的核函数出发，通过保持核函数的运算，构造两个最常用的核函数。

多项式核函数

定理5.1.7设d为正整数，则d阶齐次多项式函数

和d阶非其次多项式函数

都是核函数

Gauss径向基核函数

定理5.1.8以为参数的Gauss径向基函数

是核函数。

5.2支持向量机及其性质

5.2.1支持向量分类机

算法5.2.1（-支持向量分类机）

给定训练集，其中

选取适当的核函数以及惩罚参数；

构造并求解凸二次规划问题

得解

计算：

选取位于开区间中的的分量，据此计算

构造决策函数

其中

定义5.2.2（支持向量）设为算法所得到的问题的解，称训练点的输入为支持向量，如果的分量非零；否则称为非支持向量。

定理5.2.3设为算法

所得到的问题得解。

若由式

确定，则

（i）对应于的支持向量满足；

（ii）对应于的支持向量满足；

（iii）非支持向量满足。

5.2.2支持向量回归机

使用核函数把非线性分划的回归算法改写成如下通常使用的-支持向量回归机。

他可以看成进行线性回归的算法即线性-支持向量回归机向非线性回归的推广。

算法5.2.4（-支持向量回归机）

（1）给定训练集，其中

.

（2）选取适当的核函数以及适当的精度和惩罚参数

（3）构造并求解凸二次规划问题

得解

（4），选取位于开区间中的的分量或，若选到的是，则

若选到的是则

；