局部线性嵌入(LLE)

1、介绍

本文参考：http://www.cnblogs.com/pinard/p/6266408.html

（1）概述

LLE属于流形学习(Manifold Learning)的一种，通常流形理解起来比较抽象，在LLE里，我们可以简单的将流形看做一个不闭合的曲面，类似于下图：

而我们的目的就是将其展开到低维，在上图也就是展开到二维，同时数据的结构特征要能够得到最大程度的保持，这个过程就像两个人将流行曲面拉开一样，可以由下图表示：

在局部保持数据结构或者说是数据拓补关系的方法有很多种，不同的保持方法对应不同的流形算法。比如等距映射（ISOMAP）算法在降维后希望保持样本之间的测地距离（关于测地距离见这里，有详细介绍）而不是欧式距离，因为测地距离更能反映样本之间在流形中的真实距离。

但是等距映射算法（等距映射算法简介）有一个问题就是他要找所有样本全局的最优解，当数据量很大，样本维度很高时，计算非常的耗时，鉴于这个问题，LLE通过放弃寻找全局最优解，只是通过保证局部最优来降维。同时假设样本集在局部是满足线性关系的，进一步减少的降维的计算量。

（2）思想

LLE假设数据在较小的局部是线性的，也就是说，某一个样本可以由它最近邻的几个样本线性表示，离样本远的样本对局部的线性关系没有影响，因此相比等距映射算法，降维的时间复杂度和空间复杂度都有极大的降低。比如有一个样本x1,我们在它的原始高维邻域里用K-近邻思想找到和它最近的三个样本x2,x3,x4,然后我们假设x1可以由x2,x3,x4线性表示，即：

x1=w12x2+w13x3+w14x4

其中，w12,w13,w14为权重系数。在我们通过LLE降维后，我们希望x1在低维空间对应的投影y1和x2,x3,x4对应的投影y2,y3,y4也尽量保持同样的线性关系（局部数据结构不变），即:

y1≈w12y2+w13y3+w14y4

也就是说，投影前后线性关系的权重系数w12,w13,w14是尽量不变或者最小改变的。

2、推导

对于LLE算法，我们首先要确定邻域大小的选择，即我们需要多少个邻域样本来线性表示某个样本。假设这个值为k。我们可以通过和KNN一样的思想通过距离度量比如欧式距离来选择某样本的k个最近邻。

在寻找到某个样本的xi的k个最近邻之后我们就需要找到找到xi和这k个最近邻之间的线性关系，也就是要找到线性关系的权重系数。找线性关系，这显然是一个回归问题。假设我们有m个n维样本{x1,x2,⋯,xm},我们可以用均方差作为回归问题的损失函数：即：

J(w)=∑i=1m||xi−∑j=1kwijxj||22

一般我们也会对权重系数wij做归一化的限制，即权重系数需要满足:

∑j=1kwij=1

也就是我们需要通过上面两个式子求出我们的权重系数。一般我们可以通过矩阵和拉格朗日子乘法来求解这个最优化问题。

对于第一个式子，我们先将其矩阵化：

其中Wi=(wi1,wi2,⋯,wik),Zi=(xi−xj)T(xi−xj)，约束条件可化为∑j=1kwij=Wi1k=1，1k为k维全为1的向量。

接下来利用拉格朗日乘子法对以上式子进行求解：

对Wi归一化，那么最终我们的权重系数Wi为：

Wi=Z−1i1k1TkZ−1i1k

现在我们得到了高维的权重系数，那么我们希望这些权重系数对应的线性关系在降维后的低维一样得到保持。假设我们的n维样本集{x1,x2,⋯,xm}在低维的d维度对应投影为{y1,y2,⋯,ym}, 则我们希望保持线性关系，也就是希望对应的均方差损失函数最小，即最小化损失函数J(Y)如下：

其中，M=(I−W)T(I−W)，上式约束条件为：∑i=1myi=0;1m∑i=1myiyTi=I，即YTY=mI。

接下来利用拉格朗日乘子法对以上式子进行求解：

与拉普拉斯特征映射相似（拉普拉斯特征映射（Laplacian Eigenmaps）），最后要得到最小的d维数据集，我们需要求出矩阵M最小的d个非0特征值所对应的d个特征向量组成的矩阵Y=(y1,y2,⋯,yd)即可。

3、步骤

在上一节我们已经基本推导了LLE降维的整个流程，现在我们对算法过程做一个总结。整个LLE算法用一张图可以表示如下：

从图中可以看出，LLE算法主要分为三步，第一步是求K近邻的过程，这个过程使用了和KNN算法一样的求最近邻的方法。第二步，就是对每个样本求它在邻域里的K个近邻的线性关系，得到线性关系权重系数W，具体过程在第三节第一部分。第三步就是利用权重系数来在低维里重构样本数据，具体过程在第三节第二部分。

具体过程如下：

输入：样本集D={x1,x2,⋯,xm}, 最近邻数k，降维到的维数d

输出： 低维样本集矩阵D′
1. for i 1 to m, 按欧式距离作为度量，计算和xi最近的的k个最近邻(xi1,xi2,⋯,xik)
2. for i 1 to m, , 求出局部协方差矩阵Zi=(xi−xj)T(xi−xj),并求出对应的权重系数向量:Wi=Z−1i1k1TkZ−1i1k
3. 由权重系数向量Wi组成权重系数矩阵W,计算矩阵M=(I−W)T(I−W)
4. 计算矩阵M的前d+1个特征值，并计算这d+1个特征值对应的特征向量D={y1,y2,⋯,ym}。
5. 由第二个特征向量到第d+1个特征向量所张成的矩阵即为输出低维样本集矩阵D′={y1,y2,⋯,ym}。　

4、总结

LLE是广泛使用的图形图像降维方法，它实现简单，但是对数据的流形分布特征有严格的要求。比如不能是闭合流形，不能是稀疏的数据集，不能是分布不均匀的数据集等等，这限制了它的应用。下面总结下LLE算法的优缺点。

LLE算法的主要优点有：

1）可以学习任意维的局部线性的低维流形

2）算法归结为稀疏矩阵特征分解，计算复杂度相对较小，实现容易。

LLE算法的主要缺点有：

1）算法所学习的流形只能是不闭合的，且样本集是稠密均匀的。

2）算法对最近邻样本数的选择敏感，不同的最近邻数对最后的降维结果有很大影响。