（运筹学与控制论专业论文）支持向量机和分类问题的算法研究.pdf

摘要 支持向量机学习算法是本文的主要研究工作，它是建立在统计学习理论和数学规划 基础上的一种数据挖掘的新方法。数学规划是运筹学一个重要分支，在机器学习、网络 问题、博弈理论与经济学、工程机械学等领域有着广泛丽重要的应用，是国际上最活跃 的运筹学研究领域之一分类是机器学习的常见问题之一。本文在近似支持向量机数学 模型，近似错误分离最小化模型和推导多类支持向量机对偶性理论这三方面作者分别有 所研究，取得的结果如下： 第2 章给出了支持向量机的个近似算法一乘子极大熵算法。此算法把支持向量机 对偶模型化为极大极小模型，然后再用乘子极大熵法来解决这个问题。这是一个集极大 熵法和乘子法两者优点于一身的算法，极大熵法把非光滑的问题变成了光滑的，乘子法 能在一定程度上减少迭代次数，并且可以避免海森阵病态的问题。支持向量机的乘子极 大熵算法对于小样本问题，特别是医学上癌前诊断问题有比较好的实验结果，文中的两 个例子表明该算法能较好的解决小样本的学习分类问题。 第3 章是关于错误分离最小化的一个近似算法的。错误分离最小化是机器学习中很 常见的问题之一，本文给出了分离错误最小化数学模型的一个近似模型在分离错误点 个数最小的数学模型中，用分片线性函数来近似步函数，从而给出了一个近似模型对 于近似模型，本文做了一个序列线性化算法，并且证明了算法是有限步终止的 以往关于多类支持向量机及其对偶问题的文献在理论方面给出的结论不多。本文在 二类支持向量机对偶理论的基础上，针对多分类支持向量机的数学模型，给出原始问题 解的性质定理以及原始问题和对偶问题解的关系定理，并进行了严格的理论证明这一 章给多分类支持向量机某些算法的设计提供了理论根据 关键词：支持向量机；乘子极大熵；w o l f e - 对偶；k k t 条件；多类支持向量机；对 偶问题 s t u d i e so fo p t i m i m a la l g o r i t h m so fs u p p o r tv e c t o rm a c h i n e sa n d c l a s s i f i c a t i o nq u e s t i o n s a b s t r a c t t h i sd i s s e r t a t i o ni sm a i u l ya b o u tl e a r m n ga l g o r i t h m so fs u p p o r tv e c t o rm a c h i n e s ， w h i c hi san e wa p p r o a c ho fd a t am i n i n gb a s e do nt h es t a t i s t i c a ll e a r n i n gt h e o r ya n d m a t h e m a t i c a lp r o g r a m m i n g m a t h e m a t i c a lp r o g r a m m i n gi sa ni m p o r t a n tb r a n c ho fo p - e r a t i o n a lr e s e a r c h i th a sb e e ne x t e n s i v e l ya p p f i e dt oa r e a so fm a c h i n el e a r n i n g ，n e t w o r k s p r o b l e m ，g a m et h e o r y , e c o n o m i c s ，m e c h a n i c sa n d i ti so n eo ft h em o s ta d v a n c e da r e a so f o p e r a t i o n a lr e s e a r c h i na d d i t i o n ，c l a s s i f i c a t i o nq u e s t i o n ，o i l eo ft h ec o m m o nq u e s t i o n si n m a c h i n e sl e a r n i n g ，i sa l s oi n c l u d e di nt h ep a p e r i na p p r o x i m a t i n gm a t h e m a t i c a lm o d eo f s u p p o r tv e c t o rm a c h i n e sa n dm i s c l a s s i f i c a t i o nm i n i m i z a t i o n ，a n dp r o p o s i n gt h ed u a lt h e - o r i e so fm u l t i - c l a , 口s u p p o r tv e c t o rm a c h i n e s ，s o m ec o n c l u s i o n sa 3 ：eo b t a i n e dr e s p e c t i v e l y a sf o l l o w s ： i nc h a p t e r2 ，ap r o x i m a la l g o r i t h mc a l l e dt h em u l t i p l i e re n t r o ya l g o r i t h mo fs u p p o r t v e c t o rm a c h i n e si sc o n s t r u c t e d ，w h i c hi sam e t h o db yt r a n s f o r m i n gt h em a t h e m a t i c a lm o d e o fs u p p o r tv e c t o rm a c h i n e si n t or a i n - m a xp r o b l e ma n ds o l v i n gt h er a i n - m a xp r o b l e mu s i n g t h em u l t i p l i e re n t r o ya l g o r i t h m i th a st h ev i r t u e so fb o t hm a l t i p l i e ra l g o r i t h ma n de n t r o y a l g o r i t h m e n t r o ya l g o r i t h mc a nt u r nn o n s m o o t hp r o b l e m si n t os m o o t h ，a n dm u l t i p l i e r a l g o r i t h m c a nr e d u c et h ei t e r a t i o ni ns o m ed e g r e ea n dt h em o r b i ds t a t eo fh e s s i a nc a nb e a v o i d e d f o rs m a l ls a m p l ep r o b l e m s ，e s p e c i a l l yt h ep r e - c a n c e rd i a g n o s i s ，t h ea l g o r i t h m c a nb ep e r f o r m e de f f i c i e n t l y t h et w on m n e r i c a le x p e r i m e n t si l l u s t r a t et h a tt h em u l t i p l i e r e n t r o ya l g o r i t h mi se f f e c t i v e c h a p t e r3i sa b o u ta na p p r o x i m a la l g o r i t h mf o rm i s c l a s s i f i c a t i o nm i n i m i z a t i o n ，w h i c h i so n eo ft h ec o m m o np r o b l e m si nm a c h i n el e a r n i n g i nt h i sc h a p t e ran e wp r o x i m a lm o d e o fm i s c l a s s i f i c a t i o nm i n i m i z a t i o ni sp r o p o s e d ，w h e r ep i e c e - w i s el i n e a rf u n c t i o ni su s e dt o a p p r o x i m a t es t e pf u n c t i o n as e q u e n c el i n e a ra l g o r i t h mi sc o n s t r u c t e df o rs o l v i n gt h en e w m o d e la n da l s oi ti sp r o v e dt ot e r m i n a t eb yf i n i t ei t e r a t i o n t h e r ea r ef e wp a p e r ss t u d y i n gt h ed u a l i t yt h e o r yo fm u l t i - c l a s ss u p p o r tv e c t o rm a - c h i n e s i nt h i sc h a p t e r ，t h ep r o p e r t yo ft h es o l u t i o no ft h ep r i m ep r o b l e ma n dt h ed u a l i t y t h e o r e mo ft h em o d eo fm u l t i - c l a s ss u p p o r tv e c t o rm a c h i n e sa r ep r e s e n t e d a l s ot h es t r i c t p r o o fo ft h e s et h e o r i e sa r eg i v e n t h er e s u l t sg i v e ni nt h i sc h a p t e rp r o v i d et h ec r e d i b l e t h e o r yf o rd e s i g n i n ga l g o r i t h mo fm u l t i - c l a s ss u p p o r tv e c t o rm a c h i n e s k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e s ；m u l t i p l i e re n t r o p ；w o l f e - d u a l ；k k t c o n d i t i o n ；m u l t i - c l a s ss u p p o r tv e c t o rm a c h i n e s ；d u a lp r o b l e m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：日期： 支持向量机和分类问题的算法研究 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定。，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 保密口，在年解密后适用本授权书 本学位论文属于 不保密口 ( 请在以上方框内打”) 作者签名； 指导教师签名：拯 1 支持向量机和分类问题简介 支持向量机学习方法研究【1 】是本文的主要工作，它是数据挖掘在统计学习理论和优 化理论的基础上解决问题的一种新的方法，主要解决数据挖掘中的分类问题在此，我 们先简要介绍一下数据挖掘，统计学习理论以及分类的有关知识，以便读者对这几方面 有个了解。然后对用优化理论做支持向量机的知识背景以及模型的导出给出比较详细的 阐述 1 1 数据挖掘技术以及统计学习理论 对大型的、复杂的、信息丰富的数据集的理解实际上所有的商业、科学、工程领域 的共同需要，在商务领域，公司和顾客的数据逐渐被认为是一种战略资产在当今的竞 争世界中，吸取隐藏在这些数据后面的有用知识并利用这些知识的能力变的愈加重要 运用基于计算机的方法，包括新技术，从而在数据库中获得有用知识的整个过程，就是 数据挖掘( d a t am i a i n g ) 它是个反复迭代的过程，在这个过程中，所取得的进步用 “发现”来定义，而这种发现是通过自动和手工方法取得的。它从大量的原始数据搜寻 有价值的、非同寻常的新信息，是人和计算机合力的结果原始数据可以是结构化的，如 关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在 网络上的异构型数据发现知识的方法可以是数学的，也可以是非数学的；可以是演绎 的，也可以是归纳的发现了的知识可以被用于信息管理、查询优化、决策支持、过程控 制等，还可以用于数据库自身的维护因此，数据挖掘是一门广义的交叉学科，它汇聚了 不同领域的研究者，尤其是数据库、人工智能、数理统计、数学规划、可视化、并行计算 等方面的学者和工程技术人员。我们主要关注数据挖掘的数学规划，特别是优化方法。 当前，许多领域大量不同的问题可以作为数学规划问题被公式化并有效地得到解决，例 如，运筹研究1 2 , 3 、神经冈络问题e 4 , 5 , 6 】、博弈理论与经济学f7 8 j 、工程机械学1 9 , 1 。】。1 8 世纪伟大的数学家e u l e l 说：“任何宇宙中发生的事件都包含某种极大或极小”通过数 学规划解决数据挖掘问题成为近几年来新兴的研究领域 u - a s 。本文主要以统计学习理 论为基础，以数学规划为手段，对数据挖掘中的支持向量机方法和错误分离最小化分析 方法进行研究 1 支持向量机和分类问题的算法研究 1 1 2 统计学习理论简介 统计学习理论就是研究小样本估计和预测的理论 1 6 , 1 7 j ，最具有指导性的结果是推 广的界，与此相关的一个核心概念是v c 维。 学习系统的容量对其泛化能力有重要影响 1 8 - 2 0 。低容量学习系统只需要较小的训 练集，高容量学习系统则需要较大的训练集，但其所获的解将优于前者对给定训练集 来说，高容量学习系统的训练集误差和测试集误差之间的差别将大于低容量学习系统。 v a p n i k 指出，对学习系统来说，训练集误差与测试集误差之间的差别是训练集规模的函 数，该函数可以由学习系统的v c 维表征。换言之，v c 维表征了学习系统的容量。大 连理工大学硕士学位论文a n t h o n y l 2 1 将v c 维定义为：设f 为一个从礼维向量集x 到 o ，1 ) 的函数族，则f 的v c 维为x 的子集e 的最大元素数其中e 满足：对于任意 s 三e ，总存在函数五f ，使得当o s 时丘( z ) = 1 芦隹s 但。e 时五( o ) = 0 v c 维可作为函数族f 复杂度的度量，它是一个自然数，其值有可能为无穷大，它 表示无论以何种组合方式出现均可被函数族f 正确划分为两类的向量个数的最大值。对 于实函数族，可定义相应的指示函数族，该指示函数族的v c 维即为原实函数族的v c 维 为便于讨论，我们针对典型的二元模式识别问题进行分析。设给定训练集为 ( 。1 ，y 1 ) ，( z 2 ，驰) ，( x l ，肌) ，其中甄舻，y o ，1 ) 显然，z i 是一个礼维输入 向量，y 为二值期望输出。再假设训练样本与测试样本均满足样本空间的实际概率分布 p ( x ，) 对基于统计的学习方法来说，学习系统可以由一族二值函数 ，( z ，。) ，口a ) 表征， 其中参数c l 可以唯一确定函数，( ) ，a 为8 所有可能的取值集合。因此， ，( z ，a ) ，a 埘 的v c 维也表征了该学习系统的复杂度，即学习系统的最大学习能力，我们称其为该学习 系统的v c 维。学习的目的就是通过选择一个参数n ，使得学习系统的输出，x ，0 f + ) 与期 望输出y 之间的误差概率最小化，即出错率最小化。出错率也称为期望风险( e x p e c t e d 碰s k ) ，如下式所示： 冗( a ) = 互1 i f 一， ，口) l d p ( 以! ，) ( 1 1 ，1 ) 其中p ( x ，y ) 为样本空间的实际概率分布。由于p ( x ，y ) 通常是未知的，因此无法直接计 算r ( o ) ，但是，对给定的训练集，其经验风险( e m p i r i c a lr i s k ) 忍m p 妇) 却是确定的， 如下式所示： 见m p ( 。) ：刍圭陆一m 翘) f ( 1 1 2 ) 其中( x i ，y i ) 为训练样本，l 为训练集中样本数，即训练集规模由数理统计中的大 数定理可知。随着训练集规模的扩大，忍。( o ) 将逐渐收敛于冗( 凸) 2 大连理工大学硬士学位论文 另一个比较重要的概念就是推广的界 基于统计的学习方法大多建立在经验风险最小化原则( p r i n c i p l eo fe m p i r i c a lr i s k m i n i m i z a t i o n ) 基础上，其思想就是利用经验风险r 。( 口) 来代替期望风险r ( a ) ，用 使风。，( a ) 最小的，( z ，锄) 来近似使r ( a ) 最小的，( 。，o l 0 ) 。这类方法有一个非常基本 的假设，即如果风。( 口) 收敛于五( a ) ，那么忍m p ( 。) 的最小值将收敛于r ( d ) 的最小 值v a p n i k 与c h e r v o n e n l d s 2 q 证明，该假设成立的充要条件是函数族 ，( 。，a ) ，a a ) 的v c 维为有限值 v a p n i k 还证明，期望风险r ( q ) 满足一个上界，即任取叩满足0 7 1 ，下列边 界以概率1 一聍成立： r ( o ) 见p ( a ) +( 1 1 3 ) 其中h 为函数族 ，( z ，a ) ，o 埘的v c 维，f 为训练集规模 这一结论从理论上说明了学习机器的实际风险是有两步分组成的：一是经验风险( 训 练误差) ，另一部分是置信范围，它和学习机器的v c 维及训练样本数有关，可以简单的 表示为 r ( q ) 忍( o ) + 垂( 二)( 1 1 4 ) 刁 它表明在学习系统v c 维与训练集规模的比值很大时，即使经验风险兄。，( 口) 较小，也 无法保证期望风险r ( o ) 较小，即无法保证学习系统具有较好的泛化能力。因此，要获得 一个泛化性能较好的学习系统，就需要在学习系统的v c 维与训练集规模之间达成一定 的均衡 需要指出的，推广的界是对于最坏情况的结论，在很多情况下是较松的，尤其是当 v c 维较高时更是如此而且，这种界只在对同一类学习函数比较时有效，可以指导我们 从函数集中选择最优函数，在不同的函数集之间比较不一定成立。 神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，其组织能够模拟 生物神经系统对真实世界所作出的交互反应【2 3 】基于神经网络建立计算模型，并用于解 决科学和工程中的问题就称为神经计算。该领域最早的研究可上溯到m c c u l l o c h 和p i t t s 提出的m - p 模型劁在h e b b 提出了h e b b 学习规则【2 5 1 、r o s e n b l a t t1 2 8 研制出感知 机( p e r c e p t r o n ) 之后，神经计算受到了极大的重视，吸引了大批研究人员参与该领域的 研究工作，并取得了一定的进展。但是，由于1 9 6 9 年m i n s k y 和p a p e r t 2 7 指出感知机的 缺陷并表示出对该方面研究的悲观态度，同时，以产生式规则为内部表示的专家系统方 法展示出灿烂的前景，很长时间内神经计算的研究处于停滞状态。在此期间，为专家系统 服务的知识工程成为了人工智能研究的主流。但是，随着知识工程的发展，f e i g e n b a u m 等【2 8 】知识工程倡导者意识到了所谓知识瓶颈问题，即将人类专家的知识转化为机器可 执行的规则存在着很大的困难，而如果机器能够自学习，则可望解决该瓶颈问题于是， 机器学习研究得到了迅猛的发展嗍。 3 支持向量机和分类问题的算法研究 在研究中，研究者们1 3 0 , a 1 发现，与机械学习、类比学习等学习方式相比，示例学习 是解决知识瓶颈问题唯一可行的方法。1 9 8 2 年，h o p f i e l d 利用全互连型神经网络和计算 能量函数成功求解了计算复杂度为n p 完全型的t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 问题。这充分展示了神经计算作为一种数值型示例学习方法蕴含的巨大潜力。从此，神经 计算成为了一个非常热门的研究领域，经过多年的发展，已成为人工智能两大主流( 连 接主义和符号主义) 之一。随着研究的深入，目前神经计算研究中存在的问题也逐渐暴 露出来，其中的一些已成为神经计算进一步发展的阻碍。但是，从另一个方面来看，它 们也揭示了该领域下一步应该着重研究的问题。 1 2 分类问题 数据挖掘的主要方法有分类，聚类，粗糙集，决策树等，本文研究的主要是分类( 包 括二分类和多分类问题) 。 分类是将数据项分为一个或几个预定义的类的一个初始学习函数分类是一种有监 督的学习方法，已知数据的类别是确定的。支持向量机( s v m ) 是一种非常重要的分类 方法，它是建立在统计学习理论基础上的机器学习方法通过学习算法，s v m 可以自 动寻找那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类 的间隔，因而有较好的推广性能和较高的分类准确率。s v m 主要思想是针对两类分类 问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误率。而且 s v m 个重要的优点是可以处理线性不可分的情况。用s v m 实现分类，首先要从原始 空间中抽取特征，将原始空间中的样本映射为高维特征空间中的一个向量，以解决原始 空间中线性不可分的问题支持向量机( s v m ) 是一种非常重要的分类方法，它是建立 在统计学习理论基础上的机器学习方法通过学习算法，支持向量机可以自动寻找那些 对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因 而有较好的推广性能和较高的分类准确率。支持向量机主要思想是针对两类分类问题， 在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误率。而且支持向 量机一个重要的优点是可以处理线性不可分的情况。用支持向量机实现分类，首先要从 原始空间中抽取特征，将原始空间中的样本映射为高维特征空间中的一个向量，以解决 原始空间中线性不可分的问题 支持向量机是数据挖掘的一种新方法，是数学规划在数据挖掘领域的一个重要应用。 支持向量机是v a p n i k 等人根据统计学习理论提出的一种新的机器学习方法，其本质是数 学规划中的二次规划。如何准确、快速求解二次规划是支持向量机研究的基本问题，而这些 问题的解决与数学规划中的优化理论密切相关支持向量机( s u p p o r tv e c t o rm a c h i n e 简 称s v m ) 是v a p n i k 领导的实验室研究小组提出的一种新型通用的有监督的机器学习方 法1 3 “它建立在结构风险最小化原则( s t r u c t u r a lr i s km i n i m i z a t i o ni n d u c t i v ep r i n c i p l e ) 基础之上1 3 3 】，具有很强的学习能力和泛化性能，能够较好地解决小样本、高维数、非线 性、局部极小等问题，可以有效地进行分类、回归、密度估计等删由于有这些优点， 4 大连理工大学硕士学位论文 支持向量机已成为机器学习领域的研究热点。目前，支持向量机已经成功的应用于三维 物体识别、时间序列分析、文本自动分类、遥感图像分析、人脸检测、手写体数字识别、 蛋白质结构预测等诸多方面。 在文献【3 5 j 中，邓乃扬老师用了一个例子来直观的说明支持向量机分类问题的提出。 例假定是否患有心脏病与病人的年龄和胆圊醇水平有密切关系，下表对应十个病人 的临床数据： 病人编号年龄m -胆固醇水平p 】2有否心脏病y l6 01 6 5 1 25 71 5 01 1 07 01 9 01 表中g = 1 表示该病人属于正类，即有心脏病；= 一1 表示该病人属于负类，即无 心脏病在这里第1 位病人的数据是。1 = ( p z l ，陋1 2 ) t ；( 6 0 ，1 6 5 ) r ，y l = 一1 ；第二第 位病人的数据是z 2 = ( k 2 l ，b 】2 ) t = ( 5 7 ，1 5 0 ) t ，y 2 = 一1 ；第l o 位病人的数据是 x 1 0 = ( 扣1 0 l ，k l o 】2 ) t = ( 7 0 ，1 9 0 ) t ，y l o = 1 这些数据可综合为； t = ( x l ，y 1 ) ，( x 2 ，轨) ，一，( 。1 0 ，y t o ) 现在的问题是，对新来的一位病人，已得知他的年龄，和胆固醇水平m 2 ，试推断他是 否有心脏病，即求对应的y 是1 还是一1 这个问题是个2 维空间上的分类问题，可以在平面直角坐标系上描述如下： 根据病人的2 项指标和有无心脏病，把每个病人用一个样本点表示( 参看图1 ) 样本 点的两个坐标由2 项指标确定，点的形状由有无心脏病来确定：有心脏病者用+ 形点， 无心脏病者用圆形点。如第2 个病人用图中的最左下方的圆形点来表示。新来的一位 病人相当于给了平面上的一个点o ，现在的问题是要推断它属于正类( y = 1 ) 还是 负类( y = - i ) 换句话说，我们需要把平面划分成两部分，使得当该点落入其中一部 分时，推断该病人属于正类；而落入另一部分时，推断他属于负类，关键是如何划分平面。 5 支持向量机和分类问题的算法研究 图1 观察图1 标出的两点，可以考虑选择一条适当的直线w - z + b = 0 把平面戈4 分成两 部分，其中w - z 是w = ( 【”】z ， ”】。) 丁和z = ( i x - ，引z ) t 的内积。而把直线的两侧分别归 为正类和负类。或者说可以按下列方式推断点。所对应的y 其中s 口( - ) 是符号函数 1 3 支持向量机模型 y = ，( 。) = s g n ( w x + b ) ，、f 1 ，o 0 8 9 n 恤户i - l n 0 的样本称为支持向量由1 3 1 和1 3 2 的约束条件和k k t 互补条件可知支持向量就是满足岛= 1 一y l ( w t x l 一7 ) 且 矗0 的向量。以图1 中圆圈所代表的样本为倒，就是与本类数据在平面w t 翰= ，y 一1 异 侧的圆圈样本特别要说明的是分类间隔上的向量也是支持向量，它们对应的l a g r a n g e 乘子0 o l i g ( 其余的支持向量对应的l a g r a n g e 乘子o t i = 口) 。当啦取定时得到 w = 2 。a i 瓠盔此时，y 可以通过任意支持向量求得，这时广义最优线性分类器( 也称为 决策函数) 是 l m ) = s g n ( t z 一7 ) = 8 9 n ( q 舭i - z 一，y ) ( 1 3 4 ) i = 1 也就是图2 中的加t 。一7 ，其余两个超平面w t x = ，y 士1 我们把它们叫做边界超平面。 除了上述的标准模型外，还有一种非标准的支持向量机模型应用也十分广泛 a t , a s m i n 导w 丁w + ，y 2 + 笔。鲁 s t 瓠( 叫t 魏一7 ) + 矗1 ，i 1 ，一，f ) ( 1 3 5 ) 矗0 ，i 1 ，f ) 该模型利用0 ( w ，1 ) 胪代替原来的置信范围w | | 2 ，使用2 范数平方的训练误差来代 替l - 范数的训练误差这样得到了一个对分类结果影响很小的强凸的目标函数 3 9 】，任 何算法在该目标函数e 通常具有比标准模型更快的收敛速度 7 支持商量机和分类问题的算法研究 ( 巍s t a n d a r d s v m 。c l a 蔗s i f i e r 图2 1 3 2 非线性分离器 当给定的样本点不能用个超平面分离或近似分离时，为了提高分类的准确度，可 以引进核函数，其核心思想是将样本。映射到某个高维特征空间日，也就是做变换 圣：o 一西( z ) = ( 蛋1 ( z ) ，垂2 ( z ) ，吼( 。) ) ( 其中 是高维空间日的维数) ，而在高 维特征空间日中训练样本的像有较好的分离性，也就是说，在高维特征空间口中训练 样本可以被线性分离。此时模型1 3 2 和1 3 4 转化为 l x l a x ：l 啦一j 1 ：j ；1 啦a 7 y , y j o ( z d 圣( q ) s t 0 q isc ，i 1 ，f )( 1 3 6 ) 2 1 啦玑= 0 和 2 ，( z ) = s g n ( w t 西( 。) 一7 ) = s g n ( 啦耽西( ) 垂( 。) 一1 ) ( 1 3 7 ) f = i 上述两式就是非线性支持向量机的数学模型从上面两式可以看到寻优函数和分类函数只 涉及训练样本之间的内积，而不必知道变换的具体形式根据泛函理论，只要一种核函 数耳( ，纨) 满足m e r c e r 条件：对任意给定函数g ( 正) 当r9 2 ( z ) 出有限时，( 锄，玑) 就 对应某一空间的内积，而相应的寻优函数和分类函数也变为 m a x 。i 一；啦k ( 甄，z j ) ( 1 _ 3 8 ) k 1 “i d = l 8 大连理工大学硕士学位论文 和 ，( z ) = s g n ( ：，a i y i k ( x i , z ) 一，y )( 1 , 3 9 ) 当前常用的核函数有三种，分别是多项式核函数k ( x ，y ) = ( zy + 1 ) 8 径向基函数 ( 也叫高斯核函数) 琢( ix yi ) = e z p ( 一fz y1 2 盯2 ) 等，在本文的算例中用到的就 是高斯核函数 1 4 支持向量机的算法 在这里总结一下已有的二分类支持向量机算法。 由于s 、伽方法较好的理论基础和它在一些领域的应用中表现出来的优秀的推广性 能。近年来，许多关于s v m 方法的研究，包括算法本身的改进和算法的实际应用，都陆 续提了出来尽管s v m 算法的性能在许多实际问题的应用中得到了验证，但是算法在 计算上存在着一些问题，包括训练算法速度慢、算法复杂而难以实现以及检测阶段运算 量大等等 传统利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的主要原因： 首先，s v m 方法需要计算和存储核函数矩阵，当样本点数目较大时，需要很大的内存， 例如，当样本点数目超过4 0 0 0 时，存储核函数矩阵需要多达1 2 8 兆内存；其次，s v m 在二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的 主要部分 s v m 方法的训练运算速度是限制它的应用的主要方面，近年来人们针对方法本身 的特点提出了许多算法来解决对偶寻优问题大多数算法的一个共同的思想就是循环迭 代：将原问题分解成为若干子问题，按照某种迭代策略，通过反复求解子问题，最终使 结果收敛到原问题的最优鳃根据子问题的划分和迭代策略的不同，又可以大致分为两 类： 第一类是“块算法”( c h u n k i n ga l g o r i t h m ) 。块算法”基于的是这样一个事实，即 去掉l a g - r a n g e 乘子等于零的训练样本不会影响原问题的解对于给定的训练样本集，如 果其中的支持向量是已知的，寻优算法可以排除非支持向量，只需对支持向量计算权值 ( 即l a g r a n g e 乘子) 即可。实际上支持向量是未知的，因此“块算法”的目标就是通过 某种迭代方式逐步排除非支持向量具体的作法是，选择一部分样本构成工作样本集进 行训练，易0 除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结 果( 一般是指违反k k t 条件) 的样本( 或其中的一部分) 与本次结果的支持向量合并成 为一个新的工作样本集，然后重新训练如此重复下去直到获得最优结果 当支持向量的数目远远小于训练样本数目时，“块算法”显然能够大大提高运算速 度然而，如果支持向量的数目本身就比较多，随着算法迭代次数的增多，工作样本集也 会越来越大，算法依旧会变得十分复杂因此第二类方法把问题分解成为固定样本数的 予问题：工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程中只是将剩余 9 支持向量机和分类问题的算法研究 样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换，即使支持向量数 据挖掘中若干数学模型与算法研究的个数超过工作样本集的大小，也不改变工作样本集 的规模，而只对支持向量中的一部分进行优化。 固定工作样本集的方法和块算法的主要区别在于：块算法的目标函数中仅包含当前 工作样本集中的样本，而固定工作样本集方法的优化变量虽然仅包含工作样本，其目标 函数却包含整个训练样本集，即工作样本集之外的样本的l a g r a n g e 乘子固定为前一次迭 代的结果，而不是像块算法中那样设为0 。而且固定工作样本集方法还涉及到个确定 换出样本的问题( 因为换出的样本可能是支持向量) 。这样，这一类算法的关键就在于找 到一种合适的迭代策略使得算法最终能收敛并且较快地收敛到最优结果 最近j o h nc p l a t t 在提出s m o ( s e q u e n t i a lm i n i m a l0 p t i m i z & t i o n 或s m o ) 算 法将工作样本集的规模减到最小一两个样本之所以需要两个样本是因为等式线性约 束的存在使得同时至少有两个l a g r a n g e 乘子发生变化。由于只有两个变量，而且应用等 式约束可以将其中一个用另一个表示出来，所以迭代过程中每一步的子问题的最优解可 以直接用解析的方法求出来这样，算法避开了复杂的数值求解优化问题的过程；此外， p l a t t 还设计了个两层嵌套循环分别选择进入工作样本集的样本，这种启发式策略大大 加快了算法的收敛速度。标准样本集的实验结果证明，s m o 表现出在速度方面的良好 性能。 子问题的规模和迭代的次数是一对矛盾，s m o 将工作样本集的规模减少到2 ，一 个直接的后果就是迭代次数的增加。所以s m o 实际上是将求解子问题的耗费转嫁到迭 代上，然后在迭代上寻求快速算法。但是，s m o 迭代策略的思想是可以用到其他迭代算 法中，可见s m o 还有改进的余地。 s m o 在实际应用中取得了较好的效果，但它也存在着一些问题。s m o 算法每次迭 代都要更新阈值，但是该值有可能是无法确定的( 例如不存在0 0 ，l i m ，这意味着a + 位于单纯形a 的内部。 因此，问题2 1 2 中的嫡函数日( ) 实际上起着对数障碍函数的作用和障碍函数方法一 样，问题2 1 2 内的两个目标函数，一个是关于l ( x ，a ) 极大化的要求，而日( a ) 则迫使 解点远离边界因此，构造同题2 1 2 的方法实际上是一种( 对偶空间里的) 内点法 文中1 4 s 是用式给出的分析解来导出问题2 1 2 的一个对偶函数将2 1 4 式的解带入 岛( o ，a ) 消去乘子a ，则可得到一个仅为变量x 和p 的函数 坼，州删= 一1 娄唧吲珊 这就是待求的“凝聚函数” 极大极小问题的极大熵方法就是用这个凝聚函数来取代极大值函数进行数值计算。 1 4 大连理工大学硕士学位论文 2 1 2 极大极小问题的最优性理论 这是与乘子有关的一个比较经典的定理，是本文最优性结论和算法的主要依据。它 是对极大极小问题作了等价的变形，然后根据这个变形后模型的最优性定理得到： m i n ，( z ) = m a x l _ 0 2 1 3 模型的转化 本文的支持向量机的乘子极大熵方法是将其w o l f e 对偶问题的目标函数转化为极大 极小问题模型，然后再用乘子极大熵解决这个模型的方法在引入核函数后，人们就可 以将非线性支持向量机转化为高维空间的可分或近似可分情况实际上，线性支持向量 机是这种转化的特例，此时的核函数就是原空间两个向量的点乘，转化后的高维空间仍 是原空间在这里，我们先考虑非线性支持向量机的乘子极大熵方法，线性支持向量机 的乘子极大熵方法只是它的特殊情况。 在非线性支持向量机中，利用核函数将问题转化为如下的数学模型【q 问题( a ) m 。i n g ( a ) = ；n t q 。e t 。 s t y t o l = 0 ，0 盘c e 其中c 0 惩罚参数，0 是由核函数确定的正定矩阵q = ( 玑纷玎，) ) 。，k ( x ，y ) 是核函数在本文中我们将给出的不是这个模型的算法，面是利用w o l f e 对偶问题转化 的极大极小模型的算法 根据矩阵的c h o l e s k y 分解理论，正定矩阵q 可唯一的分解为q = s t s ，其中s 是 上三角矩阵令s 。= 让，于是问题( a ) 可以写成如下形式： 1 5 支持向量机和分类问题的算法研究 问题( b ) 珊n s t ；让一e t 口 t o = 0 s a 一札= 0 0 0 号 ( 矿) = f ( x + ) 0 = ，p v 成 m 僦 l= 肛 。： 支持向量机和分类问题的算法研究 证完。 v 。( ll n m ：1 胁矿丘帅。) 成e 州矿v 五( 。4 ) i = l 5 而一 成e 州矿 胁e 咧矿v f , ( z + ) 心 o 5 而一 邶咧矿 e p ，( 成v 工( 矿) 心 0 m e p t = 1 =0 定理2 3 2 【5 0 】：若 ( z ) ，i = 1 ，m 满足条件： ( a ) ( z ) ，i = 1 ，m 二次连续可微， ( b ) ( 矿，矿) 满足一t 条件： v 。l ( x + ，p + ) = 0 ，卢+ 0 ，e t p + = 1 ，p ；( ，扛+ ) 一a ( x + ) ) = 0 ，i = 1 ，一，m 其中，l ( x ，卢) 是l a g r a n g e 函数。 ( c ) 严格互补条件成立：成 0 ，i i ( x + ) ，( 矿) = 0 ，( 矿) = ( 矿) ) ( d )