Locally Linear Embedding.

局部线性嵌入(locally linear embedding, LLE)是一种流形学习的降维方法。LLE旨在高维空间中的样本点的局部线性关系在降维后的低维空间中得以保持。 与多维缩放 MDS和等度量映射 ISOMAP方法试图保持近邻样本之间的距离不同；LLE试图保持邻域内样本之间的线性关系，与局部保留投影 LPP类似。

1. LLE建模

低维流形空间通常在局部与欧氏空间同胚，这意味着流形在局部具有欧氏空间的性质。 对于任意样本点$x_i \in \Bbb{R}^{1 \times d}$，选择与其邻近的$k$个样本点$x_j$，根据局部的线性关系，样本点$x_j$可以被其邻域内的样本点$x_j$线性表示：

邻域样本点的选择有两种方法。可以选择与每个点欧氏距离最近的$k$个点作为邻近点，此时称为$k$近邻；也可以选择与每个点欧氏距离小于$\epsilon$的点作为邻近点，此时称为$\epsilon$近邻。

LLE试图保留邻域内样本点之间的线性关系。即样本$x_i$的降维表示$z_i$仍然可以由邻域样本$x_j$的降维表示$z_j$和上述权重$w_{ij}$线性表示：

2. 求解LLE

① 高维空间中求解权重

LLE将原始样本空间中的任意样本点$x_i \in \Bbb{R}^{1 \times d}$表示为其邻近的$k$个样本点$X_i \in \Bbb{R}^{k \times d}$的线性组合：

其中线性权重$W_i \in \Bbb{R}^{1 \times k}$是待求解的参数。进一步约束权重是归一化的，即$W_i\cdot 1_k=1$，其中$1_k$是全$1$列向量。

将权重$W_i$的求解建模为最小化问题：

采用拉格朗日方法求解上述问题，建立拉格朗日函数：

记$S_i=(1_kx_i- X_i) (1_kx_i- X_i)^T \in \Bbb{R}^{k \times k}$，则拉格朗日函数简化为：

对上式求导(值得一提的是，求导结果应和所求参数具有相同的张量尺寸)：

令导数为零得到$W_i S_i=\lambda 1_k^T$，即$W_i =\lambda 1_k^TS_i^{-1}$。进一步注意到约束项：

因此$\lambda = \frac{1}{1_k^TS_i^{-1}1_k}$，可以得到权重$W_i$的解：

注意到$1_k$是全$1$列向量，因此$1_k^TS_i^{-1}$表示对矩阵$S_i^{-1}$按列求和；$1_k^TS_i^{-1}1_k$表示求矩阵$S_i^{-1}$所有元素的和。

② 低维空间中应用权重

在高维样本空间学习到权重$W_i$后，将其应用到降维后的低维空间中。

对于样本$x_i$的降维表示$z_i \in \Bbb{R}^{1 \times d’}$及其邻域样本$X_i$的降维表示$Z_i \in \Bbb{R}^{k \times d’}$，建立最小化问题：

将$W_i \in \Bbb{R}^{1 \times k}$扩充为$W \in \Bbb{R}^{1 \times N}$，无关位置填充为$0$。则优化问题可由降维后的全体样本$Z \in \Bbb{R}^{N \times d’}$表示，并可进一步表示为：

通常对低维空间中的待求解特征增加标准化约束，使其特征维度的方差为零，即：

最终的优化问题可写作：

上式为瑞利商，因此降维表示$Z$可以由矩阵$(I_{N\times N}-W)^T(I_{N\times N}-W)$最小的$k$个特征值对应的特征向量构造。具体地，采用拉格朗日方法求解上述问题，建立拉格朗日函数：

对上式求导(值得一提的是，求导结果应和所求参数具有相同的张量尺寸)：

令导数为零，得到：

记$M=(I_{N\times N}-W)^T(I_{N\times N}-W) \in \Bbb{R}^{N \times N}$，注意到降维后的样本矩阵$Z$就是$M$的特征向量矩阵。

目标函数最小等价于$\lambda$最小，因此选取$d’$个最小的特征值对应的特征向量构成降维矩阵。

在实践中由于最小的特征值接近$0$，因此选取除最小特征值外最小的$d’$个特征值对应的特征向量。

3. 实现LLE

① LLE from scratch

由上述介绍，LLE的一般步骤如下：

1. 给定输入样本$X \in \Bbb{R}^{N \times d}$、近邻参数$k$和降维维度$d’$;
2. 对于每个样本点$x_i$计算与其距离最近的$k$个样本点$X_i \in \Bbb{R}^{k \times d}$；
3. 计算矩阵$S_i=(1_kx_i- X_i) (1_kx_i- X_i)^T \in \Bbb{R}^{k \times k}$；
4. 对样本点$x_i$计算权重参数$W_i =\frac{1_k^TS_i^{-1}}{1_k^TS_i^{-1}1_k}$；
5. 将$W_i \in \Bbb{R}^{1 \times k}$扩充为$W \in \Bbb{R}^{1 \times N}$，无关位置填充为$0$；
6. 计算矩阵$M=(I_{N\times N}-W)^T(I_{N\times N}-W) \in \Bbb{R}^{N \times N}$；
7. 对矩阵$M$进行特征值分解，选取除最小特征值外最小的$d’$个特征值对应的特征向量构成降维矩阵$Z \in \Bbb{R}^{N \times d’}$

def LLE(data, n_dims=2, n_neighbors=12):
    N, d = data.shape
    D = np.zeros([N, N])
    # 计算距离矩阵D
    for i in range(N):
        for j in range(N):
            D[i, j] = np.sqrt(np.sum((data[i]-data[j])**2))
    # 计算样本邻域
    index = np.argsort(D, axis=1)[:,1:n_neighbors+1]
    # 计算权重Wi
    Wi = np.zeros([N, n_neighbors])
    for i in range(N):
        Xi = data[index[i]]
        xi = [data[i]]
        I = np.ones([n_neighbors,1])
        Si = np.dot(I.dot(xi)-Xi, (I.dot(xi)-Xi).T)
        Si_inv = np.linalg.pinv(Si)
        Wi[i] = I.T.dot(Si_inv)/(I.T.dot(Si_inv).dot(I))
    # 扩充Wi为W
    W = np.zeros([N, N])
    for i in range(N):
        W[i, index[i]] = Wi[i]
    # 计算矩阵M
    I = np.eye(N)
    M = np.dot((I-W).T, I-W)
    # 计算特征值和特征向量
    eig_values, eig_vectors = np.linalg.eig(M)
    # 选择前n_dims个最小的特征值标号
    index = np.argsort(eig_values)[1:n_dims+1]
    # 选择对应的特征值和特征向量
    reduced_data = eig_vectors[:, index]
    return reduced_data

② LLE from sklearn

LLE也可以通过sklearn库快速实现：

import matplotlib.pyplot as plt
from sklearn.datasets import make_swiss_roll
from sklearn.manifold import LocallyLinearEmbedding

data, color = make_swiss_roll(n_samples=500)
X_lle = LocallyLinearEmbedding(n_components=2, n_neighbors = 12).fit_transform(data)

plt.figure(figsize=(10, 5))
plt.scatter(X_lle[:, 0], X_lle[:, 1], c=color, label="LLE")
plt.legend()
plt.show()