Abstract：
統(tǒng)一流形逼近與投影(UMAP:Uniform Manifold Approximation and Projection)是一種新的降維技術(shù)，其理論基礎(chǔ)是黎曼幾何和代數(shù)拓?fù)?。相?duì)于T-SNE降維，UMAP的優(yōu)點(diǎn)在于:(1)能夠盡可能多的保留全局結(jié)構(gòu)，（2）耗時(shí)更短(見(jiàn)表一)，（3）對(duì)嵌入維數(shù)沒(méi)有限制可以擴(kuò)展到更大的維度的數(shù)據(jù)集（T-SNE對(duì)數(shù)據(jù)的維度有所限制（Hinton的T-SNE實(shí)驗(yàn)中先用PCA降到50,再進(jìn)一步的使用T-SNE）、密集的數(shù)據(jù)才能達(dá)到較好的可視化效果）。（T-SNE是建立在二維的基礎(chǔ)上，而UMAP則是建立在三維的黎曼流行上，相關(guān)定義、計(jì)算方法都會(huì)發(fā)生一定的變化）。
1. Introduction
????降維可以定義為將高維數(shù)據(jù)降低為低維同時(shí)盡可能保證數(shù)據(jù)的全局性，降維技術(shù)是機(jī)器學(xué)習(xí)中大數(shù)據(jù)預(yù)處理的一種重要技術(shù)。降維的算法主要分為兩類：（1）在數(shù)據(jù)中保持距離結(jié)構(gòu)的算法——線性降維（PCA、MDS和Sammon映射），（2）在全局距離上保持局部距離的算法（流形學(xué)習(xí)）——非線性降維（t-SNE、Isomap、LargeVis、Laplacian特征映射和difusion映射）。
? ??UMAP的數(shù)學(xué)基礎(chǔ)主要是Belkin和Niyogi在拉普拉斯特征映射所做的工作，對(duì)于流形數(shù)據(jù)的分布問(wèn)題，采用的是黎曼幾何和David Spivak在范疇論（category theoretic）方法中的工作。UMAP目前已經(jīng)應(yīng)用于生物信息學(xué)、材料科學(xué)和機(jī)器學(xué)習(xí)等領(lǐng)域得到廣泛應(yīng)用。這篇文章的基本框架如圖一：
2 .Teoretical Foundations for UMAP
? ??UMAP的理論基礎(chǔ)主要基于流形理論和拓?fù)鋽?shù)據(jù)分析。許多理論最容易用拓?fù)鋵W(xué)和范疇理論來(lái)解釋。UMAP利用局部流形逼近（ local manifold approximations）和局部模糊單純形集表示（local fuzzy simplicial set representations）來(lái)構(gòu)造高維數(shù)據(jù)的拓?fù)浔硎尽＝o定數(shù)據(jù)的一些低維表示，可以使用類似的過(guò)程來(lái)構(gòu)造等價(jià)的低維拓?fù)浔硎尽呔S和低維換種表達(dá)方式。然后UMAP優(yōu)化低維空間中數(shù)據(jù)表示的布局，以最小化兩個(gè)拓?fù)浔硎局g的交叉熵(（交叉熵（Cross Entropy）是Shannon信息論中一個(gè)重要概念，主要用于度量?jī)蓚€(gè)概率分布間的差異性信息。交叉熵的意義是用該模型對(duì)文本識(shí)別的難度，或者從壓縮的角度來(lái)看，每個(gè)詞平均要用幾個(gè)位來(lái)編碼）交叉熵CSDN鏈接：交叉熵（Cross-Entropy）_Python_rtygbwwwerr的專欄-CSDN博客,。
? ??模糊拓?fù)浔硎镜臉?gòu)造可分為兩個(gè)問(wèn)題：一個(gè)是假設(shè)數(shù)據(jù)所在的流形的逼近問(wèn)題；另一個(gè)是流形逼近的模糊單純形集表示問(wèn)題。通過(guò)以下三節(jié)2.1、2.2、2.3對(duì)算法進(jìn)行詳細(xì)介紹。
2.1 Uniform distribution of data on a manifold and geodesic approximation（流形上數(shù)據(jù)的均勻分布和測(cè)地線近似）
frst step:逼近我們假設(shè)的數(shù)據(jù)所在的流形(從數(shù)據(jù)中推斷出來(lái)，事先不知道)。輸入數(shù)據(jù)X = {X1, . . . , XN}，Belkin和Niyogi在Laplacian特征映射上的工作：假設(shè)流形有一個(gè)不是從環(huán)境空間繼承來(lái)的黎曼度量，我們可以定義一個(gè)度量那么數(shù)據(jù)在流形上均勻分布。M是我們假設(shè)數(shù)據(jù)所在的流形，設(shè)g是M的黎曼度量，對(duì)于每個(gè)點(diǎn)p∈M，我們有
，它是切線空間(tangent space)
M上的內(nèi)積。
Lemma 1：設(shè)（M，g）是一個(gè)環(huán)境中的黎曼流形，數(shù)據(jù)點(diǎn)p∈M（數(shù)據(jù)流）,g是關(guān)于開(kāi)鄰域U的局部常數(shù)，使得g在環(huán)境坐標(biāo)系中是一個(gè)常數(shù)對(duì)角矩陣，那么在以p為中心的球B?U中，相對(duì)于g的體積πn/2Γ（n/2+1），p到任意點(diǎn)q∈B的測(cè)地線距離( geodesic distance：在三維空間中，兩點(diǎn)之間的最短路徑)是p到任意點(diǎn)q∈B的測(cè)地線距離為
dRn（p，q），其中r是球在環(huán)境空間中的半徑，dRn是環(huán)境空間上的現(xiàn)有度量（證明略）。
? ? 通過(guò)引理1，可以對(duì)的
近鄰的距離進(jìn)行正規(guī)化來(lái)近似于xi與其近鄰的測(cè)地線距離。通過(guò)為每個(gè)
創(chuàng)建一個(gè)自定義距離，我們可以確保在流形假設(shè)下均勻分布假設(shè)的有效性。而這些距離概念可能不兼容。我們有一個(gè)離散度量空間家族（每個(gè)度量空間對(duì)應(yīng)一個(gè)度量空間），我們希望將其合并為一致的全局結(jié)構(gòu)。這可以通過(guò)將度量空間(metricspaces)轉(zhuǎn)換為模糊單純形集（fuzzy simplicial sets）以自然的方式完成。
2.2 Fuzzy topological representation
? ??我們將數(shù)據(jù)轉(zhuǎn)換為模糊拓?fù)浔硎荆院喜?shù)據(jù)的不相容局部視圖，方法的主要理論依據(jù)來(lái)自于邁克爾·巴爾（Michael Barr）和大衛(wèi)·斯皮瓦克（David Spivak）的工作。我們將轉(zhuǎn)換為模糊拓?fù)浔硎荆?b>以合并數(shù)據(jù)的不相容局部視圖。首先，我們將回顧簡(jiǎn)單集（simplicial sets）的定義。單純形集為拓?fù)淇臻g的研究提供了一種組合方法。它們與簡(jiǎn)單復(fù)合物（simplicial complex）的簡(jiǎn)單概念有關(guān)，簡(jiǎn)單復(fù)合物通過(guò)將稱為simplicies的簡(jiǎn)單構(gòu)建塊粘合在一起來(lái)構(gòu)造拓?fù)淇臻g，但它們更為普遍。在范疇論的語(yǔ)言中，簡(jiǎn)單集合是最容易被完全抽象化的。
范疇論的理解：范疇論（ category theory）是數(shù)學(xué)的一門(mén)學(xué)科，以抽象的方法來(lái)處理數(shù)學(xué)概念，將這些概念形式化成一組組的“物件”及“態(tài)射”。數(shù)學(xué)中許多重要的領(lǐng)域可以形式化成范疇，并且使用范疇論，令在這些領(lǐng)域中許多難理解、難捉摸的數(shù)學(xué)結(jié)論可以比沒(méi)有使用范疇還會(huì)更容易敘述及證明。????????范疇最容易理解的一個(gè)例子為集合范疇，其物件為集合，態(tài)射為集合間的函數(shù),設(shè)X{0、1、2、3、4}0<=x<=4，態(tài)射：y=x+1。但需注意，范疇的物件不一定要是集合，態(tài)射也不一定要是函數(shù)；一個(gè)數(shù)學(xué)概念若可以找到一種方法，以符合物件及態(tài)射的定義，則可形成一個(gè)有效的范疇，且所有在范疇論中導(dǎo)出的結(jié)論都可應(yīng)用在這個(gè)數(shù)學(xué)概念之上。
函子（ functor）：將一個(gè)范疇的每個(gè)物件和另一個(gè)范疇的物件相關(guān)連起來(lái)，并將第一個(gè)范疇的每個(gè)態(tài)射和第二個(gè)范疇的態(tài)射相關(guān)連起來(lái)。
每一范疇都由其對(duì)象，態(tài)射，和復(fù)合態(tài)射來(lái)表述。為了方便起見(jiàn)，以下的“函數(shù)”即是指態(tài)射。
Set?是所有集合和它們彼此之間的全函數(shù)構(gòu)成的范疇
Ord?是所有預(yù)序集和其間的單調(diào)函數(shù)構(gòu)成的范疇
Mag?是所有廣群和其間的同態(tài)映射構(gòu)成的范疇
Med?是所有對(duì)換廣群和其間的同態(tài)映射構(gòu)成的范疇
Defnition 1：范疇?具有作為對(duì)象的fnite順序集[n] = {1, . . . , n},用（非嚴(yán)格）保序映射給出的圖
Defnition 2：一個(gè)單純集是從?op到數(shù)據(jù)集（Sets）集合的函子。給定一個(gè)簡(jiǎn)單集X，?op→ Sets,n用來(lái)表示中的元素，單純形集最簡(jiǎn)單的例子是標(biāo)準(zhǔn)單純形
被定義用來(lái)表示函數(shù)hom?(·,[n])。據(jù)Yoneda引理，X的n-單純形與單純形集范疇中的態(tài)射?n→ X之間存在著自然的對(duì)應(yīng)關(guān)系，通過(guò)密度定理和使用少量的符號(hào)，我們得到了：
covariant functor：函子?保留箭頭的方向，則該函子稱為協(xié)變，即每個(gè)箭頭都映射到一個(gè)箭頭 | · | : ? → Top mapping
一個(gè)標(biāo)準(zhǔn)的協(xié)變函子|·|:?→高級(jí)類別?的映射的拓?fù)淇臻g范疇發(fā)送[n]標(biāo)準(zhǔn)n單形|?n |?Rn + 1 defned被定義為：
用標(biāo)準(zhǔn)的子空間拓?fù)?。如果X : ?op→ Sets是一個(gè)簡(jiǎn)單的集合，那么我們可以構(gòu)造X表示逆極限。
拓?fù)淇臻g與給定的單純形集相關(guān)聯(lián)。相反地，給定一個(gè)拓?fù)淇臻gY，我們可以通過(guò)構(gòu)造一個(gè)關(guān)聯(lián)的單形集S（Y），S（Y）叫做Y的奇異集：
實(shí)現(xiàn)函子和奇異集函子是經(jīng)典同倫理論的一個(gè)標(biāo)準(zhǔn)結(jié)果，并提供了拓?fù)淇臻g與單純形集之間轉(zhuǎn)換的標(biāo)準(zhǔn)方法。我們的目標(biāo)是使這些強(qiáng)大的經(jīng)典結(jié)果適用于fnite度量空間的情況。
Defnition 3：一個(gè)預(yù)層P是 I^op?集上的函子。模糊集是I上的一個(gè)預(yù)割，使得所有映射P(a ≤ b)都是注入。（I上的預(yù)升形成一個(gè)范疇，其態(tài)射由自然變換給出）。
Defnition 4：fuzzy集的范疇Fuzz是fuzzy集所跨越的I上帶輪的完全子范疇。
Defnition 5：模糊單純形集的范疇sFuzz是指從?op到Fuzz函子給出對(duì)象，由自然變換給出態(tài)射的范疇。
Defnition 6：
擴(kuò)展偽度量空間（X，d）是一個(gè)集X和一個(gè)映射d:X×X→R≥0∪{∞}，使得
擴(kuò)展偽度量空間EPMet的范疇看做對(duì)象擴(kuò)展偽度量空間和非擴(kuò)展映射作為態(tài)射。給出了fnite擴(kuò)展偽度量空間FinEPMet的子范疇。
Defnition 7：
Defnition 8：
利用模糊奇異集函子將族中的每個(gè)度量空間轉(zhuǎn)化為一個(gè)模糊單純形集，在模糊結(jié)構(gòu)中保留度量信息的同時(shí)提取拓?fù)湫畔?。消除由此產(chǎn)生的模糊單形集族的不相容性，只需在整個(gè)族上?。╢uzzy）并即可。結(jié)果是一個(gè)單一的模糊單純形集，它捕獲流形M的相關(guān)拓?fù)浜偷讓佣攘拷Y(jié)構(gòu)。
Defnition 9：
fuzzy集并集提供了將不同度量空間合并在一起的方法。Tis提供了一個(gè)模糊單純形集作為流形的全局表示，流形是由多個(gè)局部表示拼湊而成的。我們可以通過(guò)簡(jiǎn)單地尋找與源數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)緊密匹配的低維表示來(lái)進(jìn)行降維。我們現(xiàn)在考慮尋找這樣一個(gè)低維表示的任務(wù)。
2.3 Optimizing a low dimensional representation
????讓Y={Y1，，YN}?是一個(gè)低維（d<<n）表示X，使yi表示源數(shù)據(jù)點(diǎn)Xi。與我們要估計(jì)數(shù)據(jù)均勻分布的流形的源數(shù)據(jù)相比，我們知道Y的流形是
。因此我們知道了流形和流形先驗(yàn)度量，并且可以直接計(jì)算模糊拓?fù)浔硎?。值得注意的是，我們?nèi)匀幌Ｍ鶕?jù)局部連通性要求合并到最近鄰的距離。它可以通過(guò)提供一個(gè)參數(shù)來(lái)定義嵌入空間中最近鄰居之間的期望距離來(lái)實(shí)現(xiàn)。
? ??給定x和Y的模糊單純形集表示，需要一種比較方法。如果我們只考慮模糊單純形集的 1-skeleton，我們就可以把它們描述成一個(gè)模糊圖，或者更具體地說(shuō)，一個(gè)模糊邊集。為了比較兩個(gè)模糊集，我們將使用模糊集交叉熵。為此，我們將回到經(jīng)典的模糊集表示法。由參考集A和隸屬度函數(shù)μ：A→[0,1]給出模糊集?？杀饶：哂邢嗤膮⒖技?。給定一層表示P，我們可以通過(guò)設(shè)置將其轉(zhuǎn)化為經(jīng)典模糊集A =Ua∈(0,1)P（[0，a）和μ（x）=sup{a∈（0,1]| x∈P（[0，a））}將其轉(zhuǎn)化為經(jīng)典模糊集。
Defnition 10:
信息熵的計(jì)算：
類似于t-SNE，我們可以利用隨機(jī)梯度下降來(lái)優(yōu)化嵌入Y相對(duì)于模糊集交叉熵C的性質(zhì)。然而，這需要一個(gè)可區(qū)分的模糊奇異集函子。如果點(diǎn)之間的期望最小距離為零，則模糊奇異集函子在這些情況下是可差分的，但是對(duì)于任何非零值，我們需要進(jìn)行可差分逼近（從合適的可差分函數(shù)族中選擇）。
????完成了該算法:利用流形逼近和局部模糊單純集表示相結(jié)合的方法，構(gòu)造了高維數(shù)據(jù)的拓?fù)浔硎?。然后，我們?cè)诘途S空間中優(yōu)化數(shù)據(jù)的布局，以最小化兩種拓?fù)浔硎局g的誤差。我們注意到，在這種情況下，我們限制了對(duì)模糊單形集的 1-skeleta的比較。我們可以通過(guò)定義成本函數(shù)C‘將其擴(kuò)展到?1-skeleta。
T-SNE的損失函數(shù)是通過(guò)KL散來(lái)進(jìn)行構(gòu)造的。
其中表示X的 i-simplices的模糊集，
適當(dāng)選擇的實(shí)值權(quán)重。雖然這種方法可以更準(zhǔn)確地捕捉整體拓?fù)浣Y(jié)構(gòu)，但由于越來(lái)越多的高維單純形，其計(jì)算代價(jià)是不可忽略的。因此，目前的實(shí)現(xiàn)僅限于1-skeleton（?曲面的一組邊和頂點(diǎn)，例如，立方體的1骨架是連接角的12條邊的集合。）。
3 A Computational View of UMAP
? ? 前面已經(jīng)對(duì)相關(guān)的概念進(jìn)行了理解，為了進(jìn)一步理解UMAP算法實(shí)際上是在進(jìn)行什么樣的計(jì)算UMAP論述是基于模糊單形集（ fuzzy simplicial sets）。在計(jì)算上實(shí)際可以描述為加權(quán)圖的一個(gè)骨架。從實(shí)際計(jì)算的角度來(lái)看，UMAP最終可以用加權(quán)圖的構(gòu)造和操作來(lái)描述。特別地，這將UMAP定位在一類基于k-鄰域的圖學(xué)習(xí)算法中，例如Laplacian特征映射、Isomap和t-SNE。UMAP可以分為兩個(gè)階段來(lái)描述。在第一階段，構(gòu)造了一個(gè)特定的加權(quán)k鄰域圖。在第二階段，計(jì)算該圖的低維布局。
3.1 Graph Construction（高維空間中）
圖的構(gòu)造基本過(guò)程：
UMAP第一個(gè)階段可以被認(rèn)為是加權(quán)k近鄰圖的構(gòu)造，X = {x1, . . . , xN} 為輸入的數(shù)據(jù)，具有度量（或不同度量）d:X×X→R≥0。給定一個(gè)輸入超參數(shù)k，K表示所具有的K個(gè)鄰居，在度量d計(jì)算每個(gè)數(shù)據(jù)點(diǎn)
的k近鄰，然后采用最近鄰下降算法。
3.2 Graph Layout(空間中）
UMAP在低維空間中使用了一種力導(dǎo)向圖布局算法（force directed graph layout algorithm ）。力導(dǎo)向圖布局利用沿邊施加的一組反作用力和頂點(diǎn)之間施加的一組斥力。任何力定向布局算法都需要描述引力作用力和斥力。算法通過(guò)在每個(gè)邊或頂點(diǎn)迭代施加引力和斥力來(lái)進(jìn)行。收斂性是通過(guò)緩慢降低反作用力和斥力來(lái)保證的，其方式與模擬退火中使用的方法類似。在UMAP中，坐標(biāo)yi和yj處的兩個(gè)頂點(diǎn)i和j之間的作用力分別由以下公式確定：
其中a和b是超參數(shù)。由于計(jì)算上的限制，斥力是通過(guò)采樣來(lái)計(jì)算的。當(dāng)一個(gè)引力作用于一條邊時(shí)，該邊的一個(gè)頂點(diǎn)會(huì)被其他頂點(diǎn)的采樣所排斥。斥力由
這個(gè)算法可以隨機(jī)初始化，但在實(shí)際應(yīng)用中，由于圖G的對(duì)稱Laplacian是流形的Laplace-Beltrami算子的離散逼近，我們可以使用譜布局來(lái)初始化嵌入。Tis在算法中提供了更快的收斂性和更大的穩(wěn)定性。
4 Implementation and Hyper-parameters
首先對(duì)實(shí)現(xiàn)的算法進(jìn)行更詳細(xì)的描述，最后討論了該算法的超參數(shù)及其實(shí)際效果。
4.1 Algorithm description
當(dāng)在局部模糊單形集上執(zhí)行一個(gè)模糊并集時(shí)，我們發(fā)現(xiàn)使用概率型t-conorm是最有效的(正如人們所期望的那樣，如果將隸屬?gòu)?qiáng)度視為單形存在的概率)。下面將更詳細(xì)地描述用于構(gòu)造局部模糊簡(jiǎn)單集、確定譜嵌入以及根據(jù)模糊集交叉熵優(yōu)化嵌入的各個(gè)函數(shù)。
算法2描述了局部模糊單純形集的構(gòu)造。為了表示模糊單純形集，我們使用[0]和[1]的模糊集圖像（即1-骨架），我們將其表示為fs-set0和fs-set1。我們也可以使用更高階的simplice，但當(dāng)前的實(shí)現(xiàn)不能。通過(guò)對(duì)n個(gè)最近鄰進(jìn)行fnite，在流形上生成適當(dāng)?shù)恼?guī)化距離，然后通過(guò)函子搜索將fnite度量空間轉(zhuǎn)化為一個(gè)簡(jiǎn)單集，在這種情況下，它轉(zhuǎn)化為負(fù)距離的指數(shù)。
我們不直接使用到第n近鄰的距離作為標(biāo)準(zhǔn)化，而是使用平滑版的knn距離，它將1-單純形模糊集的基數(shù)固定為固定值。為此，我們?cè)趯?shí)驗(yàn)的基礎(chǔ)上選擇了log2（n）。
構(gòu)造局部模糊單形集
譜嵌入初始化
度矩陣（degree matrix）：度矩陣和拓?fù)鋵W(xué)相關(guān)，矩陣中只有main diagonal上有非零值，節(jié)點(diǎn)的度表示與該節(jié)點(diǎn)相連的邊的數(shù)量（如果自循環(huán)則算兩個(gè)），圖的度矩陣即用于描述圖中每個(gè)節(jié)點(diǎn)的度的矩陣，一般使用D表示。
UMAP的主要組成部分是通過(guò)最小化模糊集交叉熵來(lái)優(yōu)化嵌入。對(duì)于給定的隸屬函數(shù)μ和ν
我們采用基于抽樣的優(yōu)化方法。我們對(duì)概率為μ（a）的1-單形樣本進(jìn)行采樣，并根據(jù)處理術(shù)語(yǔ)μ（a）log（ν（a））的v（a）值進(jìn)行更新。這項(xiàng)（1-u（a））log（1-v（a））需要負(fù)采樣-而不是計(jì)算所有潛在的單形，我們隨機(jī)采樣潛在的1-單形，并假設(shè)它們是一個(gè)負(fù)示例（即成員強(qiáng)度為0），然后根據(jù)1-v（a）的值進(jìn)行更新。提供的頂點(diǎn)采樣（vertex sampling）分布：
因此，對(duì)于給定的 1-simplex a，它只剩下一個(gè)v（a）的可差分近似值，通過(guò)負(fù)采樣確定u（a）然后對(duì)v（a）應(yīng)用梯度下降法進(jìn)行優(yōu)化。具體如下：
Defnition 11：
優(yōu)化過(guò)程采用隨機(jī)梯度下降法，如算法5所示：
4.2 Implementation
????該算法的實(shí)際實(shí)現(xiàn)需要（近似）k近鄰計(jì)算和通過(guò)隨機(jī)梯度下降的有效優(yōu)化。利用文[16]中的近鄰下降算法，可以實(shí)現(xiàn)高效的近似k近鄰計(jì)算。降維技術(shù)中固有的誤差意味著這種近似對(duì)于這些目的來(lái)說(shuō)是足夠的。雖然沒(méi)有為最近鄰下降建立理論復(fù)雜度邊界，但原始論文的作者報(bào)告了經(jīng)驗(yàn)復(fù)雜度O（N1.14）。最近鄰法的另一個(gè)優(yōu)點(diǎn)是它的通用性；它適用于任何有效的相異度量，即使對(duì)于高維數(shù)據(jù)也是有效的。
? ??在所提供的目標(biāo)函數(shù)下優(yōu)化嵌入時(shí)，我們遵循了[45]的工作；利用概率邊緣采樣和負(fù)采樣。由于沒(méi)有規(guī)范化要求，它提供了一種非常有效的近似隨機(jī)梯度下降算法。此外，由于輸入數(shù)據(jù)的模糊圖表示的規(guī)范化拉普拉斯是流形，我們可以使用規(guī)范化Laplacian的特征向量為隨機(jī)梯度下降提供合適的初始化。所需的優(yōu)化工作量將隨模糊圖中的邊數(shù)（假設(shè)為fxed負(fù)采樣率）而縮放，從而導(dǎo)致復(fù)雜性為O（kN）。
4.3 Hyper-parameters
算法一中含有四個(gè)超參數(shù)，
1、n表示逼近局部度量時(shí)要考慮的鄰域數(shù)目
2、d表示目標(biāo)嵌入維數(shù)
3、min-dist,嵌入空間中閉合點(diǎn)之間的期望間隔。
4、n-epochs，優(yōu)化低維表示時(shí)要使用的訓(xùn)練階段數(shù)。
在圖1中，我們提供了為玩具數(shù)據(jù)集（toy dataset）更改超參數(shù)的效果示例。這個(gè)數(shù)據(jù)是來(lái)自三維彩色立方體的均勻隨機(jī)樣本，通過(guò)使用相應(yīng)的RGB顏色，可以方便地顯示嵌入空間中的原始三維坐標(biāo)。由于數(shù)據(jù)是三維立方體，因此沒(méi)有局部流形結(jié)構(gòu)，因此對(duì)于此類數(shù)據(jù)，我們希望更大的n值更有用。n比較小時(shí)會(huì)將隨機(jī)采樣的噪聲解釋為fne尺度流形結(jié)構(gòu)，產(chǎn)生潛在的雜散結(jié)構(gòu)。
5 Practical Efficacy?
Pen digits：是一組1797個(gè)灰度數(shù)字圖像，使用數(shù)字輸入板輸入。每個(gè)圖像都是一個(gè)8x8圖像，我們將其視為一個(gè)64維向量，假設(shè)它在歐氏向量空間中。
COIL 20：是一組1440個(gè)灰度圖像，由20個(gè)對(duì)象組成，72個(gè)不同的旋轉(zhuǎn)范圍為360度。每個(gè)圖像是一個(gè)128x128圖像，我們將其作為一個(gè)16384維向量來(lái)計(jì)算圖像之間的距離。
COIL 100：是一組7200幅彩色圖像，由100個(gè)對(duì)象組成，在360度的72個(gè)不同旋轉(zhuǎn)。每個(gè)圖像由3個(gè)128x128強(qiáng)度矩陣組成（每個(gè)顏色通道一個(gè)）。為了計(jì)算圖像之間的距離，我們將其視為一個(gè)49152維向量。
Mouse scRNA-seq：提供了成年小鼠20921個(gè)細(xì)胞的基因表達(dá)數(shù)據(jù)。每個(gè)樣本由26774個(gè)測(cè)量向量組成
Statlog (Shuttle) ：是美國(guó)宇航局的一個(gè)數(shù)據(jù)集，包含與航天飛機(jī)中散熱器位置相關(guān)的各種數(shù)據(jù)，包括時(shí)間戳。Te數(shù)據(jù)集在9維特征空間中有58000個(gè)點(diǎn)。
MNIST：是一個(gè)28x28像素的手寫(xiě)數(shù)字灰度圖像集。Tere是10位數(shù)的類（0到9），總共有70000個(gè)圖像。Tis被視為70000個(gè)不同的784維向。
F-MNIST ：時(shí)尚MNIST是一個(gè)28x28像素的時(shí)尚物品（服裝、鞋類和箱包）灰度圖像的數(shù)據(jù)集。有10個(gè)類，共70000張圖片。與MNIST一樣，這被視為70000個(gè)不同的784維向量。
Flow cytometry：是一個(gè)流式細(xì)胞術(shù)測(cè)量CDT4細(xì)胞的數(shù)據(jù)集，由1000000個(gè)樣本組成，每個(gè)樣本有17個(gè)測(cè)量值。
GoogleNews word vectors ：是一個(gè)由300萬(wàn)個(gè)單詞和短語(yǔ)組成的數(shù)據(jù)集，這些單詞和短語(yǔ)來(lái)自Google新聞文檔的樣本，并通過(guò)word2vec嵌入到300維空間中
5.1多種算法的質(zhì)量比較
????t-SNE和LargeVis在數(shù)據(jù)定位和保存局部結(jié)構(gòu)方面都有顯著的改進(jìn)。通過(guò)比較它們的嵌入與Laplacian特征映射和PCA在2中生成的嵌入，可以定性地看到Tis。我們認(rèn)為，當(dāng)減小到二維或三維時(shí)，UMAP生產(chǎn)的埋件質(zhì)量與t-SNE相當(dāng)。例如，圖2顯示了COIL20、MNIST、Fashion、MNIST和Google News數(shù)據(jù)集的UMAP和t-SNE嵌入。當(dāng)精確的嵌入不同時(shí)，UMAP區(qū)分了與t-SNE和LargeVis相同的結(jié)構(gòu)。
????可以說(shuō)UMAP比t-SNE[4]捕獲了更多的數(shù)據(jù)集的全局和拓?fù)浣Y(jié)構(gòu)。COIL20數(shù)據(jù)集中的更多循環(huán)保持完整，包括交織的循環(huán)。類似地，MNIST digits數(shù)據(jù)集中不同數(shù)字之間的全局關(guān)系更清楚地被捕捉到，1（紅色）和0（深紅色）位于嵌入空間的遠(yuǎn)角，4,7,9（黃色、海綠和紫色）和3,5,8（橙色、綠色和藍(lán)色）被分離為不同的相似數(shù)字簇。在時(shí)尚MNIST數(shù)據(jù)集中，服裝（深紅色、黃色、橙色、朱紅色）和鞋類（黃綠色、海綠和紫色）之間的區(qū)別更加明顯。最后，當(dāng)t-SNE和UMAP都捕獲相似的詞向量組時(shí)，UMAP嵌入可以證明在不同的詞簇之間有更清晰的全局結(jié)構(gòu)。
5.2 Embedding Stability
圖2: 幾種降維算法的比較。我們注意到UMAP成功地反映了大量由拉普拉斯特征映射和主成分分析（尤其是MNIST和時(shí)尚MNIST）很好地表示的大規(guī)模全局結(jié)構(gòu)，同時(shí)也保留了類似于t-SNE和LargeVis的局部fne結(jié)構(gòu)。
? ? 為了比較UMAP、LargeVis和t-SNE（考慮的三維隨機(jī)降維技術(shù)）的次采樣下的穩(wěn)定性。從而度量嵌入的穩(wěn)定性，我們使用歸一化普洛克魯斯距離（Procustes distance：是兩個(gè)圖形或者兩個(gè)矩陣中地標(biāo)位置差異平方和的平方根。這可以用來(lái)描述許多地標(biāo)配置之間的差異）來(lái)度量?jī)蓚€(gè)潛在可比分布之間的距離。給定兩個(gè)數(shù)據(jù)集X={x1、、、xN}和Y={y1、、yN}，xi對(duì)應(yīng) yi。確定Y0={y10。，yN0}使平方誤差PNi=1(xi? yi）^2最小化的Y的最佳平移、均勻縮放和旋轉(zhuǎn)，定義為：
由于在嵌入空間中使用距離的任何度量都可能對(duì)嵌入的范圍或規(guī)模敏感，因此我們?cè)谟?jì)算Procrustes距離之前先將數(shù)據(jù)標(biāo)準(zhǔn)化，然后除以嵌入數(shù)據(jù)集的平均范數(shù)。在圖3中，我們可視化了對(duì)UMAP和t-SNE的子樣本嵌入使用Procrustes對(duì)齊的結(jié)果，演示了Procrustes距離如何測(cè)量嵌入的整體結(jié)構(gòu)的穩(wěn)定性。給定不同嵌入之間距離的度量，我們可以通過(guò)考慮子樣本嵌入與整個(gè)數(shù)據(jù)集嵌入的相應(yīng)子樣本之間的規(guī)范化Procrustes距離來(lái)檢查子采樣下的穩(wěn)定性。隨著子樣本大小的增加，子樣本嵌入點(diǎn)之間的平均每點(diǎn)距離應(yīng)減小，在重復(fù)運(yùn)行
下可能朝著最大一致性的某個(gè)漸近線移動(dòng)。理想情況下，該漸近值為零誤差，但對(duì)于隨機(jī)嵌入，如UMAP和t-SNE，這是不可能實(shí)現(xiàn)的。我們使用流式細(xì)胞儀數(shù)據(jù)集對(duì)算法的穩(wěn)定性進(jìn)行了經(jīng)驗(yàn)比較，因?yàn)樗哂休^大的尺寸、有趣的結(jié)構(gòu)和較低的環(huán)境維度（有助于t-SNE的運(yùn)行時(shí)性能）。我們注意到，對(duì)于這么大的數(shù)據(jù)集，我們發(fā)現(xiàn)有必要將t-SNE的默認(rèn)n_iter值從1000增加到1500，以確保更好的收斂性。
5.3 Computational Performance Comparisons
實(shí)驗(yàn)設(shè)備：
實(shí)世界數(shù)據(jù)集的基準(zhǔn)測(cè)試在Macbook Pro上執(zhí)行，Macbook Pro具有3.1 GHz的Intel Corei7和8GB的RAM（用于表1），在服務(wù)器上使用Intel XeonE5-2697v4處理器和512GB的RAM（用于5.3.1、5.3.2和5.3.3小節(jié)中的大規(guī)?；鶞?zhǔn)測(cè)試）。對(duì)于t-SNE，我們選擇了MulticoreTSNE[48]，我們認(rèn)為這是目前BarnesHut t-SNE最快的實(shí)現(xiàn)。
5.3.1 Scaling with Embedding Dimension，
UMAP的整合性能遠(yuǎn)比t-SNE高效，即使是非常小的嵌入維數(shù)為6或8(參見(jiàn)圖5)。這主要是由于UMAP不需要全局規(guī)范化的事實(shí)。它允許算法在不需要空間樹(shù)的情況下工作，例如t-SNE使用的四叉樹(shù)和oct樹(shù)[49]。這種空間樹(shù)在維數(shù)上呈指數(shù)級(jí)縮放，導(dǎo)致t-SNE相對(duì)于嵌入維數(shù)的縮放效果相對(duì)較差。
相比之下，我們發(fā)現(xiàn)UMAP在嵌入維度上具有很好的一致性，使得該算法在可視化之外的更廣泛應(yīng)用中具有實(shí)用性，T-SNE對(duì)于維度過(guò)高或者過(guò)低的處效果都不好。
5.3.2 Scaling with Ambient Dimension
通過(guò)結(jié)合本地連接性約束和近似近鄰搜索，UMAP甚至可以對(duì)非常高維的數(shù)據(jù)執(zhí)行有效的降維（關(guān)于直接在180萬(wàn)維數(shù)據(jù)上操作UMAP的示例，請(qǐng)參見(jiàn)圖9）。tis許多其他流形學(xué)習(xí)技術(shù)（包括t-SNE和LargeVis）形成對(duì)比，對(duì)于這些技術(shù)，通常建議在應(yīng)用這些技術(shù)之前使用PCA來(lái)減小維數(shù)（例如，參見(jiàn)[50]）。為了比較相對(duì)于數(shù)據(jù)的環(huán)境維度的運(yùn)行時(shí)性能縮放，我們選擇使用高維度的鼠標(biāo)scRNA數(shù)據(jù)集，但也可以使用PCA來(lái)減少數(shù)據(jù)30的維度，作為預(yù)處理步驟，而不會(huì)丟失太多重要結(jié)構(gòu)3。在圖6中，我們比較了UMAP、FItSNE、MulticoreTSNE和LargeVis在將小鼠scRNA數(shù)據(jù)集的PCA還原為不同維度上的性能，以及在原始數(shù)據(jù)集上的性能。
5.3.3 Scaling with the Number of Samples
對(duì)于數(shù)據(jù)集大小性能比較，我們選擇將UMAP與FItSNE進(jìn)行比較，F(xiàn)ItSNE[30]是t-SNE的一個(gè)版本，它使用近似近鄰搜索和傅立葉插值優(yōu)化方法；MulticoreTSNE[48]，我們認(rèn)為它是Barnes?Hut t t-SNE現(xiàn)存最快的實(shí)現(xiàn)；
UMAP允許生成任意大的、超高維的數(shù)據(jù)集，這些數(shù)據(jù)集仍然具有需要探索的有意義的結(jié)構(gòu)。在圖9和圖10中，我們顯示了從大約180萬(wàn)維的環(huán)境空間嵌入30000000個(gè)數(shù)據(jù)樣本。在一個(gè)大內(nèi)存SMP上，Tis計(jì)算大約需要2周。注意，盡管環(huán)境維度高，數(shù)據(jù)量大，UMAP仍然能夠fnd并顯示有趣的結(jié)構(gòu)。在圖11中，我們展示了嵌入的局部區(qū)域，展示了捕捉到的細(xì)節(jié)結(jié)構(gòu)。
6 Weaknesses
1、UMAP缺乏主成分分析（PCA）和非負(fù)矩陣分解（NMF）等相關(guān)技術(shù)的強(qiáng)大解釋能力（strong interpretability）。由于UMAP是基于觀測(cè)值之間的距離而不是源特征（ source features），因此它不具有PCA或因子分析等線性技術(shù)所能提供的等效因子載荷。如果很強(qiáng)的可解釋性是至關(guān)重要的，建議使用線性技術(shù)。
2、隨著采樣的數(shù)據(jù)越多，從噪聲中明顯可見(jiàn)的結(jié)構(gòu)數(shù)量將趨于減少，UMAP變得更加健壯，但是必須注意小樣本的噪聲數(shù)據(jù)，或僅具有大尺度流形結(jié)構(gòu)的數(shù)據(jù)（小噪聲的數(shù)據(jù)的噪音影響較大。
3、UMAP主要關(guān)注的是準(zhǔn)確地表示局部結(jié)構(gòu)。雖然我們相信UMAP可以捕獲比這些其他技術(shù)更多的全局結(jié)構(gòu)，但如果全局結(jié)構(gòu)是主要關(guān)注點(diǎn)，那么UMAP可能不是降維的最佳選擇。
4、為了提高算法的計(jì)算效率，進(jìn)行了一些近似計(jì)算（k近鄰算法，以及在優(yōu)化中使用負(fù)采樣，會(huì)導(dǎo)致次優(yōu)嵌入:suboptimal embeddings），對(duì)于小于500維的數(shù)據(jù)集將會(huì)產(chǎn)生影響.
7 Future Work
1、可以擴(kuò)展到支持（半監(jiān)督）降維和異構(gòu)數(shù)據(jù)集降維。每種數(shù)據(jù)類型（或監(jiān)督情況下的預(yù)測(cè)變量）可以被視為底層結(jié)構(gòu)的替代視圖，每種類型都有不同的關(guān)聯(lián)度量
2、每個(gè)視圖和度量都可以獨(dú)立地生成模糊簡(jiǎn)單集，然后將模糊簡(jiǎn)單集交叉在一起，創(chuàng)建一個(gè)用于嵌入的模糊簡(jiǎn)單集。
3、擴(kuò)展UMAP以處理混合數(shù)據(jù)類型將極大地增加它可以應(yīng)用到的數(shù)據(jù)集的范圍。用于（半監(jiān)督）降維的用例包括半監(jiān)督聚類和交互式標(biāo)記工具。為UMAP建立的Te計(jì)算框架允許潛在的技術(shù)發(fā)展，將新的不可見(jiàn)數(shù)據(jù)點(diǎn)添加到現(xiàn)有的嵌入中，并生成嵌入空間中任意點(diǎn)的高維表示。
4、將新樣本添加到現(xiàn)有嵌入將允許UMAP用作特征工程工具，作為集群或分類任務(wù)的通用機(jī)器學(xué)習(xí)管道的一部分。將點(diǎn)從嵌入的空間拉回到原始的高維空間，可以使UMAP用作生成模型，類似于自動(dòng)編碼器的一些用例。
5、在開(kāi)發(fā)技術(shù)以檢測(cè)和減輕潛在的虛假嵌入方面仍然有著重要的作用，特別是在小數(shù)據(jù)情況下。這種技術(shù)的加入將使UMAP作為探索性數(shù)據(jù)分析的工具變得更加健壯，這是為了可視化而減少到二維時(shí)的常見(jiàn)用例
8 Conclusions
UMAP降維算法明顯快于t-SNE算法，并且提供了更好的尺度。它允許我們生成比以前無(wú)法實(shí)現(xiàn)的更大數(shù)據(jù)集的高質(zhì)量嵌入。UMAP在各種科學(xué)領(lǐng)域的應(yīng)用和有效性證明了算法的強(qiáng)大性。
