ELastic MAPs
|
|
elmap - is a tool for fast constructing non-linear principal surfaces with
different topologies in multidimensional as well as in low-dimensional spaces,
for discrete sets of weightened points.
keywords: principal curve, principal surface, probabilistic, dimensionality reduction, nonlinear manifold, generative topographic mapping
Description
Principal curves and surfaces are nonlinear generalizations of principal components
and subspaces, respectively. They can provide insightful summary of high-dimensional
data not typically attainable by classical linear methods. They were first defined
by Trevor Hastie and Werner Stuetzle as "self-consistent" smooth curves which
pass through the "middle" of a d-dimensional probability distribution or data
cloud. Good biobliography on the subject is available at http://www.iro.umontreal.ca/~kegl/research/pcurves/
.
We present a novel algorithm to construct principal surfaces using methaphor
of elasticity. The picture on the right symbolizes the idea behind the
algorithm. The small points are datapoints, the big ones are a grid approximation
of a principal curve. We define an elastic energy of such system and propose
an effective algorithm to minimize it.
The methodology of principal curves and surfaces construction that we
propose has several advantages: 1) it is "natural"; 2) it is
fast; 3) it is flexible and allows many variations and adaptations; 4)
it allows easily constructing surfaces with any dimension and topology.
|
|
Examples
1) Contours extraction
2) Complex surface modelling
3) Multidimensional data visualization
PCA View View
on the non-linear manifold
References
- Gorban A., Zinovyev A. Elastic Principal Graphs and Manifolds and their Practical Applications. Computing, 2005 (PDF)
- Andrei Zinovyev. Method And Software For Fast Construction Of Principal Manifolds Approximations. (PDF)
- Alexander Gorban, Andrei Zinovyev. Visualization of Data by Method of Elastic Maps and Its Applications in Genomics, Economics and Sociology. (PDF)
- Alexander Gorban, Andrei Zinovyev and Donald Wunsch. Application of the method of elastic maps in analysis of genetic texts. (PDF)
You can also have a look at the following Powerpoint presentation:
- Non-linear Principal Manifolds - elastic maps approach. (PPT)
Implementation
For the moment the elastic maps algorithm has three implementations:
1) as a stand-alone full-featured tool VidaExpert fot multidimensional data visualization.
- The tool is written on Object Pascal.
2) as a C++ package for fast construction of fine grid approximations to principal surfaces.
- The package is written using standard C++, which allows to compile it on very different platforms.
It uses modestly STL. To solve quadratic optimization problem, the Sparselib++ library is used to represent
sparse matrices and IML++ library to solve system of linear equations iteratively.
3) as a part of vdaoengine Java package
- This implementation uses Colt library
for effective computations of linear systems with sparse matrices.
Downloads
Binaries:
The sources are available upon request.
Contact
Andrei Zinovyev