In recent years there has been a resurgence of interest in nonlinear dimension reduction
methods. Among new proposals are so-called “Local Linear Embedding” (LLE)
and “Isomap”. Both use local neighborhood information to construct a global lowdimensional
embedding of a hypothetical manifold near which the data fall.
In this talk we will introduce a family of new nonlinear dimension reduction methods
called “Local Multidimensional Scaling” or LMDS. Like LLE and Isomap, LMDS only
uses local information from user-chosen neighborhoods, but it differs from them in that
it uses ideas from the area of “graph layout”. A common paradigm in graph layout is
to achieve desirable drawings of graphs by minimizing energy functions that balance
attractive forces between near points and repulsive forces between non-near points
against each other. We approach the force paradigm by proposing a parametrized
family of stress or energy functions inspired by Box-Cox power transformations. This
family provides users with considerable flexibility for achieving desirable embeddings,
and it comprises most energy functions proposed in the past.
Facing an embarrassment of riches of energy functions, however, one needs a method
for selecting viable energy functions. We solve this problem by proposing a metacriterion
that measures how well the sets of K-nearest neighbors agree between the
original high-dimensional space and the low-dimensional embedding space.This metacriterion
has intuitive appeal, and it performs well in creating faithful embeddings.