機器學習之：流形與降維概述

流形與降維：概述

• 降維算法概述
• • 流形學習
  • 距離的定義
• KNN圖與流形降維
• • KNN圖
  • SNE算法

降維算法概述

降維，顧名思義就是把資料或者特征的次元降低，一般分為線性降維和非線性降維。

線性降維有：PCA、LDA、MDS（Classical Multidimensional Scaling）

非線性降維有： ISOmap( Isometric Mapping), LLE(Locally Linear Embedding), LE(Laplacian Eigenmaps) 非線性降維算法中用到的，大多屬于流行學習方法。

流形學習

關于流形學習(Manifold Learning)最形象的解釋莫過于這幅圖：

這幅圖又被稱為Swiss Roll，瑞士卷，是一種常見的卷狀蛋糕，如何計算蛋糕卷起表面上兩點距離，就是流行計算中要解決的一個問題。

距離的定義

在歐式幾何中，我們将兩點的距離定義為兩點的直線距離，這個距離也是在歐式空間中A到B的最短距離。由于在瑞士卷上，從A點到B點實際上有無數中路徑，那麼該如何定義A和B之間的距離呢？與歐式空間中的距離定義類似，我們也可以将其簡單地定義為“最短路徑”。

那麼這個最短距離又如何定義呢？現實生活中測量從北京到紐約的距離也是一個這樣的問題。由于地球實際上是球形的，從北京的紐約的距離 不是空間中這兩個地點的直線距離，而是通過GIS中稱為測地距離（根據球面幾何，球體上任意兩點的距離就是同時經過這兩點的球面大圓的弧長）的度量來計算。在瑞士卷的問題中，類似地，我們也需要找到“測地距離”。

總結一下，這裡提到的幾個概念：

• 測地距離：流形上兩個點之間的最短測地線的長度。
• 測地線：流形上兩個點之間最短的曲線。
• 黎曼測度：黎曼流形上某一點的切空間上定義的内積的集合。
• 黎曼測度的性質：黎曼流形上某一點的切空間上某一切向量的範數等于這個切向量對應的測地線的長度。

KNN圖與流形降維

KNN圖

KNN圖（k-Nearest Neighbour Graph）是對空間中的n個節點，通過某種距離度量的方式找到距離他最近的k個鄰居，然後分别将這k個點連接配接起來，形成k條有向邊。當然在實際中為了便于處理，通常是構造成無向邊。這樣的處理方法類似于局部微分，認為流行上每個點的鄰域符合歐式空間定義。就類似于處理從北京到紐約的距離這樣的問題不能用歐式幾何，應該用黎曼集合，但是對于日常生活中常用的距離概念都是用歐式距離來描述一樣。從直覺上來講，一個流行好比是d維的空間，在一個m維的空間中被扭曲（m>d）之後的結果，d維流形的任意點都局部同胚于（正逆映射都是光滑的一一映射）歐式空間 R D R^D RD。

KNN圖就可以在計算流行上兩點的距離時起到“估算”測地線的作用，用歐式距離得到一個近似，如下圖所示，圖中藍色的曲線是沿着流行真實的測地線距離，紅色的是在原始資料點上根據歐式距離構造KNN 圖得到的近似測地線距離。

SNE算法

SNE（stochastic neighbor embedding）算法的基本假設和上述KNN圖算法基本上是一緻的，在高維空間相似的資料點，映射到低維空間距離也是相似的。但是與KNN圖算法不同的是，SNE把這種距離關系轉換為一種條件機率來表示相似性。

假設高維空間中的資料點服從高斯分布，那麼任意兩點之間的距離，例如 X j X_j Xj​點相距 X i X_i Xi​點的距離認為是：

p j ∣ i = e x p ( − ∣ ∣ X i − X j ∣ ∣ 2 / ( 2 δ i 2 ) ∑ k ≠ i e x p ( − ∣ ∣ X i − X k ∣ ∣ 2 / ( 2 δ i 2 ) p_{j|i}= \frac{exp(-||X_i-X_j||^2/(2\delta_i^2)}{\sum_{k \ne i}{exp(-||X_i-X_k||^2/(2\delta_i ^2)}} pj∣i​=∑k̸​=i​exp(−∣∣Xi​−Xk​∣∣2/(2δi2​)exp(−∣∣Xi​−Xj​∣∣2/(2δi2​)​

資料映射到低維空間後，高維資料點之間的相似性應該在低維空間保持一緻。這裡同樣用條件機率的形式描述，假設高維資料點 x i x_i xi​和 x j x_j xj​在低維空間的映射點分别為 y i y_i yi​和 y j y_j yj​。類似的，低維空間中的條件機率用 q j ∣ i q_{j∣i} qj∣i​表示，并将所有高斯分布的方差均設定為 1 2 \frac{1}{\sqrt{2}} 2

​1​，是以有：

q j ∣ i = e x p ( − ∣ ∣ Y i − Y j ∣ ∣ 2 ∑ k ≠ i e x p ( − ∣ ∣ Y i − Y k ∣ ∣ 2 q_{j|i}= \frac{exp(-||Y_i-Y_j||^2}{\sum_{k \ne i}{exp(-||Y_i-Y_k||^2}} qj∣i​=∑k̸​=i​exp(−∣∣Yi​−Yk​∣∣2exp(−∣∣Yi​−Yj​∣∣2​

如果降低次元後 Y i Y_i Yi​和 Y j Y_j Yj​真實反映了高維資料點 X i X_i Xi​和 X j X_j Xj​之間的關系，那麼條件機率 p j ∣ i p_{j∣i} pj∣i​與 q j ∣ i q_{j∣i} qj∣i​應該完全相等。