PCA是至今为止运用最为广泛的数据降维算法，它通过最小化重构误差达到将高维数据映射到低维并同时保留数据中所存在的绝大部分信息。但是一般的PCA也有缺点，它只能实现线性降维。当然现在也有kernel PCA可以实现非线性降维，但我们今天介绍的是另一种实现非线性降维的算法——局部线性嵌入(Local Linear Embedding)，其是基于流形学习的思想。
一、流形学习(Mainfold Learning)
流形学习是基于流形的思想，其认为现实世界中的高维数据集都可以用低维的流形所代替，而流形一般指高维空间中的几何结构，如曲线或曲面在高维空间中的推广，其是一个空间而不是面。所以直观上来讲，一个流形好比是一个d维的空间，在一个m维的空间中(m>d)被扭曲之后的结果。可以通过Python在三维空间中绘制简单的流形：
#%matplotlib inline
import matplotlib as mpl
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import proj3d
#Generate mainfold data set
from sklearn.datasets import make_swiss_roll
X, t = make_swiss_roll(n_samples=1000, noise=0.2, random_state=42)
axes = [-11.5, 14, -2, 23, -12, 15]
#plot figure
fig = plt.figure(figsize=(6, 5))
ax = fig.add_subplot(111, projection='3d')
ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=t, cmap=plt.cm.hot)
ax.view_init(10, -70)
ax.set_xlabel("$x_1$", fontsize=18)
ax.set_ylabel("$x_2$", fontsize=18)
ax.set_zlabel("$x_3$", fontsize=18)
ax.set_xlim(axes[0:2])
ax.set_ylim(axes[2:4])
ax.set_zlim(axes[4:6])
plt.show()
可以看到，虽然数据集是在三维空间中的，但是我们完全可以通过一定的方法将其平铺在二维空间中并同时保存其数据结构。最简单的方法就是将卷曲的带状数据集拉直，如下图：
而这时如果想通过PCA将数据进行降维，效果将会非常差，因为你很难能够找到一个线性的平面将数据很好的进行投影，我们可以通过以下代码对比两种方法：
plt.subplot(121)
plt.scatter(X[:, 0], X[:, 1], c=t, cmap=plt.cm.hot)
plt.axis(axes[:4])
plt.xlabel("$x_1$", fontsize=18)
plt.ylabel("$x_2$", fontsize=18, rotation=0)
plt.grid(True)
plt.subplot(122)
plt.scatter(t, X[:, 1], c=t, cmap=plt.cm.hot)
plt.axis([4, 15, axes[2], axes[3]])
plt.xlabel("$z_1$", fontsize=18)
plt.grid(True)
plt.show()
左边是将数据投影在xy平面上的结果，而右边是按照上图所示拉直数据集得到的结果。可以看到右边的降维效果远远好于左边。
基于流形与流形学习的思想，我们可以对数据进行非线性的降维，常见的方法有局部线性嵌入，拉普拉斯特征映射，局部保持投影，等距映射等。
二、局部线性嵌入(LLE)
LLE的基本思想如下,数据集X中每个样本ximathrm{x}_{i}xi都可以通过与其邻近的几个样本近似的线性重构,用公式表示为：
xi≈∑jwijxjmathrm{x}_{i} approx sum_{j} w_{i j} mathrm{x}_{j}xi≈j∑wijxj
其中j为与ximathrm{x}_{i}xi相近的j个邻居。这样，求解如下的优化问题就可以得到重构系数：
ε(W)=∑i∥xi−∑jwijxj∥2varepsilon(mathrm{W})=sum_{i}left|mathrm{x}_{i}-sum_{j} w_{i j} mathrm{x}_{j}right|^{2}ε(W)=i∑∥∥∥∥∥xi−j∑wijxj∥∥∥∥∥2
∑jwij=1sum_{j} w_{i j}=1j∑wij=1
得到重构系数后，将数据集X映射低维空间Y中，要保持同样的重构关系：
Φ(Y)=∑i∥yi−∑jwijyj∥2Phi(Y)=sum_{i}left|y_{i}-sum_{j} w_{i j} y_{j}right|^{2}Φ(Y)=i∑∥∥∥∥∥yi−j∑wijyj∥∥∥∥∥2
这样，我们便可以将流形铺开到低维空间中。通过求解上述优化问题就可以得到映射后的数据集Y。
三、算法推导
高维状态下重构系数的计算
设数据集X中样本个数为m，样本维数为n，映射后的数据集Y中样本维数为d，d<
J(W)=∑i=1m∥xi−∑j=1kwijxj∥22J(W)=sum_{i=1}^{m}left|x_{i}-sum_{j =1}^{k} w_{i j} x_{j}right|_{2}^{2}J(W)=i=1∑m∥∥∥∥∥xi−j=1∑kwijxj∥∥∥∥∥22
∑jkwij=1sum_{j}^{k} w_{i j}=1j∑kwij=1
通过∑jkwij=1sum_{j}^{k} w_{i j}=1∑jkwij=1，我们可以对优化函数进行化简：
J(W)=∑i=1m∥xi−∑jkwijxj∥22=∑i=1m∥∑jkwijxi−∑jkwijxj∥22=∑i=1m∥∑jkwij(xi−xj)∥22=∑i=1mWiT(xi−xj)T(xi−xj)Wibegin{aligned} J(W) &=sum_{i=1}^{m}left|x_{i}-sum_{j }^{k} w_{i j} x_{j}right|_{2}^{2} \ &=sum_{i=1}^{m}left|sum_{j}^{k} w_{i j} x_{i}-sum_{j }^{k} w_{i j} x_{j}right|_{2}^{2} \ &=sum_{i=1}^{m}left|sum_{j }^{k} w_{i j}left(x_{i}-x_{j}right)right|_{2}^{2} \ &=sum_{i=1}^{m} W_{i}^{T}left(x_{i}-x_{j}right)^{T}left(x_{i}-x_{j}right) W_{i}end{aligned}J(W)=i=1∑m∥∥∥∥∥xi−j∑kwijxj∥∥∥∥∥22=i=1∑m<
