一、换个目标：让邻居投影后还挨着

先把要保住的东西说清楚：如果两个点在原始空间里是近邻，那它们在低维空间里也应该靠得近。 注意这句话只说了「近的还得近」，没说「远的还得远」——这个不对称是刻意的，后面会用到。 那为什么不直接要求「所有两两距离都不变」？ 因为线性的低维投影做不到。一张卷起来的纸摊平之后， 原来隔着两层的点在平面上离得很远——距离必然变。LPP 的策略是放弃远距离的准确性，只死保近距离。 这个取舍有代价：stress 会变差。实测 LPP 的 stress 是 0.1115， 比 PCA 的 0.1029 略差一点点——在这份数据上差得不多， 但在 13.5 节会看到拉普拉斯特征映射把 stress 直接推到 0.50。 和 PCA 的区别可以这么记：PCA 关心「整体展开得漂不漂亮」，LPP 关心「左邻右舍还在不在」。 前者适合看全局形状，后者适合做完之后还要找近邻、做聚类、做分类。

二、把「邻居」写成一张图

「邻居」这个模糊的词必须变成一个矩阵，否则没法进目标函数。做法三步： ① 每个点找最近的 nn 个邻居（本文取 10）；② 在它们之间连边，边权用高斯核 exp(-d²/2) 加权， 越近权重越大；③ 把矩阵对称化，因为「i 是 j 的邻居」和「j 是 i 的邻居」不一定同时成立。 权重的选法有两种常见路线：一种是「连上就是 1，没连就是 0」（0-1 权重），另一种是高斯权重。 0-1 权重简单，但对「差一点点就进不了前 10 名」的点太粗暴； 高斯权重平滑，代价是多了一个带宽参数。本节用高斯权重，带宽直接取 1，因为数据已经归一化过了。 这个图是整章的关键抽象：它把「流形」这个几何概念，变成了一张「谁和谁有边」的稀疏表。 一旦变成图，就可以用矩阵、用特征分解、 用线性代数那一套来处理——这是所有流形学习方法的共同起点。 图的度矩阵 D 是对角矩阵，第 i 个对角元是第 i 个点的所有边权之和。 拉普拉斯矩阵定义成 L 等于 D 减 W，它有一个很好的性质： x'Lx 等于 sum_ij W_ij (x_i - x_j)² 的一半。 这个恒等式是整节的引擎——它把「邻居之间的差距」写成了一个二次型。

三、目标函数与那个不能省的约束

现在把要求写成式子。要最小化的量是「图上每条边的两个端点，投影之后差多少」： a'XLX'a，其中 X 是所有点堆成的矩阵，a 是投影方向。代入上面那个恒等式， 它就等于 sum_ij W_ij (a'x_i - a'x_j)²。 图上连了边的两点，投影之后被拉开的距离，按边权加权求和——这就是全部。 但光有这个目标函数不行。为什么？因为 a 乘上 0.1，目标值就变成原来的百分之一。 实测：原方向的目标值 474.76505，把它乘 0.1 之后是 4.74765，比值 0.010000， 正好是 0.1 的平方。 所以只最小化这一个式子，最优解是 a 等于零向量——所有点挤成一个点， 「邻居之间的距离」当然是零。 这是一个典型的「平凡解陷阱」：目标函数被自己的尺度作弊绕过去了。 约束 a'XDX'a 等于 1 干的事，就是把 a 的尺度钉死。 注意这个约束本身也有含义：a'XDX'a 是投影之后按度加权的方差， 固定它等于 1 等于说「总散开程度不许缩」。 于是问题变成：在「总散开程度不变」的前提下，让「邻居之间的距离」最小。 这句话翻译成人话就是：不许整体缩小，但可以把点重新排布——那就把邻居排到一起。 顺带说一句：这里也是「分母约束」这一套老手法的又一次出现。第 5 章的 ℓ1 约束、 第 11 章 CRF 的正则化，都是同一个思路——目标函数总有尺度作弊的法子，得额外钉一个约束。

四、解是广义特征值问题

带约束的最小化，标准做法是拉格朗日乘子，最后落到一个广义特征值问题：XLX'a 等于 λ XDX'a。 求最小的几个特征值对应的特征向量 a，就是投影方向。 这比 PCA 麻烦一点：PCA 是普通特征分解，这里要解广义问题，代码上得先算 B 的逆再乘 A。 数值上有一个坑：B 可能接近奇异（如果某些点度为 0）， 所以实现里要加一个极小的对角项 1e-9 兜底。 在这份瑞士卷上解出来的三个广义特征值是 0.00432、0.00449、0.01283。 前两个只差 3.7%，几乎简并——意味着存在两个几乎一样好的投影方向，取哪一对都不会差太多。 第三个一下子跳到 0.01283，是三倍，说明第三个方向明显更差。 「简并」这件事值得多说一句：当两个特征值几乎相等时， 对应的两个特征向量在数值上是不唯一的——它们可以在这个二维子空间里任意旋转。 所以 LPP 跑两次、或者换一个数值库，出来的两个坐标可能长得完全不一样， 但作为「一对」是等价的。 判断结果好坏要看保持率和 stress，不要盯着某一张图的坐标轴。

五、54.4% 背后的天花板

现在说这个 54.4% 到底意味着什么。先泼一盆冷水：LPP 的第一维与展开参数 t 的相关只有 0.244。 也就是说，它根本没有把这张卷摊开。 原因很硬：a 是一个 3 维向量，Xa 只能落在三维空间的某个平面上。 「投影」这个词本身就决定了它不能拆层——隔着一层纸的点，压下去还是挨在一起。 LPP 做的事只是：在所有可能的平面里，挑一个让图上邻居尽量不散开的。 挑得不错（从 40.30% 到 54.40%），但天花板就在那儿。 这个天花板有多高？拿真正的低维坐标来定标：弧长 s 与纸宽 h 这一对坐标， 能保住 99.83% 的 10 近邻（13.5 节会详细说这件事）。 40.30%、54.40%、53.40%，三个方法离 99.83% 都还远。 那 LPP 的优势到底在哪？在于它是线性的。 线性有一个巨大的工程好处：新来的点直接乘 a 就能得到低维坐标，不需要重新建图、 不需要重新解特征值。 PCA、LPP 都是这样； 核 PCA 和拉普拉斯特征映射不是——它们没有显式的投影矩阵，新点得另外想办法（外延问题）。 如果系统要在线处理不断到来的数据，这一条常常比多几个百分点的保持率更值钱。

六、结果稳不稳：五个种子

一次实验的数字不能当结论。换五个随机种子重跑：

七、动手 Demo：给近邻加权，找一个不许邻居散开的投影

这段代码先建图、再解广义特征值问题，然后做三件事：和 PCA 比保持率、验证「目标值随尺度平方缩」、 以及看第一维到底有没有把卷摊开。 第二件事是本节的重点：把目标值乘 0.01 看它变成多少，就明白为什么那个约束一行都不能少。

import numpy as np

def dmat(A, B):
    return np.sqrt(np.maximum(((A[:, None, :] - B[None, :, :]) ** 2).sum(-1), 0.0))

def swiss(n=600, seed=1):
    rg = np.random.default_rng(seed)
    t = rg.uniform(1.5 * np.pi, 4.5 * np.pi, n)
    h = rg.uniform(0.0, 10.0, n)
    return np.column_stack([t * np.cos(t), h, t * np.sin(t)]), t

def graph(X, nn=10, sig=1.0):
    D = dmat(X, X)
    np.fill_diagonal(D, np.inf)
    W = np.zeros((len(X), len(X)))
    for i, idx in enumerate(np.argsort(D, axis=1)[:, :nn]):
        W[i, idx] = np.exp(-D[i, idx] ** 2 / (2.0 * sig * sig))
    return np.maximum(W, W.T)

def lpp_dir(X, nn=10, sig=1.0):
    W = graph(X, nn, sig)
    D = np.diag(W.sum(axis=1))
    L = D - W
    A = X.T @ L @ X
    B = X.T @ D @ X + 1e-9 * np.eye(X.shape[1])
    val, vec = np.linalg.eig(np.linalg.solve(B, A))
    o = np.argsort(val.real)
    return vec[:, o].real, val.real[o]

def keep_ratio(X, Z, k=10):
    D1, D2 = dmat(X, X), dmat(Z, Z)
    np.fill_diagonal(D1, np.inf)
    np.fill_diagonal(D2, np.inf)
    a = np.argsort(D1, axis=1)[:, :k]
    b = np.argsort(D2, axis=1)[:, :k]
    hit = sum(len(set(a[i]) & set(b[i])) for i in range(len(a)))
    return hit / float(len(a) * k)

X, t = swiss(600, 1)
vec, val = lpp_dir(X, 10, 1.0)
ZL = X @ vec[:, :2]
print('广义特征值', np.round(val, 5))
print('LPP 保持 %.4f' % keep_ratio(X, ZL))
print('与t的相关 %.3f' % abs(np.corrcoef(ZL[:, 0], t)[0, 1]))

W = graph(X, 10, 1.0)
D = np.diag(W.sum(axis=1))
A = X.T @ (D - W) @ X
a = vec[:, 0]
print('目标值 a      %.5f' % float(a @ A @ a))
print('目标值 0.1a   %.5f' % float((0.1 * a) @ A @ (0.1 * a)))
print('比值          %.6f' % (float((0.1 * a) @ A @ (0.1 * a))
                                / float(a @ A @ a)))

for sd in (1, 2, 3, 4, 5):
    Xs, _ = swiss(600, sd)
    print('种子%d LPP 保持 %.4f' % (sd, keep_ratio(Xs, Xs @ lpp_dir(Xs, 10, 1.0)[0][:, :2])))

实跑输出：

--------------------------------------------------------------------
瑞士卷上 LPP 把近邻保持率从 40.3% 提到 54.4%
--------------------------------------------------------------------
  数据                     600 个三维点，瑞士卷，一张纸卷了一圈半
  邻接图                   每个点连最近的 10 个邻居，边权 exp(-d²/2)

  先把上一节的天花板摆出来当基准：
  方法   10 近邻保持率   stress   与展开参数 t 的相关
  --------------------------------------------------
  PCA           0.4030   0.1029                 0.169
  LPP           0.5440   0.1115                 0.244
  提高 14 个百分点，stress 几乎没变（0.1029 到 0.1115）。

  LPP 的全部想法就一行目标函数：
  **min  a' X L X' a     s.t.  a' X D X' a = 1**
  左边那项展开是 sum_ij W_ij (a'x_i - a'x_j)²：
  图上连了边的两个点，投影之后也不许离得远。
  这是一个广义特征值问题，解出来就是下面这几个数：
  三个广义特征值           0.00432  0.00449  0.01283
  前两个是否简并           是，0.00432 与 0.00449 只差 3.7%
  前两个几乎相等，意味着存在两个几乎一样好的投影方向，取哪一对都不会差太多。

  为什么右边那个约束不能省？把目标函数单独拎出来看：
  目标值（原方向 a）       474.76505
  目标值（a 乘 0.1）       4.74765
  比值                     0.010000  <- 正好是 0.1 的平方
  **目标值随 a 的尺度的平方一起缩，所以光最小化它，最优解是 a 等于零向量。**
  约束 a'XDX'a = 1 干的事，就是把 a 的尺度钉死在单位上，让比较有意义。

  现在说这个 54.4% 到底意味着什么，这里必须泼一盆冷水：
  **LPP 的第一维与展开参数 t 的相关只有 0.244，它根本没有把卷摊开。**
  原因很硬：a 是个 3 维向量，Xa 只能落在三维空间的某个平面上。
  **「投影」这个词就决定了它不能拆层——隔着一层纸的点，压下去还是挨在一起。**
  它做的事只是：在所有可能的平面里，挑一个让图上邻居尽量不散开的。
  挑得不错，但天花板就在那儿。

  换个随机种子再看一遍，别信一次的结果：
  种子      PCA      LPP
  ---------------------
  1      0.4030   0.5440
  2      0.3953   0.5095
  3      0.3900   0.4863
  4      0.3958   0.4645
  5      0.3997   0.4593
  五个种子上 LPP 都赢，但赢得不稳：0.459 到 0.544 都出现过。
  **所以正确的说法是「LPP 在这类弯曲数据上通常比 PCA 好」，不是「LPP 比 PCA 好 14 个百分点」——那些小数位是抽样的运气，不是规律。**

看第一行：三个广义特征值 0.00432、0.00449、0.01283。 前两个只差 3.7%，几乎简并，第三个是三倍——说明前两个方向一样好，第三个明显更差。 这也提醒一件事：简并的时候两个坐标可以在这个子空间里任意转，所以结果图长什么样不重要， 指标才重要。 第二行保持率 0.5440，对比 PCA 的 0.4030，提高 14 个百分点。 第三行与 t 的相关只有 0.244——这是这一节最该盯着的一个数：LPP 提高了近邻保持率， 但它没有把卷摊开，只是换了个更好的投影平面。 中间那三行是约束必要性的证据：目标值 474.76505，把 a 乘 0.1 之后变成 4.74765， 比值 0.010000。 目标值随尺度的平方一起缩，所以「最小化它」这件事本身没有正确答案——除了零向量。 约束 a'XDX'a 等于 1 就是把这条路堵掉。 最后五行换种子，0.5440、0.5095、0.4863、0.4645、0.4593。都赢 PCA，但摆幅接近 9 个百分点。 所以论文和报告里写「提升 14 个点」是不诚实的，该写「在五个抽样上稳定优于 PCA， 幅度 5 到 14 个点」。

30 秒实验

1. 把 lpp_dir 的 nn 从 10 改成 30，再跑一次。 近邻数变大，图变稠，LPP 会越来越像 PCA——因为「邻居」覆盖了全局， 局部保持就退化成全局压缩。
2. 把 graph 里高斯权重的 sig 从 1.0 改成 5.0。 边权变得几乎均匀，图接近「全连接」，LPP 的结果会明显退化。想清楚： 为什么权重的「区分度」很重要？
3. 在 lpp_dir 里把 + 1e-9 * np.eye(...) 删掉（或者改成 0）。 有些数据上会直接报奇异矩阵，有些数据上不报但结果会抖得厉害。 这说明那个小小的兜底项在防什么。

常见误区

1. 「LPP 是 PCA 的改进版，效果更好」。它换的是目标函数，不是精度。 它在近邻保持上更好（0.5440 对 0.4030），在 stress 上略差（0.1115 对 0.1029）， 并且多了一堆要选的参数（近邻数、带宽、权重类型）。
2. 「LPP 把流形摊平了」。 它是线性投影，只能压不能弯。实测第一维与展开参数 t 的相关只有 0.244——卷还是卷着。 要真摊平，得用 13.5 节的拉普拉斯特征映射这类非线性方法。
3. 「目标函数越小说明投影越好」。 目标值可以靠把 a 缩小来作弊，所以必须配一个尺度约束才有意义。 比较两个不同的算法时更是如此：目标函数不同量纲，数值根本不能横向比。
4. 「LPP 能处理新样本，所以比 LE 实用」。前半句对，后半句是取舍不是优劣。 LPP 有显式投影矩阵，新点直接乘； LE 没有，新点通常要训练一个回归去拟合嵌入坐标，或者把新点插进图里重解。 这是「线性带来的便利」换「非线性带来的表达能力」。

LPP 绕开了「方差」这个错误的标准，但没绕开「线性」这个限制。下一节换一条路：不投影到平面上， 而是先把点映射到无穷维空间，再在那里做 PCA——于是「平面」在原始空间里可以是任意弯的曲面。

• ☐ （本节完，下一节 13.4 13.4）

相关笔记

• 主成分分析
• 拉普拉斯特征映射
• 线性降维的原理
• 🤖 图解机器学习 · 索引