（信号与信息处理专业论文）线性图嵌入算法及其应用.pdf

中文摘要 中文摘要 本文主要研究基于图嵌入理论的线性图嵌入算法，图和流形都可以嵌入到欧氏 空间，目前许多流形学习算法及经典的维数缩减、特征提取算法可以使用图的方 法表示，从而可以通过图矩阵的谱特征来近似描述流形的内在主要结构，利用特 征向量来表示全局低维坐标。与其它研究方法相比，一个显著的优点是基于图嵌 入框架的流形学习方法能够发现全局最优解的凸优化问题，不会陷入局部极值。 通过数据点之间的流形距离度量构建本征图与惩罚图来表征局部近邻结构与全局 结构信息，然后通过解决图嵌入框架下的优化问题来得到低维嵌入坐标。可以有 效地发现嵌入高维数据中有意义的低维子流形，揭示隐藏在高维观测数据中的内 在几何结构与规律性。 图嵌入通过本征图和惩罚图来描述样本点之间的相互关系，并把目前常用的降 维算法，如p c a ，l d a ，i s o m a p ，l l e ，l e 等均统一到了图嵌入的框架下，并 在该框架中进行扩展，使其能够线性化、核化及张量化。在图嵌入框架下对流形 学习算法进行研究，通过数据点之间的流形距离度量构建本征图与惩罚图来表征 局部近邻结构与全局结构信息，然后通过解决图嵌入框架下的优化问题来得到低 维嵌入坐标。可以有效地发现嵌入高维数据中有意义的低维子流形，揭示隐藏在 高维观测数据中的内在几何结构与规律性。 本文进行针对图嵌入算法的线性扩展进行了如下几个方面的研究： 直接图嵌入算法：在高维小样本问题应用中，传统的线性图嵌入算法往往 包含p c a 预处理步骤来避免矩阵奇异问题，在p c a 预处理中往往会丢掉 一些较小特征值对应的特征向量，从而可能丢掉了一些可分性信息，同时 也没有很好地抑制噪声和有限样本造成的影响。我们提出直接图嵌入算法 可以直接从数据集中提取特征而无需p c a 预处理，在多个数据库的仿真 结果表明，直接图嵌入算法的可分性更好，鲁棒性更强。 基于局部特征分析的直接线性图嵌入算法：一般来说，图像的局部结构特 征往往反映了图像的一些重要内在特征，具备较强的细节刻画能力，包含 重要的鉴别信息。为了能够更有效地利用数据集的局部结构信息，我们提 出利用l f a 特征，结合直接线性图嵌入算法，是一种有效地适用于图像 识别的特征提取算法。 正交化直接线性图嵌入：线性图嵌入算法得到的变换矩阵往往是非正交的， 非正交性使算法不能保持高维数据空间中的测度结构，且不能准确地估计 高维数据的内蕴维数，对数据的重建不利，极大地影响了算法的性能，为 此本文我们提出了基于最小二乘准则的正交化直接线性图嵌入算法。 北京交通大学博士学位论文 正则化】莹接图嵌入算法：我们在直接线性图嵌入算法的基础上，提出了正 则化的l 呈接线性图嵌入算法，在不增加算法计算复杂度的同时，提高了算 法的性能和泛化能力。 基于图像欧氏距离的线性图嵌入算法：我们提出利用图像的欧氏距离代替 向量欧氏距离来描述样本点之间的相似性，考虑了图像本身像素间的几何 信息，降低了线性图嵌入算法对图像噪声和变化的敏感度。 在多个数据库的实验结果验证了我们提出的这些算法的有效性。 关键词：图嵌入；流形学习；模式识别；正则化；正交化； a b s t r a c t a bs t r a c t t h i st h e s i s s t u d i e s t h el i n e a re x t e n s i o no fg r a p he m b e d d i n g b o t hg r a p h sa n d m a n i f o l d sc a nb ee m b e d d e di ne u c l i d e a ns p a c e ，t h ec u r r e n tm a n i f o l dl e a r n i n g a l g o r i t h m sa n dm a n yo ft h ec l a s s i c a ld i m e n s i o nr e d u c t i o n ，f e a t u r ee x t r a c t i o nm e t h o d s ， c a nc h a r a c t e r i s t i c st h r o u g hs p e c t r a lg r a p ht h e o r y m a n yd i m e n s i o nr e d u c t i o na l g o r i t h m s ，s u c ha sp c a ，l d a ，i s o m a p , l l e ，l e ， d e s p i t et h e d i f f e r e n tm o t i v a t i o n so ft h e s ea l g o r i t h m s ，c o u l db eu n i f i e db yag e n e r a l f o r m u l a t i o nk n o w na sg r a p he m b e d d i n gw i t h i nac o m m o nf r a m e w o r k i ng r a p h e m b e d d i n g ，e a c ha l g o r i t h mc a nb ec o n s i d e r e da st h ed i r e c tg r a p he m b e d d i n go r i t s l i n e a r k e m e l t e n s o re x t e n s i o no fas p e c i f i ci n t r i n s i cg r a p ht h a td e s c r i b e sc e r t a i nd e s i r e d s t a t i s t i c a lo r g e o m e t r i cp r o p e r t i e s o fad a t a s e t ，w i t h c o n s t r a i n t sf r o ms c a l e n o r m a l i z a t i o no rap e n a l t yg r a p ht h a tc h a r a c t e r i z e sas t a t i s t i c a lo rg e o m e t r i cp r o p e r t y m a ts h o u l db ea v o i d e d i nt h i st h e s i s ，w ei n t r o d u c eo u rw o r ko nl i n e a re x t e n s i o no fg r a p he m b e d d i n g ： d i r e c tl i n e a rg r a p he m b e d d i n ga l g o r i t h m ：i ns m a l ls a m p l es i z ep r o b l e m a p p l i c a t i o n s ，t h e t r a d i t i o n a ll i n e a rg r a p he m b e d d i n ga l g o r i t h m s n e e da np c a p r e p r o c e s s i n gs t e pt o a v o i dt h em a t r i xs i n g u l a r i t yp r o b l e m ，w h i c hm a yl o s es o m e d i s c r i m i n a t i n gi n f o r m a t i o n w ep r o p o s ead i r e c tl i n e a rg r a p he m b e d d i n ga l g o r i t h mc a n e x t r a c tf e a t u r e sd i r e c t l yf r o mt h ed a t as e tw i t h o u tp c ap r e p r o c e s s i n g t h ed i r e c tl i n e a rg r a p he m b e d d i n ga l g o r i t h mb a s e do i ll o c a lf e a t u r ea n a l y s i s ： i ng e n e r a l ，t h el o c a ls t r u c t u r e so ft h ei m a g e sr e f l e c ts o m ei n h e r e n tc h a r a c t e r i s t i c so ft h e i m a g e s ，w ep r o p o s e da ne f f e c t i v ea l g o r i t h mo fi m a g er e c o g n i t i o nw h i c hb a s e dl o c a l f e a t u r ea n a l y s i sa n dt h ed i r e c tl i n e a rg r a p he m b e d d i n ga l g o r i t h m o r t h o g o n a ld i r e c tl i n e a rg r a p he m b e d d i n g ：l i n e a rg r a p he m b e d d i n ga l g o r i t h m s a r eu s u a l l yn o n o r t h o g o n a l ，w ep r o p o s et h eo r t h o g o n a ll e a s ts q u a r e sl i n e a rg r a p h e m b e d d i n ga l g o r i t h md i r e c t l y r e g u l a r i z a t i o n d i r e c tl i n e a r g r a p he m b e d d i n ga l g o r i t h m ：w ep r o p o s e d r e g u l a r i z a t i o n d i r e c t l i n e a r g r a p he m b e d d i n ga l g o r i t h m ，w i t h o u t i n c r e a s i n g t h e a l g o r i t h mc o m p l e x i t y , w h i c hc a ni m p r o v et h ep e r f o r m a n c eo ft h ea l g o r i t h ma n dt h e g e n e r a l i z a t i o na b i l i t y l i n e a rg r a p he m b e d d i n ga l g o r i t h mb a s e do ni m a g ee u c l i d e a nd i s t a n c e ：w e p r o p o s et h a ti m a g ee u c l i d e a nd i s t a n c ei n s t e a do fv e c t o re u c l i d e a nd i s t a n c et od e s c r i b e v 北京交通大学博士学位论文 一一一 t h es i m i l a r i t yb e t w e e nt h es a m p l ep o i n t s ，c o n s i d e rt h eg e o m e t r i ci n f o r m a t i o nb e t w e e n p i x e l so ft h ei m a g e s e x p e r i m e n t a l r e s u l t s p e r f o r m e d o ns o m et y p i c a ld a t a b a s e sd e m o n s t r a t e dt h e e f f e c t i v e n e s sa n dr o b u s t n e s so fo u r p r o p o s e da l g o r i t h m s k e y w o r d s ：g r a p he m b e d d i n g ，m a n i f o l d l e a n i n g ，p a t t e r nr e g o n i t i o n ， r e g u l a r i z a t i o n ，o r t h o g o n a l i z a t i o n 致谢 本论文的工作是在我的导师袁保宗教授的悉心指导下完成的，导师对学科方 向的准确把握、对学生特点的全面了解和为研究工作创造的良好条件，他孜孜不 倦的严谨治学态度、科学的工作方法以及高尚的学术道德给我留下深刻的影响， 将使我终生受益匪浅。在此衷心感谢这些年来我的导师袁保宗教授对我的关心和 指导，谨向袁保宗教授表达我最诚挚的谢意! 唐晓芳老师在学习上和生活上都给予了我很大的关心和帮助，在此向唐晓芳 老师表示衷心的谢意。 感谢苗振江教授和刘渭滨副教授在我的课题研究方向，研究思路中提出的宝 贵的指导性意见，感谢他们在课题研究中对我的关心和悉心帮助。此外，感谢北 京信息所阮秋琦教授、裘正定教授对我学习和论文工作的热情帮助。 在实验室工作及撰写论文期间，陈京、李波、周卫东、王丽辉等同学对我的 学习及研究工作给予了热情帮助，在此向他们表达我的感激之情。 感谢我硕士阶段的导师，裴炳南教授。裴炳南教授将我领入信号处理和模式 识别这一研究领域，并一直关心和支持我的发展。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 时间的仓促及自身专业水平的不足，整篇论文肯定存在尚未发现的缺点和错 误。恳请阅读此篇论文的老师、同学，多予指正，不胜感激! 引言 1 引言 1 1 研究背景和意义 模式识别能够自动检测数据集中的相似性，并将模式进行分类。作为一个研 究领域，其兴起于2 0 世纪6 0 年代，涉及到统计学、人工智能、计算机科学、生 理学、心理学等多个学科。模式识别的广泛应用吸引了众多的研究者，并产生了 许多新的方法，从而推动了该学科的进一步发展。 随着信息技术的飞速发展，人们所获得的数据也在飞速增长，并出现了越来 越多不确定性的、海量、高维、非线性的复杂数据。许多实际应用，如人机交互f 1 1 ， 文本聚类 2 ，图像检索，数据挖掘，遥感，军事，医学影像处理等均需要更强大 有效的模式识别技术。大量的数据带来了很多问题 3 ，如计算效率低下、维数灾 难问题( c u r s eo f d i m e n s i o n a l i t y ) 等，而这些数据中往往包含着人们难以观察到的 知识和规律。传统的数据分析方法在处理这些数据时，往往无法探索和揭示蕴含 在数据中的信息或规律。因而，如何有效地从高维复杂数据中获取信息或规律已 成为当今信息科学与技术所面临的基本问题。 图1 1 给出了一般化的模式分类过程： 一 传感器j 一表示模式z 、，一 图1 1 模式识别简图 特征是决定相似性和分类的关键，因此，如何寻找合适的特征就成为了模式 识别的核心问题，特征的选择和提取直接决定了模式识别系统的性能。为有效地 实现分类识别，模式识别通常需要对表示模式进行变换，从而得到能够反映分类 本质的特征模式，这就是特征选择和提取的过程。表示模式组成的空间称为测量 空间，直接获取的表示模式维数通常都很高，直接对高维数据进行处理会碰到很 多问题，除计算量和存储量大、数据可视性差、包含多种噪声外，其中最突出的 问题就是容易造成维数灾难。特征模式组成的空间称为特征空间，维数通常远低 于测量空间。在样本测量空间中直接进行运算存在诸多弊端，具体应用中，如人 北京交通大学博士学位论文 脸识别、文本聚类等，数据集中样本之间往往存在一定的规律性和相关性，即数 据集具有外在的高维表现和内在的低维特征。因此，经过特征的选择和提取，降 低模式的维数，剔除多余的和不相关的信息，从而将数据的表示模式转换为更适 合后续分类的特征模式，无疑具有重要意义。 特征选择是一种选择最佳地输入特征子集的方法，而特征提取算法是通过变 换和重新构造新的特征的方法。选用特征提取还是特征选择取决于实际问题和所 获得的数据集。特征选择保留了测量误差和被选择的特征保持了原先的物理特性。 而且这些被保存的特征有利于理解模式产生的物理过程。另一方面，特征提取中 重构的特征将会产生比最佳子集更好的分类效果，但是这些新的特征可能没有明 确的物理概念。 通常认为特：征选择和提取包括两方面的目标，一是寻找针对模式的最具鉴别 性的描述，尽可能地提高模式间的区分度；二是适当降低数据的维数。实际问题 中通常不易找到那些最重要的特征，或受条件限制不能对它们进行测量，这就使 特征选择和提取成为构造模式识别系统最困难的一步，越来越受到人们的重视， 本文的工作也围绕特征的提取方法展开。 1 2研究现状 特征选择和：提取是从测量数据集中选出最有利模式分类的变量，这些变量可 以通过原始测量数据集的线性或者非线性变换得到，从某种意义来讲，特征的选 择和提取需要根据实际应用紧密相关的，目前还没有统一地解决这种变换的有效 理论和方法。 测量空间通常维数很高，在大多数情况下，不能直接在测量空间进行分类器 设计。以图像识别为例，最直接、简单的方法就是在高维空间中计算图像向量化 后的欧氏距离 4 ，但是直接用原始图像进行匹配会面临一些问题。这主要是由图 像的高维性所引起的。例如，一幅尺寸为1 2 8 1 2 8 像素的灰度图像将形成一个 l x l 6 3 8 4 长度的向量，也就是说图像空间的维数为1 6 3 8 4 。在这样一个高维空间中 进行识别、分类：不但计算开销大，而且也容易受到光照、噪声等因素影响。为此， 人们提出了多种的算法来对原始图像进行分析，从原始图像中提取出稳定的特征 实现图像的降维，进而在特征空间进行分类器设计，从而提高识别的效果 2 5 6 7 8 】 9 ， 特征提取是一种变换( 线性或非线性) ，可以将原始数据( 所有变量) 变换到 较低维数的数据空间( 特征空间) 上，可以提高系统的计算速度，降低数据需求 量，最大程度地减少信息损失，并为分类器提供合适的特征模式，从而提高分类 引言 器性能，减少冗余，发现原始数据集的潜在特性，使原始数据的关系和结构更容 易识别。这种变换可以是原始变量的线性或非线性组合，也可以分为有监督，无 监督和半监督的。 将数据集从高维的测量空间变换到较低维的特征空间，更好地对数据集进行 分类是特征选择和提取的目标，因此衡量变换的有效性最好使用分类器的错误概 率来进行衡量，但分类器错误概率地计算往往非常复杂，因此实际中通常使用另 外的一些替代准则来确定特征提取及选择方法，常用的准则有距离度量、概率可 分性度量、及熵度量等 11 。 在模式的特征提取过程中，最优化的变量在所有可能的变换上得到，通常先 指定变换的类型，然后再寻找一个最优变换鑫，使得： 厂11 、 j ( a ) = m a x j ( a ( x ) ) j7 n l n 上式中a 表示所有可能的变换集合，x 表示观测数据。 特征提取从高维的特征空间中确定一个合适的低维特征子集。线性变换如主 成分分析、线性鉴别分析、因子分析、非负矩阵分解、多尺度分析等线性映射的 方法在特征提取中被普遍应用。线性特征提取方法具有许多优良的特性，保留了 原数据空间的最大信息量，这为数据描述提供了更好的手段，同时也大大降低了 计算的复杂度，计算简便速度快、具有解析解、对具有线性结构的数据集合非常 有效、便于解释等。线性特提取方法实际是在不同优化准则之下，寻求最佳线性 模型的方法。首先通过某种定义的优化准则，求得最优的特征向量集，张成较低 维的特征空间，然后将训练样本和测试样本投影到这个特征子空问，得到相应的 投影系数。最后计算训练样本和测试样本投影系数之间的距离，并将此作为判断 测试样本与模式类之间相似度的依据，从而判定测试样本的类别。 1 2 1经典线性特征提取方法 主成分分析( p r i n c i p a lc o m p o n e n t sa n a l y s i s ，p c a ) 1 0 是应用最广泛的特 征提取方法，可用较少数量的特征描述样本，而p c a 在人脸识别 2 5 】中地成功应 用已经成为人脸识别领域的一个里程碑式的工作。从矩阵分析 1 1 1 2 的角度来看， p c a 的目标就是使用另一组基去重新描述得到的数据空间，这样一来数据就可以 被表示为这组基的线性组合。p c a 空间的基向量揭示了原有的数据间的关系，可 最大程度地去除冗余和噪音的干扰。p c a 通过正交变换来获取特征模式，这些新 特征由于相互正交，因此不再有信息的冗余，从而将存在信息冗余的高维测量空 间变换为一个无信息冗余的低维特征空间，用较少数目的特征向量刻画样本的全 北京交通大学博士学位论文 局关联性，最终达到降低原始空间维数的目的。p c a 方法假设了数据本身具有较 高的信噪比，所以具有较高方差的基向量就可以被看作是主元，而方差较小的变 化则被认为是噪二爵。通过对求得的p c a 基向量进行排序，根据需要取前面最重要 的部分，将后面的维数省去，达到降维从而简化模型或是对数据进行压缩的效果， 同时最大程度地保持了原有数据的信息。 将原始数据集变换到p c a 子空间，可以使得p c a 子空间包含的信息损失最小， 但p c a 并没有应用数据集的类别信息。如果能够将数据集的类别信息引入特征提 取过程，就可以增强被提取特征的可分性。线性鉴别分析( 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 ) l i l 3 1 4 就是基于这样一个认识被引入了。1 9 3 6 年f i s h e r 提出的线 性鉴别分析，通过定义了一个可分性准则，并找到一个最优的投影方向，使不同 类的样本在该投影方向上具有最大的可分性。然而在实际应用中，往往哇j 于数据 维数过高而训练样本数过少，从而遇到矩阵奇异问题，即使该矩阵非奇异，也会 由于维度过高、样本数过少而具有较差的推广性能。为此，研究人员提出了很多 的办法，例如：鉴别主分量分析算法( s u b s p a c el d a ) 4 ；r o b u s tl d a 1 5 ；d i r e c t l d a 7 ；广义鉴别分析 1 6 1 7 1 等。 p c a 是基于数据集的二阶统计信息，忽略了高阶统计信息，而高阶统计信息 对模式分类来说通常也是非常有用。独立主元分析( i n d e p e n d e n tc o m p o n e n t a n a l y s i s ，i c a ) 1 8 】 1 9 】【2 0 】 2 1 】 2 2 通过线性变换，从训练样本中找到一组互相独 立的基( 独立元：) ，以此来描述样本数据。p c a 实际上是在数据集的二阶统计意义 上去相关，而独立主元分析则是在数据集任意阶统计意义下去相关，作为基于高 阶统计量的信号：处理方法，能够抑制高斯白色和有色噪声，并能分解出相互独立 的非高斯信号。由于i c a 基于所有阶的统计信息，因而其求解较p c a 和l d a 更 复杂。 典型相关分；忻( c a n o n i c a lc o r r e l a t i o na n a l y s i s ，c c a ) 研究两个数据集之间 的线性相互关系，以简单直观的方式反映被观察对象之间的关系。作为一种传统 的数据分析方法：c c a 最早可以追溯到1 9 3 6 年 2 3 。有研究指出，当一组样本取 值为其类标号时，c c a 和l d a 等价。c c a 和i c a 也有着显著区别和联系，i c a 将数据分离为统：汁独立的非高斯信号源的线性组合，将成分之间的互信息最小化， 而c c a 是一种基于样本二阶矩的统计方法，将特征之间的相互关系最大化。 实际应用中：，对单个数据点往往认为是向量形式的，即在进行处理时，将数 据视为高维空间中的数据点。这就要将数据序列化为向量，将原始数据映射到向 量特征空间中，：在得到的特征空间中进行分类。由于得到的向量维数过高，会使 得计算开销过大，甚至遇到奇异值问题。实际应用中，数据往往不是以向量形式 存在的，如图像数据以像素矩阵的形式给出。 引言 为了降低计算维数，y a n g 2 4 提出了一种直接用图像矩阵进行投影的方法，二 维主元分析( 2 d p c a ) 。与传统的p c a 和l d a 不同，y a n g 的方法是直接对图像 矩阵进行统计分析。采用这个策略，2 d p c a 有两个明显的优势：更好的识别效果 和更低的计算开销。然而由于2 d p c a 是基于主元分析，并没有考虑到类别信息， 2 d p c a 保留了很多由于光照、表情变换以及其它因素所产生的信息。当同一个人 的人脸图像由于光照变换和视角变换所引起地变换大于不同人所引起的图像变化 时，2 d p c a 的性能就会明显下降。 基于2 d p c a 中直接采用图像矩阵进行分析和l d a 中运用类别信息指导特征 提取的思想，m i n gl i 2 6 提出了一种直接基于图像矩阵的线性鉴别分析方法：二 维线性鉴别分析，2 d l d a 。稍后y e 2 5 也同样提出了2 d l d a 的方法，区别在于 优化准则的构造和解决方案上。2 d l d a 避免了l d a 的奇异问题，于传统方法对 比，2 d l d a 有更高的识别率，更加鲁棒，计算开销更低。文献 2 7 深入研究了 1 d l d a 和2 d l d a ，文献 2 8 1 贝, 1 j 提出了( 2 d ) 2 l d a ，在保证识别率的前提下进 一步地降低了所需的特征系数。一些两次投影的策略，如2 d p c a + 2 d l d a 2 9 1 ， 2 d p c a + l d a 3 0 等也纷纷被提了出来。而其他一些基于向量的算法也出现了2 d 的扩展，如2 d c c a 3 1 1 。 1 2 2核函数 上面提到了一些经典的线性特征提取方法，由于其相对的简洁性和有效性在许 多领域得到了广泛地应用。然而，这种线性的本质限制了它们对于具有非线性结 构的数据的处理能力。因为从本质上说，线性方法都是建立在模式空间的线性可 分的基础上的，而在实际应用中，数据集通常不能简单地用线性函数的组合来产 生。 非线性特征提取方法是特征提取研究中的难点和热点，而核技术是模式识别 中处理非线性可分的重要方法，其基本思想是将在原始测量空间中的数据映射到 某一线性可分的更高维特征空问，然后在高维特征空间中构造最优分类平面作为 原空间中的非线性最优分类面。在此过程中，由于一般采用非线性映射，因此核 技术可以利用数据的高阶相关性。核技术的优点在于无需给出明确的映射函数或 显式构造高维特征空间，而只使用样本在原输入空间中的度量通过核函数( 内积) 便可实现高维特征空间中的算法。这一点避免了高维空间的维数灾难问题，也减 轻了计算负担。 利用核方法，可以将能够表示成数据内积运算的线性方法扩展到非线性的情 况。s c h o l k o p f e 等 3 2 他们利用核方法的思想，将线性主分量分析p c a 扩展到了非 北京交通大学博士学位论文 线性的情况，提出了核主分量分析( k e r n e lp r i n c i p a lc o m p o n e n t a n a l y s i s ，k p c a ) 算 法。b a c h 等【3 3 针对独立分量分析i c a 提出了核独立分量分析( k e r n e li n d e p e n d e n t c o m p o n e n ta n a l y s i s ，y d c a ) 算法。m i k a 等 3 4 针对线性判别分析( f i s h e rl i n e a r d i s c r i m i n a n ta n a l y s e s ，f l d a ) 提出了核费舍尔判别分析( k e r n e lf i s h e rd i s c r i m i n a n t a n a l y s i s ，k f d a ) 算法等等。这些核方法已经在在许多实际问题中成功应用，应用 证明了它们对于非线性数据的分析和处理能力。 1 2 3 流形学习 传统的子空间分析方法，如p c a 和l d a ，对数据集的假定是构成数据集的各 变量是独立无关的，如p c a 关注的是整体数据的重构误差，而l d a 衡量的是几 类数据间的分类误差，它们对数据的局部的分布结构描述能力不够。当数据呈现 高度的非线性时，传统子空间分析方法不能有效地恢复数据集内在结构的描述， 而更多的是提供了一种统计意义下的数据分布描述。相对于全局线性结构而言， 非线性流形中的欧氏度量通常只能在局部意义下成立。而许多相关研究表明，一 些实际应用中的数据集通常来自样本测量空间r 中的低维子流形m 。 流形可以描：述任何可以用局部平坦空间所覆盖的物体。从2 0 0 0 年开始，流形 学习( m a n i f o l dl e a m i n g ) 开始受到了越来越多的关注。2 0 0 0 年，s c i e n c e ；发表了 3 篇文章：i h em m i f o l dw a y so f p e r c e p t i o n 3 5 ，n o n l 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 nb y l o c a l l y l i n e a r e m b e d d i n g 36 】，ag l o b a l g e o m e t r i cf r a m e w o r kf o rn o n l i n e a r d i m e n s i o n a l i t yr e d u c t i o n 3 7 ，分别从神经科学和计算机科学的角度对流形学习问 题进行了研究，探讨了神经系统与嵌入在高维数据空间中低维认知概念之间的关 系，引导了流形学习的迅速发展。之后流形学习领域有比较大影响的方法还有 l a p l a c i a ne i g e n m a p s 3 8 ，h e s s i a ne i g e n m a p s 3 9 ，l o c a lt a n g e n ts p a c ea l i g m n e n t 4 0 丘灯 2 奇：。 s e u n g 等 3 5 1 1 从神经生理学的角度提出了感知以流形的形式存在，视觉记忆也 可能是以稳态的：流形( 或连续吸引子) 存储，并且通过实验证明连续吸引子的确 存在于人脑中，从认知学的角度支持了图像数据是高维空间中的流形这一观点。 而传统线性方法不能有效地提取出这种非线性特征，因此需要建立非线性学习模 型，发展非线性特征提取方法，以发现数据集所蕴含的内在流形结构及规律。 i s o m a p 3 7 方法首先在几何空间中计算成对测地距离，再运用经典m d s 方法把数 据点从高维输入空间投影到低维非线性拓扑空间中，从而获得保持样本间测地距 离不变的低维流形。而l l e 3 6 方法( l o c a l l yl i n e a re m b e d d i n g ，l l e ) 更加关注 样本数据集的内蕴特征，一个流形在很小的局部邻域上可以近似看成欧氏的，即 引言 局部线性的。因此在小的局部邻域上，一个点就可以用它周围的点在最小二乘意 义下最优的线性组合表示。l l e 把这个线性拟合的系数作为该流形局部几何性质 地刻画，通过保持数据集局部邻域间相互关系的方式，把高维数据映射到一个低 维全局坐标系下。 l l e 试图保持数据的局部几何性质，设法将流形上的邻域点映射到它的低维嵌 入上的邻域点。该算法的主要思想是对于一组具有嵌套流形的数据集，在嵌套空 间与内在低维空间局部邻域间的点的关系应该不变，即在嵌套空间每个采样点可 以用其近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据 点，使重构误差最小。 l l e 算法可以归结为三步： ( 1 ) 寻找每个样本点的k 个近邻点； ( 2 ) 由每个样本点的近邻点计算出该样本点的局部重建权值矩阵； ( 3 ) 由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。 2 0 0 1 年，b e l k i n 和n i y o g i 提出了拉普拉斯特征映射算法 3 8 ，主要思想是利 用拉普拉斯b e l t r a m i 算子的特性，通过求拉普拉斯b e l t r a m i 算子的特征函数来实 现流形的最优嵌入。b e l k i n 等在拉普拉斯特征映射方面的系列研究使得拉普拉斯特 征映射及其扩展算法成为了理论基础最丰富的一类流形学习算法 4 3 4 4 4 5 。 流形是欧氏空间的推广，是微分几何和拓扑代数的研究对象，流形上每一点 都存在一个邻域和欧氏空间的一个开集同胚，因此流形上每点处都存在一个邻域 可以用局部坐标系来刻画。对给定的高维观测数据集，数据变量可以用少量几个 变量来表示，在几何学上表现为数据点散布在低维光滑流形上，或者是在低维光 滑流形附近。而要有效揭示数据内在的几何结构，需要根据有限的离散观测样本 数据学习和发现嵌入在高维空间中的低维光滑流形，这也就是流形学习的主要目 标。 文献 4 1 1 给出了流形学习的定义： 设】厂是包含在欧氏空间r d 中，且设从d 维欧氏空间r a 到d 维欧氏空间尺d 存在 一个光滑嵌入映射： r1 ，) 、 厂：y _ r d ，d 直接图嵌入算法：在高维小样本问题应用中，为避免求解中遇到的矩阵奇 异问题，同时降低噪声干扰，线性图嵌入算法往往首先把原始数据投影到 p c a 子空间，然后在p c a 空间中利用线性图嵌入算法求得投影矩阵。线 性图嵌入算法中的p c a 预处理步骤往往会丢掉一些较小特征值对应的特 征向量，从而丢掉了一些可分性信息，同时没有很好地抑制噪声和有限样 本造成的影响。我们提出直接图嵌入算法可以直接从数据集中提取特征而 无需p c a 预处理，在多个数据库的仿真结果表明，直接图嵌入算法的可 引言 分性更好，鲁棒性更强。 基于局部特征分析的直接线性图嵌入算法：一般来说，图像的局部结构特 征往往反映了图像的一些重要内在特征，具备较强地细节刻画能力，包含 重要的鉴别信息。为了能够更有效地利用数据集的局部结构信息，我们提 出利用l f a 特征( l o c a lf e a t u r ea n a l y s i s ) ，结合直接线性图嵌入算法提出 了一种有效的特征提取算法，在几个人脸数据库的实验表明了我们提出的 算法的鲁棒性和有效性。 正交化的线性图嵌入：线性图嵌入算法，如l p p ，n p e ，l d a 等，得到 的变换矩阵往往是非正交的，非正交性使算法不能保持高维数据空间中的 测度结构，且不能准确地估计高维数据的内蕴维数，对数据地重建不利， 极大地影响了算法的性能，为此本文我们提出了基于最d - 乘准则的正交 化直接线性图嵌入算法，计算机仿真结果表明了正交化的引入提高了算法 的性能。 正则化的图嵌入算法：将正则化技术引入到图嵌入框架下，可利用数据集 中的局部信息，可以使得不适定问题适定，也可以提高算法的泛化能力， 我们在直接线性图嵌入算法的基础上，提出了正则化的线性图嵌入算法， 在不增加算法计算复杂度的同时，提高了算法的性能和泛化能力。实验结 果表明，正则化项的引入极大地提升了算法的性能。 基于图像欧氏距离的线性图嵌入算法：当图嵌入算法应用于如图像等数据 时，通常的做法是先将其向量化，然后计算向量之间的欧氏距离。实际应 用中，不同的训练样本之间往往不能进行精确对齐，会有一些平移，旋转， 伸缩等变化，当图像由矩阵形式扩展为向量形式时，也失去了图像本身所 具有的几何信息，因此图像向量化后的欧氏距离对图像噪声和变化非常敏 感，即使图像仅有微小地变化，也有可能导致较大的向量欧氏距离。为此 我们提出利用图像的欧氏距离代替向量欧氏距离来描述样本点之间的相 似性，实验结果证明了基于图像欧氏距离的线性图嵌入算法性能得到了提 高。 论文由以下几部分组成： 第1 章绪论。主要介绍本文研究背景、研究意义及当前研究现状。 第2 章图嵌入算法及其线性扩展。本章首先介绍拉普拉斯特征映射，然后引 申到图嵌入的框架下，针对本文关注的线性图嵌入算法，重点介绍目前常用的几 种线性图嵌入算法，同时简单介绍了图嵌入框架的张量扩展及核扩展。 第3 章直接线性图嵌入算法。本章首先介绍线性图嵌入算法的直接求解，并 北京交通大学博士学位论文 在人脸识别，文：本聚类两类问题上验证了算法的有效性。同时结合局部特征分析 和直接线性图嵌入算法，提出了一种有效的特征提取算法。 第4 章正交化的线性图嵌入。本章基于最j 、- 乘准则对线性图嵌入算法进行 了正交化的扩展。 第5 章正则化的线性图嵌入。正则化技术能够提高算法的泛化能力，本章研 究正则化的线性图嵌入算法。 第6 章基于图像欧氏距离的线性图嵌入。本章我们考虑了图像像素点之间存 在联系，因此提出了基于图像的欧氏距离代替向量欧氏距离的线性图嵌入算法。 第7 章对全文的研究工作进行了总结，并且对未来的工作方向提出了建议和 展望。 图嵌入算法及其扩展 2 图嵌入算法及其扩展 图谱理论主要研究图的邻接矩阵和拉普拉斯矩阵的特征值和特征向量，图是由 若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之 间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这 种关系。 b e l k i n 和n i y o g i 在文献 3 8 提出了流形学习中著名的拉普拉斯特征映射，作为 非线性维数缩减的算法，具有局部保持性质。拉普拉斯特征映射算法的论证来源 于l a p l a c e 。b e l t r a m i 算子在流形中的一个最佳嵌入及图的拉普拉斯算子能够近似逼 近流形上的l a p l a c e b e l t r a m i 算子。拉普拉斯特征映射基于保持数据集的局部几何 结构不变，而不是保持距离不变的思想获得高维观测空间与低维结构在局部意义 下的对应，从而实现高维空间中离得很近的点投影到低维空间中的像也离得很近。 从其给出的算法实现步骤中可以看出，拉普拉斯特征映射只需要很少的计算量， 当得到图的边权重矩阵后，转化为广义特征值问题求解。而其权值的选取方式简 单直接，拉普拉斯特征映射只能保证流形上邻近的点仍然映射到低维空间中的邻 近的位置，对于流形上距离较远的点，对应低维空间中的距离则可能会放大。拉 普拉斯特征映射算法的局部保持特征性使它相对地对离群值和噪声并不敏感。 b e l k i n 等在拉普拉斯特征映射方面的系列研究使得拉普拉斯特征映射及其扩展算 法成为了理论基础最丰富的一类流形学习算法 4 3 4 4 4 5 。 文献 5 8 1 提出了图嵌入( g r a p he m b e d d i n g ) 的概念，通过本征图和惩罚图来描 述样本点之间的相互关系，目前常见的降维算法，如p c a ，l d a ，i s o m a p ，l l e ， l e 等，均可使用图嵌入的框架来进行解释。根据图嵌入的理论，文献 5 8 1 还提出 了边界费舍尔分析( m f a ) 算法，在人脸识别等应用中的实验结果较好。 本章首先介绍拉普拉斯特征映射的基本原理，在此基础上介绍拉普拉斯特征特 征映射的线性化扩展算法一局部保持投影( l p p ) 算法，之后介绍图嵌入框架及其 扩展，并重点介绍图嵌入算法的线性扩展，在本章还将介绍图嵌入算法在高维小 样本问题中的应用情况。 2 1拉普拉斯特征映射 拉普拉斯特征映射及其扩展算法是理论基础最丰富的一类流形学习算法，得 到了全面的研究，b e l k i n 和n i y o g i 等在黎曼几何的框架内，给出了完整的几何分 析。拉普拉斯特征映射的基本思想就是用一个无向有权图来描述一个流形，保持 北京交通大学博士学位论文 图的局部邻接关系的情况下，通过用图的嵌入来找低维表示。拉普拉斯特征映射 认为在高维空间中离得很近的点投影到低维空间中的像也应该离得很近，最终求 解归结到拉普拉斯算子的广义特征值问题。 拉普拉斯特：征映射算法描述如下： 给定观测数据集( 毪= f ( y ) ) cr d ，共有聆个样本，采样白d 维嵌入流形， y = ( y f ) 是包含在欧氏空间r d 在嵌入流形上对应的低维坐标，求l 拉普拉斯特征 映射共有三个步骤 3 8 ： s t e p l ：构建一个具有心个顶点的邻接图g 。如果邻接图的两个顶点f 和，邻近 ( 可以用s 近邻或k 近邻算法确定其邻是否邻近；也可引入观测数据集的类标信息) ， 则g = 1 ，否贝, t j a f = 0 ： ，f1x 和x f 邻近 ( 2 1 ) u j t0 其它 s t e p 2 ：确定图的边权重矩阵矽。矩阵形的定义可以多种形式，如： = e - l l x l - 。x | 1 2 g 玎= 1 g u = o 虱( 2 2 ) 米用热核( h e a t k e r n e l ) 万法，兵