nearOptimalPaths

dtw.nearOptimalPaths(d, threshold=None, max_paths=10000)

List nearly-optimal warping paths

Enumerate all the warping paths whose cumulative distance does not exceed a given threshold, i.e. the optimal alignment and its runners-up.

Details

[dtw()] returns one path of least cumulative distance. Other paths may be equally good (ties) or only slightly worse. Listing them shows how well determined the alignment is: parts of the warping curve shared by all the nearly-optimal paths are robust, while parts where they spread out are not.

The paths are found with the algorithm of Waterman and Byers (1985). Paths are grown backwards from the end of the alignment. A partial path is extended to a cell only if it can still be completed within threshold. This is known from the cumulative cost matrix, which holds the cost of the best path reaching each cell. No time is spent on paths that are later discarded, so the run time is proportional to the size of the output.

The problem parameters (local cost matrix, step pattern, window, open end) are taken from d, which must be computed with keep_internals=True. The alignment found by [dtw()] is not used.

Open-end alignments are supported with "N"-normalizable step patterns (see [stepPattern()]), for which ranking paths by distance or by normalized distance gives the same order. Paths may then end at any column of the last row. Open-begin alignments are not supported.

Distances are compared with a small tolerance, proportional to the rounding error expected when adding up a path (of the order of N+M times the machine epsilon, relative to threshold). This ensures that the default threshold returns all the optimal paths. The distance of the path found by [dtw()] is identical to d.distance.

The number of paths grows exponentially with the size of the problem (see [countPaths()]), so thresholds far from the optimum can produce very many paths, even for short timeseries. max_paths guards against running out of memory.

Parameters:

  • d – an object of class dtw, computed with keep_internals=True

  • threshold – list paths whose cumulative distance (not normalized) is less than or equal to this value. The default (None) is d.distance, which lists the optimal paths, including ties.

  • max_paths – stop with an error if more than this many paths are within the threshold

Returns:

  • A list of paths, sorted by increasing distance. Each element is a DTW

  • object with the fields index1, index2, index1s, index2s, stepsTaken,

  • distance and normalizedDistance, which have the same meaning as in [dtw()]

  • objects. The list is empty if threshold is below the optimal

  • distance. Otherwise, the first element is the path found by [dtw()], and

  • other paths with equal distance follow in an unspecified order.

References

Michael S. Waterman, Thomas H. Byers. A dynamic programming algorithm to find all solutions in a neighborhood of the optimum. Mathematical Biosciences, 77(1-2), 179-188, 1985. doi:10.1016/0025-5564(85)90096-3

Examples

>>> from dtw import *
>>> import numpy as np

Compute the optimal alignment

>>> ds = dtw(np.arange(1, 8) + 2, np.arange(1, 9),
...          keep_internals=True, step_pattern=asymmetric)

There are 126 possible paths. List them all.

>>> allPaths = nearOptimalPaths(ds, threshold=np.inf)
>>> len(allPaths) == countPaths(ds)
True

How many paths have each distance

>>> np.unique([p.distance for p in allPaths], return_counts=True)[1]
array([ 1,  6, 10, 10, 11, 12, 13, 13, 12, 11,  9,  7,  5,  3,  2,  1])

The best path is the one found by dtw()

>>> np.array_equal(allPaths[0].index2, ds.index2)
True

Paths at most 1 unit worse than the optimum

>>> nearPaths = nearOptimalPaths(ds, threshold=ds.distance + 1)
>>> import matplotlib.pyplot as plt
>>> for p in nearPaths:
...     plt.plot(p.index1, p.index2, color="grey")
>>> plt.plot(ds.index1, ds.index2, color="red", lw=2)
>>> plt.xlabel("Query index"); plt.ylabel("Reference index")