ISOMAP (Tenenbaum et al. 2000) is a relatively simple but often effective method for nonlinear dimensionality reduction. The implementation in Past follows these steps:
- Find the k closest neighbors of each point, using any distance measure. The result will strongly depend on the value of k, which must be specified by the user.
- Produce a graph where two vertices are connected if they are among their closest neighbors.
- Find the shortest paths between all vertices in the graph using the Floyd-Warshall algorithm. These path lengths represent “geodesic” distances along the manifold.
- Compute a standard PCoA (metric multidimensional scaling) on the geodesic distances.
Reference
Tenenbaum, J.B., de Silva, V., Langford, J.C. 2000. A global geometric framework for nonlinear dimensionality reduction. Science 290:2319-2323.