首页 / 算法 / DTW算法Python实现

DTW算法Python实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了DTW算法Python实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1396字，纯文字阅读大概需要2分钟。

内容图文

DTW算法可以用来衡量两个时间序列的相似性，而且两个时间序列的长度可以不必相等。

DTW算法原理

如图1所示，图中矩阵$dij$表示时间序列$A$时刻$i$和时间序列$B$时刻$j$的距离，DTW算法就是要从$(1,1)$到$(m,n)$找到一条路径使得累计$dij$最小。

技术分享图片

图1：DTW算法示意图，r表示warping window，红色圆点表示累计距离最小的路径。

如何找到这条路径呢，我们这里采用动态规划算法。假设我们要求到位置$(i,j)$的最小累计距离$D(i,j)$，那么它只能由$D(i-1,j)$，$D(i,j-1)$和$D(i,j)$这三个位置的最小累计距离中寻找，也就是$D(i,j)=dij+min[D(i-1,j),D(i,j-1),D(i,j)]$。如图2所示，最优路径只能从三个临近位置寻找。最终，$D(m,n)$越小，表示两个时间序列间的相似性越高。

技术分享图片

图2：动态规划算法寻找最小累计距离路径的三种可能

DTW算法的Python实现 

            
                def dtw_distance(ts_a, ts_b, d=lambda x,y: abs(x-y), mww=10000):
    """Computes dtw distance between two time series
    
    Args:
        ts_a: time series a
        ts_b: time series b
        d: distance function
        mww: max warping window, int, optional (default = infinity)
        
    Returns:
        dtw distance
    """# Create cost matrix via broadcasting with large int
    ts_a, ts_b = np.array(ts_a), np.array(ts_b)
    M, N = len(ts_a), len(ts_b)
    cost = np.ones((M, N))

    # Initialize the first row and column
    cost[0, 0] = d(ts_a[0], ts_b[0])
    for i in range(1, M):
        cost[i, 0] = cost[i-1, 0] + d(ts_a[i], ts_b[0])

    for j in range(1, N):
        cost[0, j] = cost[0, j-1] + d(ts_a[0], ts_b[j])

    # Populate rest of cost matrix within windowfor i in range(1, M):
        for j in range(max(1, i - mww), min(N, i + mww)):
            choices = cost[i-1, j-1], cost[i, j-1], cost[i-1, j]
            cost[i, j] = min(choices) + d(ts_a[i], ts_b[j])

    # Return DTW distance given window return cost[-1, -1]

 

原文：https://www.cnblogs.com/ningjing213/p/10502519.html

内容总结

以上是互联网集市为您收集整理的DTW算法Python实现全部内容，希望文章能够帮你解决DTW算法Python实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1139294.html

来源：【匿名】