Elastic map

Energy of elastic map

Let {\mathcal S} be a data set in a finite-dimensional Euclidean space. Elastic map is represented by a set of nodes {\bf w}_j in the same space. Each datapoint s \in {\mathcal S} has a host node, namely the closest node {\bf w}_j (if there are several closest nodes then one takes the node with the smallest number). The data set {\mathcal S} is divided into classes K_j={s \ | \ {\bf w}_j \mbox{ is a host of } s}.

The approximation energy D is the distortion : D=\frac{1}{2}\sum_{j=1}^k \sum_{s \in K_j}|s-{\bf w}_j|^2, which is the energy of the springs with unit elasticity which connect each data point with its host node. It is possible to apply weighting factors to the terms of this sum, for example to reflect the standard deviation of the probability density function of any subset of data points {s_i}.

On the set of nodes an additional structure is defined. Some pairs of nodes, ({\bf w}_i,{\bf w}_j), are connected by elastic edges. Call this set of pairs E. Some triplets of nodes, ({\bf w}_i,{\bf w}j,{\bf w}k), form bending ribs. Call this set of triplets G. : The stretching energy is U{E}=\frac{1}{2}\lambda \sum{({\bf w}_i,{\bf w}_j) \in E} |{\bf w}_i -{\bf w}j|^2 , : The bending energy is U_G=\frac{1}{2}\mu \sum{({\bf w}_i,{\bf w}_j,{\bf w}_k) \in G} |{\bf w}_i -2{\bf w}_j+{\bf w}_k|^2 , where \lambda and \mu are the stretching and bending moduli respectively. The stretching energy is sometimes referred to as the membrane, while the bending energy is referred to as the thin plate term.

For example, on the 2D rectangular grid the elastic edges are just vertical and horizontal edges (pairs of closest vertices) and the bending ribs are the vertical or horizontal triplets of consecutive (closest) vertices. : The total energy of the elastic map is thus U=D+U_E+U_G. The position of the nodes {{\bf w}_j} is determined by the mechanical equilibrium of the elastic map, i.e. its location is such that it minimizes the total energy U.

Expectation-maximization algorithm

For a given splitting of dataset {\mathcal S} in classes K_j, minimization of the quadratic functional U is a linear problem with the sparse matrix of coefficients. Therefore, similar to principal component analysis or k-means, a splitting method is used:

• For given {{\bf w}_j} find {K_j};
• For given {K_j} minimize U and find {{\bf w}_j};
• If no change, terminate.

This expectation-maximization algorithm guarantees a local minimum of U. For improving the approximation various additional methods are proposed. For example, the softening strategy is used. This strategy starts with a rigid grids (small length, small bending and large elasticity modules \lambda and \mu coefficients) and finishes with soft grids (small \lambda and \mu ). The training goes in several epochs, each epoch with its own grid rigidness. Another adaptive strategy is growing net: one starts from a small number of nodes and gradually adds new nodes. Each epoch goes with its own number of nodes.

Applications

Most important applications of the method and free software for exploratory data analysis and visualisation of multidimensional data, for data visualisation in economics, social and political sciences, as an auxiliary tool for data mapping in geographic informational systems and for visualisation of data of various nature.

The method is applied in quantitative biology for reconstructing the curved surface of a tree leaf from a stack of light microscopy images. This reconstruction is used for quantifying the geodesic distances between trichomes and their patterning, which is a marker of the capability of a plant to resist to pathogenes.

Recently, the method is adapted as a support tool in the decision process underlying the selection, optimization, and management of financial portfolios.

The method of elastic maps has been systematically tested and compared with several machine learning methods on the applied problem of identification of the flow regime of a gas-liquid flow in a pipe. There are various regimes: Single phase water or air flow, Bubbly flow, Bubbly-slug flow, Slug flow, Slug-churn flow, Churn flow, Churn-annular flow, and Annular flow. The simplest and most common method used to identify the flow regime is visual observation. This approach is, however, subjective and unsuitable for relatively high gas and liquid flow rates. Therefore, the machine learning methods are proposed by many authors. The methods are applied to differential pressure data collected during a calibration process. The method of elastic maps provided a 2D map, where the area of each regime is represented. The comparison with some other machine learning methods is presented in Table 1 for various pipe diameters and pressure.

Here, ANN stands for the backpropagation artificial neural networks, SVM stands for the support vector machine, SOM for the self-organizing maps. The hybrid technology was developed for engineering applications. In this technology, elastic maps are used in combination with Principal Component Analysis (PCA), Independent Component Analysis (ICA) and backpropagation ANN.

The textbook provides a systematic comparison of elastic maps and self-organizing maps (SOMs) in applications to economic and financial decision-making.

References

References

1. A. N. Gorban, A. Y. Zinovyev, [https://arxiv.org/abs/0809.0490 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.
2. Wang, Y., Klijn, J.G., Zhang, Y., Sieuwerts, A.M., Look, M.P., Yang, F., Talantov, D., Timmermans, M., Meijer-van Gelder, M.E., Yu, J. et al.: Gene expression profiles to predict distant metastasis of lymph-node-negative primary breast cancer. Lancet 365, 671–679 (2005); [https://www.ihes.fr/~zinovyev/princmanif2006/ Data online]
3. A. Zinovyev, [http://bioinfo-out.curie.fr/projects/vidaexpert/ ViDaExpert] - Multidimensional Data Visualization Tool (free for non-commercial use). [[Curie Institute (Paris). Institut Curie]], Paris.
4. A. Zinovyev, [https://www.ihes.fr/~zinovyev/vida/ViDaExpert/ViDaOverView.pdf ViDaExpert overview], IHES ([[Institut des Hautes Études Scientifiques]]), Bures-Sur-Yvette, Île-de-France.
5. Michael Kass, Andrew Witkin, Demetri Terzopoulos, Snakes: Active contour models, Int.J. Computer Vision, 1988 vol 1-4 pp.321-331
6. A. N. Gorban, A. Zinovyev, [https://arxiv.org/abs/1001.1122 Principal manifolds and graphs in practice: from molecular biology to dynamical systems], [[International Journal of Neural Systems]], Vol. 20, No. 3 (2010) 219–232.
7. are in bioinformaticsA.N. Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), [http://pca.narod.ru/contentsgkwz.htm Principal Manifolds for Data Visualisation and Dimension Reduction], LNCSE 58, Springer: Berlin – Heidelberg – New York, 2007. {{ISBN. 978-3-540-73749-0
8. M. Chacón, M. Lévano, H. Allende, H. Nowak, [http://pca.narod.ru/ElNetChakon.pdf Detection of Gene Expressions in Microarrays by Applying Iteratively Elastic Neural Net], In: B. Beliczynski et al. (Eds.), Lecture Notes in Computer Sciences, Vol. 4432, Springer: Berlin – Heidelberg 2007, 355–363.
9. A. Zinovyev, [https://arxiv.org/abs/1008.1188 Data visualization in political and social sciences], In: SAGE [http://knowledge.sagepub.com/view/intlpoliticalscience/n129.xml "International Encyclopedia of Political Science"], Badie, B., Berg-Schlosser, D., Morlino, L. A. (Eds.), 2011.
10. H. Failmezger, B. Jaegle, A. Schrader, M. Hülskamp, A. Tresch., [http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fjournal.pcbi.1003029#pcbi-1003029-g005 Semi-automated 3D leaf reconstruction and analysis of trichome patterning from light microscopic images], PLoS Computational Biology, 2013, 9(4):e1003029.
11. M. Resta, [https://doi.org/10.1007%2F978-3-540-74827-4_80 Portfolio optimization through elastic maps: Some evidence from the Italian stock exchange], Knowledge-Based Intelligent Information and Engineering Systems, B. Apolloni, R.J. Howlett and L. Jain (eds.), Lecture Notes in Computer Science, Vol. 4693, Springer: Berlin – Heidelberg, 2010, 635-641.
12. H. Shaban, S. Tavoularis, [http://www.sciencedirect.com/science/article/pii/S0301932214000159 Identification of flow regime in vertical upward air–water pipe flow using differential pressure signals and elastic maps], International Journal of Multiphase Flow 61 (2014) 62-72.
13. H. Shaban, S. Tavoularis, [https://dx.doi.org/10.1016/j.ijmultiphaseflow.2014.08.012 Measurement of gas and liquid flow rates in two-phase pipe flows by the application of machine learning techniques to differential pressure signals], International Journal of Multiphase Flow 67(2014), 106-117
14. M. Resta, [https://www.springer.com/gp/book/9783319214399 Computational Intelligence Paradigms in Economic and Financial Decision Making], Series Intelligent Systems Reference Library, Volume 99, Springer International Publishing, Switzerland 2016.