（系统工程专业论文）支持向量机算法研究及其在智能交通系统中的应用.pdf

中文摘要 传统统计学研究的是样本数目趋于无穷大时的渐进理论，而统计学习理论研 究的是小样本条件下的学习理论。由于实际的样本数量是有限的，因而在理论上 统计学习理论有其优越性。基于统计学习理论和结构风险最小化原则的支持向量 机不仅模型结构简单，而且具有良好的泛化能力。因此，其受到了广泛的关注， 并逐渐成为机器学习领域的研究热点之一。 随着通信、信息与电子工程以及计算机技术的快速发展，智能交通系统越来 越受到广泛重视，从而对车型识别、车牌识别和交通流预测等技术提出了更高要 求。本文以支持向量机为基础，对模式识别和回归分析的基本算法及其在智能交 通系统中应用进行了广泛的研究。 本文的主要工作以及成果包括： ( 1 ) 在中心型支持向量机基础上，吸取了解决各类别样本数量不均衡和增 量学习的思想与方法，定义了一种新的权系数矩阵，并结合多类别分类问题，提 出了均衡增量型多类别分类算法。实验结果表明该算法具有较高的稳定性和判别 精度。 ( 2 ) 通过对几种多类别分类算法的研究，分析了这些算法的优缺点，并结 合霍夫曼树，提出了一种基于霍夫曼决策树的多类别分类算法。最后在多种开放 式数据集上进行仿真实验，结果验证了该算法不仅具有较高判别精度，而且训练 效率非常高。 ( 3 ) 首先比较系统地对支持向量机回归的理论和基本实现进行研究，然后 分析了v s v r 的优点与不足，并提出v - e s v r 算法。实验结果表明该算法可以有 效地进行非线性系统建模；具有与v - s v r 算法相类似的特性；另外，其对偶模型 非常简单，可以较方便地设计增量学习和在线回归算法。 ( 4 ) 在简要地介绍了智能交通系统的特点和相关技术基础上，分别使用基 于霍夫曼决策树的多类别分类算法和v - e s v r 算法来处理车型识别和短时交通量 预测问题。最后实验表明支持向量机在交通系统中应用的可行性和有效性，并具 有广阔的前景。 关键词：统计学习理论支持向量机多类别分类算法支持向量回归智能交通系 统 a b s t r a c t t h et r a d i t i o n a ls t a t i s t i c si sag r a d u a lt h e o r yw h i c ht h ea m o u n to fs p e c i m e ni s t e n d i n gt oi n f i n i t e ，w h i l es t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) i s at h e o r ya tt h ec o n d i t i o n o fs m a l ls p e c i m e na m o u n t s i n c et h es p e c i m e na m o u n ti sa l w a y sl i m i t e di nr e a l i t y , s l th a si t st h e o r e t i c a la d v a n t a g e b a s e do ns l ta n ds t r u c t u r e 砌s km i n i m u m ( s g m ) p r i n c i p l e ，s u p p o r tv e c t o rm a c h i n e ( s v m ) i sn o to n l ys i m p l ei ns t r u c t u r e ，b u ta l s oh a s 9 0 0 dg e n e r a l i z a t i o na b i l i t y s os v mh a sg r a d u a l l yb e c o m eo n eo fh o t s p o ti s s u e si n t h ef i e l do f m a c h i n el e a r n i n g w i t ht h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o n i n f o r m a t i o ns c i e n c e & e l e c t r o n i c e n g i n e e r i n ga n dc o m p u t e rt e c h n o l o g y , i n t e l l i g e n c et r a n s p o r ts y s t e m ( i t s ) h a sb e e n a t t a c h e de x t e n s i v ei m p o r t a n c ei n c r e a s i n g l y , t h u sp u tf o r w a r dag r e a t e rd e m a n do n t e c h n o l o g i e si nm a n yf i e l d s ，s u c ha sr e c o g n i t i o no fv e h i c l e - t y p ea n dv e h i c l e p l a t e ， p r e d i c t i o no ft r a f f i cf l o we t e t h ep u r p o s eo ft h i sa r t i c l ei st o ，b a s e do nt h es v m ， c o n d u c tr e s e a r c ho nb a s i cm e t h o d so fm o d e li d e n t i f i c a t i o na n dr e g r e s s i v ea n a l y s i s ， a n dt h e i ra p p l i c a t i o n st oi t s t h i sa r t i c l ei n c l u d e st h ef o l l o w i n gm a i nt a s k sa n de x i s t i n ga c h i e v e m e n t s ： i b a s e do nt h ep r o x i m a ls v m ，t h i st h e s i sd r e wu p o nt h ei d e ao fi n c r e m e n t a l l e a r n i n ga l g o r i t h ma n dt h es o l u t i o no fi m b a l a n c ei nt r a i n i n gs p e c i m e na m o u n t 缸 d i f f e r e n ts o r t s ，l a t e rd e f i n e dan e wk i n do fw e i i g h t e dc o e f f i c i e n tm a t r i x ，p u tf o r t ha m u l t i c l a s sc l a s s i f i c a t i o na l g o r i t h mo fb a l a n c e da n di n c r e m e n t e x p e r i m e n t a lr e s u l t s h a v es h o w e dt h a tt h i sa l g o r i t h mh a sf a i r l yh i g hs t a b i l i t ya n dc l a s s i f i c a t i o na c c u r a c y 2 b yc o n d u c t i n g r e s e a r c ho ns e v e r a lm u l t i - c l a s sc l a s s i f i c a t i o n a l g o r i t h m s ， s u m m a r i z i n gt h e i rm e r i t sa n dd e m e r i t sa n dc o m b i n i n gw i t ht e c h n o l o g yo fh u f f m a n t r e e ，t h i sd i s s e r t a t i o nb r o u g h tf o r w a r dam u l t i - c l a s sc l a s s i f i c a t i o na l g o r i t h mw h i c hi s b a s e do nh u f f m a nd e c i s i o nt r e e l a t e ro nc o n d u c t e ds i m u l a t i v ee x p e r i m e n t so n m a n yo p e n e dd a t a b a s e s ，h a v ep r o v e dt h a ta l g o r i t h mi sn o to n l yw i t hr e l a t i v e l yh i g h c l a s s i f i c a t i o na c c u r a c y , b u ta l s ow i t hv e r yh i g ht r a i n i n ge f f i c i e n c y 3 f i r s t l y , w ec o n d u c t e dr e l a t i v e l ys y s t e m a t i cr e s e a r c ho nt h e o r ya n dr e a l i z a t i o no f s u p p o r tv e c t o rr e g r e s s i o n ，t h e na n a l y z e dt h em e r i t sa n dd e m e r i t so fv s v g , a n d f u r t h e rp u tf o n l lt h ev - e s v ra l g o r i t h m f i n a l l y , c o n d u c t e dt h ee x p e r i m e n t t h er e s u l t s o f w h i c hi n d i c a t et h i sa l g o r i t h mi sn o to n l yw i t hs i m i l a rf e a t u r e st ov - s v r ，b u ta l s oi t s d u a lp r o b l e mi sv e r ys i m p l e ，s oc a nb eu s e dt od e s i g ni n c r e m e n t a ll e a r n i n ga l g o r i t h m a n do n - l i n eo n ei na r e l a t i v e l yc o n v e n i e n tw a y 4 b a s e do nt h ea n a l y s i so nt h ec h a r a c t e r i s t i c so f l t sa n dr e l e v a n tt e c h n o l o g i e s , t h i s a r t i c l em a d eu s eo fh f m l h es v mt od e a lw i t hv e h i c l e - t y p er e c o g n i t i o n a n d v - e s v rt os o l v et h ef o r e c a s t i n go fs h o r t - t e r mt r a f f i cf l o w f i n a l l y , e x p e r i m e n t a l r e s u l t ss h o w t h ef e a s i b i l i t ya n de f f e c t i v e n e s so f a p p l i c a t i o no f s v mi ni t s a n di t w i l l h a v eag o o df u t u r e k e yw o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) ，s u p p o r tv e c t o rm a c h i n e ( s v m ) ， m u l t i c l a s sc l a s s i f i c a t i o na l g o r i t h m ，s u p p o r tv e c t o rr e g r e s s i o n ( s ui n t e l l i g e n c e t r a n s p o r ts y s t e m ( i t s ) 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盘生盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 硝 签字开期： j 学位论文版权使用授权书 年多月甜闩 | 本学位论文作者完全了解盘注盘茎有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数掘库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 靴做储戳：荆 签字嗍年月咖 导师签名： 签字隅衫年石月芗f 1 第一章绪论 1 1 研究背景 第一章绪论 随着科学技术的日益进步，以及社会的全面、快速、健康发展。各行各业逐 步发展并走向成熟，积累可谓丰富，但是自从入世以来，也清醒地看到竞争的不 断加剧。企业面临的不仅是内部激烈竞争，而且还有大量的海外公司，这就促使 企业需要改变以前的经营管理模式，逐步地构建企业核心竞争力。著名的诺贝尔 奖得主西蒙说过“管理就是决策”。不禁要问：决策依据是什么? 显然，管理决策的依据来自于组织的日常业务和市场调查数据，但是面对这 些海量数据，决策者往往束手无策，这就对统计工作者提出了很高要求。同时越 来越多的非线性高维数据需要分析处理，也给传统统计学方法提出了严峻的挑战 “1 。为了解决这样的复杂难题，从而产生了一系列的数据挖掘理论与技术，并且 借助于计算机技术的飞速发展，使得复杂数据分析处理的工作变得越来越容易 【2 】 o 上面提到组织进行决策时不能直接使用大量的原始数据，而是需要从数据中 发现感兴趣的知识，以作为决策的依据。模式识别和回归分析是知识发现中的重 要内容，也是处理众多其它问题的核心。 用于模式识别和回归分析的方法很多，例如统计方法、多元统计分析”“”以 及人工神经网络”1 等。这些方法虽然在实际中使用的比较多，但是还存在许多不 足。例如，统计方法通常需要样本的先验知识，并要求有足够多的样本数量，而 这些要求往往很难满足，以致于这类方法在实际应用中的效果并不理想。人工神 经网络虽然较好地解决了非线性问题，但是由于存在网络结构不易确定、过学习、 欠学习和易于限于局部极小等固有缺陷，从而限制了其应用。另外，人工神经网 络的学习算法仅仅试图使经验风险最小化，与传统的最小二乘法相比，在原理上 面缺乏实质性的突破，这也是出现过拟合现象的根本原因，导致其推广能力的下 降。 第一章绪论 1 2 数学规划理论 1 2 1 非线性规划 非线性规划( 亦称非线性优化) 是求一个定义在甩维空间中单值函数的极值 问题，另外自变量可能受限于有限个不等式或等式约束。其数学表达式为： m i n ，( x ) 。i c ，( x ) = 0 ，( f e ) ( 1 1 ) i c ，( 石) o ，( f ，) 、 其中x r “，e = l ，2 ，他) ，i = + 1 ，肼 。满足问题( 卜1 ) 约束条件的点称 为可行点，所有可行点的集合称为可行域，记为d 显然， d = 圳c j ( x ) = o ，i e ；e ( 的o f d ( 1 2 ) 从约束条件上来看，当没有约束条件时，则称为无约束优化问题，否则称约 束优化问题；若只有等式约束，即栅= 帆 0 ，则称为等式约束优化问题；另外 如果所有约束函数都是线性函数，这时称问题( 1 - 1 ) 是线性约束优化问题。 下面将介绍一类特殊的非线性规划凸规划。 当问题( 1 1 ) 的等式约束函数c ，( ni e 都是工的线性函数，而且，( 工) 和 不等式约束函数e o ) ，f 1 分别是开凸集d c r ”上的凸函数和凹函数，则称之为 凸规划。如果f ( x ) 还是开凸集d 上的严格凸函数，则称为严格凸规划。凸规划 问题的任何局部解都是全局最优解，并且解集是凸的。若问题是严格凸规划，则 其全局最优解( 如果存在) 是唯一的。 1 2 2 相关定理 定义1 1 约束最优化问题( 卜1 ) 的可行域为d 。若，d ，存在占 0 ，当 x d g l l x x i i ，( ，) 成立，则称x 为 约束问题的严格局部极小值( 严格局部解) 。 定义1 2 设，e d ，当工d 、 x ) 时，总有f ( x ) f ( x ) 成立，则称x 为问 题( 卜1 ) 的全局极小值( 全局解) 。若总有f ( x ) f ( x ) h f f c o ，则称，为约束问 题的严格全局极小值( 严格全局解) 。 定义1 3 如果，d ，且存在= ( 彳，z ，鬈) r ”满足 夥( ，) = g v c , c ) ，彳o ( i e l ) ( 1 - 3 1 ) 百 g c , f ) = o ( f e u l ) ( 卜3 - 2 ) 则称，是问题( 卜1 ) 的k a r u s h k u h n t u c k e r 点( 或k k t 点) ，条件( 1 3 ) 称为 2 第一章绪论 问题( 卜1 ) 的k k t 条件。通常条件( 卜3 - 2 ) 被称为互补性条件。如果对于所有 的f e e u l ，石与c j ( ，) 不同时为零，那么称问题( 卜1 ) 在，处是严格互补的。 定理1 1 ( 约束问题局部解的一阶必要条件”) 设约束最优化问题( 1 - 1 ) 中f ( x ) 和c ( x ) 具有连续的一阶偏导数，若f 是约束问题( 1 - 1 ) 的局部解，则存 在常数彳，( f = 1 , 2 ，研) ，使得k k t 条件( 1 - 3 ) 成立。 定理1 2 ( 约束问题局部解的二阶充分条件“1 ) 设约束最优化问题( 1 - 1 ) 中的，( 和c ( x ) 具有连续的二阶偏导数，若存在f 和五满足： ( 1 ) 在f 处一阶必要条件( 1 - 3 ) 成立，且条件( 1 - 3 2 ) 是严格互补的； ( 2 ) 对于v s m ，有 ，v ：三( ，a 弦 0 成立。 其中m = 妇ls t v c , ( x ) = o ，i e e u j ( ，) ) ，j ( ，) = f i c ( x ) = o ，i e ， ，贝l j x 是问题 ( 1 - 1 ) 的严格局部解。 1 2 3 w o i f e 对偶问题 定义1 4 对于凸规划( 卜1 ) ，如果f ( x ) 和c ，( x ) ，f 1 分别是包含容许集s 的 开凸集d 上的一阶可微凸函数和凹函数，称 m a xl ( x ，a ) 趾j v l ( x ，五) 2 0 ( 1 - 4 ) i 五0 ，( f j ) 为凸规划( 卜1 ) 的w o l f e 对偶问题。其中l ( x ，a ) 为l a g r a n g i a n 函数，即 l ( x ，兄) = ，( x ) + 五1 c ( 功 ( 1 5 ) 定理1 3 ( w o l f e 对偶定理川”) 在包含容许集s 的开凸集d 上，设f ( x ) 和 c ：o ) ，f ，分别为可微凸函数和凹函数，o ，) 为凸规划( 卜1 ) 的一个k k t 对， 则0 ，z ) t g g _ o l f e 对偶问题( 卜4 ) 的最优解。 1 3 机器学习问题及方法 机器学习是现代智能技术中的重要研究领域之一。该研究是从观测数据( 样 本) 出发根据特定的规则进行实验过程设计、结果分析，这一阶段通常称为训练 过程，最终目的是希望能够找到一个可靠的结果。进一步地，如果能够使用数学 模型来刻画实验结果，那么就可以应用该模型对未来数据或无法观测的数据进行 预测，这就是所谓的判别过程。迄今为止，关于机器学习还没有一个被广泛接受 的理论框架，其实现方法大致可以分为以下三种”1 ： 3 第一章绪论 第一种是统计模式识别。使用统计学的基本原理与方法来解决模式识别中的 问题。具体的可以分为两大类“”：( 1 ) 基于模型的方法，如贝叶斯决策、概率密 度参数和非参数估计“”1 等。该类方法是采用先验的类条件概率密度函数( 给定 类别的特征向量的概率密度函数) 进行识别。在实际应用中类条件概率密度函数 是无法准确地知道，只能由采集到的样本，并结合统计学的方法( 参数和非参数 估计) 来估计。( 2 ) 基于决策规则的方法，该类方法直接使用样本来估计决策边 界，而不需要计算类的条件概率密度，如线性判别“”( f i s h e r 线性判别和感知 器等) 、非线性判别旧( 核函数法和神经网络) 以及近邻法“1 等。 第二种方法是经验非线性方法，如人工神经网络( a n n ) “。这种方法利用 训练样本建立所要研究系统的非线性模型，克服了传统参数估计方法依赖于屯验 知识及模型假设的缺陷。 统计模式识别中的参数估计方法是基于传统统计学理论，该方法的前提是假 定模型形式已知，但参数未知，使用训练样本来估计参数的值，从而确定模型。 这种方法有很大的局限性，首先它需要已知样本分布函数形式，这将需要花费很 大代价；其次传统统计学研究的是样本数量趋于无穷大时的渐近理论( 目前大多 数学习方法是基于此假设) ，但是在实际中，样本数量是有限的。因此，一些在 理论上很优秀的方法在实际中的表现却可能不尽如人意。 同样，神经网络方法也存在不足，缺乏严密的理论体系指导，其应用效果往 往取决于使用者的经验。为了克服神经网络结构不易确定、过学习及泛化能力差 等缺点，1 9 9 0 年，h a n d s e n 等人“2 1 开创性地提出神经网络集成( n e u r a ln e t w o r k e n s e m b l e ) 方法，并证明了通过训练多少神经网络并将其进行合成，从而可以显 著地提高神经网络的泛化能力。 由于上面两类方法存在着不足，促使人们发展出一套比较完备的理论体系来 解决上述问题，这就是下节将要介绍的第三类机器学习方法一统计学习理论 【i 胡【h 儿1 5 】 o 学习问题的一般模型可以用图卜1 表示，其中包括三个组成部分“： ( 1 ) 数据( 样本) 发生器g 。 ( 2 ) 目标算子s ( 有时也称为训练器算子或训练器) ，是需要研究的对象， 在给定输入x 时，它可以得到相应输出y 。 ( 3 ) 学习机器( l e a r n i n gm a c h i n e 或l m ) 。机器学习就是要根据训练样本 估计出系统输入输出之间的函数关系，并尽可能准确地预测未知的输出。 4 第一章绪论 图1 - 1 机器学习基本模型 发生器g 是源头，用来确定训练器和学习机器的工作环境。这里研究的是最 简单的环境：g 依据某一未知的( 固定的) 分布函数f ( 石) 随机产生输入向量工。 由发生器g 产生的向量x 输入到训练器s ，并返回输出值y 。将茸向量变换 成y 的训练器算子是未知的，但它是存在且不变的。 学习机器观测到m 个点对( 训练样本集) ： ( x ，y 。) 卫1 它包含输入向量x 和训练器响应y 。训练阶段，学习机器使用这些点对构造某一 算子，用来预测由发生器g 产生的某一向量薯对应的训练器响应片。 学习机器的目标是构造一个对训练器算子的逼近。为了构造这个逼近，可以 选择下面两个目标之一n ”： ( 1 ) 模仿训练器的算子：对于某特定的发生器g ，构造一个对训练器输出 提供最佳预测的算子。 ( 2 ) 辨识训练器算子：构造一个非常接近于训练器算子的算子。 这两个目标存在本质区别：第一个目标是在确定的发生器条件下，追求对训 练器输出预测的最佳效果；第二个目标不仅要求具有良好的预测效果，而且使得 构造的算子在给定的测度条件下非常接近于训练器算子。这两个目标预示着处理 学习问题的两种不同方法。在实际中模仿训练器算子方法是可行的和有效的，而 训练器辨识方法实质上是一个不适定问题“，可行性较低。 1 4 统计学习理论 与传统统计学理论相比，统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y 或 s l t ) 是一种专门研究小样本条件下机器学习规律的理论。该理论是针对小样本 统计问题建立起的一套新型理论体系，在该体系下的统计推理规则不仅考虑了对 渐近性能的要求，而且追求在有限信息条件下得到最优结果。v a p n i k 等人从上 世纪六、七十年代开始致力于该领域研究，直到九十年代中期，有限样本条件下 的机器学习理论才逐渐成熟起来，形成了比较完善的理论体系统计学习理 论。 5 第一章绪论 统计学习理论的一个核心概念是v c 维( d i m e n s i o n ) ，它是描述函数集或学 习机器的复杂性或者说学习能力( c a p a c i t yo ft h em a c h i n e ) 的一个重要指标。 在此概念基础上发展出了一系列关于统计学习的一致性( c o n s i s t e n c y ) 、收敛速 度及推广性能( g e n e r a l i z a t i o np e r f o r m a n c e ) 等的重要结论。 接下来，首先介绍一些相关的基本概念与结论嘲n ”： 定义1 5 依概率收敛( c o n v e r g e n c ei np r o b a b i l i t y ) 考虑随机变量序列 玩) 。当且仅当垤 o ，概率关系p ( 1 矗一而p 占) 斗o ( 当疗哼) 成立。那么随 机变量序列魄) 依概率收敛于随机变lx o 。 定义1 6 训练样本( t r a i n i n gs a m p l e ) 点对( x ，力服从形式未知的联合概 率分布f “力，其中x 为输入，y 为输出。集合s = = ( ，弗) ) ：包含所个独立 同分布的点对，则称该集合为训练样本集，每个点对即为训练样本。 定义1 7 损失函数( l o s sf u n c t i o n ) 已知输入工、预测值“妨和真实 输出值y 。用t ( x ，f ，功) 表示预测损失函数，其通常是有界的。典型的有均方 损失函数l ( y ，) = ( y f ( x ，硼2 。 定义1 8 期望误差( e x p e c t e de r r o r ) 假定训练样本集s ，且样本的概率 分布函数为f ( x ，力。根据贝叶斯决策理论，预测函数f ( x ，功的期望误差可以定 义为： r = l 三0 ，f ( x , e o ) ) d f ( x ，力 ( 1 6 ) 当使用均方损失函数时，则有， 胄u ) = i o , - f ( x ，) ) 2 d f ( x ，y ) ( 卜7 ) 其目标是要寻找使泛函尺最小化的函数八五) 。 定义1 9 经验误差( e m p i r i c a le r r o r ) 与期望误差的定义1 8 类似，在 训练样本集s 上，定义经验误差为： 1 墨。( 力- - x l ( y , ，( ，功) ( 卜8 ) i = i 最小化经验误差t 。( d 得到函数，( ) 。由于样本的概率分布f 力未知，所 以无法最小化期望误差，通常使用最小化经验误差来替代。 定义1 1 0 经验风险最小化原则根据定义1 8 与1 9 ，如果使用使经验误差 j 。( 厂) 最小化的函数f ( x , c a = ) 逼近使期望误差冗最小化的函数f ( x , c a o ) ，这一 原则被称为经验风险最小化( e m p i r i c a lr i s km i n i m i z a t i o n 或e r m ) 原则。 定义1 - 1 1 一致性( c o n s i s t e n c y ) 对于函数集 ，( x ，奶，国a ) 以及概率分 布函数f ( x ，力，如果下面两个序列依概率收敛于同一极限， r ( q ) 差：- i n fr ( ) k ( q ) 专- i n f r ( o ) 6 第一章绪论 则称e r g 原则是一致的。 也就是说，如果e r m 原则能够提供一个函数序列f ( x ，) ，a ，使期望误 差和经验误差均依概率收敛于( 对于给定的函数集) 最小的可能风险值，则e r m 原则是一致的。如图1 - 2 所示： i n f r ( 图卜2e r m 原则下的一致收敛原理图 定义1 1 2p 维( v a p n i k - c h e r v o n e n k i sd i m e n s i o n ) v c 维是对由学习机 器实现的分类函数族的容量或表示能力的测度。 直观定义“”如下：假定存在一个有h 个样本的集合能够被一个函数集中的函 数按照所有可能的2 6 种形式分为两类，则称函数集能够把数量为h 的样本集打散 ( s h a t t e r i n g ) 。指示函数集的v c 维等于使用这个函数集中的函数能够打散的最 大样本数目。也就是说，如果存在样本数为h 的集合能够被函数集打散，且不存 在大于h 的样本集被函数集打散，则该函数集的v c 维为h 。若对于任意的样本 数，总能找到一个样本集能够被某函数集打散，则该函数集的v c 维无穷大。 由定义1 1 1 容易看出在二维平面中，直线集的v c 维数为3 ，如图1 - 3 所示。 更一般地，在昨维欧氏空间中超平面集的v c 维是雄+ l 。 弋，么 。 夕， 五xxx 。z 弋。 图1 - 3 二维平面上直线集的v c 维 定义1 1 2 结构风险最小化原则s l t 系统地研究了在各种类型函数集中， 经验误差与实际误差之间的一致收敛速度问题，即推广性的界。关于模式识别的 7 第一章绪论 结论：对于指示函数集中的任意函数而言，经验误差与实际误差之间至少以概率 l 一口满足关系： 胄( 曲f t 。( m ) + 岛( ，厅，1 2 ) ( 1 1 0 ) 其中表示样本数，| l l 为该指示函数集的比7 维，毛( ，h ，口) 为置信范围。该结 论从理论上描述了学习机器的实际风险组成包括经验误差和置信范围( 与学习机 器的复杂度和样本数有关) ；并且说明了在有限训练样本条件下，学习机器的v c 维越高则置信范围越大，导致期望风险与经验风险之间误差就越大。机器学习过 程不仅需要使经验误差最小，还要使v c 维尽量小，即减小置信范围，则称之为 结构风险最小化( s t r u c t u r a lr i s km i n i m i z a t i o n 或s 剐) 原则”“”。 统计学习理论是建立在一套较为坚实的理论基础之上，为解决有限样本学习 问题提供了统一的框架。它能将很多现有方法纳入其中，有望解决许多原来难以 解决的问题( 如统计方法的模型依赖性强和神经网络结构选择、推广能力较弱 等) 。另外，1 9 9 2 - - 1 9 9 5 年期间，在统计学习理论基础上发展出了一种新的机器 学习方法一支持向量机( s u p p o r t v e c t o rm a c h i n e 或s v m ) ，在解决小样本、 非线性及高维模式识别问题时表现出许多良好的特性，并能够推广到密度函数估 计和回归分析等其它问题领域中。虽然s l t 和s v m 尚有许多问题需要进一步研究， 但很多学者认为，它们正成为继模式识别与神经网络之后机器学习领域的另研 究热点，并将推动机器学习理论与技术的快速发展。 目前，国际上对这一理论的讨论和研究比较广泛，而国内的研究才刚起步。 因此需要及时学习并掌握有关理论，开展有效的研究工作，使我们在这一有着重 要意义的领域中能够尽快赶上国际先进水平。由于s l t 和s v m 尚处在发展阶段， 很多方面尚不完善，例如许多理论目前还只有理论上的意义，尚不能在实际算法 中实现；s v m 如何根据具体问题选择适当的内积核函数也没有明确的理论依据。 因此，可做的研究工作还是很多的。 1 5 支持向量机 1 5 1s v m 基本原理 早在二十世纪七十年代，v a p n i k 等人就已经建立了s l t 的基础体系，该理 论系统地研究了机器学习问题，尤其是在有限样本条件下的统计学习问题。但由 于当时这些理论尚不完善，在解决模式识别问题时往往趋于保守，且数学上比较 晦涩，并未得到足够重视。直到九十年代中期，s v m 的产生并表现出了良好的性 能后，才逐渐地引起人们广泛关注，并成为一个研究热点。 8 第一章绪论 支持向量机是建立在s l t 和s 蹦基础上，根据有限的样本数据在模型复杂性 ( 即对训练样本的学习精度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本 的能力) 之间寻求折衷，以期获得最好的推广能力( g e n e r a l i z a t i o na b i l i t y ) s v m 具有以下几个显著特点： ( 1 ) 是专门处理有限样本条件下的机器学习问题，其目标是得到在现有信 息下的最优解而不仅仅是样本数量趋于无穷大的最优值。 ( 2 ) 算法最终转化成为一个二次规划问题，从理论上来说，得到的是全局 最优解，克服了神经网络方法难以避免的局部极值问题。 ( 3 ) 使用非线性函数将问题从输入空间( i n p u ts p a c e ) 映射到特征空间 ( f e a t u r es p a c e ) ，在特征空间中构造线性函数来实现输入空问中的非线性关 系，同时巧妙地解决了维数问题，使得算法复杂度与样本维数无关。 ( 4 ) 基于结构风险最小化原则，利用大间隔的思想降低分类器的比维，从 而提高模型的推广能力。 ( 5 ) 简洁性，即模型仅由支持向量集完全确定，从而提高了判别阶段的执 行效率。 支持向量机训练得到的判别函数在形式上类似于前馈神经网络，其输出是若 干中间层节点的线性组合，而每个中间层节点对应于输入样本和某个支持向量的 内积运算，所以通常也被称为支持向量机网络。 内积运算通常使用满足m e r c e r 定理”1 的内积核函数实现隐式定义。只要定 义不同的内积核函数，即可以实现诸如多项式逼近、贝叶斯分类器、径向基函数 ( r a d i a lb a s i cf u n c t i o n 或r b f ) 以及多层感知器网络等许多现有算法。 1 5 2s v m 与神经网络的关系 神经网络是建立在经验风险最小化原则基础上，被广泛地用来处理非线性高 维回归估计问题。其具有以下两个特点：( 1 ) 大规模并行分布式结构；( 2 ) 神经 网络学习能力以及由此而来的泛化能力。但是在实际中，神经网络不能单独做出 解答，需要被整合在一个协调一致的系统工程方法中。具体地说，一个复杂问题 往往被分解成若干相对简单的子任务，而神经网络只是用来处理与其能力相符的 子任务。一般说来，从网络结构上可以将神经网络分为以下三种：( 1 ) 单层前馈 网络；( 2 ) 多层前馈网络；( 3 ) 递归网络。 研究表明：在训练阶段完成后，得到的支持向量集可以构成一个包含单隐含 层的前馈网络。虽然在结构上s v m 与神经网络中的前馈网络极为相似，但是在原 则、收敛速度以及泛化能力等方面还是存在比较大的差异，如表卜1 所示： 9 第一章绪论 表i - 1s w 与前馈神经网络的比较 原则结构收敛速率泛化能力 前馈神经网络 经验风险最小化确定快弱 支持向量机结构风险最小化不确定慢强 a 指在训练阶段之前的网络结构。 1 5 3s v m 研究进展 由于s v i i 具有良好特性，所以逐渐地被许多学者和研究机构关注。除了较早 开展研究工作的贝尔实验室、柏林工业大学以外，其他一些著名的科研机构也纷 纷加入到研究队伍中来，如微软研究中心、麻省理工学院人工智能实验室等。另 外，还有许多学者在各个领域内围绕着s v m 从理论、算法到应用进行了大量的研 究工作，这将极大地促进了s v m 的发展并走向成熟。 1 5 3 1s v m 理论研究 统计学习理论从产生到现在还不足五十年，理论体系仍然有值得研究和完善 的地方。在其基础上发展出来的s v m 更是一项崭新的机器学习方法，无论在理论， 还是在应用上面都有很多地方值得我们去研究与探索。目前国内外许多的研究机 构与学者对s v m 所涉及的理论知识进行了广泛的研究，包括有以下几个方面的内 容： ( 1 ) 统计学习理论 通过前面内容我们简要地了解了s l t 研究的基本内容与方法，以及s w 这种 重要的机器学习方法。但是，该理论体系中仍然存在着有待于研究的地方，例如 v c 维虽是核心概念，但至今没有一个通用的分析方法来处理实际问题；有关s w l 的某些理论解释也并非严谨( b u r g e s “”提出s r m 原则并不能严格证明s v m 具有良 好的泛化能力) 等。 ( 2 ) 核空间理论 借助于核空间理论s v m 可以用来处理非线性问题。但是就目前来讲核函数的 选择比较局限，常用的有多项式、高斯及s i g m o i d 函数等，而且还缺少有效的方 法指导如何进行选择。文献 1 8 研究表明多项式函数为全局核函数，高斯函数为 局部核函数，它们均存在着应用方面的不足，同时还研究了核函数构造与应用等 问题。随着再生核空间理论研究的日益完善，如何将其应用于s 也是值得研究 的问题。 ( 3 ) 正则化理论 正则化理论最早由t i k h o n o v 于二十世纪六十年代创立的，经过不断地研究 与发展逐渐成为完善的理论准则。其基本思想是通过某些含有解的先验知识的非 1 0 第一章绪论 负辅助泛函来使解稳定“。先验知识的一般形式是用一个光滑的曲线来逼近输入 输出映射函数。在形式上，正则化理论等价于求解如下所示的优化问题： 2 r a i n r = + 詈l l o f j f ( 卜1 1 ) 二 其中正则化参数五 0 ，定义在某个适当的函数空间中，u ) 是经验风险泛 函，线性微分算子d 包含了先验知识，它可以使解光滑从而满足连续性要求。文 献 1 9 研究表明正则化理论的思想蕴含于支持向量机中，另外 1 9 和 2 0 还研究 了借助于正则化理论与s v m 相统一的结论来指导s v m 中某些参数选择问题。 ( 4 ) 贝叶斯理论 贝叶斯理论0 1 是两大统计理论之一，其根据先验知识对类的条件概率分布进 行修正得到后验概率，由此进行统计推断。由此可见，在综合了先验知识和样本 信息后，得到的后验概率是贝叶斯统计推断的基础。近来，有研究。”提出了在贝 叶斯理论框架下的s v m ，其将贝叶斯推断分为三个准则，分别用来挑选参数m 、 正则化参数c 及核参数，从而得到最优模型。 支持向量机在解决模式识别、回归函数估计和密度函数估计等机器学习中获 得了比较好的应用。但是，目前s v m 存在着一大缺陷是训练时问较长。当处理规 模较大的问题时，目前的s v m 训练算法速度均比较慢。所以在s v m 研究中，如何 提高训练效率，仍然是一个亟待解决难题。 在s v m 训练过程中，需要求解一个大规模的条件约束二次规划。它的运算量 非常大且对系统内存要求与训练样本数量的平方成正比，所以是一项非常富有挑 战性的工作。目前，国内外已有许多学者提出了多种分解算法来优化此类大规模 二次规划的求解，其中包括： ( 1 ) 分块( c h u n k i n g ) 算法 c h u n k i n g 算法是由v a p n i k 首先提出的种快速训练算法。具体来说，首先， 从训练样本中任意选择一个小的子集，训练模型并提取支持向量集加以保留。其 次，在剩余的样本中启发式地选择新的子集，并加入到当前保留的支持向量集中， 组成新的训练样本集进行训练，反复迭代上面过程直到所有样本满足k k t 收敛条 件为止。 另外，增量学习算法也属于c h u n k i n g 算法。g c a u w e n b e r g h s 乜2 1 等人提出了 增量与减量支持向量机学习算法，即增加或减少一个样本对s v m 模型的影响以及 有效地对l e a v e - o n e - o u t 技术的泛化能力评价。p m i t r a 。”提出错误驱动技术来 实现增量学习，即使用当前s v m 模型逐个对增量样本进行识别，将所有判断错误 的增量样本与当前支持向量集组成训练样本集，重新训练s v m 模型，如此重复。 k s u n g ”采用固定划分技术实现增量学习。l r a l a i v o l 。”、c d o m e n i c o n i ”1 、 s r u p i n 9 0 7 3 等学者也分别提出了一些其它的增量学习算法。 1 1 第一章绪论 当支持向量的数量比较小时，c h u n k i n g 算法能够很有效地提高训练效率。 但是当支持向量很多时，训练