（应用数学专业论文）基于支撑矢量机的模式识别算法的研究.pdf

论文题目：基于支撑矢量机的模式识别算法的研究 专业：应用数学 硕士生：高滨( 签名)茧煞 指导老师：丁正生( 签名)工丝 摘要 支撑矢量机( s v m ，s u p p o r tv e c t o rm a c h i n e ) 是基于统计学习理论的一种模式识别方 法。使用结构风险最小化原则替代经验风险最小化原则，避免了一些长期困扰其他模式 识别方法的问题，使它对于小样本学习有着较好的处理能力。利用核函数，把非线性空 间的问题转换到线性空间上来解决，降低了算法的复杂度。由于具有得天独厚的优点( 完 备的理论基础和较好的学习性能) ，使它成为当前模式识别领域研究的热点。 本文首先对s v m 的理论基础一统计学习理论和相关概念进行了介绍。然后对两类 s v m 实现算法进行深入研究，并对他们的性能进行分析，对其优缺点进行了总结。下 来对多类分类及实现算法进行了研究与分析，并对他们的算法特点进行对比。 针对大规模训练集，对s v m 引入增量学习方法。这种算法通过分析s v 分布的特 点，采用小规模的矩阵运算来代替大规模的矩阵运算。通过对织物疵点识别的实验结果 表明，该算法有效的提高了训练速度。 关键词：支撑矢量机；统计学习理论；模式识别 研究类型：应用研究 s u b j e e t ：p a t t e r n r e c o g n i t i o na l g o r i t h m b a s e do ns u p p o r tv e c t o r m a c h i n e s p e c i a l t y ：a p p l i e dm a t h e m a t i c s n a m e：g a o b i n( s i g n a t u r e ) 萱遑 i n s t r u c t o r ：d i n gz h e n g s h e n g( s i g n a t u r e ) a b s t r a c t s u p p o r tv e c t o rm a c h i n ei sap a u e mr e c o g n i t i o na l g o r i t h mb a s e do ns t a t i s t i c a ll e a r n i n g t h e o r y b e i n gs u b s t i t u t e ds t r u c t u r a lr i s km i n i m i z a t i o nf o re m p i r i c a lr i s km i n i m i z a t i o n ，s u p p o r t v e o o rm a c h i n es o l v e ss o m ep r o b l e m sp u z z l i n gp a t t e r nr e c o g n i t i o nf i e l dw i t h i nal o n gp e r i o d s u p p o r tv e c t o rm a c h i n eh a s a g o o da b i l i t yp r o c e s s i n gf e w e rs i m p l e s an o n l i n e a rp r o b l e mc a n b et r a n s f o m a e dt oal i n e a rp r o b l e mw i t hu s i n gk e r n e lf u n c t i o n s t h et r a n s f o r m a t i o nr e d u c e s c o m p l e x i t yo ft h ea l g o r i t h m w i t hs o m eh i g h l i g h t ss u c ha sp e r f e c tt h e o r i e s ，s u p p o r tv e c t o r m a c h i n ei sah o tp o i n ti np a a e mr e c o g n i t i o nf i e l dn o w a d a y s t h e o r e t i c a lb a s i sf o rs v m r e l a t e ds t a t i s t i c a ll e a r n i n gt h e o r ya n dc o n c e p t sa r ei n t r o d u c e d a tt h eb e g i n n i n g s o m ea n a l y s i so f2 - c a t e g o r ys v ma l g o r i t h m sp e r f o r m a n c ea n das u m m a r y o ft h e i ra d v a n t a g e sa n dd i s a d v a n t a g e sa r ed o n ei nc h a p t e r2 r e a l i z a t i o no fm u l t i c a t e g o r y c l a s s i f i c a t i o na l g o r i t h m sb er e s e a r c h e da n da n a l y z e di nt h en e x tc h a p t e r s o m ec o m p a r i s o n s o f t h e i rf e a t u r e sa r ed o n ei nt h ec h a p t e r f o rm a s s i v et r a i n i n gs e t s ，a l li n c r e m e n t a ll e a r n i n gm e t h o df o rs v mi sp r o p o s e di nc h a p t e r 4 s u c ha l g o r i t h m s t h r o u g ha n a l y s i ss u p p o r tv e c t o r s d i s t r i b u t i o nc h a r a c t e r i s t i c su s e s m a l l s c a l em a t r i xo p e r a t i o n st or e p l a c el a r g e s c a l em a t r i xo p e r a t i o n s e x p e r i m e n t a lr e s u l t so f f a b r i cb l e m i s hd e t e c t i o ns h o wt h a tt h ea l g o r i t h me f f e c t i v e l yi m p r o v e st r a i n i n gs p e e d k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e ，s t a t i s t i c a ll e a r n i n gt h e o r y ，p a t t e mr e c o g n i t i o n t h e s i s ：a p p l i e dr e s e a r c h 压要料技太学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体己经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：高氓日期：娜莎、钐厂 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 指导教师签名： 丁z 壁 砷f 年qr 予日 1 绪论 l 绪论 1 1 研究背景 支撑矢量机是一种用于模式识别的方法。模式识别的作用就在于让计算机面对某一 事物时将其正确的归入某一类别，它诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出 现，5 0 年代人工智能的兴起，模式识别在6 0 年代初迅速发展成一门学科。几十年来， 模式识别研究取得了大量的成果，在很多方面取得了成功的应用，推动了人工智能的发 展。经典的模式识别方法有统计模式识别和结构( 句法) 模式识别。统计模式识别可看 成是基于数据的机器学习的特例。基于数据的机器学习是现代智能技术中十分重要的一 个方面，主要研究如何从一些观测数据出发得出尚不能通过原理分析得到的规律，利用 这些规律去分析客观对象，对未来数据或无法观测数据进行预测。当把要研究的规律抽 象成分类关系时，这种机器学习问题就是模式识别问题。随着人工智能的发展，模糊模 式识别，神经网络模式识别也取得了大量的成果。特别是在神经网络模式识别领域，集 中了大量的研究人员，成果层出不穷。神经网络模式识别方法的一个重要特点就是它能 够有效的解决很多非线性问题。但另一方面，神经网络中很多重要的问题没有从理论上 得到解决，实际应用中仍有许多因素需要凭经验确定，像网络节点数及网络层数的选择， 初始权值和学习步长的确定等：局部极小点问题，过学习与欠学习等都是很多神经网络 方法中普遍存在的问题。这些问题几乎使以神经网络为代表的经典机器学习方法的研究 停滞不前。 人的智慧中一个很重要的方面是从实例学习的能力，通过对己知事实的分析总结出 规律，预测不能直接观测的事实。在这种学习中，重要的是要能够举一反三，即利用学 习得到的规律，不但可以较好地解释已知的实例，而且能够对未来的现象或无法观测的 现象做出正确的预测和判断。我们把这种能力叫做推广能力。 在人们对机器智能的研究中，希望能够用机器( 计算机) 来模拟这种学习能力，这 就是我们所说的基于数据的机器学习问题，或者简单地称作机器学习问题。我们的目的 是，设计某种( 某些) 方法，使之能够通过对己知数据的学习，找到数据内在的相互依 赖关系，从而对未知数据进行预测或对其性质进行判断。同样，在这里，我们最关心的 仍是推广能力问题。 统计学在解决机器学习问题中起着基础性的作用。但是，传统的统计学所研究的主 要是渐近理论，即当样本趋向于无穷多时的统计性质。在现实的问题中，我们所面对的 样本数目通常是有限的，有时还十分有限。虽然人们实际上一直知道这一点，但传统上 西安科技大学硕士学位论文 仍以样本数目无穷多为假设来推导各种算法，希望这样得到的算法在样本较少时也能有 较好的( 至少是可接受的) 表现。然而，相反的情况是很容易出现的。其中，近年来经 常可以听到人们谈论的所谓神经网络过学习问题就是一个典型的代表：当样本数有限 时，本来很不错的一个学习机器却可能表现出很差的推广能力。 人们对于解决此类问题的努力实际上一直在进行。但是，其中多数工作集中在对已 有( 基于传统统计学原则的) 方法的改进和修正，或者利用启发式方法设计某些巧妙的 算法。 在人类迈进一个新世纪的时候，人们开始逐渐频繁地接触到一个词，就是“统计学 习理谢l j ”。这实际上是早在2 0 世纪7 0 年代就已经建立了其基本体系的- - i 理论，它系 统地研究了机器学习的问题，尤其是有限样本情况下的统计学习问题。在9 0 年代，这 一理论框架下产生出了“支撑矢量机( s v m ) 2 】口】【4 】”这一新的通用机器学习方法。或许是由 于统计学习理论为人们系统研究有限样本情况下机器学习问题提供了有力的理论基础， 或许更是因为在这一基础上的支撑矢量机方法所表现出的令人向往的优良特性，人们开 始迅速重视起这一早在3 0 年前就该重视的学术方向。 现在，越来越多的学者认为，关于统计学习理论和支撑矢量机的研究，将很快出现 像在8 0 年代后期人工神经网络研究那样的飞速发展阶段。然而，所不同的是，统计学 习理论有完备的理论基础和严格的理论体系( 相比之下神经网络有更多的启发式成分) ， 而且其出发点是更符合实际情况的有限样本假设，因此，我们期望，统计学习理论的这 个研究热潮将持续更长久，而且将在人们关于机器智能的研究中做出影响更深远的贡 献。 1 2s v m 的理论基础 1 2 1 统计学习理论 机器学习问题可以形式化地表示为：己知变量y 与输入x 之间存在一定的未知依赖 关系，即存在一个未知的联合概率f ( x ，y ) ( x 和y 之间的确定性关系可看作是一个特 例) ，机器学习就是根据m 个独立同分布观测样本( ，y 1 ) ，( 恐，虬) ，( ，m ) ，在一组函数 f ( x ，w ) ) 中，求一个最优函数f ( x ，w o ) ，使预测期望风险 r ( w ) = i l ( y ，f ( x ，w ) ) d f ( x ，y )( 1 1 ) 最小。其中， f ( x ，”) 称作预测函数集，w q 为函数的广义参数，故 ，( 上，w ) ) 可表示 任何函数集，l ( y ，f ( x ，w ) ) 为由于用 f ( x ，w ) 对y 进行预测而造成的损失。不同类型的 学习问题有不同形式的损失函数。预测函数通常称作学习函数，学习模型或学习机器。 2 1 绪论 显然，要使式( 1 1 ) 定义的期望风险最小，必须依赖关于联合概率f ( x ，y ) 的信息。由概率 论可知，必须要求己知类先验概率和类条件概率密度才能求得联合概率。但是，在实际 的机器学习问题中，我们只能利用已知样本的信息，因此期望风险无法直接计算和最小 化。根据概率论中大数定律的思想，我们用算术平均代替式( 1 1 ) 6 0 的数学期望，定义 1 上 疋，( 1 叻= 亡，厂( 葺，w ) ) ( 1 2 ) ，i = 1 来逼近式( 1 1 ) 定义的期望风险。由于式( 1 2 ) 是用已知的训练样本定义的，因此称作经验 风险。 用经验风险代替期望风险，就是经验风险最小化原则。以神经网络为代表的传统机 器学习方法，都采用经验风险最小化原则训练分类器。 仔细研究经验风险最小化原则和机器学习问题中的期望风险最小化要求，可以发 现，从期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上合理的想 当然的做法。 首先，式( 1 1 ) 和式( 1 2 ) 都是w 的函数，概率论中的大数定律只说明( 在一定条件下) 当样本量趋于无穷时，式( 1 2 ) 将在概率意义上趋近于式( 1 1 ) ，并没有保证使式( 1 2 ) 最 小的w 与使式( 1 1 ) 最小的w 是同一个点，也不能保证8 一( w ) 能够趋近于r ( w ) 。其次， 即使我们有办法使这些条件在样本数无穷大时得到保证，我们也无法认定在这些前提下 得到的经验风险最小化方法在样本数有限时仍能得到好的结果。 尽管有这些未知的问题，经验风险最小化作为解决模式识别等机器学习问题的基本 思想仍统治了这一领域几乎所有的研究，人们多年来一直将大部分注意力集中到如何更 好地求取最小经验风险上。v a p n i k 对传统统计学应用在机器学习问题中的这些不足做了 系统的研究，从而提出了专门针对解决小样本学习问题的统计学习理论，该理论系统地 给出了经验风险最小化原则下统计学习一致性的条件以及在这些条件下关于统计学习 方法推广性的界的结论，并在这些界的基础上建立了全新的小样本归纳推理原则，以及 实现这些原则的算法。 1 2 2 指示函数集的v c 维 函数集的v c 维是统计学习理论中的一个核心概念，由v a p n i k 和c h e r v o n e n k i s 提出， 并取两人名首字母而得名。v c 维反映了函数集的容量。在模式识别问题中，我们研究 指示函数集的v c 维。一个指示函数集的v c 维，是能够被集合中的函数以所有可能的2 “ 种方式分成两类的矢量的最大数目( 也就是能够被这个函数集打散的矢量的最大数目) 。 如果对任意的 ，总存在一个n 个矢量的集合可以被函数集打散，那么函数集的v c 维 就是无穷大。统计学习理论指出，是函数集的v c 维( 而不是其自由参数个数) 影响了 西安科技大学硕士学位论文 学习机的推广性能。这样，我们可以通过控制函数集的v c 维来控制学习机的推广性能 而不必考虑所谓的“维数灾难”问题。 o 图1 1v c 维示例：平面中直线的v c 维等于3 ，因为它们能打散3 个向量而不能打散4 个 例如向量2 2 ，z 4 不能被直线与向量2 l ，z 3 分开 1 2 3 结构风险最小化原则 在解模式识别问题的过程中，由于实现由贝叶斯决策理论导出的期望风险最小化原 则必须依赖类先验概率和类条件概率密度，故期望风险无法直接计算并最小化。在实际 应用中，我们只能用经验风险逼近期望风险，并希望通过最小化经验风险来实现期望风 险最小口】。经验风险最小化( e r m ) 原则一直是解统计模式识别等统计机器学习问题的基 本思想在此思想的指导下，人们主要解决如何更好地求取最小经验风险。但实践证明， 一味追求训练误差最小( 对应经验风险最小) 并不能得到最好泛化能力，有些情况下， 训练误差太小反而会导致泛化能力下降，这在神经网络中表现得尤为突出( 过学习问 题) 。导致出现该问题的一个根本原因就是传统统计学是一种渐进理论，它的许多结论 都是在样本数目趋向于无穷大的条件下得出的，而在小样本条件下，以传统渐进统计学 为理论基础的经验风险最小化原则并不能很好的实现由贝叶斯决策理论导出的期望风 险最小化原则。统计学习理论指出，在小样本条件下，只有同时控制经验风险和学习机 的容量( 用v c 维衡量) ，才能获得具有良好推广能力的学习机该思想在数学上可由下 式表示的衡量分类器推广能力的界来表达： 胄( w ) 咒。( w ) + 妒 ( 1 3 ) 毛 f _ 一 、硝1j叫，、一，kfk、一 z 一 一竖 弓 、 一 ， 、 一 ， 、 一一 ： ， 、 一 ，、，、 k 一 、 一鲨 1 绪论 其中 称作置信范n l ( c o n f i d e n c ei n t e r v a l ) ，r ( 川表示 实际风险，8 。( w ) 表示经验风险，h 表示v c 维，胛为训练集样本数，1 一町为置信水平。 但该界不具备构造性，即我们无法直接由该界构造出能实现其理论思想的有效学习算 法。因此我们必须找出某个能同时实现该理论思想并具备构造性的理论。结构风险最小 化原则就是满足这样要求的一个理论。 结构风险最小化( 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 r m ) t 6 1 t7 】原则很好地实现了同时控制 经验风险和学习机容量的思想，其原理如图2 所示。s r m 将分类器构成的函数集合划 分成若干按置信范围( 也即按v c 维) 升序排列的子集，然后再在每一个子集中寻找最 小经验风险，从而分两步实现式f 1 3 ) 的思想。 c o c 图1 2s r m 原理图 1 _ 3s v m 的基本原理 s r m 原则具备算法构造性，s v m 就较好的实现了s r m 原则。在众多分类器当中， 线性分类器具有最简单的结构，人们便考虑用类似线性判别函数的方法来实现s r m 原 则，s v m 便是从模式类线性可分情况下的最优分类面( o p t i m a lh y p e r p l a n e ) 提出的，它的 基本思想是：若在原始特征空间中实现的分类器结构十分复杂，则通过定义适当的核函 数诱导出某个非线性变换，用此变换将原始特征空间映射到一个高维空间，然后在这个 新的特征空间中求得最优线性分类面，以降低分类器的复杂度。由r k h s ( r e p r o d u c i n g 西安科技大学硕士学位论文 k e r n e lh i l b e r ts p a c e s ) 理论阍嘲可知，当选定的核函数满足一定条件时，由该核函数导 出的高维特征空间中两特征矢量问的点积可由核函数在低维特征空间中对应两特征矢 量上定义的计算而得到。这样，我们便可在低维特征空间中处理对应高维特征空间中的 数据。由于求解s v m 只涉及到矢量问的点积运算，故我们可不必担心由于引入核函数 而引起计算上的维数灾难，而可将注意力集中到如何选取恰当的核函数上，以改善特征 矢量在高维特征空间中的分布，从而使分类器结构更简单。这样，求解s v m 的过程即 为在高维特征空间中求解模式类样本数据之间最优分类面的过程，此处的最优分类面是 在控制样本错分率的前提下使两类样本数据问的分类间隔( 高维特征空间中) 最大的分 类面。统计学习理论指出，一间隔分类超平面集合的v c 维上界h 可由式( 1 4 ) 给出： 一m i n 等 ，n + c 一。， 其中r 为包含训练数据的球体的半径，2 丽1 ，w 2 善只q ，一，q o i f = 1 ，2 ，7 。月 为特征空间的维数。我们考虑两类分类问题， ，m ) 为给定训练样本，其中t 为第i 个 样本矢量，m 一1 ，1 ) ，代表x 的类别。当样本线性不可分时，广义最优分类面可通过 解决下列条件约束优化问题而得到： ( w ) 2 圳1 2 ( 1 - 5 ) s j 儿 ( w ) q - b 】一1 0i = 1 ，2 ， j 【，2 图1 3 最优分类面示意图 6 1 绪论 使分类间隔最大相当于使i f w 旷最小，训练错误率为0 意味着对所有的样本( ，咒) 有 m 【( w t ) + 6 】一l 0( 1 - 6 ) 这时，求最优分类问题表示为求解下列q p ( q u a d r a t i cp r o g r a m m i n g ) i h 题： m i n 如) 5 扪1 2 ( 1 7 ) 咒 ( w 葺) + 卅一1 o i = 1 ，2 ， 在线形不可分的情况下引入松弛变量，则转化为下面的q p 问题： m i n 触沪争1 1 2 + c ( 善n 白8 )( 1 _ 8 ) s _ t y 【( w - 一) + 6 卜1 + 4 0i = 1 ，2 ，一，f 其中，亭 0 为松弛因子。 利用l a g r a n g e 方法将上述问题转化为其对偶问题，若选定某一个核函数，当万= 1 时， 就得到l i s o f t m a r g i ns v m ，这时，等价于解决下列q p ( q u a d r a t i cp r o g r a m m i n g ) 优化问 题【l o ： m i n 二口7 0 臼一e 7 口 2 0 6 1 i c ，i = 1 ，- 一，7 ( 1 - 9 ) y r a = 0 其中， q = y y j k ( x i ，x j ) ，日= ( q 吒) 7 ，y = ( 儿乃 c = ( c c ：0 ) 7 ，且q = c ：一一巳k ( x i ，_ ) 为我们选定的核函数，t 为样本矢量， m 为样本类别，c 为控制错分样本与模型复杂度之间折衷度的常量。我们称( 1 - 9 ) 为 l 1 - s v mq p 问题。解l i s v mq p 问题后即可得到s v m 厂( x ) = s g n ( q m k ( ，x ) + 6 ) ( 1 _ 1 0 ) i = 1 可以证明，( 1 9 ) 优化问题的最优解对应于一个一间隔分类超平面集合中处于几何 中心位置的元素( 在高维空间中，从几何上来讲，该优化问题的最优解所对应的学习机 即为某一个超球的中心位置所对应的矢量) 。由式( 1 4 ) 可知，在选定核函数，训练集确 定的情况下，只需最小化m i 便可控制 ，从而可以控制分类器所在的分类超平面集合 的置信范围。然后再在该集合中寻找使经验风险最小的分类器( 该分类器即对应于分类 西安科技大学硕士学位论文 器集合的几何中心) ，继而实现s r m 原则。 总结起来，s v m 主要体现了以下思想： 1 ) 分类器容量控制的思想。也即控制分类器集合函数的v c 维。该思想直接来源于 统计学习理论，s v m 通过同时控制经验风险和学习机的容量来提高推广能力。 2 ) 通过引入核的思想来控制分类器容量。若在原始特征空间中实现的分类器结构十 分复杂( 对应分类器函数集的v c 维比较高) ，则通过定义适当的核函数诱导出某个非 线性变换，用此变换将原始特征空间映射到一个高维空间，然后在这个新的特征空间中 求得最优线性分类面，以降低分类器的复杂度( 即降低分类器函数集的v c 维) 。 3 ) 通过求解q p 来实现容量控制的思想与核的思想。 1 4 现阶段s v m 的主要研究方向 1 ) s v m 提出之后，从理论的角度研究s v m 的推广性能一直是s v m 领域的研究重 点，并取得了丰硕的成果，这些成果为提高s v m 的推广性能提供了理论保证。 2 ) 从s v m 实现算法的角度看，求解s v m 可以转化成一个二次规划( q p ) i h 7 题，目前， 针对q p 的研究己相当深入，这些研究成果从算法实现上保证了s v m 的实用性。但实 际上，通过求解q p 来实现容量控制与核的思想，在实践中还存在众多问题。其中一个 主要问题就是参数选择与优化问题，包括核函数的选择与参数优化及控制经验风险与分 类器函数集v c 维的参数c 的优化等。核函数选择及参数优化是当今s v m 领域的研究 热点。 3 ) s v m 是一种两类分类器，而在实际应用中要解决多类分类问题。用s v m 构造多 类分类器是s v m 领域的又一研究重点。用s v m 构造多类分类器有众多的理论与算法 问题需要解决。一方面，衡最s v m 推广性能的现论成果不能直接应用于由s v m 构造 的多类分类器之中，因此，有必要从理论上研究由s v m 构造的多类分类器的推广能力， 为构造多类分类器提供理论指导。另一方面，虽然现阶段s v m 的实现算法已非常高效， 但由于多类分类问题往往较复杂，要处理的数据也比较庞大，因此，多类分类器的高效 构造算法的研究就显得非常重要。 4 ) s v m 的应用研究。应用研究领域包括图像识别( 指纹、卫星图像等) 与声音、压 力等感知信号的识别。日前，上述几方面问题正得到广泛研究。 1 5 主要工作和全文结构 本文主要针对支撑矢量机这种比较新的机器学习方法进行分析研究，重点在其实现 算法上。支撑矢量机原本是针对二类分类问题而提出的，通常的办法是将其转化为二次 规划问题加以解决，如何利用支撑矢量机的特点进行算法的优化和如何将其由二类分类 1 绪论 器推广到解决现实中常见的多类分类问题的多类分类器是目前的研究重点。本文针对这 些方面进行研究并探索其在织物图像识别问题中的应用。 论文的结构安排如下： 第一章绪论，简要介绍了支撑矢量机的理论基础统计学习理论的若干原理，并 对支撑矢量机算法的发展现状及主要研究内容做了简单概括。 第二章基于支撑矢量机实现算法的研究，分析现有的典型二类支撑矢量机分类算 法。 第三章支撑矢量机多类分类算法的研究，总结目前基于支撑矢量机的多类别分类方 法，包括“一对多”方法、对一”方法、一次性求解方法、决策有向无环图方法等。 第四章针对支撑矢量机学习步骤，提出了一种改进算法增量学习算法。 全文对现有支撑矢量机的实现算法进行了分析，指出其优缺点并提出改进算法，并 结合织物图像的识别，进行了试验对比，这样对这些算法的性能有了更加直观的对比。 西安科技大学顽士学位论文 2 支撑矢量机实现算法的研究 前面提到，本质上是通过求解下面的二次规划问题来实现s v m 算法： m i n1 a 7 0 a p 7 d ， 0 s 珥c ，i = 1 ，f y 。1 2 = 0 ( 2 - 1 ) 对上面的优化问题，可用传统的标准二次型优化技术来解决，例如牛顿法 ( n e w t o n ) 、拟牛顿法( q u a s i - n e w t o n ) 、若扼梯度法( c o n j u g a t eg r a d i e n t ) 、原一对偶内点 法( p r i m a l - d u a li n t e r i o rp o i n tm e t h o d s ) 等，现在也有现成的软件包，如l i n d o 但这些方 法存在一些问题，一是运算速度比较慢，二是有稳定性问题。产生这些问题的主要原因 是：首先，q p 方法需要计算和存储核函数矩阵，当样本点数且较大时，需很大的内存： 其次，s v m 在二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占 用算法时间的主要部分【1 1 1 。 由于支撑矢量机转化为二次规划问题中具有线性约束，其矩阵9 为正半定h e s s i a n 阵，其具有一些良好的数学特性：1 ) 最优化问题的凸性( 目标函数为凸函数) ，具有全 局最优解：2 ) 满足k k t ( k a r a s h k u h n t u c k e o 条件的解必为全局最优解；3 ) s v m 本身具 有：支撑矢量数目远小于训练样本数目，并且有些支撑矢量为取上界值的支撑矢量 ( b o u n d e ds u p p o g v e c t o r s ) ，反映在二次规划问题中即为其全局最优解具有稀疏性。利用 这些特性，可以使用优化技术来加快计算速度和降低存储占用。 2 1 分解算法 q s u n a 、j o a c h i m s 、p l a t _ 【等人提出了分解算法( d e c o m p o s i t i o n ) 【1 2 】【1 3 j 。其基本思想就 是循环迭代：将原q p 问题分解成为一系列小的q p 子问题，按照某种迭代策略，通过 反复求解子问题，最终使结果收敛到原问题的最优解。根据子问题的划分和迭代策略的 不同，又可以大致分为2 类。 2 1 1 块算法 块算 法( 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 孕a n g e 乘子) 即可。实 际上，支撑矢量是未知的，因此块算法的目标就是通过某种迭代方式逐步排除非支撑矢 量。具体的做法是：选择一部分样本构成工作样本集进行训练，剔除其中的非支撑矢量， 2 支撑矢量机分实现算法的研究 并用训练结果对剩余样本进行检验，将不符合训练结果( 一般指违反k k t 条件) 的样 本( 或其中的一部分) 与本次结果的支撑矢量合并为一个新的工作样本集，然后重新训 练。如此重复直到获得最优结果为止