Local Multidimensional Scaling for Nonlinear Dimension Reduction, Graph Drawing, and Proximity Analysis

• 成果类型: Article
• 署名作者: Chen, Lisha; Buja, Andreas
• 署名单位: Yale University; University of Pennsylvania
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1198/jasa.2009.0111
• 发表日期: 2009
• 页码: 209-219
• 关键词: visualization; eigenmaps

摘要

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 timing 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.