大数据课程报告

摘要流形学习办法作为一类新兴的非线性维数约简办法，重要目的是获取高维观察数据的低维紧致表达，探索事物的内在规律和本征构造，已经成为数据挖掘、模式识别和机器学习等领域的研究热点。流形学习办法的非线性本质、几何直观性和计算可行性，使得它在许多原则的toy数据集和实际数据集上都获得了令人满意的成果，然而它们本身还存在着某些普遍性的问题，例如泛化学习问题、监督学习问题和大规模流形学习问题等。因此，本文从流形学习办法存在的问题出发，在算法设计和应用（图像数据与蛋白质互相作用数据）等方面展开了一系列研究工作。首先对流形学习的典型办法做了具体对比分析，然后针对流形的泛化学习和监督学习、表征流形的局部几何构造、构造全局的正则化线性回归模型、大规模数据的流形学习等几个方面进行了重点研究，提出了三种有效的流形学习算法，并和有关研究成果进行了理论与实验上的比较，从而验证了我们所提算法的有效性。核心词：流形学习，维数约简，正交局部样条鉴别投影，局部多尺度回归嵌入目录TOC\o"1-4"\h\z\u目录 2第1章 研究背景 31.1 流形学习的研究背景 31.2 流形学习的研究现状 41.3 流形学习的应用 6第2章 流形学习办法综述 72.1 流形学习办法介绍 8第3章 流形学习办法存在的问题 113.1 本征维数预计 113.2 近邻数选择 123.3 噪声流形学习 123.4 监督流形学习 13第4章 总结 13研究背景流形学习的研究背景随着信息时代的到来，使得数据集更新更快、数据维度更高以及非构造化性等问题更突出。在科研研究的过程中不可避免地碰到大量的高维数据，这就需要一种技术能够使在保持数据信息足够完整的意义下从海量数据集中提取出有效而又合理的约简数据，满足人的存储需求和感知需要。流形学习这一非监督学习办法应运而生，引发越来越多机器学习和认知科学工作者的重视。而在海量的高维数据中，往往只有少量的有用信息，如果想快速高效的收集到人们想要的、有用的那些少量信息且快速的解决信息，这就需要某些核心技术的支持，即是必须采用对应的降维技术。而流形学习正是在数据降维方面有着重要的奉献。然而，降维的过程与《矩阵分析》中的内容有着亲密的关系。基于流形的降维办法能充足运用数据中所隐藏的低维有价值信息，进一步提高检索性能。Seung从神经心理学的角度提出“感知以流形的形式存在，视觉记忆也可能是以稳态的流形存储”，为流形提供了与人类认识有关的理由。流形学习的办法重要有主成分分析（PCA）、多维尺度化（MDS）、基于局部切空间排列法（LTSA）和基于等度规映射（ISOMAP）、局部线性嵌入算法（LLE）、拉普拉斯特性映射（LE）等。另外，流形学习办法在人脸识别、图像解决、模式识别、计算机视觉、认知科学、人工智能、人机交互等众多学科中有着广泛的应用。线性维数约简办法是通过在高维输入空间与低维子空间之间建立线性映射关系，把高维数据样本集投影到低维线性子空间。线性维数约简技术普通假设数据集采样于一种全局线性的高维观察空间。如果所要解决的数据集分布确实呈现出全局线性的构造，或者在一定程度上能够近似为全局线性构造，则这些办法能够有效地挖掘出数据集内在的线性构造，获得数据紧致的低维表达。在线性维数约简办法中，使用最广泛的算法有主分量分析（PrincipalComponentAnalysis,PCA）(Jolliffe,;TurkandPentland,1991)和线性鉴别分析（LinearDiscriminantAnalysis,LDA）(Dudaetal.,)。主分量分析（PCA）重要是根据高维数据在低维空间重构误差最小的原则，来寻找一组最优的单位正交向量基（即主分量），并通过保存数据分布方差较大的若干主分量来达成降维的目的。然而，众所周知，由于PCA算法没有运用数据样本的类别信息，因此它是一种非监督的线性维数约简办法。与PCA算法不同，LDA算法考虑到样本的类别信息，它是一种有监督的办法。基于各类样本服从高斯分布且不同类的协方差矩阵相似的假设，LDA算法在Fisher准则下选择最优的投影向量，以使得数据样本的类间散度最大而类内散度最小。由于LDA算法运用了样本的类别信息，而样本的类别信息普通有助于改善识别率，因此LDA算法更合用于分类问题。流形学习的研究现状流形学习假定输入数据是嵌入在高维观察空间的低维流形上，流形学习办法的目的是找出高维数据中所隐藏的低维流形构造。通过十数年的研究与探索，人们提出了大量的流形学习理论与算法。典型的流形学习办法有等距特性映射算法（ISOMAP）(Tenenbaumetal.,)、局部线性嵌入算法（LLE）(RoweisandSaul,;SaulandRoweis,)、Laplacian特性映射算法（LaplacianEigenmaps，LE）(BelkinandNiyogi,;BelkinandNiyogi,)、Hessian特性映射算法（Hessian-basedLocallyLinearEmbedding，HLLE）(DonohoandGrimes,)、最大差别展开算法（MaximumVarianceUnfolding，MVU）(Weinbergeretal.,;WeinbergerandSaul,;WeinbergerandSaul,;Weinbergeretal.,)、局部切空间排列算法（LocalTangentSpaceAlignment,LTSA）(ZhangandZha,)、黎曼流形学习算法（RiemannianManifoldLearning,RML）(LinandZha,;Linetal.,)和局部样条嵌入算法（LocalSplineEmbedding，LSE）(Xiangetal.,;Xiangetal.,)等。Tenenbaum提出的ISOMAP算法是多维尺度分析（MultidimensionalScaling,MDS）(CoxandCox,1994)在流形框架下的非线性推广，其核心思想是用测地距离替代欧氏距离来表征流形上数据点的内在几何关系。对于样本点和它的近邻点之间的测地距离用它们之间的欧氏距离来替代；对于样本点和近邻点之外的点之间的测地距离用它们之间的最短途径来替代。Bernstein等人证明了只要样本是随机抽取的，在样本集足够大且选择适宜近邻参数k时，近邻图上两点的最短途径能够逼近它们的测地距离(Bernsteinetal.,)。当应用于内蕴平坦的凸流形时，ISOMAP算法能够忠实地捕获数据内在的低维流形构造(DeSilvaandTenenbaum,)。ISOMAP算法的重要缺点在于：①对样本点的噪声比较敏感；②对于含有较大曲率或稀疏采样的数据集，不能发现其内在的本征构造；③需要计算全体数据集的测地距离矩阵，因此算法的时间复杂度较高。围绕ISOMAP算法，已经出现了许多有关的理论分析与研究工作。Balasubramanian等人对ISOMAP算法的拓扑稳定性进行了进一步探讨(BalasubramanianandSchwartz,)。对于数据分布所在的低维流形含有较大的内在曲率状况，deSilva和Tenenbaum提出了保角等距特性映射算法（conformalISOMAP）(DeSilvaandTenenbaum,)。为了减小ISOMAP算法的计算复杂度，deSilva和Tenenbaum提出了带标记的等距特性映射算法（LandmarkISOMAP）(DeSilvaandTenenbaum,)。针对ISOMAP算法对于数据集噪声敏感的问题，Choi等人通过观察图中的网络流提出了一种消除临界孤立点的办法以加强ISOMAP算法的拓扑稳定性(ChoiandChoi,)。在构建近邻图方面，Yang提出通过构造k连通图方式来确保近邻图的连通性，以提高测地距离的预计精度(Yang,)。年，Xiang等人提出了局部样条嵌入算法（LSE）(Xiangetal.,;Xiangetal.,)。Xiang认为，对于嵌入在高维输入空间的低维流形，非线性维数约简的任务事实上是寻找一组非线性的复合映射，即由局部坐标映射（LocalCoordinatizationMapping）与全局排列映射（GlobalAlignmentMapping）复合而成的兼容映射（CompatibleMapping）。在兼容映射的概念框架下，LSE算法首先通过主分量分析计算每个样本点局部邻域在切空间上的投影获得该邻域全部样本的局部坐标，从而保持流形的局部几何构造信息；然后采用Sobolev空间的一组样条函数把每个样本点的局部坐标映射成全局唯一的低维坐标。它们均是运用每个样本的局部切空间来捕获流形的局部几何，样本点在切空间的投影来表达样本点的局部坐标。然而它们的重要区别在于全局排列，LTSA算法是运用仿射变换来进行全局排列，而LSE算法是运用样条函数来获得全局唯一的坐标。因此相对于LTSA而言，LSE算法能够实现更小的重构误差。LSE算法的重要缺点在于：一是无法保持全局尺度信息；二是不能学习含有较大曲率的低维流形构造。除此，如何选择满足规定的样条函数也是一种值得考虑的问题。不同流形学习算法的区别在于所尝试保持流形的局部邻域构造信息以及运用这些信息构造全局嵌入的办法不同，与以往的维数约简办法相比，流形学习能够有效地探索非线性流形分布数据的内在规律与性质。但是在实际应用中流形学习办法仍然存在某些缺点，例如本征维数预计问题、样本外点学习问题、监督流形学习问题和噪声流形学习问题等。为理解决这些问题，有关的算法也不停涌现出来。Freedman等提出了一种基于简化单纯复形的流形重构办法来自动预计流形的本征维数(Freedman,)。为理解决样本外点学习问题，研究人员分别在流形学习的线性化、核化和张量化等方面作了有益的探索(Yanetal.,)。Geng等将样本的类别信息融入到ISOMAP算法，提出了一种用于可视化和分类的有监督的等距特性映射算法（S-ISOMAP）(Gengetal.,)。Zhang等提出了一种基于局部线性平滑的流形学习消噪模型(ZhangandZha,)。这些办法的提出在一定程度上缓和了现在流形学习办法中存在的某些问题，但是还需要进一步充实和完善。流形学习的应用现在，流形学习办法的应用可归纳为下列几个方面：数据的可视化。流形学习办法在高维数据的可视化方面有了广泛的应用。人不能直接感知高维数据的内部构造，但对三维下列数据的内在构造却有很强的感知能力。由于流形学习办法能够发现高维观察数据中蕴含的内在规律和本征构造，并且这种规律在本质上不依赖于我们实际观察到的数据维数。因此我们能够通过流形学习办法对高维输入数据进行维数约简，使高维数据的内部关系和构造在低于三维的空间中展示出来，从而使人们能够直观地认识和理解高维的非线性数据的内在规律，达成可视化的目的。信息检索。随着多媒体和网络技术的迅猛发展，图像和文本信息的应用日益广泛，对规模逐步庞大的图像和文本数据库如何进行有效的管理已成为亟待解决的问题。灵活、高效、精确的信息检索方略是解决这一问题的核心技术之一。这些图像和文本信息呈现出高维、大规模、非线性构造，运用流形学习办法来解决这些信息，在大大减少时间和空间计算复杂度的同时，能够有效地保存这些信息在原始高维空间的相似性。图像解决。流形学习给图像解决领域提供了一种强有力的工具。众所周知，图像解决与图像中物体的轮廓以及骨架等亲密有关。如果我们把图像中物体的轮廓以及骨架等当作是嵌入在二维平面中的一维流形或者由一组一维流形构成，那么显然流形学习办法凭借其强大的流形逼近能力能够应用于图像解决领域。流形学习办法综述流形学习办法作为一种新兴的非线性维数约简办法，重要目的是获取高维观察数据的低维紧致表达，探索事物的内在规律和本征构造，已经成为数据挖掘、模式识别和机器学习等领域的研究热点。本章首先探讨了流形学习的基础性问题，即高维数据分析的流形建模问题；然后根据保持流形几何特性的不同，把现有的流形学习办法划分为全局特性保持办法和局部特性保持办法，并介绍了每一类办法中有代表性的流形学习算法的基本原理，对多个流形学习算法进行性能比较和可视化分析，最后就流形学习办法普遍存在的本征维数预计、近邻数选择、噪声流形学习、样本外点学习和监督流形学习问题等进行了分析和讨论。流形学习办法介绍流形学习的定义：流形是局部含有欧氏空间性质的空间。假设数据是均匀采样于一种高维欧氏空间中的低维流形，流形学习就是从高维采样数据中恢复低维流形构造，即找到高维空间中的低维流形，并求出对应的嵌入映射，以实现维数约简或者数据可视化。它是从观察到的现象中去寻找事物的本质，找到产生数据的内在规律。流形学习用数学语言描述是：令Y且:Y是一种光滑的嵌套，其中D>>d。那么流形学习的目的是基于上的一种给定被观察数据集合去恢复Y与，也就是在Y中随机产生隐藏的数据，然后通过映射到观察空间，使得。从流形学习的定义中能够看出，这是一种把数据从高维映射到低维的过程，用到了线性变换，固然少不了矩阵的分解及其基本运算。2.1.1多维尺度分析（MultidimensionalScaling,MDS）多维尺度分析（MultidimensionalScaling,MDS）是一种典型的线性降维办法，其重要思想是：根据数据点间的欧氏距离，构造关系矩阵，为了尽量地保持每对观察数据点间的欧氏距离，只需对此关系矩阵进行特性分解，从而获得每个数据在低维空间中的低维坐标。设给定的高维观察数据点集为，，观察数据点对,间的欧氏距离为，传统MDS的算法环节以下：a)首先根据求出的两点之间的欧氏距离构造n阶平方欧式距离矩阵。b)将矩阵A进行双中心化计算，即计算（其中H为中心化矩阵，，将矩阵H左乘和右乘时称为双中心化）。c)计算低维坐标Y。即将B奇异值分解，设B的最大的d个特性值，对应特性向量，则d维低维坐标为。即使作为线性办法，MDS在流形学习中不能有效发现内在低维构造。但是从这一基本的算法中我们能够清晰的看出矩阵分析在流形学习研究中的应用。在这个MDS算法中，运用到了矩阵中的线性空间变换、矩阵特性值和特性向量的计算、矩阵的中心化计算、矩阵的奇异值的分解等有关知识点。想象一下，如果没有这些知识点做基础，这些算法如何进行。2.1.2等距特性映射（ISOMAP）（1）基本思想:Tenenbaum等人提出的等距特性映射算法（ISOMAP）是建立在多维尺度分析（MDS）基础上的一种非线性维数约简办法。ISOMAP算法运用全部样本点对之间的测地距离矩阵来替代MDS算法中的欧氏距离矩阵，以保持嵌入在高维观察空间中内在低维流形的全局几何特性。算法的核心是计算每个样本点与全部其它样本点之间的测地距离。对于近邻点，运用输入空间的欧氏距离直接得到其测地距离；对于非近邻点，运用近邻图上两点之间的最短途径近似测地距离。然后对于构造的全局测地距离矩阵，运用MDS算法在高维输入空间与低维嵌入空间之间建立等距映射，从而发现嵌入在高维空间的内在低维表达(Tenenbaumetal.,)。（2）算法流程<1>构造近邻图G<2>计算最短途径<3>计算d维嵌入(3)算法分析ISOMAP算法是一种保持全局几何特性的办法，它的低维嵌入成果能够反映出高维观察样本所在流形上的测地距离。如果高维观察样本所在的低维流形与欧氏空间的一种子集是整体等距的，且与样本所在流形等距的欧氏空间的子集是一种凸集，那么ISOMAP算法能够获得比较抱负的嵌入成果。但是当流形曲率较大或者流形上有“孔洞”，即与流形等距的欧氏空间的子集非凸时，流形上的测地距离预计会产生较大的误差，造成嵌入成果产生变形。从算法的时间复杂度来看，ISOMAP算法有两个计算瓶颈(DeSilvaandTenenbaum,)。第一种是计算n×n的最短途径距离矩阵DG。当使用Floyd算法时，计算复杂度为O(n3)；若采用Dijkstra算法，可将计算复杂度减少到O(kn2logn)（k为近邻数大小）(Cormen,)。第二个计算瓶颈源于应用MDS时的特性分解。由于距离矩阵是稠密的，因此特性分解的计算复杂度为O(n3)。从中我们能够看出，随着样本个数n的增大，ISOMAP算法计算效率低下的问题会变得十分突出。2.1.3局部线性嵌入（LLE）1、基本思想与ISOMAP和MVU算法不同，局部线性嵌入算法（LLE）是一种局部特性保持办法。LLE算法的核心是保持降维前后近邻之间的局部线性构造不变。算法的重要思想是假定每个数据点与它的近邻点位于流形的一种线性或近似线性的局部邻域，在该邻域中的数据点能够由其近邻点来线性表达，重建低维流形时，对应的内在低维空间中的数据点保持相似的局部近邻关系，即低维流形空间的每个数据点用其近邻点线性表达的权重与它们在高维观察空间中的线性表达权重相似，而各个局部邻域之间的互相重叠部分则描述了由局部线性到全局非线性的排列信息(RoweisandSaul,)。这样就能够把高维输入数据映射到全局唯一的低维坐标系统。2、算法流程LLE算法的基本环节分为三步：选择邻域计算重构权值矩阵W求低维嵌入Y3、算法分析通过前面算法描述我们不难发现，LLE算法能够学习任意维含有局部线性构造的低维流形。它以重构权值矩阵作为高维观察空间与低维嵌入空间之间联系的桥梁，使得数据点与其近邻点在平移、旋转和缩放等变化下保持近邻关系不变。并且LLE算法含有解析的全局最优解，无需迭代。在算法的计算复杂度上，选择邻域的计算复杂度为O(Dn2)，计算重构权值矩阵的计算复杂度为O((D+k)k2n)，求解低维嵌入Y的计算复杂度为O(dn2)。因此与ISOMAP和MVU算法相比，LLE算法的计算复杂度要小得多。但LLE算法也存在某些缺点：①由于LLE算法只是保持局部近邻的重构权值关系，并不是保持距离关系，因此，LLE算法普通不能较好的恢复出含有等距性质的流形。②LLE算法但愿样本集均匀稠密采样于低维流形，因此，对于受噪声污染、样本密度稀疏或互有关联较弱的数据集，在从高维观察空间到低维嵌入空间的映射过程中，可能会将互有关联较弱的远点映射到局部近邻点的位置，从而破坏了低维嵌入成果。流形学习办法存在的问题流形学习相对于传统的线性维数约简办法来说，它能够更加好地发现高维复杂非线性数据内在的几何构造与规律。但其多个算法本身还存在着某些普遍性的问题，例如本征维数预计问题、近邻数选择问题、噪声流形学习问题、泛化学习问题和监督学习问题等。本小节将对这些问题进行简要的分析和讨论。本征维数预计本征维数预计是流形学习的一种基本问题(赵连伟etal.,)。本征维数普通被定义为描述数据集中全部数据所需要的自由参数（或独立坐标）的最小数目。它反映了隐藏在高维观察数据中潜在低维流形的拓扑属性。在非线性维数约简过程中，本征维数预计的精确与否对低维空间的嵌入成果有着重要的影响。如果本征维数预计过大，将会保存数据的冗余信息，使嵌入成果中含有噪声；相反如果本征维数预计过小，将会丢失数据的有用信息，造成高维空间中不同的点在低维空间可能会交叠。因此，设计稳定可靠的本征维数预计办法将有助于流形学习算法的应用和性能的改善。现在现有的本征维数预计办法大致分为两大类：特性映射法和几何学习法(Camastra,)。特性映射法涉及全局PCA办法(Bennett,1969)、局部PCA办法(BruskeandSommer,1998;FukunagaandOlsen,1971)和多维尺度分析办法(CoxandCox,)，它重要运用了数据分布的本征特性是数据的局部特性的基本思想，对局部数据进行特性分解，选用对应特性值最大的特性向量作为本征特性。显然，这类办法所预计的本征维数大小在很大程度上取决于数据的局部邻域划分和阈值的选择，因此特性映射办法不能提供本征维数的可靠预计。几何学习法重要基于近来邻距离（NearestNeighborDistances）或分形维（FractalDimension）(Camastra,)来探索数据集所蕴含的几何信息，这类办法普通需要充足的样本数，因此，对于样本数少、观察空间维数较高的状况，经常会出现本征维数欠预计的状况。近邻数选择流形学习探测低维流形构造成功与否在很大程度上取决于近邻数的选择(Zeng,)，然而在构造近邻图时如何选择一种适宜的近邻数是一种公开的问题。如果近邻数选择过大，将会产生“短路边”现象（“short-circuit”edges），从而严重破坏原始流形数据的拓扑连通性。噪声流形学习当观察数据均匀稠密采样于一种抱负的低维光滑流形时，流形学习办法能够成功地挖掘出其内在的低维构造和本质规律。但是在实际应用中，我们经常发现高维采样数据由于受多个因素的影响，普通总是存在着噪声和污染，这将势必影响流形学习算法的低维嵌入成果。监督流形学习现有的流形学习办法多数用于无监督学习状况，如解决降维与数据可视化等问题。当已知数据的类别信息，如何运用这些信息有效地改善原始流形学习算法的分类识别能力是监督流形学习所要解决的问题。从数据分类的角度来看，人们但愿高维观察数据通过维数约简后在低维空间中类内差别小而类间差别大，从而有助于样本的分类识别。原始的流形学习算法都是无监督学习过程，某些引进监督信息的改善算法纷纷被提出来(Lietal.,;Zhaoetal.,)。这些办法的基本思想是运用样本的类别信息指导构建有监督的近邻图，然后运用流形学习办法进行低维嵌入。尽管这些办法能够获得较好的分类成果，但是这种通过类别属性构建的近邻图往往会被分割成多个互不相连的子图，而不是一种完整的近邻图，这就给原始流形学习算法的最后应用带来了很大的不便。总结流形学习是一种含有基础性、前瞻性的研究方向，其研究成果和技术已经立刻应用于模式识别、计算机视觉、图像解决等有关领域。如高维数据的可视化、可听化；基于内容检索的模型；视频中三维对象的跟踪和检测；从静态二维图像中进行三维对象的姿态预计和识别；二维和三维对象的形状重构；从运动中构建构造、从阴影中成形等。另外流形学习还应用于自然语言解决、基因体现分析等生物信息解决领域，特别是在基因体现分析中，用于检测和分辨不同的疾病和疾病类型。

尽管流形学习的算法和应用在过去的几年中已经获得了丰硕的成果，但是由于其数学理论基础较为深厚复杂，以及多个学科之间交叉融合，因此仍有许多亟需研究和解决的问题，特别在下述几个方面：

1.现在已有诸多流形学习算法，但诸多算法只是建立在实验的基础之上，并没有充足理论基础支持，因此我们首先要进一步探索能够有效学习到流形局部几何和拓扑构造的算法，提高流形投影算法的性能，另外更重要的是要不停完善理论基础。

2.各支几何都是研究空间在变换群下的不变性，微分几何亦是如此。而诸多状况下我们正需要这种不变性，因此研究局部样本密度、噪声水平、流形的正则性、局部曲率、挠率构造的交互作用对流形学习的研究有主动增进作用。

3.统计学习理论得到充足发展并逐步成熟，流形学习理论在其基础上发展自然能够把统计学中有用的技术应用于流形学习中，如流形上的取样和MonteCarlo预计、假设检查，以及流形上有关不变测度的概率分布密度问题，都值得进一步研究。

4.现在大部分学习算法都是基于局部的，而基于局部算法一种很大缺点就在于受噪声影响较大，因此要研究减小局部办法对于噪声和离群值的影响，提高学习算法鲁棒性及泛化能力。5.谱办法对噪声十分敏感。但愿大家自己做做实验体会一下，流形学习中谱办法的脆弱。6.采样问题对成果的影响。7.一种最尴尬的事情莫过于，如果用来做识别，流形学习线性化的办法比原来非线性的办法效果要好得多，如果用原始办法做识别，那个效果叫一种差。也正由于此，使诸多人对流形学习产生了怀疑。8.把偏微分几何办法引入到流形学习中来是一种很有但愿的方向。这样的工作在近来一年已有出现的迹象。

参考文献[1]R.BasriandD.W.Jacobs.L