通过拉普拉斯特征映射降维

拉普拉斯特征映射（Laplacian Eigenmaps），主要包括拉普拉斯特征映射（Laplacian Eigenmaps）使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

1 介绍
　　拉普拉斯特征映射（Laplacian Eigenmaps）是一种不太常见的降维算法，它看问题的角度和常见的降维算法不太相同，是从局部的角度去构建数据之间的关系。也许这样讲有些抽象，具体来讲，拉普拉斯特征映射是一种基于图的降维算法，它希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近，从而在降维后仍能保持原有的数据结构。

2 推导
　　拉普拉斯特征映射通过构建邻接矩阵为 $W$ (邻接矩阵定义见这里) 的图来重构数据流形的局部结构特征。其主要思想是，如果两个数据 实例 $i$ 和 $j$ 很相似，那么 $i$ 和 $j$ 在 降维后目标子空间中应该尽量接近。设数据实例的数目为 $n$ ，目标子空间即最终的降维目标的维度为 $m$ 。 定义 $ n \times m$ 大小的矩阵 $Y$ ，其中每一个行向量 $y_i^T$ 是数据实例 $i$ 在目标 $m$ 维子空间中的向量表示（即降维后的数据实例 $i$ ）。我们的目的是 让相似的数据样例 $i$ 和 $j$ 在降维后的目标子空间里仍旧尽量接近，故拉普拉斯特征映射优化的目标函数如下:

$\min \sum _{i,j}{\Vert y_i-y_j\Vert }^2{W}_{ij}$

下面开始推导：

$ \begin{array}{l} \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{{n}&\left|y_{i}-y_{j}\right|}{2} W_{i j} \ &=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{{n}\left(y_{i}}{T} y_{i}-2 y_{i}^{T} y_{j}+y_{j}^{T} y_{j}\right) W_{i j} \ &=\sum\limits_{i=1}^{{n}\left(\sum\limits_{j=1}}{n} W_{i j}\right) y_{i}^{T} y_{i}+\sum\limits_{j=1}^{{n}\left(\sum\limits_{i=1}}{n} W_{i j}\right) y_{j}^{T} y_{j}-2 \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} y_{i}^{T} y_{j} W_{i j} \ &=2 \sum\limits_{i=1}^{n} D_{i i} y_{i}^{T} y_{i}-2 \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} y_{i}^{T} y_{j} W_{i j} \ &=2 \sum\limits_{i=1}^{n}\left(\sqrt{D_{i i}} y_{i}\right)^{T}\left(\sqrt{D_{i i}} y_{i}\right)-2 \sum\limits_{i=1}^{n} y_{i}^{{T}\left(\sum\limits_{j=1}}{n} y_{j} W i j\right) \ &=2 \operatorname{trace}\left(Y^{T} D Y\right)-2 \sum\limits_{i=1}^{n} y_{i}^{T}(Y W)_{i} \ &=2 \operatorname{trace}\left(Y^{T} D Y\right)-2 \operatorname{trace}\left(Y^{T} W Y\right) \ &=2 \operatorname{trace}\left[Y^{T}(D-W) Y\right] \ &=2 \operatorname{trace}\left(Y^{T} L Y\right) \end{array} $

其中 $W $ 是图的邻接矩阵，对角矩阵 $D$ 是图的度矩阵 $\left(D_{ii}=\sum _{j=1}^n{W}_{ij}\right)$ ，$ L=D-W$ 成为图的拉普拉斯矩阵。

变换后的拉普拉斯特征映射优化的目标函数如下:

$\begin{array}{l}\min \mathrm{trace}\left(Y^{T}LY\right)\\ \text{ s.t. }{Y}^{T}DY=I\end{array}$

其中限制条件 $s.t.Y^{T}DY=I$ 保证优化问题有解，下面用拉格朗日乘子法对目标函数求解:

$f(Y)=\mathrm{tr}\left(Y^{T}LY\right)+\mathrm{tr}\left[\Lambda \left(Y^{T}DY-I\right)\right]$

$\begin{array}{lc}\frac{\partial f(Y)}{\partial Y}& =LY+L^{T}Y+D^{T}Y{\Lambda }^T+DY\Lambda \\ & =2LY+2DY\Lambda =0\end{array}$

$\therefore LY=-DY\Lambda$

其中用到了矩阵的迹的求导，具体方法见 迹求导。 $\Lambda$ 为一个对角矩阵，另外 $L$ 、 $D$ 均为实对称矩阵，其转置与自身相等。对于单独的 $y$ 向量，上式可写为: $Ly=\lambda Dy$，这是一个广义特征值问题。通过求得 $m$ 个最小非零特征值所对应的特征向量，即可达到降维的目 的。

关于这里为什么要选择 $m$ 个最小非零特征值所对应的特征向量。将 $L Y=-D Y \Lambda $ 带回到 $\min \mathrm{trace}\left(Y^{T}LY\right)$ 中，由于有着约束条件 $Y^{T}DY=I$ 的限制，可以得到 $ \min \quad \operatorname{trace}\left(Y^{T} L Y\right)=\min \quad t r a c e(-\Lambda)$ 。即为特 征值之和。我们为了目标函数最小化，要选择最小的 $m$ 个特征值所对应的特征向量。

3 步骤
　　使用时算法具体步骤为:

步骤1：构建图

使用某一种方法来将所有的点构建成一个图，例如使用KNN算法，将每个点最近的K个点连上边。K是一个预先设定的值。

步骤2：确定权重

确定点与点之间的权重大小，例如选用热核函数来确定，如果点 i 和点 j 相连，那么它们关系的权重设定为：

$W_{ij}=e^{-\frac{{\Vert x_i-x_j\Vert }^2}{t}}$

另外一种可选的简化设定是 $W_{ij}=1$ 如果点 $i$ ，$ j$ 相连，否则 $W_{i j}=0 $ 。

步骤3：特征映射

计算拉普拉斯矩阵 $L$ 的特征向量与特征值: $L y=\lambda D y $

使用最小的 $m$ 个非零特征值对应的特征向量作为降维后的结果输出。