（控制理论与控制工程专业论文）多值svm分类投票法的改进.pdf

武汉科技大学硕士学位论文第1 页 摘要 支持向量机是一种针对分类和回归问题的新型机器学习方法。它基于结构风险最小 化原理，能有效地解决过学习问题，具有良好的推广性和较好的分类精确性。正在成为 继模式识别和神经元网络研究之后机器学习领域新的研究热点，并将推动机器学习理论 和技术的重大发展。 目前，支持向量机在模式识别、函数逼近、数据挖掘和文本自动分类中均有很好的 应用。传统支持向量机是针对两类分类问题，而在实际应用中，如数据挖掘、文本分类 等等，需要处理的数据是海量和多类别的。如何解决大规模多类别的问题，是近几年来 研究的重点之一。 本文对统计学习理论进行了介绍，探讨了建立在该理论基础上的支持向量机算法。 阐述了支持向量机的发展历史和研究内容，全面地介绍了支持向量机目前存在的二类分 类算法和多类分类算法，比较了它们的优缺点及性能。 最后，介绍了目前流行的两种投票法，并针对现有投票法的问题和缺点，提出一种 最小内凸包的算法。该算法具有计算量少，算法复杂性小，速度快的特点，适用于需处 理的样本数较多、对计算速度要求较高的多类分类问题。 关键词：机器学习，支持向量机，多类分类，最小内凸包，投票法 第1 i 页武汉科技大学硕士学位论文 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 san e wm a c h i n el e a r n i n ga l g o r i t h mf o rc l a s s i f i c a t i o na n d r e g r e s s i o nq u e s t i o n i tb a s e do ns t r u c t u r a lr i s km i n i m i z a t i o nc a ne f f e c t i v e l ys o l v et h eo v e r s t u d yp r o b l e ma n dt h eg o o de x t e n s i o na n db e t t e rc l a s s i f i e da c c u r a c y i th a sb e c o m en e w r e s e a r c hh o t s p o ta f t e rt h er e s e a r c ho f p a t t e r nr e c o g n i t i o na n da r t i f i c i a ln e r v en e ta n dw i l lp u s h d e v e l o p m e n ti nm a c h i n el e a r n i n g r e c e n t l y ，s u p p o r tv e c t o rm a c h i n ei sw e l la p p l i e di np a t t e r nr e c o g n i t i o n , f u n c t i o n a p p r o x i m a t e ，d a t am i n i n ga n dt e x ta u t oc a t e g o r i z a t i o n t r a d i t i o n a ls u p p o r tv e c t o rm a c h i n ei s d e v e l o p e df o rb i n a r yc l a s s i f i c a t i o np r o b l e m s ，w h i l ef o rp r a c t i c a lp r o b l e m ss u c ha sd a t a m i n i n ga n dt e x tc a t e g o r i z a t i o nt h a tn e e dt od e a lw i t hh u g ea n dm u l t i - c a t e g o r yd a t a i ti so n e o f t h ei m p o r t a n tc h a l l e n g e sh o wt os o l v el a r g es c a l ea n dm u l t i - c l a s sp r o b l e m si nr e c e n ty e a r s s t a t i s t i c a ll e a r n i n gt h e o r yi si n t r o d u c e di nt h i sp a p e ra n ds u p p o r tv e c t o rm a c h i n eb a s e d o nt h i st h e o r yi sr e s e a r c h e d t h ed e v e l o p m e n th i s t o r ya n dr e s e a r c hi s s u e so fs u p p o r tv e c t o r m a c h i n ea r ee x p a t i a t e d t h ed i c h o t o m yc l a s s i f i c a t i o na l g o r i t h ma n dm u l t i c l a s sc l a s s i f i c a t i o n m e t h o d sa l es u m m a r i z e d ，a n dt h e i ra d v a n t a g e ，d i s a d v a n t a g ea n d c a p a b i l i t ya r ec o m p a r e d f i n a l l y ，t h ed i s a d v a n t a g e so ft h ee x i s t i n gm e t h o d so fs u p p o r tv e c t o rm a c h i n ev o t i n g c l a s s i f i c a t i o na r ea n a l y z e da n dc o m p a r e di nt h i sp a p e r t os o l v et h ep r o b l e m s ，t h em i n i m u m i n t e r n a lc o n v e xh u l l a l g o r i t h m i s p r o p o s e d i nt h i s p a p e r t h e m e t h o dh o l d sb o t h l o w - c o m p u t a t i o n a lc o s t sa n df a s t e rc a l c u l a t i o ns p e e d i ts h o w st h a tt h es p e e d so ft r a i n i n ga n d c l a s s i l y i n ga r ei m p r o v e dr e m a r k a b l ya n di ti s ag o o ds o l u t i o nt os o l v es u p p o r tv e c t o r m a c h i n em u l t i c l a s s i f i c a t i o np r o b l e m st h a th a v eah i 曲r e q u e s tf o rc a l c u l a t i n gs p e e da n dn e e d t od e a lw i t hh u g ed a t a 。 k e y w o r d s ：m a c h i n el e a r n i n g ；s u p p o r tv e c t o rm a c h i n e s ；m i n i m u mi n t e r n a lc o n v e xh u l l ； v o t i n g 武汉科技大学硕士学位论文第1 页 第一章课题综述与本文介绍 支持向量机( s v m ，s u p p o r tv e c t o rm a c h i n e ) 是在统计学 - 3 理论的基础上发展起来的 新一代学习算法，是a t & t b e l l 实验室的v v a p n i k 等人提出的一种针对分类和回归问 题的新型机器学习方法。由于其出色的学习性能，该技术己经成为机器学习界的研究热 点，并在很多领域得到了成功的应用，包括模式识别、回归估计、概率密度函数估计等。 广义的讲，智能技术是将人工智能方法运用于生产实际中所产生的具体的技术的总和。 例如集成了知识表示与逻辑推理技术的专家系统，基于决策理论、空间信息系统的空问 决策系统等等。近些年来，随着计算机性能价格比的提高，以及网络的普及，i t 业界也 越来越重视智能技术在提高产品品质与服务质量方面的作用。例如，m i c r o s o f t 公司提出 的让计算机“更具有易用性”的口号，i b m 提出的商业智能解决方案，等等。几乎所有 的智能技术均要涉及到知识的运用，而知识的获取是进行知识运用的一个瓶颈。机器学 习的目标就是研究如何从各类数据中自动地获取知识。 1 i 机器学习的发展历史及现状 对于学习的定义，目前大家比较公认是s i m o n 对学习的阐述：“如果一个系统能够 通过执行某种过程而改进它的性能，这就是学习。” “机器学习”一般被定义为一个系统自我改进的过程，但仅仅从这个定义来理解和 实现机器学习是困难的从最初的基于神经元模型以及函数逼近论的方法研究，到以符 号演算为基础的规则学习和决策树学习的产生，和之后的认知心理学中归纳、解释、类 比等概念的引入，至最新的计算学习理论和统计学习理论的兴起，机器学习一直到在相 关学科的实践应用中起着主导作用。 机器学习的研究主要经历了如下的几个阶段f l , z g 3 0 | 1 1 9 4 3 年m c c u l l o c h 和p i t t s 对神经元模型( 简写为m p 模型) 的研究： 2 r o s e n b l a t t 的感知机为代表的研究，则是从m p 模型出发将扩展为多个神经元的 m p 模型作为优化算法的数学基函数； 3 v a p n i k 提出了“统计学习理论”。 目前，机器学习的研究己不仅是人工智能研究的重要问题而且已成为计算机科学 与技术的核心问题。这种动力来源于数字网络的普及与计算机对社会生活的普遍渗入， 由此，根据需求，提出了一些迫切的问题l ”i ：( 1 ) 发现海量数据中的规律，特别是那些 非结构化的数据。这方面主要的发展是数据中的知识发现；( 2 ) 如何对个性化的需求进行 处理和分析。 第2 页武汉科技大学硕士学位论文 1 2 统计学习理论的核心内容 结构风险最小归纳原理是统计学习理论提出的一种运用于小样本学习问题的归纳 原理，它包括了学习过程的一致性、边界的理论和结构风险最小化原理等部分。它所提 出的结构风险最小化归纳学习过程克服了经验风险最小化的缺点，实用中获得了更好的 学习效果。下面，就对此理论的一些主要内容进行介绍。 1 2 i v c 维 一个指示函数集o ( z ，口) ，a e a ，的v c 维，是能够被集合中的函数以所有可能的2 6 种 方式分成两类的向量z ，而的最大数目h ( 也就是能够被这个函数集打散的向量的最大 数目) 。如果对任意的n ，总存在一个n 个向量的集合可以被函数集o ( z ，口) ，a 人打散， 那么函数集的v c 维就是无穷大。 对实函数集来说，其v c 维的定义如下。设a o ( z ，口) s b ，a a 是一个以常数a 和 口为界的实函数集合( 一可以是一o o ，b 可以是+ m ) 。其指示器集合为 l ( z ，口，) = o q ( z ，口) 一) ， ( 1 i ) 口a ，卢( 彳，口) 其中曰( z ) 是阶跃函数 印) ：o “o ( 1 2 ) 一【i z 0 则实函数集asq ( z ，a ) b ，a a 的v c 维定义为其指示器集合的v c 维，其中参数 口a ，( a ，口) 。 在文献【2 4 】中，给出了一个关于v c 维相关的定理： 定理1 1 ( v a p n i k 和c h e r v o n e n k i s ) 令h 是v c 维为d 的假设空间。对在x 一l ，l 上 的任意概率分布d ，与，个随机样本集s 一致的任意假设空间h h 在s 上的误差以概率 l 一万不大于： p r r ( h ) 。e ( t ，h ，万) = 手( d l o g 了2 e l + l o g i 2 0 ) ( 1 3 ) d口 条件是d ，。，2 e 。 这一定理显示了对于无限假设集，过拟合的问题是可以避免的，所使用的复杂度的 度量正是v c 维。要保证好的泛化能力，在一致假设情况下训练样本的大小跟这个量呈 线性关系。 v c 理论为一致假设提供了分布无关下的一个泛化性界，由此还可以看出更紧凑的 武汉科技大学硕士学位论文第3 页 界是l o g 因子的，对于具有高v c 维的假设类存在输入概率分布要求学习器增大训练 集来获得好的泛化能力。可以看出v c 维刻画了p a c 意义上的学习能力将误差表 达为有限v c d i m ( h ) 的函数。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。遗憾的 是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道 其v c 维。比如在n 维实数空间中线性分类器和线性实函数的v c 维是n + l ，对于一些 比较复杂的学习机器( 如神经网络) ，其v c 维除了与函数集有关外，还受学习算法等的 影响，其确定更加困难。对于给定的学习函数集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学习理论中有待研究的一个问题。 1 2 2 推广误差边界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关 系，即推广性的界。关于两类分类问题的结论是，对指示函数集中的所有函数( 包括使 经验风险最小的函数) ，经验风险r 。( w ) 和实际风险r ( w ) 之间以至少l 一叩的概率满足如 下关系： r(叻蔓(w)+h(1n(2nh)圃+1)-in(r4) ( 1 4 ) 式中，h 是函数集的v c 维，疗是样本数。 这一结论从理论上说明了学习机器的实际风险由两部分组成：一部分是经验风险 ( 训练误差) ，另一部分称作置信范围，它和学习机器的v c 维h 及训练样本数打有关。 可以简单地表示为i l l ： r ( 忉s r 。( w ) + m ( 形疗) ( 1 5 ) 它表明在有限训练样本下，学习机器的v c 维越高( 复杂性越高) 则置信范围越大， 导致真实风险与经验风险之间可能的差别越大这就是为什么会出现过学习现象的原 因。机器学习过程不但要使经验风险最小，还要使v c 维尽量小，以缩小置信范围，才 能取得较小的实际风险，从而对未来样本有较好的推广性。需要指出，推广性的界是对 于最坏情况的结论，在很多情况下是较松的，尤其当v c 维较高时更是如此。而且，这 种界只在对同一类学习函数进行比较时有效，可以指导从函数集中选择最优的函数，但 在不同函数集之间比较却不一定成立。v a p n i k 指出i q ，寻找更好地反映学习机器能力的 参数和得到更紧的界是学习理论今后的研究方向之一。 第4 页武汉科技大学硕士学位论文 1 2 3 结构风险最小化归纳原则 从上面的结论看到，只考虑训练误差( 经验风险) 最小是不够的，需要同时最小化 经验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程就是调整置信 范围的过程，如果模型比较适合现有的训练样本( 相当于h n 值适当) ，则可以取得比较 好的效果。但因为缺乏理论指导，这种选择只能依赖先验知识和经验，造成了如神经网 络等方法对使用者“技巧”的过分依赖。 统计学习理论提出了一种新的策略【i “，即把函数集构造为1 个函数子集序列，使各 个子集按照v c 维的大小( 亦即。的大小) 排列，在每个子集中寻找最小经验风险，在子 集间折衷考虑经验风险和置信范围，以取得实际风险的最小，如图1 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 准 则。统计学习理论还给出了合理的函数子集结构应满足的条件及在s r m 准则下实际风 险收敛的性质1 1 1 。 风 一间 函数集子集： v c 维： s l c 是c s ， 0 b ) 当p l ，p 2 ，p 3 顺时针时，当且仅当s ( p l ，p 2 ，p 3 ) 0 d p 0 = s q r t ( ( x 3 - x 2 ) “2 + ( y 3 - y 2 ) “2 ) ； e l s e 山o = 1 0 0 0 0 0 0 0 0 0 0 0 用一个极大数表示没有交点 e n d d _ p 0 放在d _ p 0 数组中； e n d m i nd = m i n ( d _ p o ) ； i f m i n d = 1 0 0 0 0 0 0 0 0 0 0 0 调用顺时针旋转函数c l o c k w i s e ； e n d b e g i n _ p o i n t = n e w _ p o i n t ； 距离p 0 最近的点，即内凸包的起始点 n e w _ p o i n t = r d ( 1 ，2 ) ； s t a r tp o i n t = b e g i n _ p o i n t ； m a xn wp o s i t i o n = m i n _ d _ i x f i n t _ 1 s i t i o n ； x l = p o ( 1 ，1 ) ； y l = p 0 ( 1 ，2 ) ； x 2 = b e g i n _ p o i n t ( 1 ，1 ) ； y 2 = b e g i n p o i n t ( 1 ，2 ) ； 7 、w h i l e ( a l l ( n e w _ p o i n t = = s t a r t p o i n t ) ) 一0 武汉科技大学硕士学位论文第2 5 页 重复6 ： e n d 8 、输出最小内凸点并画图 3 5 算例 用本章的最小内凸包算法，对平面随机产生的9 类样本进行仿真。为了使算法有普 遍性，本算法把二维平面区域( 0 ，9 ) x ( o ，9 ) 平均分成9 个正方形区域，使得每个区域就是 一类样本。程序中各个类的区域固定，但各区域内的样本数和样本的位置是变化的，每 类用不同的符号来表示。 ( 1 ) 当某类位于整个区域的中心，即被其他类“包围”时，产生的样本集如图3 5 所示。图中，把位于区域( 3 ，6 ) ( 3 ，6 ) 的类标记为i ，i 的样本用右三角符来表示。此时， i 的最小内凸包如图3 6 所示。由图3 6 可以看出，i 的最小内凸包由6 类的内隔离线构 成，即类i 有6 个相邻类 图3 5 产生的9 类样本 第2 6 页武汉科技大学硕士学位论文 图3 6i 的最小内凸包 ( 2 ) 当某类位于整个样本区域的边缘时，不妨取图3 7 中的位于区域( o ，3 ) ( 0 ，3 ) 的样本为例，把这一类标记为j ，其样本用实心点来表示。则j 的最小内凸包如图3 8 所 示。由图3 8 可以看出，j 类只有2 个相邻类，只需计算这两类即可。 图3 7 产生的9 类样本 武汉科技大学硕士学位论文第2 7 页 图3 8j 的最小内凸包 为了说明本算法的适用性，文中再举当j 位于区域右边的情况。产生的样本集和j 的最小内凸包如图3 9 和图3 1 0 所示，此时的j 只有4 个相邻类。 由这些算例可以看出，对某一类使用最小内凸包算法时，可以分离出其不相邻类， 这样就可以在后续算法中较大程度的减少运算量，提高运算速度。 第2 8 页武汉科技大学硕士学位论文 图3 9 产生的样本集 图3 1 0j 的最小内凸包 武汉科技大学硕士学位论文第2 9 页 4 1 传统投票法 第四章最小内凸包在投票法中的应用 “一对一”分类方法首先是k n e r re t a l 提出的，该算法在多类训练样本中构造所有 可能的两类分类器，每类仅仅在多类中的两类训练样本上训练，结果共构造( n 1 ) n 2 个 分类器。用投票法来组合这些两类分类器，得票最多的类为新点所属的类。其算法如图 4 1 所示： 4 1 1 算法表述 图4 1 一对一算法示意图 假设训练样本集为：t = ( 一，y i ) ，( z 2 ，y 2 ) ，( x ，只) ) ，其中 工，r ”，y l 1 , 2 ，) ，i = 1 , 2 ，。“一对一”多类算法是对所有的( f ，_ ，) ， y j = i 和只= ，的样本点，基于这些样本点组成一个训练集： 毋i 2 ，抄一”+ c 喜掣 j ( 1 ，“) 7 中( 工一) + 舻l 一髟， 当儿= f ( w 9 ) 7 0 ( r ) + 6 ”s l + 善?当) - 。f 从训练集中抽取 ( 4 1 ) ( 4 2 ) ( 4 3 ) 第3 0 页武汉科技大学硕士学位论文 f ? 0 ， 得出决策函数，即判定x 属于第i 类或第j 类的分类器： 州= c 搿 其中 g ”( x ) = s f g n ( ( w ”) 7 中( x ) + 6 9 ) 4 1 2 算法过程 ( 4 4 ) ( 4 5 ) ( 4 6 ) 假如使用第i 类和第j 类样本训练出来的二值分类器为矿( 工) 。若g ”o ) 0 ，则样 本就属于第i 类，否则属于第j 类。分类过程如下：若待分类样本x 代入该分类器，如 果结果大于零，那么就对x 属于第i 类的可能性投一票，否则就对x 属于第j 类的可能 性投一票，照这样使用每个分类器对待分类样本x 进行求值、投票，最后样本x 属于哪 个类的投票最多，那么就说x 属于哪个类。 4 2 后验概率投票法 传统的支持向量机在决定样本的分类类别时，仅考虑两种极端情况，即属于某一类 的概率为l ，或者不属于某一类的概率为1 。p l a t t 4 7 1 引入概率，两类问题的概率建模 已经得到较好的解决。 4 2 1 后验概率投票法的算法表述 对于n 类分类问题，在“一对一”分类方法中，需要构造n ( n - 1 ) 2 个两类分类器， 即每任意两类构造一个支持向量机分类器。p l a t t 提出的两类问题的概率建模方法计算 测试样本在i 与j 两类中的后验概率，然后，结合n ( n - 1 ) 2 个两类分类器计算得到的 后验概率来确定样本在每个类中的最终后验概率。如何结合测试样本在n ( n 一1 ) 2 个两 类分类器中的后验概率，目前最常用、最简单的方法是m o r f i m t l j 的投票法，即在 n ( n 1 坨个两类分类器中计算测试样本在每类中后验概率的总和，则测试样本工属于第 i 类的最终后验概率为： 武汉科技大学硕士学位论文第3 1 页 p 坷( f _ ，；x ) p ( i x ) = 可出铲一 = 1 , 2 ，n ( 4 7 ) p 蛔( e ，；x ) - i ，1 1 i 其中，p 。o ，；x ) 表示由第f 类与第，类构成的两类支持向量机分类器，计算得到的z 属于 第i 类的后验概率。最后比较x 在各类的概率，谁的概率大，x 就在那一类。 在“一对一”多类问题的输出概率建模的投票法中，由于p , j ( i j ；x ) 仅仅是在第i 类与 第，类构成的两类支持向量机分类器中，则测试样本x 属于第i 类的概率，即可将 p 。( i l j ；x ) 看作为在第_ ，类的条件下，样本x 属于第f 类的条件后验概率。在统计每个 两类支持向量机分类器中，样本属于某类的后验概率之和时，没有考虑两类支持向量机 中另一类出现的概率情况，由式( 4 7 ) 得到的是一个近似的后验概率。为解决这种情况， 肖小玲，李腊元等提出了一种直接求解后验概率方法。利用 争争乩 ：n(n-1)(klj；x) ( 4 8 ) = 下 ( 4 8 ) k - ij - i 。j i 使得( 4 7 ) 变为 加h ) = 志，荟? _ ，( “m ) 扛l ，2 ( 4 9 ) 直接求解后验概率方法不仅具有更好的分类精度，还具有更好的概率分布形式，主 要表现在样本确定的类中具有较高的概率，而在其它类中的概率相对较低，这种概率分 布有利于解决当样本属于各类的概率出现相同时不易确定样本类别的问题。 然而，目前的投票法及其改进只是试图从提高分类精度上着手，运算量依然巨大。 4 2 2 分类器的设计方法 在文献 4 6 中。w u h b a 假设的后验概率的形式为 p ( y - l 厂) = d 嘉 ( 4 1 0 ) p ( y = - l f ) = 1 - p ( y = 1 力 ( 4 1 1 ) p l a t t l 4 1 1 把( 4 1 0 ) 的后验概率通用模式变通为含两个参数a 和b