Branching Principal Components, Principal Cubic Complexes and Topological Grammars

AN Gorban (University of Leicester, UK) 

with NR Sumner (University of Leicester, UK), and AY Zinovyev (Institute Curie, Paris)

Summary

A method of topological grammars1 is proposed for multidimensional data approximation. For data with complex topology we define a principal cubic complex of low dimension and given complexity that gives the best approximation for the dataset. This complex is a generalisation of linear and non-linear principal manifolds and includes them as a particular case.

The problem of optimal principal complex construction is transformed into a series of minimisation problems for quadratic functionals. These quadratic functionals have a physically transparent interpretation in terms of elastic energy. For the energy computation, the whole complex is presented as a system of nodes and springs.

Topologically, the principal complex is a product of one-dimensional continuums (represented by graphs), and the graph grammar2 describes transformation of these factors during construction of the optimal complex. This factorisation of the whole process onto one-dimensional transformations and using minimisation of quadratic energy functionals allow us to construct efficient algorithms.

The topology of the complex is not prescribed, but adaptive. In that sense, they are even more flexible than SOMs3. The whole approach can be interpreted as an intermediate between very flexible neural gas and significantly more restrictive elastic maps4. It includes as simple limit cases the k-means clustering algorithm, classical PCA and Principal manifolds5,6.

 

PCA_mov1    PCA_mov2

Progress and Publications

  1. AN Gorban, NR Sumner and AY Zinovyev. Topological grammars for data approximation, Applied Mathematics Letters 20, Issue 4 (2007), 382-386. (full text pdf)
  2. Nagl. Formal languages of labelled graphs, Computing 16 (1976), 113-137.
  3. T Kohonen. Self-organized formation of topologically correct feature maps, Biological Cybernetics, 43 (1982), 59-69.
  4. A Gorban, A Zinovyev. Elastic Principal Graphs and Manifolds and their Practical Applications, Computing 75 (2005), 359-379. (full text pdf)
  5. T Hastie, W Stuetzle. Principal curves, Journal of the American Statistical Association, 84 (406) (1989), 502-516.
  6. A Gorban, B Kegl, D Wunsch, A Zinovyev (Eds.). Principal Manifolds for Data Visualisation and Dimension Reduction, LNCSE 58, Springer, Berlin - Heidelberg - New York, 2007. ISBN: 978-3-540-73749-0

Share this page:

Contact

Centre for Mathematical Modelling
Michael Atiyah Building, Room 123
University of Leicester
University Road
Leicester LE1 7RH
UK

mmc@mcs.le.ac.uk
tel: +44 (0) 116 252 3896
fax: +44 (0) 116 252 3604