|
Spatio-temporal Isomap: A time-series extension to Isomap dimension reduction
|
Spatio-temporal Isomap (ST-Isomap) is an algorithm for registering a single time-series (or a set of time-series) against itself such that data points X corresponding to similar phases of the underlying spatio-temporal process are aligned (placed in close proximity within an estimated embedding Y). This algorithm emphasizes the notion of a registration kernel, where pairwise distance is indicative of how well two points align in space and time, and estimation of new coordinates that preserve distances produced by this kernel. These distances are indicative of the dynamics underlying a given time-series and embedded using multidimensional scaling (MDS).
Our similarity kernel, D(x,x'), first compares the near-term similarity between a data pair (x and x') with Euclidean distance over a fixed horizon. If two data points exhibit sufficiently similar near-term dynamics, these points are identified as common temporal neighbors (CTN), representing similar phases of the underlying spatio-process that should be registered into alignment. The registration of CTN data pairs occurs by sharply reducing their local distances between their connecting edges in a neighborhood graph, which is propagated globally by computing the shortest path betweeen all pairs in this graph. By reducing CTN distances, the resulting distance matrix reflects a transitive effect where points connected by a path of CTN relationships are registered. Registration in this case implies that pair of points connected by a CTN path has a significantly smaller distance that any pair not connected by a CTN path.
When embedding distance matrix through MDS, points representative of the same phase in the dynamics will cluster into close proximity in the resulting coordinate space. The output coordinates $Y$ can be informally described as a ``$1+\epsilon$-manifold'' curve in an embedding space, where a collection of 1-manifolds are connected at intersecting junction points (illustrated in the example below).
Matlab code for ST-Isomap is available in this zip archive. Apologies in advance for the rough state of this code and the number of windows that will be output.
Results for the example dataset (a 2D "mouse crescent" trajectory) in this code is shown in the image below. Caption: (a) a 2D mouse-click trajectory color coded from blue to red to indicate progress through time. (b) Embedding of the trajectory using standard (spatial) Isomap. (c,d) Two views of the ``windowed PCA'' for data with extended horizons and no registration. (e,f) Two ST-Isomap embeddings illustrating the time-series registration that occurs from higher c_{ctn}$ values. (g,h) The spatio-temporal correspondences (neighbors) and the spatio-temporal distance matrix computed by ST-Isomap.
Click for PDF
Sponsors