核心原理#

LLE是一种无监督流形学习算法，核心是保持样本的局部线性关系来实现降维。LLE假设高维数据位于低维流形上，每个样本可由其领域内样本线性重建，降维后需保持这种局部重建关系不变，从而在低维中保留高维数据的集合结构。

算法流程#

1. 近邻搜索：为每个点找k个近邻#

对于每个样本点 $x_i$，找到其K个最近邻 $$\mathcal{N}(i)={j_i,\cdots,j_K}$$

常见做法：（1）欧式距离+KNN；（2）高维数据时用KD-tree/Ball-tree/ANN

2. 计算局部线性重构权重#

对于每个点 $x_i$，用它的邻居线性重构，即

$$x_i\approx \sum_{j\in \mathcal{N}(i)} w_{ij}x_j$$

通过最小化重构误差来求权重：

$$\min_{w_{ij}}\Vert x_i-\sum_{j\in \mathcal{N}(i)}w_{ij}x_j\Vert^2$$

数学上可以进行如下求解：定义领域偏移矩阵

$$Z_{i}=\left[ \begin{aligned} &x_{j_1}-x_i \ &... \ &x_{j_K}-x_i \end{aligned} \right]\in \mathbb{R}^{K\times D}$$

局部协方差矩阵

$$C_i=Z_i Z_i^T\in \mathbb{R}^{K\times K}$$

权重由以下问题给出：

$$\min_{w_i} w_i^T C_i w_i,s.t. 1^T w_i=1$$

闭式解为：

$$w_i=\frac{C_i^{-1}1}{1^T C_i^{-1}1}$$

关于数值稳定性：如果$K>D$，邻居近似共线性，$C_i$可能病态，使用迭代缓解该问题

$$C_i\leftarrow C_i+\epsilon\cdot tr(C_i)I$$

3. 低维嵌入#

有了权重 $w_{ij}$，目标是在低维空间中找到点$y_i\in\mathbb{R}^d,d<<D $，使得同样的重构关系成立

$$y_i\approx \sum_j w_{ij}y_j$$

全局目标函数为：

$$\Phi(Y)=\sum_i\Vert y_i-\sum_j w_{ij}y_j \Vert^2$$

整理成矩阵形式：设$W\in \mathbb{R}^{N\times N}$为稀疏权重矩阵，$M=(I-W)^T(I-W)$，那么有

$$\Phi(Y)=Tr(Y^TMY)$$

可以将上述问题转换为特征值问题