5.4　局部线性嵌入

当数据具备某些非线性结构，如流形结构时，我们希望降维后的数据仍然保持这些结构。局部线性嵌入（locally linear embedding，LLE）给出了它的解决方案。LLE的目标是在数据降维后仍然保留原始高维数据的拓扑结构。这种拓扑结构表现为数据点的局部邻接关系。对于输入X，其类表示由对象间的局部线性组合矩阵给出。根据类紧致性准则，我们希望最小化如下目标函数

其中N（k）指点xk的近邻集合。公式（5.17）表明每个点可表示成它近邻的一个线性组合，这种局部组合关系用系数矩阵W表示。根据类表示唯一公理，因此。同时类紧致性准则要求，一个好的类输出Y需要满足如下目标函数：

在式（5.18）中，LLE根据从原始数据获得局部系数矩阵W以求取数据的低维表示。LLE的核心思想即是通过求解式（5.17）和式（5.18）获得类表示矩阵，即组合系数矩阵W。以下给出LLE算法详细的求解过程。

在求解式（5.17）时，会进行如下约束

该约束保证了W的平移不变性，即数据点经过某些线性变换时，W仍然有效。以下给出这一性质的简要说明。假定xk可由其近邻的线性组合表示，即。令向量t为某一平移量，对xk平移后，其重新构建的近邻关系为

其中vkl为平移后的重构系数。于是有

平移不变性要求wkl=vkl，由此可得

由此可得。

式（5.19）中求所有点的重构误差的最小值可以分解成求每个点的最小重构误差，以保证整个误差最小。以下给出针对每个点的W的求解方法。给定问题

令Nk∈ℝp×K为xk的K个邻居构成的矩阵，同时令Xk=［xk|xk| … |xk］ ∈ℝp×K，wk∈ℝK×1为系数向量，则式（5.23）可写成如下形式

其中Qk为xk的一个局部协方差矩阵。结合约束条件，有如下的拉格朗日方程

其中1∈ℝK×1为全1向量。针对wk求偏导并置0得

易得

利用式（5.23）中的约束，得1Twk=λk1TQ−1k1=1，进而λk=（1TQ−1k1）−1，将其代入式（5.27）得

根据上一步获得一系列的wkl，定义完整的W如下：

下面求解数据的低维嵌入Y=［y1|y2| … |yN］ ∈ℝd×N。我们希望数据被降维后仍然保持高维数据原始的局部拓扑结构，即W，因此用以下目标函数求解

其中I∈ℝd×d为单位矩阵，式（5.30）中的两个约束都是为了获得唯一有效解，第一个约束条件使得数据均值在坐标原点，由于当yi被平移固定值时，其仍为问题（5.30）的解，通过这一约束可以避免这些无效解。第二个约束条件通过令数据的协方差矩阵为一单位阵，从而避免了平凡解，并且使得嵌入空间中每一维的尺度相同。式（5.30）写成矩阵形式为

其中1∈ℝN并且

其中M=（I−W）（I−W）。若降维到d维，则问题（5.31）的解为矩阵M的最小的d个特征值对应的特征向量。由于最小的特征值对应的特征向量几乎为0，因此通常取第2到第d+1个最小特征值对应的特征向量。