（电路与系统专业论文）基于支持向量机的音乐自动分类.pdf

摘要 音乐分类实质上是音频分类的一个分支，现已逐渐成为模式识别领域的一个 研究热点，其研究发展方向大体可以归纳为以下三个方面：一是在音乐特征提取 的方法和特征向量的组成上做改进；二是在分类器的选择上做改进；三是在解决 多分类问题的方法上做改进。 本文采用s v m 做分类器，对流行音乐、古典乐器、钢琴曲、民歌、美声、 戏曲六种不同风格的音乐进行分类，实验所做的工作归纳如下： 第一，通过学习数字音频技术理论来掌握音频短时处理技术，结合实际对每 个音乐样本进行预加重、分帧、加窗、判别静音帧等短时预处理，然后提取音乐 样本的时、频域感知特征和基音频率特征：提取音乐样本的m f c c 矩阵并求取 该矩阵的统计特征。 第二，在深入理解s v m 分类原理的基础上，比较标准s 与变种s 的 优缺点，确定本实验采用标准s v m 来进行分类；测试了m f c c 维数、m f c c 统计特征、m f c c 与感知特性的各种组合方式对s v m 分类器性能的影响，比 较了同等条件下s v m 与其它分类器的优势。 第三，研究多分类方法的应用，分析比较各种多类分类方法的优劣，提出了 利用先验知识和树形结构相结合的方法构造多分类系统。用标准s v m 对样本进 行训练得到多个两类分类器，比较各分类器的分类精度，按照比较的结果对样本 进行人为的最优聚类，再用树形非交叠结构构造多分类系统，最后测试得到较好 的分类效果。 关键词：音乐分类：特征提取；支持向量机；多类分类 a b s t r a c t i ne s s e n c e ，t l i em u s i cc l a s s i f i c a t i o ni sab r 暑m c ho fa u d i oc l a s s i f i c a t i o n ，剐q dh a s b e c o m eah o tt o p i ci n p a t t e m代c o g n i t i o n ， t l l ed i r e c t i o no fi t sr e s e a r c h锄d d e v e i o p m e n ti ng e n e 豫lc 锄b es u m m a r i z e di nt h r e ea s p e c t s ：f i r s t ，t h em e t h o d so f m u s i cf e a t u r ee x t 豫c t i o n 锄dt h ef o mo ff e a t u r ev e c t o 体c 觚b em a k ei m p r 0 v e m e n t s ； c o n d ，t h ec h o i c eo fc i a s s i f i e rc 粕d ot 0i m p m v e ；t 1 1 i r d ，t 0s o l v et l l ep r o b l e mo f m u l t i p l ec l 雒s i f i e r sc 锄d ot 0i m p r o v eo n i nt h i sd i s r t a t i o n ，e x p e r i m e n t sh a v eu s e ds u p p o r tv e c t o rm a c h i n et 0c l a s s i 匆t h e v 撕o u sm u s i c ，w h i c hi n c l u d i n gp o pm u s i c ，c l a s s i c a lm u s i c ，p i 卸om u s i c ，f o l ks o n g s ， v o c a l ，o p e r ai ns i xd i 行- c r 朋ts t y l e s ，锄de x p e r i m e n t a lw o 水a 佗s u m m a r i z c d 硒f o l l o w s ： f i r s t ，b yl e 椰i n gt h et 1 1 e o 叫o fd i g i t a la u d i ot c c h n o l o g ) ，t 0m a s t e rt l l es h o n 卸d i o p r o c e s s i n gt e c h n o l o g y ，c o m b i n e dw i t l l t u a lc o n d i t i o n s ，e a c hm u s i cs 锄p l ew i i lb e g o n et h r o u 曲t h es h o r t - t e mp 他仃e a t m e n tp m c e s so fp 佗- e m p h a s i s ，f h m i n g ，w i n d o w i d e n t i f i c a t i o no fs n e n tf m m e a n dt t l e n ，t 0e x t r a c tm u s i cs 锄p l e s c h a r t e r i s t i c s w h i c ha 陀i nt i m ed o m a i n ，f 沁q u e n c yd o m a i na n de x l m c tt h em f c cm a t r i x 硒w e l l 弱 t h es t a t i s t i c a lc h a m c t e r i s t i c so f t h i sm 枷x s e c o n d ，a r e rd e 印u n d e 体t a n dt h ep r i n c i p l eo fs v mc l a s s i f i c a t i o n ，lm a d ea c o m p 撕s o nb e 铆e e ns t a n d a r ds v ma n ds v mv 撕锄t s ，锄dd e c i d c dt oc h o o s es u p p o r t v e c t o rm h i n e 弱t h ec l 嬲s i f i e r t h e n ，lt e s t e dt h ep e r f b m 觚c e so fc l a s s i f i e rw h i c h w 弱i i ld i 虢r c n tc 嬲e si n c l u d i n gm f c ci nd i 行e r e n td i m e n s i o n ，d i 腩他n tf c a t u 他so f m f c cs t a t i s t i c s ，d i 艉佗n tc o m b i n a t i o n so fm f c c 舳dp e r c e p t u a lc h a r a c t e r i s t i c s ，i n a d d i t i o n ，im a d eac o m p a r i s o nb e t v v e e ns v m 锄do t h e rc l a s s 讯e r su n d e rt h e 鼢m e c o n d i t i o n sd e f i n e di t sa d v a n t a g e s t h i r d ，i h a v es t u d i e dt h e a p p i i c a t i o n o f m u l t i c l a s s i f i c a t i o n ，a n a l y z e d a d v a n t a g e sa n dd i s a d v a n t a g e so fm u l t i - c l a s sc l a s s i f i c a t i o nm e t h o d sa n d h a v ep i o p o s e d t h em e t h o do fm a k i n gu 0 fp r i o rk n o w l e d g ec o m b i n e dw i t ht h et 他es t n j c t u r et 0 c o n s t r u c tt h em u i t i - c l a s s i f i c a t i o ns y s t e m iu s e ds t a 】n d a r ds v mo nt m i n i n gs 姗p l e s t og e ta1 0 to fc l a s s i f i e r sw h i c hw e 陀u s e di nt 、ot y p e s ，m o r e o v e r 锄a l y z i n gt h e s e c l a s s i f i e 体t 0g e tt h e i rc l a s s i f i c a t i o n 们c u 豫c y a c c o r d i n gt h ec i a s s 讯c a t i o na c c u r y l o p t i m a i i yc l u s t e 他ds a m p i e si nd i a b 佗n t 盯e 嬲t h e nt oc r e a t et h ec i a s s i 矽s y s t e mi n t h et eo fn o n - o v e r l a p p i n g 鲫r u c t u r e 柚dt e s t e dr e s u l t so ft h es y s t c m sc l a s s i f i c a t i o n a c c u r a c y k e yw o r d s ：m u s i cc l 硒s i f i c a t i o n ，f e a t u r e se x t r a c t i o n ，s u p p o nv b c t o rm a c h i n e ， m u l t i c l a s sc l a s s i f i c a t i o n 第一章绪论 1 1 研究的背景与意义 第一章绪论 自上世纪9 0 年代以来，网络技术和多媒体技术飞速发展，直接导致网络负 载信息量日渐庞大，其中包括大量的视频、音乐、图片、f i 嬲h 等多媒体信息【3 6 】， 所以建立高效的信息分类检索系统以有效的管理逐渐膨胀的网络信息是现今一 个研究的热点。 现实中应用最为广泛的信息检索主要是基于文本的【2 7 1 ，比如搜索引擎 g o o g i e 、b a i d u 等。它主要是通过定位文档中的查询关键字来寻找匹配文档，通 过匹配音乐文件名或歌曲演唱者来查找目标音乐，这种基于文本的多媒体信息检 索方式存在明显的缺陷，首先，对于海量的信息数据，人工标注无法实现，耗费 成本太高；其次，多媒体信息中的很多关键特征是无法用文本能表达清楚的，比 如即使音乐具有相同的名称，它们的音色、音高、音调亦可能有所不同【2 5 1 ，而这 些都难以用文本一一标注。最后，文本标注匹配的方法无法实现基于内容的音乐 检索。基于内容的检索思想就是在这种背景下应运而生的，它有效避免了上诉三 个缺陷，在检索速度和准确率上也有了大大的提升，作为一种新型的检索技术， 它彻底脱离了关键字匹配的方式，而是根据数据信息内容的数学特征进行检索， 如对图像的纹理、颜色，或音乐中的基音频率、平均能量、m f c c 等进行分析和 归纳【2 】，提取这些特征然后组成向量形式，再基于这些提取的特征向量来对信息 进行分类和检索。基于内容的检索方法在医疗图像、天气预报、建筑工程图、艺 术馆藏、资料管理遥感图像处理和空间探测等很多领域都有着广泛的应用，所以 它是一项实用性很强的高科技技术；尤其是随着网络技术的发展，音乐、视频、 图片称为网上的主要信息，基于内容的检索技术更加成为了一个不可或缺的搜索 方法。在现实的需求下，很多相关产品也陆续面市，比如i b ma l t a d e n a 研究开 发的q b i c ( q u e 眄b yi m a g ec 0 n t e n t ) ，它能对多媒体信息进行检索；再比如美国 加利福尼亚研究的m u s i cf i s h ，它可以应用于已知数据库中声音的自动分类和检 索。 音乐信号属于音频信号的一种，所以音频信号的所有处理方法和检索方法都 可以完全运用在音乐分析领域【l 】，在音乐检索的系统当中，音乐的分类具有重要 的研究价值，它是音乐基于内容检索的重要前提，其主要原因有三：第一，不同 类型的音乐数据需要不同的处理方式。第二，基于内容的音乐检索中，利用音乐 第一章绪论 的类别信息可以大幅度减少搜索空削3 1 ，例如，根据查询输入的类别，便可在数 据中仅搜索该类别的数据，而不必搜索其它类别的数据，加快了检索的速度。第 三，依据类别的变化将音乐数据分段，可对其它数据检索起到辅助作用，比如可 对视频数据的分段与索引起到辅助作用，从而对基于内容的视频检索具有重要的 意义。 如今音乐数量增长迅速，伴随着大量的歌手涌现，海量的专辑和网络歌曲也 纷纷面市，而且由于世界文化发展的多元化，音乐也相互影响，各种各样的音乐 风格逐渐产生，为了满足人们的偏好，准确而又快速的找到自己喜欢的歌曲，这 就要求检索系统更加高效、快速，通过音乐的分类来建立索引，并减小特定搜索 是目前最为有效的解决途径。 1 2 音乐分类发展的历史与现状 音频包括音乐、语音、环境音等部分，音乐信号处理的发展伴随于音频技术 的发展过程，而音乐分类的目的是有利于进一步的音乐检索，所以音乐分类的发 展历史可从音频信息检索技术谈起。 音频信息检索的研究工作是从2 0 世纪9 0 年代开始的，主要研究利用音频信 息的时频域物理特性来实现基于内容的音频信息检索【1 6 】。这种思想的提出起先只 是为了检索出音频中的语音类【6 】，大概过程是首先将语音信号的特征转换为文本 记录，然后通过对文本关键字的检索来间接实现对语音类音频信息的检索【5 1 ，该 方法虽然没有用到分类原理，但它的缺陷却是促使分类思想提出的原因所在。 如今，音乐检索成为了音频信息检索研究中最为活跃、最富有成果的领域， 在检索方式上，它采用哼唱检索、节拍拍打检索等方式，在音乐库本和系统构建 上皆采用了音乐分类的方法，节省了检索空间，加快了检索速度。 就分类算法而言，人们经过长时间的探索和发展，目前也形成了许多成熟的 方法，下面介绍其中几种比较著名的【。 上文提到的美国加利福尼亚研究的m u s c l ef i s h 系统。它是一种基于内容的 音乐分类方法，该方法首先提取了音乐样本时域、频域的特征并将它们级联组合 形成高维的特征向量，其中的主要特征包括短时能量、过零点率、基音频率等等， 它们某种程度上体现了响度、音调、节奏等音乐感知特性；然后再计算各帧之间 的均值、方差、自相关系数等统计特性用于接下来的分类器训练，最后形成基于 内容的检索系统。 另一个检索系统f o o t e 则是首先提取了音乐数字信号中1 2 阶的m e i 倒谱系 数，然后结合频域特征中的短时能量构成音乐样本的高维特征向量【5 】，接下来再 2 第一章绪论 将音乐样本的输入空间划分为多个互补交叠的区域( 其中用到树形结构矢量量化 器) 。在进行分类时先计算各个待分类音乐样本的特征向量到这些区域的欧式距 离，在使用n n 分类器为样本分类。 l i 在提取音乐样本的m e l 倒谱系数的基础上再提取出样本的基音频率、谱质 心、子带能量等感知特性，然后将这些特征值级联成为高维特征向量形式，并且 使用比n n 更为先进的n f l ( n e a r e s tf e a t u r el i n e ) 分类方法作为分类器对它们进行 分类，他的实验表明使用这种方法对音乐样本进行分类在正确率上比前面几种更 高些，而且n f l 分类器也优于n n 、n c 等分类器。 l i n 则是在l i 实验的基础上使用了小波变换的方法提取感知特征，包括基音 频率、子带能量、谱质心等1 7 】。他的实验表明使用小波变换方法提取的特征较之 其它方法更为精确，而在具体构造分类系统时，它则是采用自底而上的倒树结构， 并且结合s v m 分类方法，利用s v m 在小样本、高维空间上有较好的泛化能力 取得了很好的实验效果。 另外还有1 h n e t a k i s ，他是从节奏内容( r h ”h m i cc o n t e n t ) 、音色结构( t i m b m l t e x t u r e ) 和音调内容( p i c t hc o n t e n t ) 等特征【1 6 】入手，组成一个几十维的特征向量，再 结合层次性的分类结构对待分样本进行分类：虽然这种方法的实验准确率不高， 但还是给人们提出了一种可行性的思路。 当然，除了上述的几种算法外，还有许多值得应用的方法，这里不多作介绍， 但是通过学习和理解发现音乐进行分类的发展研究可以从两个方向入手：第一， 音乐特征的提取：目前包括短时能量、过零点率、基音频率、和谐度、静音率、 频谱、带宽、谱质心、子带能量等时域、频域特性，还有m e l 倒谱系数、其它倒 谱系数、线性预测系数等等，这些感知特性和非感知特性都一定程度上反映了音 乐样本的特征，人们为了提高分类的精度和速度往往会选择使用这些特征的级联 组合，在级联这些特征构成特征向量然后进行分类的过程中仍然有几个值得研究 的方面： 1 ) 提取特征的方法，很多音乐特征的提取方法有多种，好的提取方法能够 更好的凸显该特征在不同样本之间的异同，提高分类的精度，比如提取基因频率 方法有谱估计法、多路径选择法等，频域感知特性提取的方法有傅立叶变换法、 还有上面l i n 提到用小波变换提取等，对特征提取方法的研究亦是目前音乐分析 的热门课题。 2 ) 分类器的选择和分类器本身的发展：在整个模式分类识别的范畴内分类 器可以说是种类( 方法) 繁多，它们皆可用于音乐分类比较常用有基于高斯模 型的分类器、基于决策树的分类器、基于隐马尔可夫模型的分类器、基于神经网 络的分类器、基于支持向量的分类器等等，在实际音乐分类时选择什么样的分类 第一章绪论 器决定了整个系统的性能，另外这些分类算法依然还有可改进的空间，比如支持 向量机在目标表达式上呈现很多变种，在训练上出现了很多改进的方法，高斯模 型、神经网络亦有多个类型。 3 ) 系统的结构，优秀的系统结构同样能提高样本的分类精度，而且能够极 大提高分类速度，常见的有：一对多法、一对一法、d a g 法、分层法、树形结 构法等，再结合相应的聚类方法，系统的结构选择可以说多种多样，另外，对于 某些具体问题的解决还可以做一些小的改动，比如为了减小差错积累，树形结构 法引入了交叠结构，为了减少错分，引入了模糊核聚类。 音乐分类技术是现代音乐检索的有利前提，它的发展涉及到多个学科，是一 个交叉学科研究的领域，相关领域包括：数字音频处理、人耳的听觉特性、模式 识别、人工智能、机器学习、数据挖掘、信号与系统、认知科学、知识发现等等， 所以说音乐分类有着深厚的理论基础和现实需要，有着广阔的发展前景。 1 3 本文的主要内容和结构安排 本文主要介绍了支持向量机的基本理论和音乐特征的提取方法以及多分类 方法的应用。 在支持向量机( s v m ) 方面，本文是从统计学习理论切入，分析了s v m 的 引入背景和它的分类基础，为了解决线性不可分和非线性的问题分别引入了惩罚 因子和核函数，并讨论了惩罚因子结合松弛变量在分类应用上的优缺点，还列举 出了核函数的种类，接着又讨论了几种s v m 的变种类型以及它们的优劣势，最 后概括性的分析了支持向量机相较于其它方法的优势。 音乐特征提取方面，首先分别从时域和频域两方面介绍了感知特性的构成以 及它们的提取方法，然后着重讲了m e l 倒谱系数及其提取方法，分析了不同维数 和不同统计特性的m f c c 组合对分类精度的影响，最后介绍了级联的高维特征 向量的组成。 多分类方法则是简单列举了几种常用的方法，着重介绍了树形多分类机构的 构造过程和训练方式，还对这几种方法在分类精度和速度性能上做了系统的比 较。 本文对分类系统的研究做了大量的仿真实验，并在第四章和第五章给出了一 些仿真图和数据结果，本文的整体结构安排如下： 第一章：主要介绍了音乐检索、音乐分类的意义和国内外的发展现状，并概 括了文章的主要工作。 第二章：详细介绍了s v m 分类原理及几种s v m 变种算法，阐述了s v m 算 第一章绪论 法的发展方向及其发展现状。 第三章：介绍了几种多分类算法的原理，对树形多分类算法进行阐述应用。 第四章：详细介绍了音乐时、频域特征的提取，着重讲解了m f c c 的提取过 程。 第五章：对特征向量的级联构成进行了实验对比分析，设计系统并仿真实现。 第六章：对全文做出总结，对s v m 音乐分类应用进行了展望。 第二章支持向量机的基本理论 第二章支持向量机的基本理论 1 9 9 5 年，c o n e s 和v a p n i k 首次提出支持向量机( s v m ) 的概念，这是模式 识别、机器学习领域发展的重大成果，在解决高维模式识别中的非线性、小样本 等情况有着许多特有优势【1 4 】，它是以统计学习理论中最小化结构风险原理和v c 维理论为基础的i l5 1 ，这与传统的统计学相比有了很大的改进。在此之前，传统统 计学方法是完全依赖于训练样本数量的，它们的分类性能往往随着样本变化而出 现巨大差异，在实际处理的问题当中，一般待处理样本的数目是非常有限的，所 以很多优秀传统统计方法在实际应用中效果却相当不理想。相反，s v m 能在有 限的样本数中找到能够体现样本特性的支持向量，利用这些支持向量构造分类 面，然后再在学习精度与学习速度上寻求折衷，从而获得较好的泛化能力，与统 计机器学习的精密思维相比，传统的机器学习在实际应用当中并没有这样特定的 步骤，所以不同的人用同样的方法做出的结果可能会大不相同，缺乏一定的指导 和原则。 2 1 统计学习理论 机器学习本质上其实是一种对实际问题真实模型的逼近，但真实模型是无法 确切知道的，既然真实模型不得而知，所以实验得到的假设模型与问题真实解之 间是肯定有差距的，这个假设模型与问题真实解之间的差距，就叫做风斟3 n 。得 到一个分类器以后，虽然它与真实模型之间的差距无从得知，但可以通过实验得 到的数据来无限逼近它，即是用分类器在样本数据上的具体分类结果与已知结果 ( 已知结果是指待分类样本的类别已经被标注) 相比较，然后用得到的差值来表 示，这个差值叫做经验风险。统计学习理论中的一致性结论即是要求当训练样本 的数目无限大时，经验风险的最优值能够无限趋近于实际风险的最优值，所以机 器学习是在符合一致性理论的前提下尽可能提高机器的推广能力。 在模式识别中v c 维是一个非常重要的概刽1 7 】，它与问题的复杂度有着很大 的关系，最直接的解释为：假设空间中存在某m 个样本，使得一个函数集能够 按2 肘种可能将它们完全打散，且m 是该函数集能够打散的最大数目，那么即称 m 为该函数集的v c 维，如果m 为无穷大，则该函数集的v c 维也为无穷。所 以v c 越高说明问题复杂度就越大，它们之间是成正比的。上面提到s v m 就是 基于v c 理论的，在实际应用当中它关注的只是与问题复杂度相关的v c 维，而 第二章支持向量机的基本理论 样本的维数与解决问题的复杂度并不相关，所以即使样本的维数成千上万，只要 引入合适的核函数，s v m 都能够轻松处理。一般来说，对于一个实际的分类问 题，如果样本数n 是固定的，那么分类器的v c 维的数目越大，则相应的置信范 围( 与分类器对未知样本的分类能力相关) 就越大，这导致经验风险与真实风险 之间的差距也就越大( 如图2 1 ) 。因此，在设计分类器时，不仅要尽可能地使经 验风险最小，还要使v c 维的维数尽量小，这样做能使分类器的置信风险尽可能 小，从而提高了分类精度，减小了期望风险，整个过程即为所谓的结构风险最小 化原则，简称s r m 原则。 风 险 结构风险最小h 图2 1 结构风险最小化示意图 由图2 1 可知，结构风险最小化的过程要综合考虑到两个方面，它们分别为 经验风险和置信风险。前面已经提到过经验风险，从中可以了解到它是代表分类 器在给定样本上的分类误差，体现了分类器的学习能力。而置信风险代表了分类 器对未知样本的分类能力，所以它不是一个精确的具体值，而是一个取值区间， 并且它对整个泛化误差起着决定性影响。实际上往往v c 维非常高的分类器它的 经验风险也非常小，即它能记住每一个训练样本并能够1 0 0 把它们分类正确， 但可能对未知测试样本的分类却非常差，这说明该分类器只考虑了最小化经验风 险，却完全忽视了分类器的置信风险，从而导致该分类器的泛化能力( 推广能力) 极其地差。所以结构风险最小化原则需要权衡经验风险和置信风险两者之后做出 的最佳折衷，另外，置信风险的大小取决于两个量：一是训练样本的数量，给定 的训练样本的数目越大，置信风险越小，二是分类面函数的v c 维数，v c 维越 大，问题越复杂，推广能力越差，置信风险也就越大。 7 第二章支持向鼍机的基本理论 泛化误差的公式为： r ( w ) 尺唧( w ) + 互耍叵耍至三2 委掣 ( 2 ) 简单记为： 尺卜一sr 。【w j + ( 2 2 ) 公式中尺( w ) 就是真实风险，足( w ) 就是经验风险，就是置信风险( 也叫 做为v c 信任) 。置信范围不仅受置信水平1 t 1 的影响，而且还是函数集v c 维h 和训练样本数目n 的函数。h 增大或n 减小会导致m 增大。s 理论即是采用 了这种寻求置信风险和经验风险之和最小，结构风险最小的原则来训练分类器 的。这种s v m 需要说明的三点【墙】： 1 ) 小样本，并不是说样本的绝对数量少( 实际上，对任何算法来说，更多 的样本几乎总是能带来更好的效果) ，而是说与问题的复杂度比起来，s 算法 要求的样本数是相对比较少的。 2 ) 非线性，是指s v m 擅长应付样本数据线性不可分的情况，主要通过松 弛变量( 惩罚变量) 和核函数技术来实现，这一部分也是s v m 的精髓。关于样 本分类这个问题究竟是不是线性可分的，尚没有定论，因此不能简单的认为它是 线性可分的而作简化处理，在确定之前，只能先当它是线性不可分的( 线性可分 也不过是线性不可分的一种特例而已) 。 3 ) 高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过 降维处理，出现几万维的情况很正常，其他算法基本就没有能力应付了，s v m 却可以，主要是因为s v m 产生的分类器很简洁，用到的样本信息很少( 仅仅用 到那些称之为“支持向量”的样本) ，使得即使样本维数很高，也不会给存储和计 算带来大麻烦( 相对照而言，k n n 算法在分类时就要用到所有样本，样本数巨 大) 。 2 2 支持向量机的分类基础 s v m 的提出是基于两类样本模式分类识别的问题，它包含了三个核心思想： 1 ) 求取区分样本的最优分类面以期获得较好的推广能力。 2 ) 提出软间隔的概念来代替硬间隔，用允许少量错分的思想来解决由孤立 点而引起的线性不可分问题。 3 ) 引入核函数使得训练样本从低维空间中的线性不可分情况转化为高维空 8 第二章支持向量机的基本理论 间中的线性可分。 2 2 1 线性可分与最优平面 线性分类器( 也叫做感知机) 是最简单也很有效的分类器形式，支持向量机 最初也是从样本线性可分情况下寻求最优分类面的基础上发展而来的，从一个线 性分类器中，可以看到s v m 形成的思路，体现s v m 的核心概念【2 0 】。 用一个二维空间里仅有两类样本的分类问题来举个小例子。如图2 2 所示。 图2 - 2 线性可分示意图 c l 和c 2 是要区分的两个类别，在二维平面中它们的样本分布如上图2 2 所 示。中间的直线代表一个分类函数，它的作用是将两类训练样本分开。一般来讲 的，如果说某个线性函数能够将两类不同的样本完全正确的分开，那么就称这两 类样本是线性可分的，否则就称它们是非线性可分的。该分类函数在高维空间就 统称为超平面。 实际上，一个线性函数是一个实值函数( 即函数的值是连续的实数) ，而分 类问题( 例如这里的二元分类问题回答一个样本属于还是不属于一个类别的 问题) 需要离散的输出值，例如用l 表示某个样本属于类别c l ，而用0 表示不 属于( 不属于c l 也就意味着属于c 2 ) 这时候只需要简单的在实值函数的基础 上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确 定类别归属。例如有一个线性函数g ( j c ) = 眦+ 6 取阈值为o ，当样本五需要判 别时，只需确定g b 。) 的值。g b 。) o ，就判别为c l 类，若g b 。) o 时j ，l o ；反之亦然，那么就保证y l ( 煅l + 6 ) 始终大于o ，此时 间隔的定义可改写为仉= i 眦，+ 6 | 。 将w 和6 归一化，样本到超平面的距离为： 咿如k ) i 其中1 1w | l 是w 的范数，w = ( m ，w 2 ，) 。 = 獗i 丽 ( 2 - 3 ) ( 2 - 4 ) 当用归一化的w 和b 代替原值之后的间隔叫做几何间隔，几何间隔所表示的正 是点到超平面的欧氏距离。以上是单个点到某个超平面的距离定义，同样可以定 义一个点的集合( 就是一组样本) 到某个超平面的距离为此集合中离超平面最近 的点的距离。下面图2 3 更加直观的展示出了几何间隔【8 1 的现实含义： 图2 - 3 分类几何间隔示意图 = 2 川叫 由图2 3 可见，h 为训练得到的分类线， 日。和日2 是平行于h 两条直线， 它们分别通过离h 面最近的两类样本点，这些样本点即被称为支持向量，何。与 h ，日：与h 之间的距离就是几何间隔。间隔与样本的误分次数间存在关系： 误分次数5 ( 等) 2 ( 2 - 5 ) 仃 由该公式可以知道误分次数的上界是由间隔决定的。间隔越大，它的误差上 l o 第二章支持向最机的基本理论 界越小。因此最大化间隔就成了训练阶段的目标，由上面公式2 3 可知几何间 隔盯几何与m i 是成反比的，因此最大化几何间隔与最小化8w i i 完全是一回事。而 常用的方法并不是固定0 训i 的大小而寻求最大几何间隔，而是固定间隔( 例如固 定为1 ) ，寻找最小的8 叫i ，表示为m i n i lw i l 。但实际上对于这个目标，常常使用另一 个完全等价的目标函数来代替，加上附加条件( 即都样本分布在日和日，的两 侧) ，最后求解分类问题的最优分类面问题转换为求解如下优化问题： 1l i 2 m l n 剖叫i ( 2 - 6 ) j “彩e c f f d y ，【( 慨，) + 6 】一1 o( f = l ，2 ，z ) ，为样本数 ( 2 7 ) 通过解式( 2 - 6 ) 、( 2 - 7 ) 的优化问题可以得到该线性可分问题的最优分类平面， 对整个训练样本的分类就可以转化为对支持向量的分类，所以说支持向量是整个 样本集的特殊代表，它包含了该样本集的关键信息，支持向量机也因此得名。 2 2 2 线性不可分与软间隔概念 上面讨论都是基于样本线性可分的前提下进行的，当训练样本在空间中线性不 可分( 如图2 - 4 中右上方存在的深色小方形) ，即找不到一个超平面将它们完全 分开，则优化问题( 2 6 ) 、( 2 7 ) 就无可行解，如何在样本线性不可分的情况下仍然 能够找到大致划分样本类别的最优平面呢，为此v a p n i k 提出了软间隔的概念， 这一概念的关键在于分类面是允许少量错分的，是在错分比率尽可能小的前提下 优化问题的解【1 。 依照软间隔这种允许错分的思路，支持向量机引入了松弛变量的概念，原先 对样本的约束条件变为【3 2 】： y ，【( w ，) + 6 】l 一缶 ( 2 - 8 ) 缶oo = l ，2 ，)，为样本数，缶为松弛变量( 2 - 9 ) 从式( 2 9 ) 可知松弛变量是非负的，当分类结果小于l 时，表示样本出现在图 2 4 的三条平行线之间，而允许样本出现在平行线中间就表示实验者放弃了对它 们的精确分类，很显然这对分类器来说是一种损失，所换来的好处是分类面不必 向这些样本点进行移动，从而得到较大的几何间隔。 第二章支持向量机的基本理论 图2 - 4 线性不可分示意图 = 2 j | 训 出现在平行线之间的样本称为孤立点，孤立点的损失是一个能是目标函数变 大的量，把它以一阶软间隔的形式加入到目标函数中，使目标函数的表达式变为： ， n l i n 去i l 叫1 2 + c 缶 ( f = l ，2 ，) ( 2 l o ) 二 f i l 这个公式需要注意几点1 3 3 】： 1 ) 并非所有的样本点都有一个松弛变量与其对应。实际上只有孤立点才有， 非孤立点松弛变量的值可认为等于零，从这点可以看出松弛变量值的大小体现了 孤立点离分类面的远近，松弛变量越大表示样本离分类面越近，离群就越远。 2 ) 式( 2 1 0 ) 中的c 为惩罚因子，它决定了分类器对孤立点带来损失的重视 程度，对某个独立点来说，定的c 越大，分类器的损失也就越大，这就表示实 验者很不愿意放弃这些孤立点，如果把c 定为无限大，那么式( 2 1 0 ) 的值就会交 得无限大，从而又退化成了原来的硬间隔问题。 3 ) 惩罚因子c 不是一个变量，在求解式( 2 8 ) 式( 2 1 0 ) 的优化问题时，必须 事先指定c 的值，然后才能得到一个分类器，再用测试样本测试推广能力，变 换c 的值重复上述的优化问题直到得到最佳分类结果。 对非线性的s v m ，优化变量的个数与特征向量w 的维数有关，这个量可能 会很大，所以通常求解器对偶，因为在对偶问题中，变量个数等于训练样本个数， 与样本的特征向量空间的维数无关。 对于优化问题( 2 - 8 ) - ( 2 - 1 0 ) ，原问题的l a g r a n g e 问题为： 三= 扣训2 + c 军缶一军口，( ( w ，x ，) + 6 ) 一l + 鲁) 一军，参 ( 2 - 1 1 ) 1 2 第二章支持向量机的基本理论 其对偶问题为： m ，x 主口，一 y ，y ，口，口，m ，x 口，一y 叩，。 j i i 二 f _ i，- 1 sub je ctt o0s 口，scvf ( 2 - 1 2 ) j ，口，= o 而原问题的解： 同样可写出其k k t 条件 ， w = y f 口，毛 f = l 熹工= w 一乃口，= o 毗下 昙l = 一乃q = o a 6争“。 ：= c q 一“= o 【，与f 咒( ( w _ ) + 6 ) 一l + 缶o 参o q o 所o 口，陟，( w x ，) + 6 ) 一1 + 缶】= o ( 2 - 1 3 ) 若口，= c 称- 为偏差支持向量，若0 口， o ( 2 2 2 ) 七( 工，x ) = p 一口l x x 1 ，口 o ( 2 2 3 ) 上面的公式( 2 1 7 ) ( 2 1 9 ) 所对应的分类器一般被称为标准支持向量机，这主 要是与后来发展的各中变形支持向量机区分开。 下面介绍中变形支持向量机： 支持向量机的训练最终归纳为一个解凸二次优化问题，另外，s v m 中的其 他问题，比如怎样确定惩罚系数和核函数中的参数，在求解过程中也整合到该优 化问题当中去。虽然说凸优化问题是多项式时间可解的，但实现起来其实不易。 当训练样本数的规模非常大，训练的时间增长过快，即使用非常好的分类方法也 依然是二次非线性的。为了缓解问题的复杂度，人们提出了两种类型的途径： 1 ) 基于支持向量机在优化问题上的结构特点做适当的改进。 2 ) 在求解的过程中基于分解的算法。 第二种方法有c h u n k i n g 方法、分解法、s m o 法等等，这些方法如上所述并 没有对目标函数和约束条件做一定的改动，只从求解方法的角度考虑，通过把问 题分解，将大的规划转换为解一系列规模相对较小的子问题，但这样做分解法的 收敛速度较慢，训练时间也很较长，对于样本规模很大的问题并不适用，于是必 须变换思考角度，从第一种方法入手，以牺牲少量的分类精度为代价，提高训练 速度，从而提出了几种变形的s v m 。 最小二乘s v m ( l s - s ) ： l s s 是由s u y k e n s 硼dv 卸d e w a l l e 于1 9 9 9 年提出的，他们对标准支持 向量机的表达式做了两个改动：首先松弛变量改成平方型，其次将不等式约束改 成等式约束，最终该方法优化问题的表达式为： m t n 三( w w ) + c ( 喜参2 )4 ， 咒( 矿毛+ 6 ) = l 一百 f = l ，2 ， 从公式中可以看到最小平方s v m 用等式约束代替了不等式约束，这样分类 的方程完全转化成了线性方程组系统，反观标准的s v m 需要解一个二次或线性 规划的问题，并由于其组合特性，不可能明确写出解的表达式，因此标准的s v m 训练时间要长，在应用结构风险最小化原则时，两者的优化目标函数选取了不同 形式的损失函数。实验亦表明，用标准形式的s v m 训练的分类器要比最小二乘 s v m 训练的分类器具有更高的分类正确率，而最小二乘s v m 收敛速度贝0 相对更 快，但是。标准s v m 在求解凸二次规划时，得到应该是全局最优解，而且是唯 j 1 6 第二章支持向量机的基本理论 一的，但如果样本的数量特别大，那么求解时所耗费的计算时间会相当的长。相 比之下最小二乘s v m 求是在解一个线性方程，虽然它的解不一定全局最优解， 但求解线性方程的速度明显要比求解凸二次规划快得多，并且所耗费的计算资源 也会少很多。 拉格朗日s v m ： 与标准的s v m 相比，拉格朗日s v m 在目标函数中加入了附加项6 2 2 。它 的表达式为： m ；n 撕1 2 + 6 2 ) + c 喜磊 ( 2 - 2 5 ) s u b j e c tt 0 咒( ( w ，x ) + 6 ) l 一缶，v f 虽然只是增加了6 2 2 ，对于样本的输入空间来说也许只是个比较小的改动， 但对于目标函数来说它是强凸的，并且使得对偶问题中等式的约束先消失了，其 对偶问题是： 呼如一q 口 口， s u b j e c t t 0 口 0