DTW算法的python实现

关于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