2.2. 流形学习

寻找最基本的需求

简单基本的需求

忘记你的忧虑和你的争斗

我的意思是基本的需求

老祖母自然的食谱

带来生活的基本必需品

– 巴鲁的歌 [丛林之书]

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

2.2.1. 简介

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

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

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

可以将流形学习视为试图概括像 PCA 这样的线性框架，使其对数据中的非线性结构敏感。尽管存在监督变体，但典型的流形学习问题是无监督的：它从数据本身学习数据的 高维结构，无需使用预定的分类。

示例

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

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

• 参见 可视化股票市场结构，了解如何使用流形学习根据历史股价绘制股票市场结构的示例。

scikit-learn 中提供的流形学习实现总结如下

2.2.2. Isomap

Isomap 算法是最早的流形学习方法之一，它是等距映射的缩写。Isomap 可以被视为多维缩放 (MDS) 或核 PCA 的扩展。Isomap 寻找一个保持所有点之间测地线距离的低维嵌入。Isomap 可以使用对象 Isomap 执行。

复杂度

Isomap算法包含三个阶段

1. 最近邻搜索。Isomap使用BallTree进行高效的邻域搜索。其计算成本大约为\(O[D \log(k) N \log(N)]\)，其中\(k\)是\(D\)维空间中\(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\)：输出维度

参考文献

• “用于非线性降维的全局几何框架” 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\)：输出维度

参考文献

• “通过局部线性嵌入进行非线性降维” Roweis, S. & Saul, L. Science 290:2323 (2000)

2.2.4. 改进的局部线性嵌入

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完全相同。第二项与从多个权重构建权重矩阵有关。在实践中，构建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)” 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特征映射：用于高维数据局部线性嵌入技术” 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\)：输出维度

参考文献

• “用于降维和数据表示的拉普拉斯特征映射” 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\)：输出维度

参考文献

• “通过切空间对齐实现主流形和非线性降维” 张志华 & 查红. 上海大学学报. 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}\))。请注意，可以通过简单的变换轻松地从相似性获得相异性，例如，对于某些实数常数 \(c_1, c_2\)，\(\delta_{ij}=c_1-c_2 S_{ij}\)。一个简单的算法来强制执行正确的排序是使用 \(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 问题兼容，在度量情况下将被忽略。

参考文献

• “现代多维尺度分析 - 理论与应用” Borg, I.; Groenen P. Springer 统计系列 (1997)

• “非度量多维尺度分析：一种数值方法” Kruskal, J. 心理测量学, 29 (1964)

• “通过优化对非度量假设的拟合优度来进行多维尺度分析” Kruskal, J. 心理测量学, 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 的优化，因此也可能控制最终嵌入的质量。

• 困惑度 (perplexity)

• 早期放大因子 (early exaggeration factor)

• 学习率 (learning rate)

• 最大迭代次数 (maximum number of iterations)

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

困惑度定义为 \(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(10):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可能会有所帮助。如果它是由数据集中的相同点造成的，删除这些点可能会有所帮助。

另见

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