Topology Preservation Measures in the Visualization of Manifold-Type Multidimensional Data

Article type: Research Article

Authors: Karbauskaitė, Rasa | Dzemyda, Gintautas

Affiliations: Institute of Mathematics and Informatics, Akademijos 4, 08663 Vilnius, Lithuania, e-mail: {karbauskaite, dzemyda}@ktl.mii.lt

Abstract: Most of real-life data are not often truly high-dimensional. The data points just lie on a low-dimensional manifold embedded in a high-dimensional space. Nonlinear manifold learning methods automatically discover the low-dimensional nonlinear manifold in a high-dimensional data space and then embed the data points into a low-dimensional embedding space, preserving the underlying structure in the data. In this paper, we have used the locally linear embedding method on purpose to unravel a manifold. In order to quantitatively estimate the topology preservation of a manifold after unfolding it in a low-dimensional space, some quantitative numerical measure must be used. There are lots of different measures of topology preservation. We have investigated three measures: Spearman's rho, Konig's measure (KM), and mean relative rank errors (MRRE). After investigating different manifolds, it turned out that only KM and MRRE gave proper results of manifold topology preservation in all the cases. The main reason is that Spearman's rho considers distances between all the pairs of points from the analysed data set, while KM and MRRE evaluate a limited number of neighbours of each point from the analysed data set.

Keywords: dimensionality reduction, manifold learning, multidimensional data visualization, locally linear embedding, topology preservation

Journal: Informatica, vol. 20, no. 2, pp. 235-254, 2009