tsne演算法

① 10X單細胞（10X空間轉錄組）降維分析之UMAP

UMAP ，全稱uniform manifold approximation and projection，統一流形逼近與投影，是基於黎曼幾何和代數拓撲的理論框架結構構建的。在處理大數據集時，UMAP優勢明顯，運行速度更快，內存佔用小。Etienne Becht等人2019年在Nature Biotechnology上發表一篇文章將其應用在生物學數據上並闡述了UMAP在處理單細胞數據方面的應用和優勢。

如果你不知道tSNE是什麼，它是如何工作的，也沒有讀過2008年的革命性的van der Maaten & Hinton原稿，可以參考我的那文章 10X單細胞（10X空間轉錄組）降維分析之tSNE（演算法基礎知識） 。盡管tSNE對一般的單細胞基因組學和數據科學產生了巨大的影響，但人們普遍認為它有一些缺點，這些缺點很快將得到解決。（ tSNE的缺點在上次分享的文章中也做過詳細的介紹 ）。

看看上面的圖，我想說的是 t分布應該提供全局距離信息，因為它們將高維空間中相距較遠的點推到低維空間中更遠的點。

然而，這種良好的意願被成本函數(KL-divergence)的選擇所扼殺，我們將在後面看到其原因。

(1),可以顯著降低計算時間高維圖像由於求和或集成是一個代價高昂的計算過程。想想馬爾可夫鏈蒙特卡羅(MCMC)它基本上是試圖近似地計算在貝葉斯規則的分母上的積分（UMAP使用最近鄰居的數量而不是perplexity）

(2)定義perplexity, UMAP則定義了沒有log2函數的最近鄰居k的個數，即:

UMAP使用稍微不同的高維概率對稱

symmterization是必要的因為UMAP融合在一起的點與本地不同的指標(通過參數ρ),它可能發生圖A和B節點之間的重量不等於B之間的權重和節點。為什麼UMAP使用這種對稱而不是tSNE使用的對稱還不清楚。我將在下一篇文章(從頭開始編寫UMAP)中展示我對不同的對稱化規則的實驗，這並沒有使我相信這是如此重要的一步，因為它對最終的低維嵌入式產生了很小的影響。
UMAP使用曲線族1 / (1+a*y^(2b))在低維中建模距離概率，不是完全的學生t分布，但非常非常相似，請注意再次沒有應用標准化:

其中，對於默認UMAP超參數a≈1.93,b≈0.79(實際上，對於min_dist = 0.001)。在實踐中，UMAP從非線性最小二乘擬合到帶有min_dist超參數的分段函數中找到a和b:

為了更好地理解曲線族1 / (1+a*y^(2b))的行為，讓我們畫出不同a和b的曲線:

我們可以看到曲線族對參數b非常敏感，在大的參數b處，在小的參數y處，曲線族形成了一種高峰。這意味著在UMAP超參數min_dist之下，所有的數據點都是同樣緊密相連的。由於Q(Y)函數的行為幾乎像一個Heaviside階躍函數，這意味著UMAP為所有在低維空間中相互靠近的點分配了幾乎相同的低維坐標。min_dist正是導致在UMAP維數降低圖中經常觀察到的超密集集群的原因。

為了演示如何准確地找到a和b參數，讓我們展示一個簡單的分段函數(其中高峰部分是通過min_dist參數定義的)，並使用函數族1 / (1+a y^(2b))通過優化來擬合它。curve_fit來自Scipy Python庫。作為擬合的結果，我們得到了函數1 / (1+a y^(2b))的初值a和初值b。

由於我們需要知道交叉熵的梯度，以便以後實現梯度下降，讓我們快速計算它。忽略只包含p(X)的常數項，我們可以將交叉熵重新寫一下，並將其微分如下:

圖拉普拉斯、譜聚類、拉普拉斯Eignemaps、擴散圖、譜嵌入等，實際上是指將矩陣分解和鄰接圖方法結合起來解決降維問題的同一種有趣的方法。在這種方法中，我們首先構造一個圖(或knn圖)，然後通過構造拉普拉斯矩陣用矩陣代數(鄰接矩陣和度矩陣)將其形式化，最後分解拉普拉斯矩陣，即求解特徵值分解問題。

我們可以使用scikit-learn Python庫，並使用spectralembedded函數在演示數據集(即與癌症相關的成纖維細胞(CAFs) scRNAseq數據)上輕松地顯示初始的低維坐標:

最後，UMAP使用隨機梯度下降(SGD)代替常規梯度下降(GD)，如tSNE / FItSNE，這既加快了計算速度，又減少了內存消耗。

現在讓我們簡要地討論一下為什麼他們說tSNE只保留數據的局部結構。可以從不同的角度來理解tSNE的局部性。首先,我們有σ參數Eq。(1)本地數據點集這樣互相「感覺」。因為成對歐幾里得距離衰減指數的概率,在小的σ值,它基本上是零遙遠的點(大型X)和快速增長僅為最近的鄰居(小X)。相比之下,在大的σ,遙遠而近點的概率成為限制可比和σ→∞,概率就等於1為所有任何一對點之間的距離,即成為等距點。

有趣的是,如果我們擴大成對歐幾里得距離的概率高維度成泰勒級數在σ→∞,我們會在第二近似冪律:

關於兩兩歐幾里得距離的冪律類似於多維定標法(MDS)的成本函數，MDS是通過保存每對點之間的距離來保存全局距離，而不管它們是相距很遠還是很近。一個可以解釋這個大的σtSNE遠程數據點之間的相互作用,所以是不完全正確的說tSNE只能處理當地的距離。然而，我們通常會受到perplexity有限值的限制，Laurens van der Maaten建議perplexity的取值范圍在5到50之間，盡管在局部信息和全局信息之間可能會有一個很好的折衷，那就是使用平方根≈N^(1/2)來選擇perplexity，其中N為樣本量。相反的極限,σ→0,我們最終的極端「局部性」高維概率的行為類似於狄拉克δ函數的行為。

另一種理解tSNE「局部性」的方法是考慮KL-divergence函數。假設X是高維空間中點之間的距離Y是低維空間中點之間的距離

根據kl -散度的定義：

方程(9)的第一項對於X的大小都是趨近於0的，對於X的大小也是趨近於0的，因為指數趨近於1，而log(1)=0。對於大X，這一項仍然趨近於0因為指數前因子趨近於0的速度快於對數趨近於負無窮。因此，為了直觀地理解kl散度，只考慮第二項就足夠了:

這是一個看起來很奇怪的函數，讓我們畫出KL(X, Y)

這個函數的形狀非常不對稱。如果點在高維度X之間的距離很小,指數因子變成1和對數項行為日誌(1 + Y ^ 2)這意味著如果Y是在低維空間的距離大,將會有一個大的懲罰,因此tSNE試圖減少Y在小X為了減少罰款。相反，對於高維空間中的長距離X, Y基本上可以是0到∞之間的任何值，因為指數項趨於0，並且總是勝過對數項。因此，在高維空間中相距遙遠的點，在低維空間中可能會相互靠近。因此，換句話說，tSNE並不能保證高維空間中相距較遠的點在低維空間中會保持較遠的距離。然而，它確實保證了在高維空間中相鄰的點在低維空間中保持相鄰。所以tSNE不是很擅長遠距離投射至低維,所以它只保留本地數據結構提供了σ不去∞。

與tSNE不同，UMAP使用交叉熵(CE)作為成本函數，而不是KL-divergence

這導致了地方-全球結構保護平衡的巨大變化。在X的小值處，我們得到了與tSNE相同的極限，因為第二項由於前因子和對數函數比多項式函數慢的事實而消失:

因此，為了使懲罰規則最小化，Y坐標必須非常小，即Y→0。這與tSNE的行為完全一樣。但是，在大X的相反極限，即X→∞時，第一項消失，第二項的前因子為1，得到:

這里，如果Y很小，我們會得到一個很大的懲罰，因為Y在對數的分母上，因此，我們鼓勵Y很大，這樣，對數下的比率就變成了1，我們得到零懲罰。因此，我們在X→∞處得到Y→∞，所以從高維空間到低維空間的整體距離保持不變，這正是我們想要的。為了說明這一點，讓我們繪制UMAP CE成本函數:

在這里，我們可以看到圖的「右」部分看起來與上面的kl散度曲面非常相似。這意味著在X低的時候，為了減少損失，我們仍然想要Y低。然而，當X很大時，Y的距離也要很大，因為如果它很小，CE (X, Y)的損失將是巨大的。記住，之前，對於KL (X, Y)曲面，在X很大的情況下，我們在高Y值和低Y值之間沒有差別，這就是為什麼CE (X, Y)代價函數能夠保持全局距離和局部距離。

我們知道UMAP是速度比tSNE擔憂)時大量的數據點,b)嵌入維數大於2或3,c)大量環境維度的數據集。在這里,讓我們試著了解UMAP要優於tSNE來自於數學和演算法實現。

tSNE和UMAP基本上都包含兩個步驟：

然而，我注意到UMAP的第一步比tSNE快得多。這有兩個原因：

接下來，UMAP實際上在第二步中也變得更快了。這種改善也有幾個原因:

在這篇文章中，我們了解到盡管tSNE多年來一直服務於單細胞研究領域，但它有太多的缺點，如速度快、缺乏全球距離保存。UMAP總體上遵循了tSNE的哲學，但是引入了一些改進，例如另一個成本函數和缺少高維和低維概率的標准化。

除了運行速度快，內存佔用小等特點，UMAP在處理細胞學數據時還有一個大的優勢，就是可以反映細胞群體之間分化的連續性和組織性。下面將通過文獻中的數據【2】來為大家詳細講解。

對同一組數據分別進行tSNE和UMAP降維，該數據為多達30萬個從8種不同組織富集得到的T細胞和NK細胞的樣本，並使用Phenograph聚類把細胞分為6大類，每種顏色代表一種細胞。從圖中可以看出，UMAP和tSNE都可以較好地把不同類別的細胞分開。但tSNE傾向於把相同細胞群劃分為更多的群，如圖顯示，黑色圈中CD8 T細胞，在tSNE結果中，群數更多，距離更遠。

同樣這組數據用組織來源對UMAP和t-SNE圖上細胞的進行顏色區分，可以觀察到一個有意思的現象。與UMAP相比，t-SNE更加傾向於根據它們的來源來分離總體細胞。而 UMAP則會兼顧細胞群的類別和來源來排列，如圖中在CD4 T細胞和CD8 T細胞群內，細胞的排列與來源也會有一定的規律性，都是大致從臍帶血（CB）和外周血單核細胞（PBMC），到肝臟（Liver）和脾臟（Spleen），最後到一端的扁桃或另一端的皮膚（Skin）、腸道（Gut）和肺（Lung）。

通過駐留記憶T細胞標志物CD69/CD103、記憶T細胞標志物CD45 RO和naïve T細胞標志物CCR7表達群的分布，可以觀察到UMAP可以展示出T細胞連續的分化階段。而tSNE結果中，這些群之間也是連續的，但是卻沒有非常明顯的沿軸結構。同樣的現象也在造血細胞系統中被觀察到。由此可見， UMAP在大數據集的處理時可以展現細胞集群的連續性。

對三組數據（Samusik、Wong、Han_400k）分別進行數據隨機降低至100-200,000之間不同的數量級，形成小數據集。縱軸為小數據集與原始數據集的相關性，代表降維方法在不同數據量上的可重復性。UMAP表現最好，數據集越大，優勢越明顯。

下圖是UMAP和t-SNE對一套784維Fashion MNIST高維數據集降維到3維的效果的比較。

雖然這兩種演算法都表現出強大的局部聚類並將相似的類別分組在一起，但UMAP還將這些相似類別的分組彼此分開。另外，UMAP降維用了4分鍾，而多核t-SNE用了27分鍾。

UMAP的兩個最常用的參數：n_neighbors 和 min_dist，它們可有效地用於控制最終結果中局部結構和全局結構之間的平衡。

最重要的參數是 n_neighbors ，近似最近鄰居數。它有效地控制了UMAP局部結構與全局結構的平衡，數據較小時，UMAP會更加關注局部結構，數據較大時，UMAP會趨向於代表大圖結構，丟掉一些細節。

第二個參數是 min_dist，點之間的最小距離。此參數控制UMAP聚集在一起的緊密程度，數據較小時，會更緊密。較大的值會更鬆散，而將重點放在保留廣泛的拓撲結構上。

t-SNE和UMAP大部分的表現非常相似，但以下示例明顯例外：寬而稀疏的cluster中有密集的cluster(如下圖所示)。UMAP無法分離兩個嵌套的群集，尤其是在維數較高時。

UMAP在初始圖形構造中局部距離的使用可以解釋該演算法無法處理情況的原因。由於高維點之間的距離趨於非常相似(維數的詛咒)，所以可能會因此將其混合在一起。

演算法很難，所以懂的人才顯得牛

天行健，君子以自強不息

② 對數據科學家來說最重要的演算法和統計模型

對數據科學家來說最重要的演算法和統計模型
作為一個在這個行業已經好幾年的數據科學家，在LinkedIn和QuoLa上，我經常接觸一些學生或者想轉行的人，幫助他們進行機器學習的職業建議或指導方面相關的課程選擇。一些問題圍繞教育途徑和程序的選擇，但許多問題的焦點是今天在數據科學領域什麼樣的演算法或模型是常見的。
由於可供選擇的演算法太多了，很難知道從哪裡開始學起。課程可能包括在當今工業中使用的不是很典型的演算法，而課程可能沒有包含目前不是很流行的但特別有用的方法。基於軟體的程序可以排除重要的統計概念，並且基於數學的程序可以跳過演算法設計中的一些關鍵主題。

我為一些有追求的數據專家整理了一個簡短的指南，特別是關注統計模型和機器學習模型(有監督學習和無監督學習);這些主題包括教科書、畢業生水平的統計學課程、數據科學訓練營和其它培訓資源。(其中有些包含在文章的參考部分)。由於機器學習是統計學的一個分支，機器學習演算法在技術上歸類於統計學知識，還有數據挖掘和更多的基於計算機科學的方法。然而，由於一些演算法與計算機科學課程的內容相重疊，並且因為許多人把傳統的統計方法從新方法中分離出來，所以我將把列表中的兩個分支也分開了。

統計學的方法包括在bootcamps和證書程序中概述的一些更常見的方法，還有一些通常在研究生統計學程序中所教授的不太常見的方法(但在實踐中可以有很大的優勢)。所有建議的工具都是我經常使用的工具:
1)廣義線性模型，它構成了大多數監督機器學習方法的基礎(包括邏輯回歸和Tweedie回歸，它概括了在工業中遇到的大多數計數或連續結果……)
2) 時間序列方法(ARIMA, SSA, 基於機器學習的方法)
3) 結構方程建模 (模擬和測試介導途徑)
4) 因子分析法(調查設計與驗證的探索和驗證)
5) 功率分析/試驗設計 (特別是基於模擬的試驗設計，以免分析過度)
6) 非參數檢驗(從零開始的推導, 尤其通過模擬)/MCMC
7) K均值聚類
8) 貝葉斯方法(Na?ve Bayes, 貝葉斯模型求平均值, 貝葉斯自適應試驗...)
9) 懲罰回歸模型 (elastic net, LASSO, LARS...) ，通常給模型增加懲罰因素(SVM, XGBoost...), 這對於預測值超過觀測值的數據集是有用的(常見於基因組學與社會科學研究)
10) 樣條模型(MARS...) 用於靈活性建模過程
11)馬爾可夫鏈和隨機過程 (時間序列建模與預測建模的另一種方法)
12)缺失數據填補方案及其假設(missForest, MICE...)
13) 生存分析(非常有助於製造建模和消耗過程)
14) 混合建模
15) 統計推斷與分組測試(A/B測試和在許多交易活動中實施更復雜的設計)
機器學習擴展了許多這樣框架，特別是K均值聚類和廣義線性建模。在許多行業中一些有用的常見技術(還有一些更模糊的演算法，在bootcamps或證書程序中出人意料的有用，但學校里很少教) 包括:
1)回歸/分類樹(用於高精度、可解釋性好、計算費用低的廣義線性模型的早期推廣)
2)維數約簡(PCA和多樣學習方法如MDS和tSNE)
3)經典前饋神經網路
4)裝袋組合(構成了隨機森林和KNN回歸整合等演算法的基礎)
7)加速整合(這是梯度提升和XGBoost演算法的基礎)
8)參數優化或設計項目的優化演算法(遺傳演算法，量子啟發進化演算法，模擬鍛煉，粒子群優化)
9)拓撲數據分析工具，特別適合於小樣本大小的無監督學習(持久同調, Morse-Smale聚類, Mapper...)
10)深度學習架構(一般的深度架構)
11) KNN局部建模方法(回歸, 分類)
12)基於梯度的優化方法
13)網路度量與演算法(中央度量法、中間性、多樣性、熵、拉普拉斯運算元、流行病擴散、譜聚類)
14)深度體系架構中的卷積和匯聚層(專門適用於計算機視覺和圖像分類模型)
15)層次聚類 (聚類和拓撲數據分析工具相關)
16)貝葉斯網路(路徑挖掘)
17)復雜性與動態系統(與微分方程有關，但通常用於模擬沒有已知驅動程序的系統)
依靠所選擇的行業，可能需要與自然語言處理(NLP)或計算機視覺相關的附加演算法。然而，這些是數據科學和機器學習的專門領域，進入這些領域的人通常已經是那個特定領域的專家。

③ 聚類演算法數據分析

提到聚類演算法，K-Means算是略懂數據分析的人都知道的一種。但K-Means也有其局限性，基本只能處理數值型聚類。而且按距離進行聚類而非密度，無法處理環形圖樣。實際在使用聚類演算法時，還有很多技巧性問題。

聚類演算法需要各變數間相關性較低，可以採用DataFrame的corr()函數進行相關性計算。另外，聚類的變數要區分離散值和非離散值。對於非離散變數，需要進行標准化或歸一化；對於離散變數，可以轉換為虛擬變數，並採用{0, 1}編碼。建議採用min-max標准化，這樣和虛擬變數保持相同的相同范圍。

對於包含非離散變數和虛擬變數的數據集（通常情況），建議採用K-Prototype而非K-Means演算法進行聚類。在使用時可以標記相關虛擬變數，確保區別處理（實際虛擬變數採用K-Modes，非離散變數採用K-Means，再基於權重a進行結果合並）。

KPrototypes(n_clusters=np).fit(df.values, categorical=[1, 2])

其中的1, 2代表df數據集中的第1, 2列（從0計數）。評估聚類演算法可以基於輪廓系數，對比不同的K值，在業務允許范圍內得到最佳K值。建議的輪廓系數函數是silhouette_score，其最大值為1，越接近1越好，可以在不同演算法情況下進行相對比較。

除輪廓系數外，還可以降維繪制散點圖（通過TSNE降維），按聚類演算法分類對散點進行著色，進而直觀的進行聚類演算法分類結果的判斷。

TSNE(n_components=2)

總結來說，整個聚類演算法數據分析的操作步驟如下：

1. 構建低相關性變數數據集（通過給高相關性變數設置固定值）；

2. 對非離散變數進行min-max歸一化操作；

3. 對包含虛擬變數的數據集採用K-Prototype聚類演算法，對只包含非離散變數的數據集採用K-Means演算法；

4. 通過輪廓系數silhouette_score對K值進行循環測試，得到最佳K值；

5. 通過TSNE將數據集降維為兩維顯著特徵值，並通過散點圖，配合聚類演算法分類結果配色對聚類演算法分類結果進行合理判斷；

6. 對聚類演算法分類結果，結合業務邏輯進行解釋，確保分類結果支撐業務分析。