機器學習_學習筆記系列(72)：等距特徵映射(Isometric Mapping)
還記得我們之前所介紹的MDS嗎？我們會先計算每筆資料的間距，然後希望我們把數據降維到低維度空間的時候能盡可能地保持原本數據間原本的距離。
對於MDS樣計算的方式是透過所謂的歐幾里得距離(Euclidean Distance)，也就是把兩點之間個特徵的數值相減後平方，再加總起來開根號。
而今天我們就要來介紹新的演算法ISOMAP，其原理和概念和MDS非常接近，都是希望我們降維後的數據能夠盡量表現出，原本數據間的距離。然而ISOMAP其所計算的距離方式是透過所謂的測地距離(Geodesic distance)
Geodesic distance
對於側地距離，這個就牽扯到圖論了。
由上面這張圖[1]我們可以看到，對於一般計算兩者距離的方式，我們都是用所謂的歐幾里得距離去計算，但是歐幾里得距離有時候沒辦法很好的表示出整個資料的分布，所以才會透過Geodesic distance表示。
而我們可以看到，在計算Geodesic distance我們會把所有的數據與其鄰近的點連接起來，要計算距離的話，只能透過連接的edge來計算。
所以由上面這些敘述我們可以知道，當我們拿到資料時彼此之間是沒有edge連接的，所以我們需要先用一個演算法把鄰近的點連起來，而且我們還需要一個路近搜尋的演算法幫助我們計算所有資料間點到點的Geodesic distance，最後才是以和MDS的概念將我們的資料進行降維。
所以對於ISOMAP我們需要用到三個演算法
1. Nearest Neighborhood Search
2. Shortest Path Graph Search
3. Dimensional Reduction
Nearest Neighborhood Search
關於NN Search我們前兩個章節有介紹到所謂的Ball Tree和k-Nearest Neighbor Search。我們一開始拿到資料後，我們可以先用Ball Tree建立數據的資料結構，接著我們再以kNN Search找出鄰近點把他連接起來。
Shortest Path Graph Search
OK當我們用Ball Tree和kNN Search建立好我們的Graph之後就是進入搜尋演算法，來找出點到點距離，在這邊我們可以選用Dijkstra Algorithm並以Fibonacci heap最佳化。(這邊因為是演算法和資料結構的地方，所以就不贅述)
最後我們可以得到像下面的的矩陣：
Dimensional Reduction
最後我們得到了Geodesic distance的矩陣後，我就可以帶入和之前MDS一樣的方程式
這邊的(2)代表裡面的元素都取平方，D則是Geodesic distance矩陣
接下來我們對B進行eigen decomposition
然後一樣取前面K個最大的eigenvalue和其所對應的eigenvector我們就可以得到我們降維後的矩陣
Complexity
而在這邊ISOMAP的三個步驟其Complexity分別為
k-Nearest Neighbor Search:
Dijkstra Algorithms with Fibonacci Heap:
Dimensional Reduction:
其中N為資料數量、D為資料維度、k為鄰近資料點數、d為降維後的維度。
所以總體ISOMAP Complexity為
Example
接下來我們一樣以手寫辨識資料集MNIST來看看我們ISOMAP的效果
我們可以看到ISOMAP的區分效果又比MDS來得更清楚，而且我們在這張圖可以看到一件有趣的事，因為ISOMAP真實反映了數據間的距離，所以外觀相差很多的數字會相距非常的遠，而像是3、8、9這些長得比較像的數字就會離對方比較近，甚至是重疊在一起。
Python Sample Code:
Github:
Reference:
[1] Karam, Z. N., & Campbell, W. M. (2013). Graph embedding for speaker recognition. In Graph Embedding for Pattern Analysis (pp. 229–260). Springer, New York, NY.
[2] “A global geometric framework for nonlinear dimensionality reduction” Tenenbaum, J.B.; De Silva, V.; & Langford, J.C. Science 290 (5500)
[3] Scikit-learn: Machine Learning in Python, Pedregosa et al., JMLR 12, pp. 2825–2830, 2011.
