VisuMap Technologies
                  See the Invisible in your Data
A Brief Introduction to Relational Perspective Map

Relational perspective map (RPM), developed by James X. Li[1],  is a general purpose method for visualizing distance information of data points in high dimensional spaces.

The starting point of the RPM algorithm is a set of data point si, i=1,...,N, and a distance matrix δij. The matrix δij, called the relational distance, is the numeric representation of a relationship between the data points. The goal of the RPM algorithm is to map the data points si into a two or three dimensional map so that Euclidean distances dij between the image points visually approaches δij as much as possible. The resulting lower dimensional map is called Relational Perspective Map, the matrix dij is called the Image Distance Matrix. From geometric point of view, an RPM map attempts to preserve as much as possible the distance information within the original dataset.

The following figure demonstrates how the RPM algorithm works to create 2D maps: it first maps data points to the surface of a torus, then unfolds the torus surface by a vertical and a horizontal cut. This second step is relatively straightforward (see here for a short video showing the transformation between rectangle and torus), the innovation of the RPM algorithm lies in mapping the data points to the torus surface so that the distances between the image points resembles the distances between data points.

Concept of Relational Perspective Map  

In order the find the best mapping, the RPM algorithm defines an energy function as follows:
RPM energy function    
where p is an algorithm parameter called the rigidity, dij  is the geodesic block distance between two image points on the torus surface. The RPM algorithm then uses gradient descent optimization method to find the lowest-energy configuration. The rigidity parameter, which is normally a value between -1 and +1, alters the energy landscape in a global manner, so that the resulting RPM maps have different characteristics.

To better understand the RPM algorithm it is helpful to consider the image points on the torus as a force-directed, multi-particale system with mutual repulsive forces between them; and consider the energy Ep as a kind of total potential energy. According to physics, the repulsive force is characterized as proportional to relational distance:

Force directing RPM simulations

The optimization strategy is to minimize the energy Ep by simulating a dynamic system directed by the force given by above form. Since points with larger relational distances between them correspond to larger repulsive force on the torus, their image points on the torus should  be further apart from each other.

The key idea of RPM algorithm is its exploitation of the properties of closed manifold (the torus) to keep the configuration in balance. (Competing approaches are identified in the next section.) Whereas other non-linear methods apply, directly or indirectly, attractive force to map closely related points to closely located positions,  the RPM algorithm maps closely related points within a closely located area by modeling the collective repulsive force of all points. This approach makes RPM a true, and (as far as we know) the only, global mapping algorithm.

It should be noted here that the RPM algorithm relaxes one condition of the original problem setting: the resulting map is not a normal rectangle, but a torus. This means that the opposite edges of the map should be considered as contiguous or joined.

Related Methods:

Visualizing high dimensional data has been a major topic since many decades. A large group of methods target high dimensional data with sophisticated rendering techniques like 3D landscapes, special glyphs, colors, and graphics etc. Other methods approach the problem by reducing the dimensionality in a generic way with few assumptions about data type. RPM algorithm belongs to the latter group. The following is a short list of methods that directly or indirectly reduce data dimensionality:
  • Multidiemensional Scaling: Sammon Mapping, Curvilinear Component Analysis.
  • Self-Organzing Map.
  • Principal Component Analysis/Singulare Value Decomposition.
  • Non-linear Projections:  Local Linear Embedding.
  • Methods based on physical models: spring embedding model; force directed placement.
References:
  1. James Xinzhi Li: Visualization of High Dimensional Data with Relational Perspective Map. Information Visualization 2004, Vol. 3, No. 1. 49-59.



Copyright © 2002-2014 VisuMap Technologies Inc.