（信号与信息处理专业论文）基于全局统计与局部几何性质的数据降维算法研究.pdf

摘要 摘要 在机器学习和数据挖掘等领域的许多实际问题中，如人脸识别，数字图像 识别和数据可视化等，都需要面临高维数据的分析和处理。高维数据不仅会增 加算法的计算负担，而且由于包含大量的冗余信息会掩盖数据的内在真实结构， 给学习和分析任务带来很大的困难。数据降维技术是解决这一问题的有效手段， 它不仅可以挖掘出数据的本质结构，而且能够以较少的计算代价帮助完成既定 的学习任务。因此，针对数据降维技术的研究一直以来都是相关领域研究的重 点课题。 本论文重点研究针对高维数据的降维理论与方法以及在人脸识别领域中的 具体应用。论文的主要研究内容和创新成果如下： 1 从基于全局统计和基于局部几何性质的角度总结了已有数据降维算法 的各自特点和优势，分析了各种算法的本质和内在联系。 2 经典的p c a 和k p c a 算法都是在最小平方意义下进行建模的，其求解 缺乏足够的稳健性。数据中即使掺杂了少量的离群样本也会使得它们求 解的主分量方向产生很大偏倚。本文针对这一问题提出了种稳健的非 线性降维算法i r o b u s tk p c a 。该算法通过隐式的方式辨别并抑制数据 中的离群样本，能够学习出准确的非线性子空间。由于采用了迭代的方 式更新计算，算法还具有潜在的增量学习的优势。与标准k p c a 算法 的对比实验结果表明了该算法的有效性和稳健性。 3 基于局部保持的思想，提出了一种针对高维数据的流形学习和模式分类 的监督降维算法s m d a 。经典的l d a 算法仅考虑了样本的全局统计信 息，不适用于非线性分布的数据。而基于局部几何性质的流形学习算法 在解释数据的内在结构方面具有明显的优势。因此，本文基于局部分析 的思想提出了s m d a 算法。该算法试图在保持数据局部性质的同时最 大化各类别之间的间隔，能够获得良好的判别性能。并且由于采用了优 化的邻域选择机制，s m d a 能够避免已有方法在刻画数据局部几何结 构时所面临的一些问题。在y a l e 和u m i s t 人脸数据库上的实验结果表 明了该算法的有效性以及相对于主流的p c a 、l d a 、l p p 和m f a 算法 的优越性。 4 基于流形正则化的思想，提出了一种可用于多类问题半监督学习算法 i 摘要 m l a p r l s 。m l 印i 也s 算法采用多变量回归模型用于分类问题，并且构 建了所有样本的近邻图来估计整个数据空间的几何结构，作为回归目标 的正则化项。在该算法中，无标签样本的作用就是协助估计数据空间的 局部几何结构，帮助获得更为有效的判别向量。在e x t e n d e dy 葡e b 和 p i e 人脸数据库上的实验结果表明了该算法的有效性。 关键词：数据降维流形学习 半监督学习人脸识别 a b s t r a c t a b s t r a c t m a n yp a t t e mr e c o g n 纯o na n dd a _ c am 越n gp r o b l e m s ，s u c ha sf a c er e c o g 血i o n ， d i g i t a li m a g er e c o g n i t i o n 觚dd a t av i s u a l i z a t i o n ， i n v o l v ed a t ai i l v e 巧l l i 曲 d i m e n s i o n a ls p a c e s 1 1 1 eh i g hf e 舭ed i m e n s i o n a l 毋o fd a t an o to n l yb u r d e n st h e c o n l p u t a t i o n a lr e q u i r e m e n to fa l g o r i t h m s ，b u ta l s oc a n t a i n sr e d u n d a n c ya n do b s c u r e s t h ei n t r i n s i cs t r u c t u r e so fd a t a d i n l e n s i o n a l 时r e d u c t i o ni sa ne 肫c t i v ct o o lt od e a l w i t ht l l i sp r o b l e m ，w h i c hc a nh e l pt op r o b ei n t ot l l ee s s e n t i a ls t m c t u r eo ft h ei n p u t d a t aa 1 1 dc o n t r i b u t e st oa c c o m p l i s hd e s i r e dl e 咖i n gt a s k sa tl o wc o m p u t a t i o n a lc o s t a sar e s u l t ，m er e s e a r c ho nd i m e n s i o n a l i 够r e d u c t i o nh a sa l w a y sb e e ni i n p o i r t a n ti n r e l a t e ds c i e n t i f l cf i e l d s t h i st h e s i sf o c u s e so nt h et 1 1 e 嘶e sa 1 1 dm e t h o d so fd i m e n s i o n a l 姆r e d u c t i o nf o r h i g hd i m e n s i o n a ld a t a ，a sw e l la sr e l a t e da p p l i c a t i o n si nf a c er e c o g l l i t i o n t h em a i n c o m e n t sa n da c h i e v e m e n t sa r ea sf o l l o w s ： 1 t h ec h a r a c t e r i s t i c sa n da d v a i l t a g e so fe x i s t i n gd i m e n s i o n a l i 够r e d u c t i o n a l g o r i t h m sa r es u m m a r i z e d 矗o mg l o b a ls t a t i s t i c - b a s e da r l dl o c a lg e o m e n y b a s e dp e r s p e c t i v e s t h ei n t e m a lr e l a t i o n so fv 撕o u sa l g o r i t h m sa r ea l s o a n a l y z e d 2 b o mt h ec l a s s i c a lp c aa n dk p c a a l g o r i t l l i l l s ，i n 叩1 e m e n t e di nt 1 1 es e n s eo f l e a s tm e a ns 小l a r e de r r o r ，h a v em ed e f i c i e n c yo fi n s t a b i l i t ) ，w h e ni n p u td a t a a r es p o i l e d b yo u t l i e r s a n de v e ns m a l l 锄o u n to f0 u t l i e r sw i l lo b v i o u s l y d e t e r i o r a t em ep e r f o m l a n c eo fs t a j l d a r dp c aa j l dk p c aa l g o r i t h m s t o d e a lw i t hm i sp r o b l e m ，w ep r o p o s ean e wr o b u s tn o n l i n e a rp r i n c i p a l c o m p o n e n ta n a l y s i st e c 王l i q u e c a i l e di r o b u s tk p c a n ea l g o r i t h mc a n e f r e c t i v e l ye l i l 证n a t et h ee a e c to fo u t l i e r s ，a i l dp r o d u c ea n a c c u r a t e n o n l i n e a rs u b s p a c e i na d d i t i o n ，i r - o b u s tk p c ac o m p u t e si t e r a t i v e l ya n d s h o w s 也ep o t e n t i a lo fe x p a i l s i b i l i t yt ot h ei n c r e r n e n t a l l e a r i l i n gv e r s i o n t h ec o m p a r a t i v ee x p e r i m e n t a lr e s u l t sw i t hs t a n d a r dk c i ) ad e m o n s t r a t et l l e e 虢c t i v e n e s sa n dr o b u s t n e s so fi i b b u s tk p c a 3 f o c u s i n go nm ed i m e n s i o n a l i 够r e d u c t i o nf o rm a n i f o l d1 e a m i l 玛a n dp a t t e m c l a s s i f i c a t i o no nm g h d 血e n s i o n a jd a t a ，、v ep r o p o s ean e ws u p e r v i s e d d i m e n s i o n a l i t yr e d u c t i o na l g o r i t h m t h ec l a s s i c ml d a m e t h o dc o n s i d e r s o n i yt h eg l o b a ls t a t i s t i c a 王i n 最) 玎n a t i o no fs 锄p l e sa n dt e n d st o f a i li n t h a b s t r a l c t d e a l i n gw i n ln o n l m e a rd i s 仕i b u t e dd a ：t a w h i l et h em a l l i f o l dl e 锄i n g a l g o r i t h m sh a v es h o w ng r e a tp o w e ri nd i s c o v e r i n gt h ei n t r i n s i cs t r u c n 鹏s o fh i g hd i m e n s i o n a ld a t a t h e r e f o r e ，w eu t i l i z e dt l l el o c a l i 够p r e s e r v i n gi d e a a n dd e v e l o p e dan e wa l g o r i t l l 董nc a l l e ds u b - m a l l i f o l dd i s c r i m i 觚ta n a l y s i s ( s m d a ) s m d af l n d st h el o w - d i m e n s i o n a le m b e d d i n g so f l ei n p u td a t a b ym a x i m i z i n gt h es u b m a n i f o l dm a 唱i nw h i l em a i n t a i l l i n gm en e i g h b o r i n g r e l a t i o n so fs 锄p l e s i na d d i t i o n ，a no p t i r n i z e dp r o c e s so fi n 打i n s i cs 仃u c t u r e d i s c o v e 巧i sa d o p t e dt 0a v o i dt h el i r n j 协i o n so fe x i s t i n gl o c a l i 够p r e s e r v i n g b a s e dm e t h o d s t h ee x p e r i m e n t a lr e s u l t so ny a l ea 芏l du m i s tf a c e d a t a b a s e sd o m e n s t r a t et l l ee 仃e c t i v e n e s so fs m d aa n d 乱s u p i o r i 够t 0 p o p u l a rp c a ，l d a ，l p p a n dm i 狐a l g o r i l m s 4 c o n s i d e r i n gt h es e m i s u p e r v i s e dl e a r 】= l i n g f a m e 、o r kb a l s e do nm a i l i f o l d r e g u l 砒【a t i o n ，w ep r o p o s eam e t h o dc a l l e dm l a p r l s i nm l a p r l s ，a n e a r e s tn e i 曲b o rg r 印hi sc o n s t r u c t e df i r s t l yt oi n o d e lt l l ei n t r i n s i c g e o m e t r i c a ls t r u c t u r eo ft l l ed a 协s p a c e ，a n dt h e nm e 舒印hs t r u c t l e i s i n c o i p o r a l e di n t 0 m eo b j e c t i v e 如n c t i o no ft h em u l t i v a r ia _ t el i n e a r r e 盯e s s i o na sar e g u l a r i z a t i o nt e m l a i m i n gt oe x t r a c te a e c t i v ef e a t u r e sf o r t h es e n l i s u p e r v i s e dm u l t i c l a s sp r o b l e m ，m l a p r l sc a l lm a k eu s eo fa l l l i 觚t e dl a b e l e ds 锄p l e sa n dl a r g e 觚【o u n to fu i l i a b e l e ds 锄p l e s 1 h e e x p e r i m e n t a l r e s u l t so ne x t e n d e dy a l e ba n dp i ef i ed a t a b a s e s d o m e n s t r a t em ee 疏c t i v e n e s so fm l a p r l s k e yw o r d s ：d i m e n s i o n a l i 锣r e d u c t i o n ，m a l l i f o l d1 e a m i n g ，s e m i s u p e r v i s e dl e 锄i n g ， f a c er e c o g n i t i o n 插图 插图 图2 1d f f s 与d i f s 1 9 图2 2p c a 与i c a 2 l 图2 3p c a 与l d a 2 3 图2 4e 堙e n f a c e s 和f i s h e r f a c e s 2 5 图3 1 标准k p c a 在a 数据集上的结果4 3 图3 2i k p c a 在a 数据集上的结果4 3 图3 3i r o b u s tk p c a 在a 数据集上的结果4 4 图3 4k cp ：a 和i r o b u s tk p c a 在a 数据集上的特征值对比4 4 图3 5 标准k p c a 在b 数据集上的结果4 5 图3 6i k p c a 在b 数据集上的结果4 5 图3 7i r o b u s tk p c a 在b 数据集上的结果4 6 图4 1 欧氏距离( e u c l i d e 肌d i s t a n c e ) 与测地线距离( g e o d e s i cd i s t a n c e ) 4 9 图4 2l l e 算法计算步骤5 2 图4 3 图嵌入及其线性化、核化、张量化降维统一框架6 l 图4 4 数据采样不均匀时，采用欧氏距离和c a m 加权距离进行邻域选择效果对比6 4 图4 5 边缘点( m a 曙i n a lp o i n t s ) 示意图6 9 图4 6y a l e 人脸数据库图像示例7 2 图4 。7 在y a l e 人脸数据库上的实验性能对比7 2 图4 8u m i s t 人脸数据库图像示例7 3 图4 9 在i - m i s t 人脸数据库上的实验性能对比。7 4 图4 1 0 在u m i s t 人脸数据库上的平均识别率( ) 对比7 4 图5 1 无标签样本对学习结果的影响示意图7 9 图5 ，2e x t e n d e dy a l e b 人脸数据库图像示例。8 8 图5 3 采用e x t e n d e dy a l e b 数据库时，训练集中未标签样本的识别率对比8 9 图5 4 采用e x t e n d e dy a l e b 数据库时，测试集中的识别率对比9 0 图5 5p i e 人脸数据库图像示例9 l 图5 6 采用p i e 数据库时，训练集中未标签样本的识别率对比9 l 图5 7 采用e x t e n d e dy a l e b 数据库时，测试集中的识别率对比9 2 表格 表格 表4 1 在y a i e 人脸数据库上的最优识别率( 呦及对应的特征维数。7 3 表4 2 在l m i s t 人脸数据库上的最优识别率( ) 及对应的特征维数7 5 x i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名： 璩 签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 p 公开口保密( 年) 作者签名： 签字日期： 一蓼害一 导师签名： 签字日期： 第l 章绪论 1 1 研究背景及现状 1 1 1 研究背景 第1 章绪论 计算机科学与信息技术已经经历了半个多世纪的发展，给人类社会的发展 带来了巨大的影响。随着现代的数据采集技术、数据存储技术以及数据库管理 技术的日趋成熟，人们获取和收集数据的能力得到了极大的提高。无论是科学 研究领域还是社会生活的其它方面都积累了大量的数据。这些丰富的数据资源 在给人们带来便利的同时也带来了一大堆的难题，例如信息过量、难以处理、 有价值的信息淹没在海量数据中、数据难以取舍等等。面对这些“过剩的数 据信息，如果缺乏有效的分析和处理手段，就无法发掘出数据中隐含的潜在关 系和规则，也无法据此对未来的发展趋势做出推测。这就导致所谓的“数据丰 富但知识匮乏 的现象。因此，如何对这些丰富的数据资源进行有效的分析， 挖掘出数据中蕴含的有用信息已经成为目前的研究者和技术专家所面临的共同 挑战。机器学习和数据挖掘技术被证明是非常有效和可行的重要途径，并且已 经受到研究学者的广泛关注。 机器学习( m a c h i n el e a m i n g ) 是人工智能( a 州f i c i a li n t e l l i g e n c e ) 的核心研究 领域之一。它最初的研究动机是为了让计算机系统能够模拟或实现人类的学习 行为，使其能够从数据中自动地学习新的知识或者技能。因为很显然，没有学 习能力的系统是很难被认为是具有智能的。目前，有关机器学习的定义广泛采 用的是：利用经验来改善计算机系统自身的性能( m “c h e h1 9 9 7 ) 。事实上，在计 算机系统中，“经验”主要是以数据的形式存在的，因此机器学习就需要设法基 于数据进行分析，这使得它逐渐成为智能数据分析技术的创新动力之一，并因 此受到越来越多的关注。数据挖掘( d a t am i l l i n g ) 是多学科交叉的产物，它综合 了人工智能、机器学习、数据库、统计学和高性能计算等领域的技术。数据挖 掘和知识发现( k h o w l e d g ed i s c o v e 巧) 通常被相提并论，并在许多场合下被认为 是可以互相替代的两个术语。有关数据挖掘有多种描述不同但涵义接近的定义。 一般认为，所谓数据挖掘就是从大量数据中识别出有效的、新颖的、潜在有用 并最终可理解的模式的非平凡过程( f a y y a de ta 1 1 9 9 6 ) 。总体上讲，数据挖掘主 要是利用数据库领域的技术来管理数据，而利用机器学习等学科的技术来分析 第l 章绪论 数据。近年来，数据挖掘已经成为计算机学科的一个新的研究热点，并吸引了 许多相关领域的研究学者和技术专家的关注。 机器学习和数据挖掘的一个共同的目标就是探索和发现隐藏在数据中的感 兴趣信息。对于给定的学习任务，它们通常需要从已有的数据集中学习或者推 导出一个分类函数或者估计函数，并设计出具体的算法。然而，在许多实际应 用，如图像分析、字符识别、文本分类、视频分析、视频检索以及基于生物特 征的身份识别等问题中，所要处理的数据都具有很高的维数。这些高维特征一 方面能够提供更为丰富和详细的信息，理论上会对提高算法的准确性有很大帮 助。然而，数据维数的大幅度提高也会同时给算法的执行带来前所未有的困难。 例如，在一个典型的图像分类问题中，假设给定的是幅灰度图像，每幅图像 都具有m n 像素的大小，则通常可以将每幅图像分别按行或列堆叠成m n 的向量，其中每个分量表示图像的一个像素值。这样，每幅图像都可以看作是 m n 维空间的一个观测点。而对于常见的图像尺寸，例如m = n = 2 s 6 ，这些 向量的维数就会高达6 s s 3 6 维。面对如此高的维数，常用的分类算法通常无法 得到较为理想的效果。另一个例子是基于互联网的文本检索。在这个问题中， 一般需要首先建立一个包含常用词组的词库，然后通过对网页上出现的词组进 行词频统计，得到对网页的向量描述【恍，w 。】r ，其中f 为词库中包含词的个 数。显然，网页中所出现的词汇量是非常巨大的，因而所构造的向量的维数也 通常很大。 由此可见，高维数据会对后续的处理工作造成很大困难。具体地说，方 面，过度膨胀的高维特征会直接导致算法的计算量迅速上升；另一方面，高维 特征也会导致样本的数量相对较少，引发所谓的维数危机( c u r s eo f d i i l l e n s i o n a - l i t ) r ) ( b e l l m a n1 9 6 1 ) ，使得所得到的估计函数在某些统计上的渐进性质遭到破坏。 实际上，在现实世界中所获取的原始数据往往都是高维的，并且难以直接被人 理解、表示和处理。为了解决这一问题，可以首先将数据降到低维空间，然后 利用得到的低维特征进行既定的学习或者挖掘任务。有效的数据降维技术 ( d 疏e n s i o n a l 埘r e d u c t i o n ) 能够探索出原始数据的内在结构和联系，不仅可以消 除数据间的冗余，以简化数据，提高计算效率，还能够大大改善数据的可理解 性，提高学习算法的精度。因此，对数据降维的研究成为了机器学习和数据挖 掘中的重要研究课题，并且已经在很多应用中发挥了重要作用。除了上面举的 两个例子以外，降维的另一个重要的用途就是数据的可视化( d a t av i s u a l i z a t i o n ) ， 即通过将原始数据降至2 3 维，可以使人们能够直观地探究数据的内在结构和 分布性质，理解所面临的问题的本质，以便于选择出合适的解决方案。 通常，数据降维主要有两种途径，即特征选择( f e a t u r ee x t m c t i o n ) 和特征提 第1 章绪论 取( f e a t u r es e l e c t i o n ) ( d u d ae ta 1 2 0 0 1 ) 。特征选择是指在所有的特征中选择最有 代表性的一些特征，所得到的低维数据表示都包含了一定的物理意义。而特征 提取则是通过对原始特征进行某种变换，得到更有意义的低维投影。一般，在 保留的特征维数相同的情况下，特征提取能比特征选择在后续的数据分析中获 得更好的效果。在本文中所讨论的算法都属于特征提取方法，即通过映射将数 据从高维空间变换到低维特征空间。 1 1 2 降维技术研究概况 由于降维技术的重要性，在过去的几十年中，研究者已经提出了许多有效 的降维算法。这些降维算法可以根据所采用策略的不同而进行不同的分类( d u d a e ta 1 2 0 0 l ；m a a t e ne ta 1 2 0 0 8 ) 。依据数据样本的类别信息是否被利用，这些算法 可以分为非监督n s u p e r v i s e d ) 降维方法和监督( s u p e j s e d ) 降维方法。依据所要 处理的数据属性类型的不同，降维算法又可分为线性方法和非线性方法。非监 督降维算法的目标通常是使得数据在降维后信息损失最小，而监督降维算法则 通常力求最大化各类别之间的鉴别信息。此外，近年来有关半监督学习 ( s e m i - s u p e i s e dl e a m i n g ) 的研究也逐渐引起大家的广泛关注( z h u2 0 0 7 ) 。所谓 半监督学习就是指在仅有少量样本具有类别信息，或者样本的类别标定需要花 费很大的代价时，可以同时利用易于获取的无类别信息样本来帮助学习。 线性降维技术通常假设数据集采样自一个全局线性的高维空间，即构成数 据的各变量之间是独立无关的。如果所面临的数据确实具有全局线性的结构， 或者在一定程度上可以近似为全局线性时，这些方法能够有效地学习出其线性 结构，得到数据紧致的低维表示。在线性降维方法中，最为著名的算法有主成 分分析( p m c i p l ec o m p o n e n ta n a i y s i s ，p c a ) ( j o l l i 位2 0 0 2 ) 、独立成分分析 ( i n d e p e n d e n tc o n l p o n e n ta n a l y s i s ，i c a ) ( c o r n o nl9 9 4 ) 以及线性判别分析( l i n e a r d i s c r i r n i n a n t a n a l y s i s ，l d a ) ( f i s h e r1 9 3 6 ) 等。p c a 算法根据重建误差最小的原则 来寻找一组最优的正交变换基，并通过保留数据分布方差较大的若干主分量来 达到特征提取和降维的目的。i c a 算法源于信号处理中的盲信号分离问题，其 目的是将线性混叠的信号分解成为互相独立的几个分量。i c a 可以视为p c a 的 延伸，因为p c a 仅仅利用了数据的二阶统计信息，适用于高斯分布的数据，而 i c a 则可以用于非高斯分布的数据。这两种方法都没有利用数据样本的类别信 息，因而都属于非监督学习方式。与这两者不同，l d a 是一种监督方法，它是 基于同方差高斯( h o m o s c e d a s t i cg a u s s i a n ) 分布假设，在f i s h e r 准则下寻找最优 的判别向量，以使得数据样本的类间散布最大而类内散布最小。因为对于以分 类为目的的学习任务而言，样本的类别信息通常有着重要的帮助，因此，l d a 第l 章绪论 更适用于以分类问题。这三种方法尽管都是非常经典的线性降维技术，但是即 使在最近几年仍然受到研究人员的关注和深入研究，并且出现了许多针对其局 限性的改进算法。其它的线性降维方法还有因子分析( f a c t o ra n a l y s i s ) ( g o r s u c h 1 9 8 3 ) 、多维尺度变换( m u l t i d i n l e n s i o n a ls c a l i n g ，m d s ) ( c o xa n dc o x1 9 9 4 ) 以及非 负矩阵分解( n o n n e g a t i v em a t 血f a c t o r i z a t i o n ，n m f ) ( l e ea 1 1 ds e 眦gl9 9 9 ) 等。 然而，在现实中所获取的许多数据其各个属性间常常是强相关的，呈现出 高度的非线性，例如文本数据、图像数据、语音数据以及视频数据等。这些数 据都具有难以获知的复杂结构，此时，采用线性方法就无法得到理想的效果。 为了解决这一问题，研究人员也提出了许多非线性降维算法。其中，基于核思 想的降维方法是比较有代表性的一类( s h a w e 1 a y l o r1 9 9 8 ) 。这类方法的想法比较 直接，其基本思想是首先将数据从原始的非线性空间映射到一个更高维甚至是 无限维的特征空间，然后再利用传统的线性方法在该特征空间中对数据进行处 理。这个非线性映射并不需要显式地定义，而是利用核技巧( k e m e lt f i c k ) 通过定 义m e r c e r 核隐式地构建。对应的高维特征空间称为再生核希尔伯特空间 ( r e p r o d u c ek e m e lh i l b e r ts p a c e ，r k h s ) 。著名的分类算法支持向量机( s u p p o r t v e c t o rm a c h i n e ，s v m ) 就是基于核的原理构建的( c r i s t i a n j i l ie ta 1 2 0 0 0 ) 。利用核 技巧，大多数传统的线性降维方法都可以扩展到非线性的情况，例如核主成分 分析( k e m 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 ，k p c a ) ( s c h o l k o p f19 9 8 ) 、核独立成分 分析( k e n l e li n d e p e n d e n tc o n l p o n e n ta n a l y s i s ，k i c a ) ( b a c ha n dj o r d a n2 0 0 3 ) 和核 f i s h e r 判别分析( k e m e lf i s h e rd i s c r i m i n a n ta n a l y s i s ，k f d a ) ( m i k a e ta 1 2 0 0 3 ) 等 等。需要指出的是，核方法具有一个难以避免的缺点，就是如何选择合适的核 函数。一个好的核函数可以使得数据在映射到隐式的特征空间中时线性可分或 者近似线性可分，但是并不是每个核函数对于所有的数据都适用。核函数的选 择反映了人们对问题的先验认识，在实际应用中往往根据经验选择。 除核方法以外，另一类非线性的降维方法基于流形学习的方法近年来 在包括数据挖掘、机器学习、图像分析和计算机视觉等多个领域都引起了研究 者的广泛关注。流形学习的根本目的是揭示数据中内在的非线性结构，寻找高 维数据在低维空间中的紧致嵌入。相比核方法而言，流形学习的动机较为直接： 一方面，许多高维的采样数据都是由少数的几个隐含变量所决定的。例如，人 脸的图像数据就是由外部光线的强度( i l l 啪i n a t i o n ) 、人与相机之间的距离 ( d i s t a n c e ) 、人头部面对相机的姿势( p o s e ) 以及面部表情( e x p r e s s i o n ) 等因素所决 定的。另一方面，从认知心理学的角度来看，心理学家认为人的认知过程是基 于认知流形和拓扑连续性的( s e u n ga i l dl e e ，2 0 0 0 ) 。这些认识都促使了人们对流 4 第l 章绪论 形学习的深入研究。关于流形学习，最具影响力的工作是( t e n e n b a u me ta 1 2 0 0 0 ) 和( r o w e i se ta 1 2 0 0 0 ) 。这两篇文章发表于2 0 0 0 年s c i e n c e 的同一期上，并分别 提出了各自的流形学习算法，即等距离映射( i s o m e t r i cm a p p i n g ，i s o m a p ) 和局部 线性嵌入( l o c a l l yl i n e a re n l b e d d i n g ，l l e ) 。i s o m a p 是建立在m d s 算法的基础 上，试图保持数据样本点之间的几何关系，即每两个样本点间的测地距离 如e o d e s i cd i s t a n c e ) 。它是一种全局优化的算法，能够给出数据的等距低维投影。 l l e 的基本思想是构建每个样本点的邻域样本对自身的重建权重，并在寻找低 维空间嵌入时尽量保持这些邻域权值不变，是一种局部优化的算法。随后，在 2 0 0 2 年b a l a s u b 阳m a n i a na n dt e b e n b a u m ( 2 0 0 2 ) 对i s o m a p 算法的健壮性进行了进 一步讨论。同时为了降低i s o m a p 的计算量，s i l v aa n dt e n e n b a u m ( 2 0 0 2 ) 又提出 了一种优化算法即标界i s o m a p 算法( i s o m a pw i t hl a n d m a r kp o i 鹏，l i s o m a p ) 。 在继i s o m a p 和l l e 之后，基于流形学习的思想，研究者又提出了一些其 它的降维算法，包括拉普拉斯特征映射( l a p l a c i a ne i g e l l i i l a p ，l e ) ( b e l k i ne t 2 l 1 2 0 0 2 ) ，局部线性调和( l o c a l l yl i n e a rc 0 0 r d i n a t i o n ，l l c ) ( r 0 w e i se ta 1 2 0 0 2 ) ，海 森局部线性嵌入( h e s s i a nl o c a l l y “n e a re n l b e d d i n g ，h l l e ) ( d o n o h oa 1 1 dg r i m e s 2 0 0 3 ) 、最大方差展开( m a x i m 啪v a r i a n c eu n f o l d i n m v u ) ( w 色i n b e r g e fe ta 1 2 0 0 4 ) 、局部切空间排列( l o c a lt a n g e n ts p a c ea l i g i m l e n t ，l 1 s a ) ( z h a n ge ta 1 2 0 0 5 ) 以及局部坐标排列( l o c a lc o o r d i n a t e sa l i g n j n e n t ，l c a ) ( z h a n ge ta 1 2 0 0 8 ) 等等。 与i s o m a p 和l l e 一样，这些流形学习算法都有着一些共同的特点。例如，首 先它们都需要在每个样本点附近寻找一个近邻域，并基于此邻域来刻画流形在 每个样本点位置的局部几何结构；其次在将数据映射至低维空间时，这些算法 都尽量保持所刻画的局部几何结构尽量不变。这些算法的不同之处仅在于如何 描述邻域的局部几何信息，以及如何构造目标函数寻找最优的嵌入解。总的来 说，这些非线性的流形学习算法能够揭示出高维数据的内在结构，并且已经在 图像分析、图像识别和数据可视化方面展现出了巨大的潜力( t e n e n b a u me ta 1 2 0 0 0 ；r d w e i se t 出2 0 0 0 ：b e l k i l le ta 1 2 0 0 2 ) 。一些成功的例子是当应用于手写数 字、手势图像和人脸图像数据的例子时，这些算法的降维结果能够展现出图像 潜在的变量因素，如手势的方向、动作，人脸的姿态、表情、光照等等。但是， 由于这些方法都是基于数据样本的局部邻域的，它们都面临着邻域选择的问题， 即如何选取合适的邻域以获取准确的局部线性结构估计，因为邻域的选取合适 与否将直接影响着最终的嵌入结果。另外，如果数据样本抽样的密度不均匀， 也会给邻域选择带来挑战，使得局部邻域结构的估计产生偏差。 另外，这些流形学习算法在进行数据降维时，都是直接得到样本在低维空 第l 章绪论 间中的嵌入坐标，并没有得到从原空间到低维空间的显式映射关系。这样就产 生所谓的o u t o s s 锄p l e 问题，即对于新的样本，算法无法直接得到它在低维空 间中对应的坐标。针对这个问题，b e n g i oe ta 1 ( 2 0 0 4 ) 利用核的方法提出了几种 主要的流形学习算法的o u t o s a m p l e 框架，包括i s o m a p ，l e 和l l e 等。因为 这些流形学习算法和k p c a 算法有着密切的关系，即它们都可以解释为具有不 同的g r 锄矩阵的k p c a ( h a ne ta 1 2 0 0 4 ；b e n g i oe ta 1 2 0 0 4 ) 。除此之外，另一种 较为常用的策略就是进行线性化( l i n e a r i z a t i o n ) ，即通过假设数据从原空间到低 维空间的嵌入是线性映射，将原先算法中直接求解嵌入坐标的优化问题转化为 求解一个变换矩阵的问题。这类推广算法比较有代表性的有邻域保持嵌入 州e i g h b o r h o o dp r e s e r v i n ge n l b e d d i n g ，n p e ) ( h ea n l dc a ie ta 1 2 0 0 5 ) ，正交邻域保 持映射( o r t l l o g o n a ln e i g h b o r h o o dp r e s e r v i n gp r o j e c t i o n ) ( k o l ( i o p o u l o ua 1 1 ds a a d 2 0 0 5 ) ，局部保持投影( l o c a l 埘p r e s e n r i n gp r o j e c t i o n ，l p p ) ( h ea n dy 趾e ta 1 2 0 0 5 ) ， 线性局部切空间排列( l i n e a rl o c a lt a n g e n ts p a c ea l i g n m e n t ，l 【，t s a ) ( z h a n ge ta 1 2 0 0 7 ) 以及线性局部坐标排列l i n e a rl o c a lc o o r d i n a t e sa l i g m e n t ( l l c a ) ( z h a i l g e ta 1 2 0 0 8 ) 等等。 其次，尽管这些流形学习算法在数据感知方面有独到之处，但它们都是非 监督的学习方法，并不适用于分类问题。因此，研究人员也基于流形学习的思 想，提出了一些针对分类目的监督降维方法( s u g i y a m2 0 0 6 ；斑d d e re ta 1 2 0 0 3 ； m d d e