（计算机软件与理论专业论文）核函数的参数选择.pdf

山东师范大学硕士学位论文 核函数的参数选择 摘要 2 0 世纪8 0 年代，模式分析领域经历了一场“非线性革命 ：为摆脱计算和统计上的 线性局限的算法，支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 被第一次作为核方法提了出 来。随后，基于核的方法扩展到除分类以外更宽广的模式分析领域。这样，新技术都被严 格的理论分析所推动，在计算效率的保证下制造出来或发展起来。 基于核的分析对于数学家、科学家和工程师来说，是一个强大的新工具。它提供了非 常丰富的方法，可以应用在模式分析、信号处理、句法模式识别和其它模式识别领域。随 着基于核的学习理论在应用上的巨大成功，它日渐成为当今机器学习研究的热点和主流之 一。 核参数选择是基于核的分类算法的一种新型技术，对于基于核的分类器起着至关重要 的作用。近年来许多人开始认真审视这项技术，并且新的思想和技术还在不断涌现。如何 找到核参数的最优点日渐成为一项热门研究课题，并相继出现了多种核参数选择方式，其 中使用目标函数选择核参数的方式越来越受到人们的重视。 通过归纳核聚类算法，本文主要研究核函数的参数选择方法及其应用问题。在此基础 上，本文又着重研究使用目标函数为k n n 以及基于核的k d e m i o d s 选择参数的算法，并 通过实验验证和分析了目标函数的使用对核参数选择效率的影响，从而为核函数参数选择 更广泛的推广应用提供了有利的基础。 本文的主要创新点如下： 1 总结核的基本理论及划分聚类的主要算法。 本文系统和全面的总结了以前零散的核的基本理论和几种常用的核函数，并对如何构 造新的核函数进行了阐述，为核函数的构造提供了坚实的理论基础。同时，文章对主要的 划分聚类算法的进行了总结，如k 均值法、基于核的f i s h e r 判别分析、基于核的感知机等。 2 提出目标函数为k n n 选择核参数的两种方式。 传统的选择最优核参数的算法具有很高的时间复杂度和空间复杂度，并且扩展能力很 有限。本文针对基于核的最小距离分类器的特点，结合新空间中数据点的分布情况，设计 了选择最优核参数的目标函数算法，为基于核的最小距离分类器提供了有效支持，显著提 高了其分类的正确率。其中目标函数的使用可以减少运算次数、简化运算过程，从而显著 提高核参数选择算法的效率。 3 提出目标函数为基于核的k d 锄i o d s 选择核参数的方式。 基于核的k d e m i o d s 方法是一种k n n 的改进的算法。现有的基于核的分类算法主要 在通过核映射来提高分类正确率，但是分类正确率与参数的选择有直接联系。我们通过描 述数据点在新的特征空间的期望，通过目标函数来选择参数，从而改善了该算法的性能， 基于人工数据集和u c i 数据集表明了该算法的有效性。 山东师范大学硕士学位论文 4 总结了核参数选择的多种方式，并通过实验验证比较了各种选择方式的效率。 文章对于各种文献中提出的核参数选择算法进行了总结，比如试凑法、留一法等等。 这种总结对于完善和发展核参数的选择方法具有重要的指导意义。在此基础上，文章对相 关实验进行了验证和对相关的实验部分进行了详细分析。 关键词：支持向量机；k 均值法；丘s h e r 判别分析；感知机； 分类号：t p l 8 1 山东师范大学硕士学位论文 t h es e i e c t i o nf b rt h ek e r n e l b a s e dm e t h o d a b s t r a c t h 1t h e19 8 0 s ，m ep a t t e m 孤a l y s i sd o m a i nh a se x p 耐e n c e d ”t h en o n l i n e a rr e v 0 1 u t i o n ”： s u p p o r tv e c t o rm a c 址n e ( s 田i s 丘r s tp r o p o s e da st h ek e m e l - b a s e dm e t h o d st og e tr i do ft h e 1 i n e a rc o n s 打a i n t s s u b s e q u e n t l y ，m ek e m e l - b a s e dm e t h o d sa r ee x p a l l d e dt oo t h e rp a t t e m a n a l y s i s 丘e l d se x c 印tt h ec l a s s i f i c a t i o n 丘e l d h lt l l i sw a y ，a l lt 1 1 en e wt e c l l l l o l o 百e sd r i v e nb y s t r i c tm e o r e t i c a la n a l y s i sa r ed e v e l o p e dm l d e rt h eg u a r a n t e eo fe m c i e i l c yc a l c u l a t i o n t h ek e m e l b a s e da 1 1 a l y s i si sap o w e r 血ln e wt 0 0 1f o rt h em a t h e m a t i c i a l l s ，s c i e n t i s t s 觚d e n 百n e e r s i tp r o v i d e sr i c hm e m o d sf o rp a t t e ma i l a l y s i s ，s i 印a lp r o c e s s i n g ，s y l l t a c t i cp a t t e m r e c o 印i t i o na i l do t h e rp a n e mr e c o 印i t i o nf i e l d s a c c o m p a i l 如n gw i t ht h ea p p l i c a t i o no fk 锄e l m e t h o d ss u c c e s s ，t h er e s e a r c h0 nk e m e l - b a s e dl e a 玎血l ga 】g o 打t h n l sa 1 1 dt 王1 e i ra p p l i c a t i o n si so n e o ft 1 1 eh o tp r o b l e m s 狮dm 抽s t r e a m si nm a c l l i n e1 e a n l i n gw o r k s a san e w t e c l l i l o l o g y ，t h ec h o i c eo fk e m e lp a r a m e t e r sp l a y sa ni i n p o n a n tr 0 1 eo nm ek e m e l c l a s s i 丘c a t i o n m a n yp e o p l eh a v eb e 鲫lt op a ym o r ea t t e n t i o nt ot h i st e c l l l l 0 1 0 9 y h o wt of i n d t h eb e s tp a r 锄e t e rb e c o m e sah o tr e s e a r c ht o p i c ，a n dav a r i e t yo fk e n l e ls e l e c t i o na l g o r i t l l m ， w l l i c hc o u l ds i 印i f i c a n t l yi 1 1 c r e 嬲et 1 1 ee 笳c i e i l c yo fak e m e l - b a s e d1 e a n l i n g a l g o d t h l n ，i s a t t r a c t i n gm o r ea t t e n t i o n b a s e do nt h es 眦埘撕z 撕o no fk 锄e lc l u s t 鲥n ga l g o r i t h m s ，t h i sp a p e r 南c u s e so ns t u d y i n g t l l ek e m e lp a r a m e t e rs e l e c t i o nm e t h o da 1 1 di t s 印p l i c a t i o np r o b l e m s w eu s et l l eo b je c t i v e c t i o nt os e l e c t o p t i m a lk e m e lp a r a m e t e r sf o rt h ek n na 1 1 d k e m e l b a u s e dk d e m i o d s c l a s s i f i c a t i o n ，a n dt e s t i f yt h ee 伍c i e n c yo ft h es e l e c t e dp a r 锄e t e r st 1 1 工d u g has e to fe x p e r i m e n t s t h ep 印e ra l s op r 0 v i d e sm ea d v a n t a g e o u sa s p e c t sf o rc h o o s i n gt h eo p t i m a lp a r 撇e t e ro ft h e k e m e lf h n c t i o ni nw i d e s p r e a da p p l i c a t i o nf i e l d s t h em a i nc o n t 曲u t i o n so f 廿l i sp a p e ra r e1 i s t e da s ： 1 r e v i e wt h eb a s i ct h e o 巧o fk e m e ld i v i s i o na n dt h em a i na l g o 矗t h m s 矗) rc l u s t 谢n g t 1 1 i s p a p e rs y s t e m a t i c a l l y趾dc o m p r e h e n s i v e l yr e v i e w sm ep r c v i o u s l y丘a g m e m e d k e m e l b a s e dt h e o r y ，s e v e r a lk i n d so fk e m e lf u n c t i o n ，a sw e l la sc o n s t n l c t i o no fn e wk e m e l c t i o n s t h em a i nc l u s t 嘶n ga l g o r i t h m sa r ea sf o l l o w s ：k - m e a i l sa l g o r i t h m ，t 1 1 ek 锄e l _ b a s e d 丘s h e rd i s c r i m i i l a n ta i l a l y s i s ，t h ek 唧e l - b a s e dp e r c 印t r o n 2 p r o p o s eo b j e c t i v e 劬c t i o n sf o r q n s e l e c t i o np a r 锄e t e r so f t 、v o 印p r o a c h e s t h et r a m t i o n a la l g o r i t l l m so fc h o o s i l l go p t i m a lk e m e lp a m e t e r sa r eh i 曲t i m e c o n s u m i n g a i l de x p e n d a b l es p a c e c o n s 啪i 1 1 9 ，a 1 1 dc 印a c i t yo fe x p a i l s i o ni sl i m i t e d h l 锄sp a p e r ，i n1 i g h to f f l e a t u r e so ft h em i n j m u md i s t a i l c e 缸t h ek e m e lc l a s s i f i c a t i o na n dd i s t r i b u t i o no fd a t ai nm en e w s p a c e ，w ed e s i g no b je c t i v em n c t i o na l g o r i t h mt oc h o o s eo p t i m a lp a r a m e t e rf o rt h ek e m e l - b a s e d n e a r e s tn e i g h b o ra l g o r i t h m t h ep a u r a m e t e ri m p r o v e sm ec o r r e c tc l a s s i f i c a t i o nr a t es i g m f i c a n t l y 1 1 1 eo b je c t i v e 劬c t i o ni su s e dt or e d u c et h en u n l b e ro fc o h l p u t i n ga n ds i i n p l i f yc o m p u t i n g p r o c e s s ，t h e r e b ys i 印i f i c a n t l yi i n p r o v i n gt h ee m c i e n c yo ft h ek e m e la l g o r i t l l i i lw i t ht 1 1 en e w k e m e lp a r a m e t e r 山东师范大学硕士学位论文一 3 p r o p o s et h eo b je c t i v em n c t i o nf 斫t h ek e m e lb a s e do nt h ek d e 血o d ss e l e c t i o no fp a r 锄e t e r s t h ek 锄e l 七a s e dk d e m i o d si sa 1 1i 】 1 1 p r o v e dm e t h o do ft h ek n na l g o r i t h m t h ee x i s t 协g k 锄e 1 b a s e dc l a l s s i f i c a t i o nf o c u s e so n 1 ea d o p t i o no fk e m e lm a p p i n gt oi i i l p r o v em er a t eo f c o r r e c tc l a s s i f i c a t i o n ，b u tm ec o 玎e c tc 1 硒s i f i c a t i o nr a t ei sd i r e c t l yl i n k e dt ot h ep a r 锄e t e r s e l e c t i o n t 1 1 r o u 曲d e s c b i n gm ee x p e c t a t i o n so fd i s t r i b u t i o no fd a t ap o i n t si nt l l en e wf e a ：m r e s p a c e ，w ec h o o s et h eo p t i m a lp a r a m e t e r sm r o u g hm i i l i m i z i n gn l eo b j e c t i v e 劬c t i o n ，m u s i m p r o 、，i n g t 1 1 e p e r f o n l l a n c eo ft l l ek e m e l - b 雒e dc l a s s i f i c a t i o n t h ee x p e r i m e n t ss h o wt h e e f f e c t i v e n e s so ft l l ea l g o f i t l l i l lo nt l l ea r t i f i c i a ld a t as e t sa 1 1 du c id a t as e t s 4 s u 姗a r i z em ek 咖e 1p a r 撇e t e rs e l e c t i o nm e t l l o d s ，a n dc o m p a r et h e i re f f e c i t a v e n e s st h r o u g h e ) ( p e r i m e n t a lv a l i d a t i o n t l l i sp 印e rd e s c r i b e st h ec h o o s i n gp a r 锄e t e r so fm ek e m e l - b a s e dc l a s s i f i c a t i o n ，f o r e x a i r l p l e ：c u t 一趾d 一姆a i l ds oo n t h e s ea l g o r i 伽n sp l a ya i le s s c n t i a lr 0 1 ei 1 1g u i d i i l gm e s e l e c t i o n m e t h o do fm ek e m e lp 觚u n e t c r s t h ep a p e ra l s op r o v i d e st 1 1 er e l a t e de x p 嘶m e l l t a lv a l i d a t i o n a n dp a r t i c u l a re x p e r i m e l n a la n a l v s i s k e y w o r d s ：s u p p o r tv e c t o rm a c l l i n e ；k m e a i l sa 1 9 0 r i t h m ； f i s h e rd i s c 面f n i m m t a n a l y s i s ； p e r c 印t r o n ； c l a s s i f i c a t i o n ：t p l 8 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的， 本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 粒敝储样：研社 翩婵： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权i 争监可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： i p 强钰 导师签字 签字日期：2 0 0 譬年妄月孑口日 签字日期：2 山东师范大学硕士学位论文 第一章绪论 1 1 引言 模式识别解决的是如何自动监测数据中的模式这一问题，它在现代人工智能和计算机 科学领域的许多问题中起着关键作用。我们根据模式理解某个数据源中内在的关系、规律 性或者结构。通过检测提供的数据中的显示模式，系统能够对来自同一数据源的新数据作 出预测。在这个意义上，系统通过“学习”关于生成数据的数据源的信息，获得了泛化能 力( g e n e r a l i s 撕o n p o w e r ) 。许多重要的问题只有运用这种方法才能得到解决，这些问题涉 及的领域包括生物信息学、文本分类、图像分析以及w 曲检索。近年来，模式识别已经 成为一种标准的软件技术，出现在许多智能产品中。 模式识别具有悠久的历史，但在2 0 世纪6 0 年代以前，模式识别主要是统计学领域中 的理论研究。计算机的出现提高了对模式识别实际应用的需求，二者反过来又对理论发展 提出了更高的要求。就像我们的社会从工业化到后工业化阶段一样，工业生产中的自动化 以及信息处理和检索的需求变得日益重要，这种趋势把模式识别推向今天的工程应用和研 究的高级阶段。在大多数机器智能系统中，模式识别是用于决策的主要部分。 1 1 1 模式识别的应用领域 模式识别是一门以应用为基础的学科，目的是将对象进行分类。这些对象与应用领域 有关，它们可以是图像、信号波形或者任何可测量且需要分类的对象。可以用专用术语“模 式 来称呼这些对象。 在机器视觉中，模式识别是非常重要的。机器视觉系统通过照相机捕捉图像，然后通 过分析生成图像的描述信息。典型的机器视觉系统主要应用在制造业中，作为自动化视觉 检验或装配线的自动化。在装配线上，必须对不同的对象进行定位和识别，然后机器手把 这些对象放置在正确的位置。 字符( 字母或数字) 识别是模式识别应用的另一个重要领域，主要用于自动化和信息 处理。光学字符识别( o l p t i c a lc h a r a c t e rr e c o g m t i o n ，o c r ) 系统已经开始在商业中应用， 而且我们或多或少都对其有所了解。o c r 系统有一个前端设备，有光源、扫描镜头、文 档传送机和检测器组成。在光敏监测器的输出端，光的强度变化转换成数字，并形成图像 阵列。然后，一系列的图像处理技术的应用完成了线和字符的分段，模式识别软件完成字 符识别的任务，也就是将每一个符号分到相应的“字符、数字、标点符号”类中。 计算机辅助诊断是模式识别的另一个重要的应用，目的是帮助医生做诊断决定，当然 最终的诊断由医生来完成。计算机辅助诊断已经用于实际，主要研究各种医疗数据，如x 射线、计算机断层图、超声波图、心电图和脑电图。计算机辅助诊断的需求源与医疗数据 较难解释，并且解释结果多依赖于医生的经验。 语音识别是模式识别的另一个研究领域，在这个领域中已经进行了大量的研究。语音 是人类最自然的沟通和交换信息的方式。因此，长期以来，建立能够识别语音信息的智能 山东师范大学硕士学位论文 机器成为科学家和科幻小说家的目标。这种机器的潜在应用是广泛的。计算机语音输入的 速度是熟练打字员输入的两倍，而且有助于增强我们和聋哑人的交流能力。 前面提到的只是众多可能应用中的四个例子。典型的应用包括指纹识别、签名认证、 文本检索、表情和手势识别。目前的应用研究吸引了很多研究者，其目的是使人机互动更 简单，并增强计算机在办公自动化等环境中的作用。为了激发想象力，值得一提的是 m o e g 7 标准，它包含对数字图书馆中录像带的视频信息检索，在数字图书馆中查找所有 显示某人“x 微笑的视频场景。当然，要在所有这些应用中达到最终目标，模式识别还 依赖于其他一些学科的发展，如语言学、计算机图形学和计算机视觉等。 1 。1 2 三种学习方式 依照学习过程中有没有教师参与，学习可以分为三种基本形式【3 】：监督学习、增强学 习和无监督学习。 监督学习( s u p e r v i s e dl e 锄i n g ) ：在监督学习中，存在一个教师信号，对训练样本集 中的每个输入样本能提供类别标记和分类代价，并寻找能降低总体代价的方向。监督学习 过程如图1 1 所示。 图1 1 监督学习示意图 增强学习( r e i n f o r c e m e n tl e 锄i n g ) ：训练模式分类器的典型做法是，给定一个输入 样本，计算它的输出类别，把它与已知的类别标记作比较，根据差异来改善分类器的性能。 在“强化学习“( r e i n f o 】r c e m e i l tl e 锄i n g ) 或“基于评价的学习”( 1 e a n l i n g w i t ha c r i t i c ) 中， 并不需要指明目标类别的教师信号。相反的，它只需要教师对这次分类任务完成情况给出 “对”或“错 的反馈。这就好像是说一个评价仅仅给出了某种判断是“对”还是“错”， 而没有给出“错在哪里。在模式识别中，最普通的评价是一个二值的标量：“对”或者“错”。 图1 2 给出了一个增强学习的示例。 2 山东师范大学硕士学位论文 强 图1 2 增强学习示意图 无监督学习( u ，n s u p e i s e dl e a n l i n g ) ：在无监督学习算法或“聚类算法 中并没有现 实的教师。系统对输入样本自动形成“聚类”( c l u s t e r ) 或“自然的”组织。所谓“自然 与否是由聚类系统所采用的显式或隐式的准则确定的。给定一个特定的模式集和代价函 数，不同的聚类算法将导致不同的结果。通常要求用户事先指定预定的聚类的数目。如图 1 3 所示。 环境 状态向量学习系统 图1 3 无监督学习 1 1 3 学习问题研究的四个阶段 学习问题的研究可以分为四个阶段，它们分别以下面四个重要事件为标志【2 3 】： 1 第一个学习机器的创立( 2 0 世纪6 0 年代) 2 0 世纪6 0 年代初，f r o s e n b l a t t 【1 9 】提出了第一个学习机器的模型，称作感知器，标 志着人们对学习过程进行数学研究的真正开始。 2 学习理论基础的创立( 2 0 世纪6 0 7 0 年代) 2 0 世纪6 0 年代末，m m i n s l ( y 和s p a p 嘶在感知器一书中指出感知器的缺陷并 表示出对该方面研究的悲观态度，从而使得对感知器的研究陷入停滞状态。然而，这段时 间里统计学习的发展却是硕果累累。vv 却1 1 i k 等人【2 2 】【2 3 1 确立了经验风险最小化原则的理 论；a n t i l ( 1 l o n o v 等提出解决不适定问题的正则化理论；e p a r z e n 等密度估计的非参数 方法以及r j s 0 1 0 m o n o 仃和a n k 0 1 m o g o r o v 等提出算法复杂度思想等等【2 3 1 。 3 神经网络的创立( 2 0 世纪8 0 年代) 2 0 世纪8 0 年代初，h o p n e l d 网络【1 1 】以及多层感知器的反向传播算法【1 8 】的提出，掀起 了神经网络研究的热潮。这一阶段诞生了一系列重要的神经网络模型。比如t k o h o n e n 【1 2 】 的自组织映射网络( s e l f o 唱a 1 1 i z i n gm a p ，简称s o m ) ，ge h i n t o n 【1 0 】的b o l t z m 锄机， 3 山东师范大学硕士学位论文 s g r o s s b e 玛【9 j 的自适应谐振模型( a d a p t i v er e s o n a l l c et h e o r y ，简称脚玎) 以及d s b r o o m h e a d 和d l 0 w e 【5 】的径向基函数( r b f ) 神经网络。 4 神经网络替代方法一新的学习方法的创立( 2 0 世纪9 0 年代至今) 这一阶段，人们把更多的注意力放在了对神经网络的替代算法的研究上，统计学习理 论中的较高深的部分现在开始吸引更多的学者。2 0 世纪9 0 年代初，随着建立在结构风险 最小化原则基础上的支持向量机( s u p p o nv e c t o rm a c t l i l l e s ，简称s v m s ) h 儿2 2 鹏1 的诞生， 延伸出了一种基于核的学习方法。本文将在下一节以及随后的几章对此做详细的阐述。 1 2 基于核的学习 支持向量机分类器的基本原理是：使用个非线性变换将一个线性不可分的空间映射 到一个高维的线性可分的空间，构造样本的最优分类面，也就是建立一个具有极小n 维数 的分类器，该分类器仅由大量样本中的极少量支持向量确定，且具有最大的边界宽度。这 个最优分类面的构造过程即实现结构风险最小化的准则的过程。 支持向量机分类器的技巧在于放弃直接计算复杂的非线性变换，转而采用核函数来计 算非线性变换的点积，从而大大简化了计算。通过把核函数引入到一些学习算法，可以方 便地把线性算法转换为非线性算法，我们将其与支持向量机一起称为基于核函数的方法。 这种思想已经被成功地运用到除s 订s 之外的其它算法上，比如核主分量分析( k e m e l p 血圮i p a lc o m p o n 铋ta m a l y s i s ，简称c a ) 就是线性主分量分析( p 血c i p a lc o l n p o n e n t a n a l y s i s ，简称p c a ) 的自然推广，在输入空间映射后的特征空间中进行p c a 操作，提取 样本的非线性特征。典型的基于核的学习算法还有核f i s h e r 判别7 d a 仪e m e lf i s h e r d i s c r 沛i 1 1 a n ta n a l y s i s ) ，即在核映射的特征空间里求解f i s h e r 线性判别，从而生成输入空间 里的非线性判别量。 在这之后，众多研究者纷纷开始“核化 原有的线性算法，即通过把数据映射到高维 特征空间的核代入过程把传统的线性算法推广为相应的非线性算法，从而加强传统的线性 学习器的计算能力，并且开辟了一个被称为“基于核的学习( k 锄e 1 一b a s el e 卸血g ) ”( 简 称核方法) 嘲嘲m 懈1 的研究领域。 。， 1 9 9 2 年在计算学习理论( c o l t ) 会议上首次出现的支持向量机( s v m s ) 理论已经 成为了机器学习领域内的一个重要的革新。s s 的一个关键特性是坚实的理论基础和几 何上的可解释性。事实上，s s 是少数几个源自学习理论本身并成为业内标准的算法之 一。目前，s v m s 已经从最初的分类拓展到了处理回归、密度估计以及新颖性检测等多种 任务1 5 1 2 3 | 。 s 汀s 中的一个关键技巧是用核函数替换内积从而使线性算法变成非线性。通过核代 入( 隐含地把数据映射到高维特征空间) ，一个线性的算法可以转换成非线性算法，这种 思想已经被成功地运用到除s v m s 之外的其它算法上，比如线性主分量分析( 蹦n c i p a l c o i n p o n e n ta n a l y s i s ，简称p c a ) 暖1 | 。在这之后，众多研究者纷纷开始“核化”原有的线 性算法，即通过核代入把传统的线性算法推广为相应的非线性算法，并且开辟了一个被称 为“基于核的学习( k e m e l b a s el e 锄i n g ) ”( 简称核方法) 的研究领域。本节将在下面的 4 山东师范大学硕士学位论文 部分介绍核方法的实质、目前典型的基于核的学习算法以及一些应用领域。 1 2 1 核方法的实质 比较古老的核的理论，即m e r c e r 定理可以追溯到1 9 0 9 年。a n k 0 1 1 1 1 0 9 0 r o v 和n a r o n s z 旬n 从2 0 世纪4 0 年代开始了有关再生核空间的研究。2 0 世纪6 0 年代，m m i i l s k y 和s p a p e n 指出：线性学习器( 包括感知器) 的计算能力是十分有限的。一般说来，真实 世界中一些复杂的应用需要比线性函数更富表达能力的假设空间。换句话说，目标概念通 常不能由给定属性的简单线性函数组合产生，而是需要利用数据更抽象的特征。 核的理论最早被引入机器学习领域是在1 9 6 4 年，m z e m 锄、e b r a v e n n a n n 和l - r o z o e n e r 在势函数方法中应用m e f c e r 定理把核解释为特征空间中的内积。然而一直到 2 0 世纪9 0 年代中期，b b o s e r 、i g u y o n 和vn v a p n i l 【提出支持向量机( s s ) 算法 后，该理论的实际价值才开始被人们所广泛认识。并且在经过b s c h 6 1 k o p f 等人后续的工 作，逐渐形成了如下的“核技巧”：任何一个只依赖于内积的算法都可以被“核化”。 可从以下几个方面来理解核代入方法的实质： 首先，由t m c o v e r 的模式可分性定理可以知道，一个复杂的模式分类问题从低维 空间映射到高维空间后，变得更容易线性可分h 1 。图1 4 给出了一个低维空间中的非线性 问题映射到高维空间后变成线性问题的一个示例。如图所示，左图是一个低维空间中的非 线性数据集，右图是经过核转换后在高维空间中所形成的线性数据集。我们可以看到，使 用线性分类器经过核转化后可以对非线性的数据集进行分类，并且分类效率更优。 其次，由满足m e r c e r 定理( m e r c e r1 9 0 8 ) 的核函数可以诱导出从输入空间到高维特 征空间的隐含的映射。核函数要求满足m 条件。非线性产生的是一个高维特征空间，如 果直接在这个特征空间作内积计算会面临另一个维数灾难问题。核函数的内积计算的应用 解决了维数灾难问题。 最后，将非线性分类器通过核函数映射到高维特征空间中去，但计算量并没有随着维 数增多而增加很多。 x 轴 图1 。4 低维空间中的非线性问题映射到高维空间后变成线性问题 5 山东师范大学硕士学位论文 1 2 2 典型的基于核的学习算法 在这一小节中，我们回顾自s s 被提出后出现的典型的基于核的学习算法如下： 1 支持向量机s v m s 1 9 9 2 年由vv a p i 放等人n 2 1 开创性地提出。像多层感知器和径向基函数网络一样， s v m s 可以被用于模式分类和非线性回归等领域。s s 的主要思想是寻找使正负样本间 隔最大的分类面，这通过极小化包括经验风险和v c 维在内的结构风险而得到。 2 核主分量分析k p c a ( k e n l e lp r i n c i p a lc o m p o n e n ta n a l y s i s ) 1 9 9 8 年由b s c h 6 l k o p f 等人心提出。与主分量分析( p c a ) 一样，k p c a 也属于无监 督学习。k p c a 是p c a 的一个自然的推广，在输入空间映射后的特征空间中进行p c a 操 作，提取样本的非线性特征。 3 核f i s h e r 判别l 江d a ( k e n l e lf i s h e rd i s c r i m i n a l l ta n a l y s i s ) 分别由s m i k a 等n 引，v r o t h 等啪1 以及gb a u d a t 等嘲提出。k f d a 是在核映射的特 征空间里求解f i 幽e r 线性判别，从而生成输入空间里的非线性判别量。 4 其它模型 包括核感知器模型k p ( k e m e lp e r c e p 怕n ) 8 1 2 钔嘲、模糊核感知器f k p ( f u z z yk e m e l p e r c 印们n ) 乜1 l 、核最近邻算法k n n ( k e m e ln e a r e s t n e i g h b o r ) 乜引、核自组织映射k s o m ( k e m e ls o m ) 1 7 】。 1 3 本章小节 本章从核方法入手，简单介绍了核方法的实质。然后通过图像得出核方法的参数的 选择对于基于核的分类法具有重要作用的结论。最后文章对现有的选择核参数的方式效果 进行了归纳与比较，从而分析得出了各种选择参数方式的优缺点。 6 山东师范大学硕士学位论文 第二章核的理论基础 2 1 引言 早在2 0 世纪6 0 年代，m m i i l s k y 和s p a p e n 侧就已指出了线性学习器( 包括感知器) 的计算能力是十分有限的。一般说来，真实世界中一些复杂的应用需要比线性函数更富表 达能力的假设空间。换句话说，目标概念通常不能由给定属性的简单线性函数组合产生， 而是需要利用数据的更抽象的特征。解决该问题的一个办法是采用多层阈值线性函数，从 而导致了多层神经网络以及训练该系统的反向传播学习算法的发展田1 核函数的使用提供了一种强有力的、符合原理的方法，在适当的特征空间中用人们熟 知的线性算法检测非线性关系。这种方法把算法设计从特征空间的描述中分离开来。这种 内在的模块性，不仅增强了这种方法的灵活性，也使得学习算法和核设计更加经得起形式 化分析的检验。不管使用哪一种模式分析算法，指定的核的理论性质都是相同的。 2 2 特征空间及核的定义 核方法提供了解决上述问题的另一种途径：即通过把数据映射到高维特征空间来增 加传统的线性学习器的计算能力。本文在第一章绪论中简单回顾了核方法的由来及其实 质、典型的基于核的学习算法及其相关应用。本章将更为深入的介绍核的理论基础，首先 在2 2 节介绍特征空间及核的概念；2 3 节阐述再生核理论及m e r c e r 定理；2 4 节介绍几种 常用的核函数及其构造：2 5 节对本章做了一个小节。 首先给出特征空间及核( 函数) 的概念如下： 定义2 一l 特征空间口1 ：假定模式x 属于输入空间z ，即x z ，通过映射矽将输入空间z 映射到一个新的空间f = 做叫x 力，称作特征空间。 定义2 2g r 锄矩阵n 3 1 ：给定一个向量集合s = 讧l ，魂j ，g r 硼矩阵被定义为z z 的矩 阵g ，其元素为g = ( x f ，工，) 。 如果我们利用核函数盯来求特征映射为矽的特征空间中的内积，则与之关联的g r 锄 矩阵的元素是g ：【= ( 如工如) ) = 如，) ，在这种情况下，这个矩阵经常被称为核矩阵 ( k e r n e lm a t r i x ) 。 定义2 3 正定矩阵。订：一个朋m 矩阵k ，如果对所有一个都满足：c f c ，七驴o 则被称 扩 为正定矩阵。 定义2 4 正定核：令z 为一非空集，一个定义在静z 上的函数k ，如果满足对所有 聊圭( 为自然数集合) 西z 都产生一个正定g r a m 矩阵，则称其为正定核，简称 为核。 将数据映射到特征空间以便更有效地处理原空向中的任务，这一技术在模式识别领域 7 山东师范大学硕士学位论文 又称作特征选择。特征选择是模式识别的关键问题，特征选择的好坏往往对整个系统产生 决定性的作用。但如何获得针对特定问题的最合适的特征，目前仍然是模式识别领域中的 一个难点。一般地，由特征选择得到的特征空间的维数小于输入空间的维数，也就是通常 所说的降维，因为传统的方法在处理高维问题时容易导致维数灾难，即随着特征空间维数 的升高，计算复杂性呈指数增长。 另一方面，由第一章介绍的c o v c r 定理可知，一个复杂的模式分类问题在高维空间会 比在低维空间更容易线性可分。如果问题可以仅仅由特征空间中的内积来表示，则高维空 间中特征向量的内积可以通过核函数用低维空间中的输入向量直接计算得到，从而使得计 算量不会呈指数增长，避免了一般扩维方法中的维数灾难，这就是核方法的实质。公式表 示为： 忌( 万，z ) = ( 2 1 ) 其中尹是从x 到( 内积) 特征空间f 的一个映射 ：石争矽b ) f( 2 2 ) 这里尼( z ，z ) 表示内积运算，矽是从x 到( 内积) 特征空间f 的一个映射。实际上， 是( 石，z ) = 是核的另一种定义。 另外，使用核函数不需要事先知道映射的具体形式。事实上，给定一个核函数，我们 总能构建一个与这个核相联系的特征空间，使得该空间中的内积可以由核函数来表示。这 一点将由下一节中的理论得到保证。 2 3 再生核理论及m e r c e r 定理 我们已构造出特征空间，但是还必须指定映射下的输入x 的映像 矽：x x 卜专矽0 0 = k 阮) 乓( 2 3 ) 现在可以利用等式( 2 3 ) 求疋的一个元素和输入x 的映像之间的内积 ( 厂，g ) = ( 厂，k g ，) = 厂( x ) ( 2 4 ) 这正是我们所需的，也就是说，确实可以把函数f 表示成由特征空间e 中的内积( 核 函数f 本身) 定义的线性函数。而且，这一内积是严格的，如果l l 州= o ，那对于所有的x 有： i 厂g ) l = i ( 厂，g ) i i i 厂朋矽g 】l = o ( 2 5 ) 一个满足有限半正定性质的函数匿，我们把对应的空间只称为它的再生核希尔伯特 空间( r 印r o d u c i l l g k e m e lh i l b e r t s p a c e ，砌( h s ) 。类似地，当我们想强调对应的内积 的来源时，用记号( ，) ，表示这个内积。我们已经证明，如何使用任意的一个核构造个 满足再生性的希尔伯特空间。可以很直观的看到，如果对称函数茁( ，) 在这些函数的希尔 伯特空间f 中满足再生性，则 山东师范大学硕士学位论文 ( k ，g ，) ，厂( ) ，= 厂g ) ，其中厂， ( 2 6 ) 定义2 6 希尔伯特空间( h i l b e r ts p a c e ) ：希尔伯特空间( h il b e r ts p a c e ) 是一个具备 两个性质即f 可分性( s 印a r a b l e ) 和完备性( c o m p l e t e ) 的严格的内积空间。 完备性是指这样一种性质，即f 的元素