2.2. 流形学习¶

​ Look for the bare necessities

​ The simple bare necessities

​ Forget about your worries and your strife

​ I mean the bare necessities

​ Old Mother Nature’s recipes

​ That bring the bare necessities of life

​ – Baloo’s song [The Jungle Book]

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

2.2.1. 介绍

高维数据集很难可视化。虽然可以绘制二维或三维数据来显示数据的固有结构，但是等价的高维图就不那么直观了。为了改善可视化数据集的结构，必须以某种方式减少维数。

完成这种降维最简单的方法是对数据进行随机投影。虽然这允许在一定程度上可视化数据结构，但是选择随机性的方式还有很多需要改进的地方。在随机投影中，数据中更有趣的结构可能会丢失。

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

流形学习可以被认为是一种把线性框架（如主成分分析）推广到数据中敏感的非线性结构的尝试。虽然有监督变量存在，但典型的流形学习问题是无监督的:它从数据本身学习数据的高维结构，而不使用预先确定的分类。

示例：

• 参见 手写数字上的流形学习：局部线性嵌入，Isomap… ,手写数字降维的示例。
• 参见 流形学习方法的比较 ,有关玩具 “S-曲线” 数据集降维的示例。

scikit-learn中提供的多种学习实现总结如下

2.2.2. Isomap

Isomap算法是最早的流形学习方法之一，它是等距映射的缩写。Isomap可以看作是多维尺度分析(MDS)或核主成分分析的扩展。Isomap寻求一种更低维度的嵌入，以保持所有点之间的测地线距离（geodesic distances）。Isomap可以通过Isomap 对象来执行。

2.2.2.1. 复杂度

Isomap 算法包括三个阶段:

1. **最近邻搜索.**Isomap使用 sklearn.neighbors.BallTree 高效的进行近邻搜索。对于维度中个点的个最近邻，其代价近似为 。
2. 最短路径图搜索. 这方面算法中已知最有效的算法是 Dijkstra 算法或 Floyd-Warshall 算法，复杂度分别是约 和 。 用户可通过使用 isomap 的 path_method 关键字来选择算法。 如果未指定，代码会尝试为输入数据选择最佳算法。
3. **部分特征值分解.**嵌入编码在对应的xisomap核的个最大特征值的特征向量中。对于一个密集求解器，代价大约是。这个代价通常可以通过ARPACK求解器来提高。用户可以使用Isomap的path_method关键字指定特征求解器。如果未指定，代码将尝试为输入数据选择最佳算法。

Isomap的总体复杂度是

• : 训练数据点个数

• : 输入维度

• : 最近邻个数

• : 输出维度

  参考资料:

  “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 来实现。

2.2.3.1. 复杂度

标准的 LLE 算法包括三个阶段:

1. 最邻近搜索. 参见上述 Isomap 讨论。
2. 构造权重矩阵. , LLE 权重矩阵的构造包括每个 局部邻域的线性方程的解。
3. 部分特征值分解. 参见上述 Isomap 讨论。

标准 LLE 的整体复杂度是

: 训练数据点个数

: 输入维度

: 最近邻个数

: 输出维度

参考资料:

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

2.2.4. 改进型局部线性嵌入（MLLE）

局部线性嵌入(LLE)一个众所周知的问题是正则化问题。当邻域数大于输入维数时，定义每个局部邻域的矩阵是不满秩的。为了解决这个问题，标准LLE应用了一个任意的正则化参数 ，它的取值受局部权重矩阵的迹的影响。虽然可以形式化的表示为：当正则化参数 ,解收敛于期望的嵌入,但是当 时不保证找到最优解。这个问题表现在嵌入过程中扭曲了流形的基本几何形状。

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

2.2.4.1. 复杂度

MLLE 算法分为三个阶段:

1. **近邻搜索.**与标准 LLE 的相同。
2. **权重矩阵构造.**大约是 。该式第一项恰好等于标准 LLE 算法的复杂度。第二项与由多个权重来构造权重矩阵相关。在实践中，构造 MLLE 权重矩阵所增加的损耗（就复杂度而言），比其它两部分要小。
3. **部分特征值分解.**与标准 LLE 的相同。

综上，MLLE 的复杂度为 。

• : 训练集数据点的个数
• : 输入维度
• : 最近邻域的个数
• : 输出维度

参考资料:

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

2.2.5. 黑塞特征映射（HE）

黑塞特征映射 (也称作基于黑塞的 LLE: HLLE ）是解决 LLE 正则化问题的另一种方法。在每个用于恢复局部线性结构的邻域内，它会围绕一个基于黑塞的二次型展开。虽然其它的实现表明它对数据大小进行缩放的能力较差，但是 sklearn 实现了一些算法改进，使得在输出低维度时它的损耗可与其他 LLE 变体相媲美。HLLE 通过函数 locally_linear_embedding 或其面向对象的形式 LocallyLinearEmbedding 被执行，附带关键词 method = 'hessian' 。它需满足 n_neighbors > n_components * (n_components + 3) / 2 。

2.2.5.1. 复杂度

HLLE 算法分为三个阶段:

1. **近邻搜索.**与标准 LLE 的相同。
2. **权重矩阵构造.**大约是 。其中第一项与标准LLE相似。第二项来自于局部黑塞估计量的一个 QR 分解。
3. **部分特征值分解.**与标准 LLE 的相同。

综上，HLLE 的复杂度为 。

• : 训练集数据点的个数
• : 输入维度
• : 最近邻域的个数
• : 输出维度

参考资料:

• “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 来执行。

2.2.6.1. 复杂度

谱嵌入（拉普拉斯特征映射）算法包含三部分：

1. **加权图结构.**把原始输入数据转换为用相似（邻接）矩阵表达的图表达。
2. **图拉普拉斯结构.**非规格化的图拉普拉斯是按 构造，并按规格化。
3. **部分特征值分解.**在图拉普拉斯上进行特征值分解。

综上，谱嵌入的复杂度为 。

• : 训练集数据点的个数
• : 输入维度
• : 最近邻域的个数
• : 输出维度

参考资料:

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

2.2.7. 局部切空间对齐（LTSA）

虽然从技术上讲局部切空间对齐(LTSA) 不是LLE的变体，但在算法上与LLE非常相似，因此可以将其归入这一类。与LLE不同的是，LTSA不像LLE那样注重保持邻域距离，而是通过其切空间来描述每个邻域的局部几何形状，并执行全局最优化来对齐这些局部切空间以得到对应的嵌入。 LTSA 可通过函数 locally_linear_embedding 或其面向对象的对应函数 LocallyLinearEmbedding 来执行，附带关键词 method = 'ltsa' 。

2.2.7.1 复杂度

LSTA算法包含三部分：

1. **近邻搜索.**与标准 LLE 的相同。
2. **权重矩阵构造.**大约是 。其中第一项与标准LLE相似。
3. **部分特征值分解.**与标准 LLE 相同。

综上，复杂度为 。

• : 训练集数据点的个数
• : 输入维度
• : 最近邻域的个数
• : 输出维度

参考资料:

• “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）

多维尺度分析 Multidimensional scaling （ MDS ） 寻求数据的低维表示，而且低维数据间的距离保持了它们在原始高维空间中的距离。

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

MDS算法有度量算法和非度量算法两种。在scikit-learn中， MDS 类可以实现这两种算法。在度量MDS中，输入相似度矩阵源于一个度量(因此尊重三角不等式)，后设置输出两点之间的距离尽可能接近相似或不相似的数据。在非度量的情况下，算法会尽量保持对距离的控制，从而在嵌入空间的距离与相似点/不相似点之间寻找单调关系。

设是相似度矩阵，是 个输入点的坐标。差异 是某些最优方式所选择的相似度转换。然后，通过 $\sum_{i

2.2.8.1. 度量 MDS

最简单的度量 MDS 模型称为 absolute MDS（绝对MDS），差异由 定义。对于绝对 MDS，值应精确地对应于嵌入点的点 和 之间的距离。

大多数情况下，差异应设置为 。

2.2.8.2. 非度量 MDS

非度量 MDS 关注数据的排序。如果$S_{i j}

这个问题的 a trivial solution（一个平凡解）是把所有点设置到原点上。为了避免这种情况，将差异正则化。

参考资料:

• “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-curve示例中突出显示的那样。这种基于局部结构对样本进行分组的能力可能有助于从视觉上分离同时包含多个流形的数据集，就像数字数据集中的情况一样。

利用梯度下降的方法，使原始空间和嵌入空间的联合概率的离散度达到最小。注意KL散度不是凸的，也就是说，用不同的初始化方法多次重新启动，最终会得到KL散度的局部极小值。因此，有时尝试不同的种子并选择KL散度最低的KL散度的嵌入是有用的。

使用 t - SNE 的缺点大致如下:

• t-SNE 的计算成本很高，在百万样本数据集上花费数小时，而PCA在几秒钟或几分钟内就可以完成。
• Barnes-Hut t-SNE 方法仅限于二维或三维嵌入。
• 该算法是随机的，不同种子的多次重启可以产生不同的嵌入。然而，以最小的误差选择嵌入是完全合理的。
• 未明确保留全局结构。这个问题可以通过使用PCA初始化点(使用 init=’pca’)来缓解。

2.2.9.1. 优化t-SNE

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

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

• 困惑度
• 早期增长因子
• 学习率
• 最大迭代次数
• 角度（不在精确方法中使用）

困惑度定义为，其中是条件概率分布的香农熵。面色子的复杂度是 ，它实际上是t-SNE在生成条件概率时考虑的最近邻的个数。困惑度越大导致更近，对小结构也越不敏感。相反，较低的困惑度考虑的是较少的邻域，因此忽略了更多的全局信息，而更加关注局部邻域。随着数据集的增大，需要更多的点来获得合理的局部邻域样本，因此可能需要更大的困惑度。同样的，噪声越大的数据集需要越大的困惑度来包含足够多的局部邻居，以便在背景噪声之外查看。

迭代的最大次数通常足够高，不需要任何调优。优化包括两个阶段:早期增长阶段和最终优化阶段。在早期的增长阶段，原始空间中的联合概率将通过与给定的因子相乘而被人为地增加。越大的因子导致数据中自然聚类之间的差距越大。如果因子过高，则KL散度在此阶段可能增大。通常不需要对其进行调整。一个关键的参数是学习率。如果梯度降得太低，就会陷入局部极小值。如果KL散度过高，则在优化过程中KL散度会增大。更多的技巧可以在Laurens van der Maaten的FAQ中找到(见参考资料)。最后一个参数角度，它是性能和精度之间的权衡。角度越大意味着我们可以用单个点来近似更大的区域，从而得到更快的速度，但结果越不准确。

“How to Use t-SNE Effectively” （如何高效使用t-SNE）提供了一个关于各种参数效果的讨论，以及用来探索不同参数效果的交互式绘图。

2.2.9.2. Barnes-Hut t-SNE

这里实现的Barnes-Hut t-SNE通常比其他流形学习算法要慢得多。优化比较困难，梯度的计算为，其中为输出维数，为样本数。t-SNE复杂度是,Barnes-Hut 方法在此基础上进行了改进，但有几个其他显著差异:

• Barnes-Hut 仅在目标维度为3或更小时才有效。构建可视化时，基于2-D的情况就是典型的用于可视化。
• Barnes-Hut 仅对密集的输入数据有效。稀疏数据矩阵只能用精确方法嵌入，或者可以通过密集的低阶投影来近似，例如使用 sklearn.decomposition.TruncatedSVD
• Barnes-Hut 是精确方法的近似。这个近似值是用角度参数来参数化的，因此当参数 method=”exact” 时，angle 参数无效。
• Barnes-Hut 的拓展性很高。Barnes-Hut 可用于嵌入数十万个数据点，而精确方法只能处理数千个样本，再多就会变得难以计算。

出于可视化目的(这是t-SNE的主要用例)，强烈建议使用Barnes-Hut方法。精确的t-SNE方法可以用来检验高维空间中嵌入的理论性质，但由于计算能力的约束而仅限于小数据集。

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

参考资料:

• “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.” L.J.P. van der Maaten. Journal of Machine Learning Research 15(Oct):3221-3245, 2014.

2.2.10. 实用技巧

• 确保对所有特征中使用相同的缩放比例。由于流形学习方法是基于最近邻搜索的，否则算法的性能可能很差。有关缩放异构数据的方便方法，请参阅 StandardScaler 。
• 每个程序计算的重构误差可以用来选择最优的输出维数。对于嵌入在维参数空间中的 维流形，重构误差将随着 n_components 的增加而减小，直到 n_components == d 。
• 注意，有噪声的数据会使流形管“短路”，本质上是在流形管的各个部分之间起到桥梁作用，否则流形管就会被很好地分开。基于噪声和/或不完全数据的流形学习是一个活跃的研究领域。
• 某些输入配置可能导致奇异加权矩阵，例如，当数据集中有两个以上的点是相同的，或者当数据被分割成不关联的组时。在这种情况下， solver='arpack' 将无法找到零空间。解决这一问题的最简单方法是使用 solver='dense' ，它将在一个奇异矩阵上工作，尽管它可能因为输入点的数量而非常慢。或者，可以尝试理解奇点的来源:如果是由于不相交的集合，增加 n_neighbors 可能会有所帮助；如果是由于数据集中的相同的点，则删除这些点可能有所帮助。

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