What is Dynamic Time Warping?

hard

Answer

$Similarity between two sequences allowing non-linear alignment (stretch/compress).$
$Finds the best matching via dynamic programming through a cost matrix.$
$Robust to phase shifts and different lengths.$
$(\mathrm{mitigated}\;\mathrm{by}\;\mathrm{lower} - \mathrm{bounds}\;\mathrm{like}\;\mathrm{LB}_{\mathrm{Keogh}}, \;\mathrm{sakoe} - \mathrm{chiba}\;\mathrm{constraint}\;\mathrm{window})$
$Standard for shape-based time-series similarity in speech, ECG, gesture recognition.$

Check yourself — multiple choice

Same as Euclidean
DP alignment allowing stretch/compress → phase-shift-robust sequence distance; O(mn); $\mathrm{LB}_{\mathrm{Keogh}}\; / \;\mathrm{warping}$ window for scale
Random
Not real

DTW: dynamic-programming alignment; robust to phase shifts.

#clustering#similarity

214 interview questions in this topic.