（计算机软件与理论专业论文）基于加权度量支持向量机下的分类算法研究.pdf

基于加权度量支持向量机下的分类算法研究 论文题目：基于加权度量支持向量机下的分类算法研究 专业：计算机软件与理论 硕士生：梅芳 指导教师：印鉴教授 摘要 支持向量机( s v m ) 在分类算法原理中基于结构风险最小化的优越性使得 其应用领域越来越广泛。其顺次最小优化算法( s m o ) 比传统的块算法和固定 工作样本集的迭代优化算法具有更好的时间复杂性和空间复杂性。虽然s v m 是 专门针对有限样本发展起来且不依赖对所解问题先验知识的分类算法，但是在实 际应用领域中往往对样本的需求量仍然很大。目前已有研究证明在一些应用领域 中专家知识在理论上可以代替样本不足的问题。 本文提出了引入先验知识的支持向量机模型即加权度量支持向量机 w m - s v m ( w e i g h t e dm a r g i ns v m ) ，通过对训练样本引入先验信息量而减少所 需的样本数量，同时提出了相应的w m - s m o 算法，基于l i b s v m2 6 和c + + 语言编写实验程序并应用于中医证候分类。实验数据来自广东省中医药管理局资 助课题“中医证候信息数据库系统的设计与开发”中的中医证候数据库。首先通 过专家所提供的中医证候专家知识规则对训练样本集进行置信度的计算，然后使 用w m s m o 算法训练w m s v m 并测试。实验结果表明w m s m o 是种对s v m 在具体应用问题下更有效的算法，它能把应用背景中的先验知识与t f 练样本中的 信息量很好地结合起来，在中医证候分类有专家知识的情况下，分类的正确率比 原有s v m 有较大的提高。 关键词：分类，支持向量机，中医证候。先验知识，w m - s v m ，w m s m o 基于加权度量支持向量机下的分类算法研究 t i t l e ：t h er e s e a r c ho f c l a s s i f i c a t i o na l g o r i f l m ao nt h ew e i g h t e d - m a r g i ns v m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：m e if a n g s u p e r v i s o r ：y i n j i a np r o f e s s o r 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 e s ( s v m ) h a sb e e ns u c c e s s f u l l ya p p l i e d i n m a n y r e a l w o r l da p p l i c a t i o n s s e q u e n c em i n i m u mo p t i m i z a t i o n ( s m o ) a l g o r i t h mh a sl e s s c o m p l e x i t yo ft i m ea n ds p a c ec o m p a r e dw i t ht r a d i t i o n a lb l o c ka l g o r i t h ma n df i x a t i v e s a m p l ec o l l e c t i o na l g o r i t h m ，s v mi sf o c u s e do nt h el i m i t e ds a m p l ea n di n d e p e n d e n t o fp r i o rk n o w l e d g e ，h o w e v e r ，t h es a m p l en e e d e di nr e a la p p l i c a t i o nf i e l di ss t i l lv e r y l a r g e i ns o m ea p p l i c a t i o n s ，t h e r em i g h tb eh u m a nk n o w l e d g e , a v a i l a b l et h a t ，i n p r i n c i p l e ，c o u l dc o m p e n s a t ef o rt h el a c ko f d a t a t h i sp a p e rp r o p o s e sam e t h o dw m - s v mt h a tc a nr e d u c et h ed e m a n d i n g q u a n t i t y o fs a m p l e sb yi n t r o d u c i n gt h ei n f o r m a t i o no fp r i o rk n o w l e d g ei n t ot h es a m p l e s ， m e a n w h i l e # v e st h er e l a t e da l g o r i t h mn a m e dw m - s m o o u re x p e r i m e n td a t a s e t c o m e sf r o mt h es o f t w a r e d e v e l o p i n gp r o j e c t ：n f o r m a t i o nm a n a g e m e n ts y s t e mo f t c ms y n d r o m e ，f u n d e db yt h eg u a n g d o n gb u r e a uo ft r a d i t i o n a lc h i n e s em e d i c i n e ( t c m ) a d m i n i s t r a t i o n a f t e rf o r m i n gt h er u l e sf r o me x p e r tk n o w l e d g e ，w ea tf i r s t c a l c u l a t et h ec o n f i d e n c ev a l u e so fe a c hs a m p l e ，a n dt h e nu s et h es a m p l es e tt ot r a i n w m s v mb yu s i n gw m s m oa l g o r i t h m ，w h i c hi sap r i o r k n o w l e d g eb a s e d i m p r o v e dv e r s i o no u to ft h et r a d i t i o n a lo n e s nt h ea p p l i c a t i o no fc h i n e s em e d i c i n e s y n d r o m ec l a s s i f i c a t i o n ，w eu s el i b s v m2 6a n dc + + i np r o g r a m m i n gi m p l e m e n t p u t t i n gt h ew m - s v mi d e aa n dw t v l s m oa l g o r i t h mi n t ot h ee x p e r i m e n t ，t h er e s u l t s h o w sa g r e a ti m p r o v e m e n tc o m p a r e dw i t ht h eo r i g i n a ls v mi nc l a s s i f y i n ga c c u r a c y k e yw o r d ：c l a s s i f i c a t i o n ，s v m ，c h i n e s em e d i c i n es y n d r o m e ，p r i o rk n o w l e d g e ， w i v i - s v m w m s m o 基于加权度量支持向量帆下的分类算法研究 1 1 引言 第1 章绪论 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是一种学习机制。支持向量机的概 念是前苏联学者v a p n i k 等人在1 9 7 4 年提出的，但直到最近几年才受到重视，并成 为人工智能界的一个研究热点 1 】。该项研究属于机器学习、模式识别和人工神 经网络等多个学科，由于它与这些学科现有的理论和方法相比，有明显的优越性， 因此有重大的潜在应用价值。s v m 可广泛应用于文本识别、川脸检测、三维图 像识别、非线性回归建模、数据压缩、时间序列预测、生物信息学等各个方面， 但应用研究的报道较少。对s v m 核心算法一求解拉格朗日乘子的优化算法，若 采用经典的二次规划方法，一般无法解决实际问题，尤其是大规模样本问题，这 直接影响着s v m 的实际应用 2 。因此，近年来国际上对s v m 优化算法的研究非 常重视，以期加深和扩大s v m 应用领域。这其中，序贯最，j 、优化( s e q u e n t i a l m i n i m a lo p t i m i z a t i o n ，s m o ) 算法 3 】经过不断的改进，成为目前较为有效的s v m 训练方法。 同时，目前基于传统统计学的数据分析手段以被广泛应用于中医证候的研究 中，并取得了初步成果。例如郭蕾 4 等提出证候是中医学对人体整体功能状态 的认识和把握，具有复杂性特点，应使用研究复杂系统和复杂现象的手段进行研 究，以找出中医证候和病因、理化指标、方剂效应之间的非线性关系。同时，这 些非线性关系又是目前研究中遇到的主要障碍。王阶【5 认为，在中医学古籍中 已经有模糊定量的记载，所以数理统计，尤其是多元统计能充分运用到中医学证 候诊断的研究中；方法上提出使用半定量的方法，如加权法，以及多元统计分析 方法，如判别分析中的f i s h e r 判别、b a y e s 判别和逐步判别分析，回顾分析，最 大似然法，b a y e s 公式法等。刘稼 6 】提出运用聚类分析法对不同的证候进行判断 和区分，认为中医证候在分类、组成、变化中包含有多元模糊的数学思想，聚类 分析能较好地避免了数据处理时掺杂的主观因素，能客观、准确地反映目标证候 的情况。 所有这些研究都是基于传统统计学的经典参数体系的。在这种体系中，核心 基于加极度量支持向量机下的分类算法研究 思想是：为了从数据中找到一种函数依赖关系，必然能够定义一个与参数成线性 关系的函数集，它包含了对所求函数的最佳逼近，并且描述函数集的自由参数个 数较小，这个可以由w e i e r s t r a s s 定理进行说明；大多数实际问题的随机分量所隐 含的统计规律是正态分布，这个可以由巾心极限定理进行说明；在参数估计体系 下的归纳手段是最大似然方法，是估计参数的有效工具，这个可以由条件最优性 定理进行说明【7 【8 。以上的这三点，又都是基于这样的一个前提的，也就是假 如存在一个数学证明，说某一方法给出一个渐近最优解，则在实际问题中该方法 将对少量的数据样本提供一个合理的解 7 】 8 】。也就是说，就某一实际问题而言， 可能只能提供给学习机器一个极其有限的样本集，经典的参数体系认为必然能够 从中抽取出所给定那一类问题的一般规律，并对测试数据给出较优的解。 这样的信念对于样本数趋于无穷时，并且样本服从一定 ! l l 律分布的问题是很 有效的。但是随着计算机技术的发展，人们在应用计算机分析复杂模型( 包含很 多因子) 的过程中，发现了传统参数估计体系存在如下的缺点： 当考虑的因素和精度增加时，所需要的计算量会成指数增加。这就是由 r b e l l m a n 所提出的维数灾难 7 。经验表明，很多实际问题的统计成分并不仅用 经典的统计分布函数来描述，它们1 ；能或很难用有限个正态分布通过叠加得到， 也就是说这些情况下中心极限定理未必适用，比如说对于某些转导推理的问题， 我们无法找到合适的分布函数，在这种情况下经典的统计方法就不适用。最大似 然方法不一定是最好的，不一定是每个样本都会对分类函数有同样的贡献 7 】。 传统参数估计体系有很大的局限性，首先，它需要已知样本分布形式，这需 要花费很大代价，还有，传统统计学研究的是样本数目趋于无穷大时的渐近理沦， 现有学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此 一些理论上很优秀的学习方法，应用到小样本的实际中表现却可能不尽人意。 所以有关小样本学习理论的研究就显得很重要。在这种情况下人们展开了对 统计学习理论的研究。与针对大数据样本集发展起来的统训学和基于各种先验信 息的统计学相比，统计学习理论是专门针对小数据样本集发展起来的，并不依赖 于对所解问题的先验知识，而是只考虑学习机器所实现一种函数集的结构，并日 在结构上定义了一种子集容量的特定度量，也就是所谓的v c 维理论。 统计学习理论( 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 ) 是一利，专门研究小样本 情况下机器学习规律的理论。该理论针对小样本统计问题建立了套新的理论体 系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现 有有限信息条件下得到最优结果 8 。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习 问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多 基于加权度量支持向量机下的分类算法研究 原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ；同时， 在这一理论基础上发展了一种新的通用学习方法一支持向量机( s u p p o r tv e c t o r m a c h i n e 或s v m ) ，它在很多的应用方面已经表现出很好的性能，并且有很好的 理论基础，是一种很有发展前景的机器学习算法。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理 基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度， a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以 期获得最好的推广能力( g e n e r a l i z a t i o n a b i l i t y ) 。支持向量机方法的几个主要优点 有： 1 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅 仅是样本数趋于无穷大时的最优值； 2 算法最终将转化成为一个二次型寻优问题，从数学理论上说，得到的将是 全局最优点，解决了在神经网络方法中无法避免的局部极值问题： 3 算法将实际问题，也就是线性不可分的问题，通过非线性变换转换到高维 的特征空间( f e a t u r es p a c e ) ，在高维空间中构造线性判别函数来实现原空间中的 非线性判别函数，这种特殊性质能保证机器有较好的推广能力，同时它巧妙地解 决了维数问题，其算法复杂度与样本维数无关。 在支持向量机方法中，只要定义不同的内积函数，就可以实现多项式逼近、 贝叶斯分类器、径向基函数( r a d i a lb a s i cf u n c t i o n 或r b f ) 方法、多层感知器 网络等许多现有的学习算法。 s v m 是近年来兴起基于统计学习理论的分类和预测算法。它首先是由 v a p n i k 提出来的，在【7 】【8 中系统地阐述了有关统计学习理论和s v m 的理论。随 着人们对统计学习理论研究的深入，s v m 的研究方向主要集中在核函数的性质 研究、s v m 模型的变化、s v m 训练算法的改进、把应用背景知识引入到s v m 模型中以及把s v m 与各种应用相结合产生的各种解决方案上。 1 2 国内外研究现状 在支持向量机核函数方面的研究，主流工作多是选取些给定的核函数，讨 沦不同核函数在不同应用情况下的不同性质，研究用这些给定的核函数的分类能 力及其选取问题。吴涛在 9 中提出了采用插值方法进行核函数的构造，使用 s h e p a r d 方法构造核函数在特定点的值。其实质是遵循统计学习的原则，即当受 基于j j u 权度量支持向量机下的分类算法研究 限于有限数量的信息时，不要通过解决一个更一般的问题来解决所面临的特殊问 题。插值方法通过训练样本点直接确定某些我们感兴趣的点的函数值，也即机器 学习中的一种转导推理方法，它对于小样本学习特别有效。但是插值方法的运算 量较大 9 ，算法的时问复杂度会比较高。与此同时，s a m a r i 等在 1 0 中提出了 一种用核函数所导出的黎曼度量的性质刺核函数进行了局部的改进，也就是所谓 的动态核函数的方法，以弥补单一核函数对于分类器的推广能力贡献的不足。但 是 1 0 只是做了$ - t 对所给数据确定核函数形式的丌创性工作，还未形成真正意义 上的构造核的方法【9 。目前的核函数研究还没能深入到足以指导我们如何选取 核函数，更谈不上根据具体的数据构造一个核函数了。陈光英等在 1 1 中提出了 应用遗传算法对给定核函数组合的参数选择算法，针对特定的数据集选择特定核 函数的组合参数，以达到更好的推广能力。这种思想利用已有的核函数进行组合， 实现了针对应用的核函数部分选择，是广义的核函数选择与目前这种单一核函数 的一种折衷方案。在c h e n g 等的【1 2 中提出了使用非正定的核函数的想法，【乜就 是使用不满足m e r c e r 条件的核函数，在特征空间里求输入向量象的内积，以k r e i n 空间代替一直以来s v m 核函数所使用的h i l b e r t 空问。这种思想下可以选用的核 函数的种类会更多，也为针对不同的样本集选用最合适的核函数提供了基础。只 是这种己不是传统意义一卜- 的支持向量机了，但是从某种意义上说明了某些“传统” 的规则是可以打破的，这种打破带来的将是从一种新的高度去看待原问题。非正 定核函数思想的提出，提出了是否可以选择具有特定性质的内积空间作为特征空 间，而不是仅限于我们已知的h i l b e r t 空间的问题，或者说是否可以根据特定数 据集的特点来确定所选用特征窄问的性质。而l m 的 1 3 中，进一步讨论了非正 定核函数和s i g m o d 函数，并提出了基于非正定核的s v m 训练算法t y p e s m o 。 对于训练算法，s m o 及其改进算法在训练速度和效果方面都有较好的表现， 对于大样本数的情况也能处理。a l p h a s e e d i n g 1 5 这类针对于普通s m o 算法的启 发式的选取策略，使选择优化样本过程的效率进一步提高。同时，利用先验知识 在训练初期就可以去掉相当部分的非支持样本，使训练的效率有较大的提高。目 前支持向量机方法已经在各个领域中得到广泛的应用。其中在图像识别、语音识 别、文本分类等方面已经发挥了重要作用。支持向量机方法和核学习方法主要用 于解决小样本的学习问题，而且对数据维数和多变性不敏感，具有较好的分类精 度和泛化能力。1 类一s v m 方法已被成功用于孤立的手写体识别、文本分类、人 脸识别等，并显示出巨大的优越性。s v m 方法应用于入侵检测的研究【乜越来越 多，有e l e a z a re s k i n 等人用s v m 来实现主机异常状态的发现。李辉等人通过定 义归一化距离计算两个样本的内积，并在此基础上提出了l 类s v m 的训练算法 1 6 。 4 基于加权度量支持向量机下的分类算法研究 在先验知识与s v m 模型结合方面， 2 提出了s v m 基于加权度量距离的数 学模型及一种基于s m o 的训练算法的思想，通过先验知识计算分类标识的置信 度，以确定样本离分类面间隔的大小，开创性地提出了一种带权距离的思想。g f u n g 等在 1 4 仲提出了基于知识的s v m 模型，是先验知识引入s v m 的开创性 工作。s v m 已经逐渐有了许多成功的应用，但是将先验知识引入其算法的研究 还不多，s v m 算法提出的初衷是不考虑应用背景的知识，运用数据集所提供的 信息来完成训练过程以及推广。在小样本学习的大框架中，s v m 在理论上最大 限度地利用样本集所提供的知识，但是却没有考虑由于问题的背景所关联的先验 知识，我们相信，在先验知识的指导下，训练效率以及分类器的推广能力都将得 到不同程度的提升。 目前主要有两个热点研究的方向：一方面如 1 8 中提出了如何选择特定背景 知识下的核函数。不同的核函数对分类器的推广能力有很大的影响，某些特定应 用选用特定的核函数会有非常好的表现。另一方面的研究是直接把先验知识引入 s v m 分类器中，包括直接在训练样本中引入先验知识属性，然后统一通过s v m 表示；也有对优化的目标，即最大分类间隔重新定义，使之成为在某种意下的最 大间隔。目前有学者提出把先验知识引入s v m 分类模型中。 1 7 中证明了在合 适的核函数中引入先验知识的可行性。 1 4 】证明了以多维数据集为形式的先验知 识可重新构造与其相关的s v m 。对核函数的研究以及对于先验知识的表示形式 都还处于研究阶段，成功的应用还不是很多。 在中医证候的应用研究领域，统计理论和数据挖掘算法在中医证候的分析方 面近年来也进行了不少的研究工作，人们将中医证候专家知识引入s v m 模型方 面也做了很多工作，但是远没有达到较高的水平。胡镜清等 1 8 】提出，针对中医 证候信息多维与多阶、多态与多粒度和缺失、折叠与混杂的特征，建立“中医l 临 床个体化诊疗体系”，应用神经网络、决策树等数据挖掘方法，以研究证候信息 的特征与诊断规范化。陈明等【1 9 根据“诊断= 诊断要素1 十贡献率1 ( 或影响因 子1 ) + 诊断要素2 $ 贡献率2 ( 或影响因子2 ) + - ”的诊断思维模式，使用关 联规则中的a p r i o r i 算法，计算不同证候间的相关性，以找出各个证型之间的内 在联系。 我们从中医证候的先验知识出发，定义对于中医证候训练样本的置信度，也 就是样本在实际背景下可能属于某一类的可能性，进而提出带权度量的s v m 模 型w m - s v m ，然后应用w m s m o 算法对带置信度属性的数据集进行训练：通 过定义置信度标准化函数f 和松弛变量标准化函数g ，把表示先验知识的置信度 集成到由松弛变量控制的软间隔分类器中，通过把先验知识表示的规则应用到训 练样本集合，得出样本分类标记的置信度，由此重新确定支持向量离分类超平面 基于加权度量支持向量机下的分类算法研究 的距离。实质上是把传统s v m 的最大化分类间隔推广为最大化带权的分类间隔， 而这种权值是由应用背景的先验知识所决定。我们将改进得出加权度量s v m 模 型w m s v m ，并在实验中和传统s v m 进行分类准确率的比较，最后对结果做 出进一步讨论。 1 3 论文结构 本文的余下部分组织如下：第2 章阐述了传统s v m 在线性可分和非线性可 分情形下的数学模型及其分类算法s m o ；第3 章提出了引入了先验知识的加权 度量w m s v m 的数学模型以及相应的w m s m o 算法；第4 章阐述针对中医证 侯数据进行相关先验知识的表达并应用w m s m o 进行症候分类：有关本文的实 验环境和实验对比结果也在第4 章进行说明；第5 章是本文的结论。 基于加权度量支持向量帆下的分类算法研究 1 1 引言 第1 章绪论 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是一种学习机制。支持向量机的概 念是前苏联学者v a p n i k 等人在1 9 7 4 年提出的，但直到最近几年才受到重视，并成 为人工智能界的一个研究热点 1 】。该项研究属于机器学习、模式识别和人工神 经网络等多个学科，由于它与这些学科现有的理论和方法相比，有明显的优越性， 因此有重大的潜在应用价值。s v m 可广泛应用于文本识别、川脸检测、三维图 像识别、非线性回归建模、数据压缩、时间序列预测、生物信息学等各个方面， 但应用研究的报道较少。对s v m 核心算法一求解拉格朗日乘子的优化算法，若 采用经典的二次规划方法，一般无法解决实际问题，尤其是大规模样本问题，这 直接影响着s v m 的实际应用 2 。因此，近年来国际上对s v m 优化算法的研究非 常重视，以期加深和扩大s v m 应用领域。这其中，序贯最，j 、优化( s e q u e n t i a l m i n i m a lo p t i m i z a t i o n ，s m o ) 算法 3 】经过不断的改进，成为目前较为有效的s v m 训练方法。 同时，目前基于传统统计学的数据分析手段以被广泛应用于中医证候的研究 中，并取得了初步成果。例如郭蕾 4 等提出证候是中医学对人体整体功能状态 的认识和把握，具有复杂性特点，应使用研究复杂系统和复杂现象的手段进行研 究，以找出中医证候和病因、理化指标、方剂效应之间的非线性关系。同时，这 些非线性关系又是目前研究中遇到的主要障碍。王阶【5 认为，在中医学古籍中 已经有模糊定量的记载，所以数理统计，尤其是多元统计能充分运用到中医学证 候诊断的研究中；方法上提出使用半定量的方法，如加权法，以及多元统计分析 方法，如判别分析中的f i s h e r 判别、b a y e s 判别和逐步判别分析，回顾分析，最 大似然法，b a y e s 公式法等。刘稼 6 】提出运用聚类分析法对不同的证候进行判断 和区分，认为中医证候在分类、组成、变化中包含有多元模糊的数学思想，聚类 分析能较好地避免了数据处理时掺杂的主观因素，能客观、准确地反映目标证候 的情况。 所有这些研究都是基于传统统计学的经典参数体系的。在这种体系中，核心 基于加权度量支持向量机下的分类算法研究 原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ；同时， 在这一理论基础上发展了一种新的通用学习方法一支持向量机( s u p p o r tv e c t o r m a c h i n e 或s v m ) ，它在很多的应用方面已经表现出很好的性能，并且有很好的 理论基础，是一种很有发展前景的机器学习算法。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理 基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度， a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以 期获得最好的推广能力( g e n e r a l i z a t i o n a b i l i t y ) 。支持向量机方法的几个主要优点 有： 1 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅 仅是样本数趋于无穷大时的最优值； 2 算法最终将转化成为一个二次型寻优问题，从数学理论上说，得到的将是 全局最优点，解决了在神经网络方法中无法避免的局部极值问题： 3 算法将实际问题，也就是线性不可分的问题，通过非线性变换转换到高维 的特征空间( f e a t u r es p a c e ) ，在高维空间中构造线性判别函数来实现原空间中的 非线性判别函数，这种特殊性质能保证机器有较好的推广能力，同时它巧妙地解 决了维数问题，其算法复杂度与样本维数无关。 在支持向量机方法中，只要定义不同的内积函数，就可以实现多项式逼近、 贝叶斯分类器、径向基函数( r a d i a lb a s i cf u n c t i o n 或r b f ) 方法、多层感知器 网络等许多现有的学习算法。 s v m 是近年来兴起基于统计学习理论的分类和预测算法。它首先是由 v a p n i k 提出来的，在【7 】【8 中系统地阐述了有关统计学习理论和s v m 的理论。随 着人们对统计学习理论研究的深入，s v m 的研究方向主要集中在核函数的性质 研究、s v m 模型的变化、s v m 训练算法的改进、把应用背景知识引入到s v m 模型中以及把s v m 与各种应用相结合产生的各种解决方案上。 1 2 国内外研究现状 在支持向量机核函数方面的研究，主流工作多是选取些给定的核函数，讨 沦不同核函数在不同应用情况下的不同性质，研究用这些给定的核函数的分类能 力及其选取问题。吴涛在 9 中提出了采用插值方法进行核函数的构造，使用 s h e p a r d 方法构造核函数在特定点的值。其实质是遵循统计学习的原则，即当受 基于加权度量支持向量机下的分类算法研究 的距离。实质上是把传统s v m 的最大化分类间隔推广为最大化带权的分类间隔， 而这种权值是由应用背景的先验知识所决定。我们将改进得出加权度量s v m 模 型w m s v m ，并在实验中和传统s v m 进行分类准确率的比较，最后对结果做 出进一步讨论。 1 3 论文结构 本文的余下部分组织如下：第2 章阐述了传统s v m 在线性可分和非线性可 分情形下的数学模型及其分类算法s m o ；第3 章提出了引入了先验知识的加权 度量w m s v m 的数学模型以及相应的w m s m o 算法；第4 章阐述针对中医证 侯数据进行相关先验知识的表达并应用w m s m o 进行症候分类：有关本文的实 验环境和实验对比结果也在第4 章进行说明；第5 章是本文的结论。 基于加权度量支持向量机下的分类算法研究 第2 章支持向量机的模型与算法 支持向量机方法是在统计学习理论基础上发展起来的种分类方法，有较系 统得数学理论基础。本章简单介绍s v m 的数学模型与传统s m o 算法，这是 w m - s m o 训练算法的基础。 2 1 基本概念和定理 2 1 1 最优分类超平面 我们称来自训练样本集( y l ，x 1 ) ( y h ，x h ) ，x r i i ，y 一l ，1 ) 的向量x 的 两个有限子集( 其中，子集i 对应y = 1 ，子集对应y = 1 ) ，对于超平面 ( x + 一c 是可分的，若存在一个单位向量中( 川= 1 ) 和一个常数c ，使得不等式 ( x + 平) c ，若x i i( 2 - 1 ) ( x + 平) 0 的 展开式 k ( u ，v ) = a k z k ( u ) z k ( v ) k 2 i ( 2 3 ) ( 也就是说k ( u ，v ) 描述了某一特征空间中的内积) 的充要条件是： 9 基于加权度量支持向量帆下的分类算法研究 川k ( u , v ) g ( u ) g ( v ) d u d v _ 0 对于所有g l z ( c ) 成立( c 为r n 的一个紧子集) 。 可用于构造支持向量机的h i l b e r t 空间中内积结构的好的性质是：对于满足 m e r c e r 条件的任何核函数k ( u ，v ) ，存在一个特征空间( z l ( u ) ，z k ( u ) ，) ，在该 空间中核函数生成满足要求的内积。 这样，我们只要找到一个满足m e r c e r 定理充要条件的核函数，就一定可以 得到一个支持向量机，它对于给定的样本集在特征空间中是线性可分的。 由于判断一个函数是否满足m e r c e r 定理的充要条件不容易，目前的研究多 是集中于对以下儿类已被证明是满足m e r c e r 定理并目在实际应用中显示出良好 性能的核函数：多项式、径向基函数r b f 和两层神经网络。而且在具体的应用 问题下，不同的核函数对于分类器推广能力有不同的影响。 2 1 4 支持向量机 支持向量机要解决最优分类超平面的参数确定问题。求解最优分类超平而的 问题，实质是一个二次优化问题： l ：w t w + c - e t m 呱w ，b ， ) i2 1 满足： y i l “、j 纠一岛岛 0 i = l j 其几何意义是求在约束条件下的分类间隔的最大值，为了求值的方便，我们 对目标函数取倒数，也就是求最小值的表达式。 考虑到当输入空间的维数可能会很高，最优分类超平面的法向量w 的维数 也会变得很高，这导致了直接求解原二次优化问题时需要大量内存来存放w ，使 算法的扩展性受到很大的限制。所以一般的处理方法是通过求解原问题的w b l f e 对偶问题来解决 7 。对偶问题的表示形式如下： i ， 1 w ( 。) = ( n i ) 一j + 哪y iy j + x j m a x i = 1 u = 1 其中a i _ o ，i = 1 1 在高维特征空间中牛成内积允许我们构造一些函数k ( x j ，x 2 ) ，它们在输入空 0 = y a 。e 足满 基于加权度量支持向量机下的分类算法研究 间中是非线性的，也就是有以下形式的非线性判别函数： 电a ) = s i g n f y i c t i 小) + b 1 l 支持向量 ( 2 - 4 ) 而它们在特征空问z 1 ( x ) ，2 k ( x ) ，中等价于线性决策函数： r 0 0 、 屯a ) ：s t g n i y i 吣如) 御礼i l 支持向量 r = 1 ( 2 - 5 ) 构造这一类决策函数的学习机器称为支持向量机。支持向量机的示意图如图 2 2 所示： 0 x x d 图2 - 2 支持向量机示意图 k ( x i ，x j ) s v m 把在输入空间中的非线性分类问题转化为特征空间的线性分类问题， 而这种转换最终是通过核函数计算特征空间中向量与支持向量之间的内积实现 的。 s v i v i 处理非线性可分问题的核心思想是：对于输入空间中非线性可分的情 形，选择一个适当的非线性映射，将输入空间中的样本点映射到一个高维的特征 空间，使得对应的样本点在该特征空间中是线性可分的，也就是说在该特征空间 中可以找到一个最优分类超平面把两类数据分开。 2 1 5k k t 条件 k k t 条件是k a r u s h k u h n t u c k e r 条件的简称，它是对最优分类超平面仅由 支持向量决定，与其它向量无关这个事实的一种数学描述。实际上k k t 条件是 目前s v m 训练算法迭代的判断条件。k k t 条件的数学描述如下： 【y i ( ( w x i ) + b ) 一1 弋i 】- 0 ， i 。1 ，n ，( 吼一c ) = 0 ， i _ 1 ，n 幂于加权艘量支持向量机下的分类算法研究 k k t 条件说明了这样一个事实：在最终的分类器函数中，每一个训练样本 都对应着一个系数，但是只有支持向量样本所对应的系数才有非零值即对h 的 确定产生负献系数，而其它的系数都是零。于是我们可以在训练算法中根据目前 的分类器函数是否满足这样的条件而决定需要怎样使用样本对系数进行优化。 2 2 问题模型 2 2 1 线形可分 对于线形可分的二类分类问题，s v m 分类器也不失一般性，目标就是产生 一个分类器，能够对未观察到的例子分类，即常况的具有良好的泛化能力。如图 2 - 3 ，二类样本用图中的几条分类线都可以分隔样本，但哪条是分类效果最好的 呢? 答案是h ，这就是s v m 分类器模型的基本理论核心，因为h 使得被分开的 两类样本集中离它最近的样本点之间的距离间隔最大。虚线也能分隔样本，但其 分隔问距就要比h 小得多。由此基本模型引出与s v m 相关的名词定义：支持向 量s v 、最大间距、最优分类超平面。支持向量机所探索的核心就是如何将这个 超平面w x + b 训练出来。现在的方法都是基于较强的数学理论背景( 拉格朗 日乘子的方法) 而归结成二次规划问题。 2 2 2 非线形可分 图2 3 寻找最大分类间隔的分类面 对于非线性可分的情况，引入松弛因子放松约束的规范或者用惩罚函数来扩 充推广最优超平面的概念。现在很多研究者提出更一般的理论：点积空间的核函 数理论。这个理论领域研究是目前s v m 相关研究的核心热点之一，可深入研究 的空间很大。因为利用点积空间可以引入非线性映射将输入空间映射到高维空 l 瑚，使得s v m 能产生高维空间下的最优超平面，解决非线性可分的情况。 基于加权度量支持向量机下的分类算法研究 另外，关于不可分的情形，同一般的处理方法一样，引入软边缘分类间隔的 概念，通过在数学模型中引入惩罚项来放松约束条件，后面实验中c s v c 需要 用到的一个参数c 即引入惩罚项后的惩罚系数。 2 3 数学模型 上节描述了最初解决问题的模型，下面给出s v m 的数学模型 2 3 1 线形可分 假定训练数据( x 1 ，y 1 ) ，( x 。，y n ) ，x r 。，y + l ，1 ，可被一个超平面 w x + b = 0 分开，s v m 理论按照直观的推测：与两类样本距离( m a r g i n ) 虽大的 的超平面有最佳的推广能力。换言之，此超平面最稳妥地描述了两种样本的界限。 我们的任务即如何找到这个最优超平面? 那自然就去寻找它的决定因素：决定这 个超平面的样本点很特殊，是离它最近的少数样本点决定的，与大多其他样本无 关，即上图所描述的s v 。再看图2 - 4 分析： 图2 - 4 线性可分s 的数学模型 超平面：( w x ) + b = o 1 1 w l l = l 设样本与超平面间隔为，那么描述为 若( w x ) + b a ，贝0y = l ， 若( w x ) + b ，贝9y = 一l 。 基于加权度量支持向量机下的分类算法研究 将此超平面归一化：令= l ，按比例缩放w 和b ，那么离超平面最近的样本可 描述为： 若y = l ，贝u ( w x ) + b = l ， 若y = 一l ，则( w x ) 巾b = - l 。 那么s v 到超平面的距离为i l l w l | 。 则最初的数学提法如下： m m ，b ) = 扣 满足：y i ( x w + b ) 一i 0 ，i = l i 这是数学中的一个严格的二次规划问题，根据最优化理论中此类问题的解决 方法，转化为w o l f e 对偶问题： m a x w ( 咖骞a ，一；左a j y i y j ( x ，1 ) 满足：圭蚶：o 旺qi ：l ，1 其数学推导在此不详述，但在推导过程中值得注意的是：d 是拉格朗日乘子， 每个x i 对应一个，并且推导必须满足数学中的k u h m t u c h e r 条件，求解山的o l 是整体最优的旺，那分类的决策函数也随之确定：f ( x ) = s i g n w + x + b 。 2 3 2 非线形可分 前面已经提到过非线性可分的思想：映射到高维特征空问，构造线性的最优 超平面。但随之带来两个问题：一是概念上，在如此高维的空间如何找到一个推 广性好的分类超平面。二是技术上，如何处理高维空间中的计算问题。w o l f e 对 偶问题一个很重要的副产品解决了维维数灾难和技术上的计算问题：如果数学上 可以找到一个函数k ：( k ，r n ) 一 r ，使得k ( x ，x j ) 等于x i 和x j 在高维特征窄间中 的映射的点积，那么用k ( x ，x j ) 可以代替线性可分情况下的点积，计算量会大大 减少，丁是不必知道这个非线性映射的形式，也不必在高维特征空间中进行计算， 这个k ( x ，x j ) 就是核函数。但由此也引发了新的问题，比如怎么样选择核函数怎 样根据需求构造核等，实验证明不i 司种类的核函数性能相似，找到的支持向量大 致相同。常用的有：多项式、径向基函数r b f 和两层神经网络。相应的决策函 数就转换为：f ( x ) = s i g n y i c qk ( x i ，x ) + b 。可见，支持向量数量很多时在决策阶 基于加权度量支持向量机下的分类算法研究 段的计算量也不小。i 司时，对于不可分情形，只需要通过引入惩罚凼子实现软边 缘间隔，数学模型中优化问题的约束条件只多了一个上限c ，因此最终的数学模 型描述如下： m i nw ( ) = 妻1 h q 一队1 1 0 【 满足：o 【。y ，= 00 a 如 i = 1 ，1 其中h 是半正定对称矩阵：h = y ：y ，k ( x i , x j ) l 。 而且x = i x l ，x2 ，x l l y = d i a g ( y l ，y 2 ，y 1 ) 最终分类超平面的决策函数表示为：f ( x ，c o = y ，0 【k ( x ，x ) + b 2 4s m o 算法 2 4 1s v m 问题的一般算法 数学模型建立以后，现在可以对“支持向量机”这一名词中i “机”和“支持 向量”分别作一点说明，这里的“机”实际上是一个算法。在机器学习领域，常 把一些算法看做一个机器。我们这里采用了机器学习领域中的术语，称分类算法 为分类机。至于“支持向量”，则是指训练集中的某些训练点的输入x i 。事实上， 最优化问题的解口的每一个分量都与一个训练点相对应，显然上节所描述的 数学模型通过算法所构造的分类超平面( 决策函数) ，仅仅依赖于那些相应与 不为零的训练点( x i ，y i ) ，这些训练点的输入x i 即为支持向量。显然，只有支持向 量对最终求得的分类超平面的法方向w 而与非支持向量无关。在这个意义上， 我们真正理解“支持向量分类机”的含义。 因此，一般的s v m 的二类分类算法如下： 1 设已知训练集( x l ，y 1 ) ，( x 。，y n ) ，x 心，y e + 1 ，一1 2 选择核函数k ( x i ，x j ) 和惩罚参数c ，构造并求解二次优化问题如2 3 2 所描 述，并得到最优解值= b ，：) t ； 基于办i 权度量支持向量机下的分类算法究 3 选择+ 一小于c 的正分量c 【：，并据此计算b + = y ， 4 - 求得决策函数f ( x