2.2. 流形学习

寻找最基本的需求

最简单的基本需求

忘记你的烦恼和你的斗争

我的意思是基本需求

老祖母自然的食谱

带来生活的基本需求

– 巴鲁的歌 [丛林奇遇记]

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

2.2.1. 简介

高维数据集可能非常难以可视化。虽然二维或三维数据可以绘制以显示数据的内在结构，但等效的高维图直观性要差得多。为了帮助可视化数据集的结构，必须以某种方式降低维数。

实现此降维的最简单方法是对数据进行随机投影。虽然这允许在一定程度上可视化数据结构，但选择的随机性却令人不满意。在随机投影中，数据中更有趣的结构很可能会丢失。

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

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

示例

• 参见 手写数字上的流形学习：局部线性嵌入、等距映射…，了解对 手写数字进行降维的示例。

• 参见 流形学习方法的比较，了解对玩具“S 形曲线”数据集进行降维的示例。

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

2.2.2. 等距映射

等距映射算法 (Isomap) 是最早的流形学习方法之一，它是等距映射的简称。Isomap 可以看作是多维尺度分析 (MDS) 或核主成分分析 (Kernel PCA) 的扩展。Isomap 寻求一个低维嵌入，该嵌入保持所有点之间的测地距离。Isomap 可以使用对象 Isomap 执行。

复杂度

Isomap 算法包含三个阶段

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

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

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

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

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

• \(D\) : 输入维度

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

• \(d\) : 输出维度

参考文献

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

2.2.3. 局部线性嵌入

局部线性嵌入 (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\) : 输出维度

参考文献

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

2.2.4. 改进的局部线性嵌入

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

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

复杂度

MLLE 算法包含三个阶段

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

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

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\) : 输出维度

参考文献

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

2.2.5. Hessian 特征映射

Hessian 特征映射（也称为基于 Hessian 的 LLE：HLLE）是解决 LLE 正则化问题的另一种方法。它围绕每个邻域的基于 Hessian 的二次形式展开，该形式用于恢复局部线性结构。虽然其他实现指出它在数据大小方面的扩展性较差，但 sklearn 实现了一些算法改进，使其成本与其他 LLE 变体在小输出维度方面相当。HLLE 可以使用函数 locally_linear_embedding 或其面向对象的对应物 LocallyLinearEmbedding 执行，使用关键字 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\) : 输出维度

参考文献

• “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. 谱嵌入

谱嵌入是一种计算非线性嵌入的方法。Scikit-learn 实现拉普拉斯特征映射，该映射使用图拉普拉斯的谱分解来找到数据的低维表示。生成的图可以被认为是高维空间中低维流形的离散近似。基于图的成本函数的最小化确保流形上彼此靠近的点在低维空间中彼此靠近映射，从而保留局部距离。谱嵌入可以使用函数 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\) : 输出维度

参考文献

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

2.2.7. 局部切空间对齐

虽然从技术上讲不是 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\) : 输出维度

参考文献

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

2.2.8. 多维尺度 (MDS)

多维尺度 (MDS) 寻找数据的低维表示，其中距离很好地反映了原始高维空间中的距离。

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

存在两种类型的 MDS 算法：度量和非度量。在 scikit-learn 中，类 MDS 实现了这两种算法。在度量 MDS 中，输入相似性矩阵来自度量（因此满足三角不等式），然后将输出两个点之间的距离设置为尽可能接近相似性或差异性数据。在非度量版本中，算法将尝试保留距离的顺序，因此寻求嵌入空间中的距离与相似性/差异性之间的单调关系。

令 \(S\) 为相似性矩阵，\(X\) 为 \(n\) 个输入点的坐标。差异 \(\hat{d}_{ij}\) 是以某种最佳方式选择的相似性的变换。然后，目标（称为压力）由 \(\sum_{i < j} d_{ij}(X) - \hat{d}_{ij}(X)\) 定义。

度量 MDS

最简单的度量 MDS 模型，称为绝对 MDS，差异由 \(\hat{d}_{ij} = S_{ij}\) 定义。使用绝对 MDS，值 \(S_{ij}\) 应该与嵌入点中点 \(i\) 和 \(j\) 之间的距离完全一致。

最常见的是，差异设置为 \(\hat{d}_{ij} = b S_{ij}\)。

非度量 MDS

非度量 MDS 专注于数据的排序。如果 \(S_{ij} > S_{jk}\)，则嵌入应该强制执行 \(d_{ij} < d_{jk}\)。出于这个原因，我们用差异性 (\(\delta_{ij}\)) 而不是相似性 (\(S_{ij}\)) 来讨论它。请注意，差异性可以通过简单的变换轻松地从相似性中获得，例如 \(\delta_{ij}=c_1-c_2 S_{ij}\)，其中 \(c_1, c_2\) 为一些实常数。一个简单的算法来强制执行正确的排序是使用 \(d_{ij}\) 对 \(\delta_{ij}\) 的单调回归，从而产生与 \(\delta_{ij}\) 顺序相同的差异 \(\hat{d}_{ij}\)。

这个问题的一个平凡解是将所有点都放在原点上。为了避免这种情况，差异 \(\hat{d}_{ij}\) 被归一化。请注意，由于我们只关心相对排序，因此我们的目标应该对简单的平移和缩放保持不变，但是度量 MDS 中使用的压力对缩放很敏感。为了解决这个问题，非度量 MDS 可能会使用归一化的压力，称为压力-1，定义为

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

通过设置 normalized_stress=True 可以启用归一化压力-1 的使用，但是它只与非度量 MDS 问题兼容，并且在度量情况下将被忽略。

参考文献

• “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-SNE)

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

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

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

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

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

原始空间和嵌入空间中联合概率的 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 的优化，因此可能控制最终嵌入的质量：

• 困惑度

• 早期夸大因子

• 学习率

• 最大迭代次数

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

困惑度定义为 \(k=2^{(S)}\)，其中 \(S\) 是条件概率分布的香农熵。一个 \(k\) 面骰子的困惑度为 \(k\)，因此 \(k\) 有效地是 t-SNE 在生成条件概率时考虑的最近邻的数量。更大的困惑度会导致更多的最近邻，并且对小结构不太敏感。相反，较低的困惑度会考虑较少的邻居，因此会忽略更多全局信息，而有利于局部邻域。随着数据集大小的增加，将需要更多点才能获得局部邻域的合理样本，因此可能需要更大的困惑度。类似地，噪声更大的数据集将需要更大的困惑度值来包含足够的局部邻居，以便看到背景噪声之外的内容。

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

“如何有效地使用 t-SNE” 对各种参数的影响进行了很好的讨论，并提供了交互式绘图来探索不同参数的影响。

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 或更小时才有效。当构建可视化时，二维情况是典型的。

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

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

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

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

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

参考文献

• “使用 t-SNE 可视化高维数据” van der Maaten, L.J.P.; Hinton, G. 机器学习研究杂志 (2008)

• “t 分布随机邻域嵌入” van der Maaten, L.J.P.

• “使用基于树的算法加速 t-SNE” van der Maaten, L.J.P.; 机器学习研究杂志 15(Oct):3221-3245, 2014.

• “用于 T 分布随机邻域嵌入的自动优化参数改善了大型数据集的可视化和分析” Belkina, A.C., Ciccolella, C.O., Anno, R., Halpert, R., Spidlen, J., Snyder-Cappione, J.E., 自然通讯 10, 5415 (2019).

2.2.10. 实际使用技巧

• 确保所有特征都使用相同的比例。因为流形学习方法基于最近邻搜索，否则算法可能会执行不佳。见 StandardScaler 以便于缩放异构数据。

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

• 请注意，噪声数据会“短路”流形，本质上充当了流形中原本应该分离良好的部分之间的桥梁。在噪声和/或不完整数据上进行流形学习是一个活跃的研究领域。

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

另请参阅

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