Local Multidimensional Scaling for Nonlinear Dimension Reduction, Graph Drawing, and Proximity Analysis
- 1 March 2009
- journal article
- Published by Taylor & Francis Ltd in Journal of the American Statistical Association
- Vol. 104 (485), 209-219
- https://doi.org/10.1198/jasa.2009.0111
Abstract
In the past decade there has been a resurgence of interest in nonlinear dimension reduction. Among new proposals are “Local Linear Embedding,” “Isomap,” and Kernel Principal Components Analysis which all construct global low-dimensional embeddings from local affine or metric information. We introduce a competing method called “Local Multidimensional Scaling” (LMDS). Like LLE, Isomap, and KPCA, LMDS constructs its global embedding from local information, but it uses instead a combination of MDS and “force-directed” graph drawing. We apply the force paradigm to create localized versions of MDS stress functions with a tuning parameter to adjust the strength of nonlocal repulsive forces. We solve the problem of tuning parameter selection with a meta-criterion that measures how well the sets of K-nearest neighbors agree between the data and the embedding. Tuned LMDS seems to be able to outperform MDS, PCA, LLE, Isomap, and KPCA, as illustrated with two well-known image datasets. The meta-criterion can also be used in a pointwise version as a diagnostic tool for measuring the local adequacy of embeddings and thereby detect local problems in dimension reductions.Keywords
This publication has 23 references indexed in Scilit:
- Data Visualization With Multidimensional ScalingJournal of Computational and Graphical Statistics, 2008
- PARAMAP vs. Isomap: A Comparison of Two Nonlinear Mapping AlgorithmsJournal of Classification, 2006
- Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion mapsProceedings of the National Academy of Sciences of the United States of America, 2005
- Nonrigid Embeddings for Dimensionality ReductionLecture Notes in Computer Science, 2005
- Laplacian Eigenmaps for Dimensionality Reduction and Data RepresentationNeural Computation, 2003
- Hessian eigenmaps: Locally linear embedding techniques for high-dimensional dataProceedings of the National Academy of Sciences of the United States of America, 2003
- Visualization Methodology for Multidimensional ScalingJournal of Classification, 2002
- Prosection Views: Dimensional Inference through Sections and ProjectionsJournal of Computational and Graphical Statistics, 1994
- Principal CurvesJournal of the American Statistical Association, 1989
- Using distance information in the design of large multidimensional scaling experiments.Psychological Bulletin, 1979