61高维数据的低维表示综述

高维数据的低维表示综述一、研究背景在科学研究中，我们经常要对数据进行处理。而这些数据通常都位于维数较高的空间，例如，当我们处理200个256*256的图片序列时，通常我们将图片拉成一个向量，这样，我们得到了65536*200的数据，如果直接对这些数据进行处理，会有以下问题：首先，会出现所谓的“位数灾难”问题，巨大的计算量将使我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接对他们进行处理，不会得到理想的结果。所以，通常我们需要首先对数据进行降维，然后对降维后的数据进行处理。降维的基本原理是把数据样本从高维输入空间通过线性或非线性映射投影到一个低维空间，从而找出隐藏在高维观测数据中有意义的低维结构。（8）之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余：·有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的·有些变量和其他的变量有很强的相关性(例如是其他变量的线性组合或是其他函数依赖关系)，可以找到一组新的不相关的变量。（3）从几何的观点来看，降维可以看成是挖掘嵌入在高维数据中的低维线性或非线性流形。这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的点在嵌入空间中也相互靠近。（12）数据降维是以牺牲一部分信息为代价的，把高维数据通过投影映射到低维空间中，势必会造成一些原始信息的损失。所以在对高维数据实施降维的过程中如何在最优的保持原始数据的本质的前提下，实现高维数据的低维表示，是研究的重点。（8）二、降维问题1．定义定义1.1降维问题的模型为(,)XF，其中D维数据空间集合1NllXx（一般为DR的一个子集），映射F:FXY(),xyFxY是d空间集合（一般是dR，dD）的一个子集，我们称F是数据集X（到Y）的降维。若F为X的线性函数，则称F为线性降维；否则，称为非线性降维。定义1.2称映射1F1:FYX1()yxFy为嵌入映射。（8）2．分类针对降维问题的目的和待处理数据集合表象维数的多少，对其进行初步的、粗略的分类如下：·硬降维问题：数据维数从几千到几万甚至几十万的变化，此时需要对数据集进行“严厉”的降维，以至于达到便于处理的大小，如图像识别、分类问题以及语音识别问题等。·软降维问题：此时数据集合的维数不是太高，降维的需求不是非常的迫切。如社会科学、心理学以及多元统计分析领域皆属于此类。·可视化问题：此时数据集合的绝对维数不是很高，但为了便于利用人们的直观洞察力，即为了可视化，我们将其降到2或3维。虽然我们可以可视化更高维数的数据，但是它们通常难于理解，不能产生数据空间的合理形态。若我们还考虑时间变量的话可以对降维问题进行更加进一步的分类，静态降维问题和动态降维问题。后者对于时间序列来讲是有用的，如视频序列、连续语音信号等的处理。（4）3．方法介绍如何将高维数据表示在低维空间中，并由此发现其内在结构是高维信息处理研究的关键问题之一。实际处理中，由于线性方法具有简单性、易解释性、可延展性等优点，使得线性降维在高维数据处理中是一个主要研究方向。已有的线性维数约简方法，主要包括主成分分析(PrincipalComponentAnalysis，PCA)[16]、独立成分分析(IndependentComponentAnalysis，ICA)、线性判别分析ineardiscriminantanalysis(LDA)[17]、Fisher判别分析(FisherDiscriminantAnalysis，FDA)、主曲线(PrincipalCurves)、投影寻踪(ProjectionPursuit,PP)、多维尺度方法(MultidimensionalScaling，MDS)等。这些方法实际是在不同优化准则之下，寻求最佳线性模型，这也是线性维数约简方法的共性。（10）通过消除数据建模过程中的全局线性假设，Sammon提出了一种非线性映射，即Sammon映射(SM)，该算法能够保持输入样本之间的相关距离；Hastie提出了principalcurves(PC)，其定义为通过概率分布或数据中间的光滑曲线；Kohonen基于自组织神经网络提出了self-organizingmap(SOM)用来保存数据空间的拓扑属性；Scholkopf等应用Mercer核将PCA扩展为KernelPCA(KPCA)，该算法在高维空间中计算主分量，而该高维空间由输入空间经某种非线性映射得到。Mika等采用相同的思想来非线性扩展LDA，从而提出了kernelLDA（KLDA）；然而，基于核的方法其难点在于如何选择一个合适的核函数，一个好的核函数可以使数据在特征空间上线性可分或者近似线性可分，但并不是所选核函数对于每一种数据都适用。核函数的选择反映了人们对问题的先验知识，在实际的应用中往往是经验地选择某种核函数，比如径向基函数(RadialBasisFunction，RBF)。同时，在使用核函数时不必知道具体的特征空间，使得核函数方法缺乏物理直观性，这也是核函数方法的一个缺点。（10）最近兴起的流形学习算法也是用来维数约减的非线性方法，并且依靠它们在探测嵌入在高维空间中低维流形的能力和灵活性而被广泛应用。具有代表性的流形学习算法包括等距映射(IsometricMapping，Isomap)、局部线性嵌入方法(LocallyLinearEmbedding，LLE)、Laplacian特征映射(LaplacianEigenmap，LE)、局部切空间排列方法(LocalTangentSpaceAlignment，LTSA)、Hessian等距映射(Hessianeigenmaps，HLLE)和最大方差展开(maximumvarianceunfolding，MVU)。其中，LLE运用线性系数，来表达局部几何，该系数能够重建一个给定的样本点利用其近邻点，然后寻找一个低维空间，在该空间中这些线性系数仍然可以用来重建相应的点；ISOMAP作为MDS的变种，能够保存点对之间的全局的测地线距离；LE通过对一个描述了点对之间邻域关系的无向图的操作，来保持数据之间的近邻关系。HLLE先通过估计邻域上的Hessian而构建一矩阵，然后在此矩阵上运用特征值分解而得到最终的低维坐标。LTSA运用局部切信息作为局部几何的表达，然后将这些切信息在全局中排列从而得到最终的全局坐标。MVU不是一个绝对的局部方法而是一个介于局部和全局之间的方法，因为MVU不仅保存近邻点之间的几何关系而且在它的目标函数中考虑了全局点对之间的距离。除了基于谱分析的流形学习的算法，基于概率参数模型，Rowels提出了globalcoordination(GC)；Teh和Roweis开发了locallylinearcoordination(LLC)；Brand提出了manifoldcharting(Charting)。这些方法也属于流形学习的重要范畴。然而，这些非线性的算法却不能够为样本提供一个外在的映射，也就是说，它们很难被应用于识别问题。但是，一些基于谱分析的算法由于其具有特殊的特征分解机制而能够较为容易的扩展为线性算法，其线性化可以通过在解决优化的过程中施加线性逼近来实现。Localitypreservingprojection(LPP)作为LE的线性化是其中最早提出的算法。后来提出的还包括neighborhoodpreservingembedding(NPE)，LLE的线性化扩展，和orthogonalneighborhoodpreservingprojections(ONPP)，LLE的正交线性化扩展。这种线性化扩展使流形学习的思想更能够应用到现实世界中。图1.1给出了以上所提提及的降维算法的分类图。在谱方法的线性化扩展中，LPP可以被看作为基于图结构的最具代表性的算法，在接下来的几年中，又不断地有这种基于图的算法被提出，从而进一步完善了这种基于图的框架。Cai等对LPP算法分别对监督设置和非监督设置两种情况作了系统的分析，并且将LDA用这种基于图的框架重新公式化。Yan等提出了一种一般性的框架即“图嵌入”，来统一各种各样的降维算法。基于此种框架，一种新的线性算法，marginalfisheranalysis（MFA）将开发出来。MFA不同于LPP其只用一个图来描述数据的几何结构，该算法采用了两个图，其中一个为固有图（intrinsicgraph），它用来刻画数据的类内紧凑性；而另一个图为惩罚图（penaltygraph），用来描述数据类间的分离性。因此，MFA比LPP更具有判别性。Chen等同时提出的localdiscriminantembedding（LDE）算法在本质上与MFA的思想是相同的。（5）非线性降维方法与线性降维方法相比的一个显著特点是，分析中的局部性(数据集合经常满足的一个简单假设)。原因在于对数据集合的内蕴结构而言，有下列特性：·由泰勒定理，任何可微函数在一点的充分小的邻域之内满足线性性。形象的来讲，相当于认为曲面流形可由大小不一的局部线性块拼接而成；·数据流形经常是由许多可分割的子流形所组成；·数据流形的本征维数沿着流形不断的发生变化，只有局部性才能抓住其根本特性。（4）三、常见降维方法（一）线性1.主成分分析(PrincipalComponentAanlysisPCA)[1]PCA将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息越多，反之提供的信息就越少。它是在损失很少的信息的前提下把多个指标转化为几个综合指标的一种多元统计方法。它具有概念简单，计算方便以及最优线性重构误差等优良的特性。PCA是一种全局算法，它可以较好地揭示具有线性结构的高维数据集的全降维线性流行学习概率参数模型全局谱分析局部全局局部早期的非线性PCAMVUISOMAPChartingLLCKernelPCSMSOMGCLDALPPNPELLELLTSAONPPLELTSAHLLE线性化局分布。然而对于嵌入在高维空间中具有非线性流形结构的数据，PCA很难学习出隐含在数据集中的低维流形结构。PCA假设数据之间的关系是线性的。它在保存原始高维数据协方差结构的基础上计算低维表达，也就是最大化总体方差。它的目标函数可以写为：2121=argmaxargmax()argmax()..PCAPCAPCANmPCAiUiNTmTTPCAiPCATPCAPCAPCAdUUiUyyUxxtrUSUstUUI其中，1miyyN，1mixxN，且TS为总体离散矩阵：i=1=()()TNTiiSxxxx。对转换矩阵做尺度约束d=TPCAPCAUUI，其中dI为dd单位矩阵。则目标函数可以写为：argmax()PCATPCATPCAUtrUSU，..TPCAPCAdstUUI上式问题可以转化为TS的标准的特征值问题：PCA的最优转换矩阵为TS的d个最大的特征值所对应的d个m维特征向量。2.线性判别法(LinearDiscriminantAnalysisLDA)[2]其基本思想是投影，首先找出特征向量，把这些数据投影到一个低维的方向，使得投影后不同的组之间尽可能的分开，而同一组内的的样本比较靠拢，然后在新空间中对样本进行分类。通过最小化类内离散矩阵WS的秩而最大化类间离散矩阵BS的秩，来寻找一个子空间来区分不同的类别。WS和BS分别定义如下：()()()()i=11=()()iNCiiiiTWjjjSxmxm()()1()()CiiTBiiSNmmmm其中，iN是第i个类中样本的个数；()ijx是第i个样本中第j个样本。()im为第i个类的质心；m用来表示所有样本的质心，C为样本的类别数。LDA则有以下的优化准则：argmax()()TLDABLDATLDAWLDAtrUSUtrUSU..TLDALDAdstUUI上述的优化可以转化为求解一个广义的特征分解问题：BWSS且最优的解为d个特征向量其对应于d个最大的非零特征值。3.投影寻踪(ProjectionPursuitPP)[3]基本思想主要