## ELastic MAPs |

Principal curves, graphs and surfaces are nonlinear generalizations of principal components and subspaces, respectively. 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. A biobliography on the subject is available in A. N. Gorban, A. Y. Zinovyev, Principal Graphs and Manifolds, In: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques, Olivas E.S. et al Eds. Information Science Reference, IGI Global: Hershey, PA, USA, 2009. 28–59. and 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. |

PCA View View on the non-linear manifold

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.

3) as a Java applet for 2D data distributions, available online

**Binaries:**

- ELMAP package: Win32 platform
- Source codes of elmap
- Link to the VidaExpert tool page

The sources are available upon request.

- A. Zinovyev, E. Mirkes. Data complexity measured by principal graphs, Computers and Mathemtatics with Applications (2013). http://arxiv.org/abs/1212.5841
- A. N. Gorban, A. Y. Zinovyev, Principal Graphs and Manifolds, In: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques, Olivas E.S. et al Eds. Information Science Reference, IGI Global: Hershey, PA, USA, 2009. 28–59.
- A. N. Gorban, A. Zinovyev, Principal manifolds and graphs in practice: from molecular biology to dynamical systems, International Journal of Neural Systems, Vol. 20, No. 3 (2010) 219–232.
- A.N. Gorban, A.Yu. Zinovyev. Elastic principal manifolds and their practical applications. Computing, 75 (4) (2005), 359 - 379
- A. Zinovyev. Method And Software For Fast Construction Of Principal Manifolds Approximations. IHES Preprint, 2003
- A.N. Gorban, A. Zinovyev. Visualization of Data by Method of Elastic Maps and Its Applications in Genomics, Economics and Sociology. IHES Preprint, 2002.
- A.N. Gorban, A. Zinovyev, D.C. Wunsch, Application of the method of elastic maps in analysis of genetic texts, in: Proceedings of International Joint Conference on Neural Networks, IJCNN-2003, Vol 3, pp. 1826–1831.

You can also have a look at the following Powerpoint presentation:

- Non-linear Principal Manifolds - elastic maps approach. (PPT)