局部线性嵌入（LLE）的数学原理

局部线性嵌入（LLE）是一种非线性降维方法，它的目标是在较低维度空间中保持高维数据的局部特征。LLE的步骤可以概括如下：

1. 邻域选择：对于每个数据点 $x_i$，找出其 $k$ 个最近邻。

2. 重建权重计算：对每个点 $x_i$，使用其邻域中的点来线性重建它，并找到重建误差最小的权重系数。这可以通过最小化下列代价函数实现：
   $$\min \sum _i{\left|x_i-\sum _{j\in N(i)}{W}_{ij}{x}_j\right|}^2$$
   其中，$N(i)$ 表示 $x_i$ 的邻域中的点的集合，$W_{ij}$ 是重建权重。

3. 降维映射：在低维空间中寻找点 $y_i$ 的集合，使得这些点保持原始重建权重所表示的局部几何结构。这涉及到最小化以下代价函数：
   $$\min \sum _i{\left|y_i-\sum _{j\in N(i)}{W}_{ij}{y}_j\right|}^2$$

LLE的核心目标是在保留高维空间中局部结构的同时，找到数据点的低维表示 $y_i$。

LLE中的重建权重计算

在LLE算法中，重建权重计算是一个关键步骤，目的是在高维空间中使用每个数据点的邻域来线性重建该点。这一步骤可以分解为以下几个部分：

1. 选择邻域：对于每个数据点 $x_i$，根据某种准则（如欧几里得距离）找出其 $k$ 个最近邻。

2. 计算重建权重：对于每个点 $x_i$，找出一组权重 $W_{ij}$，使得使用这些权重线性组合邻域中的点所得到的重建点 ${\hat{x}}_i={\sum }_{j\in N(i)}{W}_{ij}{x}_j$ 与原始点 $x_i$ 尽可能接近。这通过最小化下列代价函数实现：
   $$\underset{W_{ij}}{\min }\sum _i\Vert x_i-\sum _{j\in N(i)}{W}_{ij}{x}_j{\Vert }^2$$
   其中，约束条件是对于每个 $i$，${\sum }_{j\in N(i)}{W}_{ij}=1$。

示例

假设我们的数据集包含三个点：A $(0,0)$，B $(1,0)$ 和 C $(1,1)$。我们的目标是为点 A 计算重建权重，假设它的最近邻是点 B 和点 C。

1. 定义重建误差：重建误差是原始点和基于其邻居的线性组合之间的差异。对于点 A，这个误差可以表示为：
   $$E=\Vert A-(W_{AB}\cdot B+W_{AC}\cdot C){\Vert }^2$$
   其中，$W_{AB}$ 和 $W_{AC}$ 是我们要找的重建权重。

2. 应用约束条件：在LLE中，每个点的重建权重之和应该等于1，即 $W_{AB}+W_{AC}=1$。这保证了重建过程的稳定性。

3. 构建并求解优化问题：我们需要最小化重建误差 $E$，同时满足权重的约束条件。将点 A, B, C 的坐标代入，并利用约束条件简化表达式，得到一个可以求解的优化问题。

考虑点 A $(0,0)$，点 B $(1,0)$ 和点 C $(1,1)$，我们可以将重建误差 $E$ 表达为：
$$E=\left[(0-W_{AB}\cdot 1-W_{AC}\cdot 1{)}^2+(0-W_{AB}\cdot 0-W_{AC}\cdot 1{)}^2\right]$$
根据约束条件 $W_{AB}+W_{AC}=1$，我们可以替换其中一个权重，比如用 $W_{AB}=1-W_{AC}$，
将 $W_{AB}=1-W_{AC}$ 代入代价函数，得到：
$$E=\left[(0-(1-W_{AC})\cdot 1-W_{AC}\cdot 1{)}^2+(0-(1-W_{AC})\cdot 0-W_{AC}\cdot 1{)}^2\right]$$
简化后得到：
$$E={\left[-2W_{AC}+1\right]}^2+{\left[-W_{AC}\right]}^2$$

4. 求导：对 $E$ 关于 $W_{AC}$ 求导，得到：
   $$\frac{dE}{d{W}_{AC}}=2(-2W_{AC}+1)(-2)+2(-W_{AC})(-1)$$
   简化后得到：
   $$\frac{dE}{d{W}_{AC}}=8W_{AC}-4-2W_{AC}=6W_{AC}-4$$

5. 求解最优权重：令导数等于零解出 $W_{AC}$：
   $$6W_{AC}-4=0⟹W_{AC}=\frac{2}{3}$$
   因此，$W_{AB}=1-W_{AC}=\frac{1}{3}$。

综上所述，对于点 A，最优的重建权重是 $W_{AB}=\frac{1}{3}$ 和 $W_{AC}=\frac{2}{3}$。

这个结果表明，在使用点 B 和点 C 重建点 A 的过程中，点 C 对重建点 A 的贡献比点 B 大。

LLE降维映射的详细解释

在局部线性嵌入（LLE）算法中，降维映射是最后一个步骤，它的目标是在低维空间中找到一个数据点的新表示，这些新表示应保留高维空间中的局部结构。这是通过优化一个新的代价函数来实现的，该函数基于之前计算的重建权重。

1. 定义低维映射的代价函数：假设 $y_i$ 是高维空间中点 $x_i$ 的低维表示。降维映射的目标是最小化以下代价函数：
   $$\Phi =\sum _i\Vert y_i-\sum _{j\in N(i)}{W}_{ij}{y}_j{\Vert }^2$$
   其中，$W_{ij}$ 是之前计算得到的重建权重，$N(i)$ 是点 $x_i$ 的邻域。

2. 优化过程：这个优化过程寻找一组低维表示 { y i } \{y_i\} {yi​}，使得每个点 $y_i$ 与使用其高维邻居的重建权重 $W_{ij}$ 线性组合的低维表示尽可能接近。这个过程通常需要使用数值优化方法来实现，因为直接解析求解可能非常复杂。

3. 保持局部结构：通过这种方式，低维表示 { y i } \{y_i\} {yi​} 能够保留原始高维数据中的局部邻域关系。如果两个高维点在原始空间中彼此接近，它们的低维表示也会彼此接近。

LLE降维映射的示例

假设我们有一个简单的高维数据集，并且我们已经计算出了每个点的重建权重。现在，我们的目标是将这些点映射到低维空间（例如，从3维映射到2维）。我们将展示这个过程的简化版本。

示例数据集

考虑以下三维空间中的四个点：

• 点 A: $(1,2,3)$
• 点 B: $(4,5,6)$
• 点 C: $(7,8,9)$
• 点 D: $(10,11,12)$

假设我们已经根据LLE的第一步计算出了重建权重，例如：

• 对于点 A，邻居是 B 和 C，权重分别是 $W_{AB}=0.5$ 和 $W_{AC}=0.5$。
• 类似地，对于其他点也有类似的邻居和权重。

降维映射

1. 优化问题：我们现在希望找到这些点在二维空间中的新表示 { y i } \{y_i\} {yi​}，使得代价函数 $\Phi$ 最小：
   $$\Phi =\sum _i\Vert y_i-\sum _{j\in N(i)}{W}_{ij}{y}_j{\Vert }^2$$
   在这个例子中，我们将求解一组新坐标 { y A , y B , y C , y D } \{y_A, y_B, y_C, y_D\} {yA​,yB​,yC​,yD​}。

2. 数值求解：在实际应用中，这通常需要使用数值优化方法，如梯度下降或特征值分解，来求解。

3. 构建矩阵M：根据计算出的重建权重，我们构建一个矩阵M。这个矩阵的元素是通过比较每对点之间的重建权重差异得到的。对于点A，B，C和D，这个矩阵可能看起来像这样（这是一个简化的示例）：
   $$M=\left[\begin{array}{cccc}1& -0.3& -0.7& 0\\ -0.3& 1& -0.4& -0.3\\ -0.7& -0.4& 1& -0.1\\ 0& -0.3& -0.1& 1\end{array}\right]$$
   矩阵 M 的构建
   对角线元素：矩阵 $M$ 的每个对角线元素 $M_{ii}$ 反映了点 $i$ 与其邻居的重建权重之和：
   $$M_{ii}=1-\sum _{j\in N(i)}{W}_{ij}^2$$
   其中，$N(i)$ 表示点 $i$ 的邻居集合，$W_{ij}$ 是点 $i$ 用于重建自己的来自邻居 $j$ 的权重。
   非对角线元素（邻居间）：对于邻居点 $i$ 和 $j$，矩阵 $M$ 中的元素 $M_{ij}$ 是它们之间的重建权重：
   $$M_{ij}=-W_{ij}\text{如果}j\in N(i)$$
   这表示点 $i$ 和 $j$ 在重建过程中的直接影响。
   非对角线元素（非邻居间）：对于不是邻居的点 $i$ 和 $j$，矩阵 $M$ 的元素 $M_{ij}$ 设为0：
   $$M_{ij}=0\text{如果}j\notin N(i)\text{且}i\notin N(j)$$

4. 求解特征值问题：接下来，我们解决特征值问题 $Mv=\lambda v$，其中$v$是特征向量，$\lambda$是特征值。我们关注的是最小的非零特征值对应的特征向量。

5. 低维嵌入：找到对应最小非零特征值的特征向量后，这些特征向量（除了对应最小特征值的向量）构成了数据的低维嵌入。在我们的例子中，这将是一个2维表示。

从LLE的特征值和特征向量到低维数据（低维嵌入）

在LLE算法中，一旦计算出矩阵 $M$ 的特征值和特征向量，我们可以按照以下步骤得到数据的低维表示：

特征值和特征向量的计算

1. 求解特征值问题：首先，我们求解特征值问题 $Mv=\lambda v$，其中 $v$ 是特征向量，$\lambda$ 是对应的特征值。通常，这是通过数值方法完成的，如使用Python中的 numpy.linalg.eigh 函数。

2. 排序特征值：求解后，我们得到一系列特征值和相应的特征向量。特征值按照从小到大的顺序排序，与之对应的特征向量也按同样的顺序排列。

选择特征向量以获得低维表示

1. 选择最小的非零特征值：在LLE中，我们通常忽略最小的特征值（通常接近或等于零），因为它对应的特征向量通常是数据的平均值或类似的全局结构。

2. 选择后续特征向量：为了得到 ( k ) 维的低维表示，我们选择紧随最小特征值之后的 ( k ) 个特征向量。例如，如果我们想将数据降至2维，我们将选择第二小和第三小的特征值对应的特征向量。

构建低维数据表示

1. 构建特征向量矩阵：将选定的特征向量组合成一个矩阵，其中每一列是一个特征向量。假设我们选择了第二小和第三小的特征值对应的特征向量，那么这个矩阵将有两列。

2. 转换为低维数据：这个特征向量矩阵就是数据点在低维空间中的新坐标。每个数据点的低维表示是这个矩阵中相应行的值。

代码

import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.linalg import eigh

def compute_reconstruction_weights(X, k):
    n_samples = X.shape[0]
    W = np.zeros((n_samples, n_samples))
    for i in range(n_samples):
        distances = np.sum((X[i] - X) ** 2, axis=1)
        neighbors = np.argsort(distances)[1:k+1]

        # 构建局部邻域矩阵
        K = X[neighbors] - X[i]
        G = K.dot(K.T)
        G_inv = np.linalg.inv(G + np.eye(k) * 1e-3) # 加入小的正则项防止矩阵奇异

        # 计算重建权重
        weights = G_inv.sum(axis=1) / G_inv.sum()
        W[i, neighbors] = weights

    return W

def lle(X, k, n_components):
    W = compute_reconstruction_weights(X, k)

    # 构建矩阵 M
    M = (np.eye(len(X)) - W).T @ (np.eye(len(X)) - W)

    # 计算特征值和特征向量
    eigenvalues, eigenvectors = eigh(M, eigvals=(1, n_components))

    return eigenvectors

# 示例数据（可以是任意高维数据）
np.random.seed(0)
X = np.random.rand(10, 3) # 10个样本，每个样本3维

# 使用LLE降维到2维
embedded_X = lle(X, k=5, n_components=2)

print("低维表示:\n", embedded_X)

结果