（计算机应用技术专业论文）基于双标签支持向量机的快速多标签分类算法.pdf

摘要 摘要 分类问题是指通过对已知类别的样本集的学习，来预测未知类别样本的问 题。对于分类问题而言，根据样本集合所拥有的标签数，可分为两类问题和多类 问题；而按样本所拥有的标签数，可分为单标签分类问题和多标签分类问题。这 里所说的多标签分类问题，是指一个样本可以同时拥有多个标签或者一个样本同 时属于多个类别。在实际生活中，多标签问题越来越多的得到人们的广泛关注和 认可，例如，蛋白质分类、文本分类和景观分类等。目前，广泛使用的处理多标 签问题的方法有基于数据分解的方法和基于单个优化问题的方法。 对于多标签分类问题，采用“一对一”的分解策略与支持向量机相结合的算 法已经逐渐成为一种行之有效的处理方法。但如何提高算法的训练和测试的效率 却仍然是一个富有挑战性的课题。为了提高多标签分类算法的效率，本文推广经 典两类支持向量机提出了一种两类双标签支持向量机。在算法中，将同时拥有正 类标签和负类标签的样本看作为双标签样本，将双标签样本置于正类样本和负类 样本的中间区域。我们采用投票策略集成子分类器设计出快速多标签分类算法。 本文中基于双标签支持向量机的快速多标签分类算法通过用著名的s v m g m 算法 来实现。 在算法的实验部分，本文归纳了一些常用的多标签分类算法的评价准则，并 在四个基准数据集酵母数据集、景观数据集、情感数据集和基因数据集上来进行 实验，并通过与现存的一些多标签分类算法在分类性能上的比较得出，没有一个 多标签分类算法在所有的评价准则上均保持最优，而我们的算法无论是在哪个基 准数据集上，总体上均居于前列，这说明我们的算法总体性能良好。在算法的训 练时间上，我们将我们的算法与其他两个基于支持向量机的分解算法以及基于三 类支持向量机的快速多标签分类算法进行比较，对于景观与情感数据集，我们的 算法的运行效率是这三种算法的3 倍以上。因此，本文所提出的算法具有良好的 运行效率。而在能够决定测试时间的支持向量个数上，我们的算法在标签总数较 少的数据集上也具有很大优势。 关键词：多标签分类，支持向量机，“一对一的分解策略 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 np r o b l e mi st ol e a r nam o d e lb ys o m ek n o w ns a m p l e sa n dt h e nt o p r e d i c tt h es a m p l e sw h o s el a b e l sa r eu n k n o w nb yt h i sm o d e l f o rt h ec l a s s i f i c a t i o n p r o b l e m s ，t h e yc a nb ed i v i d e di n t ob i n a r ya n dm u l t i c l a s sc l a s s i f i c a t i o np r o b l e m s b a s e do nt h en u m b e ro fd i f f e r e n tc l a s s e si nt h es a m p l es e t so rd i v i d e di n t os i n g l el a b e l a n dm u l t il a b e lc l a s s i f i c a t i o np r o b l e m sb yt h en u m b e ro fs a m p l el a b e l s as a m p l ec a n b e l o n gt os e v e r a ld i f f e r e n tc l a s s e si nam u l t i l a b e lp r o b l e m n o w a d a y s ，m u l t i l a b e l c l a s s i f i c a t i o nm e t h o d sa r ei n c r e a s i n g l yr e q u i r e db ym o d e r na p p l i c a t i o n s ，s u c ha s p r o t e i nf u n c t i o nc l a s s i f i c a t i o n ，t e x tc a t e g o r i z a t i o na n ds e m a n t i cs c e n ec l a s s i f i c a t i o n w i t ho n e - v e r s u s o n ed e c o m p o s i t i o ns t r a t e g y , am u l t i l a b e lc l a s s i f i c a t i o np r o b l e mi s a l s od e c o m p o s e di n t os e v e r a lb i n a r ys i n g l el a b e lo rb i n a r yd o u b l el a b e lc l a s s i f i c a t i o n s u b p r o b l e m sw h i c hc a nb ed i s p o s e di n d e p e n d e n t l y a tp r e s e n t ，t h ew i d e l yu s e d m e t h o d so fd e a l i n gw i t hm u l t i - l a b e lp r o b l e m sa r eb a s e do nd a t ad e c o m p o s i t i o n m e t h o d so ras i n g l eo p t i m i z a t i o np r o b l e m c o m b i n i n go n e - v e r s u s - - o n ed e c o m p o s i t i o ns t r a t e g yw i t hs u p p o r tv e c t o rm a c h i n e h a sb e c o m ea ne f f i c i e n tm e a n sf o rm u l t i l a b e lc l a s s i f i c a t i o np r o b l e m b u th o wt o s p e e du pi t st r a i n i n ga n dt e s tp r o c e d u r e si ss t i l lac h a l l e n g i n gi s s u e i nt h i sp a p e r , w e g e n e r a l i z et h ep r i m a r yb i n a r ys u p p o r tv e c t o rm a c h i n et oc o n s t r u c tad o u b l el a b e l s u p p o r tv e c t o rm a c h i n et h r o u g hl o c a t i n gd o u b l el a b e li n s t a n c e sa tm a r g i n a lr e g i o n b e t w e e np o s i t i v ea n dn e g a t i v es a m p l e s ，a n dt h e n d e s i g n af a s tm u l t i - l a b e l c l a s s i f i c a t i o n a l g o r i t h mu s i n gt h ev o t i n gr u l e t h ea l g o r i t h mi n t h i s p a p e r i s i m p l e m e n t e db yt h ek n o w na l g o r i t h ms v m l i g h t a tt h ee 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 t i l i z e di nt h ee x p e r i m e n to ff o u r b e n c h m a r kd a t a s e t sy e a s t ，s c e n e ，e m o t i o na n dg e n b a s ei nt h i st h e s i s c o m p a r e d 谢m s e v e r a le x i s t i n gm u l t i l a b e lc l a s s i f i c a t i o na l g o r i t h m s ，n o n eo ft h e mc a na c h i e v et h e b e s ta ta l le v a l u a t i o nc r i t e r i a t h ep e r f o r m a n c eo fo u ra l g o r i t h mi sb e t t e rt h a nt h a to f o t h e re x i s t i n gm u l t i l a b e lc l a s s i f i c a t i o na l g o r i t h m so nf o u rb e n c h m a r kd a t a s e t s o n t h es c e n ea n de m o t i o nd a t a s e t s ，o u ra l g o r i t h mr l l n st h r e et i m e sa sf a s ta so t h e rt w o a l g o r i t h m sw h i c ha r ea l s ob a s e do ns u p p o r tv e c t o rm a c h i n ea n dt h ea l g o r i t h mo n t r i p l ec l a s ss u p p o r tv e c t o rm a c h i n e o u ra l g o r i t h mc a l lo b t a i nt h em i n i m a ls u p p o r t v e c t o r sw h i c hc a nd e t e r m i n et h et e s t i n gt i m e k e y w o r d s ：m u l t i l a b e lc l a s s i f i c a t i o n ，s v m ，o n e - v e r s u s - o n ed e c o m p o s i t i o ns t r a t e g y 第1 章绪论 第1 章绪论 分类是人类最重要的基本活动之一，在人们的同常生活、社会活动以及科研 工作中，无处不在的存在着分类问题。分类问题是模式识别的基本问题之一。分 类的复杂性在于，不存在纯客观的分类标准也不仅仅是单纯的数学问题，因为任 何分类都是带有主观性。随着人们对分类问题的进一步细化，又可以划分为单标 签分类问题和多标签分类问题，单标签分类问题认为一个样本仅仅属于一个类别 ( 或标签) ，而多标签问题认为一个样本可以属于多个类别( 或标签) 。 1 1 研究背景及意义 分类1 1 3 j 是模式识别的核心内容之一，它的目的是找出一组能够描述数据集 合典型特征的模型或函数，以便能够识别未知数据的归属和类别。单标签分类假 定类之间是相互排斥的，并且每个样本只属于一个类；相反，多标签分类是指类 别之间并非相互排斥而是相互关联的。多标签分类问题的研究工作始于互联网和 媒体的需求。例如，一篇新闻报道，如果从不同的角度分析，就可以将其分到不 同的类别中，即一篇新闻报道既可以看作是政治类的，也可以划分到经济类或者 体育类中去；还有一个比较常见的问题是电影分类问题，电影的类别有很多种， 如：喜剧、动作、科幻和文艺等，一部电影也可以同时拥有多个类别；在风景图 像分类【4 儿5 】中，一个图像可以拥有多个主题，如树林、海滩和山峰等等。例如， 图1 1 所示，a ) 中的景观图像主题包括蓝天和白云，而b ) 中的景观图像主题包括 蓝天、树林和白云，这两幅图像均是多标签景观图，拥有两个或以上的类别标签。 目前，由于计算机和信息技术的快速发展，人们丌始越来越重视多标签分类 问题的研究。例如，多标签分类算法在生物基因掣6 】【7 】方面的应用，可以通过计 算机的多标签分类算法预测基因所拥有的功能，然后再进行生物实验，这样可以 大大降低成本。相信随着世界总趋势由单一向多元化方向发展，多标签问题的应 用将会越来越广。 第1 章绪论 a ) 蓝天+ l h 图1 1 多标签实例 b ) 监大+ 树林+ 公路 支持向量机【3 l ( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 是由v a p n i k 在19 9 5 年提出的， 是一种基于统计学习理论的新型的通用学习方法，它建立在学习理论的v c 理论 。3 】和结构风险最小化原理 1 _ 3 】的基础上，根据有限样本信息在模型的复杂性( 即 对特定训练样本的学爿精度) 和学习能力( 即无错误的识别任意样本的能力) 之 问寻求最佳折衷，以期望获得更好的泛化能力。其基本思想是首先通过非线性变 换。3 j j 各输入空间映射到一个高维特征空f n j ，然后在这个新空倒中求取最优线性 分类面，而这种非线性变换是通过定义适当的内积函数( 核函数) 来实现的。支 持向量机的应用在目前已知的分类方法中具有极高的评价。传统的支持向量机只 能解决两类、多类问题，要处理多标签问题，就要将支持向量机和相应的多标签 算法相结合。 目前，由于多标签分类问题的复杂性和其庞大的数据集，使得目前所存在的 多标签算法都并不十分完善。例如基于“一对一”分解策略的支持向量机的多标 签分类算法在保证了分类精准性的同时，在算法的运算效率上还有待进一步提 高。因此，寻找一个合适的基于支持向量机的多标签分类算法，保证分类性能的 同时提高算法的效率将是一个值得研究的课题。 1 2 国内外研究现状 目前，现存的多标签分类算法主要有两大类。 一类是采用算法改造的方法。即针对多类问题的算法，通过适当的改造，使 之适合于多标签分类问题。例如针对多类分类问题的算法c 4 5 8 1 ；c l a r ea n dk i n g ( 2 0 0 1 ) 通过增加信息熵计算来使之可以处理多标签数据集；m l k n n t 9 】【1 0 1 算法是 第1 章绪论 对k n n 算法的改造，首先对整个数据集使用k n n 算法，然后使用朴素贝叶斯决策 1 1 l ( n a i v eb a y e s ) 来解决多标签分类问题；另外，还有e l i s s e e f f $ i w e s t o n 提出 r a n k s v m i l 2 】算法来处理多标签分类问题，该方法遵循s v m ，使用最小化经验代 价函数的同时最大化间隔，所使用的代价函数是排序损失，但该方法的缺点在于 无法直接确定样本的相关标签集合与超大规模的二次优化问题。 另一类是采用问题转换的方法。通过将多标签问题转换成两类或多类问题， 再用相应的算法来解决。问题转换方法的大致思路是，首先通过一种分解策略将 一个多标签问题分解成多个单标签问题，然后再用传统的处理两类问题的方法逐 个求解这些子问题，最后在使用一个合理的策略来集成这些单标签子问题。即我 们通常所说的三个步骤，分解、处理和集成。目前，比较优秀的分解策略有：“一 对一”【13 】的分解策略和“一对多1 8 1 1 3 】的分解策略。“一对一【8 】【1 3 】的分解策 略即对于任意两个类别的样本，构造一个分类器，这样，完成这个过程需要 k ( k - 1 ) 2 个分类器； “一对多 【8 】【1 3 】的分解策略即磷问题建立k 个分类器，第m 个分类器将第m 类与其余的类分开，完成这个过程需要建立阶分类器。许多学 者都比较关注基于问题转换的方法来处理多标签问题，原因是这类方法在训练阶 段有较好的分类效率。这里，值得说明的是，使用“一对一 分解策略所产生的 子问题的规模一般都较小，但所要求建立的分类器的个数较多，适用于样本标签 数不大的数据集合。而“一对多”的分解策略所产生的子问题的规模一般来说都 较大，但所要求建立的分类器的个数较少，因此，比较适用于样本标签数较大的 数据集合。 对于以上两类处理多标签问题的算法，各有优缺点。第一类算法步骤少，便 于解释，但是由于类别太多，实现起来相对复杂。第二类算法的步骤较多，但便 于实现，尤其在存在大量数据的情况下较之第一类方法效率较高。 1 3 本文的主要工作及组织结构 本文的主要工作包括以下几个方面： 1 ) 介绍现有的多标签分类算法和现有的研究技术。首先，介绍有关于多标 签分类算法的基础知识和基本理论。然后分析目前主要的多标签分类算法，并说 明现存多标签分类算法的优缺点。 2 ) 提出我们的基于双标签支持向量机的多标签分类算法，并介绍该算法的 理论基础和技术支持。 3 ) 在我们提出的基于双标签支持向量机的快速多标签分类算法的基础上， 进行相关的实验，并分别与其他的多标签分类算法在分类性能和效率上比较，说 明我们提出的算法的优缺点。 第1 章绪论 本文的具体组织安排如下： 第一章为绪论部分，主要介绍了多标签分类算法的研究背景、研究价值以及 多标签分类算法的国内外研究现状，最后列出了本文的主要研究工作与组织结 构。 第二章简要介绍了多标签分类算法的基本理论和当前主要存在的两大类多 标签分类技术。 第三章简要介绍了支持向量机的特点，重点介绍了线性可分和线性不可分的 情况下支持向量机的解决方法以及核函数的相关知识。 第四章主要描述了我们所提出的基于双标签支持向量机的快速多标签分类 算法。详细阐述了该算法的基本原理、算法流程、实现思路、集成阶段的投票策 略以及多标签分类算法性能的评价标准。 第五章在我们所提出的基于双标签支持向量机的快速多标签分类算法上进 行相关实验，并从分类性能和分类效率两个方面将我们所提出的算法与现存的多 标签分类算法进行比较。 第六章为总结与展望。对全文的研究工作进行总结，指出下一步的研究目标 和计划。 4 第2 章多标签分类算法 第2 章多标签分类算法 2 1 多标签分类算法概述 多标签分类问题是分类问题中比较复杂的问题，不同于两类分类问题，它允 许问题中存在多个类别( 或称为标签) ；不同于多类分类问题，它允许样本同时属 于多个类别。即多标签问题是可以将一个样本同时划分到多个类中的一种分类问 题。它在文本分类、景观分类和基因分类等方面都有广泛的应用。 目前，将现有的多标签分类方法分为两大类，1 ) 基于数据分解的多标签分类 技术，2 ) 基于单个优化问题的多标签分类技术。基于数据分解的多标签分类技术， 即是将一个多标签问题转换为一个或多个单标签问题，然后再通过使用适用于单 标签问题的分类算法来处理分解后的子问题；基于单个优化问题的多标签分类技 术是指将现有的单标签问题的处理方法进行拓展，使之直接用于处理多标签问 题。 在文章 8 和 1 4 】文章中，分别介绍了基于数据分解的多标签分类的处理方 法，以及“一对一”和“一对多”的分解策略。另外，文中还介绍了七种基于单 个优化问题的多标签分类的处理方法，分别为c 4 5 、r a n k s v m 、最大化间隔标 签算法( m m l ) 、多标签最大化熵算法( m l m e ) 、多类多标签关联分类算法 ( m m a c ) 、多标签k 近邻算法( m l k n n ) 和自举算法( a d a b o o s t m h 以及 a d a b o o s t m r ) 。在下面的章节中将主要介绍这些多标签分类算法。 2 2 基于数据分解的多标签分类技术 基于数据分解的多标签分类方法又称为问题转换法，将多标签分类问题转换 为一个或多个单标签问题，然后再用处理单标签问题的方法来处理多标签问题， 这类方法的优点在于算法本身简单易懂，步骤清晰，运算速度快。一般可以分为： 分解，处理和集成三个阶段。问题转换法既可以以标签为基础也可以以样本为基 础进行转换，以标签为基础的分解法称为标签转换法，以样本为基础的分解法称 为样本转换法。目前，广泛使用的以标签为基础的问题转换法的分解法有“一对 一 和“一对多”两种，以样本为基础的分解法有幂集法等等。 “一对多”的分解策略是一种以标签为基础的分解策略是指将具有k 个标 签的数据集分解成k 个两类分类器，但是每一个分类器中都要包含所有的样本， 如图2 1 所示的多标签问题，图中有四个类别标签。每一个分类器均与一个类别 标签相联系。使用“一对多”的分解策略，将此多标签问题分解为四个两类问题。 第2 章多标签分类算法 例如，第彳个分类器将含有第彳个标签的样本作为正类样本，而其余样本作为 负类样本。使用“一对多”的分解策略来处理多标签问题时，需要在训练阶段选 择合适的阈值，而选择合适的阈值是为了在测试阶段决定测试样本的归属。在“一 对多分解策略的决策阶段，我们要计算这k 个判别函数的值并将其排序，然后 对每个测试样本来检测相关的标签子集。在文章 8 】中标注的分解策略p t 4 即是 我们这罩所说的“一对多”的分解策略，而p t 4 s m o 算法，即是基于支持向量 机的“一对多”的分解算法。例如，对于每一个两类分类器可以使用各种两类分 类方法来处理，如使用k 近邻算法( p t 4 k n n t8 】) 、c 4 5 算法( p t 4 c 4 5 t 8 】) 、贝 叶斯算法( p t 4 n b 8 】) ，以及基于支持向量机的b i n a r y - s v m 8 】算法和p t 4 s m o 8 】 算法等等，这旱需要特别说明的是，g o d b o l e 和s a r a w a g i t ”】( 2 0 0 4 ) 提出了支 持向量机的改进算法，这种改进算法结合“一对多”的分解策略，使之适应可以 直接处理多标签分类问题。但，这种改进算法使用了两次“一对多”的分解策略。 第一次使用“一对多”的分解策略后，用s v m 来处理分解后的样本，并将分类 结果加入到样本的特征中去。然后第二次对新的样本集使用“一对多”的分解策 略，依然用s v m 的方法来处理分解后的样本。在所有的测试样本中，也使用两 次分类。使用这种两次分类的方法，考虑到了标签之间的潜在关系。但缺点在于 使用两次“一对多”的分解策略，影响算法的效率。结合“一对多”的分解策略 和支持向量机来处理多标签问题的方法主要缺点在于所有的子分类器的优化规 模都是相同的，这样会造成分类的效率低下；并且在当样本所拥有的标签目较多 的情况下，“一对多”的分解策略会使得正类样本的数量远远大于负类样本的数 量。 图2 1 “一对多”分解策略示意图 6 第2 章多标签分类算法 “一对一”的分解策略是指对于具有j | 个标签的数据集，将任意两个类来构 造一个分类器，只对含有这两个标签的样本进行分类，这样的两两配对共有 盯肛1 ) 2 种可能的情况，将会产生以“1 ) 2 个单标签问题，相应地需要设计k ( k - 1 ) 2 分类器，在以支持向量机为基础的多标签分类算法中，使用“一对一”分解策略 往往运行速度较快，因为“一对一”分解策略所产生的子问题较小【8 】【1 4 】，但在数 据集的标签数目较多的情况下，使用“一对一”的分解策略的运行效率不如使用 “一对多”的方法，原因在于使用“一对一”的分解策略所产生的子问题数量较 多。因此，“一对一”的分解策略适用于规模较大，但标签数目较小的数据集。 如图2 2 所示，假设图中的多标签问题，有四个类别标签。每一个分类器均与一 个类别标签相联系，因此，需要训练六个分类器。使用“一对一”的分解策略来 处理多标签问题时，子数据集中可能存在三种类型的样本，即只拥有第一个标签 的样本，只拥有第二个标签的样本和同时拥有第一个和第二个标签的样本。如何 处理同时拥有第一个和第二个标签的样本已经成为使用“一对一”分解策略的关 键所在。要处理这样的子问题最直接的方法是忽略掉同时拥有第一和第二标签的 样本，将其看成一个两类问题，直接用两类分类器进行分类，但这样做会降低分 类的正确率。另一种方法是用两个两类分类器来处理这样的子问题，如多标签成 对比较算法l l6 | ，在第一个分类器中将样本分为只拥有第一个标签的样本和拥有 第二个标签的样本两类；在第二个分类器中将样本分为只拥有第二个标签的样本 和拥有第一个标签的样本两类，这样，一个样本同时通过这两个分类器就可以确 定样本的归属。例如，一个测试样本通过第一个分类器中是拥有第二个标签的样 本，在第二个分类器中是拥有第一个标签的样本，那么，该样本就属于同时拥有 第一个和第二个标签的样本。但是，使用两个两类分类器的方法会使得训练速度 较慢，分类效率成为该方法的瓶颈。因此，人们很自然的就想到假定同时拥有第 一个和第二个标签的样本位于j 下类样本和负类样本的中间区域。在文章 1 7 1 8 】， 将同时拥有第一个和第二个标签的样本作为一个独立的新的类别，并使用两个平 行超平面将三类样本分隔开。但在文章 1 8 】中，所建立的二次规划问题的变量个 数是训练样本的两倍，相比较而言，文章 1 7 】中的方法将待求解的变量的个数降 低为多标签问题中标签的个数，其中，同时拥有第一个和第二个标签的样本含有 两倍的标签数。所以，文章【1 7 】中的方法相比较文章 1 8 】中所介绍的方法规模更 小，在算法的效率上也更具有优势。但以上两种方法都需要计算两个阈值，其中 一个阈值可以通过标准两类支持向量机来求解，而另一个阈值需要通过额外的线 性规划问题来解决。在分解和处理阶段之后还要进行结果的集成，集成阶段一般 采用投票策略来统计结果。投票策略将在下面的章节中做详细介绍。 第2 章多标签分类算法 多标签问题：单标签问题： 样本标签 分类器正类负类混合类 la ，b ab 2 ，3 ，64 ，5 l 2a ，d acl ，2 ，64 ，73 3a ，c adi ，3 ，64 ，52 4b ，c ，d bcl ，53 ，74 5b ，d bdl2 ，74 ，5 6a cd 32 ，54 ，7 7c ，d 图2 2 “一对一”的分解策略示意图 除了“一对多”和“一对一”这种以标签为基础的分解策略以外，还有一种 以样本为基础的分解策略称之为幂集法，该方法的基本思想是预处理数据集，在 数据集中，每一组多于一个标签的组合形式都将作为一个新的标签来使用，如图 2 3 所示。使用幂集法构造新的数据集会造成标签的数目大量增加，而在某些类 别中，样本的数量是非常稀少的。例如在图2 3 中，原始的多标签数据集共含有 四个标签，而经过幂集法将多标签转换为单标签问题时，共产生了八个标签，较 之原始数据集多产生了四个新标签，分别是标签a 、b 的组合e ，a 、d 的组合 f ，a 、c 的组合g 以及b 、d 的组合h 。还有些不常使用的以样本为基础的 分解策略，例如剔除策略【l4 1 ，剔除策略是指直接删除多标签样本，直接剔除多 标签样本改变了原始数据集的基本属性，造成分类的准确率过低，一般不采用剔 除法来处理多标签数据集。 多标签问题： 单标签问题： 样本类别 样本标签 le l a ，b 2f 2 a ，d 3g 3a ，c 4h 4b ，d 5 h 5b ，d 6a 6a 7f 7 a ，d 图2 3 幂集法的分解策略示意图 第2 章多标签分类算法 2 3 基于单个优化问题的多标签分类技术 在前面一节中介绍了基于数据分解的多标签分类技术，在本节中，着重介绍 多标签分类技术的另一大类解决方案，即基于单个优化问题的多标签分类技术。 基于单个优化问题的多标签分类技术，是指通过对现有两类问题或者多类问题的 算法的改造，使其可以直接处理多标签问题，而不是通过对数据集的改造柬处理 多标签问题。下面，我们将分别介绍几种常用的基于单个优化问题的多标签分类 技术。 决策树算法c 4 5 t 8 】【1 9 1 使用信息熵来定义决策树的节点，使之可以直接用末处 理多标签问题。所使用的支持多类的信息熵的表示如下所示： 卫 e n t r o p y ( s ) = 一芝：( p ( q ) l o g p ( c _ f ) + q ( q ) l o g g ( q ) ) ( 2 1 ) 百 其中，为标签的个数，p ( c f ) 为属于标c i 的概率，g ( q ) = 1 - p ( c ，) 为不 属于标签g 的概率。改造的决策树算法c 4 5 同时允许叶子节点为一个标签集合， 样本分类的输出也可以是一个标签集合。但这样做的缺点是决策树的叶子节点会 很多，因为每一种可能的标签组合都必须有一个叶子节点与之对应。 目前，许多多标签分类问题都采用支持向量机的形式，传统的支持向量机方 法是一个行之有效的分类方法。支持向量机采用了结构风险最小化的原则，通过 最大化间隔来使置信区间最小化。例3 1 1 e l i s s e e f f 平f l w e s t o n 提出的r a n k s v m l l 2 】算 法，该方法采用最大化间隔的同时最小化排序损失来处理多标签问题。 r a n k s v m t 忆】采用了基于核函数的形式，对于该模型，作者定义了排序系统，根 据输出的不同来确定标签的阈值。r a n k s v m t l 2 】算法的缺点在于无法直接确定样 本的相关标签集合与超大规模的二次优化问题。 最大化问隔标签算法【2 0 】( m a x i m a lm a r g i nl a b e l i n g 简称m m l ) 与 r a n k s v m 眩】算法相同，都是以支持向量机为基础的基于单个优化问题方法的 多标签分类算法，m m l 算法同样使用了结构风险最小化的原则，也是通过最大 化间隔来使得置信区间达到最小。但，与r a n k s v m 眩】算法相比较而言，最大化 间隔标签分类算法是以错误分类的样本作为损失函数的，r a n k s v m 5 】是以排序 损失作为损失函数。 多标签最大化熵算、法【2 ”( m u l t il a b e lm a x i m u me n t r o p y 简称m l m e ) ，该 方法不仅考虑了样本与标签之间的关系，还考虑了标签与标签之间的关系，同时 它还使用了一个正则化参数来调整经验风险和实际的分布，从而避免产生过学习 的情况。该方法主要的缺点是样本的分布函数难以计算，只能使用直方图的方法 求近似值。 9 第2 章多标签分类算法 此外，还有m m a c 引睇2 1 ( m u l t i c l a s sm u l t i 1 a b e la s s o c i a t i v ec l a s s i f i c a t i o n ) 算 法，m m a c 算法是一种遵循关联分类器范式的算法，这种算法使用关联规则挖 掘来构造分类规则。m m a c 通过挖掘关联规则初始化分类规则集合，删除与这 些关联规则集合相联系的样本，从剩余样本中递归地学习新的规则集合直到项的 左边无频繁项目集产生。多个规则集合可能包含相似的规则，但，项的右边的标 签是有所不同的，这样的规则可以合并为一个多标签规则。 多标签k 近邻算法【8 】【9 】( m u l t il a b e lkn e a r e s tn e i g h b o r 简称m l k n n ) 是通 过对k n n 算法的改造来使得其适应多标签分类算法的。m l k n n 8 】【9 】算法以k 近 邻算法为基础，对全部的样本集合首先使用胁附算法。先找到离测试样本最近 的k 个样本，需要计算样本的先验概率以及可以反映有多少邻居属于该样本的条 件概率。m l k n n 8 】【9 】算法可以直接确定排序的标签集合作为自己的输出，而其 缺点在于对于无法保证独立同分布的特定样本在计算条件概率时并不一定十分 准确。 a d a b o o s t m h 8 】【1 1 1 算法和a d a b o o s t m r 8 】【i l 】算法是通过扩展a d a b o o s t 算法 来处理多标签问题的。这两种扩展的算法依然采用a d a b o o s t 算法的分类器形式， 即h ：xx l - - ) r 。在a d a b o o s t m h 8 】【l l 】算法中，对于一个新样本x ，如果分类器 输出为正类样本且其标签为f ，那么，将其标记为z ，若其输出为负类样本，则 不将其标记为，。在训练阶段每次的循环中，不断的改变样本的标记。而 a d a b o o s t m r 8 】【l l 】算法为每个样本所拥有的标签进行排序，为每个样本建立有序 的标签队列，排序的准则是按照样本所拥有的标签概率的大小来进行的。 总体而言，基于单个优化问题的多标签分类技术的优点在于没有改变数据集 的结构，无需对数据集进行任何前处理，也没有改变类与类之间的联系，但该方 法的主要缺点是问题过于复杂，需要花费大量的计算时间。 1 0 第3 章支持向量机 第3 章支持向量机 基于数据的机器学习是现代智能技术中的重要研究内容，主要研究如何从一 些观测数据( 样本) 出发得出目前尚不能通过原理分析得到的规律，利用这些规律 去分析客观对象，对未来数据或无法观测的数据进行预测。v a p n i k 等人早在2 0 世纪6 0 年代就丌始研究有限样本情况下的机器学习问题。统计学习理论 【1 】【2 】【3 l ( s t a t i s t i c a ll e a r n i n gt h e o r y ) ，简称s t l 是一种专门研究小样本情况下机器 学习规律的理论，它建立在一套较坚实的理论基础之上，为解决有限样本学习问 题提供了一个统一的框架。9 0 年代中期，随着其理论的不断发展和成熟，s t l 开始受到了越来越广泛的重视。同时，在这一理论的基础上发展了一种新的模式 识别问题一支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) ，在解决小样本、非 线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合 等其他机器学习问题中。因此，支持向量机理论正在成为继模式识别和神经网络 研究之后机器学习领域新的研究热点，并将推动机器学习理论和技术的进一步重 大发展。 3 1 支持向量机的特点 支持向量机【l 】【2 】【3 】是前苏联学者v a p n i k 于1 9 9 5 年首先提出的一种建立在统 计学习理论的v c 维理论和结构风险最小化原理基础上的机器学习理论，它根据 有限样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推 广能力。 支持向量机有如下几个特点【2 3 】： ( 1 ) 支持向量机是一种有坚实理论基础的新颖的学习方法，是一种建立在统 计学习理论和严格的数学推证过程之上的机器学习理论。从本质上看，它避开了 从归纳到演绎的传统过程，实现了高效的从训练样本到预测样本的“转导推理”， 大大简化了传统的分类和回归等问题。 ( 2 ) 支持向量机采用结构风险最小化原则设计学习算法，将经验风险和置信 范围进行了折衷，因此具有较好的推广能力。其研究的对象是有限样本，研究的 目标是不仅要得到当样本数趋于无穷大时的最优解，而且要得到现有有限的信息 情况下的最优解。 ( 3 ) 非线性映射是支持向量机方法的理论基础，支持向量机利用内积核函数 代替向高维空间的非线性映射。核函数理论将在下一节中加以介绍。 ( 4 ) 支持向量机算法将分类问题最终转化成一个凸二次型规划问题。由于在 第3 章支持向量机 凸二次规划问题中，局部最优点即是全局最优点，从而解决了神经网络无法避免 的局部最优解的问题。 ( 5 ) 对特征空间划分的最优超平面是支持向量机的目标，最大化分类间隔思 想是支持向量机理论的核心。支持向量是支持向量机的训练结果，在支持向量机 的分类决策中起决定性作用。 ( 6 ) 支持向量机的最终决策函数只由少数的支持向量所确定，计算的复杂性 取决于支持向量的数目而不是整个样本空间的维数，这在某种意义上避免了“维 数灾难”。少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本， “剔除 大量冗余样本，而且还使得算法简单易懂具有很好的“鲁棒”性。 虽然支持向量机发展只有短短十几年时间，但是由于它的产生具有坚实的理 论基础，近几年涌现出的大量理论研究成果，己被证明是一种很有效的学习机， 并己广泛应用到语音处理、图像检索、己被证明是一种行之有效的学习方法，并 己广泛应用到语音处理、图像检索、人脸识别、入侵检测以及数据挖掘等领域。 尽管如此，支持向量机也有一些固有的缺点： ( 1 ) 支持向量机算法对大规模训练样本难以实施，由于支持向量机是借助于 二次规划来解支持向量的，而求解二次规划问题将涉及朋阶矩阵( m 为样本的 个数) 的计算，当m 数目很大时该矩阵的存储和计算将耗费大量的机器内存和 运算时间。针对以上问题，主要的改进算法有p l a t t 提出的s m o t 2 4 】算法、j o a c h i m s 提出的s v m l i g h t 3 1 】的分解算法以及o s u n a 等所提出的分解算法【2 5 】等等。 ( 2 ) 传统的支持向量机算法只给出了两类分类问题的算法，而在实际应用中， 一般要解决多类或多标签的分类问题，这样，就需要通过对多个两类支持向量机 的组合来解决。目前，主要的组合模式有“一对一”的组合模式、“一对多”的 组合模式以及s v m 决策树理论等等。 3 2 支持向量机的理论基础 3 2 1 最优分类面i l i l 2 1 支持向量机方法是基于结构风险最小化原则建立起来的机器学习方法，支持 向量机最初是针对两类模式识别问题。支持向量机是通过构造一个最优超平面， 对两类问题进行分割。所谓最优分类面【卜2 1 是指不仅要将两类正确分开，而且还 要使得分类间隔最大。如图3 1 所示， 第3 章支持向量机 图3 1 最优分类面示意图 n = 2 l lw 图中实心点和空心点分别表示两类的训练样本，h 为把两类没有错误地分开 的分类线，h 。和h ：分别为过各类样本中离分类线最近的点且平行于分类线的直 线，如图3 1 所示，日和e 之间的距离叫做两类的分类空隙或分类间隔 怛6 j 1 2 ( m a r g i n ) 。所谓最优分类线就是要求分类线不但能将两类无错误地分开，而 且要求两类的分类空隙最大。将两类无错误地分丌是为了保证经验风险最小，而 使分类空隙最大是为了使得推广性的界中的置信范围最小，从而使得真实风险最 小。这里值得说明的是，推广性的别3 】是指统计学习理论中经验风险和实际风险 之间的关系。推广到高维空间，最优分类线就成为最优分类面。 在向量集中，距离超平面最近的向量被称之为支持向量【2 6 - 2 8 ( s u p p o r t v e c t o r ) ，一组支持向量可以唯一地确定一个超平面w x + 6 = 0 ，还可以以( w ，b ) 的 形式表示。支持向量机理论最初来源于数据的分类问题，意在寻找一个满足要求 的最优分类超平面。若将二维平面中的相关概念推广到高维空间，则最优分类线 就成为了最优分类面。 设输入模式集合为 x ，) r ”由两类样本点组成，则类别集合为y 一l ，+ 1 】， 即若x ，属于正类样本，则y i = + 1 ；否则y i = 一1 ，那么，训练集合的样本集为 x ，y 小待1 ，川。支持向量机的目标就是要根据结构风险最小化原理，构造一个 将两类样本模式尽可能分开的目标函数。下面将分别介绍线性支持向量机和非线 性支持向量机。 3 3 2 线性支持向量机1 2 6 1 1 2 7 1 1 2 8 i 对于图3 1 所示的问题，很容易用一条直线把训练集j 下确地分开，因为两类 样本点分别在分类线的两侧，无错分样本点，我们称这类问题为线性可分问题。 假设d 维空间中线性判别判别函数的一般形式为g ( x ) = w x + 6 ，其中，w 和 第3 章支持向量机 6 分别为权值向量和阈值。可设分类超平面的方程为： w x + 6 = 0 ， ( 3 1 ) 将判别函数进行归一化处理，使得所有样本均满足ig ( x ) i l ，即使得离分类 面最近的样本点的判别函数值为ig ( x ) l = 1 。因此，有判别函数为： w x i + b l , 2 + 1 ， ( 3 2 ) w x ，+ b - 1 ，y f = 一1 、7 如图3 1 所示，平行于最优分类而的超平面h 。和日，的判别函数值分别为： 日：w x + b = 1 i ：w x + 6 ：一l ( 3 3 ) 它们之间的距离，即为前面所说的两个平行超平面的间隔为，原点到日的 距离减去原点到日：的距离。这样，分类间隔就等于2 川w i | ，其中所说的分类最 优面即是要最大化分类问隔，而最大化间隔等价于最小化i | wj l 【2 】1 3 】。根据式( 3 2 ) 和 ( x l ，y 1 )