scikit-learn 流形學(xué)習(xí)

? Look for the bare necessities

? The simple bare necessities

? Forget about your worries and your strife

? I mean the bare necessities

? Old Mother Nature’s recipes

? That bring the bare necessities of life

? – Baloo’s song [The Jungle Book]

流形學(xué)習(xí)是一種非線性降維方法。這一任務(wù)的算法基于這樣的思想:許多數(shù)據(jù)集的維數(shù)過高是人為的。

2.2.1. 介紹

高維數(shù)據(jù)集很難可視化。雖然可以繪制二維或三維數(shù)據(jù)來顯示數(shù)據(jù)的固有結(jié)構(gòu)，但是等價的高維圖就不那么直觀了。為了改善可視化數(shù)據(jù)集的結(jié)構(gòu)，必須以某種方式減少維數(shù)。

完成這種降維最簡單的方法是對數(shù)據(jù)進行隨機投影。雖然這允許在一定程度上可視化數(shù)據(jù)結(jié)構(gòu)，但是選擇隨機性的方式還有很多需要改進的地方。在隨機投影中，數(shù)據(jù)中更有趣的結(jié)構(gòu)可能會丟失。

為了解決這個問題，設(shè)計了一些有監(jiān)督和無監(jiān)督的線性降維框架，如主成分分析(PCA)、獨立成分分析、線性判別分析等。這些算法定義了特定的規(guī)則來選擇數(shù)據(jù)的“有趣的”線性投影。這些方法可能非常強大，但是常常會忽略數(shù)據(jù)中重要的非線性結(jié)構(gòu)。

流形學(xué)習(xí)可以被認為是一種把線性框架（如主成分分析）推廣到數(shù)據(jù)中敏感的非線性結(jié)構(gòu)的嘗試。雖然有監(jiān)督變量存在，但典型的流形學(xué)習(xí)問題是無監(jiān)督的:它從數(shù)據(jù)本身學(xué)習(xí)數(shù)據(jù)的高維結(jié)構(gòu)，而不使用預(yù)先確定的分類。

示例：

• 參見 手寫數(shù)字上的流形學(xué)習(xí)：局部線性嵌入，Isomap… ,手寫數(shù)字降維的示例。
• 參見 流形學(xué)習(xí)方法的比較 ,有關(guān)玩具 “S-曲線” 數(shù)據(jù)集降維的示例。

scikit-learn中提供的多種學(xué)習(xí)實現(xiàn)總結(jié)如下

2.2.2. Isomap

Isomap算法是最早的流形學(xué)習(xí)方法之一，它是等距映射的縮寫。Isomap可以看作是多維尺度分析(MDS)或核主成分分析的擴展。Isomap尋求一種更低維度的嵌入，以保持所有點之間的測地線距離（geodesic distances）。Isomap可以通過Isomap 對象來執(zhí)行。

2.2.2.1. 復(fù)雜度

Isomap 算法包括三個階段:

1. **最近鄰搜索.**Isomap使用 sklearn.neighbors.BallTree 高效的進行近鄰搜索。對于維度中個點的個最近鄰，其代價近似為 。
2. 最短路徑圖搜索. 這方面算法中已知最有效的算法是 Dijkstra 算法或 Floyd-Warshall 算法，復(fù)雜度分別是約 和 。 用戶可通過使用 isomap 的 path_method 關(guān)鍵字來選擇算法。 如果未指定，代碼會嘗試為輸入數(shù)據(jù)選擇最佳算法。
3. **部分特征值分解.**嵌入編碼在對應(yīng)的xisomap核的個最大特征值的特征向量中。對于一個密集求解器，代價大約是。這個代價通?？梢酝ㄟ^ARPACK求解器來提高。用戶可以使用Isomap的path_method關(guān)鍵字指定特征求解器。如果未指定，代碼將嘗試為輸入數(shù)據(jù)選擇最佳算法。

Isomap的總體復(fù)雜度是

• : 訓(xùn)練數(shù)據(jù)點個數(shù)

• : 輸入維度

• : 最近鄰個數(shù)

• : 輸出維度

  參考資料:

  “A global geometric framework for nonlinear dimensionality reduction” Tenenbaum, J.B.; De Silva, V.; & Langford, J.C. Science 290 (5500)

2.2.3. 局部線性嵌入

局部線性嵌入（LLE）通過保留局部鄰域內(nèi)的距離來尋求數(shù)據(jù)的低維投影。 它可以被認為是一系列的局部主成分分析在全局范圍內(nèi)的相互比較，找到最優(yōu)的局部非線性嵌入。

局部線性嵌入可以通過 locally_linear_embedding 函數(shù)或其面向?qū)ο蟮牡刃Х椒?LocallyLinearEmbedding 來實現(xiàn)。

2.2.3.1. 復(fù)雜度

標準的 LLE 算法包括三個階段:

1. 最鄰近搜索. 參見上述 Isomap 討論。
2. 構(gòu)造權(quán)重矩陣. , LLE 權(quán)重矩陣的構(gòu)造包括每個 局部鄰域的線性方程的解。
3. 部分特征值分解. 參見上述 Isomap 討論。

標準 LLE 的整體復(fù)雜度是

: 訓(xùn)練數(shù)據(jù)點個數(shù)

: 輸入維度

: 最近鄰個數(shù)

: 輸出維度

參考資料:

• “Nonlinear dimensionality reduction by locally linear embedding” Roweis, S. & Saul, L. Science 290:2323 (2000)

2.2.4. 改進型局部線性嵌入（MLLE）

局部線性嵌入(LLE)一個眾所周知的問題是正則化問題。當(dāng)鄰域數(shù)大于輸入維數(shù)時，定義每個局部鄰域的矩陣是不滿秩的。為了解決這個問題，標準LLE應(yīng)用了一個任意的正則化參數(shù) ，它的取值受局部權(quán)重矩陣的跡的影響。雖然可以形式化的表示為：當(dāng)正則化參數(shù) ,解收斂于期望的嵌入,但是當(dāng) 時不保證找到最優(yōu)解。這個問題表現(xiàn)在嵌入過程中扭曲了流形的基本幾何形狀。

解決正則化問題的一種方法是在每個鄰域中使用多個權(quán)重向量。這就是改進的局部線性嵌入(MLLE)算法的本質(zhì)。MLLE可以通過函數(shù) locally_linear_embedding 或者其面向?qū)ο蟮母北?LocallyLinearEmbedding 來執(zhí)行，附帶關(guān)鍵詞 method = 'modified' 。它需要滿足 n_neighbors > n_components。

2.2.4.1. 復(fù)雜度

MLLE 算法分為三個階段:

1. **近鄰搜索.**與標準 LLE 的相同。
2. **權(quán)重矩陣構(gòu)造.**大約是 。該式第一項恰好等于標準 LLE 算法的復(fù)雜度。第二項與由多個權(quán)重來構(gòu)造權(quán)重矩陣相關(guān)。在實踐中，構(gòu)造 MLLE 權(quán)重矩陣所增加的損耗（就復(fù)雜度而言），比其它兩部分要小。
3. **部分特征值分解.**與標準 LLE 的相同。

綜上，MLLE 的復(fù)雜度為 。

• : 訓(xùn)練集數(shù)據(jù)點的個數(shù)
• : 輸入維度
• : 最近鄰域的個數(shù)
• : 輸出維度

參考資料:

• “MLLE: Modified Locally Linear Embedding Using Multiple Weights” Zhang, Z. & Wang, J.

2.2.5. 黑塞特征映射（HE）

黑塞特征映射 (也稱作基于黑塞的 LLE: HLLE ）是解決 LLE 正則化問題的另一種方法。在每個用于恢復(fù)局部線性結(jié)構(gòu)的鄰域內(nèi)，它會圍繞一個基于黑塞的二次型展開。雖然其它的實現(xiàn)表明它對數(shù)據(jù)大小進行縮放的能力較差，但是 sklearn 實現(xiàn)了一些算法改進，使得在輸出低維度時它的損耗可與其他 LLE 變體相媲美。HLLE 通過函數(shù) locally_linear_embedding 或其面向?qū)ο蟮男问?LocallyLinearEmbedding 被執(zhí)行，附帶關(guān)鍵詞 method = 'hessian' 。它需滿足 n_neighbors > n_components * (n_components + 3) / 2 。

2.2.5.1. 復(fù)雜度

HLLE 算法分為三個階段:

1. **近鄰搜索.**與標準 LLE 的相同。
2. **權(quán)重矩陣構(gòu)造.**大約是 。其中第一項與標準LLE相似。第二項來自于局部黑塞估計量的一個 QR 分解。
3. **部分特征值分解.**與標準 LLE 的相同。

綜上，HLLE 的復(fù)雜度為 。

• : 訓(xùn)練集數(shù)據(jù)點的個數(shù)
• : 輸入維度
• : 最近鄰域的個數(shù)
• : 輸出維度

參考資料:

• “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. 譜嵌入

譜嵌入是計算非線性嵌入的一種方法。Scikit-learn實現(xiàn)了拉普拉斯特征映射，它使用拉普拉斯圖的譜分解方法來進行數(shù)據(jù)的低維表示。所生成的圖可以看作是低維流形在高維空間中的離散近似值?；趫D的代價函數(shù)的最小化確保流形上相互接近的點在低維空間中相互映射并保持局部距離。譜嵌入可使用行為函數(shù) spectral_embedding 或它的面向?qū)ο蟮膶?yīng)形式 SpectralEmbedding 來執(zhí)行。

2.2.6.1. 復(fù)雜度

譜嵌入（拉普拉斯特征映射）算法包含三部分：

1. **加權(quán)圖結(jié)構(gòu).**把原始輸入數(shù)據(jù)轉(zhuǎn)換為用相似（鄰接）矩陣表達的圖表達。
2. **圖拉普拉斯結(jié)構(gòu).**非規(guī)格化的圖拉普拉斯是按 構(gòu)造，并按規(guī)格化。
3. **部分特征值分解.**在圖拉普拉斯上進行特征值分解。

綜上，譜嵌入的復(fù)雜度為 。

• : 訓(xùn)練集數(shù)據(jù)點的個數(shù)
• : 輸入維度
• : 最近鄰域的個數(shù)
• : 輸出維度

參考資料:

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

2.2.7. 局部切空間對齊（LTSA）

雖然從技術(shù)上講局部切空間對齊(LTSA) 不是LLE的變體，但在算法上與LLE非常相似，因此可以將其歸入這一類。與LLE不同的是，LTSA不像LLE那樣注重保持鄰域距離，而是通過其切空間來描述每個鄰域的局部幾何形狀，并執(zhí)行全局最優(yōu)化來對齊這些局部切空間以得到對應(yīng)的嵌入。 LTSA 可通過函數(shù) locally_linear_embedding 或其面向?qū)ο蟮膶?yīng)函數(shù) LocallyLinearEmbedding 來執(zhí)行，附帶關(guān)鍵詞 method = 'ltsa' 。

2.2.7.1 復(fù)雜度

LSTA算法包含三部分：

1. **近鄰搜索.**與標準 LLE 的相同。
2. **權(quán)重矩陣構(gòu)造.**大約是 。其中第一項與標準LLE相似。
3. **部分特征值分解.**與標準 LLE 相同。

綜上，復(fù)雜度為 。

• : 訓(xùn)練集數(shù)據(jù)點的個數(shù)
• : 輸入維度
• : 最近鄰域的個數(shù)
• : 輸出維度

參考資料:

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

2.2.8. 多維尺度分析（MDS）

多維尺度分析 Multidimensional scaling （ MDS ） 尋求數(shù)據(jù)的低維表示，而且低維數(shù)據(jù)間的距離保持了它們在原始高維空間中的距離。

通常，MDS是一種用于分析相似或不同數(shù)據(jù)的技術(shù)。它試圖在幾何空間上將相似或不相似的數(shù)據(jù)進行建模。數(shù)據(jù)可以是對象之間的相似性評級，分子的相互作用頻率，或國家之間的貿(mào)易指數(shù)。

MDS算法有度量算法和非度量算法兩種。在scikit-learn中， MDS 類可以實現(xiàn)這兩種算法。在度量MDS中，輸入相似度矩陣源于一個度量(因此尊重三角不等式)，后設(shè)置輸出兩點之間的距離盡可能接近相似或不相似的數(shù)據(jù)。在非度量的情況下，算法會盡量保持對距離的控制，從而在嵌入空間的距離與相似點/不相似點之間尋找單調(diào)關(guān)系。

設(shè)是相似度矩陣，是 個輸入點的坐標。差異 是某些最優(yōu)方式所選擇的相似度轉(zhuǎn)換。然后，通過 $\sum_{i

2.2.8.1. 度量 MDS

最簡單的度量 MDS 模型稱為 absolute MDS（絕對MDS），差異由 定義。對于絕對 MDS，值應(yīng)精確地對應(yīng)于嵌入點的點 和 之間的距離。

大多數(shù)情況下，差異應(yīng)設(shè)置為 。

2.2.8.2. 非度量 MDS

非度量 MDS 關(guān)注數(shù)據(jù)的排序。如果$S_{i j}

這個問題的 a trivial solution（一個平凡解）是把所有點設(shè)置到原點上。為了避免這種情況，將差異正則化。

參考資料:

• “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 ）將數(shù)據(jù)點的相似性轉(zhuǎn)換為概率。原始空間中的相似性用高斯聯(lián)合概率表示，嵌入空間中的相似性用”學(xué)生“的t分布表示。這使得t-SNE對局部結(jié)構(gòu)特別敏感，并且比現(xiàn)有技術(shù)有一些其他的優(yōu)勢:

• 在一個單一映射上按多種比例顯示結(jié)構(gòu)
• 顯示位于多個、不同的流形或聚類中的數(shù)據(jù)
• 減輕在中心聚集的傾向

雖然Isomap、LLE和其他變體最適合展開單個連續(xù)的低維流形，但t-SNE將重點關(guān)注數(shù)據(jù)的局部結(jié)構(gòu)，并傾向于提取聚類的局部樣本組，如S-curve示例中突出顯示的那樣。這種基于局部結(jié)構(gòu)對樣本進行分組的能力可能有助于從視覺上分離同時包含多個流形的數(shù)據(jù)集，就像數(shù)字數(shù)據(jù)集中的情況一樣。

利用梯度下降的方法，使原始空間和嵌入空間的聯(lián)合概率的離散度達到最小。注意KL散度不是凸的，也就是說，用不同的初始化方法多次重新啟動，最終會得到KL散度的局部極小值。因此，有時嘗試不同的種子并選擇KL散度最低的KL散度的嵌入是有用的。

使用 t - SNE 的缺點大致如下:

• t-SNE 的計算成本很高，在百萬樣本數(shù)據(jù)集上花費數(shù)小時，而PCA在幾秒鐘或幾分鐘內(nèi)就可以完成。
• Barnes-Hut t-SNE 方法僅限于二維或三維嵌入。
• 該算法是隨機的，不同種子的多次重啟可以產(chǎn)生不同的嵌入。然而，以最小的誤差選擇嵌入是完全合理的。
• 未明確保留全局結(jié)構(gòu)。這個問題可以通過使用PCA初始化點(使用 init=’pca’)來緩解。

2.2.9.1. 優(yōu)化t-SNE

t-SNE的主要目的是實現(xiàn)高維數(shù)據(jù)的可視化。因此，當(dāng)數(shù)據(jù)被嵌入到二維或三維時，它的效果最好。

優(yōu)化KL散度有時會有點棘手。有五個參數(shù)控制t-SNE的優(yōu)化，因此可能也會影響最終嵌入的質(zhì)量:

• 困惑度
• 早期增長因子
• 學(xué)習(xí)率
• 最大迭代次數(shù)
• 角度（不在精確方法中使用）

困惑度定義為，其中是條件概率分布的香農(nóng)熵。面色子的復(fù)雜度是 ，它實際上是t-SNE在生成條件概率時考慮的最近鄰的個數(shù)。困惑度越大導(dǎo)致更近，對小結(jié)構(gòu)也越不敏感。相反，較低的困惑度考慮的是較少的鄰域，因此忽略了更多的全局信息，而更加關(guān)注局部鄰域。隨著數(shù)據(jù)集的增大，需要更多的點來獲得合理的局部鄰域樣本，因此可能需要更大的困惑度。同樣的，噪聲越大的數(shù)據(jù)集需要越大的困惑度來包含足夠多的局部鄰居，以便在背景噪聲之外查看。

迭代的最大次數(shù)通常足夠高，不需要任何調(diào)優(yōu)。優(yōu)化包括兩個階段:早期增長階段和最終優(yōu)化階段。在早期的增長階段，原始空間中的聯(lián)合概率將通過與給定的因子相乘而被人為地增加。越大的因子導(dǎo)致數(shù)據(jù)中自然聚類之間的差距越大。如果因子過高，則KL散度在此階段可能增大。通常不需要對其進行調(diào)整。一個關(guān)鍵的參數(shù)是學(xué)習(xí)率。如果梯度降得太低，就會陷入局部極小值。如果KL散度過高，則在優(yōu)化過程中KL散度會增大。更多的技巧可以在Laurens van der Maaten的FAQ中找到(見參考資料)。最后一個參數(shù)角度，它是性能和精度之間的權(quán)衡。角度越大意味著我們可以用單個點來近似更大的區(qū)域，從而得到更快的速度，但結(jié)果越不準確。

“How to Use t-SNE Effectively” （如何高效使用t-SNE）提供了一個關(guān)于各種參數(shù)效果的討論，以及用來探索不同參數(shù)效果的交互式繪圖。

2.2.9.2. Barnes-Hut t-SNE

這里實現(xiàn)的Barnes-Hut t-SNE通常比其他流形學(xué)習(xí)算法要慢得多。優(yōu)化比較困難，梯度的計算為，其中為輸出維數(shù)，為樣本數(shù)。t-SNE復(fù)雜度是,Barnes-Hut 方法在此基礎(chǔ)上進行了改進，但有幾個其他顯著差異:

• Barnes-Hut 僅在目標維度為3或更小時才有效。構(gòu)建可視化時，基于2-D的情況就是典型的用于可視化。
• Barnes-Hut 僅對密集的輸入數(shù)據(jù)有效。稀疏數(shù)據(jù)矩陣只能用精確方法嵌入，或者可以通過密集的低階投影來近似，例如使用 sklearn.decomposition.TruncatedSVD
• Barnes-Hut 是精確方法的近似。這個近似值是用角度參數(shù)來參數(shù)化的，因此當(dāng)參數(shù) method=”exact” 時，angle 參數(shù)無效。
• Barnes-Hut 的拓展性很高。Barnes-Hut 可用于嵌入數(shù)十萬個數(shù)據(jù)點，而精確方法只能處理數(shù)千個樣本，再多就會變得難以計算。

出于可視化目的(這是t-SNE的主要用例)，強烈建議使用Barnes-Hut方法。精確的t-SNE方法可以用來檢驗高維空間中嵌入的理論性質(zhì)，但由于計算能力的約束而僅限于小數(shù)據(jù)集。

還需要注意的是，數(shù)字標簽與t-SNE發(fā)現(xiàn)的自然聚類大致匹配，而PCA模型的線性2D投影則產(chǎn)生了一個標簽區(qū)域大部分重疊的表示。這是一個強有力的線索，表明該數(shù)據(jù)可以通過關(guān)注局部結(jié)構(gòu)的非線性方法(例如帶有高斯RBF核的SVM)很好地分離。然而，在2維中不能很好地將t-SNE標記的均勻分組可視化并不一定意味著數(shù)據(jù)不能被監(jiān)督模型正確分類?？赡艿那闆r是，2維不夠低，不能準確地表示數(shù)據(jù)的內(nèi)部結(jié)構(gòu)。

參考資料:

• “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. 實用技巧

• 確保對所有特征中使用相同的縮放比例。由于流形學(xué)習(xí)方法是基于最近鄰搜索的，否則算法的性能可能很差。有關(guān)縮放異構(gòu)數(shù)據(jù)的方便方法，請參閱 StandardScaler 。
• 每個程序計算的重構(gòu)誤差可以用來選擇最優(yōu)的輸出維數(shù)。對于嵌入在維參數(shù)空間中的 維流形，重構(gòu)誤差將隨著 n_components 的增加而減小，直到 n_components == d 。
• 注意，有噪聲的數(shù)據(jù)會使流形管“短路”，本質(zhì)上是在流形管的各個部分之間起到橋梁作用，否則流形管就會被很好地分開。基于噪聲和/或不完全數(shù)據(jù)的流形學(xué)習(xí)是一個活躍的研究領(lǐng)域。
• 某些輸入配置可能導(dǎo)致奇異加權(quán)矩陣，例如，當(dāng)數(shù)據(jù)集中有兩個以上的點是相同的，或者當(dāng)數(shù)據(jù)被分割成不關(guān)聯(lián)的組時。在這種情況下， solver='arpack' 將無法找到零空間。解決這一問題的最簡單方法是使用 solver='dense' ，它將在一個奇異矩陣上工作，盡管它可能因為輸入點的數(shù)量而非常慢?；蛘撸梢試L試理解奇點的來源:如果是由于不相交的集合，增加 n_neighbors 可能會有所幫助；如果是由于數(shù)據(jù)集中的相同的點，則刪除這些點可能有所幫助。

也可以看看：完全隨機樹嵌入也可用于導(dǎo)出特征空間的非線性表示，并且它不執(zhí)行降維。