機器學習_學習筆記系列(74)：拉普拉斯特徵映射(Laplacian Eigenmaps)
上一回我們提到了Locally Linear Embedding演算法，接下來我們要來介紹另一個非線性降維的演算法Laplacian Eigenmaps。
Laplacian Eigenmaps
關於Laplacian Eigenmaps其是由芝加哥大學的Mikhail Belkin和Partha Niyogi所提出，論文名稱叫做
Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
關於Laplacian Eigenmaps其和ISOMAP一樣，希望能在降維過後盡量保持原本資料點間的相似性(Similarity)。對於兩者的區別在於
ISOMAP希望保存的是global geometry
Laplacian Eigenmaps希望保存的是local geometry。
而對於Laplacian Eigenmaps，在一開始的時候，我們一樣會用Ball Tree搭配kNN Search建立我們每個資料鄰近的數據點，並計算與其鄰近點的歐幾里得距離。
而在這邊為了抓取local information，我們會將點和點之間的距離d以Gaussian Weight來表示：
其中X為我們的資料，總共有N筆資料M個特徵X∈ R^(N×M)。t>0為我們自已所設定的參數，另外當j不為i的鄰近點時，w_ij=0，所以我們的矩陣W為一個N乘N的矩陣。
而我們現在希望把資料降到K維，其降維後的資料表示為Y∈ R^(N×K)，我們希望
也就是說當w_ij很接近1的時候，代表兩點很接近，所以我們必須讓Y_i和Y_j也相距很近。
而為了不讓我們的解為Y=0，我們對其做一些限制
其中
接下來為了求解我們的最佳化問題，我們將我們的式子進行改寫
其中L=D-W。所以我們現在的最佳化問題可以寫成
現在我們一樣用Lagrange equation去解
對Y微分
因為D、L為對稱矩陣，Λ為對角矩陣。所以
我們現在的問題就是變成解D^(-1)L的eigenvector。而在這裡因為我們的最佳問題是minimize，所以我們要取eigenvalue最小的eigenvector，如此一來就可以得到我們投影後的座標Y。
Example
接下來我們來看MNIST手寫辨識的例子
我們可以看到，相較於其他方法，Laplacian Eigenmaps把數據分得更開，已經可以很明顯的看出10個類別分布的位置。
Python Sample Code:
Github:
Reference:
[1] Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6), 1373–1396.
