（计算机应用技术专业论文）基于双核复合的核分类算法研究.pdf

摘要 随着支撑向量机的成功应用，古老的核方法作为其重要组成部分，重新引起了 众多研究者的重视，并广泛地应用于模式识别，图像处理，机器学习等诸多领域。 随着核方法研究的深入，人们发现，使用了单一且固定核函数的传统核分类算法不 能有效地适应复杂多变的数据集合，从而导致分类效果欠佳。 针对传统核分类算法使用单一且固定核函数的不足，本文提出了一种基于双核 最优复合的核分类算法( o p t i m a ld o u b l e k e r n e lc o m b i n a t i o nm e t h o do d k c ) 。o d k c 算法复合了两个基本核函数，这样可以综合不同核的特性，很好的适应复杂多变的 数据集合，提高分类准确率。 具体工作如下： ( 1 ) 为了寻求核函数的最优复合，设计了一种准则函数。该准则函数的最优化 问题可以方便的转化为一个广义特征值问题，从而使算法具备了非迭代和低复杂度 的特性。 ( 2 ) 本文利用双核复合的方法构造了用于分类任务的目标核函数。首先，利用 两个基本核函数，将相同的输入数据集分别映射到两个不同的特征空间中去。然后， 通过融合这两个特征空间的属性信息构建目标核函数。本文研究了双核复合的三种 方式及其对分类效果的影响，并把这三种复合方式纳入到了统一的框架下讨论。在 该框架下，可以方便的讨论和比较各种核函数复合方式的性能。 ( 3 ) 采用了核函数与数据集匹配程度的度量( a l i g n m e n tm e a s u r e ) 和分类准 确率两种指标，在五种数据集合上进行了实验，实验结果表明了本文所提算法的有 效性。 关键词核复合；分类；核方法；模式识别 a b s t r a c t a b s t r a c t w i t ht h es u c c e s s f u la 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 e ( s v m ) k e r n e lm e t h o d s ， a sa r ti m p o r t a n tc o m p o n e n to fs v m h a v ec a u s e dm o r ea n dm o r er e s e a r c h e r s a t t e n t i o n n o w a d a y s ，a n da r ew i d e l yu s e di np a t t e r nr e c o g n i t i o n ，i m a g ep r o c e s s i n g ，m a c h i n e l e a r n i n ga n dm a n yo t h e rf i e l d s a l o n gw i t ht h ef u r t h e rd e v e l o p m e n to fk e r n e lm e t h o d s r e s e a r c h e r sr e a l i z e dt h a tt r a d i t i o n a lk e r n e l i s e dc l a s s i f i c a t i o nm e t h o d sa r el i m i t e di nt h e i r p e r f o r m a n c eo nc o m p l i c a t e dd a t as e t sb e c a u s eo ft h eu s i n go fas i n g l ea n df i x e dk e r n e l i no r d e rt oo v e r c o m et h el i m i t a t i o no ft r a d i t i o n a lk e m e l i s e dc l a s s i f i c a t i o nm e t h o d s a n o v e lo p t i m a ld o u b l e k e r n e lc o m b i n a t i o nm e t h o d ( o d k c ) i sp r o p o s e di n t h i sp a p l e l o d k ci sc o m p o s e do ft w od i f f e r e n tb a s i ck e r n e l s w h i c hc a nt a k et h ea d v a n t a g e so f v a r i o u sk e m e l st ob e t t e ra d a p tt oc o m p l i c a t e dt a s k s t h e w o r ki nt h i sp a p e ri sa sf o l l o w ： ( 1 ) ak i n do fc r i t e r i o nf u n c t i o ni sp r o p o s e dt os e e kt h eo p t i m a ld o u b l e k e r n e l c o m b i n a t i o n t h ep r o b l e mo fo p t i m i z a t i o nw i t ht h i sc r i t e r i o nf u n c t i o nc a nb er e d u c e dt oa g e n e r a l i z e de i g e n v a l u ep r o b l e me a s i l y , s ot h a t0 d k cp r o c e s s e sn o n i t e r a t i v ea n d1 0 w c o m p u t a t i o n a lc o m p l e xp r o p e r t y ( 2 ) au n i f i e df r a m e w o r ki sp r o p o s e d ，i nw h i c hw es t u d yt h r e ek i n d so fc o m b i n a t i o n s o fm a p p i n g s f i r s t l y , d a t as e t sa r em a p p e db yt w ob a s i ck e r n e l si n t od i f f e r e n tf e a t u r e s p a c e sr e s p e c t i v e l y , a n dt h e nt h r e ek i n d so fo p t i m a lc o m p o s i t ek e r n e l sa r ec o n s t r u c t e d b yi n t e g r a t i n gi n f o r m a t i o no ft h et w of e a t u r es p a c e s i ti st h eu n i f i e df r a m e w o r k t h a tw e c a nd i s c u s sa n dc o m p a r et h ee 疏c to f e a c hk i n do fc o m b i n a t i o ne a s i l y ( 3 ) t w op a r t so fe x p e r i m e n t so nf i v ed a t as e t sa r ec o n d u c t e dt od e m o n s t r a t et h e e f f e c t i v e n e s so fo u rm e t h o d s k e yw o r d sk e r n e lc o m b i n a t i o n ；c l a s s i f i c a t i o n ；k e r n e ll e a r n i n g ；p a t t e r nr e c o g n i t i o n i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：寻微日期： 第1 章绪论 1 1 课题研究的背景 第1 章绪论 2 0 世纪8 0 年代，模式识别领域几乎同时引入了后向传播多层神经网络算法和高 效的决策树学习算法。尽管这些方法用到了启发式算法和不完全统计分析，它们第 一次使得检测非线性模式成为可能，激活了诸如数据挖掘和生物信息学的整个领域。 然而，这些非线性算法，是建立在梯度下降法或贪心启发式法的基础上，因而受到 局部极小化的限制，同时存在着“维数灾难”的问题。 2 0 世纪9 0 年代中期，出现了新的被称为基于核的( k e r n e lb a s e d ) 学习方法的 模式分析方法。核方法在数学中是个古老的命题，早在1 9 0 9 年j m e r c e r 提出了有关 核函数的概念。直到1 9 6 4 年a i z e r m a n 率先在机器学习领域引入了核函数的使用。2 0 世纪9 0 年代，c o r t e s 和v a p n i k 弓l 入了支撑向量机模型n m 别，使得核方法在与支撑向量 机模型的结合应用中爆发出新的活力，成为当时非线性算法领域的研究热点之一。 随后，高效且有理论保证的线性算法在与核方法结合后，产生了一系列的核化方法， 如：核f i s h e r 判别( k f d a ) 口1 ，核最小均方误差( k m s e ) h 1 等等。它是通过一个隐性的 特征映射可以将输入空间( 低维的) 中的线性不可分数据映射成高维特征空间中的 线性可分数据。因此成熟而高效的线性分类算法得以在高维的特征空间中进行。核 方法正是借用这一隐性的非线性特征映射( 当然也可以是线性的) 使得线性不可分 的数据在高维特征空间中变得易于处理，同时又回避了高维空间带来的维数灾难。 该方法最终使得研究人员能够高效地分析非线性关系，而这种高效率原先只有线性 算法才能够达到。该方法在统计理论方面进一步发展之后，控制了过度拟合的危险。 从计算的、统计的和概念的角度来看，核方法和线性算法一样，高效而富有理论根 据。同时，这些方法在处理非向量型数据方面非常有效，这样就建立起了和模式分 析的其他分支的联系。 但在实际应用中，传统的核化分类算法对各种复杂任务的适应能力是十分有限 的。如何选择核函数及其参数使之适应复杂多变的分类任务是实际应用中面临的现 实问题。针对这一问题，许多研究者做出了卓越的贡献。近年来，针对这些核化分 类算法的改进主要集中在了核参数的选择上。然而，由于分类任务的复杂性和多样 性，传统核方法由于使用了单一且固定的基本核函数，即使得到了最优的核参数， 对各种复杂任务的适应能力也十分有限哺儿8 7 1 。 北京工业大学工学硕士学位论文 为此，出现了面向特定任务，利用多个基本核构造新的目标核函数的核优化方 法，从而避免了传统方法使用单一核的局限性。l a n c k i e t 等人在文献 5 中，利用多 个核函数的凸组合来构造目标核函数，并通过求解二次规划问题优化目标核。b a c h 等人在文献 6 中，针对文献 5 对大规模数据处理上的局限，提出了 5 3 中二次规划 问题的对偶形式。文献 7 和文献 8 提出了加速算法用于实现多种基本核的复合。 在文献 9 中，x i o n g 使用了依赖数据核( d a t a d e p e n d e n tk e r n e l ) 作为目标核函数并 提出了新的类间分离性度量。针对文献 9 中的缺点，c h e n 等人在 1 0 中指出，文献 9 使用的准则函数不能很好的适应某些复杂数据集，同时提出了统一的核优化方法 的框架。然而，无论是 9 还是 1 0 ，其方法总是需要更多的标签数据。因为一部分 样本将用来构造依赖数据核，而另一部分则用来训练。另外，文献 9 ，1 0 使用了迭 代算法，而迭代次数需提前给出。在文献 1 1 中，c r i s t i a n i n i 等人提出了衡量核函 数“好坏”的度量，即，目标核适合性度量( k e r n e lt a r g e ta 1 i g n m e n tk t a ) 。k t a 值越高，说明核函数越适应于目标数据。为了表明o d k c 核函数比传统的基本核函数 能更好的适应各种目标数据，本文在5 2 节采用了“适应性度量”( a 1i g n m e n tm e a s u r e ) 实验。 与传统方法相比，上述各方法在对复杂数据的适应性上有了一定的改善，但都 没有从计算结构( 计算机制) n 习上分析其对复杂多变的分界面函数学习的有效性。 而且，其中的大多数算法仍无法摆脱作为浅层计算机制n 羽的算法局限性。计算结构 是y o s h u a 等人在文献 1 2 中提出的重要概念，如图 卜1 和图 1 2 所示。 加权和 l 固定的 基函数 加权和 彳卜 模板匹配 加权和 f 简单的可训练 基函数 ( a ) ( b )( c j 图i - i 三种浅层计算结构的学习算法的结构图 f i g 1 - lt h es t r u c t u r eo ft h r e ek i n d so fl o wa r c l l i t e c t u r el e a r n i n ga l g o r i t h m s 第1 章绪论 输入层隐藏层输出层 图1 - 2 深层计算结构学习算法网络结构图 f i g 1 - 2t h en e t w o r ks t r u c t u r eo f d e e pa r c h i t e c t u r el e a r n i n ga l g o r i t h m 在 1 2 中，作者将各种学习算法划分为浅层计算结构和深层计算结构加以分析 和研究，并从数学上和实验上证明：浅层计算结构学习算法( 如，传统核方法和单隐 含层的神经网络) 不能有效的表达复杂多变的函数，而深层计算结构学习算法( 如，2 层或更多隐含层的神经网络) 则更具表现力。然而，训练困难时常成为深层计算结构 学习算法应用的局限。 为了探索一种非迭代低复杂度且能适应复杂数据集学习任务的学习算法，本文 提出了一种双核复合的核分类算法( o p t i m a ld o u b l e - k e r n e lc o m b i n a t i o nm e t h o d o d k c ) 。 从计算机制和使用性能上讲，o d k c 方法可被看作介于浅层和深层计算结构算法 的一种折中。优于传统核方法等浅层计算结构算法，o d k c 由两个基本核复合而成， 这样可以很好的适应复杂数据集，并有着更强的学习能力。由于目标函数的最优化 问题转化成了广义特征值问题，o d k c 同时又比深层计算结构算法有着较低的时间复 杂度。从信息融合的角度上讲，相对于抽象层上的分类器融合，o d k c 是对较低层( 即 特征空间层) 信息融合的一个崭新探索。 本文正是以目标核函数的核优化这个研究热点为研究内容，分析和借鉴了传统 方法和上述诸多算法的特点，提出了如何利用双核复合的方式去构造最优的目标核 函数，并在诸多方面有着优于传统方法和上述各算法的优越性。 北京工业大学丁学硕士学位论文 1 2 课题研究的内容及其现实意义 核方法是一种优越的非线性学习算法在各个领域得到了广泛的应用。作为模块 化的学习算法，核方法可与现有的经典学习算法相结合，从而产生新的扩展版本算 法，并且广泛的应用于模式识别，图像处理，机器学习等诸多领域。本文相关课题 的研究具有深远的理论意义和现实意义。 随着核方法理论的不断发展，人们可以高效处理非线性数据。但在实际应用中， 传统的核化分类算法对各种复杂任务的适应能力是十分有限的。但在实际应用中， 传统的核化算法使用了固定且单一的核函数，对各种复杂任务的适应能力十分有限。 如何选择核函数及其参数使之适应复杂多变的任务是实际应用中面临的现实问题。 针对这一问题，许多研究者作出了卓越的贡献。其中包括核参数的优化和利用多个 基本核构造新的目标核函数的核优化方法。 与传统方法相比，这些方法在对复杂数据的适应性上有了一定的改善，但都没 有从计算结构上分析其对复杂多变的分界面函数学习的有效性。而且，其中的大多 数算法仍无法摆脱作为浅层计算结构学习算法( 如，传统核方法和单隐含层的神经 网络) 的局限性。深层计算结构学习算法( 如，2 层或更多隐含层的神经网络) 虽然能 有效的表达复杂多变的函数，然而，训练困难时常成为深层计算结构学习算法的局 限。 作为浅层计算结构与深层计算结构算法的一种折中，本文提出了种双核复合 的核分类算法( o p t i m a ld o u b l e k e r n e lc o m b i n a t i o nm e t h o do d k c ) 。具体工作 如下： ( 1 ) 为了寻求核函数的最优复合，提出了种准则函数。该准则函数的最优化 问题可以方便的转化为一个广义特征值问题，从而使算法具备了非迭代和低复杂度 的优良特性。 ( 2 ) 本文利用双核复合的方法构造了用于分类任务的目标核函数，研究了双核 最优复合的三种方式及其对分类效果的影响，并把这三种复合方式纳入到了统一的 框架下讨论。在该框架下，首先利用两个基本核映射，将相同的输入数据集分别映 射到两个不同的特征空间中去。然后，通过融合这两个特征空间的属性信息构建目 标核函数。 ( 3 ) 采用了核函数与数据集匹配程度的度量( a l i g n m e n tm e a s u r e ) 和分类准 确率两种指标，在五种数据集合上进行了实验，实验结果表明了本文所提算法的有 效性。 第1 章绪论 从计算结构和使用性能上讲，o d k c 是作为一种折中方案，优于传统核方法等浅 层计算结构算法。o d k c 由两个基本核复合而成，这样可以很好的适应对复杂数据集 并有着更强的学习能力。由于目标函数的最优化问题转化成了广义特征值问题，o d k c 同时又比深层计算结构算法有着较低时间复杂度。 从信息融合的角度上讲，相对于抽象层上的分类器融合，o d k c 是对较低层，即 特征空间层，信息融合的一个崭新探索。因此，作为未来相关领域研究工作的基础， 本课题有着重要的理论价值。另外，在处理高维复杂数据集合的实际应用场合，0 d k c 方法有着不可比拟的优越性，该课题的研究同时有着重要的现实意义。 1 3 本文结构 本文主要提出了一种双核复合的核分类算法，并从理论和实验上论证了该方法 的优越性。 本文正文部分总共分五章，主要结构和内容如下： 第1 章是绪论，提出问题。介绍了课题研究的背景和现实意义。 第2 章对核方法理论作了一个总体介绍，并对本文主要涉及的一些基本概念和理 论知识作了阐述。 第3 章对目前广泛应用的核化方法进行了简要的叙述并分析了当今国内外关于 核方法的研究现状和发展趋势。 第4 章提出了一种双核复合的核分类算法( o d k c ) 。主要研究了三种双核复合的方 式及其对分类效果的影响，并把这三种复合方式纳入到了统一框架下讨论。 第5 章进行了适应性实验和分类准确度实验，并对实验结果进行了分析。 最后是对整个论文以及研究生期间学习研究工作的总结，指出了本文的研究内 容和所取得的创造性成果以及创新点理论，对核方法和o d k c 方法的理论价值进行了 预测和评价，并对在该研究方向将来的进一步研究工作的开展进行了展望。 第2 章核方法理论概要 2 1 引言 第2 章核方法理论概要 2 0 世纪9 0 年代，c o r t e s 和v a p n i k 弓j 入了支撑向量机模型口1 ，使得核方法在与支 撑向量机模型的结合应用中爆发出新的活力，成为当时非线性算法领域的研究热点 之一。随后，高效且有理论保证的线性算法在与核方法结合后，产生了一系列的核 化方法，如：核f i s h e r 判别( k f d ) 嘲，核最小均方误差( i ( m s e ) h 1 等等。事实上，基于 核方法的学习算法可以看作是模块化的学习算法。它通常由两个模块构成。第一个 模块是特征映射，由所谓的核函数隐式定义。对于分类任务，输入空间数据集合通 过这个隐性的特征映射可以将输入空间( 低维的) 中原本线性不可分数据映射成高 维特征空间中的线性可分数据，如图2 - 1 。这时，成熟而高效的线性分类算法作为第 二个模块得以在高维的特征空间中进行。核方法正是借助于这一隐性的非线性特征 映射，使得线性不可分的数据在高维特征空间中变得易于处理，同时又回避了高维 空间带来的维数灾难。该方法在统计理论进一步发展之后，还控制了过度拟合的危 险。 d 图2 - 1 特征映射西把数据映射到特征空间 f i g 2 - if e a t u r em a p p i n g 妒m a p d a t as e tt of e a t u r es p a c e 在实际应用中，核函数决定了特征映射的形式，也决定着算法应用的成败。正 是核函数概念的引入，有效的回避了高维空间带来的维数灾难。下节将简介核函数 概念及性质。 北京工业大学工学硕士学位论文 2 2 核函数的定义与性质 2 2 1 核函数的定义与g r a m 矩阵 定义2 一l ：令x = 五，吒) 为非空数据集合，蕾r d 。函数七：x x x 。r 被称 为有限半正定核或核函数当且仅当尼( ，_ ) = 后( _ ，x t ) 以及下面等式成立： c ，勺七( 薯，x j ) 0 ，v 刀2 ， 1 = 1j = l 其中c r r v r = l ，力。 核函数可以表示为：七( 葺，_ ) = 庐( 五) o x j ) ，其中驴：x f ，是输入空间x 到 高维特征空间确映射。 定义2 2 - 给定一个数据集合s = x l 一，x 。 ，g r a m 矩阵被定义为刀刀的矩阵g ， 其元素g f = ( 庐( x ，) ，4 , ( x j ) ) = 后( x ，x ) 。其中，后为对应于特征映射驴的核函数。g r a m 矩阵也被称为核矩阵。可以证明g r a m 矩阵是半正定矩阵。 目前广泛使用的基本核函数主要有多项式核和高斯核，下面给出这两种具体核 函数的定义。 定义2 - 3 多项式核( p o l y n o m i a lk e r n e l ) 定义为，对于一个给定的核函数 毛( x ，z ) ，其衍生的多项式核定义为： k ( x ，z ) = p ( 墨( x ，z ) ) ( 2 1 ) 其中p ( x ) 为任意一个具有正系数的多项式函数。但通常，多项式核是指下面 的特殊情况： ( x ，z ) = ( + r ) d ( 2 2 ) 其中，x ，z 为n 维向量空间x 中的元素，脐口提参数。式( 2 1 ) 是式( 2 2 ) 当p ) = + 月) d ，局( x ，z ) = 时的特例。多项式核作为全局核有利于发 现数据中蕴含着的宏观信息。 定义2 - 4 对于仃 0 ，高斯核定义为： k ( x ，y ) = e x p ( - u x - z l l 2 2 a 2 ) 。 其中，仃是该核的参数。高斯核函数是标准化了的核，因为k x ，x ) = e x p ( o ) = l ， 第2 章核方法理论概要 即，特征空间中点的范数为1 ：由k ( x ，z 1 _ o ，坛，z 彳可知，高斯核特征空间中的点 处于同一象限；参数。对核的灵活性有着控制作用，其作用相当于多项式核的参数d 。 仃值过小，容易过度拟合，核矩阵接近单位矩阵。相反，仃值过大，核函数接近常 值函数，无法分类。高斯核作为局部核有利于发现数据中蕴含的局部信息。 本文所提出的利用双核复合来构造目标核函数的方法，正是选择了多项式核和 高斯核作为基本核。这样可以发挥这两种核函数全局性和局部性的特点，有效的适 应复杂多变的数据集合。下面小节将不予证明的引入一个重要定理，该定理是该论 文工作的理论根据，它证明了若干个基本核函数经过下列复合之后仍然是合法的核 函数。 2 2 2 核函数的构造定理 定理2 一l ：令毛和也是定义在x x 上的核函数，x r n ，口r + ，( ) 是x _ k 的 一个实值函数，妒：x 专r ，毛是定义在r x r 上的一个核函数，腥一个f x 刀的 半正定对称矩阵。那么下列函数都是合法的核： ( 1 ) k ( x ，z ) = 墨( x ，z ) + 如( x ，z ) ( 2 ) k ( x ，z ) = a k i ( x ，z ) ： ( 3 ) 后( x ，z ) = 墨( x ，z ) 如( x ，z ) ； ( 4 ) k ( x ，z ) = 厂( 功( z ) ： ( 5 ) 七( z ，z ) 2 岛 ( 力，驴( z ) ) ： ( 6 ) k ( x ，z ) = x 。b z 。 若p ( x ) 是一个具有正系数的多项式。那么下列函数也是合法的核： ( 1 ) k ( x ，z ) = p ( k l ( x ，z ) ) ： ( 2 ) k ( x ，z ) = e x p ( k , ( x ，z ) ) ： ( 3 ) j j ( x ，z ) = e x p ( 一0 x z | | 2 ( 2 0 - 2 ) ) 。 注：一般把( 1 ) 称作广义多项式核，( 2 ) 称作指数核，利用t a y l o r 公式，指 数函数可被多项式函数任意逼近。( 3 ) 即高斯核，是指数核的标准化，即： e x p ( o - 2 ) 一 e x p ( o r 2 ) 乒x p ( 1 l xf2 o r 2 ) e x p ( 帅i i o r 2 ) e x p ( 2 c r 2 ) e x p ( 7 2 0 r 2 ) 北京t 业大学工学硕士学位论文 2 3 特征空间中的计算 = e x p ( 一i i x z l l 2 2 0 r 2 ) 基于核方法的学习算法在应用时通常包含两个步骤。首先将输入空间中的数据 集合通过一个特征映射，映射到高维( 甚至是无穷维) 特征空间中去。然后，成熟 而高效的现有算法得以在高维的特征空间中进行。核方法正是借用这一隐性的特征 映射回避了高维空间带来的维数灾难，使得数据在高维特征空间中变得易于处理。 直观上分析，在高维的特性空间中，传统的显式计算定会带来计算量关于空间维数 指数级，即维数灾难。核方法正是采用了隐式的计算方法从而有效的避免了维数灾 难。下面给出应用核方法时的常用计算公式。这些公式表明：在应用核方法时，只 需知道数据集合在原空间中的两两内积，而无需知道特征映射的显示形式。这正是 核方法可以有效避免维数灾难的机理。 给定输入空间x 的一个有限子集s = 五，西) ，核函数k ( x ，z ) ，以及对应的特征 映射砂，则有：k ( x ，z ) = ( ( x ) ，庐( z ) ) 和特征空间中的数据集合妒( s ) = 驴( _ ) ，妒( 西) ) 。 此时： ( 1 ) 特征空间中的向量2 一范数为： 8 妒( x ) 0 ：= i i ( x ) 9 2 = 石i 硼= 厕。 ( 2 ) 特征空间中数据点的线性组合为： 0 喜口，( , i 2 - = a ，a 知( 蕾) ，妒( 一) ) = a ，a ，后( ，_ ) 厶一lj ”j ， ( 3 ) 特征空间中特征向量之间的距离： 咖( x ) 一( z ) 0 2 = ( ( x ) 一咖( z ) ，咖( x ) 一咖( z ) ) = ( 庐( x ) ，庐( 工) ) 一2 ( 妒( x ) ，驴( z ) ) + ( ( z ) ，驴( z ) ) = 七( 石，x ) - 2 k ( x ，z ) + 七( z ，z ) 第2 章核方法理论概要 ( 4 ) 设特征空间中的数据集合的中心点为，( s ) 即：( s ) = 驴( 薯) 则，中 心点的2 范数为： ) h 邢) 纵s ) ) = 镰地) ，净( _ ) = f 1 荟i ( 妒( 五) ，妒( - ) ) = 古毫七( ) ( 5 ) 咖( x ) 到中心点咖( s ) 的距离为： 忪( x ) - 妒s l l 2 = ( 驴( x ) ，( x ) ) ( 九，丸) 一2 ( ( x ) ，九) = k ( x , 4 + 吉尼( ，x j ) 一号尼( 碱) ( 6 ) 特征空间所有数据点到中心点妒( s ) 的平均距离为： ( 屯) 一九0 = 号七( t ，t ) 一嘉七( _ ，x j ) 一手后( t ，誓) s = l s = l f j = l2 ，。s = l = 导七( t ，) 一吉七( 薯，_ ) 上述各个公式表明，只要知道了核函数的形式，从而计算g r a m 矩阵，就可以在 不知道特征映射咖显示形式的情况下完成各种算法。图2 2 显示了基于核方法学习系 统的执行过程。输入空间的数据集合通过核函数构建g r a m 矩阵，在使用相应的模式 分析算法作用于g r a m 矩阵。最后输出模式函数。 数 据 g r a m 矩阵 图2 2 基于核方法学习算法的执行过程 f i g 2 - 2t h ep r o c e s so fk e r n e lb a s e dl e a r n i n ga l g o r i t h m 北京丁业大学工学硕士学位论文 2 4 本章小结 本章首先介绍了核函数的定义以及如何利用基本核构造合法的复合核。然后对 特征空间的常用计算进行了推导，展示了核方法如何克服维数灾难的机理。在以后 章节中所提出的各种算法，都建立在本节相关定义和定理基础上。 第3 章国内外关于模式分析核方法的研究现状和分析 第3 章国内外关于模式分析核方法的研究现状和分析 3 1 引言 随着非线性支撑向量机的成功应用，使得核方法在与支撑向量机模型的结合应 用中爆发出新的活力，从而产生了一系列的经典算法与核方法的结合版本。这些方 法在使用时，首先，通过一个隐性的特征映射可以将输入空间( 低维的) 中的数据 映射到高维特征空间中，然后，成熟的经典学习算法得以在高维的特征空间中进行。 核方法正是借用这一隐性的非线性特征映射( 当然也可以是线性的) 使得数据在高 维特征空间中变得易于处理，同时回避了高维空间带来的维数灾难。该方法最终使 得研究人员能够高效地分析非线性关系，而这种高效率原先只有线性算法才能够达 到。尤其在统计理论方面进一步发展之后，核方法能够控制过度拟合的危险。 目前，核方法的广泛应用，主要作为各种经典算法的扩展化和非线性化。其中， 应用广泛且有理论保证的核化模式分析算法有：核模糊均值聚类，核f i s h e r 判别分 析，核m s e ，核p c a ，核c c a 等等。这些方法在本文中称为传统的核化方法。传统的核 化方法由于使用了单一且固定的基本核函数，在许多复杂数据集合中的效果欠佳。 针对这一问题，本文提出了一种基于双核最优复合的核分类算法( o p t i m a l d o u b l e k e r n e lc o m b i n a t i o nm e t h o do d k c ) 。在与这些传统方法比较之后显示了 o d k c 方法的优越性。下面简单回顾几种经典算法及其核化版本。 3 2 几种经典的模式分析算法及其核化方法 3 2 1 聚类分析与核聚类方法 作为无监督模式分类系统中的主要方法，聚类是一个古老的问题，它伴随着人 类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事 物间的相似性，而每个概念的最初形成无不借助于事物的聚类分析。因此，聚类分 析的研究不仅具有重要的理论意义，也具有重要的工程应用价值和人文价值。近年 北京工业大学t 学硕士学位论文 来，涌现出了许多著名的聚类方法，主要有：k 均值法( k m e a n s ) ，模糊c 均值( f u z z y c - m e a n s ，f c m ) 1 4 1 ， 可能性c 均值划分( p o s s i b i l i s t i cc - m e a n s ，p c m ) n 5 1 ，自 组织映射( s e l fo r g a n i z i n gm a p s ，s o m ) i t 6 ，n e u r a lg a s 1 刀，c u r e n 引，c h a m e l e o n 1 引， 基于粗糙集聚类乜，基于等价关系的聚类，图论方法，基于核方法的聚类方法等等。 这些方法在很多领域得到了广泛的应用，例如：数据挖掘，文本恢复，图象分割， 模式分类等等。对于聚类分析方法的分类尚无形成一致，但大多数研究者把聚类方 法粗略的分为两类：层次聚类昭u ( h i e r a r c h i c a lc l u s t e r i n g ) 和划分聚类 ( p a r t i t i o n i n gc l u s t e r i n g ) 。层次聚类能够对划分得到的子类进一步划分，如此 重复，最后形成层次或树状结构。而划分聚类只是对数据进行次划分，不会象层 次聚类那样产生层次状结构，划分聚类通常需要最优化适当的目标函数。这里，给 出简单的聚类问题形式化描述： 给定一组输入数据( 模式) 集x = 而，。) ，其中= x j l 2 ，。，) 1 r d ， 每一x ，是一个特征( 属性a t t r i b u t e ，维d i m e n s i o n ，变量v a r i a b l e ，特征f e a t u r e ) 。 硬划分聚类( h a r dp a r t i t i o n i n gc l u s t e r i n g ) 试图将输入数据成0 分到k 个类 别中去，c = c l ，q ( k n ) ，其中： ( 1 ) g 驴，= l ，k ； ( 2 ) u ：。c ，= 置 ( 3 ) cn c ，= 驴，j = 1 ，k a n d ， 层次聚类试图对输入数据踺立树状嵌套的划分结构：h = q ， ( q ) ， 满足：e 矾，c ，q ，当忉 - ，时，对于所有的，j f ，m ，= l ，q 有 c i c j o r c i r 、c j = 由。 对于层次聚类方法由于不能适应大数据量的情况，难以满足实时性较高的场合， 因此在实际中应用逐步减少。实际中受到普遍欢迎的是划分聚类方法。该方法通常 把聚类分析归结为一个带约束的非线性规划问题，通过优化求解获得最佳的划分和 聚类。因此，有些文献也把这种聚类称为：基于目标函数的聚类方法。 传统的聚类方法大多为硬划分，它把每个待分类的输入模式严格地划分到某个 聚类中，具有非此即彼的性质。而在现实生活中由于“模糊现象”的存在，实际上 大多数对象并没有严格的归属，它们在类属方面存在模糊性，具有亦此亦彼的性质。 模糊集理论恤1 的提出为进行能够反映对象类属方面存在模糊性的软划分提供了有力 的理论基础和分析工具，人们开始用模糊的方法来处理聚类问题，称为模糊聚类分 析。模糊聚类分析实际是硬划分方法的一种推广，更能客观的反映现实世界，表达 第3 章国内外关于模式分析核方法的研究现状和分析 样本类属关系的模糊性，从而成为当前聚类分析的研究主流 该方法把聚类分析归结成一个带约束的非线性规划问题，通过优化求解获得数 据集的模糊划分和聚类。这类方法设计简单、解决问题的范围广，还可以转化为优 化问题而借助经典数学的非线性规划理论求解，并易于计算机实现。因此，随着计 算机的应用和发展，基于目标函数的模糊聚类算法成为新的研究热点。下面给出有 关模糊聚类方法( f u z z yc - m e a n s ，p o s s i b i l i s t i cc - m e a n s ) 的数学模型。 定义3 - 1 模糊c 均值聚类：记4 。为实数域c x 刀的向量空间，给定输入数据集 合五如以及c n ，2 c 珂，则。啪模糊c 划分空间是集合： rc厅1 蚝= u 如：【o l m 办；= 1 v h ；0 - 一 - 0 ，汪1 ，n ，写成联立方程的形式i r a = 6 。 o y 2 0 ) n a b = b l 6 2 ，岛 0 ，i = l ，n 由于通常n d 即样本数( 方程的个数) 大于未知数的个数，所以上述方程组 一般为矛盾方程组，没有准确解。但可以定义一个误差向量p = g a b 和平方误差 准则函数：以( 口) = l e l l 2 = y a - b2 = ( 口7 乃一岛) 2 求使以( 口) 极小的a 作为问题的解。 i = l 这是矛盾方程组的最d , - - 乘解。正( 口) 称为最小平方误差准则函数。 作为m s e 的核化版本k e r n e lm s e ，实际上是先将待分类数据集通过特征映射西映 射到高维的特征核空间，然后在该特征空间求解矛盾方程组的最小二乘解。使用核 技巧，可得k e r n e lm s e 的判别函数为： f ( t ) = s g n ( 1 。+ k ) r ( 1 。l ：+ k ) + b 其中，o = ( 七( _ ，f ) ，尼( 吃，f ) ，忌( ，f ) ) 。，l 。= ( 1 ，1 ，1 。) 7 。 3 2 4p c a 与核p c a 主成分分析是把各燹量之司互相关联的复杂关系进行简化分析的方法。它试图 在力保数据信息丢失最少的原则下，对这种高维数据表