WarpingCorrespondence
WarpingCorrespondence[s1,s2]
gives the time warping (DTW) similarity path between sequences s1 and s2.
WarpingCorrespondence[s1,s2,win]
uses a window specified by win for local search.
Details and Options
- WarpingCorrespondence is also known as dynamic time warping.
- WarpingCorrespondence returns {{n1,…,nk},{m1,…,mk}} of nondecreasing positions such that s1〚ni〛 correspond to s2〚mi〛.
- The returned positions attempt to minimize the distance
over all possible such positions, and with the constraint that all elements of s1 and s2 are represented as some s1〚ni〛 and s2〚mj〛, respectively. - Compute the effective distance using WarpingDistance.
- The sequences si can be lists of numeric or Boolean scalars or vectors.
- Possible settings for the search window win are:
-
Automatic a full search 
r a slanted band window of radius 
{"SlantedBand",r} a slanted band window of radius 
{"Band",r} band window of radius 
(Sakoe-Chiba)
{"Parallelogram",a} parallelogram window placed at origin with slopes 
and 
(Itakura) - A smaller
typically gives a faster but less optimal result. If ![max(Length[s_1],Length[s_2])<=2 r +1](Files/WarpingCorrespondence.en/13.png "max(Length[s_1],Length[s_2])<=2 r +1")
, then 
has no effect. - The following options are supported:
-
DistanceFunction Automatic the distance function to be used Method Automatic the variant of DTW to use - WarpingCorrespondence accepts a DistanceFunctiond option with settings:
-
Automatic automatically determine distance function EuclideanDistance Euclidean distance ManhattanDistance Manhattan or "city block" distance BinaryDistance 0 if elements are equal; 1 otherwise ChessboardDistance Chebyshev or sup norm distance SquaredEuclideanDistance squared Euclidean distance NormalizedSquaredEuclideanDistance normalized squared Euclidean distance CosineDistance angular cosine distance CorrelationDistance correlation coefficient distance BrayCurtisDistance Total[Abs[u-v]]/Total[Abs[u+v]] CanberraDistance Total[Abs[u-v]/(Abs[u]+Abs[v])] MatchingDissimilarity matching dissimilarity between Boolean vectors - By default, the following distance functions are used:
-
EuclideanDistance numeric data MatchingDissimilarity Boolean data - Using Method->Automatic, all elements of s2 are matched with all elements of s1.
- Using Method->{"MatchingInterval"match}, s2 can be matched with a subsequence of s1. Possible settings for match include:
-
Automatic a full match "Flexible" flexible at both ends "FlexibleEnd" flexible only at the end of the interval
Examples
open all close allBasic Examples (1)
Find the time warping correspondence between two sequences:
s1 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6};
s2 = {1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7};{n, m} = WarpingCorrespondence[s1, s2]Plot the correspondence between indices:
ListLinePlot[{n, m}]Time-warped versions are approximately equal:
ListLinePlot[{s1[[n]], s2[[m]]}]Scope (9)
Data (6)
Find the time warping correspondence between two real-valued vectors:
WarpingCorrespondence[{Pi, E, E + Pi, -Pi / E}, {Pi ^ E, E - Pi, -E * Pi, E ^ Pi}]//TextGridFind the time warping correspondence between two sequences of vectors:
s1 = {{11, 12}, {13, 14}, {15, 16}};
s2 = {{12, 13}, {14, 15}};WarpingCorrespondence[s1, s2]//TextGridFind the time warping correspondence between two Boolean vectors:
s1 = PrimeQ /@ Range[1, 20]s2 = CoprimeQ[#, 6]& /@ Range[1, 20]WarpingCorrespondence[s1, s2]//ListLinePlotSequences of Boolean-valued vectors:
s1 = {{True, True, True}, {False, True, True}, {False, False, True}, {True, True, False}, {False, True, True}};
s2 = {{True, True, True}, {True, False, True}, {False, True, True}, {False, True, True}};WarpingCorrespondence[s1, s2]//TextGridSequences of quantities with compatible units:
s1 = QuantityArray[{1, 2.5, 4}, "Decimeters"];
s2 = {Quantity[0.1, "Kilometers"], Quantity[200, "Inches"]};WarpingCorrespondence[s1, s2]//TextGridTwo-dimensional quantity arrays:
s1 = QuantityArray[{{1, 2.5}, {4, 5}, {5, 4}}, {"Seconds", "Minutes"}]s2 = Table[Quantity[(i + j) / 60, "Hours"], {i, 5}, {j, 2}]WarpingCorrespondence[s1, s2]//TextGridSearch Window (3)
By default, the search is not locally constrained:
s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
s2 = {1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7};WarpingCorrespondence[s1, s2]//TextGridWarpingCorrespondence[s1, s2] == WarpingCorrespondence[s1, s2, Automatic]Specify a radius for the search window:
WarpingCorrespondence[s1, s2, 1]//TextGridA search radius of 2 allows you to find the optimal alignment:
WarpingCorrespondence[s1, s2, 2]//TextGrids1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
s2 = {1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};WarpingCorrespondence[s1, s2, {"Band", 1}]//TextGridUse a parallelogram of slope 3:
WarpingCorrespondence[s1, s2, {"Parallelogram", 3}]//TextGridFor signals of equal length, the "Band" window is equivalent to the "SlantedBand" window:
s1 = RealDigits[Pi, 10, 25]//First;
s2 = RealDigits[E, 10, 25]//First;WarpingCorrespondence[s1, s2, {"Band", 3}] == WarpingCorrespondence[s1, s2, {"SlantedBand", 3}]Options (4)
DistanceFunction (3)
With Boolean sequences, WarpingCorrespondence uses MatchingDissimilarity:
s1 = {{True, False, False}, {True, True, False}, {True, False, False}, {True, False, False}, {False, False, False}};
s2 = {{False, False, False}, {True, True, False}, {False, True, False}, {False, True, False}, {True, False, True}, {False, False, False}, {True, False, False}};WarpingCorrespondence[s1, s2]WarpingCorrespondence[s1, s2, DistanceFunction -> MatchingDissimilarity] == %Find correspondences between two sequences using different distance functions:
v1 = {50, 60, 70, 71, 71, 73, 75, 80, 80, 80, 78, 76, 75, 73, 71, 71, 71, 73, 75, 76, 76, 68, 76, 76, 75, 73};
v2 = {61, 62, 62, 64, 69, 69, 73, 75, 79, 80, 79, 78, 76, 73, 72, 71, 70, 70, 69, 69, 69, 71, 73, 75, 76};
distances = {EuclideanDistance, BinaryDistance, CorrelationDistance};ListLinePlot[Transpose[WarpingCorrespondence[v1, v2, DistanceFunction -> #]]& /@ distances, PlotLegends -> distances]In case of one-dimensional signals, some distance functions are equivalent:
s1 = Range[10];
s2 = Range[15];Euclidean, Manhattan, and the chessboard distance are always the same:
WarpingCorrespondence[s1, s2, DistanceFunction -> EuclideanDistance] == WarpingCorrespondence[s1, s2, DistanceFunction -> ManhattanDistance] == WarpingCorrespondence[s1, s2, DistanceFunction -> ChessboardDistance]Normalized Euclidean distance and correlation distance are the same:
WarpingCorrespondence[s1, s2, DistanceFunction -> NormalizedSquaredEuclideanDistance] == WarpingCorrespondence[s1, s2, DistanceFunction -> CorrelationDistance]For Boolean data, matching dissimilarity and binary distance are the same:
s1 = {True, False, True};
s2 = {False, False, True};WarpingCorrespondence[s1, s2, DistanceFunction -> MatchingDissimilarity] == WarpingCorrespondence[s1, s2, DistanceFunction -> BinaryDistance]Method (1)
Compare the result of full search to a flexible search:
query = Table[{Cos[a], Sin[a]}, {a, Range[10] * Pi / 5.}];
ref = PadLeft[PadRight[query, {15, 2}], {20, 2}];(openEnd = WarpingCorrespondence[ref, query, Method -> {"MatchingInterval" -> "FlexibleEnd"}])//TextGrid(full = WarpingCorrespondence[ref, query])//TextGridListLinePlot[{openEnd, full}, PlotLegends -> {"Relaxed DTW", "Strict DTW"},
GridLines -> {Range[20], Range[10]}, PlotStyle -> {Thickness[.03], Automatic}, PlotRange -> {{0, 21}, {0, 11}}]Applications (2)
Visualize the time warping correspondence by drawing lines between corresponding points:
timeWarpingPlot[s1_, s2_] :=
Module[{n, m},
{n, m} = WarpingCorrespondence[s1, s2];
ListLinePlot[{s1, s2}, PlotMarkers -> Automatic, Epilog -> {RGBColor[0.560181, 0.691569, 0.194885], Line@Transpose[{{n, s1[[n]]},
{m, s2[[m]]}}]}]
];{s1, s2} = {{1, 2, 3, 4, 5, 9}, {11, 9, 8, 9, 12, 14}};WarpingCorrespondence[s1, s2]timeWarpingPlot[s1, s2]Compare the first quarter of 2017 of the HPQ stock prices with historical data from 2010 to 2016:
recent = QuantityMagnitude[FinancialData["HPQ", {{2017, 1, 1}, {2017, 3, 31}}]["Values"]];history = FinancialData["HPQ", {{2010, 1, 1}, {2016, 12, 31}}, "DateValue"];
{histDates, hist} = {history["Dates"], QuantityMagnitude[history["Values"]]};Find the best matching subsequence of historical data:
{corrHist, corrRecent} = WarpingCorrespondence[hist, recent, Method -> {"MatchingInterval" -> "Flexible"}];Detect the historical interval most similar to quarter one of 2017:
{m, n} = corrHist[[{1, -1}]];
histDates[[{m, n}]]Visually compare recent data and the best historical match:
DateListPlot[{AssociationThread[Take[histDates[[m ;; n]], UpTo@Length[recent]], Take[recent, UpTo[n - m + 1]]], AssociationThread[histDates[[m ;; n]], hist[[m ;; n]]]}, ...]Predict the stock prices for the next 30 days based on historical data:
l = Length[recent];
colDat = ColorData[97];
offset = Last[recent] - hist[[n]];
hist30d = hist[[n ;; n + 30]];
ListLinePlot[{recent, {l + Range[31], hist30d + offset}, hist[[m ;; n]], {n - m + Range[31], hist30d}}, ...]Properties & Relations (7)
The two sequences need not have the same length:
WarpingCorrespondence[{1, 2, 3, 4, 5}, {1, 2, 3}]The warping path of two equal sequences goes along a diagonal line:
c = WarpingCorrespondence[Range[10], Range[10]];
ListPlot[c]Smaller values of the search window radius emphasize speed of computation:
s1 = Sin[Range[1000] / 50 * 2 * Pi];
s2 = Sin[Range[5, 1004] / 100 * 2 * Pi] + RandomReal[{-.1, .1}, 1000];w1 = WarpingCorrespondence[s1, s2, 10];//AbsoluteTiming//Firstw2 = WarpingCorrespondence[s1, s2];//AbsoluteTiming//FirstThere may be a tradeoff with quality of the computation:
ListLinePlot[{Legended[Transpose[w1], "r = 10"], Legended[Transpose[w2], "optimal warping"]}]When computing the full correspondence, WarpingCorrespondence is symmetric:
s1 = {1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7};
s2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6};
WarpingCorrespondence[s1, s2] == Reverse@WarpingCorrespondence[s2, s1]The function is not symmetric when matching subsequences:
WarpingCorrespondence[s1, s2, Method -> {"MatchingInterval" -> "Flexible"}] == Reverse@WarpingCorrespondence[s2, s1, Method -> {"MatchingInterval" -> "Flexible"}]Adding to or subtracting from values of one sequence may result in a different correspondence:
s1 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6};
s2 = {1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7};
res1 = WarpingCorrespondence[s1, s2];res2 = WarpingCorrespondence[s1, s2 - 2];
ListLinePlot[{res1, res2}, PlotLegends -> {"original signal", "translated signal"}]Adding to or subtracting from both sequences will not affect the result when distance function is induced by a norm (translation invariant):
s1 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6};
s2 = {1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7};This is true for Euclidean, Manhattan, and some more:
WarpingCorrespondence[s1, s2] == WarpingCorrespondence[s1 - 3, s2 - 3]Using distance functions that are not translation invariant may produce different correspondence:
res1 = WarpingCorrespondence[s1, s2, DistanceFunction -> BrayCurtisDistance];res2 = WarpingCorrespondence[s1 - 3, s2 - 3, DistanceFunction -> BrayCurtisDistance];
ListLinePlot[{res1, res2}, PlotLegends -> {"original signals", "translated signals"}]Relation with WarpingDistance:
s1 = Sin[Range[100] / 50 * 2 * Pi];
s2 = Sin[Range[5, 104] / 100 * 2 * Pi] + RandomReal[{-.1, .1}, 100];
distance = EuclideanDistance;{n, m} = WarpingCorrespondence[s1, s2, DistanceFunction -> distance];Find the time warped sequences using the correspondence:
l1 = s1[[n]];
l2 = s2[[m]];WarpingDistance gives the sum of all the distances between corresponding elements:
Total[MapThread[distance, {l1, l2}]] == WarpingDistance[s1, s2, DistanceFunction -> distance]Possible Issues (3)
All elements in the two sequences must be commensurate:
WarpingCorrespondence[{1, 2, 3}, {{1, 2}, {3, 4}, {5, 6}}]
Elements in the two sequences should be of the same type:
WarpingCorrespondence[{1, 2, 3}, {True, False, True}]
If the specified window is too narrow to find a correspondence, a larger window is automatically used:
s1 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6};
s2 = {1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7};
WarpingCorrespondence[s1, s2, {"Band", 1}]
Text
Wolfram Research (2016), WarpingCorrespondence, Wolfram Language function, https://reference.wolfram.com/language/ref/WarpingCorrespondence.html.
CMS
Wolfram Language. 2016. "WarpingCorrespondence." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/WarpingCorrespondence.html.
APA
Wolfram Language. (2016). WarpingCorrespondence. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/WarpingCorrespondence.html