2.2. 流形學習#
流形學習是一種非線性降維的方法。此任務的演算法基於以下觀念：許多資料集的維度只是人為地設定較高。
2.2.1. 簡介#
高維資料集可能難以視覺化。雖然可以繪製二維或三維資料以顯示資料的固有結構，但等效的高維圖形則較不直觀。為了協助視覺化資料集的結構，必須以某種方式縮減維度。
達成此降維的最簡單方法是採用資料的隨機投影。儘管這允許某種程度的資料結構視覺化，但選擇的隨機性仍有許多不足之處。在隨機投影中，資料中較有趣的結構很可能會遺失。
為了處理這個問題，已設計出許多監督式和無監督式線性降維架構，例如主成分分析 (PCA)、獨立成分分析、線性判別分析和其他。這些演算法定義了特定的規則，以選擇資料的「有趣」線性投影。這些方法可能很強大，但往往會遺漏資料中重要的非線性結構。
流形學習可以被視為嘗試將線性架構（如 PCA）推廣為對資料中的非線性結構敏感。儘管存在監督式變體，但典型的流形學習問題是無監督式的：它從資料本身學習資料的高維結構，而無需使用預定的分類。
範例
請參閱 手寫數字的流形學習：局部線性嵌入、Isomap…，以瞭解手寫數字降維的範例。
請參閱 流形學習方法比較，以瞭解玩具「S 曲線」資料集降維的範例。
請參閱 視覺化股票市場結構，以瞭解如何使用流形學習根據歷史股價繪製股票市場結構圖。
以下概述 scikit-learn 中可用的流形學習實作
2.2.2. Isomap#
Isomap 演算法是流形學習最早的方法之一，是 Isometric Mapping 的縮寫。Isomap 可以視為多維度縮放 (MDS) 或核 PCA 的延伸。Isomap 尋求維持所有點之間測地距離的較低維度嵌入。可以使用物件 Isomap 執行 Isomap。
複雜度#
Isomap 演算法包含三個階段
最近鄰搜尋。 Isomap 使用
BallTree進行有效率的鄰近搜尋。成本約為 \(O[D \log(k) N \log(N)]\)，對於 \(D\) 維空間中 \(N\) 個點的 \(k\) 個最近鄰點。最短路徑圖搜尋。 此最有效率的已知演算法是Dijkstra 演算法，約為 \(O[N^2(k + \log(N))]\)，或是 Floyd-Warshall 演算法，約為 \(O[N^3]\)。使用者可以使用
Isomap的path_method關鍵字來選取演算法。如果未指定，程式碼會嘗試為輸入資料選擇最佳演算法。部分特徵值分解。 嵌入編碼在 \(N \times N\) Isomap 核的 \(d\) 個最大特徵值對應的特徵向量中。對於密集求解器，成本約為 \(O[d N^2]\)。使用
ARPACK求解器通常可以改善此成本。使用者可以使用Isomap的eigen_solver關鍵字來指定特徵值求解器。如果未指定，程式碼會嘗試為輸入資料選擇最佳演算法。
Isomap 的整體複雜度為 \(O[D \log(k) N \log(N)] + O[N^2(k + \log(N))] + O[d N^2]\)。
\(N\)：訓練資料點的數量
\(D\)：輸入維度
\(k\)：最近鄰點的數量
\(d\)：輸出維度
參考文獻
「非線性降維的整體幾何架構」Tenenbaum, J.B.; De Silva, V.; & Langford, J.C. Science 290 (5500)
2.2.3. 局部線性嵌入#
局部線性嵌入 (LLE) 尋求資料的較低維度投影，以保留局部鄰域內的距離。它可以被視為一系列局部主成分分析，這些分析會進行全域比較以找出最佳的非線性嵌入。
可以使用函式 locally_linear_embedding 或其物件導向的對應項目 LocallyLinearEmbedding 來執行局部線性嵌入。
複雜度#
標準 LLE 演算法包含三個階段
最近鄰搜尋。請參閱上文 Isomap 下的討論。
權重矩陣建構。 \(O[D N k^3]\)。LLE 權重矩陣的建構涉及對每個 \(N\) 個局部鄰域求解一個 \(k \times k\) 的線性方程式。
部分特徵值分解。請參閱上面 Isomap 的討論。
標準 LLE 的總體複雜度為 \(O[D \log(k) N \log(N)] + O[D N k^3] + O[d N^2]\)。
\(N\)：訓練資料點的數量
\(D\)：輸入維度
\(k\)：最近鄰點的數量
\(d\)：輸出維度
參考文獻
“局部線性嵌入的非線性降維” Roweis, S. & Saul, L. Science 290:2323 (2000)
2.2.4. 修改後的局部線性嵌入#
LLE 的一個眾所周知的問題是正規化問題。當鄰居數量大於輸入維度數量時，定義每個局部鄰域的矩陣是秩虧的。為了處理這個問題，標準 LLE 應用了一個任意的正規化參數 \(r\)，該參數是相對於局部權重矩陣的跡來選擇的。儘管可以正式證明當 \(r \to 0\) 時，解會收斂到期望的嵌入，但不能保證對於 \(r > 0\) 會找到最佳解。這個問題會體現在扭曲流形底層幾何結構的嵌入中。
解決正規化問題的一種方法是在每個鄰域中使用多個權重向量。這是修改後的局部線性嵌入 (MLLE) 的本質。可以使用函數 locally_linear_embedding 或其物件導向的對應物 LocallyLinearEmbedding 執行 MLLE，關鍵字為 method = 'modified'。它需要 n_neighbors > n_components。
複雜度#
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：使用多個權重的修改後局部線性嵌入” Zhang, Z. & Wang, J.
2.2.5. 黑塞特徵映射#
黑塞特徵映射（也稱為基於黑塞的 LLE：HLLE）是解決 LLE 正規化問題的另一種方法。它圍繞每個鄰域的基於黑塞的二次形式，用於恢復局部線性結構。儘管其他實現方式指出它在資料大小上的縮放效果不佳，但 sklearn 實施了一些演算法上的改進，使其成本與其他小輸出維度的 LLE 變體相當。可以使用函數 locally_linear_embedding 或其物件導向的對應物 LocallyLinearEmbedding 執行 HLLE，關鍵字為 method = 'hessian'。它需要 n_neighbors > n_components * (n_components + 3) / 2。
複雜度#
HLLE 演算法包含三個階段
最近鄰搜尋。與標準 LLE 相同
權重矩陣建構。約為 \(O[D N k^3] + O[N d^6]\)。第一項反映了與標準 LLE 相似的成本。第二項來自局部黑塞估計量的 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\)：輸出維度
參考文獻
“黑塞特徵映射：用於高維數據的局部線性嵌入技術” Donoho, D. & Grimes, C. Proc Natl Acad Sci USA. 100:5591 (2003)
2.2.6. 譜嵌入#
譜嵌入是一種計算非線性嵌入的方法。Scikit-learn 實施了拉普拉斯特徵映射，它使用圖拉普拉斯的譜分解找到數據的低維表示。生成的圖可以被認為是高維空間中低維流形的離散近似。基於圖的成本函數的最小化確保了流形上彼此靠近的點在低維空間中映射為彼此靠近，從而保留局部距離。可以使用函數 spectral_embedding 或其物件導向的對應物 SpectralEmbedding 執行譜嵌入。
複雜度#
譜嵌入（拉普拉斯特徵映射）演算法包含三個階段
加權圖建構。使用親和力（鄰接）矩陣表示將原始輸入數據轉換為圖表示。
圖拉普拉斯建構。非正規化的圖拉普拉斯構造為 \(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\)：輸出維度
參考文獻
“用於降維和數據表示的拉普拉斯特徵映射” M. Belkin, P. Niyogi, 神经计算，2003 年 6 月；15 (6):1373-1396
2.2.7. 局部切線空間對齊#
雖然在技術上不是 LLE 的變體，但局部切線空間對齊 (LTSA) 在演算法上與 LLE 非常相似，可以歸入此類。LTSA 並非像 LLE 那樣側重於保留鄰域距離，而是試圖透過其切線空間來描述每個鄰域的局部幾何結構，並執行全局優化以對齊這些局部切線空間，從而學習嵌入。可以使用函數 locally_linear_embedding 或其物件導向的對應物 LocallyLinearEmbedding 執行 LTSA，關鍵字為 method = 'ltsa'。
複雜度#
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\)：輸出維度
參考文獻
“透過切線空間對齊的主流形和非線性降維” Zhang, Z. & Zha, H. Journal of Shanghai Univ. 8:406 (2004)
2.2.8. 多維尺度分析 (MDS)#
多維尺度分析 (MDS) 尋求數據的低維表示，其中距離能很好地尊重原始高維空間中的距離。
一般來說，MDS 是一種用於分析相似性或相異性資料的技術。它試圖將相似性或相異性資料建模為幾何空間中的距離。這些資料可以是物件之間的相似性評分、分子之間的交互頻率，或是國家之間的貿易指數。
MDS 演算法有兩種：度量式 (metric) 和非度量式 (non-metric)。在 scikit-learn 中，MDS 類別同時實作了這兩種演算法。在度量式 MDS 中，輸入的相似性矩陣來自於一個度量（因此符合三角不等式），輸出兩點之間的距離會被設定成盡可能接近相似性或相異性資料。在非度量版本中，演算法會試圖保留距離的順序，並因此尋求嵌入空間中的距離與相似性/相異性之間的單調關係。
令 \(S\) 為相似性矩陣，而 \(X\) 為 \(n\) 個輸入點的座標。差異值 \(\hat{d}_{ij}\) 是以某種最佳方式選擇的相似性轉換。目標（稱為應力 (stress)）然後定義為 \(\sum_{i < j} d_{ij}(X) - \hat{d}_{ij}(X)\)。
度量式 MDS#
最簡單的度量式 MDS 模型，稱為絕對 MDS，其差異值定義為 \(\hat{d}_{ij} = S_{ij}\)。使用絕對 MDS，值 \(S_{ij}\) 應該完全對應到嵌入點中點 \(i\) 和 \(j\) 之間的距離。
最常見的情況下，差異值設定為 \(\hat{d}_{ij} = b S_{ij}\)。
非度量式 MDS#
非度量式 MDS 著重於資料的排序。如果 \(S_{ij} > S_{jk}\)，那麼嵌入應該強制執行 \(d_{ij} < d_{jk}\)。基於這個原因，我們用相異性 (\(\delta_{ij}\)) 而非相似性 (\(S_{ij}\)) 來討論它。請注意，相異性可以透過簡單的轉換從相似性輕鬆獲得，例如對於某些實數常數 \(c_1, c_2\)，\(\delta_{ij}=c_1-c_2 S_{ij}\)。強制正確排序的一種簡單演算法是對 \(\delta_{ij}\) 上的 \(d_{ij}\) 使用單調迴歸，產生與 \(\delta_{ij}\) 順序相同的差異值 \(\hat{d}_{ij}\)。
這個問題的一個簡單解法是將所有點都設定在原點。為了避免這種情況，差異值 \(\hat{d}_{ij}\) 會被正規化。請注意，由於我們只關心相對排序，我們的目標應該對簡單的平移和縮放保持不變，但是度量式 MDS 中使用的應力對縮放很敏感。為了處理這個問題，非度量式 MDS 可以使用正規化的應力，稱為 Stress-1，其定義如下
可以透過設定 normalized_stress=True 來啟用正規化的 Stress-1，但它只與非度量式 MDS 問題相容，並且在度量式情況下會被忽略。
參考文獻
《現代多維尺度分析 - 理論與應用》 Borg, I.; Groenen P. Springer Series in Statistics (1997)
「非度量多維尺度分析：一種數值方法」 Kruskal, J. Psychometrika, 29 (1964)
「透過最佳化對非度量假設的擬合優度進行多維尺度分析」 Kruskal, J. Psychometrika, 29, (1964)
2.2.9. t 分佈隨機鄰近嵌入 (t-SNE)#
t-SNE (TSNE) 將資料點的親和力轉換為機率。原始空間中的親和力由高斯聯合機率表示，而嵌入空間中的親和力由學生 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'）來緩解。
最佳化 t-SNE#
t-SNE 的主要目的是視覺化高維資料。因此，當資料嵌入到二維或三維時，效果最佳。
最佳化 KL 散度有時可能會有點棘手。有五個參數控制 t-SNE 的最佳化，因此也可能影響最終嵌入的品質
困惑度 (perplexity)
早期誇大因子 (early exaggeration factor)
學習率 (learning rate)
最大迭代次數 (maximum number of iterations)
角度 (angle)（未在精確方法中使用）
困惑度定義為 \(k=2^{(S)}\)，其中 \(S\) 是條件機率分佈的香農熵。一個 \(k\) 面骰子的困惑度是 \(k\)，因此 \(k\) 實際上是 t-SNE 在產生條件機率時考慮的最近鄰居數量。較大的困惑度會導致更多的最近鄰居，並且對小型結構不太敏感。相反地，較低的困惑度會考慮較少的鄰居數量，因此會忽略更多整體資訊，而偏好局部鄰域。隨著資料集大小的增加，將需要更多的點來取得局部鄰域的合理樣本，因此可能需要較大的困惑度。同樣地，較嘈雜的資料集將需要較大的困惑度值，以涵蓋足夠的局部鄰居，才能看到背景雜訊之外的資訊。
最大迭代次數通常足夠高，不需要任何調整。最佳化包含兩個階段：早期誇大階段和最終最佳化。在早期誇大期間，原始空間中的聯合機率將通過乘以給定的因子而被人工地增加。較大的因子會導致資料中自然叢集之間的間隙更大。如果該因子太高，KL 散度可能會在此階段增加。通常它不需要調整。一個關鍵參數是學習率。如果它太低，梯度下降將會停留在不好的局部最小值中。如果它太高，KL 散度將會在最佳化期間增加。Belkina 等人 (2019) 提出的啟發式方法是將學習率設定為樣本大小除以早期誇大因子。我們將此啟發式方法實作為 learning_rate='auto' 參數。更多提示可以在 Laurens van der Maaten 的常見問題解答 (FAQ) 中找到（請參閱參考資料）。最後一個參數角度是效能和準確性之間的權衡。較大的角度表示我們可以將較大的區域近似為單個點，從而獲得更好的速度但較不準確的結果。
「如何有效地使用 t-SNE」提供了對各種參數的影響的良好討論，以及用於探索不同參數影響的互動式圖表。
Barnes-Hut t-SNE#
此處實作的 Barnes-Hut t-SNE 通常比其他流形學習演算法慢得多。最佳化相當困難，而梯度的計算複雜度為 \(O[d N log(N)]\)，其中 \(d\) 是輸出維度數量，\(N\) 是樣本數量。Barnes-Hut 方法改進了 t-SNE 複雜度為 \(O[d N^2]\) 的精確方法，但還有其他幾個顯著差異。
Barnes-Hut 實作僅在目標維度為 3 或更小時才有效。2D 情況在建立視覺化時很常見。
Barnes-Hut 僅適用於密集輸入資料。稀疏資料矩陣只能使用精確方法嵌入，或者可以透過密集低秩投影來近似，例如使用
PCA。Barnes-Hut 是精確方法的近似。此近似值使用角度參數進行參數化，因此當 method=”exact” 時，角度參數不會被使用。
Barnes-Hut 的可擴展性明顯更高。Barnes-Hut 可用於嵌入數十萬個資料點，而精確方法在達到計算上的難以處理之前，只能處理數千個樣本。
為了視覺化目的（這是 t-SNE 的主要用例），強烈建議使用 Barnes-Hut 方法。精確的 t-SNE 方法適用於檢查嵌入的理論特性，可能在高維空間中，但由於計算上的限制，僅限於小型資料集。
另請注意，數字標籤大致符合 t-SNE 找到的自然分組，而 PCA 模型的線性 2D 投影產生的表示，其標籤區域則大多重疊。這強烈暗示此數據可以透過專注於局部結構的非線性方法（例如，具有高斯 RBF 核心的 SVM）很好地分離。然而，在 2D 中使用 t-SNE 無法很好地視覺化分離均質標記的群組，並不一定意味著數據無法透過監督模型正確分類。可能是 2 個維度不足以準確表示數據的內部結構。
參考文獻
“使用 t-SNE 可視化高維數據” van der Maaten, L.J.P.; Hinton, G. Journal of Machine Learning Research (2008)
“t-分佈隨機鄰居嵌入” van der Maaten, L.J.P.
“使用基於樹的演算法加速 t-SNE” van der Maaten, L.J.P.; Journal of Machine Learning Research 15(Oct):3221-3245, 2014。
“用於 T 分佈隨機鄰居嵌入的自動優化參數，改善大型數據集的可視化和分析” Belkina, A.C., Ciccolella, C.O., Anno, R., Halpert, R., Spidlen, J., Snyder-Cappione, J.E., Nature Communications 10, 5415 (2019)。
2.2.10. 實用技巧#
請確保所有特徵都使用相同的尺度。由於流形學習方法基於最近鄰搜尋，否則演算法可能會表現不佳。請參閱 StandardScaler 以了解方便縮放異質數據的方法。
每個常式計算的重建誤差可用於選擇最佳輸出維度。對於嵌入在 \(D\) 維參數空間中的 \(d\) 維流形，當
n_components增加時，重建誤差將會減少，直到n_components == d。請注意，雜訊數據可能會「短路」流形，本質上充當流形各部分之間的橋樑，這些部分否則會很好地分離。在雜訊和/或不完整數據上進行流形學習是一個活躍的研究領域。
某些輸入配置可能導致奇異權重矩陣，例如當數據集中有兩個以上的點相同時，或者當數據被分成不相交的群組時。在這種情況下，
solver='arpack'將無法找到零空間。解決這個問題最簡單的方法是使用solver='dense'，它可以在奇異矩陣上工作，儘管根據輸入點的數量，它可能會非常慢。或者，可以嘗試了解奇異性的來源：如果是由於不相交的集合，增加n_neighbors可能會有幫助。如果是由於數據集中存在相同的點，刪除這些點可能會有所幫助。
另請參閱
完全隨機樹嵌入 也可用於推導特徵空間的非線性表示，它也不執行降維。