局部线性嵌入算法及其稳定性实现

夏洁云

（广东工程职业技术学院）

0 引言

局部线性嵌入（locally linear embedding，LLE）算法[1-2]基于简单的几何直觉，由于计算简单，性能良好，被广泛应用[3-5]。近些年来对LLE算法的改进有很多，如改进距离测度的有：加权距离[6]、核相关变换[7]；改进权重计算的有：局部线性变换[8-9]、多权重组合方法[10-11]；改进嵌入计算的有：减少孤立子影响算法[12-13]、展开流形算法[14]等。虽然这些改进算法对LLE算法的性能有很大的提升，但对于LLE算法关键步骤的理论实现却相对较少，并且对 LLE算法在非均匀采样条件下，对邻域点数以及数据采样点数的稳定性实现也很少。本文对 LLE算法的关键步骤进行理论实现，同时在各种经典流形上对 LLE算法的实际降维效果进行验证分析，并在非均匀采样条件下，验证并讨论 LLE算法对邻域点数和采样点数的稳定性。

1 LLE算法

给 定 一 个 数 据 点 集 XN×M， 这 里表示一个N×M的矩阵，其中 XN×M的每一行表示某个数据点的各个坐标。假定这些数据点是采样自一个潜在的流形。如果这些数据是充足的（即对流形是一个充分的采样），即使不知道这个潜在的流形是什么样，但可以认为，对于每一个数据点，它与其邻点所形成的局部区域（通常称为一个 patch）是线性的。可用一个数据点的邻点线性组合来逼近它（重构这个数据点）。

重构误差使用式(1)度量：

其中，权重 wij反映了第j个数据点对重构第i个数据点的贡献。

重构权重W反映了数据的内在属性，且对于旋转、尺度、平移等变换具有不变性。据此，对数据在原高维空间的局部几何关系的刻画同样适用于→流形上的patch。即在M 维空间里用→于重构数据点的权重 wij与在m维空间里重构权重一样。LLE基于上述思想，构造一个能够保持邻居关系的→映射。算法的最后结果是，每一个高维的观测数据都被映射到一个低维表示。数据的低维表示通过式(2)求得：

式(2)与式(1)一样，都→是基于重构误差。不同的是，这里是固定W而求得的坐标的最优解。Y表示一个N×m的矩阵，其中Y的每一行表示某个数据点在低维空间的坐标。

2 算法关键步骤

对 LLE算法两个关键步骤的理论基础进行分析和推导，从理论层面实现LLE算法的具体过程。

2.1 权重构建

通过正则化可得：

一阶微分可得：

2.2 嵌入向量

3 LLE算法实验

LLE算法的降维效果在3个比较经典的人工流形数据集Swiss roll、Two peaks和Punched sphere上进行验证，其中Punched sphere为非均匀采样数据集。另外，在Punched sphere上又分别验证LLE算法在非均匀数据集上对于邻域点选择和数据点采样的稳定性。

3.1 LLE算法的实际降维效果

图 1～图 3分别为 LLE算法在 Swiss roll、Two peaks和Punched sphere上的数据降维效果。数据集统一采样1000个数据点，采样8个点的数据邻域。

由图1～图3 可以看出，LLE算法具有很好的非线性数据降维效果。在有效降低高维数据的同时还能够有效保持数据点之间的邻域关系不变。从图像上数据点的分布情况可以看到，降维之前相对较近的数据点，降维之后依然保持近邻关系。图1(a)为三维的卷曲瑞士卷曲面，图1(b)为LLE算法的降维效果图，虽然不能将瑞士卷完全展开成平面，但已经降维为二维图形；图2 (a)为三维空间的双极曲面，图2 (b)为LLE算法的降维效果图，从图形上可以看到 LLE算法完全将双极曲面展开，这表明了 LLE算法的良好数据降维效果；图3 (a)为非均匀采样的三维半球面，图3 (b)为LLE算法的降维效果。结果表明：LLE算法不仅能够有效对高维数据进行降维，还能完整地保存高维数据点之间的邻域关系。

图1 LLE算法在Swiss roll上的降维效果

图2 LLE算法在Two peaks上的降维效果

图3 LLE算法在Punched sphere上的降维效果

3.2 LLE算法对于邻域点个数以及数据采样点数的稳定性

本节实验验证 LLE算法对于邻域点个数和采样点数的稳定性。

图 4(a)、(b)、(c)分别为 LLE 算法在Punched sphere上采样5、10、15个邻域点，1000个数据点的降维效果。实验结果可以看出，当邻域点个数从5变化到15时，LLE算法对于非均匀采样数据集的降维效果一直优良，邻域点的个数对于 LLE算法的降维效果没有太大的影响。因此，在适当的邻域大小范围内，LLE算法都可以保持较好的数据降维效果。这表明：LLE算法在一定程度上具有对于数据点邻域选择的稳定性。

图 5(a)、(b)、(c)为 LLE 算法在 Punched sphere上分别采样200、1000、2000个点，10个邻域点的降维效果。

图5 (a) 采样点为200时的降维效果

图5 LLE算法在Punched sphere上的降维效果

实验结果可以看出，当采样点数从 200变化到2000时，LLE算法对于非均匀采样数据集始终保持良好的数据降维效果，数据点采样的个数对于 LLE算法的降维效果没有太大影响。因此，对于非均匀数据集，无论是稀疏采样还是密集采样，LLE算法都具有良好的数据降维效果。这表明：LLE算法对于数据点的采样个数有很好的稳定性。

本文在非均匀采样数据集Punched sphere上分别验证了 LLE算法对于邻域点数以及数据采样点数的双重稳定性。图4、图5的实验结果完全验证了LLE算法的稳定特性。实验表明：LLE算法是一种非常有效的非线性数据降维算法。该算法不仅对于均匀采样数据集有良好的降维效果，同时对于非均匀采样数据集也有着优良的性能。

4 结论

LLE算法是一种非常有效的非线性数据降维方法，有广泛的应用。它主要是通过两次局部最小化实现对高维数据的降维处理。本文实现了 LLE算法的两个局部最小化的理论推导过程，完善了 LLE算法的理论基础。同时，对 LLE算法的非线性降维效果进行了实际验证，分别在均匀采样和非均匀采样的数据流形上对 LLE算法进行实际验证。另外，在非均匀采样数据集上，分别验证了 LLE算法对于邻域点选择和数据点采样的稳定性。通过一系列的分析探讨，证实 LLE算法确实是一种非常有效的非线性数据降维算法。

[1]S T Roweis,L K Saul. Nonlinear dimensionality reduction by locally linear embedding[J]. Science,2000,290: 2323-2326.

[2]L K Saul,S T Rowels. Think globally,fit locally: Unsupervised learning of low dimensional manifolds[J]. Journal of Machine Learning Research,2003,4: 119-155.

[3]Wang Y,Wu Y. Complete neighborhood preserving embedding for face recognition[J].Pattern Recognition,2010,43(3):1008-1015.

[4]Yan Y,Zhang Y .Discriminant projection embedding for face and palmprint recognition[J]. Neurocomputing,2008,71(16–18):3534-3543.

[5]Ying H P,Andrew Teoh B J,Wong E K. Neighbourhood discriminant embedding in face recognition[J]. IEICE Electron Express,2008,5(24):1036-1041.

[6]Pan Y,Ge S S,Al Mamun A. Weighted locally linear embedding for dimension reduction[J]. Pattern Recognitn,2009,42(5):798-811.

[7]Wen Guihua,Jiang Lijun,Wen Jun. Kernel relative transformation with applications to enhancing locally linear embedding[C]. International Joint Conference on Neural Networks,2008:3401-3406.

[8]Goldberg Y,Ritov Y. LDR-LLE: LLE with low-dimensional neighborhood representation[J]. ISVC,2008,1: 43-54.

[9]Hou C,Wang J,Wu Y,Yi D. Local linear transformation embedding[J]. Neurocomputing,2009,72(10-12):2368-2378.

[10]Wang J,Zhang Z. Nonlinear embedding preserving multiple local-linearities[J]. Pattern Recognition,2010,43(4):1257-1268.

[11]Zhang Zhenyue,Wang Jiang. Modified locally linear embedding using multiple weights[C]Advances in Neural Information Processing Systems,2007,19:1593-1600.

[12]Hong Chang,Dit-Yan Yeung. Robust locally linear embedding[J]. Pattern Recognit,2006,39(6):1053-1065.

[13]Zeng Xianhua,Luo Siwei. Generalized locally linear embedding based on local reconstruction similarity[C]. Fifth International Conference on Fuzzy Systems and Knowledge Discovery,2008:305-309.

[14]Hou Chenping,Zhang Changshui,Wu Yi,et al. Stable local dimensionality reduction approaches[J]. Pattern Recognit,2009,42(9): 2054-2066.