2.2. 流形学习#
流形学习是一种非线性降维方法。用于此任务的算法基于这样的思想：许多数据集的维度只是人为地高。
2.2.1. 简介#
高维数据集可能非常难以可视化。虽然二维或三维数据可以通过绘图来显示数据的固有结构，但等效的高维绘图则远不如直观。为了帮助可视化数据集的结构，必须以某种方式降低维度。
实现这种降维的最简单方法是对数据进行随机投影。尽管这在一定程度上允许可视化数据结构，但这种选择的随机性仍有许多不足之处。在随机投影中，数据中更具趣味性的结构很可能会丢失。
为了解决这一问题，已经设计了许多监督和无监督的线性降维框架，例如主成分分析（PCA）、独立成分分析、线性判别分析等。这些算法定义了特定的规则来选择数据的“有趣”线性投影。这些方法可能很强大，但通常会忽略数据中重要的非线性结构。
流形学习可以被认为是尝试将PCA等线性框架推广，使其对数据中的非线性结构敏感。尽管存在监督变体，但典型的流形学习问题是无监督的：它从数据本身学习数据的高维结构，而不使用预定的分类。
示例
有关手写数字降维的示例，请参阅手写数字上的流形学习：局部线性嵌入、Isomap...。
有关玩具“S曲线”数据集降维的示例，请参阅流形学习方法比较。
有关使用流形学习根据历史股票价格映射股票市场结构的示例，请参阅可视化股票市场结构。
有关将流形学习技术应用于球形数据集的示例，请参阅截断球体上的流形学习方法。
有关在瑞士卷数据集上使用流形学习技术的示例，请参阅瑞士卷和瑞士孔降维。
scikit-learn 中可用的流形学习实现总结如下
2.2.2. Isomap#
流形学习最早的方法之一是 Isomap 算法，即等距映射（Isometric Mapping）的缩写。Isomap 可以被视为多维尺度变换（MDS）或核PCA的扩展。Isomap 旨在找到一个低维嵌入，该嵌入能保持所有点之间的测地距离。Isomap 可以通过对象 Isomap 进行。
复杂度#
Isomap 算法包括三个阶段
最近邻搜索。Isomap 使用
BallTree进行高效的邻居搜索。对于 \(D\) 维空间中 \(N\) 个点的 \(k\) 个最近邻，其成本约为 \(O[D \log(k) N \log(N)]\)。最短路径图搜索。目前已知最有效的算法是 Dijkstra 算法（大约为 \(O[N^2(k + \log(N))]\)）或 Floyd-Warshall 算法（\(O[N^3]\)）。用户可以通过
Isomap的path_method关键字选择算法。如果未指定，代码会尝试为输入数据选择最佳算法。部分特征值分解。嵌入被编码在对应于 \(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\) : 输出维度
参考文献
“非线性降维的全局几何框架” Tenenbaum, J.B.; De Silva, V.; & Langford, J.C. Science 290 (5500)
2.2.3. 局部线性嵌入#
局部线性嵌入（LLE）旨在寻找数据的低维投影，该投影能保留局部邻域内的距离。它可被视为一系列局部主成分分析，这些分析经过全局比较以找到最佳非线性嵌入。
局部线性嵌入可以通过函数 locally_linear_embedding 或其面向对象的对应类 LocallyLinearEmbedding 来执行。
复杂度#
标准 LLE 算法包括三个阶段
最近邻搜索。参见上面 Isomap 部分的讨论。
权重矩阵构建。\(O[D N k^3]\)。LLE 权重矩阵的构建涉及为 \(N\) 个局部邻域中的每一个求解一个 \(k \times k\) 线性方程。
部分特征值分解。参见上面 Isomap 部分的讨论。
标准 LLE 的整体复杂度为 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[d N^2]\)。
\(N\) : 训练数据点数
\(D\) : 输入维度
\(k\) : 最近邻数量
\(d\) : 输出维度
参考文献
“通过局部线性嵌入进行非线性降维” 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 算法包括三个阶段
最近邻搜索。与标准 LLE 相同
权重矩阵构建。大约为 \(O[D N k^3] + O[N (k-D) k^2]\)。第一项与标准 LLE 的成本完全相同。第二项与从多个权重构建权重矩阵有关。实际上，与阶段 1 和 3 的成本相比，构建 MLLE 权重矩阵的额外成本相对较小。
部分特征值分解。与标准 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: 使用多个权重的修正局部线性嵌入” Zhang, Z. & Wang, J.
2.2.5. 海森特征映射#
海森特征映射（也称为基于海森的 LLE：HLLE）是解决 LLE 正则化问题的另一种方法。它围绕每个邻域的海森二次型展开，该二次型用于恢复局部线性结构。尽管其他实现注意到其在数据大小方面的扩展性不佳，但 sklearn 实施了一些算法改进，使其成本对于小输出维度而言与其他 LLE 变体相当。HLLE 可以通过函数 locally_linear_embedding 或其面向对象的对应类 LocallyLinearEmbedding 来执行，使用关键字 method = 'hessian'。它要求 n_neighbors > n_components * (n_components + 3) / 2。
复杂度#
HLLE 算法包括三个阶段
最近邻搜索。与标准 LLE 相同
权重矩阵构建。大约为 \(O[D N k^3] + O[N d^6]\)。第一项反映了与标准 LLE 相似的成本。第二项来自局部海森估计器的 QR 分解。
部分特征值分解。与标准 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\) : 输出维度
参考文献
“海森特征映射：用于高维数据的局部线性嵌入技术” Donoho, D. & Grimes, C. Proc Natl Acad Sci USA. 100:5591 (2003)
2.2.6. 谱嵌入#
谱嵌入是一种计算非线性嵌入的方法。Scikit-learn 实现了拉普拉斯特征映射，该方法使用图拉普拉斯算子的谱分解来找到数据的低维表示。生成的图可以被视为高维空间中低维流形的离散近似。基于图的成本函数最小化可确保流形上彼此接近的点在低维空间中也被映射为彼此接近，从而保留局部距离。谱嵌入可以通过函数 spectral_embedding 或其面向对象的对应类 SpectralEmbedding 来执行。
复杂度#
谱嵌入（拉普拉斯特征映射）算法包括三个阶段
加权图构建。使用亲和（邻接）矩阵表示将原始输入数据转换为图表示。
图拉普拉斯算子构建。未归一化的图拉普拉斯算子构造为 \(L = D - A\)，归一化的则构造为 \(L = D^{-\frac{1}{2}} (D - A) D^{-\frac{1}{2}}\)。
部分特征值分解。在图拉普拉斯算子上进行特征值分解。
谱嵌入的整体复杂度为 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[d N^2]\)。
\(N\) : 训练数据点数
\(D\) : 输入维度
\(k\) : 最近邻数量
\(d\) : 输出维度
参考文献
“用于降维和数据表示的拉普拉斯特征映射” M. Belkin, P. Niyogi, Neural Computation, 2003 年 6 月; 15 (6):1373-1396
2.2.7. 局部切空间对齐#
尽管局部切空间对齐（LTSA）在技术上并非 LLE 的变体，但其算法与 LLE 足够相似，可归入此类。LTSA 不像 LLE 那样侧重于保留邻域距离，而是通过其切空间表征每个邻域的局部几何结构，并执行全局优化以对齐这些局部切空间来学习嵌入。LTSA 可以通过函数 locally_linear_embedding 或其面向对象的对应类 LocallyLinearEmbedding 来执行，使用关键字 method = 'ltsa'。
复杂度#
LTSA 算法包括三个阶段
最近邻搜索。与标准 LLE 相同
权重矩阵构建。大约为 \(O[D N k^3] + O[k^2 d]\)。第一项反映了与标准 LLE 相似的成本。
部分特征值分解。与标准 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\) : 输出维度
参考文献
“通过切空间对齐的主流形和非线性降维” Zhang, Z. & Zha, H. Journal of Shanghai Univ. 8:406 (2004)
2.2.8. 多维尺度变换 (MDS)#
多维尺度变换（MDS）旨在寻找数据的低维表示，其中距离能够很好地反映原始高维空间中的距离。
通常，MDS 是一种用于分析相异度数据的技术。它试图将相异度建模为欧几里得空间中的距离。数据可以是物体之间的相异度评级、分子相互作用频率或国家之间的贸易指数。
MDS 算法有两种类型：度量型和非度量型。在 scikit-learn 中，类 MDS 同时实现了这两种。在度量 MDS 中，嵌入空间中的距离被设置为尽可能接近相异度数据。在非度量版本中，算法将尝试保留距离的顺序，从而寻求嵌入空间中的距离与输入相异度之间的单调关系。
令 \(\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 关注数据的排序。如果 \(\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 返回归一化应力，也称为应力-1，定义为
如果 normalized_stress=True，则返回归一化应力-1。
参考文献
“R 中多维尺度变换和展开的更多内容：smacof 版本 2” Mair P, Groenen P., de Leeuw J. Journal of Statistical Software (2022)
“现代多维尺度变换 - 理论与应用” Borg, I.; Groenen P. Springer Series in Statistics (1997)
“非度量多维尺度变换：一种数值方法” Kruskal, J. Psychometrika, 29 (1964)
“通过优化对非度量假设的拟合优度进行多维尺度变换” 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 的 FAQ 中找到（参见参考文献）。最后一个参数，角度，是性能和准确性之间的权衡。更大的角度意味着我们可以用一个点近似更大的区域，从而提高速度但降低准确性。
“如何有效使用 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 或更少时有效。在构建可视化时，2D 情况是典型的。
Barnes-Hut 仅适用于密集输入数据。稀疏数据矩阵只能通过精确方法嵌入，或者可以通过例如使用
PCA的密集低秩投影进行近似。Barnes-Hut 是精确方法的一种近似。该近似通过角度参数进行参数化，因此当 method=”exact” 时，角度参数不被使用。
Barnes-Hut 的可扩展性显著更强。Barnes-Hut 可用于嵌入数十万个数据点，而精确方法在计算上变得不可行之前只能处理数千个样本。
为了可视化目的（这是 t-SNE 的主要用例），强烈建议使用 Barnes-Hut 方法。精确 t-SNE 方法对于检查嵌入在更高维空间中的理论特性很有用，但由于计算限制，仅限于小型数据集。
另请注意，数字标签大致与 t-SNE 发现的自然分组相匹配，而 PCA 模型的线性 2D 投影产生的表示中标签区域大部分重叠。这强烈暗示该数据可以通过侧重于局部结构的非线性方法（例如，带有高斯 RBF 核的 SVM）很好地分离。然而，在 2D 中未能用 t-SNE 可视化出良好分离的同质标签组，并不一定意味着数据不能被监督模型正确分类。可能的情况是 2 维不足以准确表示数据的内部结构。
参考文献
“使用 t-SNE 可视化高维数据” van der Maaten, L.J.P.; Hinton, G. Journal of Machine Learning Research (2008)
“t-分布随机邻域嵌入” van der Maaten, L.J.P.
“使用基于树的算法加速 t-SNE” van der Maaten, L.J.P.; Journal of Machine Learning Research 15(Oct):3221-3245, 2014。
“T-分布随机邻域嵌入的自动化优化参数改善了大型数据集的可视化和分析” 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可能会有所帮助。如果它是由数据集中相同的点引起的，删除这些点可能会有所帮助。
另请参阅
全随机树嵌入 也可以用于导出特征空间的非线性表示，但它不执行降维。