高维数据的低维表示综述 - 图文(3)

现在形式化地概括流形学习这一维数约简过程：假设数据是均匀采样于一个高维欧氏空间中的低维流形，流形学习就是从高维采样数据中恢复低维流形结

构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约简或者数据可视化。它是从观测到的现象中去寻找事物的本质，找到产生数据的内在规律。

用数学语言可以这样描述，令YD?d?Rd且

f:Y?RD是一个光滑的嵌套，

，流形学习的目标是基于RD上的一个给定被观测数据集合?xi?去恢复Y和

ff，在Y中隐藏的数据?yi?被随机地产生，然后被

?f(yi)?。（12）

映射到观测空间，使得

?xi1.局部线性嵌入方法 LLE (Locally Linear Embedding) [5]

LLE在保存原始高维数据邻域线性结构的基础上计算低维表达。（5）是一种局部方法，它试图保持数据的局部几何特征，就本质上来说，它是将流形上的近邻点映射到低维空间的近邻。（9）

图2 非线性降维实例 B是从 A中提取的样本点（三维），通过非线性降维算法 LLE将数据映射到二维空间中（C），从C图中的颜色可以看出通过 LLE算法处理后的数据能很好的保持原有数据的邻域特性(引用文献[6])

主要思想：对一组具有嵌套(流形)的数据集，在嵌套空问与内在低维空间局

部邻域问的关系应该不变，即在嵌套空间中每个采样点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据点，使重构误差最小。(8)

LLE的实现过程

步骤：LLE方法可以归结为三步： (1) 寻找每个样本点的k个近邻点；

把相对于所求样本点距离最近的k个样本点规定为所求样本点的k个邻近点。k是一个预先给定值。距离的计算既可采用欧式距离也可采用Dijkstra距离。Dijkstra距离是一种测地距离，它能够保持样本点之间的曲面特性。

(2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵； 这里定义一个成本函数，如下式，来测量重建误差：

?(w)?xi??2jwijxj

?0解得wij其中Gijk??kGjki?1/?lmGlmi?1，?xj?Nwij?1,xj?N时wij

?(xi??j)(xi??k)，?j和?k是xi的近邻点；

为了使重建误差最小化，权重wij服从一种重要的对称性，即对所有特定数据点

来说，它们和它们邻居点之间经过旋转、重排、转换等变换后，它们之间的对称性是不变的。由此可见重建权重能够描述每个邻居本质的几何特性。因此可以认为原始数据空间内的局部几何特征同在流形局部块上的几何特征是完全等效的。

（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。 映射条件满足如下成本函数：

?(Y)??iYi??2jwijYj

要使低维重构误差最小，计算得出，Y等价于求M的特征向量，其中

M?(I?W)(I?W)T在处理过程中，将M的特征值从小到大排列，第一个特征

值几乎接近于零，那么舍去第一个特征值。通常取第2到m+l之间的特征值所对应的特征向量作为输出结果。

优点：LLE算法可以学习任意维的局部线性的低维流形，就是用局部性——用局部的的线性来逼近全局的非线性，保持局部的几何结构不变，通过相互重叠的局部邻域来提供整体的信息，从而保持整体的几何性质。LLE既有非线性的特点又具有线性方法的优点。（8）同时由重构成本函数最小化得到的最优权值遵循对称特性，每个点的近邻权值在平移、旋转、伸缩变换下是保持不变的LLE算法有解析的全局最优解，不需迭代，低维嵌入的计算归结为稀疏矩阵特征值的计算，这样计算复杂度相对较小。

缺点：LLE算法要求所学习的流形只能是不闭合的且在局部是线性的，还要求样本在流形上是稠密采样的。另外，该算法的参数选择不确定，对样本中的噪音很敏感。（12）此外，(1)对于一个新样本点。没有显式的方法把该点嵌入到低维空间中，这在检索应用中不适用。(2)新空间的维数没有显式准则进行确定，只有通过经验的方法。(3)LLE没有利用数据点的类信息。在分类问题中，对于有类标号的样本数据，LLE无能为力。

SLLE算法[7]

Dick和Robert提出一种针对有监督的 LLE算法，即Supervised linear locally embedding (SLLE)传统的LLE算法在第一步时是根据样本点间的欧氏距离来寻找k个近邻点，而SLLE在处理这一步时增加了样本点的类别信息，SLLE算法的其余步骤同LLE算法是一致的。