只保留邻域配方，弯曲流形怎样展开？LLE 的重构权重与谱嵌入

上一篇的 Isomap 用近邻图最短路近似测地距离，再让低维坐标复现所有样本对的全局距离。它能把瑞士卷摊开，但一条跨折叠捷径会缩短许多路径；当全局距离不够可靠时，我们能否只保存每个点周围的小块几何？

局部线性嵌入（Locally Linear Embedding，LLE）的答案是：**先学习每个点由邻居线性重构的配方，再寻找一组低维坐标，使同一配方仍能重构它。**本文聚焦标准 LLE 的邻域、权重与特征向量解；改进变体只用于说明边界。

01 为什么局部线性比全局距离更容易相信？#

光滑曲面放大一小块后近似平面。即使整条曲线弯曲，一个点通常仍可由两侧邻居线性插值得到：

高维弯曲流形                       低维展开

      x₂                              y₂
    ╱    ╲                           ╱  ╲
  x₁   xᵢ   x₃        ──►           y₁  yᵢ  y₃
       ↑                              ↑
  xᵢ ≈ 0.5x₁+0.5x₃              yᵢ ≈ 0.5y₁+0.5y₃

保存的不是绝对坐标，而是邻域里的重构权重

text

旋转、平移或把整块流形弯起来，局部“谁能由谁拼出”的关系可能仍保持。LLE 用这些局部配方代替 Isomap 的全局测地距离。

02 完整数据流与张量形状#

设 $X\in\mathbb R^{N\times D}$ ，每点有 $K$ 个邻居，输出维数为 $d$ ：

X [N,D]
  │ KNN
  ▼
J [N,K]：每点邻居索引
  │ 每点解一个 K×K 线性系统
  ▼
W [N,N]：稀疏重构权重，每行仅 K 个非零，行和为 1
  │ M=(I-W)ᵀ(I-W)
  ▼
M [N,N]：全局嵌入代价矩阵
  │ 最小的 d+1 个特征向量，丢弃常数向量
  ▼
Y [N,d]：低维坐标

text

训练分两次优化：先固定原数据学习 $W$ ，再固定 $W$ 学习 $Y$ 。它不是用梯度下降同时更新一个神经网络。

03 每个点的重构权重优化什么？#

记点 $x_i\in\mathbb R^D$ 的近邻集合为 $\mathcal N(i)$ ，LLE 求：

\min_{w_i}\left\lVert x_i-\sum_{j\in\mathcal N(i)}w_{ij}x_j\right\rVert_2^2, \qquad \sum_jw_{ij}=1

和为 1 的约束让权重对整体平移不变。若所有点都加向量 $a$ ：

\sum_jw_{ij}(x_j+a)=\sum_jw_{ij}x_j+a

因此重构误差不因坐标原点改变。标准 LLE 的权重可以为负；它是局部仿射坐标，不是概率。

把邻居相对中心点的差写成：

Z_i=\begin{bmatrix} (x_{j_1}-x_i)^\top\\ \vdots\\ (x_{j_K}-x_i)^\top \end{bmatrix}\in\mathbb R^{K\times D}

局部协方差（更准确地说是局部 Gram 矩阵）为：

C_i=Z_iZ_i^\top\in\mathbb R^{K\times K}

目标变成 $w_i^\top C_iw_i$ 。带和约束的解可由一次线性方程得到：

C_i\tilde w_i=\mathbf1, \qquad w_i=\frac{\tilde w_i}{\mathbf1^\top\tilde w_i}

实现时应使用 solve，不要显式计算 $C_i^{-1}$ 。

04 两个邻居的手算例为何暴露病态矩阵？#

一维点 $x_i=1$ 的两个邻居是 $x_1=0,x_2=2$ 。直觉上：

x_i=0.5x_1+0.5x_2

相对差与局部矩阵是：

Z_i=\begin{bmatrix}-1\\1\end{bmatrix},\qquad C_i=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}

$C_i$ 的两行互为相反数，行列式为 0，无法直接求解。这不是偶然：当 $K>D$ 或邻域位于更低维平面时， $C_i$ 最多只有秩 $D$ 。

标准做法是按局部尺度加对角正则：

C_i' = C_i + r\operatorname{tr}(C_i)I

若 $r=10^{-3}$ ，这里对角线各加 0.002。由对称性，求解并归一化后仍得 $w_i=[0.5,0.5]$ ，但线性系统现在可逆。

05 低维坐标为何仍用同一组权重？#

权重固定后，LLE 求低维点 $y_i\in\mathbb R^d$ ：

\min_Y\Phi(Y)=\sum_i\left\lVert y_i-\sum_jw_{ij}y_j\right\rVert_2^2

把所有权重放入 $W\in\mathbb R^{N\times N}$ ，则：

\Phi(Y)=\lVert(I-W)Y\rVert_F^2 =\operatorname{tr}(Y^\top MY), \qquad M=(I-W)^\top(I-W)

若不加约束，所有 $y_i=0$ 就能让代价为 0。为排除平移与塌缩，常要求：

Y^\top\mathbf1=0, \qquad \frac1N Y^\top Y=I_d

于是解为 $M$ 最小的非平凡特征向量。由于 $W\mathbf1=\mathbf1$ ，有 $(I-W)\mathbf1=0$ ；最小特征值对应常数向量，只表示整体平移，必须丢弃。接下来的 $d$ 个特征向量形成嵌入。

M 的特征值：  0       λ₁       λ₂       λ₃ ...
               │        │        │
             常数     坐标1    坐标2
             丢弃      └── Y [N,2] ──┘

text

特征向量可整体变号，多个接近的特征值还允许子空间内旋转。因此比较两次嵌入时，应先做 Procrustes 对齐，不能逐坐标要求完全相等。

06 训练算法伪代码#

input: X [N,D], K, d, reg
J = knn_indices(X, K)                            # [N,K]
W = zeros(N,N)

for i in 0..N-1:
    Z = X[J[i]] - X[i]                          # [K,D]
    C = Z @ Z.T                                 # [K,K]
    C += reg * trace(C) * I                     # 局部尺度正则
    raw = solve(C, ones(K))                     # [K]
    W[i, J[i]] = raw / sum(raw)                 # 行和为 1

M = (I-W).T @ (I-W)                            # [N,N]
values, vectors = eigh(M)                       # 升序
Y = sqrt(N) * vectors[:, 1:d+1]                 # 跳过常数向量
return Y, W, J

text

工程实现通常保留稀疏 $W$ 并使用部分特征分解；教学版的稠密矩阵只适合小数据。

07 不调用 LLE，写出最小 NumPy 实现#

import numpy as np

def standard_lle(X, n_neighbors=8, n_components=2, reg=1e-3):
    X = np.asarray(X, dtype=float)                    # [N,D]
    n_samples = X.shape[0]
    if not n_components < n_neighbors < n_samples:
        raise ValueError('需要 n_components < n_neighbors < n_samples')

    distances2 = ((X[:, None, :] - X[None, :, :]) ** 2).sum(axis=2)
    np.fill_diagonal(distances2, np.inf)
    neighbors = np.argsort(distances2, axis=1)[:, :n_neighbors]  # [N,K]

    W = np.zeros((n_samples, n_samples))              # 教学用稠密 [N,N]
    ones = np.ones(n_neighbors)
    for i, idx in enumerate(neighbors):
        Z = X[idx] - X[i]                             # [K,D]
        C = Z @ Z.T                                   # [K,K]
        scale = np.trace(C)
        C.flat[:: n_neighbors + 1] += reg * max(scale, 1e-12)
        weights = np.linalg.solve(C, ones)
        weights /= weights.sum()
        W[i, idx] = weights

    A = np.eye(n_samples) - W
    M = A.T @ A                                       # [N,N]
    eigenvalues, eigenvectors = np.linalg.eigh(M)
    Y = np.sqrt(n_samples) * eigenvectors[:, 1:n_components + 1]

    assert np.allclose(W.sum(axis=1), 1.0)
    assert np.allclose(Y.mean(axis=0), 0.0, atol=1e-8)
    return Y, W, neighbors, eigenvalues

python

这段实现的近邻搜索、 $W$ 和特征分解都是平方级内存，不用于大规模生产；它的作用是让每个数组和约束都可检查。

08 用 scikit-learn 1.9 正确落地#

当前官方 LocallyLinearEmbedding API ↗ 提供标准方法和三个变体：

import numpy as np
from sklearn.manifold import LocallyLinearEmbedding, trustworthiness
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)       # [N,D]

lle = LocallyLinearEmbedding(
    n_neighbors=12,
    n_components=2,
    reg=1e-3,
    method='standard',       # standard / modified / hessian / ltsa
    eigen_solver='auto',     # auto / arpack / dense
    random_state=42,         # eigen_solver='arpack' 时控制随机性
    n_jobs=-1,
)
Y_train = lle.fit_transform(X_train_scaled)           # [N,2]

assert Y_train.shape == (len(X_train), 2)
assert lle.embedding_.shape == Y_train.shape
assert np.isfinite(lle.reconstruction_error_)

score = trustworthiness(
    X_train_scaled,
    Y_train,
    n_neighbors=12,
)

python

embedding_ 是训练坐标，reconstruction_error_ 是当前嵌入的重构代价，nbrs_ 保存拟合后的近邻搜索器。误差只衡量模型自己的目标；一个过大的邻域仍可能得到数值较小却几何错误的结果。

官方文档提醒 ARPACK 在部分问题上不稳定。若出现不收敛或不同种子差异大，先检查近邻图和局部病态性，再比较多个随机种子或小数据上的 eigen_solver='dense'；不要只机械增加 max_iter。

09 新样本 transform 的能力与边界#

scikit-learn 1.9 提供训练外变换：

X_valid_scaled = scaler.transform(X_valid)           # [Q,D]
Y_valid = lle.transform(X_valid_scaled)               # [Q,2]

python

新点会在训练集邻域中获得局部权重，再用训练嵌入坐标重构位置；训练点不会为它重新移动。这种扩展适合靠近训练流形的新点，不能证明远离流形的查询仍有意义。

官方还特别提醒：transform 的缩放行为不适合直接与 SVM 等非尺度不变方法无检查组合。若低维坐标要进入下游模型，应在每个训练折内拟合“原特征缩放 → LLE → 低维再缩放 → 预测器”，并用部署时完全相同的顺序变换验证集。

10 K、正则和维数怎样调？#

邻域数 $K$ 同时控制几何与数值：

K 太小：图可能断开，局部估计对噪声和单点删除敏感。
K 太大：一个邻域跨过弯折、分支或不同层，局部线性假设被破坏；当 $K>D$ 时局部矩阵还天然秩亏。
正则太小：病态线性系统产生巨大正负权重；太大则抹平真实局部方向。
d 太小：必须折叠本来不同的内在方向；太大可能保存噪声与不稳定特征向量。

建议联合记录：近邻图连通分量、邻居距离分位数、每个 $C_i$ 的条件数、最大 $|w_{ij}|$ 、负权重比例、特征值间隙、reconstruction_error_、信任度、重采样稳定性和下游验证分数。

11 常见错误与最短调试路径#

把权重当概率：检查是否存在负值；它们是仿射重构系数，行和为 1 不代表非负。
忘记排除自身近邻：自身权重为 1 会让局部目标退化；断言邻居索引不含行号。
显式求逆：用 solve(C, ones)，并记录条件数和失败点。
统一加固定绝对正则：不同尺度邻域受影响不同；标准 LLE 按 trace(C) 缩放正则。
只看二维图挑参数：视觉判断易受旋转、颜色与抽样影响；加入信任度、稳定性和任务指标。
全数据先拟合再切分：验证样本参与近邻和全局特征向量；所有无监督步骤也必须只在训练折拟合。
逐坐标比较两次结果：先消除平移、旋转、反射与尺度自由度，再判断结构是否改变。

12 它会在哪些流形上失败？#

标准 LLE 对非均匀采样、强噪声、异常点、相交流形和分支结构敏感。曲率半径小于邻域尺度时，一个局部块不再近似平面；靠近边界的点只有单侧邻居，权重也更不稳定。

大规模时，近邻搜索之外还要为每个点解 $K\times K$ 线性系统，并求 $N\times N$ 稀疏矩阵的部分特征向量。官方给出的标准 LLE 复杂度包含 $O(DNK^3)$ 的权重构造和约 $O(dN^2)$ 的特征步骤；它并非百万样本默认降维器。

method='modified' 用多组权重缓解标准 LLE 的正则问题；hessian 与 ltsa 保存不同的局部微分结构，并有更严格的邻居数要求。它们不是无条件升级，仍需基于数据、稳定性和官方约束验证。

13 与相近方法的边界#

方法	保存的核心关系	错误传播方式	主要适用与限制
PCA	全局线性投影与方差	全局但目标凸、稳定	快、可外推；不能展开非线性流形
Isomap	所有点对的图测地距离	一条捷径可改写许多最短路	保留全局距离；怕断图与短路
LLE	每点的局部线性重构权重	先局部建权重，再由谱解全局耦合	保存局部配方；怕病态邻域
Laplacian Eigenmaps	邻边在低维仍靠近	由图拉普拉斯传播	与谱聚类紧密；不显式保存重构配方
t-SNE	高低维邻域概率匹配	强调局部概率、牺牲全局尺度	可视化强；簇距与面积不宜直接解释

LLE 适合“局部可以近似为线性片，并且局部重构关系比全局距离更可信”的中小规模数据。它仍是基于样本图的转导式几何方法，不会自动学得可泛化的深层语义表示。

14 今天真正需要记住什么？#

LLE 先在每个高维邻域求和为 1 的线性重构权重，再用 $M=(I-W)^\top(I-W)$ 的最小非平凡特征向量寻找低维坐标。核心风险在邻域病态、正则敏感和全局谱求解；可靠实践必须检查权重、条件数、特征值、重采样稳定性、训练外接入和数据泄漏，而不是把 fit_transform 当成黑盒绘图函数。

15 思考题与小练习#

在手算例中把邻居改为 $x_1=0,x_2=3$ ，在和为 1 的约束下求能精确重构 $x_i=1$ 的两个权重。它们是否仍各为 0.5？
对 S 曲线扫描 n_neighbors={4,8,16,32} 和 reg={1e-5,1e-3,1e-1}，记录最大绝对权重、负权重比例、重构误差与信任度，解释几何错误和数值错误的区别。
删除一个近邻图中的“桥点”，对两次 LLE 嵌入做 Procrustes 对齐后比较。哪些变化只是坐标自由度，哪些表示全局结构真的不稳定？

16 下一篇预告#

Isomap 与 LLE 都试图保存确定性的几何关系。下一篇将转向面向可视化的概率邻域：t-SNE 怎样把高维相似度变成条件概率，并用重尾分布缓解低维空间的拥挤问题，同时看清“簇之间很远”为什么不等于原数据真的相距很远。

01 为什么局部线性比全局距离更容易相信？#

02 完整数据流与张量形状#

03 每个点的重构权重优化什么？#

04 两个邻居的手算例为何暴露病态矩阵？#

05 低维坐标为何仍用同一组权重？#

06 训练算法伪代码#

07 不调用 LLE，写出最小 NumPy 实现#

08 用 scikit-learn 1.9 正确落地#

09 新样本 transform 的能力与边界#

10 K、正则和维数怎样调？#

11 常见错误与最短调试路径#

12 它会在哪些流形上失败？#

13 与相近方法的边界#

14 今天真正需要记住什么？#

15 思考题与小练习#

相关工作#

16 下一篇预告#