Quality assessment of dimensionality reduction: Rank-based criteria

Lee, John Aldo [UCL] Verleysen, Michel [UCL]

Dimensionality reduction aims at providing low-dimensional representations of high-dimensional data sets. Many new nonlinear methods have been proposed for the last years, yet the question of their assessment and comparison remains open. This paper first reviews some of the existing quality measures that are based on distance ranking and K-ary neighborhoods. Next, the definition of the co-ranking matrix provides a tool for comparing the ranks in the initial data set and some low-dimensional embedding. Rank errors and concepts such as neighborhood intrusions and extrusions can then be associated with different blocks of the co-ranking matrix. Several quality criteria can be cast within this unifying framework: they are shown to involve one or several of these characteristic blocks. Following this line, simple criteria are proposed, which quantify two aspects of the embedding quality, namely its overall quality and its tendency to favor intrusions or extrusions. They are applied to several recent dimensionality reduction methods in two experiments, with both artificial and real data. (C) 2009 Elsevier B.V. All rights reserved.