高维数据的低维表示综述.doc

高维数据的低维表示综述一、研究背景在科学研究中，我们经常要对数据进行处理而这些数据通常都位于维数较高的空间，例如，当我们处理 200 个 256*256 的图片序列时，通常我们将图片拉成一个向量，这样，我们得到了 65536*200 的数据，如果直接对这些数据进行处理，会有以下问题：首先，会出现所谓的“位数灾难”问题，巨大的计算量将使我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接对他们进行处理，不会得到理想的结果所以，通常我们需要首先对数据进行降维，然后对降维后的数据进行处理降维的基本原理是把数据样本从高维输入空间通过线性或非线性映射投影到一个低维空间，从而找出隐藏在高维观测数据中有意义的低维结构 （8）之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余：· 有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的· 有些变量和其他的变量有很强的相关性(例如是其他变量的线性组合或是其他函数依赖关系)，可以找到一组新的不相关的变量 （3）从几何的观点来看，降维可以看成是挖掘嵌入在高维数据中的低维线性或非线性流形这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的点在嵌入空间中也相互靠近。

（12）数据降维是以牺牲一部分信息为代价的，把高维数据通过投影映射到低维空间中，势必会造成一些原始信息的损失所以在对高维数据实施降维的过程中如何在最优的保持原始数据的本质的前提下，实现高维数据的低维表示，是研究的重点 （8）二、降维问题1．定义定义 1.1 降维问题的模型为 ，其中 维数据空间集合 （一(,)XFD1NlXx般为 的一个子集） ，映射DR:Y(),xy是 空间集合（一般是 ， ）的一个子集，我们称 是数据集YddRDF（到 ）的降维X若 为 的线性函数，则称 为线性降维；否则，称为非线性降维FF定义 1.2 称映射 1:YX1()yx为嵌入映射 （8）2．分类针对降维问题的目的和待处理数据集合表象维数的多少，对其进行初步的、粗略的分类如下：·硬降维问题：数据维数从几千到几万甚至几十万的变化，此时需要对数据集进行“严厉 ”的降维，以至于达到便于处理的大小，如图像识别、分类问题以及语音识别问题等·软降维问题：此时数据集合的维数不是太高，降维的需求不是非常的迫切如社会科学、心理学以及多元统计分析领域皆属于此类·可视化问题：此时数据集合的绝对维数不是很高，但为了便于利用人们的直观洞察力，即为了可视化，我们将其降到 2 或 3 维。

虽然我们可以可视化更高维数的数据，但是它们通常难于理解，不能产生数据空间的合理形态若我们还考虑时间变量的话可以对降维问题进行更加进一步的分类，静态降维问题和动态降维问题后者对于时间序列来讲是有用的，如视频序列、连续语音信号等的处理 （4）3．方法介绍如何将高维数据表示在低维空间中，并由此发现其内在结构是高维信息处理研究的关键问题之一实际处理中，由于线性方法具有简单性、易解释性、可延展性等优点，使得线性降维在高维数据处理中是一个主要研究方向已有的线性维数约简方法，主要包括主成分分析(Principal Component Analysis，PCA)[16]、独立成分分析(Independent Component Analysis，ICA)、线性判别分析 inear discriminant analysis(LDA) [17]、Fisher 判别分析(Fisher Discriminant Analysis，FDA)、主曲线(Principal Curves)、投影寻踪 (Projection Pursuit, PP)、多维尺度方法(Multidimensional Scaling，MDS)等。

这些方法实际是在不同优化准则之下，寻求最佳线性模型，这也是线性维数约简方法的共性 （10）通过消除数据建模过程中的全局线性假设，Sammon 提出了一种非线性映射，即 Sammon 映射(SM)，该算法能够保持输入样本之间的相关距离；Hastie提出了 principal curves(PC)，其定义为通过概率分布或数据中间的光滑曲线；Kohonen 基于自组织神经网络提出了 self-organizing map(SOM)用来保存数据空间的拓扑属性；Scholkopf 等应用 Mercer 核将 PCA 扩展为 Kernel PCA(KPCA)，该算法在高维空间中计算主分量，而该高维空间由输入空间经某种非线性映射得到Mika 等采用相同的思想来非线性扩展 LDA，从而提出了 kernel LDA（ KLDA） ；然而，基于核的方法其难点在于如何选择一个合适的核函数， 一个好的核函数可以使数据在特征空间上线性可分或者近似线性可分，但并不是所选核函数对于每一种数据都适用核函数的选择反映了人们对问题的先验知识，在实际的应用中往往是经验地选择某种核函数，比如径向基函数 (Radial Basis Function，RBF)。

同时，在使用核函数时不必知道具体的特征空间，使得核函数方法缺乏物理直观性，这也是核函数方法的一个缺点 （10）最近兴起的流形学习算法也是用来维数约减的非线性方法，并且依靠它们在探测嵌入在高维空间中低维流形的能力和灵活性而被广泛应用具有代表性的流形学习算法包括等距映射 (Isometric Mapping，Isomap)、局部线性嵌入方法(Locally Linear Embedding， LLE)、Laplacian 特征映射(Laplacian Eigenmap，LE) 、局部切空间排列方法 ( Local Tangent Space Alignment，LTSA)、Hessian 等距映射(Hessian eigenmaps，HLLE) 和最大方差展开(maximum variance unfolding，MVU)其中， LLE 运用线性系数，来表达局部几何，该系数能够重建一个给定的样本点利用其近邻点，然后寻找一个低维空间，在该空间中这些线性系数仍然可以用来重建相应的点；ISOMAP 作为MDS 的变种，能够保存点对之间的全局的测地线距离；LE 通过对一个描述了点对之间邻域关系的无向图的操作，来保持数据之间的近邻关系。

HLLE 先通过估计邻域上的 Hessian 而构建一矩阵，然后在此矩阵上运用特征值分解而得到最终的低维坐标LTSA 运用局部切信息作为局部几何的表达，然后将这些切信息在全局中排列从而得到最终的全局坐标MVU 不是一个绝对的局部方法而是一个介于局部和全局之间的方法，因为 MVU 不仅保存近邻点之间的几何关系而且在它的目标函数中考虑了全局点对之间的距离除了基于谱分析的流形学习的算法，基于概率参数模型，Rowels 提出了 global coordination(GC)；Teh 和 Roweis 开发了 locally linear coordination(LLC)；Brand 提出了 manifold charting(Charting)这些方法也属于流形学习的重要范畴然而，这些非线性的算法却不能够为样本提供一个外在的映射，也就是说，它们很难被应用于识别问题但是，一些基于谱分析的算法由于其具有特殊的特征分解机制而能够较为容易的扩展为线性算法，其线性化可以通过在解决优化的过程中施加线性逼近来实现Locality preserving projection(LPP)作为 LE 的线性化是其中最早提出的算法。

后来提出的还包括 neighborhood preserving embedding(NPE)，LLE 的线性化扩展，和 orthogonal neighborhood preserving projections(ONPP)，LLE 的正交线性化扩展这种线性化扩展使流形学习的思想更能够应用到现实世界中图 1.1 给出了以上所提提及的降维算法的分类图在谱方法的线性化扩展中，LPP 可以被看作为基于图结构的最具代表性的算法，在接下来的几年中，又不断地有这种基于图的算法被提出，从而进一步完善了这种基于图的框架Cai 等对 LPP 算法分别对监督设置和非监督设置两种情况作了系统的分析，并且将 LDA 用这种基于图的框架重新公式化Yan 等提出了一种一般性的框架即“图嵌入” ，来统一各种各样的降维算法基于此种框架，一种新的线性算法，marginal fisher analysis（MFA）将开发出来MFA不同于 LPP 其只用一个图来描述数据的几何结构，该算法采用了两个图，其中一个为固有图（intrinsic graph） ，它用来刻画数据的类内紧凑性；而另一个图为惩罚图（penalty graph） ，用来描述数据类间的分离性。

因此，MFA 比 LPP 更具有判别性Chen 等同时提出的 local discriminant embedding（LDE）算法在本质上与 MFA 的思想是相同的 （5）非线性降维方法与线性降维方法相比的一个显著特点是，分析中的局部性(数据集合经常满足的一个简单假设)原因在于对数据集合的内蕴结构而言，有下列特性：·由泰勒定理，任何可微函数在一点的充分小的邻域之内满足线性性形象的来讲，相当于认为曲面流形可由大小不一的局部线性块拼接而成；·数据流形经常是由许多可分割的子流形所组成；·数据流形的本征维数沿着流形不断的发生变化，只有局部性才能抓住其根本特性 （4） 降维 线性流行学习概率参数模型全局谱分析 局部全局局部早期的非线性PCAMVUISOMAPChartingLLCKernelPCSMSOMGCLDALPPNPELLELLTSAONPPLELTSAHLLE线性化三、常见降维方法（一）线性1. 主成分分析(Principal Component Aanlysis PCA) [1]PCA 将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息越多，反之提供的信息就越少它是在损失很少的信息的前提下把多个指标转化为几个综合指标的一种多元统计方法。

它具有概念简单，计算方便以及最优线性重构误差等优良的特性PCA 是一种全局算法，它可以较好地揭示具有线性结构的高维数据集的全局分布然而对于嵌入在高维空间中具有非线性流形结构的数据，PCA 很难学习出隐含在数据集中的低维流形结构PCA 假设数据之间的关系是线性的它在保存原始高维数据协方差结构的基础上计算低维表达，也就是最大化总体方差它的目标函数可以写为： 2121=argmx()argmx().PCAPCA PCANiUiT TTi PCAPCAdUiytSstUI 其中， ， ，且 为总体离散矩阵：miyN1ixT对转换矩阵做尺度约束 ，其中 为 单i=1()TNTiiSx d=PCAIdI位矩阵则目标函数可以写为：，argm()PCATPCAUtS.TPCAdstUI上式问题可以转化为 的标准的特征值问题：PCA 的最优转换矩阵为T的 d 个最大的特征值所对应的 d 个 m 维特征向量TS2.线性判别法(Linear Discriminant Analysis LDA) [2]其基本思想是投影，首先找出特征向量，把这些数据投影到一个低维的方向，使得投影后不同的组之间尽可能的分开，而同一组内的的样本比较靠拢，然后在新空间中对样本进行分类。

通过最小化类内离散矩阵 的秩而最大化类间离散矩阵 的秩，来寻找WSBS一个子空间来区分不同的类别 和 分别定义如下：B()()()i=1iNCiiiiTWjjjSxm()()1iiTBi其中， 是第 i 个类中样本的个数； 是第 i 个样本中第 j 个样本iN()ijx为第 i 个类的质心； 用来表示所有样本的质心，C 为样本的类别数LDA()imm则有以下的优化准则：argmx()TLDABWtUS.TLDAds。