Spectral dimensionality reduction is frequently used to identify low-dimensional structure in high-dimensional data. However, learning manifolds, especially from the streaming data, is computationally and memory expensive. In this paper, we argue that a stable manifold can be learned using only a fraction of the stream, and the remaining stream can be mapped to the manifold in a significantly less costly manner. Identifying the transition point at which the manifold is stable is the key step. We present error metrics that allow us to identify the transition point for a given stream by quantitatively assessing the quality of a manifold learned using Isomap. We further propose an efficient mapping algorithm, called S-Isomap, that can be used to map new samples onto the stable manifold. We describe experiments on a variety of data sets that show that the proposed approach is computationally efficient without sacrificing accuracy.
Errors in Isomap have been discussed in prior work @cite_12 , but those studies have been typically in regards to selection of parameters. For example, @cite_2 proposed measuring a simple manifold embedding error for a range of @math to find the best choice of @math . Similarly, an approach based on the @math -edge disjoint minimal spanning tree algorithm has been proposed to construct a neighborhood graph with connectivity guarantees @cite_9 . In the same spirit, several strategies to assess intrinsic manifold dimension @math are available @cite_12 . However, to the best of our knowledge there is no prior work in defining and understanding the behavior of error that persists even with the selection of optimal parameters. We address this error in taking an abstract view of Isomap, providing a protocol for measuring collective error, and understanding its behavior. In doing so we identify the optimal point where we may switch from exact to lightweight methods.
@cite_9 @cite_12 @cite_2
2132192618 2176206423 2055292465
Isometric data embedding requires construction of a neighborhood graph that spans all data points so that geodesic distance between any pair of data points could be estimated by distance along the shortest path between the pair on the graph. This paper presents an approach for constructing k-edge-connected neighborhood graphs. It works by finding k edge-disjoint spanning trees the sum of whose total lengths is a minimum. Experiments show that it outperforms the nearest neighbor approach for geodesic distance estimation. The isometric feature mapping (Isomap) method has demonstrated promising results in finding low-dimensional manifolds from data points in high-dimensional input space. Isomap has one free parameter (number of nearest neighbours K or neighbourhood radius @e), which has to be specified manually. In this paper we present a new method for selecting the optimal parameter value for Isomap automatically. Numerous experiments on synthetic and real data sets show the effectiveness of our method.