（模式识别与智能系统专业论文）支持向量数据描述在野点检测方面的应用.pdf

五邑大学硕士学位论文 摘要 野点检测实质e 就是个单值分类问题，野点能提供比正常数据点更多、更重要的信息。 野点检测技术已成功的应用到机械故障诊断、手写数字识别、网络异常入侵检测、说话人识别 等方面。 支持向量数据描述，是种在统计学习理论和支持向量机基础上发展起来的单值分类方法。 其基本思想是通过在特征空间中找出个包围目标样本点的超球体，并通过最小化该超球体所 包围的体积来让目标样本点尽可能的被包围在超球体中，而非目标样本点尽可能的不被包含在 超球体中，从而实现两类之间的划分。本文对支持向量数据描述方法领域进行了详细研究，同 时将其应用到机械故障诊断中。 本文内容包括：基本学习理论、核函数和支持向量机及其性质；支持向量数据描述算法原 理；对s v d d 算法中- g - ) 习核函数的性能进行研究，验证了高斯核函数具有一定的实用性；探讨 了高斯核参数对s v d d 分类器的影响，实验表明：支持向量数据描述算法适合于小规模样本的 单值分类问题；根据s v d d 分类边界线上的支持向量之间距离的相似度来对训练集进行约减， 提出了种新型的支持向量数据约减算法s v d d s r 算法，此算法在小规模数据中具有一 定的有效| 生；采用了小波包分解方法进行特征提取，用s v d d 方法进行分类的故障诊断方法， 得到较好的分类性能。 关键词野点检测，核函数，支持向量数据描述，支持向量数据约减算法，距离相似度 五邑大学硕士学位论文 a b s t r a c t t h e 圈止愿切i l c eo fn o v e l t yd l 舰c t i o ni sap r o b l e mo fo n e - c l a s sc l a s s i f i c a t i o n , n o v e l t yd a t ap a n p r o v i d em o r ei n f o n m t i o na n dm o 佗i m p o r t a n ti n f o n m t i o nt h a nt h en o r m a ld a t a t h et e c h n i q u eo f n o v e l t yd e t e c t i o ni su s e f u li na p p 跏o ms u c h 舔f a u l td i a g n o s e , h a n dw r i t t e nd i g i tr e c o g n i t i o n , n e t w o r ka b n o n m li n t r u s i o nd e t e c t i o n , s p e a k e rr e c o g n i t i o na n ds e v e r a lo t h e r s s u p p o r tv e c t o rd a t ad e s c r i p t i o n ( s v d d ) i sao n e - c l a s sc l a s s i f i c a t i o nm e t h o dt h a td e v e l o p e df r o m t h es t a t i s t i cl e a r n i n gt h e o r ya n ds u p p o r tv e c t o rm a c h i n e t h eb a s i ci d e ao fs v d dm e t h o di st of i l x la s u p e r - s p h e r ei nf e a t u r es p a c ea n dl i m i tt h ev o l u m eo ft h es p h e r et ob et h es m a l l e s t , i nt h es a m et i m e i n c l u d ea sp o s s i b l ea sm o r et a r g e td a t aa n de x c l u d ea sp o s s i b l ea sm o l en o n - t a r g e ts a m p l ed a t a , t h u st h e d a t ac a nb ec l a s s i f i e d t h ep a p e rr e s e a r c h e db r i e f l yo ns v d da n dt h em e t h o dw a sa p p l i e dt of a u l t d i a g n o s i s t h ep a p e r sc o n t e n t si n c l u d e ：b a s i gl e a m i n gt h e o r y , k e r n e lt e c h n o l o g y , s u p p o r tv e c t o r m a c h i n e ( s v m ) a n ds v m sc h a r a c t e r i s t i c s ；t h et h e o r yo fs v d d ；t h ep e r f o r m a n c eo fc o m m o nk e m e l f u n c t i o n so ns v d dw a sr e s e a r c h e d , t h eg a u s s - k e m e lt h a tp o s s e s s e dc e r t a i np r a c t i c a b i l i t yw a sv e r i f i e 】d ； t h ei n f l u e n c eo ns v d dp r o b e db yg a t t s s - k e m e l - p a r a m e t e r , a n de x p e r i m e n t ss h o w e d ：s v d dm e t h o d w a s a d a p t i v e t oo n e - c l a s sc l a s s i f i c a t i o no f s m a l l - s c a l es a m p l e ；a c c o r d i n gt od 缸i t 愀s i m i l a r i t yt or e d u c e t h el r a i n i n gs a m p l e sb e t l w e e l ls u p p o r tv e c t o r sl o c a t i n go nt h ec l a s s i f i c a t i o nb o u n d a r y , t h en e w - s t y l e m e t h o do fs v d d - s i m i l a r i t yr e d u c t i o nw a sp r o p o s e d , a n dt h em e t h o di nt e r m so f s m a l l s c a l ed a t ah a d s o m ee f f e c t i v e n e s s ；f a u l td i a g n o s i se m p l o y e ds v d dt oc l a s s i f ya n du s e dt h ew a v e l e tp a c k e t d e c o m p o s i n gt e c h n o l o g yt of e a t u r ee x t r o 而o n , f i n a l l y , g o o dc l a s s i f i c a t i o ne f f e c tw a so b t a i n e di n e x p e r i m e n t s k e yw o r d sn o v e l t yd e t e c t i o n , k e m e lf u n c t i o n , s u p p o r tv e c t o rd a t ad e s c r i p t i o n , s u p p o r tv e c t o rd a t a d e s c r i p t i o n s i m i l a r i t yr e d u c t i o n , d i s 撇s i m i l a r i t y 本人声明 我声明，本论文及其研究工作由本人在导师指导下独立完成，完成论文所用的切资料均 已在参考文献中列出。 作者：阜艳 签字：琴括 2 0 0 8 年4 月2 0 日 五邑大学硕士学位论文 1 1 研究的背景和意义 第一章绪论 野点，又称异常值、劣值( o u t l i e r 或n o v e l t y ) 的定义为：鼍素洽d 中严重偏离大部分数据所 呈现趋势的小部分数据点。这一定义强调主体数据所呈现的j 刍旁妒以偏离数据集合主体的变 化趋势为判别异常数据的依据，并明确指出野点在集合d 中只占小部分( 即最多不超过一半) ， 这从直观匕是合理的【l 】o 野点的存在，常常使得传统的建模、估计及检验方法陷入困境，难以良好地拟合动态数据， 也难以准确地进行预测和控制。对于些测量数据集合，要准确识别出所含有的全部野点是一 件十分不容易的事。特别是随着工程对象复杂化和高速计算柳迅速普及，人们碰到的数据集合 越来越大、数据维数越来越高，检测采样数据质量和诊断野点的工作变得愈来愈困难。因此， 建立高效、可靠的野点检测与诊断方法是个值得关注的重要课题。 在一些应用领域中，如机械设备运行状态监测、数据库中的知识发现等，野点能提供比正 常数据点更多、更重要的信息。野点检测是新知识、新类别发现的一条有效途径，并已成功应 用于电子商务、伪造信用卡检测、机械设备运行监测与故障诊断等领域。 1 2 目前国内外研究现状 在国内外的研究文献中，可把野点检测大致归结为以下几种方法： 门限判别准则、b a y e s 方法、密度估计方法、重构方法、最优线l 生滤波算法、a r m a 模 型、最小二乘法、m 估计、极大熵谱估计以及边界估计法等方法。 大量关于总体符合各种分布条件下的野点检验和剔除的方法中，对于独立同分布的样本， 剔除野点可分为拉依达准则、肖维勒( c h a u v 锄吣准则、格拉布斯( g r u b b s ) 、准贝l j 、f 检验准则、狄 克逊( 】d i x o n ) 准则掣1 1 。根据样本测量次数的多少来选择合适的门限判别准则，而门限值常根据 经验来选择的，从而会造成野点判别的失效，发生误判或漏判。 b a y e s 方法需要大量的正例，且计算量比饺大，所以这种方法更适用于对少量野点进行判 别的情况。 密度估计方法是种值得考虑的方法。它的基本思想是直接根据所给的训练样本对它们所 代表的类进行密度估计。根据所选的密度估计方法的不同，此类方法又包括：p a 嘞密度估计 法、高斯方法、混合高斯方法等。其实这些方法的区别只是在于对密度函数所选用的参数估计 五邑大学硕士学位论文 模型不同而已。 重构方法也是野点检测中种比较常用的方法。该方法的基本思想是尽可能利用些先验 知识，并结合特征提取的手段，实珊训练样本的重构。所谓重构，就是在一定的规则下将训练 样本进行重新表示。它们未必与原来输入的训练样本相同，但是如果属于同类样本，重构后 的样本表示与原来的样本表示之间的差别应该不是很大。所以在给出距离度量后，我们就可以 f j m 重构前后样本间的距离进行野点判别。许多传统的特征提取和变换方法都可以在这里得到 应用。先验知识的准确与否对i 比类方法的效果至关重要，如果能够有效利用先验知识，这类方 法会有非常好的效果。但是如果只是靠各种聚类算法实现先验知识的获取，则训练样本的分布 就必须充分目有代表性。否则会导致结果离真实值差别很远。 野点对高精度数据处理工作有着十分不利的影响。大量的研究结果也表明【1 司：无论是最 小二乘法、m 估计、a r m a 模型参数最优估计、最优线性滤波算法( 包括多项式滤波、递推k a l m a n 滤波以及k a l m a n 滤波新息正交等) ，还是频谱分析中著名的极大熵谱估计，对采样数据中包含 的野点反应都极为敏感。 边界估计法主要是要估计某类样本与野点之间的边界，从而避免直接估计样本的分布。该 方法相对于其它方法的优点在于所需的训练样本相对较少，对训练样本进行采样时不需要很密， 而且完全可以不去考虑真实的分布如何，只需要尽可能把各个有代表性的地方都采样到即可。 此类方法包括k - 中心方法，最近邻方法( n e a r e s tn e i g h b o r ，n n ) 以及支持向量数据描述算法 ( s u p p o r tv e c t o rd a t ad e s c r i p t i o n ，s v d d ) 2 6 。 野点检测的应用领域p n 】是广泛的，例如，在故障诊断和网络领域中对异常状态的检测、 异常状态原因的识别以及包括异常状态预测等；在经济领域中发现异常将具有重大的商业价值， 如客户流失、银行的信用卡欺诈、电信中移动话费拖欠以及医学中特殊病情的征兆等；在网络 安全领域中发现并报告系统中未授权或异常现象，防ie 入侵等。本文主要讨论的是基于支持向 量数据描述算法基础及其改进e 解决单值分类问题，和s v d d 算法在野点检测方面的应用。 1 3 支持向量数据描述理论及其国内外发展概况 1 3 1 支持向量数据描述理论 v a p n i k 等人提出的统计学习理论( s 脚m c a li 翩一n gn 舶彤s e t ) 是种针对小样本情况研究 统计学习规律的理论，该理论的核心思想是通过引入结构风险最小化准则来控制学习机器的容 量，从而刻画了过度拟合与泛化能力之间的关系。 2 五邑大学硕士学位论文 支持向量柳| ( s u p p o nv 咖rm 砌1 i n e s ，s v m ) 是v a p n i k 掣2 5 j 人根据统计学习理论提出的种 新的学习方法。s v m 方法是建立在统计学习理论的v c 维理论和结构风险最小原理基础匕的， 根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期望获得最好的推广能 力。支持向量杌理论的最大特点是根据v a p n i k 结构风险最小化原则，尽量提高学习机的泛化能 力，即由有限的训练集样本得到的小的误差能够保证对独立的测试集仍保持小的误差。标准的 s v m 算法是有监督的学习算法，主要解决二值分类问题，在手写数字识别、人脸识别、文本分 类等问题上取得了很好的应用效果。 支持向量数据描述算法s v d d 是由d a v i dm j t a x 等人于近几年研究发展起来的种单值 分类方法，其理论基础源于vv a p n i k 提出的统计学习理论及在其基础匕发展起来的s v m 算法。 其基本思想是把要描述的对象作为个整体，在特征空间中建立个超球体，使被描述的对象 全部或尽可能多的包容在该超球体内，而非该类对象没有或尽可能少的包含在该超球体内。超 球体内的点被认为属于目标类，而超球体外的点则被认为不属于该类，从而达到将两类分开的 目的。 支持向量数据描述是一种有效的单值分类数据描述算法。单值分类与传统的二值分类不同， 二值分类是把某给定的样本x 分类为类别i 或类别1 1 ，而单值分类的目标是要将x 分类为属于 该类或不属于该类。在单值分类问题中只有个类别，这样在构成单值分类器时也只需要个 给定类别样本的信息，把这种类别的样本称为目标样本，而不需要目标以外的其他样本非 目标样本。由于以上特点，s v d d 特别适合于类样本数据很容易得到而另类样本数据由于 经济或其他方面的原因很难得到的场合。 基于s v d d 野点检测方法的优点在于：( 1 ) s v d d 算法不使用类别标志，是一种无监督学习 方法，因而免去了为训练数据标志数据类别的工作；( 2 ) 无论对于仅由正常数据组成的纯净训练 集或者包含噪声的训练集，均可以通过学习得到支持向量描述模型并获得满意的检测率，这很 大程度e 降低了对训练数据集的要求，并使得模型实时更新成为可能；( 3 ) 该方法通用性强。 1 3 2 支持向量数据描述主要研究内容 当前，支持向量数据描述方法的研究主要分为理论研究和应用研究两个方面： 由于支持向量数据描述理论提出的时间不长，其本身还有许多有待完善的地方。比如对于 个具体的应用，如何有效地对原始数据集合进行预处理，以使其满足支持向量数据描述算法 的要求并提高其处理效果? 如何计算映射函数的v c 维? 如何选择确定核函数? 对于大型数据 集选择何种算法来减少其计算量等，都是亟待解决的问题，因此，对支持向量数据描述的理论 五邑大学硕士学位论文 研究直是个热点。现有的理论研究大都集中在关于核函数、算法和算法性能等的研究方面。 应用研究主要是将s v d d 方法应用到实际中，以解决具体的工程问题，使其产生经济效益。 目前，主要集中在说话人语音识别n 7 】、人脸识别、计算机网络入侵检测【l l 】、手写体文字识别嘲、 语句提取、质量过程监测以及故障诊断 3 8 - 3 9 , 4 4 等方面。在机械故障诊断方面的应用研究还不是 太多，主要是用s v d d 方法进行机器运行状态监测以及特征提取等。 1 3 3 机械故障诊断 机械故障监测或诊断过程本质e 是个故障模式分类过程嗍。目前，故障模式分类问题往 往根据几类故障产生的样本集进行训练，用训练得到的分类器判别测试样本所属类别。但是现 实故障诊断问题异常复杂，方面由于机械运转状态的复杂性，产生故障的原因和由此表现出 来的故障类别很多，全面采集各种类别故障数据几乎不可能。另一方面，由于机械正常运转状 态的数据容易采集，而故障状态下的数据般难以得到，或者得到所花费的代价比较昂贵。两 方面问题给传统故障诊断方法带来难题，往往因为缺乏足够的故障样本而导致诊断失败。事实 上，在许多机械故障监测或诊断问题中，我们只需要判断机器设备的工作状态是否正常，如果 诊断出故障则作进步分析处理。前期诊断工作可以看作是个单值分类问题。根据诊断任务 的需要，针对机械故障诊断缺乏故障样本的问题，提出了故障诊断单值分类法_ 支持向量数 据描述算法p 洲】。我们仅仅依赖机械正常运装状态的样本就能够分辨出正常和故障状态，不需 要额外地收集故障样本，从而大大降低了诊断的成本。因此，该方法在故障诊断撇有重要 推；广价值和广托的应用前景。 1 4 论文的主要内容和结构 第章绪论。主要介绍了课题的研究背景和意义，以及野点检测目前国内外的研究现状， 并描述了s v d d 算法理论及其国内外发展概况。 第二章支持向量数据描述算法的基础知识介绍。本章首先介绍了在论文中会出现的些 专业术语和定理，其次讲述了核函数和s v m 的些性质，为后面的s v d d 算法的研究作铺垫， 最后介绍了种对于模式识别问题中数据的降维方法_ f i s l 讶判别方法。 第三章介绍了种有效的单值分类数据描述算法s ) d 算法，此算法适合于小规模 样本的单值分类问题。研究了常用核函数在s v d d 算法中的分类性能，实验表明高斯核s v d d 在分类性能上具有一定的实用性和优越性。并探讨了高斯核参数与s v d d 模型区域边界、超球 体半径、支持向量数目、漏判和误判以及测试样本的正确识别率之间的关系。 4 五邑大学硕士学位论文 第四章提出了种根据位于s v d d 分类边界上的支持向量之间的距离相似度来对训练样 本进行约减得到种新型的支持向量数据约减算法s ) n s r 算法，并将这种约减算法和 传统s v d d 算法进行了比较实验，结果表明s v d d - s r 算法在小规模数据中具有一定的优越性 和实用性。 第五章对应用s v d d 算法处理机械故障诊断问题进行了研究，并将小波包分解技术应用 到基于s v d d 算法的故障诊断方法中。提出种用小波包分解方法进行特征提取，用s v d d 方法进行分类的故障诊断方法。通过对滚动轴承的实验，验证了该方法的有效性。 第六章总结与展望。总结了论文的主要工作，并对下步待开展的工作作了展望。 5 五邑大学硕士学位论文 2 1 核函数 第二章基本理论 核函数黼k e r n e l 仃i c k s ) 因其在支持向量机中的成功应用，促进了采用该技术改进传统线 性数据处理算法的研究，由此产生了多种基于核函数的方法，并在模式识别、自动控制、信号 处理等新兴的生物信息学等领域的应用研究中取得了丰硕的成果，核函数方法已成为人工神经 网络方法之后机器学习领域十分流行和有效的方法。 2 1 1 核函数方法原理 根据模式识别理论，低维空间线性不可分的模式通过非线性映射到高维特征空间则可能实 现线性可分。但是如果直接采用这种技术在高维空间进行分类或回归，则存在确定非线性映射 函数的形式和参数、特征空间维数等问题，而最大的障碍则是在高维特征空间运算时存在的“维 数灾难 。采用核函数技术可以有效地解决这样的问题。 设x ，g x ，x r ”，非线性函数矽实现输入空间x 到特征空间f 的映射，其中f = r ”， 拧m 。根据核函数技术有 k ( x ，z ) = ( 矽( x ) ，矽( z ) ) ( 2 1 ) 其中： 为内积，k ( x ，z ) 为核函数。从式( 1 ) 可以看出，核函数将m 维高维空间的内积 运算转化为n 维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维 数灾难等问题，从而为在高维特征空间解决复杂的分类或回归问题奠定了理论基础。 通常把采用核函数技术的类方法称为核函数力l 、法。概括起床，核函数方法的主要特点如 下： 1 )函数的计算量与特征空间的维数无关。核函数的引入避免了直接在变换后的高维特征空间 的运算，大大减小了计算量，避免了“维数灾难 。因此，甚至可以选择些核函数，使得 特征空间的维数为无穷大，以提高模式分类或回归能力。 2 ) 无需知道非线性变换函数的形式及其参数。不同的核函数确定了不同的非线性变换函 数。核函数的形式和参数的变化会改变特征空间的性质，进而改变各种核函数方法的性能。 3 ) 核函数方法可以和不同的算法结合起来，形成多种不同的基于核函数技术的方法。而且这 两部分的设计可以单独进行，并可以为不同的应用而选择不同的核函数和算法。 6 五邑大学硕士学位论文 2 1 2m e r c e 定理 m e r c e r 定理陶令x 是r ”的紧子集。假定k 是连续沸际函数，存在积分算子 瓦：厶( x ) 专厶( x ) ，值得 互= ( 瓦厂) ( ) = lk ( ，x ) f ( x ) e x ( 2 2 ) 为正，即： l 。z k ( x ，z ) 厂( x 沙( z ) 施沈o 可厶( x ) ( 2 3 ) 对所有的厂厶( x ) 成立。然后扩展k ( x ，z ) 到个致收敛的序列( 在x x 上) ，这个 序列由瓦的特征函数力厶( x ) 构成，归化使得0 唬忆= 1 ，并且乃o ，则有： k ( x ，z ) = 乃咖( 彳) 办( z ) ( 2 4 ) = l 其中条件式( 2 3 ) 对应于有限输入空间情况下的半正定条件。m e r c e r 定理的条件等价于对x 的任意有限子集其相应的矩阵是半正定的，这就是核函数的第二个特征，这个特征在构造核时 最有用。核般是指满足这个性质的函数，文献中通常称为m e r c e r 核。式( 2 3 ) 进步说明，输 入空间的核函数实际上与特征空间的内积相等价。由于核方法只需要应用特征空间的内积，而 不需要了解映射矽的具体形式。换句话说，在使用核方法时只需要考虑如何选定个适当的核 函数，而无需关心与之对应的映射矽可能具有复杂的表达式和很高的维数。 2 1 3 常用核函数 核函数的确定比较容易，满足条件的任意对称函数都可作核函数。 目前，核函数类型基本匕还是凭经验选定。选定核函数后，再进行相关参数的确定。在实 际使用中被广泛使用的仍然是下面四种核函数： 线性核函数( 可视为特例) k ( x ，y ) = x y ( 2 5 ) p 阶多项式核函数 ， ： k ( x ，y ) = 一y ) + 1 户 ( 2 6 ) 7 五邑大学硕士学位论文 高斯径向基函数f ) 核函数 咖) ：唧f - 譬 多层感知器( m 【，p ) 核函数 r ( x ，y ) = t a i l l l v ( x y ) + c ( 2 8 其中又尤其以i m f 核函数使用得最广。无论是在低维、高维、小样本、大样本等情况，r b f 核函数均适用，具有较宽的收敛域，是较为理想的分类依据函数。 在s 和s 、方法中，选择适当的核函数是个重要的因素。除了这里介绍的几种常见的核 函数外，还可以根据具体问题构造相应的核函数。 2 1 4 核函数的构造 一般地，模式识别问题选择核函数只是在常用函数集中比较其分类i 生能，从中找出某个 最佳的核函数，它只是在所给函数集中的最佳，未必是对所要解决的问题最有效的核函数。所 以核函数研究的最终目标是针对具体的问题确定最佳的核函数。下面介绍构造核函数的几条基 本途径。 2 1 4 1 基于特征变换的核函数构造陶 核函数是作为种非线性映射的隐式表达方法而提出的。这种隐式表达方法给我们分析映 ， 射的性质带来了不少的困难。但是反过来，在知道非线性映射的j 隋况下，构造与之对应的核函 数，则是个非常容易的事隋。正如核函数所要表达的含义：k ( x ，y ) = 矿( x ) 矽( y ) 。因此任 何种特征提取时所构造的非线性变换( ) ，都可以通过匕式来实现相应的核函数的构造。 用这种方法构造核函数，存在的最大问题是：核函数性能的好坏，直接取决于特征变换的 好坏。但是对很多实际问题，找到合适的特征变换往往很难。 2 1 4 2 利用m e r c e r 核函数的性质组合核函数陶 利用m e r c e r 核函数的性质构造核函数，就是利用核函数集合在某些运算下封闭的性质， 组合现有的些核函数而构造出新的核函数。 如果毛( x ，y ) ，乞( x ，j ，) 是满足m e i 船条件的核函数，则下面这些核函数也是m e r c 嬲核函 数： 毛( 石，y ) = 口毛( x ，y ) + b k 2 ( x ，y ) ， 对v 口，b 吼+ 8 五邑大学硕士学位论文 屯( x ，y ) = 毗( x ，y ) 。 岛( x , y ) = 毛( x ，y ) 也( x , y ) 屯( x ，y ) - - 毛( x ) ，矽( y ) ) ，即先进行初步的特征变换，再用核函数作用，最后得到的整 个变换仍是个核函数； 毛( x , y ) = p o z y , , o m i 口z ( k , ( x ，y ) ) 屯( x ，j ，) = e x p ( 毛( x ，y ) ) 2 1 4 3 基于插值的核函数构造方法【4 3 】 此方法是借助散乱插值的方法实现从训练样本之间的内积值到测试样本和训练样本之间 的内积值的外推。在这过程中，需要确定两件事情：一是训练样本之间的内积值的确定，这 一步对应着插值时的初值；二是确定插值( 拟合) 的方法。这种方法不仅有效减少了支持向量方 法训练中的不确定性，而且泛化能力要优于绝大部分的基于传统核函数的支持向量方法。 2 1 4 4 基于混合的核函数构造方法【镐1 支持向量方法的许多特性是由所选择的核函数来决定的，为了得到性能更为优良的支持向 量方法，种改进的方法是把多个核函数组合起来，形成种混合核函数，由这种混合核函数 构造的支持向量方法不仅学习能力强，而且具有很好的推广性。核函数主要分为两种类型，即： 局部性核函数和全局性核函数。r b f 函数就是个典型的局部性核函数，此函数仅仅在测试点 附近小领域类对数据点有影响。而多项式核函数是个典型的全局性核函数，此函数允许远离 测试输入的数据点对核函数的值也有影响。因为局韶陛核函数学习能力强、泛化眭能较弱，而 全局性核函数泛化性能强、学习能力较弱，因此考虑把这两类核函数混合起来。 2 2k k t 条件 k k t 最优化条件是k a r u s h 1 9 3 9 以及k u h n 和m l d 【耐1 9 5 1 】先后独立提出来的。这组最优 化条件在k u h n 和t u c k e r 发表之后才逐渐受到重视，因此，许多书只记载成k u h n - t u c k e r 最优 化貅 k u h n - t u c k e rc o n t i d i o n s ) ，所以，k u h n - t u c k e r 条件也称为k a m s h - k u h n - t u c k e r 条件或 k - k t 舭。 一般情况下，k t 条件是判别约束最优点的必要条件，而不是充分条件。当优化问题属凸 规划问题，即目标函数为凸函数，。可行域为凸函数的优化问题k t 条件才是约束最优解的充要 条件，且这种情况下的局部最优解也必为问题的全局最有解。 a 五邑大学硕士学位论文 下面k k t 定理给出了般的最优化问题有最优解的条件。 k k t 定理 给定定义在凸域q 尺”上的个最优化问题： m i l l s ( w ) ， w q j j & ( w ) o ， f = 1 ，七( 2 9 ) 1 1 , ( w ) = 0 ，f = l ，m 其中，f e c l 是凸的，并且蜀，红是仿射函数。一般地，个点w + 是最优点地充要条件是 存在口。，+ 满足： 兰匕竺：型：o 0 1 4 , 兰匕竺：塑：o a p q 1 u ) 蜀( w ) = o ，f = 1 ，七 g j ( w ) 0 ，i = 1 ，j 0 ，i = 1 ，k 式( 2 1 0 ) 中第三个等式称为k k t 互补条件。它意味着对于积极约束有q 芝0 ，但是对于非 积极约束有= 0 。而扰动非积极约束对于最优化问题地解没有影响。 k k t 条件表明，要么约束是积极的，意味着蜀( w ) = o ，要么相应的乘子酊= o ，即只 有积极约束有非零对偶变量，这也意味着些最优化问题实际变量数目要比全部训练集的规模 小的很多。在后面内容中将采用支持向量这个术语代表那些对偶变量非零的训练样本。 2 3 支持向量机 2 3 1 支持向量机原理 支持向量机是从线性可分隋况下的最优分类超平面发展而来的，学习的目的是寻找个最 优超平面，将两类样本正确分开删l 练错误率为0 ) ，同时使两类样本点到它的最小距离之和间隔 最大( 分类鲁棒性最好) 。 求解最优分类面是个典型的数学规划问题。 设训练模式集是两类分类问题 薯，乃 ，f = l ，刀，薯r ，只 一l ，1 是类别号，这拧俐i i 练 样本如果是线性可分的，则必然存在某个超平面可以将两类样本完全分开。 如图2 1 所示，最优超平面目将两类样本点完全分开，类别为+ 1 的样本点在其上方，类别 l o 五邑大学硕士学位论文 为一1 的样本点在其下方。并且有两个平面q 和攻与日平行，使得与h 最近的类别为+ 1 的样 本点( 而，+ 1 ) ，( _ ，+ 1 ) 和( 恐，+ 1 ) 分布在骂上，与日最近的类别为一1 的样本点( 氏，- 1 ) ，( 而，- 1 ) 和( 黾，- i ) 分布在马上，且4 , 到日的距离与到日的距离相同，均为d 。 从数学e 看，分类平面h 的方程为 日： ( w ，x ) + 6 = o 当两类样本是线性可分时，满足条件 ：骂的外侧：( 嵋薯) + 6 1对于乃= + 1 必的夕( w ，而) + 6 一1 对于乃= - 1 即 舡( w ，一) + 6 1 待l ， 由空间解析几何理论，可得d 2 俪i l w l li 综匕所述，在类别为+ 1 和1 的样本点之间产生最大分类间隔，这对应于如下最优化问题： 。 t n i n ( w ) = m 。i n 1 2 l 2 m 咖i n l 2 ( 、w w ) ( 2 1 1 ) 豇 虹( 鸭) + 6 1 ， 净1 ，刀 利用l a g r a n g c 优化方法可以把匕述最优分类面问题转化为其对偶问题，即： m a x 矽( 口) = q 一 q 哆咒乃( 薯_ ) ( 2 1 2 ) 五邑大学硕士学位论文 旺 y i = 0 ，q o ， i = 1 , - - - , 刀 其中，为每个样本对应的l a g r a n g c 乘子系数，这是个不等式约束下的二次函数极值问 题( q 唿d 瑚血p 内舻哪n i z l g ，q p ) ，存在唯解。解中只有部分q 不为零，对应的样本五就是 支持向量 ( s u p l x r tv e c t o r s ，s v s ) 。解上述问题求得s v m 的判决函数为： ( x ) = s g n - l s v + 咒( x 薯) + 6 。 ( 2 1 3 ) j 其中，b 为分类阈值。 对于线性不可分的情况，可在条件中引入采用松弛变量毒，从而得到广义的最优分类面， 优化问题可化为： m i n 劲w | | 2 + c 窆与 ( 2 1 4 ) s j y , e l - 专t ，毒o ，i = 1 , - - - , 刀 ( 2 1 5 ) 其中，式( 2 1 4 ) 中第一项使样本到超平面的距离尽量大，从而提高泛化能力；第二项则使分 类误差尽量小，c 在这里称为惩罚参数，控制对错分样本的惩罚程度。线性不可分最优分类面 的对偶问题和线性可分隋况下几乎完全相同，只是条件变为：0 磁c ，i = 1 ，刀。 当遇到线性不可分( 非线性) 的分类问题时，s 以可通过个事先选择好的非线性映射把输 入数据映射到个高维的线性可分的特征空间，在特征空间利用结构风险最小化原则构造最优 分类超平面，并不需要以显式形式来表示特征空间，仅仅需要计算特征空间中的向量之间的内 积。由于输入空间的核函数实际上是特征空间内积的等价。因此，在实际计算中不必关心非线 性映射( x ) 的具体形式，只需要选定核函数k ( x ，) 就行a m e r c e r 定理告诉我们，任意连续 对称函数都可作为核函数。 用非线性映射矽( x ) 代替原来的x ，线性不可分s v m 的原优化问题可化为： i l l i n 劲w | | 2 + c 兰参( 2 1 0 s f 乃 ( w ，( ) ) + 6 1 一专，专o ，i = 1 ，刀 ( 2 1 7 ) 用拉格朗日法求解匕述优化问题，就得到优化问题的对偶形式： l x l a x i iq i 1 7 jq 吩乃乃k ( ，_ ) ( 2 1 8 ) 1 2 五邑大学硕士学位论文 s j y j = 0 ，o q c ， f = 1 ，胛 i - i 最优化求解得到的中，0 q c 所对应的样本毛为s v s 。其中，0 o ； 如果= c ，则样本点被视为局外点。事实上