Skip to content
Andrei Zinovyev edited this page Nov 2, 2017 · 57 revisions

Welcome to the Elastic Principal Graphs Matlab and Java Implementation wiki!

Introduction

Principal graphs are data approximators suitable for complex branching and non-linear multidimensional data distributions. The method includes construction of principal trees, principal curves, principal closed curves.

Basic self-contained formal description of ElPiGraph can be found here.

Elastic principal graphs method id based on

  1. Minimizing the approximation error between data and the graph node positions in the data space while
  2. Penalizing the elastic energy of the graph embedding; and
  3. Application of the graph grammars to find the most optimal structure of the approximating graph (see the main elastic principal graph algorithm pseudocode description)

Elastic principal graphs method is a generalization of the method of elastic maps for approximating principal manifolds.

Implementation and basic use

The method of elastic principal graphs is implemented in several programming languages:

MATLAB - ElPiGraph.M

This repository. Example of basic use of the Elastic principal graphs in Matlab is here.

Developed by Luca Albergante

Python

coming soon

Java

As a part of VDAOEngine library developed by Andrei Zinovyev, with an available MATLAB and R wrappers (the development in Java has been stopped for now)

As a part of an interactive Java applet developed by Evgeny Mirkes (can be used as a standalone application), implementing several data approximators (PCA, SOM, GSOM, Growing Neural Gas and Robust Elastic Principal Trees) for 2D case. Provided as a part of this repository.

Examples of elastic principal graph construction

Two dimensional branching data distribution, with and without noise

Iris example, visualizing several classes of data

Human Genome Diversity Project, visualizing SNP profiles of human genomes

Bibliography on elastic principal graphs

(see also complete bibliography on application of elastic energy method)

  1. Gorban A., Mirkes E., Zinovyev A. Robust principal graphs for data approximation. Archives of Data Science 2(1):1:16, 2017.
  2. Zinovyev A. and Mirkes E. Data complexity measured by principal graphs. 2013. Computers and Mathematics with Applications 65:1471-1482.
  3. Gorban A.N., Zinovyev A. 2010. Principal manifolds and graphs in practice: from molecular biology to dynamical systems. Int J Neural Syst 20(3):219-32.
  4. Gorban AN and Zinovyev AY. Principal Graphs and Manifolds. In Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques (eds. Olivas E.S., Guererro J.D.M., Sober M.M., Benedito J.R.M., Lopes A.J.S.). Information Science Reference, September 4, 2009.
  5. Gorban A, Sumner N, Zinovyev A. Beyond The Concept of Manifolds: Principal Trees, Metro Maps, and Elastic Cubic Complexes. 2008. Lecture Notes in Computational Science and Engeneering 58: 223-240.
  6. Gorban A., Sumner N., Zinovyev A. Topological grammars for data approximation. 2007. Applied Mathematics Letters 20(4), 382-386.
  7. Gorban A., Zinovyev A. Elastic Principal Graphs and Manifolds and their Practical Applications. 2005. Computing 75,359 -379