已阅读5页,还剩33页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要在过去的几十年内,数据采集能力的提高以及存储容量的增长,导致了科学研究的很多领域中信息量急剧增长,它向人们提供更加丰富、细致的信息的同时也造成了大量的信息冗余。在机器学习和模式识别领域的应用中,由于高维数据产生的维数灾难问题通常会影响传统算法的性能。维数灾难是指高维数据的估计需要的样本个数与维数构成指数增长的关系,但在实际应用中,通常样本点的数量较少而导致的高维数据空间的本征稀疏性。为了解决这一问题,维数约简通常作为数据预处理过程应用到数据分析以及机器学习的其它应用当中,以用来简化数据模型。维数约简是将高维数据转换为有意义的低维表达的一种变换,在很多领域当中都具有举足轻重的作用,如模式分类、高维数据可视化、数据压缩等等。通过降维方法可以将高维数据投影到一个低维空间,从而找出隐藏在高维观测数据中有意义的低维结构。在该低维子空间中进行分类或聚类可以得到更精确的结果,且计算代价大大降低。本文总结概括了各种常用的高维数据的降维方法及其分类。并且对这些方法进行了评估,指出存在的一些问题,提出了一种新的基于流形学习与子空间的降维方法( d r m s ) 。d i 洲s 利用l l e 算法保持同类的邻域几何结构不变,提取类间的判别特征,增大类间的距离,从而达到有效分类的目的。该方法寻求在描述高维数据集内在结构与高维数据集的可分性两种目标函数意义下的折中,将高维数据投影到一个最优的低维空间。本文将d r m s 算法应用到多模态生物认证系统中。选用了人脸图像和掌纹图像信息作为生物特征。选用了o r l 和f e r e t 人脸数据库以及p o l y u 掌纹数据库作为实验数据来源。通过进行大量的实验以及与其它降维方法进行对比,证明了d r m s 算法的有效性及鲁棒性。关键词:维数约简;维数灾难;子空间:流形学习a b s t r a c tt h ei m p r o v i n ga b i l i t i e so fd a t ac o l l e c t i o na n ds t o r a g ec a p a b i l i t i e sd u r i n gt h ep a s td e c a d e sh a v el e dt oa ni n f 6 n n a t i o no v e r l o a di nm o s ts c i e n t i f i cd o m a i n s t r a d i t i o n a la l g o r i t h m su s e di nm a c h i n el e a r n i n ga n dp a t t e r nr e c o g n i t i o na p p l i c a t i o n sa t eo f t e ns u s c e p t i b l et ot h ew e l l k n o w np r o b l e mo ft h ec u r s eo fd i m e n s i o n a l i t y ,w h i c hr e f e r st ot h ed e g r a d a t i o ni nt h ep e r f o r m a n c eo fag i v e nl e a r n i n ga l g o r i t h ma st h en u m b e ro ff e a t u r e si n c r e a s e s t od e a lw i t ht h i si s s u e ,d i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u e sa t eo f t e na p p l i e da sad a t ap r e 。p r o c e s s m gs t e po ra sp a r to ft h ed a t aa n a l y s i st os i m p l i f yt h ed a t am o d e l d i m e n s i o n a l i t yr e d u c t i o ni st h et r a n s f o r m a t i o no fh i g h - d i m e n s i o n a ld a t ai n t oam e a n i n g f u lr e p r e s e n t a t i o no fr e d u c e dd i m e n s i o n a l i t y i ti si m p o r t a n ti nm a n yd o m a i n s ,s i n c ei ta p p l i e dmc l a s s i f i c a t i o n v i s u a l i z a t i o n ,a n dc o m p r e s s i o n o fh i g h d i m e n s i o n a ld a t a w h e nt h es u i t a b l el o w d i m e n s i o n a ls u b s p a c ei si d e n t i f i e d ,w h i c hr e p r e s e n tf o rt h eo r i g i n a lh i g h 。d i m e n s i o n a ld a t as e tt h r o u g ht h ed i m e n s i o n a l i t yr e d u c t i o nt r a n s f o r m a t i o n ,t a s k ss u c ha sc l a s s i f i c a t i o no rc l u s t e r i n gc a no f t e ny i e l dm o r ea c c u r a t ea n dr e a d i l yi n t e r p r e t a b l er e s u l t s ,w h i l ec o m p u t a t i o n a lc o s t sm a ya l s ob es i g n i f i c a n t l yr e d u c e d t h ed i s s e r t a t i o np r e s e n t sar e v i e wa n dc o m p a r a t i v es t u d yo ft e c h n i q u e sf o rd i m e n s i o n a l i t yr e d u c t i o na tp r e s e n t w ea l s op o i n to u tt h ed i s a d v a n t a g eo ft h e s em e t h o d sa n dt h e np r o p o s ean o v e 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 db a s e do nm a n i f o l dl e a r n i n ga n ds u b s p a c e ,d r m s i tc a np r e s e r v ei n t r a c l a s sn e i g h b o r i n gg e o m e t r ys t r u c t u r ea n de x t r a c tb e t w e e n c l a s sr e l e v a n ts t r u c t u r e sf o rc l a s s i f i c a t i o ne f f e c t i v e l y t h ep r o p o s e dm e t h o di sa p p l i e dt om u l t i m o d eb i o m e t r i c sr e c o g n i t i o ns y s t e mw i t hf a c ea n dp a l mp f i n ti m a g e s t h em e t h o di se x a m i n e du s i n gt h eo r la n df e r e tf a c ed a t a b a s e sa n dp o l v up a l mp r i n td a t a b a s e e x p e r i m e n t a lr e s u l t ss h o wt h a td r m sc o n s i s t e n t l yo u t p e r f o r m so t h e rl 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 nm e t h o d sw h e nt h et r a i n i n gs a m p l es i z eo fp e rc l a s si ss m a l l t h i sd e m o n s t r a t e st h ee f f e c t i v e n e s sa n dr o b u s t n e s so fd r m s k e yw o r d s :d i m e n s i o n a l i t yr e d u c t i o n ;c u r s eo fd i m e n s i o n a l i t y ;s u b s p a c e ;m a n i f o l dl e a r n i n g独创性声明本人郑重声明:所提交的学位论文是本人在导师指导下独立进行研究工作所取得的成果。据我所知,除了特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体,均已在文中作了明确的说明。本声明的法律结果由本人承担。学位论文作者签名:同期:翌扛丛量一学位论文使用授权书本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定,即:东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版,允许论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技术信息研究所) 等数据库中,并以电子出版物形式出版发行和提供信息服务。( 保密的学位论文在解密后适用本授权书)学位论文作者签名:弛日期:迎扯丛学位论文作者毕业后去向:工作单位:通讯地址:指导教师签名:日期:电话:邮编:东北师范大学硕士学位论文第一章引言1 1 研究问题与背景随着科技的进步,人类早已步入信息时代。在科学研究领域,科学家们获得了大量丰富的数据信息,它向人们提供对客观对象更加丰富、细致的描述,但同时又给后续的数据处理工作带来极大的困难。在处理实际问题时,通常要对这些海量的高维数据进行处理,而这些海量数据之间往往存在着大量的冗余。如何对这些数据进行处理,找到数据之间的内在联系,从这些高维数据中找出事物的本质规律成为迫切需要解决的问题。在模式识别、机器学习领域,对于一个对象,经常使用一个向量来标志这个对象的各个属性,在实际使用时其维数往往很高。如在人脸图像识别时,将会使用一幅人脸图像的所有像素点,这将导致数据维数增至上万维甚至更高;在互联网信息检索时,一般对一个网页上常用词组进行词频统计,得到对此网页的描述,因此在实际应用中,经常会遇到高维的原始数据。直接在高维数据上寻找数据间的统计关系,会带来严重的计算问题;同时由于在实际使用中,通常样本点的数量较少,而对高维数据的估计需要的样本个数与维数构成指数增长的关系,这就是机器学习中的“维数灾难”( c u r s e o f d i m e n s i o n a l i t y )【l 】。然而,有意义的图像空间,它的本征维数是相对较低的,即高维图像数据存在相对低维的特征表达空间,这就意味着存在将高维图像进行低维转化的可能性。如何消除数据间的冗余,寻找数据间的内在联系,将数据映射到一个低维空间中去,以利于后续处理,是数据降维算法所要解决本质问题。维数约简是高维数据处理中非常重要的预处理步骤,是指样本从高维观测空间通过线性或非线性映射投影到一个低维空间,从而找出隐藏在高维观测数据中有意义的低维结构。它在很多领域当中都具有举足轻重的作用,如模式分类、高维数据可视化、数据压缩等等。通过降维方法可以将高维数据投影到一个低维空间,从而找出隐藏在高维观测数据中有意义的低维结构。在该低维子空间中进行分类或聚类可以得到更精确的结果,且计算代价大大降低。本文研究的问题为基于流形学习与子空间的降维方法及其在多模态生物认证领域中的应用。1 2 研究现状“维数灾难”问题最早是由b e l l m a n 于1 9 6 1 年提出的,当时指的是估计多变量函数所需的样本采样点数会随着变量个数的增加呈现指数增长的困难。现在一般指高维数据空间中所谓的空空间现象,即高维数据空间的本征稀疏性。维数约简方法是用来克服“维数灾难”和模型化高维数据的一种典型数据处理技术,是用来解决这一问题的有效手段之一。它可通过对离散数据集合的分析来寻求嵌入在高维数据空间中本征低维流形的不同样式,寻求事物的本质规律性。东北师范大学硕士学位论文根据数据降维采用投影函数的不同,目前已有的降维方法可以分为线性降维方法和非线性降维方法两类。线性降维方法主要包括主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s 。p c a ) 、独立成分分析( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ,i c a ) 、投影寻踪( p r o j e c t i o np u r s u i t ,p p ) 、因子分析( f a c t o ra n a l y s i s ,f a ) 、线性判别分析( l i n e a rd i s c r i m e n a n ta n a l y s i s ,l d a )等。在处理实际问题当中,这些方法具有简单性、易解释性、执行速度块、能够真实反应数据线性结构等优点,从而使得线性降维成为高维数据处理的一个主要研究方向。但就现实世界中所获得的真实数据集合而言,尤其是图像数据更多的是呈现出非线性的结构,甚至是高度非线性的结构。对于只考虑在高维数据空间中如何设计线性模型特征向量的线性降维方法而言,它们对于“高维数、非结构化”的图像数据经常不能得到较好的处理效果。近年来针对线性降维方法不能揭示数据非线性结构的问题,非线性降维方法成了数据降维领域的研究热点,各种非线性维数约简的理论与方法被提出。z h a n g 等人提出了一种可用于非线性流形学习的局部线性光滑方澍2 j ;r o w e i s 提出了局部线性嵌入方法i 引,并将其应用于脸谱图像数据和文档类数据处理中;m b e l k i n 和e n i y o g i 提出了l a p l a c i a ne i g e n m a p 方法,并在数字手写体识别中获得了良好的效剁4 j ;d o n o h o 和c a r r i eg r i m e s 通过对数据流形理论上的分析,提出了基于h e s s i a n 矩阵的局部线性嵌入方法,并说明这种方法可以看作是局部线性嵌入和l a p l a c i a ne i g e n m a p 方法的修j 下例。1 3 论文的主要内容维数约简是将高维数据转换为有意义的低维表达的一种变换。理想情况下,高维数据经过降维后能够降低至本征维数。本征维数指对任意的自然数d ,1 s d 刀,在所有的d 维子空间中,以数据互相关矩阵的前d 个特征向量所张成子空间,使得数据与它们在这个子空间的投影有最小的均方误差。我们可以说这d 个显著特征向量代表了数据几何体的信息,d 就是本征维数。数据降维问题是自然科学的基础,在很多领域中都有着重要的应用,如机器学习、模式分类、高维数据可视化、数据压缩等方面。本文对已有的各种高维数掘进行降维的方法进行总结和概括。降维方法从直观上来分析,都可以看作是对数据集合进行的一种保持其内在属性的变换,根据降维映射函数的特性,降维方法可以分为线性和非线性两类。并对现有的线性降维方法,如主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ,p c a ) 、线性判别分析( l i n e a rd i s c r i m e n a n ta n a l y s i s ,l d a )等算法进行介绍与评估。由于实际存在的很多问题都具有高度的非线性特点,线性方法对这些问题的处理无法取得较好的效果,导致很多非线性方法的提出。如基于神经网络的方法、基于核的方法、流形学习方法等。并重点讨论了流形学习的方法。针对流形学习的降维方法存在的一些问题,提出了一种基于流形学习与子空间的降维方法( d i m e n s i o n a l i t yr e d u c t i o nb a s e do nm a n i f o l dl e a r n i n ga n ds u b s p a c e ,d r m s ) ,将该方法应用到多模态生物认证领域中。本文将d i w s 方法应用到多模态生物认证领域中,进行了大量的实验,取得了较好2东北师范大学硕士学位论文的识别效果,并通过相关的对比实验说明了该方法的有效性及鲁棒性。文章的结尾总结了本文所做的工作并对数据降维技术的进一步发展进行了展望。1 4 论文的结构框架文章结构如下:第一章,阐述本文所研究的问题、选题的背景和研究现状,以及针对目日订降维方法中所遇到的主要问题,提出本文的研究内容。第二章,介绍维数约简的定义及其分类标准。并详细阐述了目前常用的数据降维方法以及结合经典理论的方法,并对相关算法的性能进行说明。第三章,对于目前新兴的流形学习的降维理论进行了系统介绍,以及目前使用较为广泛的一些基于流形学习的降维方法。并给出了非线性降维的统一框架。第四章,针对现有的降维方法所存在的一些问题,提出了一种基于流形学习与子空间的降维方法,及其在多模念生物认证领域中的应用。并通过在人脸数据库与掌纹数据库上的大量实验说明了本方法的有效性。第五章,对全文工作进行总结,提出对未来工作的展望。东北师范大学硕士学位论文第二章数据降维方法概述2 1 降维定义及其分类当所获得数据对某个特定目标来说过于稀疏,或者换句话说,在这个数据集合中,存在这太多对特定目标无用、甚至噪音的信息时,需要对这个数据集合作变换,以便浓缩这个数据集合,这个过程一般称为特征抽取。对机器学习( 或数据分析) ,这是一个不可缺少的步骤。其本质是根据目标要求,将稀疏的数据变换为稠密数据,在认知科学中就是数据到概念的归纳。特征抽取的本质可以理解为维数约简。维数约简是用来克服“维数灾难”和模型化高维数据的一种典型数据处理技术,是用来解决这一问题的有效手段之一。它可通过对离散数据集合的分析来探求嵌入在高维数据空间中本征低维流形的不同样式,寻求事物的本质规律性。维数约简通常应用到如下的方面:人脸识别系统:假设每幅图像的大小为m xn ,通过行堆叠的方式可将人脸图像转化为i n n 维向量。如果采用多层感知器的神经网络来进行分类,那么各层权重的数目将是非常大的,需要充分大的训练集合来避免过拟合,在实际应用当中这通常是不可行的。因此,我们需要进行降维处理。一种最为简单的解决方案是将图像直接缩小到一个可以接受的程度。显然,这么做会丢失丰富的细节信息。更合适的办法是通过主成分分析( p c a )的降维处理,将原始数据维数降低,从而可大大简化识别或分类的过程,提高处理的精度。多元统计分析:数据分析者感兴趣的是寻找数据集合所具有的类及其结构,或是解释变量的具体意义。为了达到这一目的,经常采用的一种简单的方式是将数据集合可视化,即在尽可能保持数据集信息的前提之下,将数据集合转化为2 或3 维的数据集合,充分利用人的直观洞察力来获得预期的效果,使得可轻易的进行数据的分类、识别处理。基于有限采样的多变量函数估计:我们可以通过减少变量的数目( 即数据维数) 来极大的减少估计多变量函数所需的采样点数目,这将会大大减少计算量、提高估计精度。上面关于数据处理的些典型场合表明,将数据的维数降低到合适的大小,同时尽可能多的保留原始数据集的信息,然后将降维后的数据送入数据处理系统,在多数情况下,经常是有用的甚至是必须的。2 1 - 1 降维的定义若以) 竺。cr d 为d 维空阈中的一个容量为n 的数据集合,假设其来自于( 或近似来自于) 维数为d ( d ) 的某数据流形的采样。我们处理的目标是寻求数据流形合适的低维坐标描述,将原始数据集合投影到低维空间,获得原始数据集的低维简洁表示。此时,4东北师范大学硕士学位论文降维问题通常由下列部分组成:( 1 ) 高维数据空间通常为r d 的某一个子集;( 2 ) 降维空间( 或称低维表示空间) ,通常为的某一个子集;( 3 ) 降维映射,f :q d q 4工啼y :尸( j ) ,( 2 1 )称y 为x 的降维表示。( 4 ) 重构映射f - 1 ( 此步骤为非必须) ,f 1 :q 4 _ q dy _ 工:f - l ( y ) ,( 2 2 )满足下面的一些限制:( 1 ) d d ,并且在不损失原数据信息的基础之上,尽可能的小;( 2 ) 流形s 垒f 一( ) ,近似含有全部的采样点,即k ) c s ,或从另一角度重新描述为重构误差尽可能的小。重构误差定义为:e d ,( ) ) 垒从矗,矗) 幸会f 一( f ( _ ) ) ,( 2 3 )。,- l其中烈,) 为中的距离测度,如中的欧式距离等。2 1 2 降维方法的分类降维方法通过构造降维映射,获得高维数据的低维表示方法。根据降维映射形式的不同,可以对降维方法做线性和非线性的划分。设也如亡r 。是d 维空间中容量为n 的数据集合,通过降维映射:f ( x 、=f 1 ( x j )( x 2 )尼( 毛)f l ( x n l ,五2 ,而d )e ( 而l ,如,j r 2 d )尼( t ,2 ,)( 2 4 )得到低维空间中的向量,= ( y 。,炊,船) 7 。若f 的每个分量e 都是x 的线性函数,则称f 为线性降维;否则称为非线性降维。线性降维方法有主成分分析方法( p r i n c i p l ec o m p o n e n ta n a l y s i s ,p c a ) 、线性判别分析( l i n e a rd i s c r i m i n a n ta n a l y s i s ,l d a ) 等,这一类方法适用于处理线性的数据结构,思想简单直观、计算方便,是大量使用的降维方法,但它们对于处理非线性程度较高的问题效果不好。非线性问题的复杂性给分析数据带来了很多处理线性结构时所不曾遇到的困难,因此迫切需要研究适用于处理高维非线性结构的降维方法。能够实现非线性降维的方法包括基于神经网络的方法、基于核的算法、流形学习方法如等距映射算法( i s o m e t r i cs东北师范大学硕士学位论文f e a t u r em a p p i n g ,i s o m a p ) 、局部线性嵌入算法( l o c a ll i n e a re m b e d d i n g ,l l e ) ,拉普拉斯特征映射( l a p l a c i a ne i g e n m a p ) 等,这类方法适用于处理高度非线性的结构,计算比较复杂。下一节我们对一些常用的降维方法进行介绍和分析。2 2 线性降维方法线性降维方法作为降维方法中最广泛使用的类,具有许多优良的特性,如计算简便、计算速度快、经常具有解析解、对具有线性结构的数据集合非常有效、便于解释等。线性降维方法实际是在不同优化准则之下,寻求最佳线性模型的方法,这是线性降维方法的共性,也是与非线性降维方法的根本差异之所在,抓住了这一点有助于更好的理解线性降维的本质。2 2 1 主成分分析主成分分析( p r i n c i p a lc o m p o n e n t a n a l y s i s p c a ) 是由1 9 0 1 年p e a r s o n 在研究回归分析时附带提出的,1 9 3 3 年h o t e l l i n g 将这个概念推广到随即变量。随着模式识别、机器学习等领域的兴起与发展,它又成为这些领域韵重要研究对象之一。p c a 是一种在数据处理、压缩和可视化中使用最广泛的线性降维技术f 6 1 。它的基本思想是在最d , - 乘意义下,寻找最能够代表原始数据的投影方法。在不同领域,它对应这众所周知的奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ,s v d ) ,k a r h u n e n l o e v e 变换p 1 。设初始数据集为 z 池cr d ,低维空间中的投影为 r 墨cr 。,其中d d 。本质上来说,p c a 是在满足方差最大的前提下,寻找一系列正交的关于初始变量的线性组合,称为主成分。主成分的个数与初始变量个数一致。对大多数数据集来讲,前几个最大的主成分能够解释几乎所有的方差,这样余下的主成分在满足最小信息损失的前提下被丢弃。基本思想如图2 1 ,( a ) 和( b ) 分别为p c a 把二维坐标下的点投影到一维和二维直线上的情况。1 2( a )( b )图2 1p c a 方法示意图对原始数据集,均值牙= 专喜置,协方差矩阵岛= 万1 ( x i ) ( 置一而7 。采用谱分解的理论,可以重新写成:6东北师范大学硕士学位论文碟= u 。a u( 2 5 )其中,人= a i 口g ( 8 ,k ) 为对角矩阵,特征值按从大到小排列乙b ,u = ( ,l f :,) ,蚱为九对应的特征向量,满足u 7 u = i d 。d ( 单位矩阵) 。那么数据集合 五) 墨。的主成分变换为:】:= 以( 置一x ) ,扣l ,2 ,= ( ,”:,蚴)( 2 6 )根据不同的选取规则,可以进一步选取合适的投影,减少l = 的维数,如采用方差准则,即对于选定的d ,选取投影矩阵亿,使r 的方差,毋譬。 州专善r r 7 】 2 善( 2 7 )达到最小。前d 个主成分所占总方差的比率为加似)( 2 8 )在给定比率下,可以通过式( 2 8 ) 确定合适的d 值。这种方法的缺点是总体离散度的最大化不仅要求类与类之间离散度的增大,而且要求类内离散度的增大,因此对于分类目的来说,这是一个障碍。由此可知,p c a 投影是由投影后特征恢复原特征的最优化解,但从分类的角度上说,p c a 并不是最佳的投影选择。由于p c a 的线性局限性,对具有非线性结构的数据集映射效果不好。2 2 2 线性判别分析虽然p c a 方法对于代表数据样本非常有效,但是并没有理由表明主成分对区分不同的类别有什么大作用。如果把所有类别的样本都放在一起,则被p c a 方法抛弃的那些分布方向有可能j 下是能够把不同的类别区分开来的分布方向。也就是说,p c a 方法寻找的是用来有效表示的主轴方向,而判别分析方法( d i s c r i m i n a n ta n a l y s i s ) 寻找的是用来有效分类的方向。线性判别分析( l i n e a rd i s c r i m i n a n t a n a l y s i s ,l d a ) 8 】也是一个用于特征提取的统计方法。由于l d a 的思想是通过寻找最优的投影方向,使得所有样本在其上的投影的类间离散度和类内离散度之比为最大,从而达到最好地区分不同类样本的目的。因此,从理论上说l d a 比p c a 更适合于模式识别问题。经典的线性判别分析中使用的是f i s h e r 准则函数,所以线性判别分析又被称为f i s h e r 线性判别分析( f i s h e rl d a ) ,f i s h e r 准则函数的定义为删) = a r g 咿嬲( 2 9 )其中,墨,& 分别为训练样本的总的类间散布矩阵和总的类内散布矩阵。式( 2 9 ) 中的了( 形)是广义的r a y l e i g h 熵,可以用l a g r a n g e 乘子法求解,令分母等于非零常数,即令w7 s 。m = cs o ,定义l a g r a n g e 函数为:7东北师范大学硕士学位论文r ( w ,九) = w7 s , w x ( w s 。形一c )( 2 1 0 )式中的a 为l a n g r a n g e 乘子。将式( 2 1 0 ) g 寸求偏导,得:掣= 嚣蹦妒( 2 1 1 )令其偏导数为零,得:s b w - x s w 簟= 0( 2 1 2 )即:嚣= 兄茂事( 2 1 3 1其中事即为仰) 取得最大值时的。在咒非奇异的时候,式( 2 1 3 ) 两边乘以或一可得茂一s b w * = a , w ( 2 1 4 )求解式( 2 1 4 ) 即为求解一般矩阵咒。1 最的特征值问题。综上所述,当况非奇异时,在数学上,求解函数( 2 9 ) 就等同于求解或一疋的特征值问题。使朋) 最大的变换矩阵是由j 1 疋的前朋个最大特征值所对应的特征向量组成的。线性判别分析又称作f i s h e r 线性分析( f i s h e rl i n e a ra n a l y s i s ) ,是一种有监督的降维方法。与p c a 相比,l d a 更关注降维后的分类效果,而p c a , 贝i 是寻找在最小化均方误差下的投影方向。l d a 在机器视觉领域,尤其是在人脸识别领域取得了巨大的成功。在b e l h u m e u r 等人将其运用到人脸识别领域后旧3 ,人脸的识别率从原来的7 0 进一步提高到9 0 左右。l d a 的计算过程中,要求解广义r a y l e i g h 熵问题。由于求解过程中存在矩阵求逆的问题,要求协方差矩阵瓦是满秩的,这给高维数据的处理带来了巨大的挑战。在特征空间中高维数的情况下,由于训练样本较少导致的小样本数据集在计算类内协方差时会产生较大偏差,而且类内协方差阵多为病态的。实际应用当中,通常训练样本数量较少,“小样本”问题使得内散布矩阵咒是奇异的,导致无法求解。针对咒不可逆的问题,许多学者提出了非常多的方法以解决这一问题。2 3 非线性降维方法人们对世界的感知是通过处理大量的感觉器官的输入信息而形成的,这些信息包括图像像素点的亮度,声音的功率谱等等。虽然这种形式的复杂刺激可以简单的用高维空间中的点来表示,但是它们通常都有更加紧致的描述,即高维数据存在可能的低维表示。事物结构的连续性导致了输入之间有很强的相关性( 例如图像相邻的像素之间) ,因而观察值实际上位于一个低维的光滑流形上。对这种非线性流形进行建模对与将这些观察进行比较和分类,进而研究客观世界起着至关重要的作用。致力于探索性数据分析或是东北师范大学硕士学位论文多元数据可视化的研究人员也面临同样的降维问题。主成分分析和其他一些线性降维方法作为经典的降维方法,易于实现,算法高效,能够找出位于高维输入向量空间的一个线性子空间上数据的线性结构。然而许多数据集合本质上含有用线性降维方法不能发现的非线性结构,因而需要用非线性的降维方法来进行处理。近些年,越来越多的人对非线性降维的研究产生兴趣。这导致了各种新的能用来处理复杂高维数据的非线性方法的提出,并且,这些方法显示了比传统线性方法在处理数据上的优越性。非线性维数约简方法可分为三类:基于神经网络的方法、基于核的方法和流形学习方法。这一节简单介绍一下基于神经网络的方法以及基于核的方法,流形学习方法将在下一章介绍。2 3 1 基于神经网络的方法神经网络通常用来建模输入向量集之间的关系。在基于神经网络的降维方法中,比较经典的是自动编码网络( a u t o - e n c o d e rn e t w o r k s ) 和自组织特征映射( s e l fo r g a n i z i n gm a p p i n g ) 。自动编码神经网络【1 0 】是一种前向反馈网络,它用来寻找数据的非线性特征并能实现数据的良好重建。网络中包含神经元数量最少的那一层被称为瓶颈。该网络把高维空间的输入向量映射到用瓶颈层的激励所表示的低维空间中,而瓶颈层的下一层再把瓶颈层中的低维表示映射回高维空间。自组织映射网络( s e l f - o r g a n i z i n gm a p ,s o m ) 3 扩畏t k - m e a n s 算法。与舡m e a n s 不同的是,在s o m 中,每个聚类都被赋予一个在隐含空间( 降维后的空间) 中的固定位置,并基于它们在隐含空间中的位置用一个邻居函数来评价聚类之间的近似度。其中,邻居函数的值越大,就意味着聚类之间的接近程度越高。很明显,将数据映射到隐含空间的过程就是降维的过程。根据算法求得的邻居函数值,高维数据点将被映射到最优聚类的位置,从而实现高维数据的降维。基于神经网路的降维方法缺点是计算相对复杂,需要多次循环迭代求解,因此在应用上受到一定限制。2 3 2 基于核的方法核函数【l2 】的思想在模式识别中是一个非常大胆的想法,面对高维非线性数据的挑战,核函数的发明者不是像以往那样去降维,而是通过升维将一个非线性的假设空间升到更高维甚至是无穷维的空间中去。对于一个高维向量x ,我们通过映射将输入空间x映射到一个新的空间中f 去,f 又被称为特征空间。我们所需要做的不是显式的构造映射,使用核技巧只需要知道在特征空间的内积k 即可,这里的k 就是核函数。基于核的降维方法的缺点是需要人工选择一个合适的核函数和相关参数。并不是每个核函数对于每一种数据都适用,在实际的应用中往往是经验的选择某种核函数,因此9东北师范大学硕士学位论文使得核函数方法在实际应用中受到一定限制。除上述方法外,还有一些新兴的方法,如基于分形的降维方法。如果一个数据集在所有的观察尺度下均具有自相似性,即一个数据集的部分分布有着与整体分布相似的结构或属性,称该数据集是分形的。与分形相对应的,分形维则体现了数据集的固有特征。采用分形的思想,可以首先较准确地估计出数据的本征维数,从而为进一步的降维提供指导性的参考。与其他方法对本征维的估计所不同的是,基于分形的方法能得到非整数值的本征维,即通常所说的分数维。关于分数维的定义,也有多种不同的描述,其中应用较广泛的则是计盒维( b o x c o u n t i n gd i m e n s i o n ) 和相关维( c o 仃e l a t i o nd i m e n s i o n ) u3 l 。基于对这些相应维的估计,产生了一系列不同的方法,它们均为降维处理奠定了良好的基础。2 4 本章小结本章介绍了数据降维的定义以及在处理实际数据过程中的必要性、可行性。数据降维的应用非常广泛,例如:人脸识别、多元统计分析、基于有限采样的多变量函数估计等领域。将已有的各种高维数据处理方法进行总结和概括并对已有的降维方法进行分类。降维方法从直观上来分析,都可以看作是对数据集合进行的一种保持其内在属性的变换,根据降维映射函数的特性,降维方法可以分为线性和非线性两类。本章详细介绍了一些常用的线性降维方法,并对其算法性能进行了评估。由于实际存在的很多问题都具有高度非线性的特点,使得非线性降维的产生变得尤为必要。本章简单介绍了基于神经网络的方法、基于核的方法等非线性降维方法。关于流形学习方法我们将在下一章做详细介绍。1 0东北师范大学硕士学位论文第三章流形学习随着计算能力的同益增强和存储容量的增长,大规模的数据的获取较以往更为简单和普遍,同时也产生了很多新的问题。在大多数的实际应用当中,如计算生物学、图像分析和计算机视觉、信息检索的文本分析、文本挖掘和生物特征认证等,获得的数据都是高维的。这种高维性质一方面导致了维数灾难的出现,另一方面是不能被人的感知能力直接理解及发现数据集内在的规律。因此,有必要对高维数据采用某种维数约简方法进行降维处理。传统的维数约简方法如主成分分析、独立分量分析和因子分析在高维数据集具有线性结构和高斯分布时能够取得较好的效果。但当数据集在高维空间呈现高度扭曲时,这些方法则难以发现嵌入在数据集中的非线性结构和恢复内在的结构。如何学习隐藏在一组高维数据集中的内在低维结构和重构就成为研究流形学习的动机之一。在计算机科学中,探索数据集流形结构可以追溯至图像识别的研究1 1 4 , 1 5j 。而近年来流形学习( m a n i f o l dl e a r n i n g ) 的研究受越来越受到机器学习和其他领域研究人员的广泛关注,这与2 0 0 0 年在s c i e n c e 上发表的三篇论文有密切关系【1 6 , 3 , 1 7 】。其原因是这几篇论文从认知的角度探讨了神经系统与嵌入在高维数据集中的低维的认知概念之间的联系,并从算法的层面部分验证了高维数据集的内在结构。同时,提出的算法简单、有效并无局部极小的缺陷。3 。1 相关概念一个流形简单说就是一个拓扑空间,它在局部上是欧氏的。流形学习一般是指一类无监督统计学习的问题,其主要目标是寻找嵌入在高维观测数据空间的低维光滑流形,发现高维数据中我们所不能直接观测到的结构信息,如流形的内在维数。因此,我们希望获得的低维嵌入能够保持这些信息,如保持胚形不变,保持度量或者角度。为了解决这一问题,常见的方法有:标架对齐、图嵌入、概率模型、泛函核空间。研究内容主要包括保留或突出原始数据特定特征的有限数据集的降维;服从某种分布的高维有限样本点的密度估计问题;由少量潜在因素影响的高维观测数据的隐变量模型建立以及流形内在维数的估计问题等。3 1 1 流形把流形定义成一个拓扑空间m ,并满足以下性质:如果脚m ,则存在工的邻域u 以及整数d 0 ,使得u 同胚于欧式空间。根据以上定义,用欧式空间中通常意义下的度量( 即欧式距离) 可以定义开球,而任意开球和欧式空间本身同胚,因此本身是个流形。i i 东北师范大学硕士学位论文3 1 2 嵌入如果一个可微映射的秩,也就是其定义域m 的维数是d ,且d m ,则映射f :m 。卜n 4 称为浸入,浸入是一个局部一一映射。如果一个一一的浸入,:p hm 是一个满射,且为同胚,那么这个浸入也被称为一个嵌入。一个被浸入的子流形m ,c m 被称为一个m 的c 。的子流形,如果包含映射i :m ,h m是一个嵌入。3 1 3 流形学习流形学习问题的数学描述:假设m 为嵌入在d 维欧式空间中的d 维参数化流形,d d ,厂:mcr 。一r d ,其中m 为上的紧致连续开子集。对于给定的高维观测数据集x = ( 五,x 2 ,h ) ,其中而r d ,服从某种潜在分布p 。玉= 八只) + 毛;f = 1 , 2 ,。这里,r = ( m ,儿,蜘) ,其中,咒r 。,t 表示独立噪声。流形学习的目标是根据观测数据集x 重构未知函数厂( ) 和y 对于任意的儿mcr 一可以( 只) 用估计薯。流形学习问题是一种病态的逆问题,如果要发现隐变量 ,和观测变量x 的联系,就必须对,( ) 加上一些限制条件。如i s o m a p 中把厂( ) 限制为黎曼几何意义上的等距映射,最近有文献提出把厂( ) 限制为保形映射引。3 2 流形学习综述“流形学习”要解决的问题其中包括:有效描述具有嵌入流形结构的数据集的相关性和发现数据集的内在规律。流形学习假定数据集在未知但存在的低维内在变量作用下,在观测空间会形成高维流形。这一问题具有普遍性,在图像、语音、文本中都存在这一现象。研究流形学习的工作可以追溯至1 9 8 5 年,由s t a n f o r d 大学的h a s t i e 在一份技术报告中提出,其目的是希望找到通过相关数据集的“中间”结构,即一维主曲线和二维主曲面 1 9 , 2 0 l 。早在这一方面的应用性研究主要通过限制某些控制变量,通过线性主成分的分析方法来实现内在维数的发现,如1 9 9 5 年n a y a r 在机器人视觉中采用的子空间方法【1 4 】和o m o h u n d r o 提出的流形学习 1 5 1 。然而,采用线性方法必然要忽略非线性数据集存在的凸性和凹性,因此,在获得一个更有效的分类系统之前,必须找到一种更合理的方法来恢复高维非线性数据集的内在主要结构和主要物理特征。目前,流形学习的研究在国际上已经受到广泛的重视。依赖对目标函数的不同定义,将流形学习分成四个主要范畴:投影法、生成式模型、谱方法和互信息【2 。( 1 ) 投影法假定具有流形的数据集属性间相互耦合,因而可以通过寻找数据集“中间”的曲面,即主流形来描述数据集具有的内在结构。这种方法采用投影和期望方法迭代计算主流形,在概率意义下满足自相合特性,即主流形上的点是投影至该点的全体数据的1 2东北师范大学硕士学位论文期望的平均。这一领域最初的研究是1 9 8 4 年由h a s t i e 提出的主曲线l l 引,随后为纠j 下h a s t i e主曲线算法中存在的模型偏差,t i b s h i r a n i 提出了概率主曲线,在考虑了主曲线的复杂性问题后,又出现了k 主曲线理论。尽管在几何上直观,但投影法的主要缺陷是:采用弧长作为全局变量来描述数据集的整体几何结构要推广至高维空间是困难的。( 2 ) 生成式模型假定数据集是由内在的等间距的低维隐节点生成,通过迭代方法可以建模内在空间与观测空间( 如图像、文本、语音等) 的映射关系。在这一领域的进展包括b i s h o p 最初提出的生成式拓扑映射、基于主曲线的自相合思想后改进的概率主曲面以及采用统计学习理论的正则化思想的正则主流形【2 2 1 。但这一方法存在着一定的缺陷,由于生成式模型普遍采用t e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 方法,生成式模型容易陷入局部极小,且存在收敛性问题。( 3 ) 谱方法的目的是基于流形结构的主要谱特征来近似描述高维流形的内在主要结构。这一方法的研究包括i s o m a p 算法6 1 、保角映射算法【2 3 1 、局部线性嵌入算法【3 1 和拉普拉斯特征映射【2 4 1 等。t e n e b a u m 于2 0 0 0 年在s c i e n c e 上提出了i s o m a p ( i s o m e t r i c a lm a p p i n g )算法,研究了图模型意义下的观测空间数据集与内在低维空间测地线距离之间的关系,随后s
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026及未来5年民用厢式车项目可行性研究报告(市场调查与数据分析)
- 2026事业单位工勤技能-广西-广西经济岗位工一级(高级技师)历年参考题库含答案详解
- 2026事业单位工勤技能-广东-广东中式面点师四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-山西-山西水工监测工四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-山西-山西下水道养护工三级(高级工)历年参考题库含答案详解
- 2026事业单位工勤技能-山东-山东水利机械运行维护工一级(高级技师)历年参考题库含答案详解
- 2026事业单位工勤技能-山东-山东园林绿化工二级(技师)历年参考题库含答案详解
- 2026事业单位工勤技能-安徽-安徽无损探伤工三级(高级工)历年参考题库含答案详解
- 2026年三年级英语上册第三次月考达标测试卷(人教PEP版)(含答案含听力材料、听力音频)
- 2026年汽车驾驶员中级工理论试题
- 抖音直播运营中心薪酬绩效考核实施管理方案
- 2026年学生入团考试题库及参考答案
- 2027届河南省部分城市联考高三上学期11月阶段检测历史试题(含答案)
- 2026年宁夏水务投资集团有限公司招聘笔试参考题库附带答案详解析版
- 2026秋北师大版选择性必修第一册Unit 1-3 句子语法填空练习(备考期中)
- 智能体电脑行业王伟东白皮书
- 秦皇岛市建设现代有轨电车项目调研报告
- 2026秋新教材苏教版五年级上册数学第七单元 用字母表示数量关系(一) 教案(共7课时)
- 《中药炮制技术》教案-13模块十三 其他炮制技术
- 2026年辅警笔试的题库及答案
- 多模式镇痛在加速康复外科中的应用现状
评论
0/150
提交评论