What is Isometric Feature Mapping (ISOMAP)?

Isomap, an abbreviation for Isometric Mapping, is a dimensionality reduction algorithm that transcends the limitations of linear approaches. Its primary objective is to unfold intricate patterns within high-dimensional data into a lower-dimensional space while meticulously preserving the essential relationships between data points. Unlike linear methods such as Principal Component Analysis (PCA), which assume a linear relationship between variables, Isomap excels at capturing the underlying non-linear structure, making it a go-to choice for a diverse array of applications.

Workings of ISOMAP?

Step 1: Construct the Neighbourhood Graph

At the core of Isomap lies a series of steps that collectively contribute to its unique ability to reveal the intrinsic geometry of complex datasets. The algorithm initiates by constructing a neighborhood graph, where nodes represent data points, and edges connect nodes that are within a certain distance of each other. A neighborhood graph is a graph where nodes are data points and edges connect nodes that are within a certain distance of each other. This neighborhood graph serves as the foundational structure for Isomap’s subsequent computations. To construct the neighborhood graph, we first calculate the Euclidean distance between all pairs of data points. Then, we select the k nearest neighbors for each data point and create edges in the graph connecting these neighbours. The value of k is a parameter of the algorithm that can be adjusted depending on the data.

Euclidean distance between all pairs of data points:

where:

• is the Euclidean distance between data points and
• is the Euclidean norm of the vector

Neighborhood graph: A graph G can be defined over the data points by connecting points i and j if they are closer than a specifiеd threshold e (e-Isomap), or if i is one of the K-nearest neighbors of j (K-Isomap).The choice of k affects the connectivity and shape of the neighborhood graph. If k is chosen too small, the neighborhood graph may not be connected, while if it is chosen too large, it may lead to a so-called “short-circuit error.”

Step 2: Approximate Geodesic Distances

Isomap then delves into the realm of geodesic distances, a concept critical to understanding the true structure of non-linear manifolds. The geodesic distance between two points in a neighborhood graph is defined as the shortest path along the edges of the graph, measuring the distance on the curved surface of a manifold. Unlike the Euclidean distance, which represents a straight-line measurement, the geodesic distance is sensitive to the underlying structure, capturing the true intricacies of the data. To approximate the geodesic distance by calculating the shortest path between the two points along the edges of the neighborhood graph variety of algorithms can be used, such as Dijkstra’s algorithm or Floyd-Warshall’s algorithm. The algorithm efficiently computes the shortest paths between all pairs of vertices in a graph.

Floyd-Warshall algorithm for finding the shortest paths in a weighted graph.

Initialize with a array Dg of minimum distances to infinity, and setting the distance from each vertex to itself as 0. For each edge (i, j), the distance in Dg should be as the weight of the edge (i, j). Finally, Iterate through all pairs of vertices (i, j) and update the distance if a shorter path is found by going through vertex k.

Step 3: Apply Multidimensional Scaling (MDS)

The final step in Isomap is to apply multidimensional scaling (MDS). MDS is a dimensionality reduction technique that aims to find a lower-dimensional representation of the data that preserves the pairwise distances between data points. Once the geodesic distances have been computed, Isomap embeds the data in a lower-dimensional space. This embedding is performed using a technique called spectral embedding. Spectral embedding is a dimensionality reduction technique that works by finding the principal components of the graph Laplacian. The graph Laplacian is a matrix that represents the connectivity of the neighborhood graph. The magic of Isomap unfolds with the application of spectral embedding. The graph Laplacian, a matrix representing the connectivity of the neighborhood graph, encapsulates the relationships and proximities between data points. By unveiling the principal components, Isomap successfully embeds the data into a lower-dimensional space while meticulously preserving the essential geometric relationships.

In the realm of machine learning and data analysis, grappling with high-dimensional datasets has become a ubiquitous challenge. As datasets grow in complexity, traditional methods often fall short of capturing the intrinsic structure, leading to diminished performance and interpretability. In this landscape, Isomap (Isometric Mapping) emerges as a potent technique designed explicitly to navigate the intricacies of complex, non-linear structures inherent in data. Dimensionality reduction is a crucial aspect of machine learning and data analysis, especially when dealing with high-dimensional datasets. One powerful technique for this purpose is Isomap, an algorithm designed to capture the underlying geometry of complex, non-linear structures. Isomap stands for Isometric Mapping, and its primary goal is to unfold intricate patterns in high-dimensional data into a lower-dimensional space while preserving the essential relationships between data points.