2.2. 流形学习#

寻找基本必需品
简单的基本必需品
忘掉你的烦恼和纷争
我指的是基本必需品
大自然母亲的食谱
带来生活的基本必需品

– 巴鲁的歌 [奇幻森林]

维度必须在某种程度上进行降维。

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

digits_img projected_img

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

PCA_img LDA_img

流形学习可以被视为一种尝试，旨在将线性框架（如PCA）推广到能够敏感地处理数据中的非线性结构。虽然存在有监督的变体，但典型的流形学习问题是无需监督的：它从数据本身学习数据的高维结构，而不使用预先确定的分类。

示例

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

2.2.1. Isomap#

最早的流形学习方法之一是 Isomap 算法，全称为等距映射（Isometric Mapping）。Isomap 可以看作是多维缩放（MDS）或核主成分分析（Kernel PCA）的扩展。Isomap 寻求一个保持所有点之间测地距离的低维嵌入。Isomap 可以通过 Isomap 对象执行。

../_images/sphx_glr_plot_lle_digits_005.png
#复杂度

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]\) 。用户可以通过 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\) : 输出维度

参考文献

2.2.2. 局部线性嵌入#

局部线性嵌入（LLE）寻求数据的低维投影，该投影保留了局部邻域内的距离。可以将其视为一系列局部主成分分析，这些分析在全球范围内进行比较，以找到最佳的非线性嵌入。

局部线性嵌入可以通过函数 locally_linear_embedding 或其面向对象的对应物 LocallyLinearEmbedding 执行。

../_images/sphx_glr_plot_lle_digits_006.png
#复杂度

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

参考文献

2.2.3. 改进的局部线性嵌入#

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

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

../_images/sphx_glr_plot_lle_digits_007.png
#复杂度

MLLE算法包括三个阶段：

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

  2. 权重矩阵构造。大约为 \(O[D N k^3] + O[N (k-D) k^2]\) 。第一项与标准LLE完全等价。第二项与构造

权重矩阵来自多个权重。 在实践中，构建 MLLE 权重矩阵的额外成本相对于第1和第3阶段成本来说是相对较小的。

  1. 部分特征值分解。与标准 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\) : 输出维度

参考文献

2.2.4. Hessian Eigenmapping#

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

../_images/sphx_glr_plot_lle_digits_008.png
#复杂度

HLLE 算法包括三个阶段：

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

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

局部Hessian估计量的分解。

  1. 部分特征值分解。与标准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\) : 输出维度

参考文献

2.2.5. 谱嵌入#

谱嵌入是一种计算非线性嵌入的方法。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\) : 输出维度

参考文献

2.2.6. 局部切空间对齐#

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

../_images/sphx_glr_plot_lle_digits_009.png
#复杂度

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

参考文献

2.2.7. 多维尺度分析 (MDS)#

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

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

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

../_images/sphx_glr_plot_lle_digits_010.png

设 \(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可能使用归一化应力，称为Stress-1，定义为

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

通过设置 normalized_stress=True 可以启用归一化Stress-1，然而它仅与非度量MDS问题兼容，并且在度量情况下将被忽略。

../_images/sphx_glr_plot_mds_001.png

参考文献

2.2.8. 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' ）可以缓解此问题。

../_images/sphx_glr_plot_lle_digits_013.png
#优化t-SNE

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

优化KL散度有时可能有点棘手。有五个参数控制着t-SNE的优化过程，从而可能影响最终嵌入的质量：

  • 困惑度（perplexity）

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

  • 学习率（learning rate）

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

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

困惑度定义为 \(k=2^{(S)}\) ，其中 \(S\) 是条件概率分布的香农熵。一个 \(k\) 面的骰子的困惑度为 \(k\) ，因此 \(k\) 实际上是t-SNE在生成条件概率时考虑的最近邻数。较大的困惑度会导致更多的最近邻，对小结构不太敏感。相反，较低的困惑度考虑较少的邻居，从而忽略更多的全局信息，更侧重于局部邻域。随着数据集规模的增大，需要更多的点来获取合理的局部邻域样本，因此

较大的困惑度可能是必需的。同样，噪声更大的数据集将需要更大的困惑度值，以包含足够的局部邻居，从而超越背景噪声。

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

“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 是精确方法的近似。近似通过角度参数进行参数化，因此当 method=”exact” 时，角度参数未使用

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

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

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

参考文献

  • `”Visualizing High-Dimensional Data Using t-SNE”

*` “t-分布随机邻域嵌入”

<https://lvdmaaten.github.io/tsne/> `_ van der Maaten, L.J.P.

*` “使用基于树的算法加速t-SNE”

<https://lvdmaaten.github.io/publications/papers/JMLR_2014.pdf> `_ van der Maaten, L.J.P.; Journal of Machine Learning Research 15(Oct):3221-3245, 2014.

*` “为T分布随机邻域嵌入自动优化参数以改善大型数据集的可视化与分析”

<https://www.nature.com/articles/s41467-019-13055-y> `_ Belkina, A.C., Ciccolella, C.O., Anno, R., Halpert, R., Spidlen, J., Snyder-Cappione, J.E., Nature Communications 10, 5415 (2019).

2.2.9. 实用使用技巧#

  • 确保所有特征使用相同的尺度。由于流形学习方法基于最近邻搜索，否则算法可能表现不佳。参见 :ref:` StandardScaler <preprocessing_scaler> ` 以了解缩放异构数据的便捷方法。

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

  • 请注意，噪声数据可以“短路”流形，本质上作为流形原本良好分离部分的桥梁。噪声和/或不完整数据的流形学习是一个活跃的研究领域。

  • 某些输入配置可能导致奇异权重矩阵，例如当数据集中有超过两个点相同，或者数据被分成不连通组时。在这种情况下， solver='arpack' 将无法找到零空间。最简单的解决方法是

使用 solver='dense' 可以在奇异矩阵上工作，尽管这可能会非常慢，具体取决于输入点的数量。 或者，可以尝试理解奇异性的来源：如果它是由不相交的集合引起的，增加 n_neighbors 可能会有所帮助。 如果它是由数据集中相同的点引起的，移除这些点可能会有所帮助。

See also

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

On this page
Show Source