（计算机软件与理论专业论文）基于支持向量机的公路车流量数据分析与预测模型.pdf

哈尔滨工程大学硕士学位论文 摘要 支掩向量机楚一种新的机器学习算法，以绫计学习理论作为其理论基 础，它的训练等价于解决一个二次规划问题，采精结掏风险最小化原刚，具 有预测能力强、全局最优及收敛速度快等显著特点。因此，本文从研究混沌 时闯序列的预测入手，掇出了一种基于支持向茧梳醋归瓒论的预溯方法，并 将其应用于混沌时间序列预测中。为了验证该算法的性能，我们做了两项工 作，一个怒和焉福空间的麓构理论对混淹时闻序列进行了革步与多步斡预溯， 并同文献中的神经网络的预测络果进行了比较分析；另个是在混沌时间序 列中掘入不丽永平的嗓声，并丽转p 网络及磁臻黼络的颥测结鬃进行了吃较 分析。仿真结果袭明，用支持向量回归算法进行混沌时间序列的预测能够取 彳葶比其他方法更持的效聚，其蠢镊好酶稳健性及泛纯麓力。 在研究混沌时间序列预测的基础上，我们结合高速公路车流量的特点， 对离速公路车流蹙颈瓣润题逡幸亍骈究，建立了基予支持翔量季且豹嵩速公籍车 流量短期预测的模型，_ 陵用实际的负荷数据进行仿真试验，实豫试验表明， 该方法在预测懿效果臻鬟懿爨予人工聿孛终嬲络方法。 关键词：统计学习理论；支持向量机；s v m ；车流量预测；混沌时间序列 哈尔滨：皤2 大学硕士学位论文 a b s tr a b t t h es u p p o r tv e c t o rm a c h i n ei san e wk i n do fm a c h i n el e a r n i n ga l g o r i t h m ，i t t a k e st h es t a t i s t i c a ls t u d yt h e o r ya si t sb a s et h e o r y i t st r a i n i n ge q u a l l yi nv a l u et o s o l v e so n et w op l a n sp r o b l e m s ，u s i n gt h es t m c t u r er i s ks m a l l e s tp r i n c i p l e ，h a st h e f o r e c a s t a b i l i t y i s s t r o n g ，t h eo v e r a l l s i t u a t i o ni sm o s ts u p e r i o ra n dt h e c o n v e r g e n c er a t ei sq u i c ka n ds oo i lt h er e m a r k a b l ec h a r a c t e r i s t i c t h e r e f o r e ，t h i s a r t i c l eo b t a i n sf r o mt h er e s e a r c hc h a o st i m es e r i e sf o r e c a s t ，p r o p o s e do n ek i n d b a s e do nt h es u p p o r tv e c t o rm a c h i n er e t u r nt h e o r yf o r e c a s tm e t h o d ，a n da p p l i e di t i nt h ec h a o st i m es e r i e sf o r e c a s t i no r d e rt oc o n f i r mt h i s a l g o r i t h mt h e p e r f o r m a n c e ，w eh a v ed o n et w ow o r k ，o n ew a st h eu s es p a c ec o n s t r u c t i o nt h e o r y c a r r i e so nt ot h ec h a o st i m es e r i e so nf o o ti nt h em a n ys t e p so ff o r e c a s t s ，a n d c a r r i e do nt h ec o m p a r i s o na n a l y s i sw i t ht h el i t e r a t u r ei nn e r v en e t w o r kf o r e c a s t r e s u l t ；t h eo t h e ri st oj o i nt h ed i f f e r e n th o r i z o n t a ln o i s ei nt h ec h a o st i m es e r i e s ， a n dc a r r i e do nt h ec o m p a r i s o na n a l y s i sw i t ht h eb pn e t w o r ka n dt h er b fn e t w o r k f o r e c a s tr e s u l t t h es i m u l a f t o nr e s u l ti n d i c a t e st h a tc a r r i e so nt h ec h a o st i m es e r i e s w i t ht h es u p p o r tv e c t o rr e t u r na l g o r i t h mt h ef o r e c a s tc a no b t a i nb e t t e re f f e c t s c o m p a r e dt oo t h e rm e t h o de v e n ，h a st h ev e r yg o o ds t e a d i n e s sa n de x u d e st h e a b i l i t y w i t ht h ef o u n d a t i o ni nc h a o st i m es e r i e sf o r e c a s tr e s e a r c h ，w em a k et h e s t u d y a b o u t h i g h w a y t r a f f i cf l o w m a g n i t u d e f o r e c a s t s a c c o r d i n g t ot h e c h a r a c t e r i s t i co fh i g h w a yt r a f f i cf l o wm a g n i t u d e ，a n dw ee s t a b l i s h e dt h eh i g h w a y t r a m cf l 。wm a g n i t u d es h 。n t e r m f o r e c a s tm 。d e lb a s e do nt h e5 u p p o r tv e c t o r m a c h i n e ，a p p l i e dt h ea c t u a ll o a dd a t ac a r r i e so nt h es i m u l a t i o ne x p e r i m e n t , s t u d y i n d i c a t e dt h a t 血i sm e t h o dh a so b v i o u sa d v a n t a g eo v e rt h ea r t i f i c i a ln e r v en e t w o r k m e t h o di nt h ef o r e c a s te f r c c t k e vw o r d s ：s t a t i s t i c a ls t u d yt h e o r y ；s u p p o r t sv e c t o rm a c h i n e ；s v m ；t r a f f i c f l o w m a g n i t u d ef o r e c a s t s ；c h a o st i m es e r i e s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指 导下，由作者本人独立完成的。有关观点、方法、数据 和文献的引用已在文中指出，并与参考文献相对应。除 文中已注明引用的内容外，本论文不包含任何其他个人 或集体已经公开发表的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：丑土嗵垒 曰期：z l ) d 占年月z 护日 哈尔滨工程大学硕士学位论文 1 1 研究背景 第1 章绪论 预测分析是根据过去和现在的已知去推测和预料将来的未知，是对被预 测事件发展过程中可能发生的一些不确定性因素和未知事件做出定性和定量 描述。预测分析的过程是从过去和现在已知的情况出发，利用一定的方法或 技术去探索或模拟不可知的、未出现的或复杂的中间过程，再推断出未来的 结果，如图1 1 所示： 图1 1 预测分析过程示意图 预测是人工智能、推理、机器学习中很重要的研究课题。在机器学习过 程中，主要是对现实情况进行抽象，建立数学模型，然后进行学习和测试。 对于预测问题，尤其是分类和回归问题，主要是根据训练集( 包括属性集和 观察值) 建立模型并进行学习和训练，然后根据测试集进行验证。学习是人 类特有的一种能力，是系统积累经验以改善其性能的过程。机器学习是继专 家系统之后人工智能应用的又一重要研究领域，也是人工智能和神经计算的 核心研究课题之一。 支持向量机是基于统计的学习理论的新一代机器学习技术。由于使用结 构风险最小化原则代替经验风险最小化原则，使它较好地解决了小样本情况 下的学习问题。又由于采用了核函数思想，使它把非线性问题转化为线性问 题来解决，降低了算法的复杂度。支持向量机的预测能力比神经网络等其它 哈尔滨1 程大学硕士学位论文 机器学习算法要优越的多”j ，因此掀起了近期机器学习的热潮。分类和回归 是机器学习中很重要的两类预测方法。根据观察值是否连续，我们可以将支 持向量机在预测方面的应用分为分类问题和回归问题。本文的主要内容就是 讨论如何将机器学习中的混合学习思想和集成学习思想应用于基于支持向量 机的预测研究中。 本文关于支持向量机的研究属于理论分析研究，主要侧重于混合算法和 集成算法研究。 混合算法与集成算法是机器学习中的重要算法。混合学习是指诸如神经 网络、遗传算法等机器学习算法的混合过程。目前在研究“混合”求解的方 法中，有串行混合，即一个智能算法作为另一个智能算法的前期预处理过程 或者后处理过程；还有就是一种智能算法集成在另一种智能算法计算过程中， 如模糊逻辑集成在神经网络的输入层上等等。目前这方面的研究已经取得了 很多成果并得到了广泛应用。对于复杂系统，已经推广到三种智能技术或更 多混合来进行求解。学习器集成是许多个分量学习器的集成，集成中的分量 学习器以某种方法组合在一起来对测试样本进行测试。众所周知，集成比组 成它的每个分量学习器表现出更优良的性能。一种集成算法是通过重采样技 术利用某种学习器构造不同的学习器，目前样本采样技术的方法有b a g g i n g ， b o o s t i n g ，r a n d o m i z a t i o n 和s t a c k i n g ：另一种集成算法是把不同种类的学习器 组合起来。 1 2 当前国内外研究现状 自1 9 7 0 年以来，v a p n i k 【4 1 等人发展了一种新的学习机支持向量 机。与现有的学习机包括神经网络，模糊学习机，遗传算法，人工智能等相 比，它具有许多的优点1 0 , 71 ：坚实的理论基础嘲和较好的推广能力、强大的非 线性处理能力和高维处理能力。因此这种学习方法有着出色的学习性能，并 在许多领域已得到成功应用，如人脸检测 9 1 、手写体数字识别0 】、文本自动 分类、非线性回归建模与预测 1 1 1 、优化控制 12 1 数据压缩及i t 寸i n 序列预测 1 3 1 等。 支持向量机主要用于模式识别和分类问题，a s ab e n h u r ”1 通过支持向 哈尔滨r 程大学硕士! 学位论文 量机将输入空间映射到高维特征空间后用于聚类分析中。b e i 】i l e t t 【1 5 1 将支持向 量机作为决策树中的每个节点，通过决策树来进行模式分类。现在已经将二 分类问题扩展到多分类问题中。c e l l i o a n g u l o 等人【16 】通过分解和重组两个过 程提出了多分类支持向量回归机一一k - s v c r ( “s u p p o r t v e c t o r c l a s s i f i c a t i o n r e g r e s s i o n ”m a c h i n e sf o rk c l a s sc l a s s i f i c a t i o np u r i p o s e s ) 。f u m i t a l e t a k a h a s h i 等人f f7 提出了基于决策树的多分类支持向量机。 a l e xj s m o l a 8 1 系统地介绍了支持向量机回归问题的基本概念和求解 算法。d r u c h e r 将支持向量机回归模型同基于特征空问的回归树和岭回归的 集成i 到归技术b a g g i n g 做了比较 1 9 j ；a l e s s a n d r ov e r r i 将支持向量机回归模 型同支持向量机分类模型和禁忌搜索( b a s i cp u r s u i td e n o i s i n g ) 作了比较，并 且给出了贝叶斯解释 2 0 1 。通过分析得出了如下结论：支持向量机回归模型由 于不依赖于输入空间的维数，所以在高维中显示出了其优越性。为了简化支 持向量机，降低其复杂性，已有了一些研究成果。比如，b u r g e s 提出根据给 定的支持向量机生成缩减的样本集，从而在给定的精度下简化支持向量机 【2 ”，但生成缩减样本集的过程也是一个优化过程，计算比较复杂；s c h o l k o p f 等人在目标函数中增加了参数v 以控制支持向量的数目，称为v s v r t 2 “， 证明了参数v 与支持向量数目及误差之间的关系，但支持向量数目的减少是 以增大误差为代价的。s u y k e n s 等人提出的最小二乘支持向量机( l s s v m ) 算 法具有很高的学习效率，对大规模数掘可采用共轭梯度法求解】；阳盛丰【4 1 等人提出了l s ，s v m 与序贯最优化算法 2 5 1s m o ) 的混合算法。 支持向量机是机器学习中的研究热点。但有关支持向量机的混合和集成 方面的文献很少。比如关于支持向量机的集成算法，主要是有关人脸识别方 面的1 2 7 , 2 8 , 2 9 1 ，它们专注于支持向量机分类器的集成，而有关回归方面的集成 鲜有文献介绍和应用。而关于集成学习的研究已经有很多文献，大多为神经 网络的集成，如可以参考h a r r i sd m c k e r 的神经网络集成 3 0 1 以及该网站上的 文章介绍。借鉴神经网络集成学习思想，本文将其应用于支持向量机的学习 中去。同样关于支持向量机的混合学习也还少有文献介绍。 从清华大学的张学工教授 3 u 2 于2 0 0 0 年引入支持向量机以来，在国内 掀起了关于支持向量机的研究热潮。李国正教授于2 0 0 4 年翻译了第一本关于 支持向量机的导论读物 3 3 1 。但是关于支持向量机的集成和混合算法，国内鲜 3 哈尔滨一【! 稃火学硕十学位论文 有研究论文。但是南京大学的周志华 3 4 , 3 5 1 已经将集成学习应用于神经网络的 研究。但总体上关于支持向量机的混合学习和集成学习在国内也还研究很少。 1 3 研究的意义及其必要i 生 近年来，合理规划、有效利用数据资源，己成为提升政府服务水平和企 事业单位核心竞争力的重要手段之一。对数据进行研究，并合理利用，受到 社会各行各业的普遍重视。 黑龙江省的公路交通在只常的管理中生成了大量的基础数据，如公路的 收费数据、车流量数据、运输客运系统的售票数据等，这些数据中隐藏着大 量的没有得到很好的利用信息。而公路管理和建设部门又经常需要对公路建 设的发展进行科学规划和调整，却常常苦于依据不足。对交通存在的各类数 据尤其是车流量数据进行研究，可以为决策者提供辅助手段，同时，研究和 建立黑龙江省的交通数据仓库可以有效的保存这些宝贵的历史资料。 黑龙江省交通科学研究所对黑龙江省的公路的数据库现状掌握有第一 手的资料，多年来也对车流量数据进行过一些基本研究，具有从事本项研究 的技术储备。本文的主要研究工作以此为依托和应用背景，具有较重大的实 际意义，同时能够促进推理、学习、s v m 技术的发展，具有一定的科学意义。 1 4 本文主要的研究工作与内容 本文所做的工作主要是对支持向量机的基础理论和应用进行研究。在详 细介绍统计学习理论和认真研究支持向量机回归理论及其算法的基础上应用 于混沌时i b j 序列预测和公路数据短期预测。 本文的内容主要包括： 第l 章引言，介绍了机器学习的研究现状，咀及本论文研究的意义。 第2 章介绍了关于统计学习理论的基本原理和支持向量机，其中包括一 些重要的概念：机器学习的推广能力、v c 维以及结构风险最小化，支持向 量机，支持向量机回归理论，支持向量机在推广能力上的体现，支持向量机 的核心部分核函数的选取以及支持向量机的算法等。 第3 章介绍了时间序列预测的概念与方法，从中引中出了一类复杂的非 哈尔滨： 程大学硕士学位论文 线性动态系统一混沌时间序列，概述其基本原理，并对典型的混沌模型作了 介绍，提出了基于s v m 的混沌时间序列预测。 第4 章根据支持向量机的原理和高速公路系统的特点，在第三章对混沌 时间序列预测的基础上，把支持向量机应用于高速公路车流量的预测之中， 并且和其他的方法相比较，显示了浚方法在车流量预测上的优越性能。 最后给出结论和展望。 哈尔滨l ：程大! 学硕士学位论文 第2 章支持向量机的学习理论 2 ，1 统计学习理论 统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理 论。它从理论上较系统的研究了经验风险最小化原则成立的条件、有限样本 下经验风险与期望风险的关系以及如何利用这些理论找到新的学习原则和方 法等问题。统计学习理论主要包括以下四方面的内容： ( 1 )经验风险最小化原则下统计学习一致性的条件； ( 2 )在这些条件下关于统计学习方法推广性的界的结论； ( 3 )在这些界的基础上建立的小样本归纳推理准则； ( 4 )实现这些新的原则的实际方法( 算法) 。 其中，最有指导性的理论结果是推广性的界的结论，与此相关的一个核 心概念是v c 维。 2 1 1 函数集的v c 维 为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性 收敛的速度，统计学习理论定义了一系列有关函数集学习性能的指标，其中 最重要的是v c 维( v a p n i kc h e r v o n e n k i sd i m e n s i o n ，简称v c 维) ，它是统计 学习理论中的一个核心概念，而且是目前为止对函数集学习性能的最好描述 指标。 模式识别方法中对v c 维的直观定义是：一个指示函数集q ( z ，c o ) ，劈q 的v c 维，是能够被集合中的函数以所有可能的2 “种方式分成两类的向量 z ；，z ，毛的最大数目h ，即能够被这个函数集打散的向量的最大数目。如果 对任意的n ，总存在一个1 , t 个向量的集合可以被函数集q ( z ，) ，巧q 打散， 那么函数集的v c 维就是无穷大。有界实函数集的v c 维可以通过用一定的 阐值将它转化成指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越 大) 。遗憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对 哈尔滨j 槲人学硕十学位论文 一些特殊的函数集知道其v c 维，比如在n 维实数空间中线性分类器和线性 实函数的v c 维是 + 1 ，而f ( x ，口) = s i n ( 似) 的v c 维则为无穷大。对于一些 比较复杂的学习机器，其v c 维除了与函数集有关以外，还受学习算法的影 响，其确定更加困难。 在图2 i ( a ) 中给出了点z ，z 2 和z ，的三种不同的可能标识，很容易的看出 这三条直线能够打散这些点。在图2 1 ( b ) 中，有四个点蜀，屯，z ，和z 。，假设其 中点= l 和z 、标为类别0 ，点z 2 和z 。标为类别l ，那么此时用一条直线不能把点 z ，和z 。与点z ，和z ，打散。因此可以看出平面中直线集的v c 维等于3 。 j z 2 繁 ( z 2 z ：八 毛 毛u _ ( 图2 1v c 维示意图 2 1 2 利用验证来界定v c 维 z v c 维很难确定。若模型用一定规范样式表示，那么v c 维被月2 爿2 + 1 所 限定，即h m i n ( r2 a2 ， ) + l 。这旱r 是包围可用到的数据向量的球体的最小 半径，4 2 是模型中各系数的平方和。这就可以避免了“维数灾难”，通过将 偏好顺序与模型系数平方和联系起来，即使在高维空间也能得到可靠模型。 在v c 维很难确定的情况下，用重复取样技术来估计期望损失，随机地将数 掘集分为训练集和验证集 4 q 。 静述模型中s 可表示为： 1 s = 三i n n 一- ；l n ( r ) ( 2 - 1 ) fz 7 哈尔滨工程大学硕士学位论文 其中：是根据验证集评估的模型数量，f 。是验证集大小。 显然，一方面验证集方法通过划分子集合，使得期望损失估计简化，可 以相对较为容易的求解；但另一方面，将数据集分为子集后也带来降低整个 估计值精确度的缺点。 2 1 3 推广能力的界 统计学习理论系统地研究了各种类型函数集的经验风险和实际风险之 阳j 的关系，目口推广性的界，关于两类分类问题有如下结论：对指示函数集中 的所有函数( 包括使经验风险最小的函数) ，经验风险和实际风险之间至少以 概率1 一玎满足如下关系【4 2 】： r ( 国) 尺。，( 。) + 1 鱼坐兰望生尘堕幽 ( 2 2 ) v 其中h 是函数集的v c 维，是样本数。 由此可见，学习机器的实际风险由两部分组成：一是经验风险刚l 练误 差) r 。( 珊) ，另一部分称为置信范围( c o n f i d e n c ei n t e r v a l ) 。置信范围和学习 机器的v c 维h 以及训练样本数，有关，因此，式( 2 2 ) 可以简单地表示为： 矗 r ( c o ) r 。，( c o ) + 中( )( 2 - 3 ) l 式( 2 2 ) - g i ( 2 3 ) 给出了关于经验风险和实际风险之间差距的上界，反映了 根据经验风险最小化原则得到的学习机器的推广能力，因此称作推广能力的 界。 从( 2 3 ) 式可以看出，当h l 较大( 即样本数z 较少) 时，置信范围中较大， 用经验风险近似实际风险就会有较大的误差，用经验风险最小化取得的最优 解可能具有较差的推广性；如果样本数较多，h 1 较小，则置信范围会很小， 那么经验风险最小化的最优解就接近实际的最优解。 另一方面，对于一个特定的问题，其样本数，是固定有限的，当学习机 器的v c 维越高( 即复杂性越高) ，则置信范围就越大，导致真实风险与经验风 险之f 刨可能的差就越大。 因此，为了得到实际风险的最好的界，我们希望能够对( 2 3 ) 式右边的项 哈尔滨： 程大学硕士学位论文 进行最小化。 2 1 4 模型估计 估计在经典统计学和统计学习理论中都发挥着核心作用；然而，它们的 估计对象完全不同。在经典方法中，模型形式是已知的，因而重点放在参数 的估计上。而在统计学习理论中，正确模型是未知的，重点在于估计竞争性 模型的相对性能以利于选择最好的模型m 】。 竞争模型的相对性能用损失函数来测定的。在经典统计学中，当比较概 率分御时用负的l o g 似然函数作为损失函数。然而其它的损失函数也被用于 不同种类的建模问题中。 一般来说，统计学习理论认为在数据向量z 和具体模型口之间的损失函 数为l ( z ，口) 。至于模型的参数族，前面介绍的概念可以被推广以便用t 7 来界 定模型的具体参数和模型所属的参数族。 当我们对数据的联合概率密度建模时，合适的损失函数为： l ( z ，口) = - l o g p ( z ，口) ( 2 - 4 ) 若z = z ，y ，则 l ( z ，口) = 一l o g p ( yl 石，口) ( 2 5 ) 另一方面，如果我们对它的实际分布并不感兴趣，而只对构造y 的预测 函数y ( x ，口) 来最小化对y 作错误预测的概率感兴趣，那么用o 1 损失函数 为： 抛= 留嚣嬲；多 池s ， 总之l ( z ，口) 可根据模型问题性质来选择。统计学习理论的必要条件是按 照惯例，较小的损失意味着较好的模型。选择了损失函数后，如果我们又知 道了数据的统计性质，那么识别最好的模型就相对容易得多了。如果数据向 量z 按照概率测度z ( z ) 随机产生，那么最好模型口就是根据f ( z ) 来最小化期 望损失( e x p e c t e dl o s s ) 的那一个： r ( a ) = i l ( z ，刚d f ( z ) ( 2 - 7 ) 哈尔暝上程大学硕士学位论文 从决策理论观点看，最小化r ( a ) 的模型是最优的。在决策理论术语中， 甜是决策向量，z 是结果，l ( z ，口) 是给定决策a 后结果z 的( 负的) 效用测度。 效用测度提供了数字编码：哪些结果优于其它结果，同时也提供了不确定程 度的定量测度：一个人愿意用较大利润较大风险的冒险策论而不愿意采用中 等利润可能性更大的保守策略。选择具有最好的期望( 负的) 效用r ( a ) 的决 策向量5 产生了同用效用测度界定的风险偏好相一致的最优决策，也就是况， 给定损失函数的最好的模型。 不幸的是，在实际中，因为界定数据统计特性的概率测度f ( z ) 未知，所 以期望损失r ( a ) 不能直接计算。然而，我们必须在观察数据集毛i = 1 ， 的基础上选择最合适的模型。假定观察数据是独立同分布的，则可以引入经 验损失函数月心，) ( e m p i r i c a ll o s sf u n c t i o n ) 作为期望损失的经验估计： 1 j r 洲p ( 口，) = ：三( 毛，口) ( 2 8 ) l r ：i 统计学习理论假定模型通过最小化r ( 0 2 ，) 来选取。 统计学习理论的根本问题在于：既然我们追求r ( 5 ，) 的最小化，那么 在什么条件下经验风险损失最小化能导出期望损失最小化的模型。这个问题 通过考察经验损失估计的精确性来回答。在经典统计学中，精确性用置信区 间来表达，然而置信区间是针对期望损失建立的而不是针对参数。既然定义 数据向量的统计性质的概率侧度f ( z ) 是固定且未知的，那么r ( 5 ) 也被认为 是固定且未知的。另一方面，既然r 。( 5 ，) 的值依赖于观察数据向量 乙，i = l ，那么r 。心，) 就是我们能够取样的随机量。因此统计学习理论 在界定给定月( 口，) 后的r ( 5 ) 时，引入了置信区间。 为了建立黉信区间，在考虑通过经验损失最小化来选择模型时，我们需 要考虑期望损失和经验损失之间差的概率分布。而这正是区别统计学习理论 和经典统计学的关键问题所在。统计学习理论的基本定理表明：为了解释最 小化经验损失来选择模型的事实，必须考虑期望损失和经验损失的最大差值； 也就是既这个差异的概率分布为：s u p f r ( a ) 一r 心，驯，n 是可供选择的模 型集。置信区问的控制是通过最大化期望损失和经验损失的差值来实现的。 v a p n i k 和c h e r v o n e n k i s 的重大贡献是在给定经验损失情况下构造小 呛尔滨l 。群人学颂十学位论文 样本的期望损失置信区间的一系列概率界定。作为结论的置信区间在三方面 不同于经典统计学： ( 1 ) 不事先假定所选模型是正确的，然后估计参数： ( 2 ) 基于小样本统计理论而不是经典的渐进近似理论； ( 3 ) 用一致的方法( 统一的衡量标准) 来考虑独立于模型形式的所选择 的模型集的自由度，这个方法是基于v c 维的测度。 v c 维在概念上被认为是完全保证发现一个完全拟合的模型所需数据向 量的最大数量。例如，因为n 个线性项能完全拟合n 个点，那么线性回归或 判别式模型的v c 维就等于模型中的项数( 也就是传统意义上的自由度) 。 v c 维的实际界定更为一般化，通常不需要完全拟合；然而，关于v c 维， 考虑完全拟合结果的直觉理解是有效的。例如，为了规避过拟合，数据样本 个数应该远远大于所选模型集的v c 维；否则只能得到对随机数据的完全拟 合( 即泛化能力差) 。 因为v c 维是用模型能够拟合的数据点个数来界定的，所以对于线性、 非线性、非参数模型和不同类型模型族的组合都是适用的。这些模型包括神 经网络、分类和回归树、分类和回归准则、径向基函数、贝叶斯网络等等。 而且v c 维是用来衡量拟合随机数据模型能力的更好的指示器，比用模型的 参数个数表示更好。v c 维提供了一个比经典统计学更为全面的自由度概念。 在v a p n i k 和c h e r v o n e n k i s 所得的概率界限中，置信区间的大小在很 大程度上取决于v c 维与数据向量个数之比。例如，若l ( z ，口) 是0 1 损失函 数，以至少1 一印的概率满足如下5 4 4 1 ： 心棚一, 7 2 脚) 州。( 叫) + 要( 1 + 1 1 + 竺丛塑) r 。( 口，) + 这早 s = 芋 1 n 【i 2 l + 1 一了4 l n 噜) 注意到尝在占的界定中起主导作用，因此在r ) 的置信区间的大小方面 哈尔滨工程大学硕士学位论文 也起主导作用。其它损失函数也有包含s 的类似的置信区间。 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是 经验风险( 训练误差) ，另一部分称作置信区间，它和学习机器的v c 维及 训练样本数有关，可以简单的表示为 r ( w ) 墨r 。( w ) 十中( h 1 ) ( 2 9 ) 它表明，在有限样本下，学习机器的v c 维越高( 复杂性越高) 则置 信区间越大，导致真实风险与经验风险之间可能的差别越大。这就是为什么 会出现过拟合( 过学习) 现象的原因。机器学习过程不但要使经验风险最小， 还要使v c 维尽量小以缩小置信区间，刁能取得较小的实际风险，即对未来 样本有较好的泛化性能。 2 1 ，5 模型选择 数据分析者不是仅仅提供一个单一的参数模型，而是根据偏好顺序的一 系列竞争模型，基于对数据的分析验证从中选择一个模型。统计学习理论的 结论用来选择最能解释数据的最高偏好的模型。 如图2 4 所示，模型的选择过程可分为两部分：一是在偏好顺序中确定 分离点：另一个是在分离点的前面，从这些竞争模型中选择平均经验损失最 小的模型。当分离点在偏好顺序中向前推进时，在分离点之前出现的模型集 及其v c 维稳定地上升。v c 维上升有两个效果： ( 1 ) 拟合数据更好的模型数量增多，因此最小平均经验损失稳定 地下降： ( 2 ) 期望均值的置信区间稳定地上升，因为其大小被v c 维控 制。 为了在偏好顺序中选择分离点，v a p n i k 和c h e r v o n e n k i s 倡导最小化期 望损失的置信区问的上限；也就是使期望损失的最坏估计最小化。 随着支持向量机在若干实际问题中应用的成功，统计学习理论正日益受 到国际主流学术界的重视，认为它有可能成为将包括神经网络在内的预知性 学习方法统一在一个理论框架内的理论基础。 哈尔滨工程大学硕士学位论文 损火 损火 最好的分离点分离点偏好 图2 2 模型选择过程示意图 统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理 论，从理论上来说，支持向量机能够克服神经网络的一些固有问题，获得较 好的泛化能力，但是在实际应用中，由于一般要解决的是多类问题，而经典 的支持向量机算法只给出了二类分类算法，因此怎样有效的把它拓展到多值 分类问题中仍是一个f 在研究的问题。 2 2 支持向量机 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本 学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助 解决许多原来难以解决的问题( 如神经网络结构选择问题、局部极小点问题 等) ；同时，在这一理论基础上发展了一种新的通用学习方法支持向量机 ( s u p p o r tv e c t o rm a c h i n e 或s v m l ，它已初步表现出很多优于已有方法的性 能。一些学者认为，s l t 和s v m 正在成为继神经网络研究之后新的研究热 点并将有力地推动机器学习理论和技术的发展。 哈自；滨t 程大学硕士学位论文 2 2 1 支持向量机多分类问题、核函数和损失函数介绍 2 2 1 1 多分类问题 对于支持向量机的多分类问题( k 一类问题) ，一般采用如下的三种方法 f 4 5 】： ( 1 ) 一对多方法( o n e a g a i n s t r e s t ) ，针对不同的世个分类，构造k 个分 类器，第k 个分类器是将第k 类与其余的类别分开，也就是况将第k 类重新标 号为+ 1 ，其它类重新标号为一1 。完成这个过程需要计算的是膨个二次规划， 求得k 个权值w 。和偏移b 。，然后根据多数投票法对每个测试样本进行预测。 1 矿( w ，六) = 去( ) + c ( 氕) ， w 妒( x ，) + b 1 一( 氕) ，i = 1 ，i f 茁，c t w ，p ( x 。) + b 一( 1 一( 彘) ，) ，i = 1 ，f i fx ，c 女 ( 磊) ， 0 ，f _ 1 ， ( 2 - 1 0 ) 决策函数为： 厂( 工) 2s g n ( m 。- a x k ( w 庐( x ) ) + b ) ) ( 2 11 ) ( 2 ) 一对一方法( o n e a g a i n s t o n e ) ，对于任意两个分类，构造一个分类器， 仅i ： ；5 别这两个分类，完成这个过程需要k ( k i ) 2 个分类器，计算量是非常 庞大的。对于每一个样本，根据每一个分类器的分类结果，看属于哪个类别 的次数多，最终就属于那一类。这个方法的不足之处在于可能产生属于多类 别的点。 1， m i n ( w 。，乞) = 去( ) w 。十c ( 岛) ， 妒( x ，) + 6 1 一( 岛) ，i = 1 ，i fx ，c w 妒( x ，) + bs 一( 1 一( 善) ，) ，i = 1 ，、t f i f x ，仨c 4 哈尔滨t 程大学硕士学位论文 ( 毛) ， o ，t = 1 ，f ( 2 1 2 ) 决策函数为： f ( x ) = m a x ( n ) ，n = # 协l ( x ) = q ) ( 2 - 1 3 ) 其中，。为通过以上的k ( k 一1 ) 2 个分类器判定x 属于k 类的次数。 ( 3 ) 层( 树) 分类方法，这种方法是一对一方法的改进，将k 个分类合并 为两个大类，每个大类旱面再分成两个子类，如此下去，直到最基本的世个 分类，这样形成不同的层次，每个层次都使用s v m 来进行分类。预测过程 是从树根开始，沿着不同的分支，直到叶子节点为止。 2 212 核函数 如果在输入空间存在一个函数k ( x ，x ，) 而且它可以表示为从输入空问 到特征空间的映射。e ( x ) 的内积，即k ( x ，x ，) = e o ( x ，) ，中( x ) ) 。一般k ( x ，x ，) 被称为核函数。在支持向量机中，这是一个重要的概念。因为正是由于核函 数的引入，才使得高维空间中的智能学习成为可能，而且学习的复杂度也没 有增加 4 6 1 。 假设给定输入空间中的样本集： ( x 1 ，y 1 ) ，( z 2 ，y 2 ) ，一，( x ，y ，) ，x ，r ，y ，r ，( f ，= 1 , 2 ，一，f ) 对于这些数据存在一个映射巾，使得下面的关系满足： 尺”斗h ：x ，斗中( x ，) 在输入空间中存在一个函数丘满足k ( x ，x ，) = ( _ ) ，中( x ，) ) ，则函数世 就称为核函数。核函数的本质是关于输入空间中数据的函数。根据前面的推 导公式可看出，应用核函数可避免直接计算o ( x ) o ( j ，) 。因此，即便我们不 知道o ( x ) m ( y ) 的表达式，也可以完成高维空间中的分类或回归。 常见的核函数有以下几种： ( 1 ) 多项式核函数 多项式映射是非线性模型的最普通方法， k ( x ，一) = “ x ( x ，一) = ( + 1 ) “ ( 2 - 1 4 ) 哈尔滨工程火学硕士学位论文 第二个核函数一般在避免h e s s i a n 阵为0 的情况下采用 ( 2 ) 径向基函数( g a u s s i a nr b f ) 足( x ，一) = e x p ( 一且! i j 粤) ( 2 1 5 ) 这个核函数由于具有某些良好的性质，表现出较强的学习能力，而受到 大家的青睐。其基本特点如下： 当参数盯寸0 时，口， 0 ，即全部样本点都是支持向量； 对任意给定的样本集q ，只要盯 0 充分小，高斯核函数支持向量机 必定可对其正确分类； 当盯- - + o o 时，高斯核函数支持向量机的判别函数为一常数，即把所 有样本点判为一类； a 过大，其分类能力较差；但仃过小也会造成“过拟合现象而降 低对新样本的正确分类能力； ( 3 ) 指数径向基函数( e x p o n e n t i a lr b f l m ，川= e x p ( 一警) ( 2 1 6 ) 当可以接受不连续时，指数径向基函数可以产生有吸引力的分段线性解。 ( 4 ) 单层感知机 带有单隐层的长期建立起来的多层感知机也有一个有效的核表示形式， k ( x ，一) = t a n h ( , o + 口)( 2 - 1 7 ) 其中参数p 是尺度值，参数目为偏移值。支持向量对应于感知机第一层， a g r a n g e 乘子对应于感知机的权重。 ( 5 ) 傅立叶序y l j ( f o u r i e rs e r i e s l 傅立叶序列可以看作是在2 n + 1 维特征空间中的扩展。该核函数界定在 区| - b j 一要，昙 ， s i n ( n + 去) ( z 一一) k ( x ，一) = _ 生一 ( 2 1 8 ) s i n ( 寺( x 一一) ) 哈尔滨工程大学硕士学位论文 因为它的规则化能力很差 3 9 ，这可以通过考虑傅立叶转换比较显而易 见，所以这个核函数可能不是较好的选择。 ( 6 ) 样条( s p l i n e s ) 样条由于其复杂性也是建模时比较常用的形式。k 次i v 个结点位于r 的有限样条为： tn k ( x ，r ) = x x “+ ( x f ，) + ( z 一f 。) ( 2 1 9 ) 定义在区间 0 ，1 上的无限样条为 k ( x ，) = x x ”+ ( x f ，) + ( x 一r 。) 。 d f ( 2 2 0 ) ( 7 ) b 样条( bs 口l i n e s ) ”“ o b 样条是另一个常用的样条表达式。这个核函数界定在 1 ，1 1 ，并且它 有一个吸引人的封闭形式 k ( x ，一) = b 2 0 一一)( 2 - 2 1 ) ( 8 ) 加核函数( a d d i t i v ek e r n e l s ) 因为两个f 定函数的和仍是正定的，所以更为复杂的核函数可以通过