====== Dynamic Time Warping ======

Dynamic Time warping is a distance based algorithm that allows you to compare and measure similarity between two time based sequences, by minimizing the Euclidean distance between points. Essentially, it aligns each point of one trace to a corresponding point on the other trace that require the least distance. All distances are added together to make the total cost function of the trace. The larger the cost function, the less similar the two traces are. This can be useful when trying to identify a singular trace or to find outliers. To review supporting literature, see [[https://ieeexplore.ieee.org/document/7023364|[1]]].

{{:DTWAlign.png}}

==== Mathematics of Dynamic Time Warping ====

Say you had a trace x of size N, and a trace y of size M, this is how you would calculate the cost matrix:

{{:DTWeq.png}}

where d() is equal to the absolute distance.

To speed up the computational cost a Lower Bound Keogh algorithm was implemented.

==== Computing Dynamic Time Warping in Sift ====

In Sift you can use Dynamic Time Warping two different ways for your analyses.

The first way to use Dynamic Time warping is by finding anomalies within your dataset. Within a data set, each trace will be compared to every other trace. Traces with a median distance that is a specified standard deviation away from the average will be identified as an anomaly. This function is useful when trying to identify particular moments that may be interesting to look at or by quickly cleaning your dataset from outliers.

In this example we have used Dynamic Time Warping to find anomalies within all workspaces of AnkleAngleX. The results have given us a list of the traces identified as anomalies and their corresponding cost function. If we have the group plotted, these traces will also be selected. After a quick visual check we can press the **Exclude Anomalies** button and they will be exclude from the group.

{{:DTWAnomalies.png}}

\\
The second way to use Dynamic Time Warping is by comparing a specific trace. This can be done if you want to find what trace is most similar to another.

In this example we found that the trace - AnkleAngleX/Sub02Workspace/TM_LKrunT2_2.c3d/LAnkleAngle/frames_439,546 is most similar to AnkleAngleX/Sub01Workspace/OG_LA_run02.c3d/frames_454,578.

{{:DTWTrace.png}}

=== Exporting Results ===

Results for each dynamic time warping test can be exported in the {{:sift_export_results.png}} [[Sift:Export:Export_Results_Dialog|Export Results Dialog]].

==== References ====

[1] F. Petitjean, G. Forestier, G. I. Webb, A. E. Nicholson, Y. Chen and E. Keogh, "Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification," 2014 IEEE International Conference on Data Mining, Shenzhen, China, 2014, pp. 470-479, doi: 10.1109/ICDM.2014.27.