大数据课程报告

大数据课程报告摘要流形学习方法作为一类新兴的非线性维数约简方法，主要目标是获取高维观测数据的低维紧致表示，探索事物的内在规律和本征结构，已经成为数据挖掘、模式识别和机器学习等领域的研究热点。流形学习方法的非线性本质、几何直观性和计算可行性，使得它在许多标准的toy数据集和实际数据集上都取得了令人满意的结果，然而它们本身还存在着一些普遍性的问题，比如泛化学习问题、监督学习问题和大规模流形学习问题等。因此，本文从流形学习方法存在的问题出发，在算法设计和应用（图像数据与蛋白质相互作用数据）等方面展开了一系列研究工作。首先对流形学习的典型方法做了详细对比分析，然后针对流形的泛化学习和监督学习、表征流形的局部几何结构、构造全局的正则化线性回归模型、大规模数据的流形学习等几个方面进行了重点研究，提出了三种有效的流形学习算法，并和相关研究成果进行了理论与实验上的比较，从而验证了我们所提算法的有效性。关键词：流形学习，维数约简，正交局部样条判别投影，局部多尺度回归嵌入目录目录.................................................................................................................................................II第1章研究背景..(1)1.1流形学习的研究背景(1)1.2流形学习的研究现状(2)1.3流形学习的应用(4)第2章流形学习方法综述(5)2.1流形学习方法介绍(6)第3章流形学习方法存在的问题(9)3.1本征维数估计(9)3.2近邻数选择(10)3.3噪声流形学习(10)3.4监督流形学习(11)第4章总结(11)第1章研究背景1.1流形学习的研究背景随着信息时代的到来，使得数据集更新更快、数据维度更高以及非结构化性等问题更突出。在科研研究的过程中不可避免地遇到大量的高维数据，这就需要一种技术能够使在保持数据信息足够完整的意义下从海量数据集中提取出有效而又合理的约简数据，满足人的存储需求和感知需要。流形学习这一非监督学习方法应运而生，引起越来越多机器学习和认知科学工作者的重视。而在海量的高维数据中，往往只有少量的有用信息，如果想快速高效的搜集到人们想要的、有用的那些少量信息且快速的处理信息，这就需要一些关键技术的支持，即是必须采用相应的降维技术。而流形学习正是在数据降维方面有着重要的贡献。然而，降维的过程与《矩阵分析》中的内容有着密切的关系。基于流形的降维方法能充分利用数据中所隐藏的低维有价值信息，进一步提高检索性能。Seung从神经心理学的角度提出“感知以流形的形式存在，视觉记忆也可能是以稳态的流形存储”，为流形提供了与人类认识相关的理由。流形学习的方法主要有主成分分析（PCA）、多维尺度化（MDS）、基于局部切空间排列法（LTSA）和基于等度规映射（ISOMAP）、局部线性嵌入算法（LLE）、拉普拉斯特征映射（LE）等。另外，流形学习方法在人脸识别、图像处理、模式识别、计算机视觉、认知科学、人工智能、人机交互等众多学科中有着广泛的应用。线性维数约简方法是通过在高维输入空间与低维子空间之间建立线性映射关系，把高维数据样本集投影到低维线性子空间。线性维数约简技术通常假设数据集采样于一个全局线性的高维观测空间。如果所要处理的数据集分布确实呈现出全局线性的结构，或者在一定程度上可以近似为全局线性结构，则这些方法能够有效地挖掘出数据集内在的线性结构，获得数据紧致的低维表示。在线性维数约简方法中，使用最广泛的算法有主分量分析（PrincipalComponentAnalysis,PCA）(Jolliffe,2021;TurkandPentland,1991)和线性判别分析（LinearDiscriminantAnalysis,LDA）(Dudaetal.,2021)。主分量分析（PCA）主要是根据高维数据在低维空间重构误差最小的原则，来寻找一组最优的单位正交向量基（即主分量），并通过保留数据分布方差较大的若干主分量来达到降维的目的。然而，众所周知，由于PCA算法没有利用数据样本的类别信息，所以它是一种非监督的线性维数约简方法。与PCA算法不同，LDA算法考虑到样本的类别信息，它是一种有监督的方法。基于各类样本服从高斯分布且不同类的协方差矩阵相同的假设，LDA算法在Fisher准则下选择最优的投影向量，以使得数据样本的类间散度最大而类内散度最小。由于LDA算法利用了样本的类别信息，而样本的类别信息通常有助于改善识别率，因此LDA算法更适用于分类问题。1.2流形学习的研究现状流形学习假定输入数据是嵌入在高维观测空间的低维流形上，流形学习方法的目的是找出高维数据中所隐藏的低维流形结构。经过十多年的研究与探索，人们提出了大量的流形学习理论与算法。经典的流形学习方法有等距特征映射算法（ISOMAP）(Tenenbaumetal.,2021)、局部线性嵌入算法（LLE）(RoweisandSaul,2021;SaulandRoweis,2021)、Laplacian特征映射算法（LaplacianEigenmaps，LE）(BelkinandNiyogi,2021;BelkinandNiyogi,2021)、Hessian特征映射算法（Hessian-basedLocallyLinearEmbedding，HLLE）(DonohoandGrimes,2021)、最大差异展开算法（MaximumVarianceUnfolding，MVU）(Weinbergeretal.,2021;WeinbergerandSaul,2021;WeinbergerandSaul,2021;Weinbergeretal.,2021)、局部切空间排列算法（LocalTangentSpaceAlignment,LTSA）(ZhangandZha,2021)、黎曼流形学习算法（RiemannianManifoldLearning,RML）(LinandZha,2021;Linetal.,2021)和局部样条嵌入算法（LocalSplineEmbedding，LSE）(Xiangetal.,2021;Xiangetal.,2021)等。Tenenbaum提出的ISOMAP算法是多维尺度分析（MultidimensionalScaling,MDS）(CoxandCox,1994)在流形框架下的非线性推广，其核心思想是用测地距离代替欧氏距离来表征流形上数据点的内在几何关系。对于样本点和它的近邻点之间的测地距离用它们之间的欧氏距离来代替；对于样本点和近邻点之外的点之间的测地距离用它们之间的最短路径来代替。Bernstein等人证明了只要样本是随机抽取的，在样本集足够大且选择适当近邻参数k时，近邻图上两点的最短路径可以逼近它们的测地距离(Bernsteinetal.,2021)。当应用于内蕴平坦的凸流形时，ISOMAP算法能够忠实地捕获数据内在的低维流形结构(DeSilvaandTenenbaum,2021)。ISOMAP算法的主要缺点在于：①对样本点的噪声比较敏感；②对于具有较大曲率或稀疏采样的数据集，不能发现其内在的本征结构；③需要计算全体数据集的测地距离矩阵，因此算法的时间复杂度较高。围绕ISOMAP算法，已经出现了许多相关的理论分析与研究工作。Balasubramanian等人对ISOMAP算法的拓扑稳定性进行了深入探讨(BalasubramanianandSchwartz,2021)。对于数据分布所在的低维流形具有较大的内在曲率情况，deSilva和Tenenbaum提出了保角等距特征映射算法（conformalISOMAP）(DeSilvaandTenenbaum,2021)。为了减小ISOMAP算法的计算复杂度，deSilva和Tenenbaum提出了带标记的等距特征映射算法（LandmarkISOMAP）(DeSilvaandTenenbaum,2021)。针对ISOMAP算法对于数据集噪声敏感的问题，Choi等人通过观察图中的网络流提出了一种消除临界孤立点的方法以加强ISOMAP算法的拓扑稳定性(ChoiandChoi,2021)。在构建近邻图方面，Yang提出通过构造k连通图方式来确保近邻图的连通性，以提高测地距离的估计精度(Yang,2021)。2021年，Xiang等人提出了局部样条嵌入算法（LSE）(Xiangetal.,2021;Xiangetal.,2021)。Xiang认为，对于嵌入在高维输入空间的低维流形，非线性维数约简的任务实际上是寻找一组非线性的复合映射，即由局部坐标映射（LocalCoordinatizationMapping）与全局排列映射（GlobalAlignmentMapping）复合而成的兼容映射（CompatibleMapping）。在兼容映射的概念框架下，LSE算法首先通过主分量分析计算每个样本点局部邻域在切空间上的投影获得该邻域所有样本的局部坐标，从而保持流形的局部几何结构信息；然后采用Sobolev空间的一组样条函数把每个样本点的局部坐标映射成全局唯一的低维坐标。它们均是利用每个样本的局部切空间来捕获流形的局部几何，样本点在切空间的投影来表示样本点的局部坐标。然而它们的主要区别在于全局排列，LTSA算法是利用仿射变换来进行全局排列，而LSE算法是利用样条函数来获得全局唯一的坐标。因此相对于LTSA而言，LSE算法能够实现更小的重构误差。LSE算法的主要缺点在于：一是无法保持全局尺度信息；二是不能学习具有较大曲率的低维流形结构。除此，如何选择满足要求的样条函数也是一个值得考虑的问题。不同流形学习算法的区别在于所尝试保持流形的局部邻域结构信息以及利用这些信息构造全局嵌入的方法不同，与以往的维数约简方法相比，流形学习能够有效地探索非线性流形分布数据的内在规律与性质。但是在实际应用中流形学习方法仍然存在一些缺点，比如本征维数估计问题、样本外点学习问题、监督流形学习问题和噪声流形学习问题等。为了解决这些问题，相关的算法也不断涌现出来。Freedman等提出了一种基于简化单纯复形的流形重构方法来自动估计流形的本征维数(Freedman,2021)。为了解决样本外点学习问题，研究人员分别在流形学习的线性化、核化和张量化等方面作了有益的探索(Yanetal.,2021)。Geng等将样本的类别信息融入到ISOMAP算法，提出了一种用于可视化和分类的有监督的等距特征映射算法（S-ISOMAP）(Gengetal.,2021)。Zhang等提出了一种基于局部线性平滑的流形学习消噪模型(ZhangandZha,2021)。这些方法的提出在一定程度上缓解了目前流形学习方法中存在的一些问题，但是还需要进一步充实和完善。1.3流形学习的应用目前，流形学习方法的应用可归纳为以下几个方面：1)数据的可视化。流形学习方法在高维数据的可视化方面有了广泛的应用。人不能直接感知高维数据的内部结构，但对三维以下数据的内在结构却有很强的感知能力。由于流形学习方法可以发现高维观测数据中蕴含的内在规律和本征结构，而且这种规律在本质上不依赖于我们实际观测到的数据维数。因此我们可以通过流形学习方法对高维输入数据进行维数约简，使高维数据的内部关系和结构在低于三维的空间中展示出来，从而使人们能够直观地认识和了解高维的非线性数据的内在规律，达到可视化的目的。2)信息检索。随着多媒体和网络技术的迅猛发展，图像和文本信息的应用日益广泛，对规模逐渐庞大的图像和文本数据库如何进行有效的管理已成为亟待解决的问题。灵活、高效、准确的信息检索策略是解决这一问题的关键技术之一。这些图像和文本信息呈现出高维、大规模、非线性结构，利用流形学习方法来处理这些信息，在大大降低时间和空间计算复杂度的同时，能够有效地保留这些信息在原始高维空间的相似性。3)图像处理。流形学习给图像处理领域提供了一个强有力的工具。众所周知，图像处理与图像中物体的轮廓以