2.2. 流形学习

寻找最基本的需求

最简单的基本需求

忘掉烦恼和斗争

我是说基本需求

老母亲大自然的食谱

带来了人生的基本需求

– 巴鲁之歌 [丛林之书]

流形学习是一种非线性降维方法。用于此任务的算法基于这样的思想：许多数据集的维度只是人为地高。

2.2.1. 引言

高维数据集非常难以可视化。虽然二维或三维数据可以绘制出来以显示数据的固有结构，但等效的高维图则不那么直观。为了帮助可视化数据集的结构，必须以某种方式降低维度。

实现这种降维的最简单方法是对数据进行随机投影。尽管这允许一定程度的数据结构可视化，但选择的随机性还有很多不足之处。在随机投影中，数据中更有趣的结构很可能会丢失。

为了解决这个问题，已经设计了许多有监督和无监督的线性降维框架，例如主成分分析（PCA）、独立成分分析、线性判别分析等。这些算法定义了特定的规则来选择数据的“有趣”线性投影。这些方法可能很强大，但通常会忽略数据中重要的非线性结构。

流形学习可以被认为是尝试将 PCA 等线性框架推广到对数据中的非线性结构敏感。尽管存在有监督的变体，但典型的流形学习问题是无监督的：它从数据本身学习数据的高维结构，而无需使用预先确定的分类。

示例

• 有关手写数字降维的示例，请参阅手写数字上的流形学习：局部线性嵌入、Isomap...。

• 有关玩具“S 曲线”数据集降维的示例，请参阅流形学习方法比较。

• 有关使用流形学习根据历史股票价格映射股票市场结构的示例，请参阅可视化股票市场结构。

• 有关将流形学习技术应用于球形数据集的示例，请参阅切断球体上的流形学习方法。

• 有关在 Swiss Roll 数据集上使用流形学习技术的示例，请参阅Swiss Roll 和 Swiss-Hole 降维。

scikit-learn 中可用的流形学习实现总结如下

2.2.2. Isomap

Isomap 算法是最早的流形学习方法之一，它是等距映射（Isometric Mapping）的缩写。Isomap 可以看作是多维尺度分析（MDS）或核 PCA 的扩展。Isomap 寻找一个低维嵌入，它保持所有点之间的测地距离。可以使用对象 Isomap 执行 Isomap。

复杂性

Isomap 算法包括三个阶段

1. 最近邻搜索。 Isomap 使用 BallTree 进行高效的邻居搜索。对于 \(N\) 个点在 \(D\) 维空间中的 \(k\) 个最近邻，成本约为 \(O[D \log(k) N \log(N)]\)。

2. 最短路径图搜索。 已知最有效的算法是 Dijkstra 算法，其复杂度约为 \(O[N^2(k + \log(N))]\)，或 Floyd-Warshall 算法，其复杂度为 \(O[N^3]\)。用户可以使用 Isomap 的 path_method 关键字选择算法。如果未指定，代码会尝试为输入数据选择最佳算法。

3. 部分特征值分解。 嵌入被编码在对应于 \(N \times N\) isomap 核的前 \(d\) 个最大特征值的特征向量中。对于密集求解器，成本约为 \(O[d N^2]\)。使用 ARPACK 求解器通常可以提高此成本。用户可以使用 Isomap 的 eigen_solver 关键字指定特征求解器。如果未指定，代码会尝试为输入数据选择最佳算法。

Isomap 的总复杂度为 \(O[D \log(k) N \log(N)] + O[N^2(k + \log(N))] + O[d N^2]\)。

• \(N\) : 训练数据点的数量

• \(D\) : 输入维度

• \(k\) : 最近邻居的数量

• \(d\) : 输出维度

References

• “A global geometric framework for nonlinear dimensionality reduction” Tenenbaum, J.B.; De Silva, V.; & Langford, J.C. Science 290 (5500)

2.2.3. 局部线性嵌入（Locally Linear Embedding）

局部线性嵌入（LLE）寻找一个保持局部邻域内距离的低维数据投影。它可以被认为是全局比较一系列局部主成分分析，以找到最佳非线性嵌入。

可以使用函数 locally_linear_embedding 或其面向对象的对应项 LocallyLinearEmbedding 来执行局部线性嵌入。

复杂性

标准 LLE 算法包括三个阶段

1. 最近邻搜索。参见上面 Isomap 下的讨论。

2. 权重矩阵构建。 \(O[D N k^3]\)。LLE 权重矩阵的构建涉及为 \(N\) 个局部邻域中的每一个求解一个 \(k \times k\) 线性方程。

3. 部分特征值分解。参见上面 Isomap 下的讨论。

标准 LLE 的总复杂度为 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[d N^2]\)。

• \(N\) : 训练数据点的数量

• \(D\) : 输入维度

• \(k\) : 最近邻居的数量

• \(d\) : 输出维度

References

• “Nonlinear dimensionality reduction by locally linear embedding” Roweis, S. & Saul, L. Science 290:2323 (2000)

2.2.4. 改进的局部线性嵌入（Modified Locally Linear Embedding）

LLE 的一个众所周知的问题是正则化问题。当邻居数量大于输入维度数量时，定义每个局部邻域的矩阵是秩亏损的。为了解决这个问题，标准 LLE 应用一个任意的正则化参数 \(r\)，它相对于局部权重矩阵的迹来选择。尽管可以形式上证明当 \(r \to 0\) 时，解收敛到所需的嵌入，但不能保证当 \(r > 0\) 时能找到最优解。这个问题表现为嵌入会扭曲流形的底层几何结构。

解决正则化问题的一种方法是在每个邻域中使用多个权重向量。这是改进的局部线性嵌入（MLLE）的精髓。可以使用函数 locally_linear_embedding 或其面向对象的对应项 LocallyLinearEmbedding 来执行 MLLE，使用关键字 method = 'modified'。它要求 n_neighbors > n_components。

复杂性

MLLE 算法包括三个阶段

1. 最近邻搜索。与标准 LLE 相同

2. 权重矩阵构建。大约 \(O[D N k^3] + O[N (k-D) k^2]\)。第一项与标准 LLE 完全等效。第二项与从多个权重构建权重矩阵有关。实际上，与阶段 1 和阶段 3 的成本相比，构建 MLLE 权重矩阵的额外成本相对较小。

3. 部分特征值分解。与标准 LLE 相同

MLLE 的总复杂度为 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[N (k-D) k^2] + O[d N^2]\)。

• \(N\) : 训练数据点的数量

• \(D\) : 输入维度

• \(k\) : 最近邻居的数量

• \(d\) : 输出维度

References

• “MLLE: Modified Locally Linear Embedding Using Multiple Weights” Zhang, Z. & Wang, J.

2.2.5. Hessian Eigenmapping（HLLE）

Hessian Eigenmapping（也称为基于 Hessian 的 LLE：HLLE）是解决 LLE 正则化问题的另一种方法。它围绕每个邻域的基于 Hessian 的二次形式展开，用于恢复局部线性结构。尽管其他实现注意到它随数据大小的缩放性较差，但 sklearn 实现了一些算法改进，使其对于较小的输出维度，成本与其他 LLE 变体相当。可以使用函数 locally_linear_embedding 或其面向对象的对应项 LocallyLinearEmbedding 来执行 HLLE，使用关键字 method = 'hessian'。它要求 n_neighbors > n_components * (n_components + 3) / 2。

复杂性

HLLE 算法包括三个阶段

1. 最近邻搜索。与标准 LLE 相同

2. 权重矩阵构建。大约 \(O[D N k^3] + O[N d^6]\)。第一项反映了与标准 LLE 相似的成本。第二项来自于局部 Hessian 估计器的 QR 分解。

3. 部分特征值分解。与标准 LLE 相同。

标准 HLLE 的总复杂度为 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[N d^6] + O[d N^2]\)。

• \(N\) : 训练数据点的数量

• \(D\) : 输入维度

• \(k\) : 最近邻居的数量

• \(d\) : 输出维度

References

• “Hessian Eigenmaps: Locally linear embedding techniques for high-dimensional data” Donoho, D. & Grimes, C. Proc Natl Acad Sci USA. 100:5591 (2003)

2.2.6. 谱嵌入（Spectral Embedding）

谱嵌入是一种计算非线性嵌入的方法。Scikit-learn 实现了拉普拉斯特征图（Laplacian Eigenmaps），它使用图拉普拉斯矩阵的谱分解来寻找数据的低维表示。生成的图可以被认为是高维空间中低维流形的离散近似。基于图的成本函数的最小化确保了流形上彼此靠近的点在低维空间中也被映射到彼此靠近的位置，从而保留了局部距离。可以使用函数 spectral_embedding 或其面向对象的对应项 SpectralEmbedding 来执行谱嵌入。

复杂性

谱嵌入（拉普拉斯特征图）算法包括三个阶段

1. 加权图构建。使用亲和度（邻接）矩阵表示将原始输入数据转换为图表示。

2. 图拉普拉斯矩阵构建。未归一化的图拉普拉斯矩阵构建为 \(L = D - A\)，归一化的图拉普拉斯矩阵构建为 \(L = D^{-\frac{1}{2}} (D - A) D^{-\frac{1}{2}}\)。

3. 部分特征值分解。对图拉普拉斯矩阵进行特征值分解。

谱嵌入的总复杂度为 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[d N^2]\)。

• \(N\) : 训练数据点的数量

• \(D\) : 输入维度

• \(k\) : 最近邻居的数量

• \(d\) : 输出维度

References

• “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation” M. Belkin, P. Niyogi, Neural Computation, June 2003; 15 (6):1373-1396.

2.2.7. 局部切线空间对齐（Local Tangent Space Alignment）

尽管从技术上讲不是 LLE 的变体，但局部切线空间对齐（LTSA）在算法上与 LLE 足够相似，可以归入此类。LTSA 并不像 LLE 那样侧重于保持邻域距离，而是通过其切线空间来表征每个邻域的局部几何形状，并执行全局优化以对齐这些局部切线空间以学习嵌入。LTSA 可以使用函数 locally_linear_embedding 或其面向对象的对应项 LocallyLinearEmbedding 来执行，使用关键字 method = 'ltsa'。

复杂性

LTSA 算法包括三个阶段

1. 最近邻搜索。与标准 LLE 相同

2. 权重矩阵构建。大约 \(O[D N k^3] + O[k^2 d]\)。第一项反映了与标准 LLE 相似的成本。

3. 部分特征值分解。与标准 LLE 相同

标准 LTSA 的总复杂度为 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[k^2 d] + O[d N^2]\)。

• \(N\) : 训练数据点的数量

• \(D\) : 输入维度

• \(k\) : 最近邻居的数量

• \(d\) : 输出维度

References

• “Principal manifolds and nonlinear dimensionality reduction via tangent space alignment” Zhang, Z. & Zha, H. Journal of Shanghai Univ. 8:406 (2004)

2.2.8. 多维尺度分析（Multi-dimensional Scaling, MDS）

多维尺度分析（MDS 和 ClassicalMDS）寻找数据的低维表示，其中距离近似于原始高维空间中的距离。

通常，MDS 是一种用于分析相异性数据的技术。它试图将相异性建模为欧几里得空间中的距离。数据可以是对象之间的相异性评级、分子之间的相互作用频率或国家之间的贸易指数。

存在三种类型的 MDS 算法：度量型、非度量型和经典型。在 scikit-learn 中，类 MDS 实现了度量型和非度量型 MDS，而 ClassicalMDS 实现了经典型 MDS。在度量型 MDS 中，嵌入空间中的距离被设置为尽可能接近相异性数据。在非度量型版本中，算法将尝试保留距离的顺序，从而寻求嵌入空间中的距离与输入相异性之间的单调关系。最后，经典型 MDS 接近 PCA，它不是近似距离，而是近似成对标量积，这是一个具有特征分解解析解的更简单的优化问题。

设 \(\delta_{ij}\) 为 \(n\) 个输入点之间的相异性矩阵（可能源自输入点坐标 \(X\) 之间的成对距离 \(d_{ij}(X)\)）。差异 \(\hat{d}_{ij} = f(\delta_{ij})\) 是相异性的一些变换。MDS 目标（称为原始应力）定义为 \(\sum_{i < j} (\hat{d}_{ij} - d_{ij}(Z))^2\)，其中 \(d_{ij}(Z)\) 是嵌入点坐标 \(Z\) 之间的成对距离。

度量型 MDS

在度量型 MDS 模型中（有时也称为绝对 MDS），差异简单地等于输入相异性 \(\hat{d}_{ij} = \delta_{ij}\)。

非度量型 MDS

非度量型 MDS 专注于数据的排序。如果 \(\delta_{ij} > \delta_{kl}\)，则嵌入旨在强制执行 \(d_{ij}(Z) > d_{kl}(Z)\)。强制执行正确排序的一种简单算法是使用 \(d_{ij}(Z)\) 对 \(\delta_{ij}\) 进行保序回归，生成差异 \(\hat{d}_{ij}\)，这些差异是相异性 \(\delta_{ij}\) 的单调变换，因此具有相同的顺序。这在优化算法的每一步之后重复进行。为了避免所有嵌入点重叠的平凡解，差异 \(\hat{d}_{ij}\) 被归一化。

请注意，由于我们只关心相对顺序，我们的目标应该对简单的平移和缩放不变，但在度量型 MDS 中使用的应力对缩放敏感。为了解决这个问题，非度量型 MDS 返回归一化的应力，也称为 Stress-1，定义为

\[\sqrt{\frac{\sum_{i < j} (\hat{d}_{ij} - d_{ij}(Z))^2}{\sum_{i < j} d_{ij}(Z)^2}}.\]

如果 normalized_stress=True，则返回归一化的 Stress-1。

经典型 MDS，也称为主坐标分析（PCoA）或Torgerson's scaling，在单独的 ClassicalMDS 类中实现。经典型 MDS 用不同的损失函数（称为应变）替换应力损失函数，应变具有特征分解的精确解。如果相异性矩阵由某些向量之间的成对欧几里得距离组成，则经典型 MDS 等效于应用于这组向量的 PCA。

形式上，经典型 MDS 的损失函数（应变）由下式给出

\[\frac{\|B - ZZ^T\|_F}{\|B\|_F} =\sqrt{\frac{\sum_{i,j} (b_{ij} - z_i^\top z_j)^2}{\sum_{i,j} b_{ij}^2}},\]

其中 \(Z\) 是 \(n \times d\) 嵌入矩阵，其行是 \(z_i^T\)，\(\|\cdot\|_F\) 表示 Frobenius 范数，\(B\) 是 Gram 矩阵，其元素 \(b_{ij}\) 由 \(B = -\frac{1}{2}C\Delta C\) 给出。这里 \(C\Delta C\) 是平方相异性的双中心矩阵，其中 \(\Delta\) 是平方输入相异性 \(\delta^2_{ij}\) 的矩阵，\(C=I-J/n\) 是中心化矩阵（单位矩阵减去一个所有元素为一的矩阵除以 \(n\)）。这可以通过 \(B\) 的特征分解精确最小化。

References

• “More on Multidimensional Scaling and Unfolding in R: smacof Version 2” Mair P, Groenen P., de Leeuw J. Journal of Statistical Software (2022)

• “Modern Multidimensional Scaling - Theory and Applications” Borg, I.; Groenen P. Springer Series in Statistics (1997)

• “Nonmetric multidimensional scaling: a numerical method” Kruskal, J. Psychometrika, 29 (1964)

• “Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis” Kruskal, J. Psychometrika, 29, (1964)

2.2.9. t 分布随机邻居嵌入（t-distributed Stochastic Neighbor Embedding, t-SNE）

t-SNE (TSNE) 将数据点的亲和度转换为概率。原始空间中的亲和度由高斯联合概率表示，嵌入空间中的亲和度由 Student’s t 分布表示。这使得 t-SNE 对局部结构特别敏感，并且比现有技术具有一些其他优势

• 在单个地图上揭示多个尺度的结构

• 揭示位于多个不同流形或集群中的数据

• 减少点聚集在中心位置的趋势

虽然 Isomap、LLE 及其变体最适合展开单个连续低维流形，但 t-SNE 将专注于数据的局部结构，并倾向于提取聚类的局部样本组，如 S 曲线示例所示。这种根据局部结构对样本进行分组的能力可能有助于可视化分解包含多个流形的数据集，如手写数字数据集中的情况。1

原始空间和嵌入空间中联合概率的 Kullback-Leibler (KL) 散度将通过梯度下降最小化。请注意，KL 散度不是凸的，这意味着使用不同初始化的多次重新启动将导致 KL 散度的局部最小值。因此，尝试不同的种子并选择具有最低 KL 散度的嵌入有时很有用。

使用 t-SNE 的缺点大致是

• t-SNE 计算成本高昂，在百万样本数据集上可能需要数小时，而 PCA 在几秒或几分钟内即可完成

• Barnes-Hut t-SNE 方法仅限于二维或三维嵌入。

• 该算法是随机的，使用不同种子的多次重新启动可能会产生不同的嵌入。然而，选择误差最小的嵌入是完全合理的。

• 全局结构未明确保留。通过使用 PCA 初始化点（使用 init='pca'）可以缓解此问题。

优化 t-SNE

t-SNE 的主要目的是可视化高维数据。因此，当数据嵌入到二维或三维时，它的效果最好。

优化 KL 散度有时会有点棘手。有五个参数控制 t-SNE 的优化，因此可能影响最终嵌入的质量

• 困惑度（perplexity）

• 早期夸大因子（early exaggeration factor）

• 学习率（learning rate）

• 最大迭代次数（maximum number of iterations）

• 角度（angle）（在精确方法中未使用）

困惑度定义为 \(k=2^{(S)}\)，其中 \(S\) 是条件概率分布的 Shannon 熵。一个 \(k\) 面骰子的困惑度是 \(k\)，因此 \(k\) 实际上是 t-SNE 在生成条件概率时考虑的最近邻居数。较高的困惑度会导致更多的最近邻居，对小结构不那么敏感。相反，较低的困惑度会考虑较少的邻居，因此会忽略更多的全局信息而偏爱局部邻域。随着数据集大小的增加，需要更多的点才能获得合理的局部邻域样本，因此可能需要更大的困惑度。同样，噪声较大的数据集将需要更大的困惑度值才能包含足够的局部邻居以超越背景噪声。

最大迭代次数通常足够高，不需要调整。优化包括两个阶段：早期夸大阶段和最终优化阶段。在早期夸大期间，原始空间中的联合概率将被人为地增加，乘以给定的因子。较大的因子会导致数据中自然聚类之间的间隙更大。如果因子太高，KL 散度在此阶段可能会增加。通常不需要调整它。一个关键参数是学习率。如果它太低，梯度下降将陷入一个不好的局部最小值。如果它太高，KL 散度将在优化过程中增加。Belkina 等人 (2019) 提出的一种启发式方法是将学习率设置为样本大小除以早期夸大因子。我们将此启发式方法实现为 learning_rate='auto' 参数。更多提示可以在 Laurens van der Maaten 的 FAQ 中找到（参见参考文献）。最后一个参数 angle 是性能和精度之间的权衡。较大的角度意味着我们可以用单个点近似较大的区域，从而提高速度但降低精度。

“How to Use t-SNE Effectively” 提供了对各种参数影响的良好讨论，以及探索不同参数影响的交互式图表。

Barnes-Hut t-SNE

此处实现的 Barnes-Hut t-SNE 通常比其他流形学习算法慢得多。优化非常困难，梯度的计算复杂度为 \(O[d N log(N)]\)，其中 \(d\) 是输出维度数，\(N\) 是样本数。Barnes-Hut 方法改进了 t-SNE 复杂度为 \(O[d N^2]\) 的精确方法，但还有其他几个显着差异

• Barnes-Hut 实现仅在目标维度为 3 或更小时才有效。在构建可视化时，2D 情况很常见。

• Barnes-Hut 仅适用于密集输入数据。稀疏数据矩阵只能通过精确方法嵌入，或者可以通过密集低秩投影（例如使用 PCA）进行近似

• Barnes-Hut 是精确方法的近似。近似由 angle 参数参数化，因此当 method="exact" 时，angle 参数未使用

• Barnes-Hut 的可扩展性显着提高。Barnes-Hut 可用于嵌入数十万个数据点，而精确方法在计算上变得不可行之前只能处理数千个样本

为了可视化目的（这是 t-SNE 的主要用例），强烈建议使用 Barnes-Hut 方法。精确 t-SNE 方法对于检查嵌入的理论特性可能在更高维空间中很有用，但由于计算限制而仅限于小型数据集。

另请注意，数字标签与 t-SNE 找到的自然分组大致匹配，而 PCA 模型的线性 2D 投影产生的表示中标签区域大部分重叠。这是一个强有力的线索，表明该数据可以通过专注于局部结构的非线性方法（例如，具有高斯 RBF 核的 SVM）很好地分离。然而，在 2D 中未能通过 t-SNE 可视化分离良好的同质标签组并不一定意味着数据不能被有监督模型正确分类。可能是 2 维不足以准确表示数据的内部结构。

References

• “Visualizing High-Dimensional Data Using t-SNE” van der Maaten, L.J.P.; Hinton, G. Journal of Machine Learning Research (2008)

• “t-Distributed Stochastic Neighbor Embedding” van der Maaten, L.J.P.

• “Accelerating t-SNE using Tree-Based Algorithms” van der Maaten, L.J.P.; Journal of Machine Learning Research 15(Oct):3221-3245, 2014.

• “Automated optimized parameters for T-distributed stochastic neighbor embedding improve visualization and analysis of large datasets” Belkina, A.C., Ciccolella, C.O., Anno, R., Halpert, R., Spidlen, J., Snyder-Cappione, J.E., Nature Communications 10, 5415 (2019).

2.2.10. 实用技巧

• 确保所有特征使用相同的比例。因为流形学习方法基于最近邻搜索，否则算法可能表现不佳。请参阅 StandardScaler 以获取缩放异构数据的便捷方法。

• 每个例程计算的重构误差可用于选择最佳输出维度。对于嵌入在 \(D\) 维参数空间中的 \(d\) 维流形，重构误差将随着 n_components 的增加而减小，直到 n_components == d。

• 请注意，嘈杂的数据可能会“短路”流形，实质上充当流形原本会很好分离的部分之间的桥梁。在嘈杂和/或不完整数据上进行流形学习是一个活跃的研究领域。

• 某些输入配置可能导致奇异权重矩阵，例如当数据集中有两个以上的点相同时，或者当数据分成不相交的组时。在这种情况下，solver='arpack' 将无法找到零空间。解决此问题的最简单方法是使用 solver='dense'，它适用于奇异矩阵，尽管根据输入点的数量可能会非常慢。或者，可以尝试理解奇异性的来源：如果它是由不相交集引起的，增加 n_neighbors 可能会有所帮助。如果它是由数据集中的相同点引起的，删除这些点可能会有所帮助。

另请参阅

完全随机树嵌入也可用于导出特征空间的非线性表示，但它不执行降维。