關(guān)于DTW算法
動態(tài)時間規(guī)整/規(guī)劃(Dynamic Time Warping, DTW)是一個比較老的算法无牵，大概在1970年左右被提出來腰涧，最早用于處理語音方面識別分類的問題神凑。
這里有兩篇我認(rèn)為講的很好的DTW算法詳解辅愿，鏈接在此：
如果對DTW算法感興趣可以去看一下~
https://www.cnblogs.com/Daringoo/p/4095508.html
http://blog.csdn.net/raym0ndkwan/article/details/45614813
在這里我主要用python實現(xiàn)了DTW算法
# -*- coding: UTF-8 -*-
from numpy import array, zeros, argmin, inf, equal, ndim
# from scipy.spatial.distance import cdist
from sklearn.metrics.pairwise import manhattan_distances
#在這里我用到的是曼哈頓距離(求絕對值距離)
#如果比較的是二維數(shù)組谈山，則用歐幾里得距離
s1 = [1, 2, 3, 4, 5, 5, 5, 4]
s2 = [3, 4, 5, 5, 5, 4]
r, c = len(s1), len(s2)
D0 = zeros((r+1,c+1))
D0[0,1:] = inf
D0[1:,0] = inf
D1 = D0[1:,1:]
#淺復(fù)制
# print D1
for i in range(r):
for j in range(c):
D1[i,j] = manhattan_distances(s1[i],s2[j])
#生成原始距離矩陣
M = D1.copy()
for i in range(r):
for j in range(c):
D1[i,j] += min(D0[i,j],D0[i,j+1],D0[i+1,j])
#代碼核心俄删，動態(tài)計算最短距離
i,j = array(D0.shape) - 2
#最短路徑
# print i,j
p,q = [i],[j]
while(i>0 or j>0):
tb = argmin((D0[i,j],D0[i,j+1],D0[i+1,j]))
if tb==0 :
i-=1
j-=1
elif tb==1 :
i-=1
else:
j-=1
p.insert(0,i)
q.insert(0,j)
print M
#原始距離矩陣
print zip(p,q)
#匹配路徑過程
print D1
#Cost Matrix或者叫累積距離矩陣
print D1[-1,-1]
#序列距離
M:
[[ 2. 3. 4. 4. 4. 3.]
[ 1. 2. 3. 3. 3. 2.]
[ 0. 1. 2. 2. 2. 1.]
[ 1. 0. 1. 1. 1. 0.]
[ 2. 1. 0. 0. 0. 1.]
[ 2. 1. 0. 0. 0. 1.]
[ 2. 1. 0. 0. 0. 1.]
[ 1. 0. 1. 1. 1. 0.]]
path:
[(0, 0), (1, 0), (2, 0), (3, 1), (4, 2), (5, 3), (6, 4), (7, 5)]
D1:
[[ 2. 5. 9. 13. 17. 20.]
[ 3. 4. 7. 10. 13. 15.]
[ 3. 4. 6. 8. 10. 11.]
[ 4. 3. 4. 5. 6. 6.]
[ 6. 4. 3. 3. 3. 4.]
[ 8. 5. 3. 3. 3. 4.]
[ 10. 6. 3. 3. 3. 4.]
[ 11. 6. 4. 4. 4. 3.]]
D1[-1,-1]:
3.0
