summerice9的个人博客分享 http://blog.sciencenet.cn/u/summerice9 用心记录身边的美好

博文

【科研速记】Dynamic time warping

已有 8496 次阅读 2013-6-19 23:19 |个人分类:科研速记|系统分类:科研笔记

DTW的作用

Dynamic time warping 简称DTW用于计算两个时间序列之间的相似性的算法,也可以理解找到两个时间序列之间的最佳匹配。DTW最著名的用途应该是用于语音识别。

 

Figure 1

DTW为什么会出现呢?

在计算两个序列相似性时,传统的度量方法如欧式距离、曼哈顿距离都会失效,或者说无法真正度量两个序列相似性。其原因是,这些距离度量方式是用一一对应的距离度量。

 

Figure 2 欧式距离

那么有没有一种根据序列的走势来计算相似性呢,比如序列A上某个点可能和序列B上多个点进行匹配。DTW就可以达到这种效果,如下图:

Figure 3  DTW

 

DTW算法形式

int DTWDistance(s: array [1..n], t: array [1..m]) {

   DTW := array [0..n, 0..m]

 

   for i := 1 to n

       DTW[i, 0] := infinity

   for i := 1 to m

       DTW[0, i] := infinity

   DTW[0, 0] := 0

 

   for i := 1 to n

       for j := 1 to m

           cost:= d(s[i], t[j])

           DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion

                                       DTW[i  , j-1],    // deletion

                                       DTW[i-1, j-1])    // match

 

   return DTW[n, m]

}

注意,

(1)     这个问题是一个动态规划问题,并且算法中经典问题——求字符串匹配的编辑距离——类似。

(2)     找两个序列的匹配路径,要从最末尾的dtw(n,m)往回找,而不是从dtw(1,1)往前搜。

 

Reference:

Distance Functions for Sequence Data and Time Series

https://en.wikipedia.org/wiki/Dynamic_time_warping

 



http://blog.sciencenet.cn/blog-212252-701037.html

上一篇:小白鼠成长日记2013年0213——缺乏讨论导致科研进度慢
下一篇:小白鼠成长日记20130621——听南洋理工大学的Xu dong的讲座

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-8-9 03:02

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部