（计算机应用技术专业论文）支持向量机研究及其在人脸检测中的应用.pdf

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 e l e a r n i n gm e t h o dd e v e l o p e do ns t a t i s t i c s l e a r n i n gt h e o r y i t s h o w sg r e a t a d v a n t a g e s i n r e s o l v i n g t h e p r o b l e m ss u c h a s s m a l l 。s a m p l e s ，n o n l i n e a ra n dh y p e r - h i g hd i m e n s i o ni np a t t e r nr e c o g n i t i o nd o m a i n t h e r e a ld a t aa r eo f t e n l i n e a r l yi n s e p a r a b l ei nt h ei n p u ts p a c e t oo v e r c o m et h i s ，d a t aa r e m a p p e di n t oah i g hd i m e n s i o n a lf e a t u r es p a c e ，i nw h i c ht h ed a t aa r es p a r s ea n dp o s s i b l y m o r es e p a r a b l e i np r a c t i c e ，t h em a p p i n gi sa l s on o te x p l i c i t l yg i v e n i n s t e a d ，ak e r n e l f u n c t i o ni si n c o r p o r a t e dt os i m p l i f yt h ec o m p u t a t i o no ft h ei n n e rp r o d u c tv a l u eo ft h e t r a n s f o r m e dd a t ai nt h ef e a t u r es p a c e h o wt os e l e c tt h ea p p r o p r i a t ep a r a m e t e r sf o rt h e k e r n e lf u n c t i o nq u i c k l yi so u rr e s e a r c hw o r k f a c er e c o g n i t i o nh a sm a n yp o t e n t i a l a p p l i c a t i o n s ，s u c h a s s e c u r i t ys y s t e m s ， h u m a n m a c h i n ei n t e r f a c e ，v i d e od a t a b a s es e a r c h ，w o r l dw i d ew e b ，e t c c o n v e n t i o n a l f a c er e c o g n i t i o nm e t h o d sa p p l yo n ek e r n e lt o g l o b a lf e a t u r e sa n dg l o b a lf e a t u r e sa r e i n f l u e n c e de a s i l yb yn o i s eo ro c c l u s i o n ，t h u st h ec o n v e n t i o n a lm e t h o d sa r en o tr o b u s tt o o c c l u s i o n t h i sa r t i c l em a i n l yc o n t a i n st h ef o l l o w i n gt w op a r t sb a s e do nt h et w op r o b l e m s a b o v e ： ( 1 ) f o rt h ep r o b l e mo ft h es e l e c t i o no ft h ek e m e lp a r a m e t e r , w eu s et h em e t h o d w h i c hc o m b i n e st h ei n t e r - c l u s t e rd i s t a n c e si nt h ef e a t u r es p a c e sa n dt h em i x e dk e r n e l f u n c t i o nt or e s o l v e c a l c u l a t i n gs u c hd i s t a n c ec o s t sm u c hl e s s c o m p u t a t i o nt i m et h a n t r a i n i n gt h ec o r r e s p o n d i n gs v mc l a s s i f i e r s t h u st h ep r o p e rk e r n e lp a r a m e t e r sc a nb e c h o s e nm u c hf a s t e r a n dt h et e s t i n ga c c u r a c yi sh i g h e rt h a nt h es t a n d a r do n e s ( 2 ) f o rt h ep r o b l e mo fg l o b a lf e a t u r e sa r ei n f l u e n c e de a s i l yb yn o i s eo ro c c l u s i o n w ea p p l yt h el o c a lg a u s s i a nk e r n e l st ol o c a lf e a t u r e s i nt h i s p a p e r , t h es u m m a t i o no f l o c a lg a u s s i a nk e r n e l si su s e da st h ei n t e g r a t i o nm e t h o d t h e nw eg e tl o c a lg a u s s i a n k e m e l a f t e rt h a tw eu s ef u z z ys u p p o r tv e c t o rm a c h i n ei n s t e a do ft r a d i t i o n a l s u p p o r t v e c t o rm a c h i n e e x p e r i m e n t ss h o w n t h a t ，i nt h ec a s eo ft h ep a r t i a lo c c l u s i o n ，t h i sm e t h o d h a sah i g hr e c o g n i t i o nr a t e k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ；f u z z ys u p p o r tv e c t o r m a c h i n e ；k e r n e l p a r a m e t e r ；l o c a lg a u s s i a nk e r n e l 目录 第1 章绪论1 1 1 研究背景1 1 1 1 支持向量机一1 1 1 2 人脸识别1 1 2 课题研究意义一2 1 3 本文：i ：作概述3 1 3 1 创新点一3 1 3 2 章节结构3 第2 章基本理论4 2 1 统计学习理论4 2 1 1 函数集的v c 维。4 2 1 2 损失函数、期单风险、经验风险4 2 1 3 结构风险最小化原则5 2 2 支持向量机6 2 2 1 线性可分支持向晕分类机7 2 2 2 线性支持向量分类机。9 2 2 3 支持向黾分类机。1l 2 3 基于支持向量机的多类分类方法一1 5 2 3 1 一对多方法( o n e a g a id s l t h er e s t ) 1 5 2 3 2 一对一方法( o n e a g a i n s t o n e ) 1 6 2 3 3d a g 方法1 7 2 4 模糊支持向量机1 8 2 4 1 输入样本的模糊属性1 8 2 4 2 支持向阜机的再构1 9 2 4 3 基于f s v m 的多类分类方法2 l 2 5 本章小结2 4 第3 章混合s v m 核函数及其参数的选择2 5 3 1 弓i 吉2 5 3 2 几种常用的核函数2 5 3 3 混合核函数2 7 3 4 核参数的选择方法2 8 3 5 利用群间距离选择核参数：- 2 9 3 6 实验结果与分析3 2 3 7 本章小结3 3 第4 章支持向量机在人脸识别中的应用3 4 4 1 引言3 4 4 2 人脸识别的相关研究3 4 4 3 局部遮挡情况下的人脸识别3 5 4 3 1g a b o r 滤波器3 6 4 3 2 局部高斯核函数s v m 3 6 4 4 实验结果与分析 3 8 4 5 本章小结4 0 第5 章总结与展望4 1 5 1 总结4 1 5 2 展望4 l 参考文献4 2 攻读硕士学位期间的研究成果4 5 致谢4 6 学位论文独创性声明4 7 学位论文知识产权权属声明4 7 第1 章绪论 1 1 研究背景 1 1 1 支持向量机 第1 章绪论 支持向量机【i 】( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是数据挖掘中的一项新技术，是 借助于最优化方法解决机器学习i 、u j 题的新工具。它最初足在2 0 世纪9 0 年代由 v a p n i k 在统计学习理论【2 3 】基础上提出的，以结构风险最小化原则以及v c 维理沦为 理论基础，在解决小样本，非线性和高维模式识别问题中表现出许多其它机器学习 方法不可比拟的优势，近年来在理论研究和应用方面都取得了令人瞩目的发展。 理论上主要有模糊支持向量机，最小二乘支持向量机，加权支持向量机，粗糙 集与支持向量机的结合，基于决策树的支持向量机，分级聚类的支持向量机，核函 数的构造和参数的选择理论研究等等。 应用方面主要主要有人脸识别，网络入侵检测，分类，回归，时i 、h j 序列预测， 生物信息，数据挖掘，金融工程，生物医药信号处理，文本挖掘，自适应信号处理， 剪接位点识别，缺陷识别，基于支持向量机的数据库学习算法，计算机键盘用户身 份验证，视频宁幕的自动定位于提取，说话人声音的确认等等。 支持向量机最初是针对二类分类问题提出的，但在实际应用中往往是多类分类 问题，因此，将支持向量机推，1 。到多类分类问题成为同前s v m 研究的热点问题之一。 到目前为止，已提出了许多解决多类分类问题的方法，如“对一”方法【4 1 ，“一对 多 方法【5 】，d a g 方法【6 】，纠错编码方法【7 1 ，二叉树支持向量机【8 】，模糊支持向量机【9 】 等。很多学者对支持向量机多类分类方法进行了总结与进一步的研究，如台湾大学 的c h i h w e i 等人对“一对一 方法，“一对多”方法和d a g 方法进行了深入研究 【1 0 】；刘志刚等人还增加了对纠错编码支持向量机和层次支持向量机的研究】。可以 将目前已提出的支持向量机多类分类方法分为两类：一类是一次性求解方法，它实 际是标准二次优化问题的推广；另一类足将多类问题转化为多个两类问题。后一种 方法无论从训练速度还是从分类精度考虑都优于日仃者，因此，目前主要的多类分类 算法都是基于后一种方法提出的。 1 1 2 人脸识别 人脸识别技术【1 2 ，1 3 ，1 4 1 就是通过计算机提取人脸的特征，并根据这些特征进行身 份验证的一种技术。人脸与人体的其他生物特征( 指纹、虹膜等) 一样与生俱来，它 青岛人 - - 7 ：倾i j 学位论文 们所具有的唯一性和不易被复制的良好特性为身份鉴别提供了必要的日，j 提；同其他 生物特征识别技术相比，人脸识别技术具有操作简单、结果直观、隐蔽性好的优越 性。因此，人脸识别在信息安全、刑市侦破、出入口控制等领域具有广泛的应用自订 景。 2 0 世纪6 0 年代木至7 0 年代初，人脸i ：5 别研究刚刚起步。最早的研究者是 b l e d s o e ，他建立了一个半自动的人脸识别系统，主要是以人脸特征点的问距、比率 等参数为特征。早期的人脸识别方法有两大特点：( 1 ) 大多数识别方法是基于局部 的，它们利用人脸的几何特征进行谚 别，提取的信息是人脸主要器官特征信息及其 之间的几何关系。这类方法比较单，但很容易丢失人脸的有用信息，从而在视角、 表情等出现变化的情况下识别能力差。鉴于这科，情况，后来出现了性能较优模板匹 配方法，即根据图像库中的人脸模板与待识别人脸模板在狄度上的相似程度来实现 人脸识别，这类方法在一定时期内占据主流。( 2 ) 人脸识别研究主要是在较强约束 条件下人脸图像识别。假设图像背景单一或无背景，人脸位置已知很容易获得，因 此对现实场景产生的图像处理效果不佳。 2 0 世纪9 0 年代以来，随着计算机软硬件的迅速发展，以及对人脸识别能力的 高要求，使发展更具鲁棒性的人脸识别方法成为必然。于是基于整体的谚 别方法出 现，并且很快成为研究的重点，基于整体的识别方法充分利用了人脸各个特征点之 间的拓扑关系和各个器官自身的信息，可以避免提取面部局部特征的操作，使识别 鲁棒性有所提高。于是，在人脸识别的研究领域出现了基于整体的方法和基于局部 的方法并存的局面。 9 0 年代中期以来，人脸识别方法向着整体识别和局部分析相结合的趋势发展。 研究人员丌始逐渐认识到人脸识别算法必须能够充分地利用人脸的各种特征信息， 融合人脸的形状拓扑结构特征、局部灰度特征和全局狄度分析j 特征等多种特钿f 。冈 此，出现了很多新的算法，这些算法是将原先单一的算法结合起来，共同完成人脸 的识别。 9 0 年代后期，一些商业性的人脸识别系统丌始逐渐进入市场，人脸谚 别技术成 为当今国际安全防范最重要的手段之一。但是，这些技术和系统离实际应用还有一 定的距离，性能和准确率有待提高。 2 0 0 0 年前后，人脸识别方法的性能虽然有了一定的提高，但仍与人们的要求有 一定的差距，现有方法对光照、年龄、表情、姿态、距离等条件的变化比较敏感， 当某些条件发生变化时，识别效果不够理想。 1 2 课题研究意义 支持向量机最初是针对二类分类问题而提出的，如何将其有效的推广到多类分 2 类问题仍是当自订s v m 研究的重要内容之一。目d 仃，对于多类分类问题，s v m 的解 决途径有两种：一种足通过构造多个s v m 二类分类器并将它们组合起来实现多类分 类；另一种是直接在一个优化公式中同时考虑所有子分类器的参数优化。前者的缺 点是每个子分类器必须都要非常仔细地调整，如果某个子分类器小规范，则整个分 类系统将趋f 过学习；后者的缺点是与前者相比，在最优化问题求解过程巾的变量 远远多于自订者，并且训练速度慢，分类精度差。冈此，构造优化的多分类s v m 分 类器以及如何快速有效地选择合适的参数具有重要的意义。 目日i ，人脸识别在一个有限制的环境巾具有非常高的准确率。但足，在实际环 境中的人脸识别仍然有许多问题需要克服，比如当有遮挡，光照改变，姿态改变时， 识别的准确率将会大大降低。因此我们希望找到一种用于实际环境中的准确有效的 识别方法。 1 3 本文工作概述 1 3 1 创新点 ( 1 ) 在支持向量机的训练过程中，我们把群间距离和混合核函数结合起来决定 核函数的参数，这样能在时间复杂度不是很高的情况下进一步增加准确率。 ( 2 ) 在人脸谚 别过程中，我们对输入样本附加一个模糊隶属度，使厂玎模糊支持 向量机，并且使用局部高斯加和核函数来增加人脸议别的准确率。 1 3 2 章节结构 本文共分为5 章，各章内容编排如下： 第一章绪论主要介绍支持向量机和人脸识别的研究现状，课题的研究意义，论 文创新点和章节的结构。 第二章主要介绍统计学习的基本理沦，支持向量机的基本理沦，同时详细介绍 模糊支持向量机的基本原理。 第三章我们介绍一种确定支持向量机核参数的方法通过计算群间距离末 确定参数。 第四章我们使用模糊支持向量机，并且采用局部高斯加和核函数来增加人脸识 别的正确率。 第五章总结与展望。对本文所做工作进行总结，并对进一步的研究提出几点看 法。 第2 审桀奉理论 2 1 统计学习理论 第2 章基本理论 统计学习理沦【3 1 ( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 是由v a p n i k 等人提出的，针对 有限样本情况研究统计学习规律的理沦，是对传统统计学理论的发展和补充，为有 限样本的机器学习问题建立了良好的理论基础。 2 1 1 函数集的v c 维 由于支持向量机是建立在v c 维和结构风险最小化理沦基础之上，因此我们首先 来介绍下v c 维理论【1 ，2 ，”。 模式识别中v c 维的直观定义是：对于一个指示函数集，如果存在刀个样本能够 被函数集中的函数按所有可能的2 ”种形式分丌，则称函数集能够把n 个样本打散， 函数集的v c 维就是它能打散的最大样本数目n 。若对任意数日的样本都有函数能 够将它们打散，则函数集的v c 维就是无穷大。有界实函数的v c 维可以通过用一 定的阂值将它转化成指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂，所以v c 维又 是学习机器复杂程度的一种衡量。但是到目前为止，对于任意函数集的v c 维的计 算还没有系统的理论体系，只能知道一些特殊的函数集的v c 维，例如在n 维实数 空问中，线性分类器和线性实函数的v c 维是n + l ，而对于一些比较复杂的学习机 器，其v c 维除了与函数集有关外，还受学习算法等的影响，所以要确定其v c 维 就更加困难。对于给定函数集的v c 维的计算仍然是目前统计学习理论中值得研究 的一个问题。 2 1 2 损失函数、期望风险、经验风险 为了理解结构风险最小化准则，我们先来介绍损失函数、期望风险、经验风险 的概念【1 ，2 1 。 定义2 1 1 ( 损失函数)设xcr ”，y = 一l ，1 ) 。引进三元组 ( x ，y ，厂( x ) ) x y 】厂，其中x 是一个模式，y 是一个观察值，f ( x ) 是一个假 设值( 或称预测值) 。若映射c ：x y y 寸 o ，o o ) 使得对任意的x x ，y y ， 4 青岛人学烦i j 学位论义 都有c ( x ，y ，y ) = 0 ，则称c 是一个损失函数。 简单的说，损失函数c ( x ，y ，y ) 是当f ( x ) = y 时c ( x ，y ，厂( x ) ) = 0 的函数。其 含义是，当预测准确无误时，损失值为零( 无损失发生) 。当然实际上我们还常常要 求当预测有误差时，或者当误差达到一定程度时，其损失值不为零。 定义2 1 2 ( 期望风险) 设p ( x ，少) 为x y 上的概率分布，c 为给定的损失函 数。再设( x ) 是一个假设( 决策函数) f ：x ( xcr ”) 专y = 一1 ，1 ) 2 一( 1 ) 所谓假设f ( x ) 的期望风险是指损失函数关于概率分前ip ( x ，y ) 的r i e m a n n s t i e l t j e s 积分 r f a a e c ( z ，y ，( x ) ) = i x 。yc ( 石，y ，( 石) ) d p ( x ，y ) 2 一( 2 ) 定义2 1 3 ( 经验j x l 险) 设给定训练集t = ( ，y 。) ，( x ，y ，) ( x xy ) ，其 中x ，xcr ”，y y = 一l ，1 ) ，i = 1 ，并且给定损失函数c 。所谓假设f ( x ) 对于它们的经验风险是指 = 手套c ( x i , y i , 似f ) ) 2 ( 3 ) 2 1 3 结构风险最小化原则 首先考虑最简单的两类模式识别问题：有，个训练样玉彤，z = l ，2 ，j ，每个 样奉的类标为只 - 1 ，+ 1 ) ，两两样本之间相互独立并且服从同一未知的概率分布 p ( x ，y ) 。模式识别就是根据训练集中x i 和y ，之f u j 的对应关系，找到一个映射 ：尺”专 一1 ，+ 1 ) ，使这个映射能很好地描述概率分布尸( z ，y ) 。该映射就是所谓 的分类器，它是一个函数，一般带有一个或多个参数( 此处，我们统一用参数向量口 来表示) 。通常，函数厂( 口) 被称为假设( h y p o l h e s is ) ，函数集合 厂( 口) i 口人 被称 为假设空间( h y p o t h e s i ss p a c e ) ，用字符丸表示，其中人为口的取值范围。 气 第2 章皋奉理论 一般情况下，对于某个特定问题，会存在多个分类器厂，它们都能反映出训练 集中样本和类标之问的关系，我们希望找到的分类器能准确地对未知样本进行识别， 那该如何去找呢? 一个重要的原则就是风险最小化，即我们选择的分类器厂，与其 它未被选择的分类器相比，具有更小的风险。常见的风险最小化原则有期望风险最 小化原则，经验风险最小化原则和结构风险最小化原则。我们重点讨论结构风险最 小化原则，因为它是支持向量机的支撑理谢1 ，2 ，3 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 ) 同时考虑到分类器厂j ：口) 的 容量和训练误差，希望在两者之间找到一个较理想的平衡点。一般情况下，分类器 的容量大小取决于参数口，参数的个数越多，函数就越复杂，分类器的容量就越大， 映射能力( 即学习能力) 就越强，训练误差就越小。这早的容量( c a p a c i t y ) 是指分类器 厂( 口) 能无误差地对任何训练集进行映射的能力。 结构风险最小化原则的理论基础是v c 边界，该边界是期望风险的一个概率边 界，并且与未知样本的概率分布p ( x ，y ) 无关。对于分类器( 6 ) ， v c 边界的定义如 下： r ( 口) r 。，口( 口) + 2 一( 4 ) 其中，h 是一个非负整数，称作v c 维度( v cd i m e n s i o n ) ，r 【o ，1 】是一个参数， 当h 0 是一个惩罚参数。 下面我们求原始问题2 一( 2 1 ) ，2 一( 2 2 ) ，2 一( 2 3 ) 的对偶问题： 类似于线性可分的情况，引入l a g ：r a n g e 函数得到： 9 、- 、少 葺 ，i - 一 。q y ，h y = 6 第2 章皋奉理论 她蝣双舻帅2 + 嘻i 缶一善i 吣f ( ( w 训+ 6 ) _ 1 + 伊喜层毒 2 一( 2 4 ) 其中，口，o ，p i 0 ，根据w b l f e 对偶定义，对l 关于w ，b ，善求极小，得 塑氅挈盟：o 一圭哪，：o 2 也5 ) a b鼍“t 丝! 兰! 垒! 主! 竺! 望! ：o o w 2 一( 2 6 ) 垦生垒竺掣：o c 一口，一屈：o 2 一( 2 7 ) d 亡 然后将上述极值条件代入l a g r a n g e 函数，得到对偶问题： 吉喜赛y 岍叫x 。 ， t s t yy ：i g g i 0 乙 2 ，= 1 0 口，c ，i = 1 ，j 求此最优化l 、口j 题得到口+ = ( 口i i ，口j ) 7 ，所以w + 2 一( 2 8 ) 2 一( 2 9 ) 2 一( 3 0 ) 选择口+ 的一个 i 分量0 口j c ，并据此计算b = y ，一y f a i ( x ，y i ) ，由此求得决策函数为 f = l f ( x ) = s g n ( ( w + x ) + b + ) 。 l o x y 口 ，h = w 优 ，h 一 、 x x + 口 y ， = 青岛人学硕i j 学位论文 2 2 3 支持向量分类机 上文主要讨论了线性可分和线性不可分两种情况，但现实中大多数样本在其原 来的空i b j 中是非线性不可分的。举个例子：如图2 2 所示的分类问题，实心网点表 示证类，空心圆点表示负类，这显然不能使用i j 仃而给出的线性支持向量分类机。图 中，记其对应的训练集为t = ( 誓，y f ) f = l ，2 0 ) ，其中xf 是( 叫。， x 】：) 平面上 的点：x i = ( 一】，i x f 】2 ) 7 ，y ，= 一l ，l ，可以猜想，比较合理的分划线是平面 ( x 】。，【x 】：) 上的一个椭圆 叫。 x 2 + w 】： x e + 6 = 0 ，其中【w ，【w ：，b 都是常数。 x 】2 、 o oo ，一 o - 、 f、 叉 儿 i q 00 图2 2 映射前两类关系 现在的l 司题是如伺求出这个非线性分划( 椭圆) ，前丽我们已经有了寻找线性分 划( 直线) 的方法，所以我们希望仍然使用线性分划方法来求出这个椭圆。为此我们 考虑从( 【引， x 】：) 平面上的点x = ( x 。， x ：) 7 到平面( x 】。，i x ：) 上的点 x = ( x 】。，i x ：) 7 的映射x = ( z ) = ( x 】；， x 】；) ，它把( x 】。，【x 】：) 甲面上的椭圆 w 】。i x ；+ w ： x 筻+ 6 = 0 映射到( x 】。， x ：) 平面上的一条直线 w l x 】l + w ： x ：+ 6 = 0 ，如图2 3 所示。所以我们只要用映射把 ( 【x 】l ， x 】2 ) 平面上的两类训练点分别映射到( x 。， x ：) 平面上，然后在 ( x 】。，i x ：) 平面上使用线性学习机求出分划直线，最后再把分划直线映射回平面 第2 章皋奉埋论 ( 【叫， x 】：) ，就得到所要的非线性分划( 椭圆) 了。 x l 图2 3 映射斤两类火系 现在我们来看一个更加广泛的例子。设t = ( x ，y ，) ，f = l ，) ，其中 x ，= ( x f l ，【x ， 2 ) r ，y ，= - 1 ，1 ) ，假设可以通过x = ( x 】， x ：) 平面上的一个二次 曲线 【w 】l + 2 w 】2 x 】l + 2 w 】3 x 2 + 2 【w 】4 【x 】l x 2 + w 5 【x 】；+ 【w 6 x ；+ b = 0 2 一( 3 1 ) 来划分。这时我们可以考虑把二维空间x = ( x 。，【x 】：) 7 映射到六维空i 日j x = ( 【x 。， x 】：，i x 3 ， x 】。，i x ，i x 。) 7 的变换： ( x ) = ( 1 ，压 x 】。，压 x 】：，压 石】：， x 2 x 】；) 7 2 一( 3 2 ) 通过映射，可以把二次曲线2 一( 3 1 ) 映射到六维空间x 上的超平面 w 。 x 】。+ 压 w ： x ：+ 压【w 】， x ，+ 习w 】4 i x 4 “w ，i x ，+ w 】。i x 。+ 6 = 0 2 一( 3 3 ) 我们利用变换2 一( 3 2 ) 把二维空间中的两类输入点，映射到六维空问中，然后用线性 学习机求出分划超平面( w x ) + 6 = 0 ，其中，w + = ( w + 】i ，一，【w + 】6 ) 7 ，最后得到 原空间中的分划二次曲线 w + 】l + 2 【w + 】2 【x 】l + 2 w + 3 x 】2 + 2 广 4 i x l i x 2 + 【w + 】5 i x ；+ w + 】6 【x 】；+ 6 = 0 2 一( 3 4 ) 1 2 青岛人学硕i j 学位论文 为求六维窄i 自j 中的分划超、f 面，我们采用线性支持向量分类l j l l ，此时，需要求解的 最优化问题为 m 口i n吉y ，少a ，口- ，( ( x ，) ( x ) ) 一口， 2 一( 3 5 ) “ 二i = l ，= l ，= l s t y f 口，= 0 ， 2 一( 3 6 ) 其中 0 口c ，i = l ，j 2 一( 3 7 ) m ( x ，) = ( 1 ，压i x 】l ，压i x f 】2 ，压i x f 】ii x ，i x 所 x 夏) r 2 一( 3 8 ) 。( x ，) = ( 1 ，掘x ，压【x a ，橱x i x a ，i x 属 x 戌2 ) r 2 一( 3 9 ) ( m ( x i ) o 川是( x ，) 和巾( x ，) 的内积。 ( ( t ) 似t ) ) = 1 + 2 k ， x a 。+ 2 t 】： _ 】：+ 2 一】。 誓 ：盹】 x a ：+ 【誓】； _ 】；+ 【誓筻【_ 】； 2 一( 4 0 ) 求得2 一( 3 5 ) 一2 一( 3 7 ) 的解口+ = ( 口i - ，口j ) 7 后，就可求得分划超平血 ( w 。x ) + b + = 0 2 一( 4 1 ) 其中 ，i w = z y ，口? 似x ，) ，b = y ，一y ，a j ( ( 石，) 中( x ) ) ， j | o a ； c ( 2 4 2 ) f = lf - l 最后得到决策函数为 ， ( 石) = s g n ( a ；4 y ，( ( x ) ( x + 6 ) 2 一( 4 3 ) ，= l 从上面可以看出，原来只需要计算二维空问中的内积( x ，y ，) ，现在则需要计 算六维空间中的内积( ( x ，) ( x ，) ) ，因此会增加计算难度，为此，我们引入个 函数 k ( x ，少，) = ( ( x f x j ) + 1 ) 2 2 一( 4 4 ) 笫2 章皋奉理论 则有 k ( x ，y ，) = ( ( 一x - ，) + 1 ) 2 = ( x ， l x 】i + 【x ， 2 【x 2 + 1 ) 2 = 誓】； _ ；+ k 】；p 压+ l + 2 誓 k ： 誓，】i _ 】：+ 2 誓】， t 。+ 她 2 【_ ： 通过比较2 一( 4 0 ) 和2 一( 4 5 ) 我们发现 2 一( 4 5 ) ( ( x ，) ( x _ ，) ) = k ( x ，y ，) = ( ( x f x j ) + 1 ) 2 2 一( 4 6 ) 这说明要计算六维空i 日j 中的内积( q 一) q t ) ) ，我们可以通过计算二维空| 日j 中的内 积( x ，y ，) 来得到，因此2 一( 3 5 ) 一2 一( 3 7 ) 可以写为 去y f y _ ，嘭口，( ( _ 石- ，) + 1 ) 2 - z 口 2 一( 4 7 ) 厶f = i ，= lf = l 0 口_ ，c ，i = 1 ，j 最后得到的决策函数就可表示为 2 一( 4 8 ) 2 一( 4 9 ) ， ( x ) = s g n ( 口；i y 烈x ，x ) + 1 ) 2 + 6 ) 2 一( 5 0 ) x ，) + 1 ) 2 ，je j i o a ； c ) 。 通过观察2 一( 5 0 ) 我们发现，决策函数是山口+ 和k ( 善，x ，) 确定的函数，而也 是由函数k ( x ，石j ) 确定的，因此在给定了训练点后，决策函数只依赖函数 k ( x ，x ，) 。也就是说，我们只需要考虑函数x ( x ，x ，) ，而不需要知道非线性变换 ，就可以求出决策函数，这旱函数k ( x ，工j ) 称为核函数。 由此我们得出支持向量分类机川 1 4 o = 口 y ，h l吼 x “ 十 f 口 y ，h y = 6 中其 青岛人学帧i j 学位论义 ( 1 )设已知训 练集t = ( _ ，y 。) ，( x ，乃) ) ( x xy ) ，其中 x ，xcr 一，y y = 一1 ，l ，i = 1 ，； ( 2 ) 选择核函数k ( x ，x ，) 和惩罚参数c ，构造并求解最优化l 、u j 题 去y ，少_ ，口f 倥k ( x i ，x j ) 一口， 2 一( 5 1 ) 二i = l ，= 1i = l 0 o f _ ，c ，i = l ，j 得最优解口+ = ( 口i - ，口? ) 7 ； 2 一( 5 2 ) 2 一( 5 3 ) ， ( 3 ) 选择口+ 的一个小于c 的f 分量，以此计算6 + = j ，一y ，a i k ( x ，x ，) ； ， ( 4 ) 求决策函数厂( x ) = s g n ( 口i + y ，k ( x ，x ) + 6 + ) 。 2 3 基于支持向量机的多类分类方法 上一节我们详细介绍了支持向量机，它最初是针对二二类分类i 、u j 题提出的，但在 实际应用中往往是多类分类问题，因此下面我们介绍几种基本的多类分类方法。 2 3 1 一对多方法( o n e a g a in s t t h er e s t ) 一对多方法【1 , 5 】是支持向量机多类分类中最早使用的算法。其策略是在训练集中 构造一系列两类分类器，每一个分类器都把其中一类同剩下的各类分，i ：。没己知洲 练集 丁= ( x l ，y 1 ) ，( _ ，少f ) ) e ( xx 】厂) 7 ， 其中x f xcr ”，y y = 1 ，尼 ，i = 1 ，j 对j = l ，k 进行如下运算，把第类看做i f 类，剩下的尼一l 看做负类，用支持向 量机求出决策函数 o i | 口 少 ，纠 l吼 - i okii-rof。-【lrl_r 笫2 章甚奉埋论 其中 f 7 ( x ) = s g n ( g 。( x ) ) 2 一( 5 4 ) ， 9 7 ( x ) = y ，a k ( x ，x ，) + 6 7 2 一( 5 5 ) ，= l 判定输入x 属于第j 类，其中d 是9 1 ( 曲，g ( 曲中最大者的上标。但是当有两 个决策函数值都达到最大时，便无法判断x 属于哪一类，即使两个决策函数值相差 很少时，其推断结果页很不可信，为此我们引入一个适当的闽值口，而把两个最大 的决策函数值的差作为可推断一个输入x 的归属置信度，如果这个差值小于给定的 阈值p ，那就不把它归入任何一类中，这样做会降低错误率。 2 3 2 一对一方法( o n e a g ain s t - o n e ) 一对一方法【1 4 】也是基于两类问题的分类方法，不过这罩的两类问题是从原来的 多类问题中抽取的。其具体做法如下：考虑k 类的分类问题，设训练集 t = ( x l ，y ) ，( ，乃) ) ( x x 】，) 。 其中x f xcr 疗，y y = 1 ，尼) ，f = l ，j ，a ) k i ) t l 练集中抽取所有y = f 和 y = j 的样本点，( f ，j ) ( f ，) l f ，f ，j = 1 ，k ) 。基于这些样本点组成一个训练 集i 一，用求解两类分类问题的支持向量分类机求得实值函数g 卜。( x ) 和判定 x x 属于第f 类或第类的分类机 h 加 ：j ；麓咖。 2 娟6 ， 然后在需要对给定的一个输入x 判断它属于k 类中的第几类时，我们考虑上述所有 的分类机对x 所属类别的意见，如果一个分类机判断x 属于第f 类，那么第f 类 就获得一票，最后得票书最多的类就是石所属的类。 1 6 青岛人学颂 ：学位论文 这种分类方法，需要许多两类分类机，对于k 类问题，就需要丛生尘个两类 2 分类机，这要比一对多方法得到的分类机数日大得多，但是这攀的每一个两类分类 机，都比一对多方法中的两类分类机的规模小，并且由于类别有较小的重合，要学 习的问题也比较简单。 尽管如此，当k 很人时，k ( k - 1 ) 就会非常大，此时一对一方法就比一对多方 z 法慢。实际上可能并不需要求丛业个两类分类机，比如在对数字谚 别中，在计 = z 算了若干两类分类机后，发现数字6 和8 的票都很少，已经不可能是票数最多的， 这时候再计算6 8 分类机就成了一种t 良费。 2 3 3d a g 方法 d a g 方法【6 】即有向无环图( d i r e c t e da c y c l i cg r a p h ) 方法，在训练阶段也是采用 一对一方法的任意两两组合的训练方式，也需要构造丛生坐个两类分类器，但在 2 分类过程中，d a g 方法将所有分类器构造成一个有向无坏图，如图2 4 ( 5 类分类) 所示，包括掣各内部节点和k 个叶子节点，每个节点是一个分类器。对未知 z 样本测试时，首先从顶部根节点开始，根据分类结果用下一层危节点或右节点继续 分类，直至达到底层某个叶子节点为止，该叶子节点所表示的类就是未知样本所属 的类。可见，d a g 方法只需使用k - 1 个决策函数就可以得出结果，分类速度较一对 多方法和一对一方法快，而且不存在误分，拒分区域。其缺点足末考虑样本不平衡 数据对分类速度的影响，而且还会有误差累积的现象，另外根节点的选择不同，会 使分类结果町能不同，导致结果的不确定性。 1 7 第2 章粜本删论 4 图2 4d a g 方法分类示意图 上面我们介绍了几种常用的基于支持向量机的多类分类方法，另外还有二叉树 方法，纠错输入编码方法，m a r y 支持向量机，这艰就不再一一介绍了。由于本文