DTW算法及快速计算技巧介绍 OS

信息发布员 6月前 151

Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping---- 论文介绍

今天要介绍一片关于DTW的论文,使用DTW进行计算的时候,会有计算量特别大,耗费时间长的问题,这篇论文就是介绍了怎么使用DTW算法在大数据集上快速计算的技巧。

  1. DTW简介
  2. DTW原理介绍
  3. 常用的加快DTW计算的方法
  4. 本论文中使用的技巧
  5. 总结

DTW简介

动态时间规整(Dynamic Time Warping, DTW)算法是1970年左右被提出一种相对古老的算法,它被应用于比较两个时间序列的相似性。从算法名中的Time Warping两个单词,我们可以知道DTW算法对序列的延展和压缩并不敏感,比如同一个单词apple,不同的人对这个单词的发音并不相同,但是这个算法能很好的识别它是同一个单词;再比如,下图中,两个时序序列,虽然两个序列不重合,但是,这两个序列的相似度很高的(DTW算法计算出的距离很小)。因此,DTW算法以及基于DTW改进的各种算法在语音识别领域有很多应用。当然,除此之外,在其他领域,比如股票等也有很多应用。

DTW原理

在讲解DTW之前,我们先来了解一下传统的欧几里得距离Euclidean distance )。

对于两个序列长度相同的  和  (|  | = |  | =  ),他们之间的欧几里得距离是

从公式中我们可以看出,欧几里得距离属于两个序列中的点是一对一模式的,但是DTW算法允许一对多模式,所以,也可以说欧几里得距离是DTW算法中的一种特例。

下面介绍一下DTW算法到底是什么?

对于两个长度不同的序列,我们仍然可以求它们之间的DTW距离,所以接下来,我们设置两个长度不同的序列  ,  。

计算方法:长度分别为  和  的时序列之间的DTW距离。

  1. 构建一个  的矩阵  ,其中第  个元素是  和  间的欧几里得距离。
  2. 在从起点  到终点  的路径中,搜索具有最小矩阵元素之和的路径。此时路径的元素总数即是DTW距离。

常用的加快DTW计算的方法

Using the squared distance:

我们在计算距离时用的都是欧几里得距离,在计算这个公式的时候,使用了根号,但是事实上,无论加不加这个根号,并不改变距离的相对大小排列顺序(我们只是找出最相似的那个,即相对距离最小的),因此,在计算的时候,我们可以跳过求平方查的计算,这样就大量节省计算时间。

Lower Bounding(下界):

对每个  序列来说,我们要在大量的候选序列中选出最相似的那个序列。如果每个候选序列都计算出和  的DTW距离,那么计算量无疑特别大,因此,我们使用lower bounding的技术,先剔除那些明显不相似的序列。对于怎么筛选序列,有许多不同的方法,下边介绍两种方法。

 方法:

如上图,先设定一个阈值,然后计算两序列的起始点和终点的距离,如果距离过大,就排除这个候选序列,不进行接下来的DTW距离计算;如果距离小于阈值,那么就计算DTW距离。

 方法:

基于 DTW 的距离计算方法,每次都要计算两条时间序列的 DTW 距离,时间复杂度是  。所以这个方法,就是先确定下界,然后计算和下界的距离,如果下界高于最小距离,就不需要进行 DTW 的计算;否则开始计算 DTW 的值。如果下界的计算速度足够快,并且下界足够精准的话,可以大量的压缩搜索的时间。

如上图,对于  ,根据它,设定了边  和  ,所以我们计算这两个边界和  的距离。在左半部分中  比  更靠近  ,所以我们计算  和  的距离,同理,右边计算  和  的距离。

Early abandoning of ED and LB_Keogh

我们在使用设定下界的方法的时候,不需要计算出  和下界的整体距离。比如,如图,当计算到第九个点的时候,如果这时的距离已经大于已有的最短距离,那么我们舍弃当前的候选序列,跳到下一个候选序列。

Early abandoning of DTW

在使用LB_Keogh 的时候,如下左图,我们需要计算从 k=0开始的所有点的下界和  的DTW距离,但是,这时候,我们先计算原来  和  , 在k = {0,1,...10} 之间的DTW距离,然后再从 k=11开始计算和下界的距离,如果两者之和大于  ,就舍弃这个候选序列。

本论文中提出提出的技巧

Early abandoning Z-Normalization

将原本的数据normalizaiton后的数据符合高斯分布。

Reordering Early Abandoning

之前讲的计算都是从左到右,但这个技巧是根据上面方法中计算出来的mean, 来选择先计算的点。如下图,可能从左到右计算,计算到第九个点的时候才能判断出当前序列距离较大,但是运用Reordering Early Abandoning 之后,右图,可能第五个点就可以作出判断。

Reversing the Query/Data Role in LB_Keogh

之前,我们是找  的下界,左图,现在他们反过来,寻找候选序列  的下界,右图。

Cascading Lower Bounds

组合使用各种加快计算的LB算法。(虚线上的为使用的,虚线下的是没使用的)

总结

DTW算法常被用于语音识别领域,股票预测等等。在这些实验中,可能会需要大量计算,因此,我们可以使用一些小trick,来缩小时间复杂度。


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


上一篇:通过Netflow进行攻击AS溯源
下一篇:火眼推出免费Windows攻击工具集
人生的价值,并不是用时间,而是用深度去衡量的。
最新回复 (0)
    • 少客联盟
      2
        登录 注册 QQ登录(停用)
返回