1.算法思想

????????Laplacian Eigenmaps 与LLE方法类似，都是用于处理流形数据的降维方法。两者的目标也是相近的，都是为了找到高维数据的低维表示，同时保留数据中的局部结构。对于如何定义局部结构？在LLE方法中，定义每个数据点与它的近邻是线性的。Laplacian Eigenmaps的提出者给出与之不同的方案。

?????????Laplacian Eigenmaps 方法中，核心的思想是通过计算数据点之间存在某种相似性来衡量局部结构。一旦有了相似性的概念，数据点彼此之间的相似性就可以用于优化低维数据点的位置，使得在低维表示下，以保持相同的相似性。

????????通常，局部距离 local distance 可作为相似性的一种度量。我们可以将这种距离相似性嵌入数据的表示中。现在的问题是如何具体地定义相似呢？

????????在数学上，从函数角度直观地理解，相似的输入就会得到一个高值输出，如果不相似，会得到一个低值。由于我们只知道数据在空间中的位置，我们能做的是，如果数据点的距离很短，希望相似度值很高，如果距离很远，它应该很小。因此，相似性的度量应该与距离成反比。

最终使用的是高斯函数，类似于kernel method中高斯基函数。

2.算法实现

2.1图形化表示

?以图形化表示整个算法的实现过程如下图所示。

2.2实现流程

Step1: 相似性度量与图重构（Graph Construction）

接着上述分析，首先定义一个度量相似性的函数

???????????????????????? $w_{ij}=sim(x_i,x_j)=exp(\frac{-\left \| x_i-x_j \right \|^2}{\sigma^2})$ ? ? ? ? ? ? ? ? ? ? ? ? ?(1)

其中， $\sigma$ 是尺度参数， $x_i,x_j$ 对应两个数据样本

????????关键疑问：既然是在流形上，为什么上述定义的是欧氏距离而不是测地线呢？

最核心的秘密就在于上述有尺度参数 $\sigma$ 。如果 $\sigma$ 与局部邻域处于同一数量级水平，那么在局部，即便是流形数据，它无论如何都是线性的，所以可以把欧氏距离作为测地线的一个很好的近似值。在邻域之外，也就是距离较远，使用上述高斯函数后，不同的位置表现出的相似性急剧下降，最终得到相似性将很小，所以并不会出现想象中类似瑞士卷上属于两层不直接连接的点有较大的相似性（两层的位置已超过了领域，相似性输出值急剧下降）。所以通过合理的设置或选择 $\sigma$ ，以体现局部的邻域特性，可以有效解决上述疑问。

使用上述相似性定义不同数据点之间的关系后，可以实现图重构，即上述图b。

Step 2: 图拉普拉斯矩阵嵌入（Embed using Graph Laplacian）

??Laplacian Eigenmaps的目标函数如下：

???????????????????????????????? $\psi(Y)=\sum_{j}w_{ij}({\left \| Y_i-Y_j \right \|^2})$