（计算机应用技术专业论文）基于lssvm的多标签分类算法.pdf

摘要 摘要 分类是用训练样本建立的模型将测试样本分到一个或多个类中。传统的单标签 分类问题是假设类之间相互独立，一个样本仅能归为其中一类，而在实际应用中， 样本会和多个类相关联，需将样本同时归到多个类，这就是多标签分类问题。目前， 多标签分类算法的研究已经取得了很多成果，大致可分为算法有关和算法无关两大 类方法。算法有关的方法虽然没有改变数据的结构以及类与类之问的联系，但是由 于它需要花费大量时间去解优化问题，因此难于应用到较大规模的数据集。算法无 关的方法不需要考虑标签的相关性，因此易于实现，并且运行速度较快。从分解的 角度可将算法无关的方法分为一对一分解、一对多分解以及幂集法等。由于一对一 分解出的数据集规模比一对多要小，并且分解出的两类样本的数量更平衡，因此， 一对一分解策略更受科研人员的青睐。 本文采用一对一分解策略，将多标签分类问题分解成k ( k - 1 ) 2 个两类单标签和 两类双标签的分类子问题，对分解后的数据子集建立l s 。s v m 分类模型，当出现两 类单标签子问题时，使用传统的l s s v m 分类算法直接处理；当出现两类双标签时， 将同时拥有两个标签的样本看成混合类，并将标签值设为0 ，对新的数据子集再用 l s s v m 分类器进行处理。两类双标签建立的分类模型一般将分类阈值t 设为o 5 。 为了得到更佳的分类阂值，本文根据正类混合类、负类一混合类的数据分布分别求 得两个分类阂值，通过实验比较说明优化分类阈值能改善算法的性能。最后，利用 投票方法将测试数据分到一个或多个类中。 在算法的实验部分，本文归纳了不同的预测评价准则，并介绍四个基准的数据 集以及数据集标签的描述。对情感、景象、酵母和基因这四个数据集分别采用本文 的方法预测，对于参数y 和盯2 选择，l s s v m 模型采用网格搜索的方法，设定这两 个参数的可行区间，由计算机自动对各参数变量组合并逐一择优，使用留一法选取 最佳参数值。对情感数据集的预测结果说明，本文的方法在汉明损失、准确度、1 错误率以及排序损失上都有较好的结果，而其他几个评价标准也均列在前列；景象 数据集上的实验结果表明，本文的预测方法在汉明损失和查全率上具有较好的结 果；本文采用的方法在酵母数据集上有较高的查全率；而对基因数据集，现存的多 标签分类方法以及本文所采用的基于l s s v m 算法均有较好的预测效果。对本文的 算法和现存的多标签分类算法的比较结果显示，没有一个算法能够保证其预测结果 在所有的评价准则上都是最优的，但是本文的算法在某些性能上优于现有的算法。 关键词：l s s v m ，多标签分类，一对一分解策略，阈值选择 a b s t r a c t a b s t r a c t c l a s s i f i c a t i o ni sam e t h o dt h a tc l a s s i f i e sas a m p l ei n t oo n eo rm o r ec l a s s e su s i n ga m o d e lt r a i n e db yt r a i n i n gs a m p l e s t r a d i t i o n a ls i n g l el a b e lp r o b l e mi sb a s e do nt h e a s s u m p t i o nt h a tc l a s s e sa r ei n d e p e n d e n t ，a n do n es a m p l ec a no n l yb e l o n gt oo n eo ft h e s e c l a s s e s b u ti np r a c t i c a la p p l i c a t i o n ，o n es a m p l em a yb er e l a t e dt om u l t i p l ec l a s s e s ，t h u s i ts h o u l db ec l a s s i f i e di n t om o r et h a no n ec l a s s ，a n dw ec a l lt h i sp r o b l e mm u l t i l a b e l c l a s s i f i c a t i o n a tp r e s e n t ，t h er e s e a r c h e so fm u l t i l a b e la l g o r i t h m sh a v eo b t a i n e dm a n y a c h i e v e m e n t s ，w h i c ha p p r o x i m a t e l yc a l lb ed i v i d e di n t oa l g o r i t h md e p e n d e n ta n d a l g o r i t h mi n d e p e n d e n tm e t h o d s a l t h o u g ha l g o r i t h md e p e n d e n tm e t h o d sd on o tc h a n g e t h es t r u c t u r e sa n dr e l a t i o n sb e t w e e nc l a s s e s ，t h e yc o s tal o to ft i m es o l v i n go p t i m i z e d p r o b l e m a sar e s u l t ，i ti sh a r dt op u ta l g o r i t h md e p e n d e n tm e t h o d si n t ou s eo fl a r g e d a t a s e t s a l g o r i t h mi n d e p e n d e n tm e t h o d sc a nb e d i v i d e di n t oo n ev e r s u so n e d e c o m p o s i t i o ns t r a t e g y , o n ev e r s u sr e s td e c o m p o s i t i o ns t r a t e g ya n dl a b e lp o w e r s e t m e t h o d ，e t c o n ev e r s u sr e s td e c o m p o s i t i o ns t r a t e g yd e c o m p o s e sm u l t i l a b e lp r o b l e m i n t os e v e r a lb i n a r yc l a s ss i n g l el a b e ls u b p r o b l e m s ；w h i l eo n ev e r s u so n ed e c o m p o s i t i o n s t r a t e g yd e c o m p o s e sam u l t i - l a b e lp r o b l e mi n t os e v e r a lb i n a r yc l a s ss i n g l el a b e lo rb i n a r y c l a s sd o u b l el a b e lc l a s s i f i c a t i o ns u b - p r o b l e m sw h i c hc a nb es o l v e di n d e p e n d e n t l y b e c a u s eo ft h es i z eo fd a t ad e c o m p o s e db yo n ev e r s u so n ed e c o m p o s i t i o ns t r a t e g yb e i n g l e s st h a nt h a to fo n ev e r s u sr e s ts t r a t e g y , a n di t sa m o u n t so fs a m p l e sb e i n gm o r eb a l a n c e d t h a nt h a to fo n ev e r s u sr e s t ，o n ev e r s u so n ed e c o m p o s i t i o ns t r a t e g yi sw i d e l yu s e d a sar e s u l t ，o n ev e r s u so n ed e c o m p o s t i o ns t r a t e g yi sa d o p t e di n t h i sp a p e r f o r b i n a r yc l a s ss i n g l el a b e ls u b - p r o b l e m ，w eu s et r a d i t i o n a ll s s v mc l a s s i f i c a t i o n a l g o r i t h m ；f o rb i n a r yc l a s sd o u b l el a b e ls u b p r o b l e m ，w es e tt h ef u n c t i o n so fm i x t u r e c l a s sa sz e r oa n du s el s s v mc l a s s i f i c a t i o nt oh a n d l et h en e wm o d e l g e n e r a l l y , w es e t t h ec l a s s i f i c a t i o nt h r e s h o l dta s o 5 i no r d e rt og e tm o r ea c c u r a t ep r e d i c t e dr e s u l t s w e g of o rc l a s s i f i c a t i o nt h r e s h o l di na c c o r d a n c ew i t hp o s i t i v e m i x i n ga n dn e g a t i v e - m i x i n g d a t ad i s t r i b u t i o n a tl a s t ，w eg e tav o t et h r e s h o l db yt r a i n i n gs a m p l e sa n dc l a s s i f yt h e t e s t i n gd a t ai n t oo n eo rm o r ec l a s s e su s i n gt h i st h r e s h o l d a te x p e r i m e n t a ls e c t i o n ，s o m ew i d e l yu s e de v a l u a t i o nc r i t e r i af o rm u l t i l a b e l c l a s s i f i c a t i o na l g o r i t h m sa r es u m m a r i z e da n du s e di nf o u rb e n c h m a r kd a t a s e t s ，e m o t i o n ， s c e n e ，y e a s ta n dg e n b a s e m o s to fa l g o r i t h m sc h o o s et h ep a r a m e t e r s 厂a n d 口2 t h r o u g ht h em a n u a l ；w h i l el s s v mm o d e lu s e sa 鲥ds e a r c hm e t h o da n dt h e nt h e ya r e a u t o m a t i c a l l yc o m p u t e dt oc h o o s et h eb e s tp a r a m e t e rv a l u e s r e s u l t so nt h ee m o t i o n d a t a s e ts h o wt h a th a m m i n gl o s s ，a c c u r a c y ，o n ee r r o ra n dr a n k i n gl o s so fo u rm e t h o da l l h a v eb e t t e rp r e d i c t e dr e s u l t s ；s c e n ed a t a s e te x p e r i m e n t a lr e s u l t si n d i c a t et h a to u rm e t h o d i nt h eh a m m i n gl o s sa n dr e c a l lh a v eb e t t e rr e s u l t s ；o u ra p p r o a c hi ny e a s td a t a s e th a s h i g h e l r e c a l l ；t h ee x i s t i n gm u l t i 1 a b e l c l a s s i f i c a t i o nm e t h o d sa n do u ra l g o r i t h mi n g e n e b a s ed a t a s e ta l lh a v eb e t t e rp r e d i c t i o n k e y w o r d s ：l s 。s v m 。m u l t i 1 a b e lc l a s s i f i c a t i o n ，o n e v e r s u so n ed e c o m p o s t i o n s t r a t e g y , t h r e s h o l ds e l e c t i o n 第1 章绪论 第1 章绪论 随着时代的发展，计算机越来越智能化，对各种事物或现象的分析、描述、判 断和识别能力也越来越强。指纹识别、语音识别、人脸识别等技术的使用也越来越 普遍，而这些技术归根结底就是计算机模式识别中分类的能力。分类川是用训练样 本建立的模型将测试样本分到一个或多个类中。传统的单标签分类问题假设类问相 互独立，一个样本只能归为其中一类，而在实际应用中，样本会和多个类相关联， 需将样本同时归到多个类，这就是多标签分类问题。 本章就多标签分类的研究目的和意义、研究目标和方法分别做出介绍，最后对 论文的整体结构进行安排。 1 1 研究目的和意义 模式识别【i 捌是伴随着计算机的研究、应用发展起来的。模式识别的研究主要集 中在两个方面，一是研究生物体是如何感知对象的，这属于认识科学的范畴；二是 在给定的任务下，如何使用计算机实现模式识别的理论和方法，从而建立模式识别 系统。 我们设计分类器时根据样本是否需要带类别标签，将模式识别问题划分为有监 督的模式识别和非监督的模式识别。有监督的模式识别即分类川，其基本思想是根 据一批带有类别标签的样本集设计分类器，再判断新样本的类别。对于分类问题， 根据样本集合中总的类别个数，我们可将其分成两类分类问题和多类分类问题；根 据样本所含的标签数可将其分为单标签分类问题和多标签分类问题。 传统的单标签分类问题是假设类之间相互独立，一个样本仅能归为其中一类。 而在实际应用中，样本会和多个类相关联，需将样本同时归到多个类，这就是多标 签分类问题。例如，一幅侧重描绘山的山水画，传统的单标签分类就将其归为山类， 但是通过这种方法得出的分类结果不精确，不能很好地反映出这幅山水画的特性。 现实中存在的多标签分类问题还有很多，比较常见的一个问题就是文本的分 类，例如，我们可以通过计算机的多标签分类功能将网络博客划分为一个或多个话 题，如某篇文章可同时属于社会、情感、娱乐的类别；又如在生物信息学的基因分 析中，我们可以通过计算机的多标签分类算法预先估计基因所包含的功能，再进行 生物实验证实，这样就大大地降低了成本。 多标签分类问题是分类问题中比较复杂的问题，与两类分类问题不同，它允许 分类问题中有多个标签( 或称为类别) 存在；也不同于多类分类问题，它允许样本 第1 章绪论 可以同时属于多个类别。 由于多标签分类算法的研究是一个比较新的领域，目前没有一个算法能够保证 其预测结果在所有的评价准则上都是最优的，因此多标签分类成为备受关注的研究 热点和自订沿性课题，越来越多的科研人员也开始从事多标签分类问题的研究。 1 2 研究目标和方法 由于多标签分类问题的实用性和复杂性，越来越多的科研人员从事多标签分类 问题的研究。但是多标签分类问题的研究时i 日j 较短，技术不够成熟，需要不断地从 时间复杂度、空间复杂度、预测性能等指标上改进。本文主要从降低多标签训练复 杂度以及提高预测性能等方面对多标签分类算法进行研究。 传统支持向量机( 简称s v m ) 两类分类算法，其算法复杂度为o ( n 3 ) ，其中咒代 表样本点的数目，这导致了其计算复杂度随着样本集合的增大迅速增加。最d - 乘 支持向量机( 简称l s s v m ) 建立的分类模型将s v m 优化问题的不等式约束变为等式 约束，因此能够降低其复杂度。获得l s s v m 模型仅仅需要求解一个线性方程组， 其复杂度为o ( n ! ) 1 3 】，且其预测性能不亚于s v m 。 本文采用一对一分解策略，对分解好的数据子集使用l s s v m 建立子分类器， 并将每个子分类器的分类阈值都置为0 5 ，为了得到更精确的预测结果，本文对两 类的分类阈值进行优化，结果表明，对分类阈值优化得出的预测结果优于固定分类 阈值的预测结果。 本文研究方法如下：首先查阅大量国内外有关多标签分类、l s s v m 和阈值选 择等文献资料以及相关书籍，了解与掌握这方面的研究动态。针对不同算法的不足， 提出新的方法应用到多标签分类中，并对其改进，降低其训练复杂度以及提高其预 测性能，使预测结果的性能更精确。最后，将本文所采用的方法应用到不同的基准 数据集中，使算法的性能更具有说服力，并观察实验结果，对其进行理论分析。 1 3 论文结构安排 本文共分六章，组织结构如下： 第一章介绍论文的研究目的、研究方法以及文章的组织结构。 第二章对多标签分类方法按照与算法有关和与算法无关的方法进行分类，并 介绍多标签分类的常用方法。 第三章介绍统计学习理论的知识、s v m 以及l s s v m 的基本原理，并比较 s v m 和l s 。s v m 。 2 第1 章绪论 第四章提出两类双标签l s s v m 的模型以及两类分类的阈值选择，接着介绍 多标签分类算法的流程及性能度量。 第五章实验部分，首先介绍数据集的相关信息，对四个基准数据集进行固定 阂值和动态阈值的比较，并与其他多标签分类算法进行比较，最后对结果分析。 第六章总结全文，指出本文基于l s s v m 多标签分类算法的不足，并对今后 进一步的研究工作提出了一些设想。 第2 章多标签分类算法 第2 章多标签分类算法 多标签分类问题【4 ，5 1 是分类问题中比较复杂的问题，它允许分类问题中存在多个 类别，由于多标签分类问题的实用性及复杂性，引起了人们的研究兴趣。多标签分 类算法大致可分为与算法有关和与算法无关【6 1 两类方法。 2 1 与算法有关的方法 与算法有关的方法顾名思义就是对特定算法进行改进。在与算法有关的方法 中，要求建立一个最优化问题来处理所有的样本，这些样本可拥有多个标签。根据 建立的最优化的问题不同，与算法有关的方法有多种形式。 2 1 1 决策树多标签算法 决策树多标签算法c 4 5 【7 1 需要使用一个支持多类的信息熵： l | e n t r o p y ( s ) = 一互( ( p ( c i ) l o gp ( c i ) ) + ( q ( c i ) l o g q ( c i ) ) ) ( 2 1 ) l 一1 其中k 为标签的个数，p ( c f ) 为样本属于标签e 的概率，g ( q ) = 1 一p ( c i ) 为样本不 属于标签c i 的概率。该算法允许叶子节点是某一组标签的集合，即拥有多个标签。 因为需要使每一种可能的标签组合都必须有一个叶子节点与其相对应，因此使用这 种方法的一个缺点是叶子节点可能会很多。 2 1 2 多标签支持向量机 多标签支持向量机是最大化边界和最小化排序损失的分类器，很多多标签分类 算法都使用了支持向量机( s v m s ) s - 1 0 】，如r a n k s v m 、m m l 等。 r a n k s v m 算法】是e l i s s e e f f 和w e s t o n 提出的采用s v m 的思想实现的多标签 分类算法，它是以s v m 为基础，使用了结构风险最小化的原则，通过最大化间隔 和最小化经验风险来使置信区间最小化；最大化间隔标签算法( 简称m m l ) e 1 2 】也是 s v m 形式的多标签分类算法，其基本思想与r a n k s v m 算法类似，只是对经验风 险的估计有所不同：m m l 算法的损失函数用一般的样本错分的程度表示；而 r a n k s v m 算法则是使得排序损失最小，但在实际应用中如果标签数或样本数较大 时，r a n k s v m 将会导致产生的二次优化问题过于巨大而难以计算。 2 1 3 多标签k 近邻算法 多标签k 近邻算法( 简称m l k n n ) t 1 3 】是以k 近邻算法为基础，在训练阶段，首 4 第2 章多标签分类算法 先计算已知样本的先验概率，以及表示相邻样本属于某个样本的个数的条件概率； 在测试阶段，使用贝叶斯规则计算样本的后验概率，最后通过后验概率来确定样本 是否属于某个标签。由于条件概率是在训练样本的一个统计值，因此对于无法保证 独立同分布的某些样本来说，其准确性不确定。 2 1 4a d a b o o s t m h 和a d a b o o s t m r 这两种方法都是多标签数据的a d a b o o s t 1 4 】方法的推导形式。a d a b o o s t m h 通 过最小化汉明损失设计分类器，它为含有k 个标签的，个训练样本分别设置权值， 初始状态时权值是相同的。通过不断迭代改变权值，加大难于分类的样本权值，减 小易于分类的样本权值。最后使用这些权值预测新的样本所具有的标签； a d a b o o s t m r 用于为样本所具有的标签排序。a d a b o o s t 算法及其推导形式存在一个 共同的问题，即它们不是基于结构风险最小化原则的算法，很难控制其算法的复杂 度，因此易于导致过学习的问题。 2 1 5 多标签最大化熵算法 多标签最大化熵算法( 简称m l m e ) t 1 5 】不仅考虑样本与标签之| 日j 的关系，同时还 考虑标签与标签之间的关系，并且它还使用了一个正则化参数柬调整经验j x l 险和实 际的分布，从而避免产生过学习的情况。但是这种方法主要缺点是样本的分布函数 难以计算，只能用直方图的方法求其近似值。 与算法有关的方法优点是没有改变数据的结构，也没有破坏类间的联系；但它 的缺点主要是最优化问题规模过于巨大，需要大量的计算时问。 2 2 与算法无关的方法 与算法无关的方法是将多标签问题转化成一系列的单标签问题，因此与算法无 关的方法也可称为问题转化法。根据转化角度可将多标签分类算法分为基于标签转 化法和基于样本转化法f 1 6 】。 2 2 1 基于标签转化的多标签分类算法 基于标签转化法【1 7 】是将多标签数据分解成多个单标签数据的问题，对分解好的 单标签数据采用传统的两类分类方法解决。表2 1 是一个多标签数据，该数据集引用 自文献 1 8 】。 5 第2 章多标签分类算法 表2 1 多标签数据 样本标签集 l ，五) 2 五，以) 3 丑) 4 五，五，五 一对多算法( 在文献 1 2 】以及 1 9 中也称为两类相关法) 是典型的基于标签的转 化法，它是指将具有k 个标签的数据集分解成k 个两类分类器，但是每一个分类器 中都要包含所有的样本，以表2 1 为例，一对多算法根据四个标签丑，无，五，丑将多标 签数据分解成四个两类分类器，例如，第五个分类器能够将包含丑标签的样本作为 f 类，而不包含元的样本作为负类，分解结果如表2 2 所示。使用一对多算法将多 标签问题分解后，需要在训练阶段选择合适的阈值，最后在测试阶段决定测试样本 的类别。常见的方法为投票法：对于某个样本，它的投票数大于阈值的标签集合就 为该样本的预测标签。一对多算法的前提是假设样本的标签之间是独立，但在实际 应用中，标签f n j 往往并不独立，忽略标签间的相关性所得到的性能结果并不一定好。 一对一算法也是基于标签的，该算法的思想是将具有k 个标签的数据集，使用 任何两个标签构造分类器，每一个分类器仅对含有这两个标签的样本进行分类，这 样的两两配对共有g ( 即k ( k - 1 ) 2 ) 种可能的情况，因此需要设计“1 ) 2 个分类器， 故表2 1 中多标签数据将分解成六( c ：= 4 x 3 2 ) 个两类分类器，例如，第 一无个分 类器能够将包含 一无的标签样本进行分类，含有丑的样本作为正类，不含有见的 样本作为负类，分解方法如表2 3 所示。使用一对一算法将多标签问题分解后，与 一对多算法一样，也需要选择合适的阈值，最后对测试样本进行分类。由于一对一 算法所产生的子问题较小，因此它适用于规模较大，但标签数目较小的数据集。 表2 2 一对多算法示意图 标签正类 负类 l ，32 ，4 允4l ，2 ，3 五 2 ，4l ，3 五 l ，2 ，43 6 第2 章多标签分类算法 表2 3 一对一算法示意图 标签上e 类负类混合类 a 一五 l ，3 4 丑一五 1 ，32 ，4 一以 32 ，4 l 五一五 24 五一五 l ，24 以一五 l 2 ，4 2 2 2 基于样本转化的多标签分类算法 基于样本转化法是重新定义样本的标签集，将原始的多标签问题转化为一个或 多个单标签问题。和基于标签转化法不同，基于样本转化法既会产生单标签分类子 集也会产生多类分类子集。有三种基于样本转化法：忽略法、重新构造新标签法和 多标签转化为单标签样本法。 1 忽略法【2 0 】是忽略所有多标签的样本，仅保留含有单个标签的样本。很显然， 这种方法虽然分类速度快，但是大大降低了算法预测的币确性。表2 4 是表2 1 忽 略多标签数据中多标签样本后的数据。 表2 4 忽略法示意图 2 重新构造新标签法将所出现的多标签集合作为一个新的标签，如表2 5 所示。 该方法典型的算法有标签幂集法( 简称l p ) 、剪枝转化法( 简称p p t ) 、随机k 标签法( 简 称r a k e l ) 等。l p 2 1 】是一个简单并且有效的问题转化方法，它为所有样本标签的可 能组合都建立单标签分类器。表2 6 是表2 1 用标签幂集法后的新样本集。p p t 2 2 1 是在标签幂集法基础上改进，将出现次数较少的标签集r 这里定义一个阈值，小于该 阈值的标签集) 直接被剪枝。r a k e l 2 3 】将样本标签组合中含k 个标签的子集作为新 的单标签问题。 7 第2 章多标签分类算法 表2 5 重新构造新标签法示意图 样本标签 1 岛，岛= a ，五 2 b ，0 2 = 乃，五) 3 4 b ，岛= 五，五，五) 表2 6 标签幂集法示意图 标签样本 标签样本 3 五， 无 如。 五五。 2 无 丑2 4 丑2 3 4 ， 五3 4 4 丑。 l 晶4 3 多标签转化为单标签样本法又可分为简单法和分解法两种方法。 简单的多标签转化为单标签样本法又可分为选择转化法、选择最大( 最小) 转化 法i l8 j 等。选择转化法是在多个标签中任意选择一个标签作为样本的新标签，如表2 7 所示。选择最大( 最小) 转化法是将多个标签中最后( 第一个) 的标签作为样本的新标 签，如表2 8 和2 9 所示。 表2 7 选择转化法表2 8 最人选择转化法表2 9 最小选择转化法 样本标签 l 无 2 五 3 丑 4 五 样本标签 1 丑 2 五 3 五 4五 分解的多标签转化为单标签样本法【1 8 1 是将七个标签，个样本的数据集分解成所 个单标签问题。其中m 的取值范围为l 一( 后一1 ) 7 。如果每个样本均只有一个标签， 则胁取1 ；若每个样本均有后一1 个标签，则，z 取( 七一1 ) 7 。分解的多标签转化为单标 签样本法又可分为加性方法和乘性方法。加性方法是将多标签样本中每个可能标 签依次作为正类考虑，需建立f ( t 一1 ) 个分类器，其中k i 为第f 个样本的标签数； 8 第2 章多标签分类算法 乘性方法2 5 1 是根据样本标签分解为所有可能的单标签分类器，因此需建立兀忍个分 类器。 多标签分类算法的分类的层次结构如图2 1 所示。 多标签方法 一 ， 算法无关 算法相关 1 【 i s v m s 决策树 其他方法 基于样本基丁标签 忽略法转化法产生标签法 一对一分解一对多分解 简单转化法分解转化法 加性方法乘性方法 图2 1 多标签分类算法的分类 本文采用一对一分解策略，它将分类问题分解成k ( k - 1 ) 2 个两类单标签和两类 双标签的分类子问题，这种分解策略属于上述多标签分类算法中基于标签的分类算 法，其示意图如图2 2 所示。 9 第2 章多标签分类算法 图2 2 一对一分解示意图 l o 第3 章支持向量机 第3 章支持向量机 传统的统计模式识别方法的前提是样本数目足够多，最好是样本数量趋于无穷 多。但是在实际应用中，样本的数目不可能是无穷多，因此很多基于统计的模式识 别方法很难取得理想的效果，达到理论上的性能。为了解决小样本的学习问题，从 最小化经验风险和最小化有序风险的基础上发展出一种专门针对小样本的统计理 论统计学习理论 2 6 , 2 7 1 ，它为研究有限样本情况下的统计模式识别和更广泛的机 器学习问题建立了比较好的理论框架，并在其基础上发展了s v m 的模式识别方法。 s v m 在解决高维非线性小样本问题中表现出许多的优势，并能够很好地推广应用 到函数拟合等其他机器学习问题中。 s v m 有完美的数学形式、直观的几何解释和良好的泛化能力，同时能够处理 模型选择与欠学习、过学习以及非线性等问题，避免在学习过程中产生局部最优解， 有效克服了“维数灾难”，并且人为设定的参数较少，便于使用。由于以上的优点， s v m 已成功应用于许多分类、识别和回归等问题中【2 8 。3 0 1 。 本章首先介绍统计学习理论的相关知识，接着重点介绍s v m 的理论基础以及 s v m 和l s s v m 模型，最后比较s v m 和l s s v m 两种方法的优缺点。 3 1 统计学习理论 目前，统计学习理论被公认是解决小样本统计和预测学习的最佳理论。本段就 统计学习理论进行介绍，该段的内容主要引用和参考于文献 1 】。 3 1 1 机器学习问题表示 机器学习的目的是根据给定的训练样本输入输出之间依赖关系的估计，来对未 知样本做出尽可能准确的估计。机器学习问题的基本模型可用图3 1 表示。其中系 统s 是我们研究的对象，当给定某个输入x 后能得到输出y 。 图3 1 机器学习的基本模型 机器学习问题就是根据，z 个独立同分布观测样本 第3 章支持向量机 ( 一，乃) ，( 恐，y ：) ，( ，只，) ， ( 3 1 ) 在一组预测函数集 f ( x ，力) 中求得一个最优的函数f ( x ，) ，使得预测的期望风险 r ( ) = i l ( y ，f ( x ，c o ) ) d f ( x ，j ，) ( 3 2 最小。其中国q 是函数的广义参数；l ( y ，f ( x ，曲) 表示用f ( x ，c o ) 对y 进行预测所造 成的误差损失，f ( x ，y ) 是输入向量x 和期望向量y 的联合概率分布。 显然，要使式( 3 2 ) 的期望风险最小化，就必须依赖x ，y 的联合概率f ( x ，y ) ， 在模式识别问题中也就是必须己知类的先验概率以及类的条件概率密度函数。但是 在实际问题中，我们可以利用的只有已知样本的信息，无法得到类的先验概率和类 的条件概率密度，因此不能直接计算期望风险并最小化。 根据概率论中的大数定理，自然想到用算术平均代替式( 3 2 ) 中的数学期望， 即使用 g e m p ( 0 ) ) = 1 l ( y i ，厂( ，国) ) ( 3 3 ) r ，= i 来逼近式( 3 2 ) 所定义的期望风险。由于毽。( ) 是用已知的训练集( 即经验数据) 定义的，因此称作经验风险。这种用求经验风险r 。( 国) 的最小值代替求期望风险 月( 缈) 的最小值的方法，就是经验风险最小化( 简称e r m ) 原则。 3 1 2 一致收敛和v c 维 学习过程的一致性收敛条件，是指经验风险的最优值当训练样本的数目趋向无 穷大时能够收敛到真实风险的最优值。因此，只有满足一致性收敛条件，才能保证 当样本无穷大时，通过经验风险最小化原则下得到的最优方法趋向于使期望风险最 小的最优结果。 经验风险和期望风险的这种关系，可以用图3 2 表示。 尺( ) 图3 2 经验风险和期望风险的关系示意图 1 2 第3 章支持向量机 为了研究学习过程一致收敛，统计学习理论定义了有关函数集学习性能的指 标，其中最重要的是v c 维。假设一个样本集有h 个样本，若存在一个函数集，该 函数集中的函数能够把h 个样本按照所有可能的2 6 种形式分成两类，则称该函数集 能够把样本数为h 的样本集打散。函数集的v c 维就是它所能打散的最大样本数。也 就是晚，如果存在h 个样本的样本集能够被函数集打散，而不存在有h + 1 个样本集 能被函数集打散，则函数集的v c 维就是h 。指示函数集的v c 维就是用这个函数集 中的函数所能够打散的最大样本集的样本数目。如果对于任意的样本数，总能找到 一个样本集能够被这个函数集打散，则函数集的v c 维就无穷大。有界实函数的v c 维可以通过用一定的阈值将它转化成指示函数来定义。 3 1 3 结构风险最小化 根据统计学习理论，经验风险和实际j x l 险之问存在以概率1 7 7 的关系 月( ) 如。( 缈) + j h ( 1 n ( 2 n h ) + 1 - i n ( r 4 ) ( 3 4 ) -， 其中，h 是v c 维，n 是样本数。 从式( 3 4 ) 可以看出，学习机器的真实风险是由经验风险和置信区间两部分组 成，它和学习集的v c 维以及训练样本数目有关。可以简单表示为 r ( o ) 如，( ) + ( 等) ( 3 5 ) 式( 3 5 ) 表日f l ，在有限训练样本情况下，即使如。( 缈) 较小，也不能保证真实风险 r ( r o ) l 权得最小值。 e r m 准则只最小化经验风险( 即训练误差) ，并没有最小化置信范围值，因此基 于e r m 准则的学习方法的学习能力强，但是其泛化能力较差，容易出现过学习的 现象。过学习现象产生的原因主要有两个：一是由于训练过程中学习样本不充分； 二是学习机器的设计不合理，这两个问题一般都是互相关联的。在神经网络中，对 于有限的训练样本，若网络的学习能力非常强，因此可以记住每一个训练样本，此 时的经验风险就可以收敛到零，但是我们却不能保证它对未知样本也有好的预测性 能。为了最小化经验风险的同时也能最小化置信范围，可以将函数集构造为一个按 照v c 维大小排列的函数子序列，在每个子集中寻找最小经验风险，在子集间折中 考虑经验风险和置信范围，使得取到的实际经验风险最小。这种基于统计学习理论 的思想称为结构风险最小化或有序风险最小化( 简称s r m ) ，如图3 3 所示。图中函 数子集scsc ，v c 维扛啊织。 第3 章支持向量机 风险 3 2 支持向量机原理 图3 3 结构风险最小化 s v m 算法【3 l 】。【3 4 】是结构风险最小化思想的具体体现，它与神经网络等传统方法 以训练误差最小化作为优化目标不同，它以置信范围值最小化作为优化目标。其实 质上是求解一个凸规划问题或者其对偶问题即二次规划( 简称q p ) i h i 题。 s v m 学习的目标是构造一个判别函数，将测试数据尽可能正确地分类，其示 意图如图3 4 所示。 图3 4 支持向餐机示意图 1 4 x = ( x 一，x ：，) 第3 章支持向量机 假定大小为，的训练样本集x = ( 一，x 2 ，西) ，薯r ，由两个类别组成， y = ( 乃，y 2 ，乃) 。如果样本属于第l 类，则将其标记为正类护1 ) ；如果属于第2 类，则将其标记为负类产1 ) 。 3 2 1 线性可分的标准分类面 如果存在分类超平面 缈x + b = 0 ( 3 6 ) 使得均有 w x + 6 l ，：1( 3 7 ) ，。t w 蕾+ 6 一1y i = 一1 则称训练集x 是线性可分，其中w x 表示向量m ，r 7 与x e r 7 的内积。公式( 3 7 ) 可以 写成如下形式 y j ( w 一+ 6 ) 1 ，i = 1 ，2 ， ( 3 8 ) 由统计学习理论知，如果训练样本能够被超平面完全分开，并且距超平面最近 的样本数据与超平面之间的距离最大，则该超平面为最优平面，如图3 5 所示，由 此得到的判别函数，其泛化能力最优。 图3 5 线性最优分类超平面 超平面 最优超平面的求解需要最大化2 ( w ) ，即最小化( 矽，) 2 ，这样可将线性分 类问题转换成如下的二次规划问题 m i n ，、1 ( w ，) ( 3 9 ) 二 s j y f ( w x f + 6 ) l ，i = 1 ，2 ， 这个二次规划是一个线性约束下的凸二次式优化问题，为了求解( 3 9 ) ，可将其转 换为对偶形式进行求解。 1 5 第3 章支持向量机 根据v a p n i k 1 】等的分析，判定分类面函数的v c 维存在如下定理：假设训练样 本完全包含在一个最小直径为尺的球内，则满足条件( m ，m ，) c 的分类面函数的v c 维h 满足 h m i n ( r 2 c 】，d ) + l( 3 1 0 ) 可见，s v m 通过尽可能减小式( 3 1 0 ) ，实现对v c 维大小的控制，降低其模型 复杂度。 3 2 2 线性不可分的广义分类面 最优的分类面是在线性可分的6 仃提下讨论的，当某个分类为线性不可分时，即 某些训练样本不能满足式( 3 9 ) 的条件，可以在条件中增加一个非负松弛项 毒，i = 1 ，2 ，来调整约束条件。线性不可分的广义分类超平面如图3 6 所示，其最优 化问题变为式( 3 11 ) 。 图3 6 线性不可分的广义超平面 面 m m 三( w w ，) + 茎杰参 ( 3 1 1 ) s f y f ( ，x i + 6 ) l 一缶 缶o ，i = 1 ，2 ， 其中y 为惩罚因子，它是分类误差与类别间距之间的折中。一般需要根据实验， 找到合适的7 值，y 值越大表示对错误分类的惩罚越大。采用l a g r a n g e 乘子法求解 这个具有线性约束的二次规划问题，即 m i n = 三( w ”，) + 兰兰缶一i 圭= 1 口，【 ( w x i + b ) 一1 + 参 一毫，缶 3 _ 2 s j 岛，口f ，f o ，i = 1 ，2 ， 其中口，以为l a g r a n g e 乘子，分别求出l a g r a n g e 函数关于w ，b ，誊的偏导数， 1 6 第3 章支持向量机 并令它们为零，由此得到 等= w 一喜口彤x ，= 。jw = 荟i 口彤一 鲁= 一善i 哪= 。善1 啾= 。 ( 3 1 3 ) ( 3 1 4 ) 等中q 一一= 。+ 以= 7 ( 3 1 5 ) 将式( 3 1 3 ) - ( 3 1 5 ) 代入公式( 3 1 2 ) ，得到其对偶最优化问题 m a x 厶= 哆一去q 哆咒乃( 薯- x j ) s j o q 7 ( 3 1 6 ) 呸y ；= 0 最优化求解( 3 1 6 ) 得到的可能有如下三种情况：( 1 ) a = 0 ；( 2 ) o q y ； ( 3 ) 0 6 = 7 。其中第一种情况的置属于非支持向量，后两者的毛为支持向量( s v ) ，三 种情况的示意图如图3 7 所示。 图3 7 支持向量与非支持向量 支持向量所对应的薯称为边界支持向量( b s v ) ，实际上是错分的训练样本点。 第( 2 ) 种情况表示正确分类的样本，第( 3 ) 种情况表示错误分类的样本。 1 7 第3 章支持向量机 根据k a r u s h k u h n t u c h e r 条件( k k t ) 矢h ，在最优点上，l a g r a n g e 乘子与约束的 积为0 ，