DTW算法初步理解 职业生涯

收集者 7月前 127

参考文献地址:原文:

blog.csdn.net/zouxy09/a


DTW(Dynamic Time Warping )动态时间规整算法,是一种计算2个时间序列尤其是不同长度序列相似度的一种动态规划算法。主要应用在时序数据上,比如孤立词语音识别、手势识别、数据挖掘以及信息检索等。

一、概述

时间序列是很常见的一种数据存在方式,而在大多数数据挖掘工作中,计算时间序列之间的相似度是经常遇到的任务。而在现实情况下,进行相似度计算的时间序列往往在时间轴上存在大致相似,但具体对应关系不得而知。例如两个人说同一个词,因为每个人的说话的音色,频率不同,所以虽然听起来都是同一个词的发音,但是在同一时刻的对应关系却不一定相同。就像图A所示,a点在形状上来看的话,更应该和b点相似,而不是同一时刻的b'点。假如通过传统的欧式距离进行计算的话,不会考虑时间上的动态变化,很明显会造成极大的误差。

因此,如何计算非等长时间序列的相似度就是一个问题,DTW的出现就是解决这个问题的。先看下经过时间规整后的对应关系就如图B所示,这2个时间序列在时间轴的并不是一一对齐的。

二、DTW如何计算?

DTW算法实质上是一个动态规划算法。假设我们又一个模板序列C、查询序列Q。他们的长度分别是m,n。

假如m=n的话,那可以不需要进行时间规整,直接计算欧式距离就可以计算出2个序列之间的距离。假如不等的话,则需要进行时间规整找出2个序列之间的最短距离。

为了进行对齐操作,我们需要先构造一个n x m的矩阵,矩阵元素(i,j)表示Qi 和Cj两个点之间的距离d(Qi,Cj),这个距离计算采用的是欧式距离,即d(Qi,Cj) = (Qi-Cj)²。DTW算法就是寻找一条从原点出发到(Qn,Cm)的最短路径。

我们定义路径为W,W的第k个元素定义为Wk = (i,j)k,第K个路径点Q与C的对齐关系。

由于时间序列数据的特点,在寻找路径之前需要有几个限制条件。

1、边界条件:

W1=(1,1)和Wk=(m,n)。任何的时间序列都符合这一条件,即开始和最后时刻的对齐是确定的,路径必须从左下角出发到右上角结束。

2、连续性:

如果Wk-1=(a',b'),那么对于下一个路径点Wk = (a,b)需要满足:(a-a')<=1和(b-b')<=1.即2个时序数据在对齐时,不会出现遗漏,跨越某个点进行对齐。

3、单调性:

如果Wk-1= (a’, b’),那么对于路径的下一个点Wk=(a, b)需要满足0<=(a-a’)和0<= (b-b’)。这限制W上面的点必须是随着时间单调进行的。以保证图B中的虚线不会相交。

这2个性质在路径上的体现就是下一个路径点的选择必须是右方、上方、右上方。

满足上述约束条件的路径有很多,但是我们需要求的是最短的路径:

分母中的K主要是用来对不同的长度的规整路径做补偿。我们的目的是什么?或者说DTW的思想是什么?是把两个时间序列进行延伸和缩短,来得到两个时间序列性距离最短也就是最相似的那一个warping,这个最短的距离也就是这两个时间序列的最后的距离度量。在这里,我们要做的就是选择一个路径,使得最后得到的总的距离最小。

这里我们定义一个累加距离cumulative distances。从(0, 0)点开始匹配这两个序列Q和C,每到一个点,之前所有的点计算的距离都会累加。到达终点(n, m)后,这个累积距离就是我们上面说的最后的总的距离,也就是序列Q和C的相似度。

累积距离γ(i,j)可以按下面的方式表示,累积距离γ(i,j)为当前格点距离d(i,j),也就是点qi和cj的欧式距离(相似性)与可以到达该点的最小的邻近元素的累积距离之和:

最佳路径是使得沿路径的积累距离达到最小值这条路径。这条路径可以通过动态规划(dynamic programming)算法得到。


少客联盟- 版权声明 1、本主题所有言论和图片纯属会员个人意见,与少客联盟立场无关。
2、本站所有主题由该帖子作者发表,该帖子作者收集者少客联盟享有帖子相关版权。
3、少客联盟管理员和版主有权不事先通知发贴者而删除本文。
4、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者收集者少客联盟的同意。
5、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任。
6、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责。
7、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意。
8、官方反馈邮箱:chinasuc@chinasuc.cn


上一篇:基于时间规整算法下的搜索挖掘大数量级的时间子序列
下一篇:招2000人来审核内容,他们是今日头条的数据勤杂工还是机器学习的训练师?
人生的价值,并不是用时间,而是用深度去衡量的。
最新回复 (0)
    • 少客联盟
      2
        登录 注册 QQ登录(停用)
返回