Topological Stability: a New Algorithm for Selecting The Nearest
  Neighbors in Non-Linear Dimensionality Reduction Techniques
  In the machine learning field, dimensionality reduction is an important task.
It mitigates the undesired properties of high-dimensional spaces to facilitate
classification, compression, and visualization of high-dimensional data. During
the last decade, researchers proposed many new (non-linear) techniques for
dimensionality reduction. Most of these techniques are based on the intuition
that data lies on or near a complex low-dimensional manifold that is embedded
in the high-dimensional space. New techniques for dimensionality reduction aim
at identifying and extracting the manifold from the high-dimensional space.
Isomap is one of widely-used low-dimensional embedding methods, where geodesic
distances on a weighted graph are incorporated with the classical scaling
(metric multidimensional scaling). The Isomap chooses the nearest neighbours
based on the distance only which causes bridges and topological instability. In
this paper, we propose a new algorithm to choose the nearest neighbours to
reduce the number of short-circuit errors and hence improves the topological
stability. Because at any point on the manifold, that point and its nearest
neighbours form a vector subspace and the orthogonal to that subspace is
orthogonal to all vectors spans the vector subspace. The prposed algorithmuses
the point itself and its two nearest neighbours to find the bases of the
subspace and the orthogonal to that subspace which belongs to the orthogonal
complementary subspace. The proposed algorithm then adds new points to the two
nearest neighbours based on the distance and the angle between each new point
and the orthogonal to the subspace. The superior performance of the new
algorithm in choosing the nearest neighbours is confirmed through experimental
work with several datasets.
