Abstract：

统一流形逼近与投影(UMAP:Uniform Manifold Approximation and Projection)是一种新的降维技术，其理论基础是黎曼几何和代数拓扑。相对于T-SNE降维，UMAP的优点在于:(1)能够尽可能多的保留全局结构，（2）耗时更短(见表一)，（3）对嵌入维数没有限制可以扩展到更大的维度的数据集（T-SNE对数据的维度有所限制（Hinton的T-SNE实验中先用PCA降到50,再进一步的使用T-SNE）、密集的数据才能达到较好的可视化效果）。（T-SNE是建立在二维的基础上，而UMAP则是建立在三维的黎曼流行上，相关定义、计算方法都会发生一定的变化）。

1. Introduction

    降维可以定义为将高维数据降低为低维同时尽可能保证数据的全局性，降维技术是机器学习中大数据预处理的一种重要技术。降维的算法主要分为两类：（1）在数据中保持距离结构的算法——线性降维（PCA、MDS和Sammon映射），（2）在全局距离上保持局部距离的算法（流形学习）——非线性降维（t-SNE、Isomap、LargeVis、Laplacian特征映射和difusion映射）。

    UMAP的数学基础主要是Belkin和Niyogi在拉普拉斯特征映射所做的工作，对于流形数据的分布问题，采用的是黎曼几何和David Spivak在范畴论（category theoretic）方法中的工作。UMAP目前已经应用于生物信息学、材料科学和机器学习等领域得到广泛应用。这篇文章的基本框架如图一：

图一

2 .Teoretical Foundations for UMAP

    UMAP的理论基础主要基于流形理论和拓扑数据分析。许多理论最容易用拓扑学和范畴理论来解释。UMAP利用局部流形逼近（ local manifold approximations）和局部模糊单纯形集表示（local fuzzy simplicial set representations）来构造高维数据的拓扑表示。给定数据的一些低维表示，可以使用类似的过程来构造等价的低维拓扑表示——高维和低维换种表达方式。然后UMAP优化低维空间中数据表示的布局，以最小化两个拓扑表示之间的交叉熵(（交叉熵（Cross Entropy）是Shannon信息论中一个重要概念，主要用于度量两个概率分布间的差异性信息。交叉熵的意义是用该模型对文本识别的难度，或者从压缩的角度来看，每个词平均要用几个位来编码）交叉熵CSDN链接：交叉熵（Cross-Entropy）_Python_rtygbwwwerr的专栏-CSDN博客,。

相对熵与交叉熵的比较

    模糊拓扑表示的构造可分为两个问题：一个是假设数据所在的流形的逼近问题；另一个是流形逼近的模糊单纯形集表示问题。通过以下三节2.1、2.2、2.3对算法进行详细介绍。

2.1 Uniform distribution of data on a manifold and geodesic approximation（流形上数据的均匀分布和测地线近似）

frst step:逼近我们假设的数据所在的流形(从数据中推断出来，事先不知道)。输入数据X = {X1, . . . , XN}，Belkin和Niyogi在Laplacian特征映射上的工作：假设流形有一个不是从环境空间继承来的黎曼度量，我们可以定义一个度量那么数据在流形上均匀分布。M是我们假设数据所在的流形，设g是M的黎曼度量，对于每个点p∈M，我们有，它是切线空间(tangent space)M上的内积。

（切空间（Tangent space）是在某一点所有的切向量组成的线性空间。向量（切向量）存在多种定义。直观的讲，如果所研究的流形（Manifold）是一个三维空间中的曲面，则在每一点的切向量，就是和该曲面相切的向量，切空间就是和该曲面相切的平面。）

Lemma 1：设（M，g）是一个环境中的黎曼流形，数据点p∈M（数据流）,g是关于开邻域U的局部常数，使得g在环境坐标系中是一个常数对角矩阵，那么在以p为中心的球B⊆U中，相对于g的体积πn/2Γ（n/2+1），p到任意点q∈B的测地线距离( geodesic distance：在三维空间中，两点之间的最短路径)是p到任意点q∈B的测地线距离为dRn（p，q），其中r是球在环境空间中的半径，dRn是环境空间上的现有度量（证明略）。

    通过引理1，可以对的近邻的距离进行正规化来近似于xi与其近邻的测地线距离。通过为每个创建一个自定义距离，我们可以确保在流形假设下均匀分布假设的有效性。而这些距离概念可能不兼容。我们有一个离散度量空间家族（每个度量空间对应一个度量空间），我们希望将其合并为一致的全局结构。这可以通过将度量空间(metricspaces)转换为模糊单纯形集（fuzzy simplicial sets）以自然的方式完成。

2.2 Fuzzy topological representation

    我们将数据转换为模糊拓扑表示，以合并数据的不相容局部视图，方法的主要理论依据来自于迈克尔·巴尔（Michael Barr）和大卫·斯皮瓦克（David Spivak）的工作。我们将转换为模糊拓扑表示，以合并数据的不相容局部视图。首先，我们将回顾简单集（simplicial sets）的定义。单纯形集为拓扑空间的研究提供了一种组合方法。它们与简单复合物（simplicial complex）的简单概念有关，简单复合物通过将称为simplicies的简单构建块粘合在一起来构造拓扑空间，但它们更为普遍。在范畴论的语言中，简单集合是最容易被完全抽象化的。

单纯集是有向图、半序集和范畴的高维推广。形式上，单纯集可以定义为从单纯形范畴到集合范畴的逆变函子。单纯集是在1950年由Samuel Eilenberg和J. A. Zilber提出的。

范畴论的理解：范畴论（ category theory）是数学的一门学科，以抽象的方法来处理数学概念，将这些概念形式化成一组组的“物件”及“态射”。数学中许多重要的领域可以形式化成范畴，并且使用范畴论，令在这些领域中许多难理解、难捉摸的数学结论可以比没有使用范畴还会更容易叙述及证明。        范畴最容易理解的一个例子为集合范畴，其物件为集合，态射为集合间的函数,设X{0、1、2、3、4}0<=x<=4，态射：y=x+1。但需注意，范畴的物件不一定要是集合，态射也不一定要是函数；一个数学概念若可以找到一种方法，以符合物件及态射的定义，则可形成一个有效的范畴，且所有在范畴论中导出的结论都可应用在这个数学概念之上。

函子（ functor）：将一个范畴的每个物件和另一个范畴的物件相关连起来，并将第一个范畴的每个态射和第二个范畴的态射相关连起来。

每一范畴都由其对象，态射，和复合态射来表述。为了方便起见，以下的“函数”即是指态射。

Set 是所有集合和它们彼此之间的全函数构成的范畴

Ord 是所有预序集和其间的单调函数构成的范畴

Mag 是所有广群和其间的同态映射构成的范畴

Med 是所有对换广群和其间的同态映射构成的范畴

Defnition 1：范畴∆具有作为对象的fnite顺序集[n] = {1, . . . , n},用（非严格）保序映射给出的图

Defnition 2：一个单纯集是从∆op到数据集（Sets）集合的函子。给定一个简单集X，∆op→ Sets,n用来表示中的元素，单纯形集最简单的例子是标准单纯形被定义用来表示函数hom∆(·,[n])。据Yoneda引理，X的n-单纯形与单纯形集范畴中的态射∆n→ X之间存在着自然的对应关系，通过密度定理和使用少量的符号，我们得到了：

covariant functor：函子 保留箭头的方向，则该函子称为协变，即每个箭头都映射到一个箭头 | · | : ∆ → Top mapping

一个标准的协变函子|·|:∆→高级类别∆的映射的拓扑空间范畴发送[n]标准n单形|∆n |⊂Rn + 1 defned被定义为：

用标准的子空间拓扑。如果X : ∆op→ Sets是一个简单的集合，那么我们可以构造X表示逆极限。

拓扑空间与给定的单纯形集相关联。相反地，给定一个拓扑空间Y，我们可以通过构造一个关联的单形集S（Y），S（Y）叫做Y的奇异集：

实现函子和奇异集函子是经典同伦理论的一个标准结果，并提供了拓扑空间与单纯形集之间转换的标准方法。我们的目标是使这些强大的经典结果适用于fnite度量空间的情况。

Defnition 3：一个预层P是 I^op 集上的函子。模糊集是I上的一个预割，使得所有映射P(a ≤ b)都是注入。（I上的预升形成一个范畴，其态射由自然变换给出）。

Defnition 4：fuzzy集的范畴Fuzz是fuzzy集所跨越的I上带轮的完全子范畴。

Defnition 5：模糊单纯形集的范畴sFuzz是指从∆op到Fuzz函子给出对象，由自然变换给出态射的范畴。

Defnition 6：

扩展伪度量空间（X，d）是一个集X和一个映射d:X×X→R≥0∪{∞}，使得

扩展伪度量空间EPMet的范畴看做对象扩展伪度量空间和非扩展映射作为态射。给出了fnite扩展伪度量空间FinEPMet的子范畴。

Defnition 7：

Defnition 8：

利用模糊奇异集函子将族中的每个度量空间转化为一个模糊单纯形集，在模糊结构中保留度量信息的同时提取拓扑信息。消除由此产生的模糊单形集族的不相容性，只需在整个族上取（fuzzy）并即可。结果是一个单一的模糊单纯形集，它捕获流形M的相关拓扑和底层度量结构。

Defnition 9：

fuzzy集并集提供了将不同度量空间合并在一起的方法。Tis提供了一个模糊单纯形集作为流形的全局表示，流形是由多个局部表示拼凑而成的。我们可以通过简单地寻找与源数据的拓扑结构紧密匹配的低维表示来进行降维。我们现在考虑寻找这样一个低维表示的任务。

2.3 Optimizing a low dimensional representation

    让Y={Y1，，YN}⊆是一个低维（d<<n）表示X，使yi表示源数据点Xi。与我们要估计数据均匀分布的流形的源数据相比，我们知道Y的流形是。因此我们知道了流形和流形先验度量，并且可以直接计算模糊拓扑表示。值得注意的是，我们仍然希望根据局部连通性要求合并到最近邻的距离。它可以通过提供一个参数来定义嵌入空间中最近邻居之间的期望距离来实现。

    给定x和Y的模糊单纯形集表示，需要一种比较方法。如果我们只考虑模糊单纯形集的 1-skeleton，我们就可以把它们描述成一个模糊图，或者更具体地说，一个模糊边集。为了比较两个模糊集，我们将使用模糊集交叉熵。为此，我们将回到经典的模糊集表示法。由参考集A和隶属度函数μ：A→[0,1]给出模糊集。可比模糊集具有相同的参考集。给定一层表示P，我们可以通过设置将其转化为经典模糊集A =Ua∈(0,1)P（[0，a）和μ（x）=sup{a∈（0,1]| x∈P（[0，a））}将其转化为经典模糊集。

Defnition 10:

信息熵的计算：

类似于t-SNE，我们可以利用随机梯度下降来优化嵌入Y相对于模糊集交叉熵C的性质。然而，这需要一个可区分的模糊奇异集函子。如果点之间的期望最小距离为零，则模糊奇异集函子在这些情况下是可差分的，但是对于任何非零值，我们需要进行可差分逼近（从合适的可差分函数族中选择）。

    完成了该算法:利用流形逼近和局部模糊单纯集表示相结合的方法，构造了高维数据的拓扑表示。然后，我们在低维空间中优化数据的布局，以最小化两种拓扑表示之间的误差。我们注意到，在这种情况下，我们限制了对模糊单形集的 1-skeleta的比较。我们可以通过定义成本函数C‘将其扩展到 1-skeleta。

T-SNE的损失函数是通过KL散来进行构造的。

其中表示X的 i-simplices的模糊集，适当选择的实值权重。虽然这种方法可以更准确地捕捉整体拓扑结构，但由于越来越多的高维单纯形，其计算代价是不可忽略的。因此，目前的实现仅限于1-skeleton（ 曲面的一组边和顶点，例如，立方体的1骨架是连接角的12条边的集合。）。

1-skeleton

3 A Computational View of UMAP

    前面已经对相关的概念进行了理解，为了进一步理解UMAP算法实际上是在进行什么样的计算UMAP论述是基于模糊单形集（ fuzzy simplicial sets）。在计算上实际可以描述为加权图的一个骨架。从实际计算的角度来看，UMAP最终可以用加权图的构造和操作来描述。特别地，这将UMAP定位在一类基于k-邻域的图学习算法中，例如Laplacian特征映射、Isomap和t-SNE。UMAP可以分为两个阶段来描述。在第一阶段，构造了一个特定的加权k邻域图。在第二阶段，计算该图的低维布局。

3.1 Graph Construction（高维空间中）

图的构造基本过程：

UMAP第一个阶段可以被认为是加权k近邻图的构造，X = {x1, . . . , xN} 为输入的数据，具有度量（或不同度量）d:X×X→R≥0。给定一个输入超参数k，K表示所具有的K个邻居，在度量d计算每个数据点的k近邻，然后采用最近邻下降算法。

3.2 Graph Layout(空间中）

UMAP在低维空间中使用了一种力导向图布局算法（force directed graph layout algorithm ）。力导向图布局利用沿边施加的一组反作用力和顶点之间施加的一组斥力。任何力定向布局算法都需要描述引力作用力和斥力。算法通过在每个边或顶点迭代施加引力和斥力来进行。收敛性是通过缓慢降低反作用力和斥力来保证的，其方式与模拟退火中使用的方法类似。在UMAP中，坐标yi和yj处的两个顶点i和j之间的作用力分别由以下公式确定：

其中a和b是超参数。由于计算上的限制，斥力是通过采样来计算的。当一个引力作用于一条边时，该边的一个顶点会被其他顶点的采样所排斥。斥力由

这个算法可以随机初始化，但在实际应用中，由于图G的对称Laplacian是流形的Laplace-Beltrami算子的离散逼近，我们可以使用谱布局来初始化嵌入。Tis在算法中提供了更快的收敛性和更大的稳定性。

4 Implementation and Hyper-parameters

首先对实现的算法进行更详细的描述，最后讨论了该算法的超参数及其实际效果。

4.1 Algorithm description

当在局部模糊单形集上执行一个模糊并集时，我们发现使用概率型t-conorm是最有效的(正如人们所期望的那样，如果将隶属强度视为单形存在的概率)。下面将更详细地描述用于构造局部模糊简单集、确定谱嵌入以及根据模糊集交叉熵优化嵌入的各个函数。

算法2描述了局部模糊单纯形集的构造。为了表示模糊单纯形集，我们使用[0]和[1]的模糊集图像（即1-骨架），我们将其表示为fs-set0和fs-set1。我们也可以使用更高阶的simplice，但当前的实现不能。通过对n个最近邻进行fnite，在流形上生成适当的正规化距离，然后通过函子搜索将fnite度量空间转化为一个简单集，在这种情况下，它转化为负距离的指数。

我们不直接使用到第n近邻的距离作为标准化，而是使用平滑版的knn距离，它将1-单纯形模糊集的基数固定为固定值。为此，我们在实验的基础上选择了log2（n）。

构造局部模糊单形集

谱嵌入初始化

特征向量：Eigenvectors

度矩阵（degree matrix）：度矩阵和拓扑学相关，矩阵中只有main diagonal上有非零值，节点的度表示与该节点相连的边的数量（如果自循环则算两个），图的度矩阵即用于描述图中每个节点的度的矩阵，一般使用D表示。

UMAP的主要组成部分是通过最小化模糊集交叉熵来优化嵌入。对于给定的隶属函数μ和ν

我们采用基于抽样的优化方法。我们对概率为μ（a）的1-单形样本进行采样，并根据处理术语μ（a）log（ν（a））的v（a）值进行更新。这项（1-u（a））log（1-v（a））需要负采样-而不是计算所有潜在的单形，我们随机采样潜在的1-单形，并假设它们是一个负示例（即成员强度为0），然后根据1-v（a）的值进行更新。提供的顶点采样（vertex sampling）分布：

因此，对于给定的 1-simplex a，它只剩下一个v（a）的可差分近似值，通过负采样确定u（a）然后对v（a）应用梯度下降法进行优化。具体如下：

Defnition 11：

优化过程采用随机梯度下降法，如算法5所示：

4.2 Implementation

    该算法的实际实现需要（近似）k近邻计算和通过随机梯度下降的有效优化。利用文[16]中的近邻下降算法，可以实现高效的近似k近邻计算。降维技术中固有的误差意味着这种近似对于这些目的来说是足够的。虽然没有为最近邻下降建立理论复杂度边界，但原始论文的作者报告了经验复杂度O（N1.14）。最近邻法的另一个优点是它的通用性；它适用于任何有效的相异度量，即使对于高维数据也是有效的。

    在所提供的目标函数下优化嵌入时，我们遵循了[45]的工作；利用概率边缘采样和负采样。由于没有规范化要求，它提供了一种非常有效的近似随机梯度下降算法。此外，由于输入数据的模糊图表示的规范化拉普拉斯是流形，我们可以使用规范化Laplacian的特征向量为随机梯度下降提供合适的初始化。所需的优化工作量将随模糊图中的边数（假设为fxed负采样率）而缩放，从而导致复杂性为O（kN）。

4.3 Hyper-parameters

算法一中含有四个超参数，

1、n表示逼近局部度量时要考虑的邻域数目

2、d表示目标嵌入维数

3、min-dist,嵌入空间中闭合点之间的期望间隔。

4、n-epochs，优化低维表示时要使用的训练阶段数。

在图1中，我们提供了为玩具数据集（toy dataset）更改超参数的效果示例。这个数据是来自三维彩色立方体的均匀随机样本，通过使用相应的RGB颜色，可以方便地显示嵌入空间中的原始三维坐标。由于数据是三维立方体，因此没有局部流形结构，因此对于此类数据，我们希望更大的n值更有用。n比较小时会将随机采样的噪声解释为fne尺度流形结构，产生潜在的杂散结构。

图1:UMAP超参数n和min dist的变化导致不同的嵌入。数据是来自三维彩色立方体的均匀随机样本，通过使用相应的RGB颜色，可以方便地显示嵌入空间中的原始三维坐标。n的低值错误地解释了随机采样噪声的结构-有关此现象的进一步讨论，请参见第6节。

5 Practical Efficacy 

Pen digits：是一组1797个灰度数字图像，使用数字输入板输入。每个图像都是一个8x8图像，我们将其视为一个64维向量，假设它在欧氏向量空间中。

COIL 20：是一组1440个灰度图像，由20个对象组成，72个不同的旋转范围为360度。每个图像是一个128x128图像，我们将其作为一个16384维向量来计算图像之间的距离。

COIL 100：是一组7200幅彩色图像，由100个对象组成，在360度的72个不同旋转。每个图像由3个128x128强度矩阵组成（每个颜色通道一个）。为了计算图像之间的距离，我们将其视为一个49152维向量。

Mouse scRNA-seq：提供了成年小鼠20921个细胞的基因表达数据。每个样本由26774个测量向量组成

Statlog (Shuttle) ：是美国宇航局的一个数据集，包含与航天飞机中散热器位置相关的各种数据，包括时间戳。Te数据集在9维特征空间中有58000个点。

MNIST：是一个28x28像素的手写数字灰度图像集。Tere是10位数的类（0到9），总共有70000个图像。Tis被视为70000个不同的784维向。

F-MNIST ：时尚MNIST是一个28x28像素的时尚物品（服装、鞋类和箱包）灰度图像的数据集。有10个类，共70000张图片。与MNIST一样，这被视为70000个不同的784维向量。

Flow cytometry：是一个流式细胞术测量CDT4细胞的数据集，由1000000个样本组成，每个样本有17个测量值。

GoogleNews word vectors ：是一个由300万个单词和短语组成的数据集，这些单词和短语来自Google新闻文档的样本，并通过word2vec嵌入到300维空间中

5.1多种算法的质量比较

    t-SNE和LargeVis在数据定位和保存局部结构方面都有显著的改进。通过比较它们的嵌入与Laplacian特征映射和PCA在2中生成的嵌入，可以定性地看到Tis。我们认为，当减小到二维或三维时，UMAP生产的埋件质量与t-SNE相当。例如，图2显示了COIL20、MNIST、Fashion、MNIST和Google News数据集的UMAP和t-SNE嵌入。当精确的嵌入不同时，UMAP区分了与t-SNE和LargeVis相同的结构。

    可以说UMAP比t-SNE[4]捕获了更多的数据集的全局和拓扑结构。COIL20数据集中的更多循环保持完整，包括交织的循环。类似地，MNIST digits数据集中不同数字之间的全局关系更清楚地被捕捉到，1（红色）和0（深红色）位于嵌入空间的远角，4,7,9（黄色、海绿和紫色）和3,5,8（橙色、绿色和蓝色）被分离为不同的相似数字簇。在时尚MNIST数据集中，服装（深红色、黄色、橙色、朱红色）和鞋类（黄绿色、海绿和紫色）之间的区别更加明显。最后，当t-SNE和UMAP都捕获相似的词向量组时，UMAP嵌入可以证明在不同的词簇之间有更清晰的全局结构。

5.2 Embedding Stability

图2: 几种降维算法的比较。我们注意到UMAP成功地反映了大量由拉普拉斯特征映射和主成分分析（尤其是MNIST和时尚MNIST）很好地表示的大规模全局结构，同时也保留了类似于t-SNE和LargeVis的局部fne结构。

    为了比较UMAP、LargeVis和t-SNE（考虑的三维随机降维技术）的次采样下的稳定性。从而度量嵌入的稳定性，我们使用归一化普洛克魯斯距离（Procustes distance：是两个图形或者两个矩阵中地标位置差异平方和的平方根。这可以用来描述许多地标配置之间的差异）来度量两个潜在可比分布之间的距离。给定两个数据集X={x1、、、xN}和Y={y1、、yN}，xi对应 yi。确定Y0={y10。，yN0}使平方误差PNi=1(xi− yi）^2最小化的Y的最佳平移、均匀缩放和旋转，定义为：

其值越小越好

由于在嵌入空间中使用距离的任何度量都可能对嵌入的范围或规模敏感，因此我们在计算Procrustes距离之前先将数据标准化，然后除以嵌入数据集的平均范数。在图3中，我们可视化了对UMAP和t-SNE的子样本嵌入使用Procrustes对齐的结果，演示了Procrustes距离如何测量嵌入的整体结构的稳定性。给定不同嵌入之间距离的度量，我们可以通过考虑子样本嵌入与整个数据集嵌入的相应子样本之间的规范化Procrustes距离来检查子采样下的稳定性。随着子样本大小的增加，子样本嵌入点之间的平均每点距离应减小，在重复运行

下可能朝着最大一致性的某个渐近线移动。理想情况下，该渐近值为零误差，但对于随机嵌入，如UMAP和t-SNE，这是不可能实现的。我们使用流式细胞仪数据集对算法的稳定性进行了经验比较，因为它具有较大的尺寸、有趣的结构和较低的环境维度（有助于t-SNE的运行时性能）。我们注意到，对于这么大的数据集，我们发现有必要将t-SNE的默认n_iter值从1000增加到1500，以确保更好的收敛性。

基于Procrustes的10%子样本（红色）与用于UMAP和t-SNE的fow细胞术数据集的完整数据集（蓝色）的对齐。

5.3 Computational Performance Comparisons

实验设备：

实世界数据集的基准测试在Macbook Pro上执行，Macbook Pro具有3.1 GHz的Intel Corei7和8GB的RAM（用于表1），在服务器上使用Intel XeonE5-2697v4处理器和512GB的RAM（用于5.3.1、5.3.2和5.3.3小节中的大规模基准测试）。对于t-SNE，我们选择了MulticoreTSNE[48]，我们认为这是目前BarnesHut t-SNE最快的实现。

图4：全流式细胞仪数据集中不同大小的子样本上t-SNE、LargeVis和UMAP的平均每点程序距离的比较。UMAP子样本嵌入非常接近完全嵌入，即使子样本占整个数据集的5%，即使使用全流式细胞仪据集，其结果也优于t-SNE和LargeVis。

5.3.1 Scaling with Embedding Dimension，

UMAP的整合性能远比t-SNE高效，即使是非常小的嵌入维数为6或8(参见图5)。这主要是由于UMAP不需要全局规范化的事实。它允许算法在不需要空间树的情况下工作，例如t-SNE使用的四叉树和oct树[49]。这种空间树在维数上呈指数级缩放，导致t-SNE相对于嵌入维数的缩放效果相对较差。

表1：各种数据集上的几种降维算法的运行时间。允许更广泛的算法运行某些数据集，其中子采样或其维数由PCA降低。流式细胞仪数据集以10%的样本为基准，GoogleNews被再抽样到200000个数据点。最后，通过PCA将小鼠scRNA数据集降到1000维。每个数据集的最快运行时间已加粗

相比之下，我们发现UMAP在嵌入维度上具有很好的一致性，使得该算法在可视化之外的更广泛应用中具有实用性，T-SNE对于维度过高或者过低的处效果都不好。

在笔数据集上UMAP、t-SNE和LargeVis的嵌入维数方面的缩放性能。

5.3.2 Scaling with Ambient Dimension

通过结合本地连接性约束和近似近邻搜索，UMAP甚至可以对非常高维的数据执行有效的降维（关于直接在180万维数据上操作UMAP的示例，请参见图9）。tis许多其他流形学习技术（包括t-SNE和LargeVis）形成对比，对于这些技术，通常建议在应用这些技术之前使用PCA来减小维数（例如，参见[50]）。为了比较相对于数据的环境维度的运行时性能缩放，我们选择使用高维度的鼠标scRNA数据集，但也可以使用PCA来减少数据30的维度，作为预处理步骤，而不会丢失太多重要结构3。在图6中，我们比较了UMAP、FItSNE、MulticoreTSNE和LargeVis在将小鼠scRNA数据集的PCA还原为不同维度上的性能，以及在原始数据集上的性能。

5.3.3 Scaling with the Number of Samples

对于数据集大小性能比较，我们选择将UMAP与FItSNE进行比较，FItSNE[30]是t-SNE的一个版本，它使用近似近邻搜索和傅立叶插值优化方法；MulticoreTSNE[48]，我们认为它是Barnes Hut t t-SNE现存最快的实现；

图6:UMAP、t-SNE、FIt-SNE和Largevis相对于数据环境维度的运行时性能缩放。当环境维数增加到几千维以上时，t-SNE、FIt-SNE和LargeVis的计算成本都会急剧增加，而UMAP在成千上万维中的表现仍然很好。

图7:t-SNE和UMAP在整个Google新闻数据集的不同大小的子样本上的运行时性能缩放。Te lower t-SNE line是8核多核t-SNE的挂钟运行时间。

图8:UMAP嵌入的GoogleNews数据集的300万字矢量的可视化。

UMAP允许生成任意大的、超高维的数据集，这些数据集仍然具有需要探索的有意义的结构。在图9和图10中，我们显示了从大约180万维的环境空间嵌入30000000个数据样本。在一个大内存SMP上，Tis计算大约需要2周。注意，尽管环境维度高，数据量大，UMAP仍然能够fnd并显示有趣的结构。在图11中，我们展示了嵌入的局部区域，展示了捕捉到的细节结构。

6 Weaknesses

1、UMAP缺乏主成分分析（PCA）和非负矩阵分解（NMF）等相关技术的强大解释能力（strong interpretability）。由于UMAP是基于观测值之间的距离而不是源特征（ source features），因此它不具有PCA或因子分析等线性技术所能提供的等效因子载荷。如果很强的可解释性是至关重要的，建议使用线性技术。

2、随着采样的数据越多，从噪声中明显可见的结构数量将趋于减少，UMAP变得更加健壮，但是必须注意小样本的噪声数据，或仅具有大尺度流形结构的数据（小噪声的数据的噪音影响较大。

3、UMAP主要关注的是准确地表示局部结构。虽然我们相信UMAP可以捕获比这些其他技术更多的全局结构，但如果全局结构是主要关注点，那么UMAP可能不是降维的最佳选择。

4、为了提高算法的计算效率，进行了一些近似计算（k近邻算法，以及在优化中使用负采样，会导致次优嵌入:suboptimal embeddings），对于小于500维的数据集将会产生影响.

7 Future Work

1、可以扩展到支持（半监督）降维和异构数据集降维。每种数据类型（或监督情况下的预测变量）可以被视为底层结构的替代视图，每种类型都有不同的关联度量

2、每个视图和度量都可以独立地生成模糊简单集，然后将模糊简单集交叉在一起，创建一个用于嵌入的模糊简单集。

3、扩展UMAP以处理混合数据类型将极大地增加它可以应用到的数据集的范围。用于（半监督）降维的用例包括半监督聚类和交互式标记工具。为UMAP建立的Te计算框架允许潜在的技术发展，将新的不可见数据点添加到现有的嵌入中，并生成嵌入空间中任意点的高维表示。

4、将新样本添加到现有嵌入将允许UMAP用作特征工程工具，作为集群或分类任务的通用机器学习管道的一部分。将点从嵌入的空间拉回到原始的高维空间，可以使UMAP用作生成模型，类似于自动编码器的一些用例。

5、在开发技术以检测和减轻潜在的虚假嵌入方面仍然有着重要的作用，特别是在小数据情况下。这种技术的加入将使UMAP作为探索性数据分析的工具变得更加健壮，这是为了可视化而减少到二维时的常见用例

8 Conclusions

UMAP降维算法明显快于t-SNE算法，并且提供了更好的尺度。它允许我们生成比以前无法实现的更大数据集的高质量嵌入。UMAP在各种科学领域的应用和有效性证明了算法的强大性。