為何需要使用動態時間校正

在前面的文章中有提到歐幾里德距離(Euclidean distance)，此計算方式適用於x和y兩個向量具有相同長度的情況。

若向量的長度不同，他們之間的距離便不能使用上述的數學式來計算。而時間序列中，每個元素的位置含有時間的概念，為了要計算不同時間序列之間的相似程度，因此我們會選擇適用此資料的計算方法，其中常見的方法則為動態時間校正(DTW)。

DTW優點為：可適用於不同長度的時間序列

假設有兩個向量為t(長度為N)與r(長度為M)，DTW的工作就是要找出一條最短路徑，使得兩向量之間的距離最小(如下圖)。

圖片來源：連結

DTW的路徑需滿足的條件：

1. 端點：頭對頭(p1,q1) = (1,1)、尾對尾 (pk,qk) = (N,M)
2. 局部：假設某一點D(i,j)為最佳路徑上的一個點，其前一點的路徑僅會有三種可能，分別為D(i-1,j), D(i-1,j-1), D(i,j-1)
   
   圖片來源：連結

DTW步驟

1. 首先定義距離表示符號：D(i,j)為t_i與r_j之間的距離
2. 利用遞迴找出向量t和r之間的最小累積距離值A(N,M)

在實際運算中，會先建立一個矩陣D，維度為N*M，然後根據遞迴式，逐行或逐列算出 D(i, j) 的值，最後就可以得到我們所要的答案 D(N, M)

實作

R: dtw套件中的dtw

library(dtw) 
ts1 <- dataset2$alx[which(dataset2$Activity == 1 & dataset2$subject == 'subject1')]
ts2 <- dataset2$alx[which(dataset2$Activity == 1 & dataset2$subject == 'subject2')]
ts3 <- dataset2$alx[which(dataset2$Activity == 1 & dataset2$subject == 'subject3')]
ts4 <- dataset2$alx[which(dataset2$Activity == 11 & dataset2$subject == 'subject1')]
ts5 <- dataset2$alx[which(dataset2$Activity == 12 & dataset2$subject == 'subject1')]

print(paste ('ts1 vs. ts2:',dtw(ts1,ts2)$distance))
print(paste ('ts1 vs. ts3:',dtw(ts1,ts3)$distance))
print(paste ('ts1 vs. ts4:',dtw(ts1,ts4)$distance)) 
print(paste ('ts1 vs. ts5:',dtw(ts1,ts5)$distance))
# "ts1 vs. ts2: 8707.25039"
# "ts1 vs. ts3: 13213.34235655"
# "ts1 vs. ts4: 30161.50823809"
# "ts1 vs. ts5: 8173.46872443999"

Python:fastdtw套件中的fastdtw

# 挑選不同人同一個動作的加速度值(x軸)
ts1 = dataset2['alx'][dataset2.index[(dataset2.Activity == 1) & (dataset2.subject == 'subject1')]]
ts2 = dataset2['alx'][dataset2.index[(dataset2.Activity == 1) & (dataset2.subject == 'subject2')]]
ts3 = dataset2['alx'][dataset2.index[(dataset2.Activity == 1) & (dataset2.subject == 'subject3')]]
# 挑選同一人不同動作的加速度值(x軸)
ts4 = dataset2['alx'][dataset2.index[(dataset2.Activity == 11) & (dataset2.subject == 'subject1')]]
ts5 = dataset2['alx'][dataset2.index[(dataset2.Activity == 12) & (dataset2.subject == 'subject1')]]

from fastdtw import fastdtw
from scipy.spatial.distance import euclidean
import math
## 歐式距離 -> 序列長度不同無法比較
def euclid_dist(t1,t2):
    return math.sqrt(sum((t1-t2)**2))

print('ts1 vs. ts2:',euclid_dist(t1,t2))  #ts1 vs. ts2: nan
print('ts1 vs. ts3:',euclid_dist(t1,t3))  #ts1 vs. ts3: nan

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

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

distance3, path3 = fastdtw(ts1, ts4)
print('ts1 vs. ts4:',distance3)

distance4, path4 = fastdtw(ts1, ts5)
print('ts1 vs. ts5:',distance4)

#ts1 vs. ts2: 5541.172390000022
#ts1 vs. ts3: 8417.331238550001
#ts1 vs. ts4: 30240.011998089958
#ts1 vs. ts5: 10811.13639443998

根據DTW的計算結果，可知道同一個人不同動作的差異非常大。