（计算机应用技术专业论文）支持向量机和非负矩阵分解理论方法的应用.pdf

j lj-_， ；， 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均己在论文中做了明确的声明并表示 谢意。 ， 学位论文作者签名： 童! l 亟自 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名： 曼! l 亟鱼一 指导教师签名： 签名日期： v _ 年 f 易月7 日 f ij蜘l，瓠；耔辩薰滋鬻寥，。； 辽宁师范大学硕士学位论文 摘要 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 最初于2 0 世纪9 0 年代由v a p n i k 提出， 它采用和传统方法不同的统计学习理论( s l t ) 为基础，是借助最优化方法解决机器学习 问题的一种数据挖掘新工具。近年来随着研究的不断深入，其理论研究和实际应用都取 得了突破性进展，尤其对维数灾难和过学习等传统方法较难解决的问题表现出了较大的 优势，并非常成功的处理了回归和模式识别等诸多问题。目前，s v m 己成为国际上机 器学习领域研究的热点。 非负矩阵分解( n o n n e g a t i v em a t r i xf a c t o r i z a t i o n ，n m f ) 理论由d d l e e 和h s s e u n g 于1 9 9 9 年在n a t u r e ) ) 上首次提出，它提取图像的局部特征，更加符合心理学和生理学 对事物的直观理解，由于其非负性的约束，也使得非负矩阵分解不同于以往的矩阵分解， 它克服了传统矩阵分解的不足，使分解后的所有分量均为非负值，也就是要求纯加性的 描述，并且实现了非线性的维数约减，在提出之始就引起了国内外学者的广泛关注。非 负矩阵分解最初成功应用在人脸识别方面，近些年来己涉及到信号处理，生物医学工程， 模式识别，计算机视觉，网络安全等众多研究领域。 本文主要围绕s v m 和n m f 相关理论展开，主要工作有如下两个部分： 1 首次使用基于正态分布概率的万型隶属度函数来计算模糊支持向量机( f s v m ) 样 本点的隶属值，根据正态分布的特性，在考虑数据分布规律的同时求得数据点的隶属值， 使求得的数据能够更加准确的反应样本的分布特点，提高了分类的准确率。 2 首次将非负矩阵分解( n m f ) 方法和全局的非线性降维方法i s o m a p 相结合，并应用 到图像检索实验中。使用n m f 提取图像的局部特征，在一定程度上勾勒出了相关图像 在基矩阵所代表空间上的分布，使用i s o m a p 方法降维，不仅使高维数据在低维空间变 得可视化，而且能发现数据的内在结构和相关性，通过实验证明了新算法的准确性和高 效性。 关键词：支持向量机；隶属度函数；非负矩阵分解；多维尺度分析；图像检索 jl1，一 支持向量机和非负矩阵分解理论方法的应用 t h e a p p l i c a t i o no fs u p p o r tv e c t o rm a c h i n ea n dn o n n e g a t i v em a t r i x f a c t o r i z a t i o nt h e o r ym e t h o d a b s tr a c t t h ev e c t o rs u p p o r tm a c h i n e ( s v m ) t e c h n o l o g yi san e wm o d e lw h i c hi sp r o p o s e db yv v a p n i ki nt h em i d9 0 s ，i ti sb a s e do nt h es 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 ) w h i c hi sd i f f e r e n t f r o mt h et r a d i t i o n a lc l a s s i f i c a t i o nm e t h o d s i ti san e wd a t am i n i n gt o o lu s i n go p t i m i z a t i o n m e t h o dt od e a l ，i t ht h em a c h i n el e a r n i n gp r o b l e m r e c e n t l yy e a r sw i mt h ed e e po ft h e r e s e a r c h ，b o t hi t st h e o r ya n da c t u a la p p l i c a t i o na c h i e v eag r e a tb r e a k t h r o u g h i ta p p e a r sa g r e a t e ra d v a n t a g et o t h ed i m e n s i o nr e d u c i n ga n do v e rf i t t i n gp r o b l e m s ，a l s oi ts o l v e s r e g r e s s i o na n dp a t t e r nr e c o g n i t i o np r o b l e ms u c c e s s f u l l y i nr e c e n t l yy e a r s ，s v mh a sb e e na h o tt o p i ci nt h em a c h i n el e a r n i n gf i l e d t h en o n - n e g a t i v em a t r i xf a c t o r i z a t i o n ( n m f ) t e c h n o l o g yf i r s t l yp r o p o s e db yd d l e ea n d h s s e u n gi n1 9 9 9i n ( ( n a t u r e ) ) ，i ti sa b l et ol e a r np a r t so f t h ei m a g et h a ti sp s y c h o l o g i c a la n d p h y s i o l o g i c a l e v i d e n c ef o rp a r t sb a s e dr e p r e s e n t a t i o n si nt h eb r a i n n o n - n e g a t i v em a t r i x f a c t o r i z a t i o n d i s t i n g u i s h e sf r o mt h eo t h e rm e t h o d sb e c a u s e i t su s eo fn o n - n e g a t i v i t y c o n s t r a i n s t h ec o n s t r a i n sl e a dt oap a r t s - b a s e dr e p r e s e n t a t i o nb e c a u s et h e ya l l o wo n l y a d d i t i v e ，n o ts u b t r a c t i v e ，c o m b i n a t i o n s n m fh a sc a u s eh u g ea t t e n t i o na tt h ev e r yb e g i n n i n g ， i ti sa p p l i e di nf a c er e c o g n i t i o nf i r s ta n da p p e a r sag o o dr e s u l t ，r e c e n t l yy e a r si th a si n v o l v e d i nal o to fa r e a ss u c ha ss i g n a lp r o c e s s i n g ，b i o m e d i c a le n g i n e e r i n g ，p a t t e r nr e c o g n i t i o n ， n e t w o r ks e c u r i t ya n ds oo n a r o u n dw i t l ls v ma n dn m f t h e r ea r et w om a i na s p e c t si nt h i sp a p e ra sf o l l o w s ： 1 i tf i r s tu t i l i z e sn o r m a ld i s t r i b u t i o nb a s e do nt h ep r o b a b i l i t yo fm e m b e r s h i pf u n c t i o n 万 t oc a l c u l a t et h ea m b i g u i t y , d u et ot h en o r m a ld i s t r i b u t i o nf e a t u r e ，t a k et h ed i s t r i b u t i o no ft h e d a t ai n t oc o n s i d e r a t i o nt oc a l c u l a t et h em e m b e r s h i p t h eo u t p u t sc a nr e f l e c tt h ec h a r a c t e r i s t i c o ft h em e m b e r s h i pm o r ea c c u r a t e l ya n di m p r o v e st h ec l a s s i f i c a t i o na c c u r a c y 2 t h e r ei san e wm e t h o d w h i c hi n t e g r a t e sn m fa n dn o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o n i s o m a pi sp r o p o s e d t h eg l o b a ld i m e n s i o n a l i t yr e d u c t i o nm e t h o dc a nd i s c o v e rt h ei n n e r s t r u c t u r ea n dr e l a t i v i t yo ft h ed a t a , i tm a k e st h eh i g hd i m e n s i o nd a t av i s u a l i z a t i o no nl o w e r s p a c e t h en m f i sal o c a ld a t am i n i n gm e t h o dw h i c hc a ne x t r a c tt h el o c a lf e a t u r eo fai m a g e ， i tc a l ld e s c r i b et h er e l e v a n ti m a g ed i s t r i b u t i o no nt h es p a c eo fb a s em a t r i xi ni m a g er e t r i e v a l e x p e r i m e n t ，t h em e t h o dc a no b t a i ni n f o r m a t i o nm o r ep r e c i s ea n di m p r o v et h ea c c u r a c y k e yw o r d s ：s v m ；m e m b e r s h i pf u n c t i o n ；n m f ；i s o m a p ；i m a g er e t r i e v a l i i 辽宁师范大学硕士学位论文 目录 摘要j ：i a b s t r a c t i i 第一部分支持向量机s v m 1 l 绪论1 1 1 研究背景及意义1 1 2 国内外研究现状一2 1 3 支持向量机的应用3 2 支持向量机模型5 2 1 相关知识5 2 1 1 统计学理论和v c 维5 。2 1 2 结构风险最小化原则5 2 1 3 核函数6 2 2 支持向量机模型推导7 2 3 序列最小最优化算法“1 2 2 3 1s m o 概述1 2 2 3 2s m o 两个变量的最优化问题解析解13 2 3 3s m o 两个训练点的选取15 2 3 4 一次成功优化后的更新1 6 2 4 停机准则18 3 结合正态分布概率的f s v m 。2 0 3 1 引言2 0 3 2f s v m 基本理论2 0 3 3 基于正态分布概率的f s v m 2 1 3 3 1 基于正态分布概率的f s v m 模型2 1 3 3 2 窍型隶属度函数2 2 3 。4 实验设计2 3 3 5 小结2 7 第二部分非负矩阵分解n m f ，2 8 1 绪论2 8 1 1 研究背景及意义o _ 2 8 1 2 国内外研究现状k 2 8 f_叠嚣 支持向量机和非负矩阵分解理论方法的应用 1 3n m f 研究趋势和有待解决的问题3 0 2 非负矩阵分解n m f ：3 1 2 1n m f 数学模型31 2 1 1 最原始的n m f 3 1 2 1 2n m f 的几种变体3 3 3n m f 和i s o m a p 相结合的图像检索新方法3 6 3 1 引言3 6 3 2 非线性降维方法i s o m a p 3 7 3 3n m f 和i s o m a p 相结合的新方法：3 8 3 4 实验设计3 9 3 5 小结4 1 结论4 2 参考文献4 3 攻读硕士学位期间发表的学术论文情况4 6 致谢4 7 辽宁师范大学硕士学位论文 机s v m 机器学习是根据从已知输入中得到的规律对未知输出做出预测的过程。统计学是目 前机器学习方法的重要理论基础之一，但是传统统计学研究的是当样本数量趋近于无穷 大时的渐近理论，而实际生活中的多数情况下样本的数量都是有限的，因此统计学虽然 在理论上是很出色的学习方法，在实际应用中却存在很大的局限性。针对这种情况， v v a p n i k l l 等人从6 0 年代开始致力于研究有限样本统计理论，并将其称为统计学习理论 ( 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 ) t 2 - 3 】。s l t 建立了一整套良好的有限样本下机器学习的理 论框架和通用方法，其主要思想和核心内容就是要求学习机器和有限的训练样本相适 应，这对解决原来许多难以克服的实际问题，比如高维数、小样本、局部极小值等具有 很大的帮助，引起国内外广大学者的极大兴趣，成为9 0 年代末发展最快、研究最广泛 的方向之一。 支持向量机( s v m ) t 4 - 6 是在统计学习理论基础上发展起来的一种新的通用学习算法， 根据有限的样本信息在模型的复杂性( u p 对特定训练样本的学习精度) 和学习能力 ( 即准确无误地识别任意样本的能力) 之间寻求最佳折衷，以期获得最好的推广能 力，s v m 的提出成为机器学习领域的一项重大成果。它利用结构风险最小化( s t r u c t u r a l 鼬s km i n i m i z a t i o n ，s r m ) 准则和核函数，将输入数据映射到高维空间，在高维空间里寻 找一个广义最优分类面，使得在低维线性空间不可分的两类分类问题转化成高维空间线 性可分问题，其求解过程可以看作是解决一个凸二次优化问题，能够保证找到的极值解 即为最优解。 支持向量机集优化、核、最佳推广能力等特点于一身，针对小样本情况，算法最终 得到的解是全局最优解，避免了局部极值问题，并巧妙的解决了维数灾难，其算法复杂 度与样本维数无关，非常适合于处理非线性问题，而且由于结构风险最小化原则的应用， 支持向量机具有非常好的推广能力。但是随着近些年研究的不断深入，s v m 存在的一 些不足也逐渐显露出来，比如算法的训练速度较慢，算法较复杂而且难以实现，对于核 函数等一些参数的选取上通常只是使用经验值，还缺乏相应的理论依据和证明，并且在 最后测试阶段的运算量也非常大，这些都是对s v m 提出的挑战，也是以后有待研究和 需要完善的地方。 支持向量机和非负矩阵分解理论方法的应用 1 2 国内外研究现状 目前国内外对支持向量机的研究不论是在理论模型还是实际应用方面都处于飞速 发展的阶段。 支持向量机是由v a p i n k 领导的a t & t b e l l 实验室研究小组在1 9 6 3 年提出的， 它的最初模型是建立在常见的标准化数据或者可以完全分开的数据的情况下，但在实际 应用过程中，这种“理想化”的数据是很少见的，我们常常遇到的会是一些数据分布规 律不合常规或难以准确分类的数据，这些数据被称作噪声数据( 野值) ，它们常常位于分 类面附近，导致获得的分类面不是真正的最优分类面。针对这种情况，l i n 等学者提出 了模糊支持向量机方法( f s 旧【_ 卜9 】，在支持向量机中引入了模糊技术，根据不同样本在 分类时的不同贡献，对他们赋予不同的权重系数，对于那些含有噪声( 野值) 的样本给予 较小的权值，这样来达到减小或者消除噪声点与野值样本对分类的影响的目的。近几年 提出的概率支持向量机( p s v m ) t l o 】和粗糙支持向量机( r s v m ) 1 1 】将样本的概率分布信息 和等价类信息加入到模型中，不同程度上优化了s v m 模型，提高了分类精度。 支持向量机最初来自对两类数据分类问题的研究，如何将其有效的推广到多类别分 类仍是当前支持向量机研究的重要内容之一，目前对于多类分类问题的解决途径主要 是一对多( o n e a g a i n s t - r e s t ) b 2 ) 和一对- - ( o n e - a g a i n s t o n e ) 两种方法。一对多的基本思想是 把多个类别中的某一种类别样本单独当作一个类别，其他剩余的样本作为另一个类别， 这样就可以把它看成是一个两类分类问题，在测试的过程中，分别计算测试样本的每个 两类分类器的决策函数值，对得到的函数值做一个排序，并选择其中最大值所对应的类 别作为测试数据的类别。而另一种一对一的做法是从多个类别中随机的取出两类，这样 就转化成一个两类分类问题进行测试和学习，也就会产生多个两类s v l v l 问题，测试时， 对所有两类分类器分别测试，并累计计算各类的得分，选择得分最高的类作为测试数据 的类别。一对一和一对多是主流的也是使用较为广泛的方法，但是也有其他的多类分类 方法，比如可以通过有向非循环图减少分类中计算的d a g s v m 1 3 ( d i r e c t e da c y c l i c g r a p hs v m ) 。还有一种是直接多类分类s v m ，它实际上是标准s v m 中二次优化问题 的一种自然推广，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优 化问题实现多类分类，这种方法使用较多的变量，并且在分类精度上也不占优势，所以 使用的较少。s v m 决策树( d e c i s i o nt r e em e t h o d ，d t m ) 通常和二叉决策树结合起来一 起构成多类别的识别器。 辽宁师范大学硕士学位论文 1 3 支持向量机的应用 理论方法只有在实际应用中才能显示出其优势并发挥真正的作用。s v m 方法在理 论上已被大家认可并表现出突出的优势，它率先由贝尔实验室应用在美国邮政手写数字 库识别研究方面并取得了较大的成功，随后，有关支持向量机的应用研究迅速的引起了 各个领域学者的极大关注，几年时间就已经被广泛并成功应用到模式识别、图像处理、 信息安全、信用评价等诸多方面。 ( 1 ) 模式识别 模式识别可以说是支持向量机一个最重要也是最成功的应用领域，无论是人脸检 测、人脸识别、指纹识别、语音识别还是文本分类等方面，s v m 都表现出了非常好的 性能和较高的准确率。最先将s v m 应用到人类检测的是o s u n a t l 4 】，首先将人脸与非人 脸进行分类，使用直接训练非线性s v m 分类器的方法完成，由于s v i v i 的训练过程需 ， 要大量的存储空间，并且非线性s v m 分类器需要较多的支持向量，所以速度很慢。s v m 在人脸识别 1 5 - 1 6 方面的成功应用，比较有代表性的是凌旭峰等将p c a 和s v m 相结合， 取得了较好的成果。文献【l7 利用s v m 对语音进行识别，而文本分类的成功例子体现在 文献【1 8 】中。 ( 2 ) 图像处理 支持向量机近年来在图像检索领域得到了充分和广泛的应用，但是由于计算机本身 是一台机器，并不能完全模拟和理解人的思维，在提取图像特征的过程中和人所要求的 语义间存在较大的差别，这样就导致图像检索得到的结果不尽人意。文献【1 9 】由张磊等人 提出了一种新的图像检索方法，即以s v m 为分类器，在检索过程中加入相关反馈技术， 将第一次检索得到的结果进行人工标记，再对样本的正例和反例进行学习，最后根据学 习所得的模型进行检索，实验表明进行反馈后的方法提高了检索的精度，并且具有较好 的泛化能力。在医学图像方面s v m 也具有成功的应用 2 0 1 。 ( 3 ) 信息安全 随着互联网的广泛应用，网络安全问题成为大家关注的重点，陈光英【2 i 】等设计并实 现了一种基于s v m 分类器的入侵检测系统，它收集并计算除服务器端之外的t c p i p 流 量特征，使用s v m 算法进行分类，从而服务器连接的类型就可以进行识别，最后要与 连接服务器端所表明的服务类型进行一个比较，通过结果就可以检测到异常的t c p i p 协议。 ( 4 ) 信用评价 文献瞄】是将s v m 模型应用在信用分析中，通过进行实证分析，根据不同企业数据 的不同特点，设计了一个较实用的增量训练方法，并取得了满意的效果。由于结合具体 支持向量机和非负矩阵分解理论方法的应用 实际需要，所以在最后结果的解释上更加谨慎，充分考虑了商业银行进行风险管理的实 际和需要，得出了很多符合商业银行风险管理实际的结论。文献2 3 1 将s v m 成功应用在 财务危机预警方面，通过搜集1 0 0 家破产企业与1 0 0 家未破产企业构成样本集，使实验 更具说服力，在构建s v m 模型方面采用多项式核函数，得到的结果显示s v m 方法对 比常规方法具有明显的优势。 一4 一 辽宁师范大学硕士学位论文 2 支持向量机模型 2 1 相关知识 2 1 1 统计学理论和v c 维 基于数据的机器学习，主要研究如何从一些观测数据出发得到目前尚不能通过原理 分析得到的规律，利用这些规律去分析客观，对未来数据进行预测洲。统计学习理论是 一种专注于研究小样本情况下数据的估计和预测理论，对解决小样本学习问题具有重要 的意义。它主要包括四个方面的内容：第一是研究在经验风险最小化的前提下如何使统 计学习获得一致性的条件，第二个最具有指导性的内容是在这些条件的基础上获得推广 性的界，第三点是在界的基础上建立一整套完整的小样本情况下的归纳推理准则，最后 一点就是寻求一个切实可行的算法实现新准则。这每一项内容都是紧密联系的。 v c 维( v a p n i k 2 一c h e r v o n e n kd i m e n s i o n ) 是统计学习理论中的核心概念，也是一个极 其重要的指标，它是和函数集的学习性能有关的，在模式识别方法中，v c 维的直观定 义是1 2 5 】：对一个指示函数集，如果存在h 个样本能够被函数集中的函数按所有可能的2 办 种形式分开，则称函数集能够把h 个样本打散。函数集中，v c 维就是它能打散的最大 样本数目h ，若对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大， 在有界实函数中，v c 维也可以用指示函数来进行定义，但是这种定义的转换需要通过 用一定的阈值。 。 v c 维是函数集的学习能力的一种体现，学习机器越复杂( 容量越大) 得到的v c 维 越大。但是对于任意一个函数集其v c 维的计算目前还没有充分的理论证明，现在知道 的只是一些比较常见和特殊函数集的v c 维。比如在，z 维实数空间中线性分类器和线性 实函数的v c 维是，z + l ，厂( x ，a ) = s i n ( a x ) 的v c 维趋于无穷大。这是一些比较简单的 函数，在函数集比较复杂的情况下，v c 维不仅与函数集有关，同时也受学习算法等其 他因素的影响，确定起来难度更大。对于给定的任意函数集，如何通过理论证明或一套 通用的计算方法得到其v c 维也是目前统计学习理论中亟需解决的一个问题。 2 1 2 结构风险最小化原则 经验风险最小化( e r m ) 原则是传统机器学习方法中采用的主导思想，多年以来人们 也是将大部分的注意力集中到如何才能更好的最小化经验风险上，然而很快就发现训练 误差小也不能一定就会得到好的结果，在某些情况下会适得其反，训练误差过小可是却 导致了推广能力的下降，也就增加了真实的风险，产生了所谓的“过学习 现象。 支持向量机和非负矩阵分解理论方法的应用 e r m 原则会产生过学习现象，主要是因为它在样本有限的情况下是不合理的，必 须同时最小化经验风险及置信范围。在以前基于数据的机器学习方法中，调整置信范围 的过程其实就是选择学习模型和算法的过程，假如学习模型和已有的训练样本恰好相互 适应，那么通过调整置信范围就会取得很好的效果，但是在实际应用中选择置信范围经 常是缺乏具体成熟的理论指导的，经常是依赖使用者的先验经验和技巧，这就导致了该 过程更多的加入了人的主观因素。针对这一问题和不足，统计学习理论引入结构风险最 小化【2 4 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 ) 准则的概念，所谓的结构风险最小化就是在 保证分类精度( 经验风险) 的同时，降低学习机器的v c 维，可以使学习机器在整个样本 集上的期望风险得到控制，而使结构风险达到最小的想法也就是选择置信范围和经验风 险之和最小的子集。如图2 1 所示。 s r m 原则是一种不同于经验风险最小化的机器学习原则，其关键内容就是找到合 适的子集函数结构，可以不用逐个计算就能够得到每个子集的最小经验风险。实现s r m 原则主要有两种思路：其一就是在每个子集中求最小经验风险，然后选择使最小经验风 险和置信范围之和最小的子集，但是当子集数目很大甚至无穷的时候，采用这种方法很 显然会浪费大量时间，实现起来具有一定的困难；另一种想法是设计函数集的结构，尽 可能最小化每一个子集的经验风险值，例如我们把训练误差设为零，这样在最小化子集 的置信范围的情况下就可以保证得到的最优函数也是经验风险最小的函数。s v m 很好 的诠释了结构风险最小化的思想。 风硷 函毂雏于集s i c 5 # 5 4 v c 雉l i t ， 图2 1 结构风险最小化模型 f i g 2 1 s 饥l c t l l r a lr i s km i n i m i z a t i o nm o d e l 2 1 3 核函数 冽 支持向量机的关键在于核函数。低维空间向量集通常难于划分，其中一种较 为常用的解决方法就是将它们映射到高维空间，但这个办法带来的一个直接问题 就是计算的复杂度会增加，而核函数恰好很巧妙地解决了这个问题，也就是说， 辽宁师范大学硕士学位论文 只要选用了适当的核函数，就可以得到在高维空间的一个分类函数。在支持向量 机理论中，使用者采用不同的核函数形式就会得到不同的支持向量机模型。本文实 验过程中采用不同的核函数进行测试，结果表明对数据做不同的处理，采用不同的核函 数得到的实验结果各不相同，但是如何根据样本的不同选取合适的核函数形式，目前还 没有统一的标准和充足的理论证明，所以在涉及具体的实际问题时，一般都是结合数据 的特点和以往的经验使用不同形式的核函数。 支持向量机中由于内积核函数不同也会形成不同的算法，下面是本文后面实验过程 中将会用到，也是比较常用的三种核函数形式： 一是径向基函数( r b f ) 核函数： ，k ( 碱) 暑e x p - 与乒 ( 2 1 ) l 。 j 由此所得到的分类器每个基函数中心与一个支持向量相对应，这是与传统r b f 方 法的一个重要区别，并且算法自动确定函数以及输出权值。 二是s i g m o i d 核函数： k ( x ，而) = t a n h ( v ( x x f ) + c )，( 2 2 ) 这时支持向量机实现的是包括一个隐层的多层感知器，其中隐层的节点数是自动的 由算法确定的，而且算法也不存局部极小点等神经网络方法十分困扰的问题。 三是多项式核函数： k ( x ，) = ( 工x f ) + 1 1 。( 2 3 ) 由此得到的是一个q 阶多项式分类器。 2 2 支持向量机模型推导 s v m 最初的想法可以用图2 2 直观的表示，它的基本思想是能够将一个两类的线性 可分问题进行准确的分类，也就是对图中的两类样本( 实心圆代表+ 1 类，空心圆代表一1 类) 能够找到两条互相平行的直线将他们分类，其中日为分类线，剧，h 2 分别为过各 类中离分类线最近的且平行于分类线的直线，它们之间的距离叫做分类间隔，由图2 2 可以看出将两类样本分开的分类线可以有无数条，但是我们要找的是最优分类线，也就 是要求分类线不但能将两类样本进行无误差的分类，而且能够最大化分类间隔，在高维 空间中，最优分类线就变成最优分类面，也叫做最优超平面。 支持向量机和非负矩阵分解理论方法的应用 图2 2s v m 模型 f i g 2 2 s v mm o d e l 、分类线骂、皿和h 可以分别表示为： h l ：，慨+ b = 1 h 2 ：w x + b = - 1 ( 2 4 ) 日：诫+ 石：o 其中w 和x 为d 维的向量，b 为单位长度，经过归一化处理以后，使得线性可分的 样本集( 而，y ，) ，i = 1 ，咒，x r ，y + 1 ，一1 ) ，满足： f w 。x + 6 = o y f ( w 石) + 6 一1 0( 2 5 ) is t ：f = 1 ，n 通过整理计算得到此时的分类间隔为2 0 叫j ，使分类间隔达到最大值，也就是等价 于使2 m l 最大，此时求解最优超平面问题就变成如下问题，为了方便计算，这里我们 求解州i 2 最小，也即 fm i n 1 w 丁w 2 ( 2 6 ) 【s t ：y ( w 。x ) + b 一1 0 利用l a g r a n g e 优化方法把上述最优分类面问题转化成对偶问题，即上述问题转化成 如下形式： 辽宁师范大学硕士学位论文 口f 0i = 1 ，n ( 2 7 ) 口，为每个样本对应的l a g r a n g e 乘子，这是一个不等式约束下的二次寻优问题，它 存在唯一的解，并且解中通常只有很少一部分口不为零，他们对应的样本就是我们所说 的支持向量，支持向量通常是那些在间隔区域边缘的训练样本点。解上述问题得到 的最优分类函数是： r 卫、 厂( x ) = s i g n ( w x + 6 ) = s i g n l a i y i ( x i 。工) + 6i口，0 。( 2 8 ) i = 1 式中的求和实际上只对支持向量进行，b 是分类阂值，只要是满足式子( 2 5 ) 的等号， 就可以通过求得支持向量以后来得到b 值。 对于线性不可分情况，s v m 无法将所有样本都正确分类，这时候上述提到的最优分 类面是无法得到的，而这种情况在现实生活中是十分常见的，为了解决这样的情况，我 们可以允许一部分样本点被错分，于是引入惩罚参数c 和松弛变量孝，。这时相应支持向 量机的模型也会有所改变，其最优问题可以表示为： in了1m 1 nw r w + c 孝f ww + 乙 二： 1厶一o 厶 i = l s t ：y ( w x ) + b 1 一毒f 孝f 0i = 1 ， c y 善， 其中篱是为了控制错误分类样本的数量。变量c 0 是s v m 中唯一的一个自由 参数，可以根据使用者的需求人为确定的一个常数，它能够控制对错分样本惩罚的程 度，是容许错分样本数目和分类间隔的宽度之间的一个折衷。c 越大，表示对错分的惩 罚程度就越大，那么分类间隔就越小，反之c 越小，则容许更多的样本被错分，得到的分 类间隔也就越大，即折衷来考虑最少错分样本和最大分类间隔。这样得到的分类面为广 义最优分类面，广义最优分类面的对偶问题与线性可分情况几乎一样，同样使用 l a g r a n g e 优化方法得至l j ( 2 9 1 式的对偶问题： x ， x口口 yy 芦 斟一2 o 一 = i 口 = 叵- 口。 m 盯 支持向量机和非负矩阵分解理论方法的应用 n l nn m a x 暑口，一言三三y ，y j g l i o l j ( h 哨j ) g ( 2 1 0 ) s t ：口f y f = 0 、 7 0 a f c i = 1 ， 此时的决策函数可以表示为： ，n 、 厂( z ) = s g n ( w x + 6 ) = s g n l a f 乃( t 力+ 6i o c( 2 11 ) i = 1 以上支持向量机方法主要是针对线性的情况，对于非线性问题，我们可以通过某种 变换把它转化为某个高维空间中的可分问题，然后在变换得到的高维空间求得最优分类 面。但是这种变换在实现过程中比较麻烦，所以这种方法通常不容易被实现和采用。不 过通过仔细观察以上式子可以发现，在( 2 1 1 ) 的对偶问题中，所涉及的无非都是训练样 本之间的内积运算( x ix ，) ，泛函的有关理论证明，对于满足m e r c e r 条件的某一种核函 数k ( x ，x ，) ，它与某一变换空间中的内积相互对应，此时我们无需考虑变换的具体形式， 只要找到一个原空间的变换函数就可以实现。如图2 3 。因此，在最优分类面中只要我 们选择了合适的核函数k ( x ，x ，) ，就可以完成将非线性不可分问题变换成线性可分问题， 这时( 2 11 ) 式就可以变为： ，n、 厂( x ) = s g n ( w x + 6 ) = s g n l a i y i k ( x i x ) + 61 0 - - ( a i c( 2 1 2 ) 核函数x 一由( x ) l t 二，一_ 卜。| 一。 暑 - 气 f 。 、- ； - - k 一l x 二7 图2 。3 核函数 f i 9 2 3 k e r n e lf u n c t i o n 一1 0 一 辽宁师范大学硕士学位论文 为了方便运算，将上述问题转化为二次规划问题，令 lh 盯= ( y f y ，k ( x i ，z ，) ) q - - - ( q l ，a n ) 1( 2 1 3 ) ly = ( y f ，y ) 。 则公式( 2 1 0 ) 变为： im l n 一1u t 日a e r o t , t 少r 仅：o 。仅c p 2 j 4 因为o r , f ( 乃( w 鼍+ 6 ) 一1 ) = o ，且仅f 0 所以也即是要求y i ( w 而+ 6 ) - 1 = 0 二次规划以后的决策函数表示为： 厂( x ) = s g n ( w z + 6 ) = s g n l a i y i ( x i x ) + 6 o _ c t c e ( 2 1 5 ) 我们知道，支持向量机中对偶问题的求解仅仅与支持向量所对应的样本点有关，在 最优化方法中也叫做有效约束。而我们所希望的就是可以通过某种方法提前确定哪些是 支持向量或有效约束，并且保留与支持向量相对应的有用样本点，删除训练集中的其他 样本点，减小计算量和节省时间。这一事实对大规模的实际问题非常重要，因为它往往 是稀疏的，只有很少的支持向量，这样就只需求解小规模的优化问题。对究竟哪些是支 持向量或有效约束一般采用启发式算法寻优，最简单的启发式方法是选块算法，它通过 不断的迭代来逐个排除支持向量，这样在样本数目十分大的时候就会随之产生各种各样 的问题，比如迭代次数会不断增多，块会越来越大，存储所需空间也会增大，计算的时 间复杂度和空间复杂度都会很大。 一种新的优化算法一序列最小最优化算法( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ，s m o ) 弥 补了选块算法的不足，它每次只更新- - d , 部分l a g r a n g e 乘子，其他的乘子保持不变，这 样每当有新的样本点加入就必然会有一个旧的样本点被淘汰，这每次“一进一出”的过 程都将工作集之外最违反约束条件的点与工作集中的一部分样本点进行交换，无论支持 向量的数目有多大也不会改变工作集的规模。它与块算法的最大不同就在于前者把主要 精力集中在约束条件上，每次的子集规模都达到了最小，而后者则是着眼于找到支持向 量来解决问题。 支持向量机和非负矩阵分解理论方法的应用 我们把口相应的分量组成的集合分为两部分，一部分为被选中的样本点，记它对应 的下标集为b ，另一部分是未被选中的样本点，也就是等待调整的样本点，其下标记作 n ，这时有： 口制y 吲h = ( 瓷a g j 6 这里，我们需要调整的是口口，口是固定不变的，由于日是对称的= 碥， 所以可将式子( 2 1 4 ) 改写为： lm i n w ( 口) = 三+ 三一沪( e h b n a n ) 础蜘+ 簖儿= o ( 2 1 7 ) + 【 0 畦q 、 、 ，由于是固定的，可知i 1 t 口- a r e 是常数，所以( 2 1 7 ) 等价于： i