Dynamic Time Warping (DTW)

DTW 是什麽

当要计算时间序列资料的相似程度时，我们可以使用不同的距离计算方式。DTW就是其中一种距离方式计算，他的优势在於：

1. 可以比较长度不同的资料：在实际生活里，通常我们想比较的资料长度都是不固定的
2. delay也不怕：比如可以计算出Ａ序列的第一个资料点（ta1)对应到Ｂ序列的第五个资料点(tb5)，强大的应用包括语音辨识（比较同一个人的说“hello”的方式，第一种正常说，第二种像树懒一样说出“Ｈeeeeeelllooooo”，DTW还是能侦测出你们是同一个人）

python：

我们先创造出三个相同长度的资料ts1, ts2, ts3，从图里我们可以很明显地看出ts1和ts2比较相似，第一种方法先透过最简单的euclidean distance计算相似度，跑出的结果却是ts1与ts3比较相近，因为euclidean distance仅考虑同个时间点下的两的序列直线距离，无法捕捉到趋势上的相似程度。

def euclid_dist(t1,t2):
    return sqrt(sum((t1-t2)**2))

print('ts1 vs. ts2:',euclid_dist(ts1,ts2))
print('ts1 vs. ts3:',euclid_dist(ts1,ts3))

接下来，我们来用用dtw，这个为了简洁方便我们就使用fastdtw package来计算：

from fastdtw import fastdtw
from scipy.spatial.distance import euclidean

distance, path = fastdtw(ts1, ts2)
print('ts1 vs. ts2:',distance)

distance2, path2 = fastdtw(ts1, ts3)
print('ts1 vs. ts3:',distance2)

我们可以发现dtw的计算结果正确地告诉我们ts1与ts3较为相近！以上只是dtw的简单小介绍，如果对背後的数学逻辑有兴趣也欢迎一起讨论～

dtw原理影片：
https://www.youtube.com/watch?v=9GdbMc4CEhE&t=551s

reference:
https://towardsdatascience.com/dynamic-time-warping-3933f25fcdd
https://pypi.org/project/fastdtw/
https://nbviewer.jupyter.org/github/alexminnaar/time-series-classification-and-clustering/blob/master/Time%20Series%20Classification%20and%20Clustering.ipynb