保持整体的局部线性嵌入算法

【摘 要】LLE算法是一种有效的非线性数据降维方法，但是直接LLE降维后的数据比原始数据小的很多，不能保持原始数据的整体特征，本文在LLE的基础上提出了一种能够保持原始流行整体结构的LLE算法，实验表明本算法在降维的同时还保持了原始流行的大小。是对LLE的有效改进。

【关键词】LLE（Locally linear embedding）；数据降维

1.引言

LLE（Locally Linear Embedding）[1-3]是一种效果显著的非线性数据降维方法。在模式识别、数据挖掘、流行学习等方面都有广泛应用。但是LLE算法本身的特点，它是采样权重矩阵的近似零空间来表示嵌入坐标的，因为权重矩阵的近似零空间里的向量比较小，不能够保持原流行的整体大小。从而在降维的时候丢失一些信息，我们提出的保持整体特性的LLE试图从LLE的降维效果中恢复出原流行的大小，从而保持了原始流行的整体特性。

2.局部线性嵌入（LLE）

局部线性嵌入是Saul先生与Roweis先生在2000年时创造性的提出的一种非线性降维理论。非线性降维理论的思想是用局部的线性来逼近全局的非线性，不改变局部的几何结构，通过相互重叠的局部邻域得出整体的信息，进而保持整体的几何性质。但是不能保持整体流行的大小，设表示均匀采样自维流行的个数据点组成的数据矩阵。LLE算法就是以为输入，输出一个由个维向量组成的矩阵，其中的第列对应的第列。算法分为三个步骤：

第一步：选邻域。关于高维空间中的每个样本点，计算得到它和其他个样本点之间的距离，根据距离的大小，找到与最近的K个点当做其近邻点，一般使用欧氏距离来计算两个点之间的距离，即：。

第二步：计算每个点和它的邻域点之间的权重，即最小化误差函数：

当不属于的邻点集时，有，权重矩阵应该满足：。

第三步：按照高维空间中的样本和它的近邻之间的权重来计算低维嵌入空间中的数值。并固定权重W，在低维空间中尽量保持高维空间中的局部线性结构不变，最小化损失函数：

求的最优解，的列表示低维数据点。

下面是在各个流行上取1500个点10个邻域的实验结果（见图1）。

从结果的坐标中看出，直接LLE降维后的嵌入结果和原始流行大小相差太多，不能很好的体现出原始流行的整体性，为此我们提出了整体保持的LLE。

3.整体保持的LLE

LLE and Linear Mapping在理论上用的d个向量作为低维嵌入坐标是可行的，而且可以找到保持局部距离的。由于，而且在实际中的维数往往为1，从而不能满足实际降维的需要，下表给出了常用流行上的数据点和对应的的维数。

图1

表1 常用流行上的数据点和对应的的维数

点

名称 500 800 10000 1500 2000 2500

Swissroll 1 1 1 1 1 1

Swiss hole 1 1 1 1 1 1

Punctured sphere 1 1 1 1 1 1

Two peaks 1 1 1 1 1 1

3D clusters 2 2 1 3 2 1

Toroidal Helix 1 1 1 2 3 3

Gaussian 1 1 1 1 1 1

表2 常用流行上的数据点和对应的的维数

点

名称 500 800 1000 1500 2000 2500

Swissroll 1 1 1 1 1 1

Swiss hole 1 1 1 1 1 1

Punctured sphere 1 1 1 1 1 1

Two peaks 1 1 1 1 1 1

3D clusters 2 2 1 3 2 1

Toroidal Helix 1 1 1 1 3 1

Gaussian 1 1 1 1 1 1

从表2中的实验结果可以看出的维数太小不能满足降维需要，为此我们在LLE的基础上利用的近似零空间给出了保持整体的LLE，即下面的第四步，Step4：设表示均匀采样自维流行的个数据点组成的数据矩阵。为了找到保持整体的，表示两点之间的距离。设表示的K个邻域，令：

命题：设是一个实对称矩阵，则二次型可表示为：

令为实对称半正定，则对于每个低维嵌入。

有上述命题可得：

令表示的伪逆，从而令：

再由计算出对称矩阵，即对进行SVD分解，从而取，即保持整体距离的降维嵌入为。

4.实验结果

保持整体的LLE在各个流行上的实验结果和LLE结果的比较（见图2）。

图2

5.结束语

本文在LLE的基础上通过引入局部保距映射，给出了保持原始流行整体大小的LLE。

参考文献：

[1]余肖生，周宁.高维数据降维方法研究[J].情报科学，2007，

25（8）：1248-1251.

[2]S.Roweis，L.Saul.Nonlinear dimensionality reduction by locally linear embedding.Science，290（2000）：2323-2326.

[3]陈莉，焦李成.文档挖掘与降维技术[J].西北大学学报（自然科学版），2003（3）：267-271.