2.2. 流形学习(Manifold learning)

（下面好像是歌曲，译者随便翻译的。请见谅。）

寻找最基本的必需品

简单的必需品

忘掉你的烦恼和纷争

我的意思是基本必需品

大自然母亲的食谱

带来了生活必需品

– Baloo’s song [The Jungle Book]

流形学习是非线性降维的一种方法。此算法基于许多数据集的维数只是被人为地设置高了的思想。

2.2.1. 简介

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

实现这种降维的最简单方法就是对数据进行随机投影。尽管这样做可以使数据结构具有某种程度的可视化效果，但随机投影仍有许多不足之处。在随机投影中，数据内部存在的更有趣的结构很有可能会丢失。

为了解决此问题，已经设计了许多有监督和无监督的线性降维算法，例如主成分分析（PCA），独立成分分析，线性判别分析等。这些算法定义了特定的原则，选择数据的“令人感兴趣”的部分进行线性投影。这些方法功能强大，但通常会丢失数据中重要的非线性结构。

流形学习被认为是一种对诸如PCA之类的线性算法进行泛化，以使其对数据中的非线性结构比较敏感。尽管存在有监督算法版本的变体，但典型的流形学习问题是无监督的：它无需使用预定分类的类别就可以从数据本身学习高维结构。

案例：

在手写数字识别数据集上降维的案例，详情请参见手写数字识别数据集上的流形学习：局部线性嵌入，Isomap…。
玩具(toy)“S型曲线”数据集降维的案例，详情请参见流形学习方法的比较。

scikit-learn中实现的流形学习的方法总结如下

2.2.2. 等距映射(Isomap)

等距映射(Isomap)算法是流形学习的最早方法之一，等距映射(Isomap)算法是Isometric Mapping（等距映射）的缩写。等距映射可以看作是多维缩放（MDS）或PCA内核的扩展。等距映射寻找低维嵌入的空间，以保持所有点之间的距离。Isomap对象可以执行等距映射方法。

2.2.2.1. 复杂度

等距映射(Isomap)算法包括三个阶段： 1. 最近邻搜索。 等距映射(Isomap)使用sklearn.neighbors.BallTree进行有效地邻居搜索。该步骤的复杂度大约是$O[D \log(k) N \log(N)]$，对于$k$个点的$N$个$D$维的最近邻居。 2. 最短路径图搜索。 已知的最有效算法是迪杰斯特拉(Dijkstra)算法，复杂度大约为$O[N^2(k + \log(N))]$或弗洛伊德算法(Floyd-Warshall)算法，复杂度是$O[N^3]$。用户可以使用Isomap的path_method关键字来选择该算法。如果未指定，则代码将尝试为输入数据选择最佳算法。 3. 部分特征值分解。 嵌入(embedding)被编码在对应于前$d$个最大特征值的$N×N$的等距映射内核上。对于密集求解器(dense solver)，复杂度约为$O[dN^2]$。通常可以使用ARPACK求解器(solver)来降低时间复杂度。用户可以使用Isomap的path_method关键字来指定特征求解器(eigensolver)。如果未指定，则代码将尝试为输入数据选择最佳算法。

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. 局部线性嵌入

局部线性嵌入(Locally linear embedding)（LLE）寻找一个数据的低维投影，以保留局部邻域内的距离。可以将其视为局部的主成分分析。具体而言，将主成分分析进行全局比较以找到最佳的非线性嵌入。

局部线性嵌入可以通过locally_linear_embedding函数或对象 LocallyLinearEmbedding的对应函数来实现。

2.2.3.1. 复杂度

标准的LEE算法包括三个阶段：

最近邻搜索。请参阅上方等距映射(Isomap)的对应部分的讨论。
权重矩阵的构建。$O[D N k^3]$。LLE权重矩阵的构建涉及对$N$个最近邻点，分别解$k×k$的线性方程。
部分特征值分解。请参阅上方等距映射(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.改进型局部线性嵌入(MLLE)

LLE的一个众所周知的问题是正则化问题。当邻居数大于输入维数时，定义每个本地邻居的矩阵会秩亏(rank-deficient)。为了解决这个问题，标准LLE应用了任意正则化参数$r$，$r$的选择与局部权重矩阵的迹是相关的。虽然当$r→0$时解可以收敛到所想要的嵌入（维度），这件事可以被正式证明，但是当$r>0$时，无法保证找到最佳解。该问题以基本几何流形的变形嵌入形式表现出来。

解决正则化问题的一种方法是在每个邻域中使用多个权重向量。这是改进型局部线性嵌入（MLLE）的本质。MLLE可以通过locally_linear_embedding方法或对象 LocallyLinearEmbedding的对应方法（传入关键字method = 'modified'）实现。它要求n_neighbors > n_components。

2.2.4.1. 复杂度

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: Modified Locally Linear Embedding Using Multiple Weights” Zhang, Z. & Wang, J.

2.2.5. Hessian特征映射(HLLE)

Hessian特征映射（也称为基于Hessian的LLE：HLLE）是解决LLE正则化问题的另一种方法。它围绕每个邻域基于hessian的二次形式进行旋转，用于恢复局部线性结构。尽管其他实现注意到Hessian特征映射在数据大小方面的缩放性较差，但是sklearn在算法上实现了一些改进，使其在较小输出维度上的时间代价可与的其他LLE变体相提并论。HLLE可以通过locally_linear_embedding函数或对象 LocallyLinearEmbedding的对应函数（传递关键字method = 'hessian'）实现。它要求n_neighbors > n_components * (n_components + 3) / 2。

2.2.5.1. 复杂度

HLLE算法包括三个阶段：

最近邻居搜索。与标准的LLE相同
权重矩阵的构建。复杂度大约$O[D N k^3] + O[N d^6]$。第一项反映了与标准的LLE相似的复杂度代价。第二项来自hessian估计器(estimator)的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$：输出维度

参考文献：

“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. 频谱嵌入(Spectral Embedding)

频谱嵌入是一种用于计算非线性嵌入的方法。Scikit-learn实现了拉普拉斯特征图，该特征图使用图拉普拉斯的频谱分解来发现数据的低维表示。可以将生成的图视为高维空间中的低维流形的离散近似。基于最小化该图的代价函数可确保在流形上彼此靠近的点在低维空间中也是彼此靠近地映射，从而保留局部距离。可以使用spectral_embedding函数或它的面向对象SpectralEmbedding 来实现频谱嵌入。

2.2.6.1. 复杂度

频谱嵌入（拉普拉斯特征图）算法包括三个阶段：

加权图构造。使用相似（邻接）矩阵将原始输入数据转换为图的形式。
图拉普拉斯构造。把非规范图拉普拉斯构造为$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$：输出维度

参考文献：

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

2.2.7. 局部切空间对齐(Local Tangent Space Alignment)（LTSA）

尽管从技术上讲，局部切空间对齐不是LLE的变体，但局部切空间对齐（LTSA）在算法上与LLE是很相似，因此可以将LTSA归入到LLE类中。LTSA并没有像LLE中那样专注于保留邻域距离，而是寻求通过其切空间来表征每个邻域的局部几何形状，并对其这些局部切空间实现全局最优化，从而得知对应的嵌入。LTSA可以通过locally_linear_embedding函数或它的面向对象 LocallyLinearEmbedding的对应函数（传递关键字method = 'ltsa'）来实现。

2.2.7.1. 复杂度

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$：输出维度

参考文献：

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

2.2.8. 多维缩放(Multi-dimensional Scaling)（MDS）

多维缩放（MDS）寻找数据的低维表示，这些低维数据间的距离保持了它们在初始高维空间中的距离。

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

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

$S$是相似度矩阵，并且$X$是n个输入点的坐标。差异$\hat{d}{ij}$_是以某些最佳方式所选择的相似度转换。然后通过$ \sum{i < j}d_{ij}(X)-\hat{d}_{ij}(X)$方式定义压力(stress)的对象。

2.2.8.1. 度量 MDS

最简单的度量MDS模型称为绝对MDS(absolute MDS)，差异由$\hat{d}{ij} = S{ij}$所组成。使用绝对MDS，$S_{ij}$的值应精确对应于嵌入点$i$和$j$点之间的距离。

最常见的是，差异设置为$\hat{d}{ij} = b S{ij}$。

2.2.8.2. 非度量MDS

非度量MDS侧重于数据的排序。如果$S_{ij} < S_{jk}$，则嵌入应强制执行$d_{ij} < d_{jk}$。一种简单的实现算法是在$S_{ij}$上使用$d_{ij}$的单调回归，以产生与$S_{ij}$相同的顺序差异$\hat{d}_{ij}$。

该问题的一个简单的解是将所有点设置在原点上。为了避免这种情况，需要标准化差异$\hat{d}_{ij}$。

参考文献：

“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）将数据点的相似度转换为概率。原始空间中的相似度由高斯联合概率表示，而嵌入式空间中的相似度由学生(Student)的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'）可以缓解此问题。

2.2.9.1. 优化T-SNE

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

有时，优化KL发散可能会有些棘手。有五个参数控制着t-SNE的优化，因此可能会控制最终嵌入的质量：

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

困惑度被定义为$k=2^{(S)}$，其中$S$是条件概率分布的香农熵。$k$面色子的困惑度是$k$，因此$k$实际上是在生成条件概率时，t-SNE考虑的最近邻域的个数。更大的困惑度将导致越多的近邻域，并且对小型结构不那么敏感。相反，较低的困惑度考虑的领域数量较少，因此忽略了更多有利于本地领域的全局信息。随着数据集大小的增加，将需要更多的点来获取本地邻域的合理样本，因此可能需要更大的困惑度。同样，噪声较大的数据集将需要更大的困惑度值，以保证包含足够的本地领域来查看超出背景噪声的范围。

通常，只要最大迭代次数设置得足够高，则不需要有任何调整。优化包括两个阶段：早期增长阶段和最终优化阶段。在早期增长阶段，原始空间中的联合概率将通过与给定因子相乘而人为增加。较大的因子会导致数据中自然聚类之间的差距更大。如果因子太大，则在此阶段KL散度可能会增加。通常不必调整它。关键参数是学习率。如果它太小，则梯度下降将会陷入局部极小值。如果它过大，则在优化过程中KL散度会增加。可以在Laurens van der Maaten的FAQ中找到更多技巧（请参阅参考资料）。最后一个参数角度，是性能和精度之间的权衡。

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

2.2.9.2. Barnes-Hut t-SNE

在sklearn中实现的Barnes-Hut t-SNE通常比其他流形学习算法要慢得多。优化是非常困难的，并且梯度的计算是$O[d N log(N)]$，其中$d$是输出维度，$N$是样本数。Barnes-Hut方法改进了t-SNE复杂度为$O[dN2]$，但还有其他几个明显的区别：

Barnes-Hut实现仅在输出维度为3或更小时有效。2D案例是构建可视化时的典型案例。
Barnes-Hut仅适用于密集的输入数据。稀疏数据矩阵只能使用精确的方法嵌入，或者可以通过密集的低秩投影来近似，例如使用sklearn.decomposition.TruncatedSVD
Barnes-Hut是精确方法的近似值。这种近似方法使用角度(angle)作为参数，因此，当参数“method = exact”时，角度(angle)参数无效
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” 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。
每个例程计算出的重建误差可用于选择最佳输出维度。为一个$d$嵌入的三维流形$D$维参数空间，重构误差将随着n_components增大而减小，直到n_components == d。
请注意，噪声数据可能会使流形“短路”，本质上是充当流形各部分之间的桥梁，否则它们将被很好地分离。基于噪声和/或不完全数据的流形学习是一个活跃的研究领域。
某些输入配置会导致奇异的权重矩阵，例如，当数据集中的两个以上点相同时，或者将数据拆分为不相交的组时。在这种情况下，solver='arpack' 将找不到零空间(null space)。解决此问题的最简单方法是使用solver='dense'将在单个矩阵上运行，尽管它可能会很慢，具体取决于输入点的数量。或者，可以尝试了解奇异性的来源：如果是由于不相交集的话，则增加n_neighbors可能会有所帮助。如果是由于数据集中存在相同点的话，则删除这些点可能会有所帮助。

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