关于DTW算法
动态时间规整/规划(Dynamic Time Warping, DTW)是一个比较老的算法，大概在1970年左右被提出来，最早用于处理语音方面识别分类的问题。
这里有两篇我认为讲的很好的DTW算法详解，链接在此：
如果对DTW算法感兴趣可以去看一下~
https://www.cnblogs.com/Daringoo/p/4095508.html
http://blog.csdn.net/raym0ndkwan/article/details/45614813
在这里我主要用python实现了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
#在这里我用到的是曼哈顿距离(求绝对值距离)
#如果比较的是二维数组，则用欧几里得距离
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:]
#浅复制
# 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])
#代码核心，动态计算最短距离
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
